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)$  пространстве, а не $O(N^2)$$O(N^{2})$ , как и в случае с другими схемами подписи на основе решёток. Операции занимают $O(N^2)$$O(N^{2})$  времени, в отличие от $O(N^3)$$O(N^{3})$  для криптографии на эллиптических кривых и RSA. Поэтому NTRUSign быстрее данных алгоритмов при низких уровнях безопасности и значительно быстрее при высоких уровнях безопасности.

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

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

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

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

Генерация ключаПравить

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

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

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

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

Вычислить $h_i=f_i^{-<!--\; -\; -->1}\ast <!--\; \ast \; -->f_i^{\prime }modq$$h_{i}=f_{i}^{-1}*f'_{i}modq$ . Установить $i=i-<!--\; -\; -->1$$i=i-1$ .

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

ПодписьПравить

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

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

1. $\left\{f_i,f_i^{\prime },h_i\right\}$$\left\{f_{i},f'_{i},h_{i}\right\}$  - $i$$i$ -е основание
2. Вычислить $x=\lfloor <!--\; \lfloor \; -->-<!--\; -\; -->\frac{1}{q}{m}_i\ast <!--\; \ast \; -->f_i^{\prime }\rceil <!--\; \rceil \; -->$$x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil$ 
3. Вычислить $y=\lfloor <!--\; \lfloor \; -->\frac{1}{q}{m}_i\ast <!--\; \ast \; -->f_i\rceil <!--\; \rceil \; -->$$y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil$ 
4. $s_i=x\ast <!--\; \ast \; -->f+y\ast <!--\; \ast \; -->f^{\prime }$$s_{i}=x*f+y*f'$ 
5. $m_i=si\ast <!--\; \ast \; -->(h_i-<!--\; -\; -->h_{i-<!--\; -\; -->1})\mathrm{mod}q$$m_{i}=si*(h_{i}-h_{i-1})\mod q$ 
6. Подпись: $s=s+s_i$$s=s+s_{i}$ 

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

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

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

ЗамечаниеПравить

• Рекомендуемые параметры $(N,q,d_f,d_g,B,t,\mathcal{N})=(251,128,73,71,1,transpose,310)$$(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