NTRUSign

• 什么是NTRUSign¹

NTRUSIGN [15] is a special instantiation of GGH with the compact lattices from the NTRU encryption scheme [12], which we briefly recall: we refer to [4,15] for more details. In the NTRU standards [4] being considered by IEEE P1363.1 [19], one selects $N = 251, q = 128$N=251,q=128. Let $R$R be the ring $Z[X]/(XN − 1)$Z[X]/(XN−1) whose multiplication is denoted by $∗.$∗. Using resultants, one computes a quadruplet $(f,g,F,G) ∈ R^4$(f,g,F,G)∈R4 such that $f ∗ G −g ∗ F = q$f∗G−g∗F=q in $R$R and $f$f is invertible mod $q$q, where $f$f and $g$g have $0–1$0–1 coefficients (with a prescribed number of 1), while $F$F and $G$G have slightly larger coefficients, yet much smaller than $q$q. This quadruplet is the NTRU secret key. Then the secret basis is the
following $(2N) × (2N)$(2N)×(2N) matrix:

where $f_i$fi​ denotes the coefficient of $X^i$Xi of the polynomial $f$f . Thus, the lattice dimension is $n = 2N$n=2N. Due to the special structure of $R$R, it turns out that a single row of $R$R is sufficient to recover the whole secret key. Because $f$f is chosen invertible mod $q$q, the polynomial $h = g/f (\mod q)$h=g/f(modq) is well defined in $R$R: this is the NTRU public key. Its fundamental property is that $f ∗ h ≡ g (\mod q)$f∗h≡g(modq) in $R$R. The polynomial $h$h defines the following (natural) public basis of the lattice:

which implies that the lattice volume is $q^N$qN .
The messages are assumed to be hashed in $\{0,...,q −1\}^{2N}${0,...,q−1}2N. Let $m ∈ \{0,...,q −1\}^{2N}$m∈{0,...,q−1}2N
be such a hash. We write $\bold m = (\bold m_1,\bold m_2)$m=(m1​,m2​) with $\bold m_i ∈ \{0,...,q − 1\}^N$mi​∈{0,...,q−1}N . It is shown in [15] that the vector $(\bold {s,t}) ∈ Z^{2N}$(s,t)∈Z2N which we would obtain by applying Babai’s round-off CVP approximation algorithm to $\bold m$m using the secret basis $R$R can be alternatively computed using convolution products involving $\bold {m_1, m_2}$m1​,m2​ and the NTRU secret key $(f,g,F,G)$(f,g,F,G). In practice, the signature is simply s and not $(\bold {s,t})$(s,t), as $\bold t$t can be recovered from $\bold s$s thanks to $h$h.Besides, $\bold s$s might be further reduced mod $q$q, but its initial value can still be recovered because it is such that $\bold {s − m_1}$s−m1​ ranges over a small interval (this is the same trick used in NTRU decryption). This gives rise for standard parameter choices to a signature
length of $251 × 7 = 1757$251×7=1757 bits. While this signature length is much smaller than other 格上签名方案，例如GGH，但比起传统DSA方案，其签名还是太大。

• NTRUSign的优势²
  NTRUSign 是Hofstein 等人针对Ｒ-NSS 签名算法的缺点而改进的一种新型数字签名算法，该算法的签名值是两个私钥的线性组合，这样就能抵抗Gentry 和Szydlo 的攻击。NTRUSign的安全性是基于格上的近似最近向量问题( app-CVP) 的困难问题。

1.**生成
a) 随机选择$f，g∈ZN$f，g∈ZN，并且满足系数分别有$d_f、d_g$df​、dg​个1，其余均为0。另外要求$f$f在$Z^N_q$ZqN​
中可逆，逆元记做$F_q$Fq​。$Normbound$Normbound为验证时使用的限。$Z^N$ZN表示最高次数为$N － 1$N－1的多项式，$Z^N_q$ZqN​表示最高次数为$N － 1$N－1、系数模$q$q的多项式。
b) 计算: $h≡Fq × g( mod q)$h≡Fq×g(modq) 。
c) 计算$F，G∈Z^N$F，G∈ZN，并且满足系数$f × G － F × g = q$f×G－F×g=q，且
$‖F‖≈‖f‖\sqrt {N/12}$‖F‖≈‖f‖N/12​，$‖G‖≈‖g‖ \sqrt {N/12}$‖G‖≈‖g‖N/12​。
2.签名
a) 用$hash$hash函数作用于消息$D$D，得到$Z^N_q$ZqN​上的多项式$m$m。
b) 计算 ${\text{B = }}\left[ {\frac{{ - F \times m}}{q}} \right]$B = [q−F×m​],${\text{b = }}\left[ {\frac{{ - f \times m}}{q}} \right]$b = [q−f×m​]
c) 计算签名值$s≡f × B + F × b( \mod q)$s≡f×B+F×b(modq) 。
3.验签
a) 与签名一样用$hash$hash 函数对消息$D$D 进行变换得到$m$m。
b) 计算$t≡s × h( mod q)$t≡s×h(modq)。
c) 验证$‖s‖ + ‖t － m‖≤Normbound$‖s‖+‖t－m‖≤Normbound，若成立，则$s$s 是消息$D$D 的签名。

• 运用
  Todo