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

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

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

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

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

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

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

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

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

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

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

Методологія

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

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

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

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

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

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

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

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

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

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

Резюме

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

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

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

Безпека

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

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

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

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

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

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

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

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

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

Примітки

1. Christoph Ludwig. The Security and Efficiency of Micciancio's Cryptosystem // IACR Cryptology : article. — 2004.
2. T. Plantard, M. Rose, W. Susilo. Improvement of Lattice-Based Cryptography Using CRT. — Quantum Communication and Quantum Networking: First International Conference. — 2009. — С. 275—282. — .
3. M. Rose, T. Plantard, F. Susilo. Improving BDD Cryptosystems in General Lattices. — Information Security Practice and Experience: 7th International Conference. — 2011. — С. 152—167. — . з джерела 22 лютого 2019
4. Thomas Richard Rond (2016). Advances in the GGH lattice-based cryptosystem (PDF). Master Thesis.
5. Daniele Micciancio. Improving lattice-based cryptosystems using the Hermite normal form // International Cryptography and Lattices Conference. — 2001. — С. 126—145. — DOI:10.1007/3-540-44670-2_11. з джерела 20 липня 2020.
6. Steven Galbraith. Cryptosystems Based on Lattices // Cambridge University Press : paper. — 2012. — 16 червня. з джерела 12 лютого 2020.
7. Oded Goldreich, Shafi Goldwasser and Shai Halevi. Public-Key Cryptosystems from Lattice Reduction Problems // Advances in Cryptology - CRYPTO. — 1997. — 16 червня. з джерела 16 липня 2019.
8. Oded Regev. CVP Algorithm. — 2004. — 16 червня. з джерела 1 листопада 2020.
9. Noah Stephens-Davidowitz. Babai’s Algorithm. — 2016. — 16 червня. з джерела 29 жовтня 2019.

Література

• 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.