NTRUSign

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

Історія

Вперше алгоритм був представлений на сесії 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,\dots ,f_{N-1}]$ і $g=[g_0,g_1,\dots ,g_{N-1}]$ є $f*g=\sum _{i+j\equiv kmodN}{f}_i\cdot g_{j}modq$.

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

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

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

1. Довільно обрати $f$, $g$ ∈ $ℝ$ взаємно прості з $d_f$, $d_g$ відповідно.
2. Знайти малі $F,G,E,R$ такі, що $f*G-F*g=q$.
3. Якщо $t=standard$, встановити $f_i=f$ і $f{\text{'}}_i=F$.

Якщо $t=transpose$, встановити $f_i=f$ і $f{\text{'}}_i=g$.

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

• Публічний ключ: вхідні параметри і $h=ho=f_0^{-1}*f{\text{'}}_0\mathrm{mod}q$.
• Закритий ключ: $\{f_i,f{\text{'}}_i,h_i\}$ для $i=0...B$.

Підпис

Підпис вимагає геш-функцію $H:𝒟\to R$ на цифровому просторі документу $𝒟$.

• Вхідні данні: цифровий документ $D\in 𝒟$ закритий ключ $\{f_i,f{\text{'}}_i,h_i\}$ для $i=0...B$.
• Встановити $r=0$.
• Встановити $s=0$$i=B$. Представити $r$як рядок біт. Встановити $m_o=H(D||r)$, де $||$ означає конкатенацию. Встановити $m=m_o$.

1. $\{f_i,f{\text{'}}_i,h_i\}$ — $i$-та підстава
2. Обчислити $x=\lfloor -\frac{1}{q}{m}_i*f{\text{'}}_i\rceil$
3. Обчислити $y=\lfloor \frac{1}{q}{m}_i*f_i\rceil$
4. $s_i=x*f+y*f^{\prime }$
5. $m_i=si*(h_i-h_{i-1})modq$
6. Пілпис: $s=s+s_i$

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

Верифікація вимагає таку ж геш-функцію $H$, «нормуючий зв'язок» $𝒩\in ℝ$ і норму полінома $||.||$. Норма $||t||$ полінома $t$ визначається як $\underset{0\le k<q}{\inf }||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\mathrm{mod}g))||$.
• підпис вважається вірним, якщо $b<𝒩$.

Зауваження

• Рекомендовані параметри $(N,q,d_f,d_g,B,t,𝒩)=(251,128,73,71,1,transpose,310)$

Див. також

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

Посилання

• Most recent NTRUSign paper, including parameter sets for multiple security levels
• Шаблон:Cite web