Криптосистема Міччанчо

Криптосистема Міччанчо — криптографічна система, заснована на схемі шифрування GGH, запропонована 2001 року професором Університету Каліфорнії в Сан-Дієго Данієлем Міччанчо.

Схема шифрування GGH спирається на криптографію на ґратках, яку вважають перспективною для використання в постквантових системах (оскільки криптосистеми, що використовують факторизацію цілих чисел, дискретне логарифмування, дискретне логарифмування на еліптичних кривих можуть бути ефективно зламані квантовим комп'ютером). Криптосистема Міччанчо, фактично, є покращенням схеми шифрування GGH, зі зменшенням вимог до розміру ключа та шифротексту в $N$ разів без погіршення безпеки системи, де $N$ — розмірність ґратки (для типових криптосистем становить кілька сотень). 2004 року Крістоф Людвіг емпірично показав, що для безпечного використання потрібно $N\ge 782$, до того ж, створення ключа і його дешифрування займає багато часу, а сам розмір ключа має бути більшим від 1 МБ. Тому ця криптосистема не може бути використана на практиці.

Основні поняття та позначення

Нехай $\mathrm{B}=\{{𝐛}_1,...,{𝐛}_N\}$, де ${𝐛}_i\in {ℝ}^M,i=\overline{1,N}$ — набір з $N$ лінійно незалежних векторів, і компоненти кожного з векторів є цілими числами, а $B$ — матриця з цих векторів розміру $M\times N$. Далі теорія будується для $M=N$. Ґраткою будемо називати множину $ℒ(\mathrm{B})=\{\mathrm{B}x\mid x\in {\mathbb{Z}}^M\}$.

Через те, що базис $\mathrm{B}$ може бути не унікальним, прийнято вибирати як базис ермітову нормальну форму, яка для кожної окремо взятої решітки унікальна. Це означає, що матриця, складена з векторів базису, є верхня трикутна, всі діагональні елементи строго додатні, інші елементи задовольняють $0\le b_{ij}<b_{ii}$. Цей вид матриць має такі корисні властивості. По-перше, через ортогоналізацію Грама — Шмідта така матриця зводиться до діагонального вигляду з елементами $b_{ii}$ на діагоналі. По-друге, визначник такої матриці дорівнює добутку її діагональних елементів, тобто $\det (\mathrm{B})={\prod }_{i=1}^n{b}_{ii}$.

З останнього також випливає важлива властивість цілих ґраток:

Нехай довільні вектори $v$ і $w$ такі, що $v_i\equiv w_{i}mod\det (\mathrm{B})$. В цьому випадку $v\in ℒ(\mathrm{B})$ тоді й лише тоді, коли $w\in ℒ(\mathrm{B})$.

Нехай $𝒫({\mathrm{B}}^{*})=\{\sum _i{x}_i{b}_{𝐢}^{\mathbf{*}}|0\le x_i<1\}$ — прямий паралелепіпед, де $x_i$ — цілочисельні координати, $b_{𝐢}^{\mathbf{*}}$ — ортогоналізовані за процесом Грама — Шмідта базисні вектори, $i=\overline{1,N}$. Простір ${ℝ}^N$ можна замостити такими паралелепіпедами. Тоді для будь-якого $v\in {\mathbb{Z}}^N$ існує унікальний вектор $w\in 𝒫({\mathrm{B}}^{*})$. Такий вектор називають редукованим для вектора $v\in {\mathbb{Z}}^N$ за модулем $\mathrm{B}$. Його отримують знаходженням відносної позиції $v$ в $z+𝒫({\mathrm{B}}^{*})$, де $z\in ℒ(\mathrm{B})$.

Цей вектор можна знайти за таким алгоритмом:

1. Знайти ${\alpha }_i=\frac{⟨v,b_i^{*}⟩}{⟨b_i^{*},b_i^{*}⟩}$
2. Обчислити вектор за формулою $w=v-\lfloor {\alpha }_i\rfloor {𝐛}_{𝐢}\in 𝒫({\mathrm{B}}^{*})$.

Методологія

У криптосистемах на ґратках ключами є базиси. Нехай $\mathrm{B}$ і $\mathrm{R}$ — публічний і приватний базиси однієї й тієї ж ґратки $ℒ=ℒ(\mathrm{B})=ℒ\mathrm{(}R)$. Відмінність цієї криптосистеми від системи шифрування GGH полягає в оптимальному виборі односторонньої функції. Важливою особливістю функції в криптосистемі Міччанчо є детермінованість. У цьому розділі будується загальний клас функцій вигляду GGH.

Клас односторонніх функцій вигляду GGH

Для схеми шифрування GGH одностороння функція набуває вигляду $c=\mathrm{B}x+ϵ$, де $c$ — шифротекст, $x$ — цілочисельний вектор і $ϵ$ — вектор помилки, завдовжки не більше $\rho$, $\frac{1}{2}\underset{i}{\min }(b_{𝐢}^{\mathbf{*}})\ll \rho =\frac{1}{2}\underset{i}{\min }(r_{𝐢}^{\mathbf{*}})$. Останнє необхідне для того, щоб помилка не створювала сильних спотворень під час обчислення з приватним базисом і, навпаки, для обчислень із публічним. Тут повідомлення $m$ кодується в $ϵ$, а $x$ вибирається випадково.

Сімейство односторонніх функцій GGH-виду $f_{\beta ,\gamma }$, параметризоване алгоритмами $\gamma$ і $\beta$, задовольняє:

1. $\beta$ приймає на вхід приватний базис $\mathrm{R}$, а виводить публічний базис $\mathrm{B}$ для тієї ж ґратки.
2. $\gamma$ отримує $\mathrm{B}$ і $ϵ$, а повертає коефіцієнти точки ґратки $x$
3. Тоді $f_{\beta ,\gamma }$ відображає множину векторів, коротших від $\rho$ так: $f_{\beta ,\gamma }(ϵ)=\beta (𝖱)\gamma (𝖱,ϵ)+ϵ$.

Якщо вектор помилки має довжину менше $\rho$ тоді приватний базис $\mathrm{R}$ можна використати для знаходження точки $\mathrm{B}x$, найближчою до $f_{\beta ,\gamma }(ϵ)$, і, відповідно, відновлення $ϵ$ (задача знаходження найближчого вектора).

Вибір публічного базису

Нехай відомий «хороший» приватний базис $\mathrm{R}$, тобто за допомогою нього можна розв'язати задачу знаходження найближчого вектора в $ℒ\mathrm{(}R)$, що те саме — розшифрувати шифротекст. Задача — згенерувати з $\mathrm{R}$ такий публічний базис $\mathrm{B}$, щоб мінімізувати в ньому інформацію про $\mathrm{R}$. У звичайній схемі шифрування GGH для знаходження $\mathrm{B}$ застосовують набір випадкових перетворень до $\mathrm{R}$. Криптосистема Міччанчо використовує як публічний базис $\mathrm{B}$ ермітову нормальну форму, тобто $\mathrm{B}=HNF(\mathrm{R})$ (HNF — Hermite Normal Form). Вона унікальна для конкретно заданої ґратки, як сказано вище. Це веде до того, що якщо є якийсь інший базис для цієї ґратки ${\mathrm{B}}^{\prime }$, то $\mathrm{B}=HNF(\mathrm{R})=HNF({\mathrm{B}}^{\prime })$. Отже, $\mathrm{B}$ містить про $\mathrm{R}$ не більше інформації, ніж про ${\mathrm{B}}^{\prime }$, на чому й ґрунтується безпека цієї криптосистеми.

Додання «випадкової» точки ґратки

Далі, потрібно зімітувати додання випадкової точки ґратки $\mathrm{B}x$. В ідеалі, ця точка повинна вибиратися рівномірно довільно серед усіх точок ґратки. Однак це неможливо ні з практичної, ні з теоретичної точки зору. Майже такий самий результат виходить при використанні редукованого вектора. Вектор помилки $ϵ$ зменшується за модулем публічного базису $\mathrm{B}$, щоб отримати шифротекст $c\in 𝒫({\mathrm{B}}^{*})$, замість додавання випадкового вектора. В результаті одностороння функція задається як $f(ϵ)=ϵ(\mathrm{mod}\mathrm{B})$, де $\mathrm{B}=HNF(\mathrm{R})$. Завдяки верхній трикутній формі матриці $\mathrm{B}$ ця функція дуже проста з обчислювальної точки зору. Застосовуючи міркування для обчислення редукованого вектора можна знайти формулу $x_i=\lfloor \frac{{ϵ}_i-\sum _{j>i}{b}_{ij}{x}_j}{b_{ii}}\rfloor$, починаючи з $x_N$, що дає унікальну точку в паралелепіпеді $𝒫({\mathrm{B}}^{*})$.

Резюме

Нехай $\mathrm{R}$ — приватний базис, причому $\rho =\frac{1}{2}\underset{i}{\min }(r_{𝐢}^{\mathbf{*}})$ є відносно великим, $\mathrm{B}$ — публічний базис і $\mathrm{B}=HNF(\mathrm{R})$. Базис $\mathrm{B}$ породжує функцію $f(ϵ)=ϵ(\mathrm{mod}\mathrm{B})$, яка переводить вектор довжини менше $\rho$ у відповідний $\mathrm{B}$ прямий паралелепіпед $𝒫({\mathrm{B}}^{*})$. Ключові моменти:

1. Навіть якщо спочатку $f(ϵ)$ близька до точки $ϵ$, після операції редукції виходить вектор, близький до інших точок ґратки.
2. Щоб відновити $ϵ$ за $f(ϵ)$, необхідно розв'язати задачу знаходження найближчого вектора, для якої доведено NP-складність. Тому відновити $ϵ$, маючи тільки $\mathrm{B}$, майже неможливо, навіть для квантових комп'ютерів. Однак вона ефективно розв'язується, якщо відомий базис $\mathrm{R}$.
3. Найближча точка до $f(ϵ)$ — центр паралелепіпеда, в якому міститься $f(ϵ)$, а його знайти легко, знаючи базис $\mathrm{R}$.

Теоретичний аналіз

Безпека

Нова функція цієї криптосистеми настільки ж безпечна, як функція в схемі шифрування GGH. Така теорема стверджує, що наведена вище функція, як мінімум, не гірша від будь-якої іншої функції вигляду GGH:

Для будь-яких функцій

$\beta ,\gamma$

і для будь-якого алгоритму, який для

$f(ϵ)$

знаходить про

$ϵ$

якусь часткову інформацію з ненульовою ймовірністю, існує ефективний алгоритм зі входом

$f_{\beta ,\gamma }(ϵ)$

, здатний відновити таку ж інформацію з такою ж імовірністю успіху.

Доведення: нехай

$A$

 — алгоритм здатний зламати

$f$

. Дано публічний базис

$\mathrm{B}$

=

$\beta (ϵ)$

та шифротекст

$c=\mathrm{B}\gamma +ϵ$

. Алгоритм злому повинен спробувати знайти якусь інформацію про

$ϵ$

. По перше,

${\mathrm{B}}^{\prime }=HNF(\mathrm{B})$

і

$c^{\prime }=c(\mathrm{mod}{B}^{\prime })$

. З теоретичних результатів у попередньому розділі випливає, що

${\mathrm{B}}^{\prime }=HNF(\mathrm{R})$

і

$c^{\prime }=\mathrm{B}\gamma +ϵ(\mathrm{mod}{B}^{\prime })=ϵ(\mathrm{mod}{B}^{\prime })$

. Тому

$B^{\prime }$

і

$c^{\prime }$

мають правильний розподіл. Застосовуючи до них алгоритм

$A$

, отримуємо твердження теореми.

Асимптотичні оцінки пам'яті

Нехай для приватного ключа виконується $|r_{ij}|<poly(N)$, тоді розмір, займаний ключем, оцінюється $O(N^2\lg N^2)$. Використовуючи нерівність Адамара, а також те, що для публічного базису та шифротексту GGH системи виконуються оцінки $O(N^2\lg (\det (ℒ)))=O(N^2\lg (N))$ і $O(N\lg (\det (ℒ)))=O(N\lg (N))$, випливає, що оцінки для публічного базису й шифротексту нашої системи $O(N^2\lg (N))$ і $O(N\lg (N))$.

Асимптотичні оцінки часу виконання

Теоретично, очікується прискорення роботи алгоритму порівняно з GGH із двох причин (емпіричні результати наведено нижче). По-перше, час шифрування для GGH систем залежить від розміру публічного ключа. Теоретичні оцінки на займану ключем пам'ять свідчать про її зменшення, отже й про прискорення шифрування. При цьому час роботи GGH можна порівняти з часом роботи схеми RSA. По-друге, для генерування ключа початковий алгоритм застосовує алгоритм Ленстри — Ленстри — Ловаса до матриць великої розмірності з великими значеннями елементів, тоді як система Міччанчо використовує досить простий алгоритм знаходження ермітової нормальної форми. Для дешифрування використовується алгоритм Бабая, з деякими втратами пам'яті та точності, але поліпшенням за часом його можна замінити простішим алгоритмом округлення, проте в цій частині прискорення за часом виконання не очікується.

Емпірична оцінка безпеки системи

На практиці для безпеки цієї системи потрібно $N\ge 782$. За припущення, що покращення часу досягає максимальних асимптотичних оцінок, найменше необхідне $N$ має бути більше $2093$. Далі було показано, що публічний ключ має бути не менше ніж 1 МБ. Більш того, час створення ключа займає порядку доби. Процедура шифрування справді досить швидка. Однак дешифрування нестабільне через алгоритм Бабая. Це можна подолати, але тоді вона займатиме 73 хвилини для $N=800$ не включаючи ортогоналізації. Якщо виконати цей крок заздалегідь, то до витрат пам'яті додається 4.8 МБ для тієї ж розмірності. З цих результатів випливає, що криптосистема Міччанчо незастосовна на практиці.

Література

• Daniele Micciancio, Oded Regev Lattice-основана криптографія // Post Quantum Cryptography. — 2009.
• Daniele Micciancio Improving lattice-базовані cryptosystems з використанням Hermite normal form // Lecture notes in Computer Science. — 2001.
• Christoph Ludwig The Security and Efficiency of Micciancio's Cryptosystem // IACR Cryptology. — 2004.