NTRUSign

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

NTRUSign
Ґрунтується на	^d
Дата публікації	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, і вирішення задачі знаходження найближчого вектора в ґратці, тісно пов'язаної з ґраткою . Дана ґратка має властивість: приватний 2N-мірний базис для ґратки можна описати з допомогою 2-х векторів, кожен з яких складається з N коефіцієнтів і базису, який може бути визначений окремим N-розмірним вектором. Це дозволяє представляти відкриті ключі в ${\displaystyle O(N)}$ просторі, а не ${\displaystyle O(N^{2})}$ як і у випадку з іншими схемами підпису на основі ґраток. Операції займають ${\displaystyle O(N^{2})}$ часу, на відміну від ${\displaystyle O(N^{3})}$ для криптографії на еліптичних кривих та RSA. Тому NTRUSign швидше даних алгоритмів при низьких рівнях безпеки і значно швидше при високих рівнях безпеки.

NTRUSign знаходиться в стадії розгляду по стандартизації робочою групою IEEE P1363.

Опис алгоритму

Так само як і в , в NTRUSign обчислення проводяться в кільці ${\displaystyle R=\mathbb {Z} _{q}[X]/(X^{N}-1)}$, де множення «${\displaystyle *}$» є циклічною згорткою по модулю ${\displaystyle q}$. Добутком двох поліномів ${\displaystyle f=[f_{0},f_{1},\ldots ,f_{N-1}]}$ і ${\displaystyle g=[g_{0},g_{1},\ldots ,g_{N-1}]}$ є ${\displaystyle f*g=\sum _{i+j\equiv k\mod N}f_{i}\cdot g_{j}\mod q}$.

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

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

• Вхідні дані: цілі ${\displaystyle N,q,d_{f},d_{g},B>0}$, рядок ${\displaystyle t=standard}$ або ${\displaystyle transpose}$.
• Генерація ${\displaystyle B}$ закритих ґраткових базисів і одиного відкритого ґраткового базису: Встановити ${\displaystyle i=B}$. До тих пір, поки ${\displaystyle i>0}$:

1. Довільно обрати ${\displaystyle f}$, ${\displaystyle g}$ ∈ ${\displaystyle \mathbb {R} }$ взаємно прості з ${\displaystyle d_{f}}$, ${\displaystyle d_{g}}$ відповідно.
2. Знайти малі ${\displaystyle F,G,E,R}$ такі, що ${\displaystyle f*G-F*g=q}$.
3. Якщо ${\displaystyle t=standard}$, встановити ${\displaystyle f_{i}=f}$ і ${\displaystyle f'_{i}=F}$.

Якщо ${\displaystyle t=transpose}$, встановити ${\displaystyle f_{i}=f}$ і ${\displaystyle f'_{i}=g}$.

Обчислити ${\displaystyle h_{i}=f_{i}^{-1}*f'_{i}modq}$. Встановити ${\displaystyle i=i-1}$.

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

Підпис

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

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

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

Перевірка підпису

Верифікація вимагає таку ж геш-функцію ${\displaystyle H}$, «нормуючий зв'язок» ${\displaystyle {\mathcal {N}}\in \mathbb {R} }$ і норму полінома ${\displaystyle ||.||}$. Норма ${\displaystyle ||t||}$ полінома ${\displaystyle t}$ визначається як ${\displaystyle \inf _{0\leq k<q}||t+kq||_{z}}$, де ${\displaystyle ||r||_{z}=\sum _{i=0}^{N-1}r_{i}^{2}-{\frac {1}{N}}\sum _{i=0}^{N}r_{i}}$ (де останнє — Евклідова норма).

• Вхідні дані: Підписані дані ${\displaystyle (D,r,s)}$ і публічний ключ ${\displaystyle h}$.
• Уявити r як рядок бітів. Встановити ${\displaystyle m=H(D||r)}$.
• Обчислити ${\displaystyle b=||(s,s*h-m\operatorname {mod} g))||}$.
• підпис вважається вірним, якщо ${\displaystyle b<{\mathcal {N}}}$.

Зауваження

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

Див. також

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

Примітки

1. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. NTRUSign: Digital Signatures Using the NTRU Lattice. з джерела 30 січня 2013. Процитовано 2018-04-16.
2. http://www.szydlo.com/ntru-revised-full02.pdf
3. P. Nguyen and O. Regev, "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures", available from http://www.cims.nyu.edu/~regev/papers/gghattack.pdf

Посилання

• A Java implementation of NTRUSign. sourceforge.net. оригіналу за 23 грудня 2015.