NTRUSign (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-размерным вектором. Это позволяет представлять открытые ключи в $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},\ldots ,f_{N-1}]$ и $g=[g_{0},g_{1},\ldots ,g_{N-1}]$ является $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$ , строка $t=standard$ или $transpose$ .
Генерация $B$ закрытых решёточных базисов и один открытый решеточный базис

Установить

i=B

. До тех пор, пока

i>0

:

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

Если

t=transpose

, установить

f_{i}=f

и

f'_{i}=g

.

Вычислить

h_{i}=f_{i}^{-1}*f'_{i}modq

. Установить

i=i-1

.

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

Подпись

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

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

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

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

Верификация требует такую же хеш-функцию $H$ , «нормирующую связь» ${\mathcal {N}}\in \mathbb {R}$ и норму полинома $||.||$ . Норма $||t||$ полинома $t$ определяется как $\inf _{0\leq k<q}||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\operatorname {mod} g))||$ .
подпись считается верной, если $b<{\mathcal {N}}$ .

Замечание

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

Примечания

↑ Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. NTRUSign: Digital Signatures Using the NTRU Lattice. Архивировано 30 января 2013 года.

Ссылки

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

[1] Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. NTRUSign: Digital Signatures Using the NTRU Lattice. Архивировано 30 января 2013 года.

[1]