NTRUSign

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

История

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

Особенности

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

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

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

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

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

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

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

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

1. Произвольно выбрать $f$, $g$ ∈ $ℝ$, взаимно простые с $d_f$, $d_g$ соответственно.
2. Найти малые $F,G\in R$ такие, что $f*G-F*g=q$.
3. Если $t=standard$, установить $f_i=f$ и $f{\text{'}}_i=F$.

Если $t=transpose$, установить $f_i=f$ и $f{\text{'}}_i=g$.

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

• Публичный ключ: входные параметры и $h=ho=f_0^{-1}*f{\text{'}}_0\mathrm{mod}q$.
• Закрытый ключ: $\{f_i,f{\text{'}}_i,h_i\}$ для $i=0...B$.

Подпись

Подпись требует хеш-функцию $H:𝒟\to R$ на цифровом пространстве документа $𝒟$.

• Входные данные: цифровой документ $D\in 𝒟$ и закрытый ключ $\{f_i,f{\text{'}}_i,h_i\}$ для $i=0...B$.
• Установить $r=0$.
• Установить $s=0$ и $i=B$. Представить $r$ как строку бит. Установить $m_o=H(D||r)$, где $||$ обозначает конкатенацию. Установить $m=m_o$.

1. $\{f_i,f{\text{'}}_i,h_i\}$ - $i$-е основание
2. Вычислить $x=\lfloor -\frac{1}{q}{m}_i*f{\text{'}}_i\rceil$
3. Вычислить $y=\lfloor \frac{1}{q}{m}_i*f_i\rceil$
4. $s_i=x*f+y*f^{\prime }$
5. $m_i=si*(h_i-h_{i-1})modq$
6. Подпись: $s=s+s_i$

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

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

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

Замечание

• Рекомендуемые параметры $(N,q,d_f,d_g,B,t,𝒩)=(251,128,73,71,1,transpose,310)$

Ссылки

• Most recent NTRUSign paper, including parameter sets for multiple security levels
• A Java implementation of NTRUSign Шаблон:Wayback