NTRUSign

NTRUSign, также известный как NTRU Signature Algorithm, является ключевым алгоритмом шифрования с открытым ключом цифровой подписи на основе схемы подписи GGH.

История

Впервые алгоритм был представлен на сессии en:Asiacrypt 2001 года и опубликован в рецензируемой форме на конференции RSA 2003 года^[1]. Издание 2003 года включало рекомендации параметров для уровня безопасности 80 бит. В следующей публикации 2005 года были пересмотрены рекомендации для уровня безопасности 80 бит, а также представлены параметры востребованных уровней безопасности 112, 128, 160, 192 и 256 бит и описаны алгоритмы для получения наборов параметров для любого желаемого уровня безопасности. NTRU Cryptosystems, Inc. подали заявку на патент на данный алгоритм.^{[когда?]}

Особенности

NTRUSign включает в себя отображение сообщения для случайной точки в 2N-мерном пространстве, где N является одним из параметров NTRUSign, и решение проблемы нахождения ближайшего вектора в решётке, тесно связанной с решёткой NTRUEncrypt. Данная решётка обладает свойством: частный 2N-мерный базис для решётки можно описать с помощью 2-х векторов, каждый из которых состоит из N коэффициентов и базиса, который может быть определён отдельным N-размерным вектором. Это позволяет представлять открытые ключи в ${\displaystyle O(N)}$ пространстве, а не ${\displaystyle O(N^{2})}$, как и в случае с другими схемами подписи на основе решёток. Операции занимают ${\displaystyle O(N^{2})}$ времени, в отличие от ${\displaystyle O(N^{3})}$ для криптографии на эллиптических кривых и RSA. Поэтому NTRUSign быстрее данных алгоритмов при низких уровнях безопасности и значительно быстрее при высоких уровнях безопасности.

NTRUSign находится в стадии рассмотрения по стандартизации рабочей группой IEEE P1363.

Описание алгоритма

Так же как и в NTRUEncrypt, в NTRUSign вычисления производятся в кольце ${\displaystyle R=\mathbb {Z} _{q}[X]/(X^{N}-1)}$, где умножение „${\displaystyle *}$“ является циклической сверткой по модулю ${\displaystyle q}$. Произведением двух полиномов ${\displaystyle f=[f_{0},f_{1},\ldots ,f_{N-1}]}$ и ${\displaystyle g=[g_{0},g_{1},\ldots ,g_{N-1}]}$ является ${\displaystyle f*g=\sum _{i+j\equiv k\mod N}f_{i}\cdot g_{j}\mod q}$.

За основу NTRUSign могут быть взяты стандартные или транспонированные решетки. Основное преимущество транспонированной решетки заключается в том, что коэффициенты многочлена принадлежат {-1,0,1}. Это увеличивает скорость умножения.

Генерация ключа

• Входные данные: целые ${\displaystyle N,q,d_{f},d_{g},B>0}$, строка ${\displaystyle t=standard}$ или ${\displaystyle transpose}$.
• Генерация ${\displaystyle B}$ закрытых решёточных базисов и один открытый решеточный базис

Установить ${\displaystyle i=B}$. До тех пор, пока ${\displaystyle i>0}$:

1. Произвольно выбрать ${\displaystyle f}$, ${\displaystyle g}$ ∈ ${\displaystyle \mathbb {R} }$, взаимно простые с ${\displaystyle d_{f}}$, ${\displaystyle d_{g}}$ соответственно.
2. Найти малые ${\displaystyle F,G\in R}$ такие, что ${\displaystyle f*G-F*g=q}$.
3. Если ${\displaystyle t=standard}$, установить ${\displaystyle f_{i}=f}$ и ${\displaystyle f'_{i}=F}$.

Если ${\displaystyle t=transpose}$, установить ${\displaystyle f_{i}=f}$ и ${\displaystyle f'_{i}=g}$.

Вычислить ${\displaystyle h_{i}=f_{i}^{-1}*f'_{i}modq}$. Установить ${\displaystyle i=i-1}$.

• Публичный ключ: входные параметры и ${\displaystyle h=ho=f_{0}^{-1}*f'_{0}\operatorname {mod} q}$.
• Закрытый ключ: ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\}}$ для ${\displaystyle i=0...B}$.

Подпись

Подпись требует хеш-функцию ${\displaystyle H:{\mathcal {D}}\rightarrow R}$ на цифровом пространстве документа ${\displaystyle {\mathcal {D}}}$.

• Входные данные: цифровой документ ${\displaystyle D\in {\mathcal {D}}}$ и закрытый ключ ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\}}$ для ${\displaystyle i=0...B}$.
• Установить ${\displaystyle r=0}$.
• Установить ${\displaystyle s=0}$ и ${\displaystyle i=B}$. Представить ${\displaystyle r}$ как строку бит. Установить ${\displaystyle m_{o}=H(D||r)}$, где ${\displaystyle ||}$ обозначает конкатенацию. Установить ${\displaystyle m=m_{o}}$.

1. ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\}}$ - ${\displaystyle i}$-е основание
2. Вычислить ${\displaystyle x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil }$
3. Вычислить ${\displaystyle y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil }$
4. ${\displaystyle s_{i}=x*f+y*f'}$
5. ${\displaystyle m_{i}=si*(h_{i}-h_{i-1})\mod q}$
6. Подпись: ${\displaystyle s=s+s_{i}}$

Проверка подписи

Верификация требует такую же хеш-функцию ${\displaystyle H}$, «нормирующую связь» ${\displaystyle {\mathcal {N}}\in \mathbb {R} }$ и норму полинома ${\displaystyle ||.||}$. Норма ${\displaystyle ||t||}$ полинома ${\displaystyle t}$ определяется как ${\displaystyle \inf _{0\leq k<q}||t+kq||_{z}}$, где ${\displaystyle ||r||_{z}=\sum _{i=0}^{N-1}r_{i}^{2}-{\frac {1}{N}}\sum _{i=0}^{N}r_{i}}$ (где последнее - евклидова норма).

• Входные данные: Подписанные данные ${\displaystyle (D,r,s)}$ и публичный ключ ${\displaystyle h}$.
• Представить r как строку бит. Установить ${\displaystyle m=H(D||r)}$.
• Вычислить ${\displaystyle b=||(s,s*h-m\operatorname {mod} g))||}$.
• подпись считается верной, если ${\displaystyle b<{\mathcal {N}}}$.

Замечание

• Рекомендуемые параметры ${\displaystyle (N,q,d_{f},d_{g},B,t,{\mathcal {N}})=(251,128,73,71,1,transpose,310)}$

Примечания

Ссылки

• Most recent NTRUSign paper, including parameter sets for multiple security levels
• A Java implementation of NTRUSign Архивная копия от 23 декабря 2015 на Wayback Machine