Криптографія на ґратках

Криптогра́фія на ґра́тках — підхід до побудови алгоритмів асиметричного шифрування з використанням задач теорії ґраток, тобто задач оптимізації на дискретних адитивних підгрупах, заданих на множині $\mathbb {R} ^{n}$.

Поряд з іншими методами постквантової криптографії вважається перспективним завдяки можливостям квантового комп'ютера зламувати широко використовувані асиметричні системи шифрування, засновані на двох типах задач теорії чисел: задачах факторизації цілих чисел і задачах дискретного логарифмування. Складність зламування алгоритмів, побудованих на ґратках, дуже велика, найкращі алгоритми ледь можуть розв'язати цю задачу за експоненційний час. Станом на середину 2010-х років невідомо жодного квантового алгоритму, здатного впоратися краще від звичайного комп'ютера.

Передумови створення

1995 року Пітер Шор продемонстрував поліноміальний алгоритм для зламування криптографічних систем з відкритим ключем при використанні квантового комп'ютера, визначивши тим самим період існування цих систем до виникнення квантових обчислювачів достатньої розмірності.

У 1996 році Лов Грувер продемонстрував загальний метод пошуку в базі даних, що дозволяє розшифровувати симетричні алгоритми шифрування, еквівалентну зменшенню ключа шифру вдвічі.

2001 року група фахівців IBM продемонструвала виконання алгоритму факторизації Шора. Число 15 розклали на множники 3 і 5 за допомогою квантового комп'ютера з 7 кубітами, побудованого з 18¹⁰ молекул, що складаються з п'яти атомів фтору та двох атомів вуглецю, із записом інформації за допомогою радіосигналів та зчитування методами ядерного магнітного резонансу.

Починаючи від другої половини 1990-х років виникла необхідність пошуку криптостійких до квантових комп'ютерів задач для постквантової епохи шифрування, як один з підходів запропоновано використовувати ґратки в $\mathbb {R} ^{n}$ — дискретні підгрупи дійсного векторного простору, лінійні оболонки яких збігаються з ним:

$L=\left\{\sum _{i=1}^{n}\lambda _{i}b_{i}\mid \lambda _{i}\in \mathbb {Z} \right\}$

Обчислювально складні задачі

Синьою крапкою позначено найкоротший вектор

Задача пошуку найкоротшого вектора (SVP, англ. Shortest Vector Problem) — знайти в заданому базисі решітки ненульовий вектор за відношенням до певної нормалі.

Задачу пошуку (приблизно) ідеального найкоротшого вектора (ISVP, англ. (approximate) ideal shortest vector problem) не вважають NP-складною. Проте, немає відомих ґраток, заснованих на методі редукції, значно ефективніших на ідеальних структурах, ніж на загальних.

Ще одна задача — пошук (приблизно) найкоротшого незалежного вектора (SIVP, англ. (approximate) shortest independent vectors problem), в якій дано базис ґратки $B$ і потрібно знайти $n$ лінійно незалежних векторів.

Синя крапка — знайдений вектор, червона крапка — заданий вектор

Задача пошуку найближчого вектора (CVP, англ. Closest Vector Problem) — знаходження вектора в ґратці за заданим базисом і деяким вектором, що не належить ґратці, при цьому якомога ближчого за довжиною до заданого вектора.

LLL-алгоритм

Приклад роботи алгоритму LLL. Червоним зображено новий базис.

Всі ці задачі можна розв'язати за поліноміальний час за допомогою відомого LLL-алгоритму, який винайшли 1982 року Ар'єн Ленстра, Хендрик Ленстра і Ласло Ловас.

У заданому базисі $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$, з n -вимірними цілими координатами, у ґратці $L$ з $\mathbb {R} ^{n}$, де $\ d\leq n$, LLL-алгоритм знаходить коротший (промірно^{[уточнити]}) ортогональний базис за час:

$O(d^{5}n\log ^{3}B)$,

де $B$ — найбільша довжина вектора $b_{i}$ в цьому просторі.

Основні криптографічні конструкції та їх стійкість

Шифрування

GGH — криптосистема заснована на CVP, а саме на односторонній функції з таємним входом, що спирається на складність редукції ґратки. Опубліковано 1997 року. Знаючи базис, можна згенерувати вектор близький до заданої точки, але щоб за відомим цим вектором знайти початкову точку, потрібен початковий базис. Алгоритм перевірено 1999 року.

Реалізація GGH

GGH складається з відкритого та секретного ключів.

Секретний ключ — це базис $B$ ґратки $L$ та унімодулярна матриця $U$.

Відкритий ключ — деякий базис у ґратці $L$ у вигляді $B'=UB$.

Для деякого $M$, простір повідомлення складається з вектора $(\lambda _{1},...,\lambda _{n})$, де $-M<\lambda _{i}<M$.

Шифрування

Задано повідомлення $m=(\lambda _{1},...,\lambda _{n})$, спотворення $e$, відкритий ключ $B'$:

$v=\sum \lambda _{i}b_{i}'$

У матричному вигляді:

$v=m\cdot B'$.

$m$ складається із цілих значень, $b'$ точка ґратки, і $v$ також точка ґратки. Тоді шифротекст:

$c=v+e=m\cdot B'+e$

Розшифрування

Для розшифрування необхідно обчислити:

$c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B^{-1}=m\cdot U+e\cdot B^{-1}$

Частина $e\cdot B^{-1}$ забирається, з міркувань наближення. Повідомлення:

$m=m\cdot U\cdot U^{-1}$

Приклад

Виберемо ґратку $L\subset \mathbb {R} ^{2}$ із базисом $B$:

$B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}$ and $B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}$

де

$U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}$ і

$U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}$

В результаті:

$B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}$

Нехай повідомлення $m=(3,-7)$ та вектор помилки $e=(1,-1)$. Тоді шифротекст:

$c=mB'+e=(-104,-79)$.

Для розшифрування необхідно обчислити:

$cB^{-1}=\left({\frac {-104}{7}},{\frac {-79}{3}}\right)$.

Округлення дає $(-15,-26)$, відновимо повідомлення:

$m=(-15,-26)U^{-1}=(3,-7)$.

NTRUEncrypt — криптосистема, заснована на SVP, альтернатива для RSA та ECC. В обчисленні використовується кільце многочленів.

Підпис

Схему підпису GGH, засновану на складності знаходження найближчого вектора, вперше запропонував 1995 року і опублікував 1997 року Голдріх. Ідея полягала у використанні ґраток, для яких «поганий» базис (вектори довгі і майже паралельні) є відкритим і «хороший» базис із короткими та майже ортогональними векторами є закритим. За цим методом, повідомлення необхідно хешувати в простір, натягнутий на ґратку, а підпис для цього хеша в цьому просторі є найближчим вузлом ґратки. Схема не мала формального доведення безпечності, і її базовий варіант 1999 року зламав Нгуен (Nguyen). 2006 року модифіковану версію знову зламали Нгуен і Реґев.

NTRUSign — спеціальна, ефективніша версія підпису GGH, що відрізняється меншим ключем та розміром підпису. Вона використовує тільки ґратки підмножини множини всіх ґраток, пов'язаних з деякими поліноміальними кільцями. NTRUSign запропоновано на розгляд як стандарт IEEE P1363.1.

Див. також

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