Криптография на решётках

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}}}$ and ${\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.