NTRUSign

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

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

Історія

Вперше алгоритм був представлений на сесії 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},\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$:

1. Довільно обрати $f$, $g$ ∈ $\mathbb {R}$ взаємно прості з $d_{f}$, $d_{g}$ відповідно.
2. Знайти малі $F,G,E,R$ такі, що $f*G-F*g=q$.
3. Якщо $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}$.

1. $\left\{f_{i},f'_{i},h_{i}\right\}$ — $i$-та підстава
2. Обчислити $x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil$
3. Обчислити $y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil$
4. $s_{i}=x*f+y*f'$
5. $m_{i}=si*(h_{i}-h_{i-1})\mod q$
6. Пілпис: $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)$

Див. також

• Криптографія на ґратках

Посилання

• Most recent NTRUSign paper, including parameter sets for multiple security levels
• A Java implementation of NTRUSign. sourceforge.net. Архів оригіналу за 23 грудня 2015.