NTRUSign

	NTRUSign
Ґрунтується на	Goldreich-Goldwasser-Halevi signature schemed
Дата публікації	1999
Описано за адресою	www3.ntu.edu.sg/home/wuhj/research/publications/2000_ACISP_PASS.pdf; math.brown.edu/~jpipher/NTRUSign_RSA.pdf

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 швидше даних алгоритмів при низьких рівнях безпеки і значно швидше при високих рівнях безпеки.^[2]^[3]

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,E,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}$ (де останнє — Евклідова норма).