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

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

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

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

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

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

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

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

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

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

1. Знайти ${\textstyle \alpha _{i}={\frac {\langle v,b_{i}^{*}\rangle }{\langle b_{i}^{*},b_{i}^{*}\rangle }}}$
2. Обчислити вектор за формулою $w=v-\lfloor \alpha _{i}\rfloor \mathbf {b_{i}} \in {\mathcal {P}}(\mathrm {B} ^{*})$.

Методологія

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

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

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

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

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

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

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

Нехай відомий «хороший» приватний базис $\mathrm {R}$, тобто за допомогою нього можна розв'язати задачу знаходження найближчого вектора в ${\mathcal {L}}\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} '$, то $\mathrm {B} =HNF(\mathrm {R} )=HNF(\mathrm {\mathrm {B} '} )$. Отже, $\mathrm {B}$ містить про $\mathrm {R}$ не більше інформації, ніж про $\mathrm {B} '$, на чому й ґрунтується безпека цієї криптосистеми.

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

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

Резюме

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

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

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

Безпека

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

Для будь-яких функцій $\beta ,\gamma$ і для будь-якого алгоритму, який для $f(\epsilon )$ знаходить про $\epsilon$ якусь часткову інформацію з ненульовою ймовірністю, існує ефективний алгоритм зі входом $f_{\beta ,\gamma }(\epsilon )$, здатний відновити таку ж інформацію з такою ж імовірністю успіху.

Доведення: нехай $A$ — алгоритм здатний зламати $f$. Дано публічний базис $\mathrm {B}$ = $\beta (\epsilon )$ та шифротекст $c=\mathrm {B} \gamma +\epsilon$. Алгоритм злому повинен спробувати знайти якусь інформацію про $\epsilon$. По перше, $\mathrm {B} '=HNF(\mathrm {B} )$ і $c'=c{\pmod {B'}}$. З теоретичних результатів у попередньому розділі випливає, що $\mathrm {B} '=HNF(\mathrm {R} )$ і $c'=\mathrm {B} \gamma +\epsilon {\pmod {B'}}=\epsilon {\pmod {B'}}$. Тому $B'$ і $c'$ мають правильний розподіл. Застосовуючи до них алгоритм $A$, отримуємо твердження теореми.

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

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

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

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

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

На практиці для безпеки цієї системи потрібно $N\geq 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.