Криптография на решётках — подход к построению алгоритмов асимметричного шифрования с использованием задач теории решёток, то есть задач оптимизации на дискретных аддитивных подгруппах, заданных на множестве ${\displaystyle \mathbb {R} ^{n))$.

Наряду с другими методами постквантовой криптографии, считается перспективным в связи с возможностями квантового компьютера взламывать широко используемые асимметричные системы шифрования, основанные на двух типах задач теории чисел: задачах факторизации целых чисел и задачах дискретного логарифмирования. Сложность взлома алгоритмов, построенных на решётках, крайне велика, самые лучшие алгоритмы могут решить эту задачу с трудом за экспоненциальное время. По состоянию на середину 2010-х годов неизвестно ни одного квантового алгоритма, способного справиться лучше обычного компьютера.

В 1995 году Питер Шор продемонстрировал полиномиальный алгоритм для взлома криптографических систем с открытым ключом при использовании квантового компьютера, тем самым определив период существования данных систем до возникновения квантовых вычислителей достаточной размерности.

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

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

Начиная со второй половины 1990-х годов возникла необходимость поиска криптостойких к квантовым компьютерам задач для постквантовой эпохи шифрования, в качестве одного из подходов было предложено использовать решётки в ${\displaystyle \mathbb {R} ^{n))$ — дискретные подгруппы вещественного векторного пространства, линейные оболочки которых совпадают с ним:

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

Задача нахождения кратчайшего вектора (SVP, англ. Shortest Vector Problem) — найти в заданном базисе решётки ненулевой вектор по отношению к определённой нормали^[2].

Задача нахождения (приблизительно) идеального кратчайшего вектора (ISVP, англ. (approximate) ideal shortest vector problem) не считается NP-сложной. Однако, нет известных решёток, основанных на методе редукции, значительно более эффективных на идеальных структурах, чем на общих^[3].

Ещё одна задача — нахождение (приблизительно) кратчайшего независимого вектора (SIVP, англ. (approximate) shortest independent vectors problem), в которой дан базис решётки ${\displaystyle B}$ и требуется найти ${\displaystyle n}$ линейно независимых векторов^[4].

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

Все эти задачи разрешимы за полиномиальное время с помощью известного LLL-алгоритма изобретённого в 1982 году Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом^[5].

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

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

где ${\displaystyle B}$ — это максимальная длина вектора ${\displaystyle b_{i))$ в этом пространстве.

GGH^[англ.] — криптосистема основанная на CVP, а именно на односторонней функции с потайным входом опирающуюся на сложность редукции решётки. Была опубликована в 1997 году. Зная базис, можно сгенерировать вектор близкий к заданной точке, но зная это вектор нам необходим исходный базис, чтобы найти исходную точку. Алгоритм был проверен в 1999 году.

GGH состоит из открытого и секретного ключа.

Секретный ключ — это базис ${\displaystyle B}$ решётки ${\displaystyle L}$ и унимодулярная матрица ${\displaystyle U}$.

Открытый ключ — некоторый базис в решётке ${\displaystyle L}$ в виде ${\displaystyle B'=UB}$.

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

Задано сообщение ${\displaystyle m=(\lambda _{1},...,\lambda _{n})}$, искажение ${\displaystyle e}$, открытый ключ ${\displaystyle B'}$:

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

В матричном виде:

${\displaystyle v=m\cdot B'}$.

${\displaystyle m}$ состоит из целых значений, ${\displaystyle b'}$ точка решётки, и v также точка решётки. Тогда шифротекст:

${\displaystyle c=v+e=m\cdot B'+e}$

Для расшифрования необходимо вычислить:

${\displaystyle 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))$

Часть ${\displaystyle e\cdot B^{-1))$ убирается, из соображений приближения. Сообщение:

${\displaystyle m=m\cdot U\cdot U^{-1))$

Выберем решётку ${\displaystyle L\subset \mathbb {R} ^{2))$ с базисом ${\displaystyle B}$:

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

где

${\displaystyle U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix))}$ и

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

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

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

Пусть сообщение ${\displaystyle m=(3,-7)}$ и вектор ошибки ${\displaystyle e=(1,-1)}$. Тогда шифротекст:

${\displaystyle c=mB'+e=(-104,-79)}$.

Для расшифровки необходимо вычислить:

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

Округление даёт ${\displaystyle (-15,-26)}$ , восстановим сообщение:

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

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

Схема подписи GGH впервые предложена 1995 году и опубликована в 1997 году Голдрихом, основана на сложности нахождения ближайшего вектора. Идея заключалась в использовании решёток, для которых «плохой» базис, векторы длинные и почти параллельные, является открытым и «хороший» базис с короткими и почти ортогональными векторами, является закрытым. По их методу, сообщение необходимо хешировать в пространство, натянутое на решётку, а подпись для данного хэша в этом пространстве является ближайшим узлом решётки. Схема не имела формального доказательства безопасности, и её базовый вариант был взломан в 1999 году Нгуэном (Nguyen). В 2006 году модифицированная версия была снова взломана Нгуэном и Реджевом (Regev).

NTRUSign — специальная, более эффективная версия подписи GGH, отличающаяся меньшим ключом и размером подписи. Она использует только решётки подмножества множества всех решёток, связанных с некоторыми полиномиальными кольцами. NTRUSign была предложена на рассмотрение в качестве стандарта IEEE P1363.1.

Криптосистемы с открытым ключом
Алгоритмы	Факторизация целых чисел Криптосистема Бенало Блюма — Гольдвассер Cayley–Purser Дамгорда — Юрика GMR Гольдвассер — Микали Накаша — Штерна Пэйе Рабина RSA Окамото — Утиямы Schmidt–Samoa Дискретное логарифмирование BLS Крамера – Шоупа Протокол Диффи — Хеллмана DSA ECDH Curve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Обмен зашифрованными ключами Схема Эль-Гамаля signature scheme MQV Схема Шнорра SPEKE SRP STS Криптография на решётках NTRUEncrypt NTRUSign Обмен ключами на основе обучения с ошибками Подпись на основе обучения с ошибками в кольце BLISS NewHope Другие AE CEILIDH EPOC Скрытые уравнения поля IES Подпись Лэмпорта McEliece Ранцевая криптосистема Меркла — Хеллмана Naccache–Stern knapsack cryptosystem Трёхэтапный протокол XTR
Теория	Дискретное логарифмирование на эллиптической кривой Эллиптическая криптография Hash-based cryptography Некоммутативная криптография RSA problem Односторонняя функция с потайным входом
Стандарты	CRYPTREC IEEE P1363 NESSIE NSA Suite B Post-Quantum Cryptography
Темы	Электронная подпись OAEP Fingerprint PKI Web of trust Размер ключа Identity-based cryptography Постквантовая криптография OpenPGP card