1.   引言

数字签名是公钥密码体制的基础原件之一，其在通讯中有着非常广泛的应用。由于整数分解和离散对数问题被证明在量子计算机下可以高效求解，因此基于上述困难问题的传统公钥密码体制在量子计算机下是不安全的，构造能够抵抗量子攻击的密码体制即后量子密码体制是公钥密码一个非常重要的研究方向。

基于格的密码体制是后量子密码体制的一类重要候选方案，就格签名而言主要有两条发展路线：一类格签名根据Hash-and-Sign范式进行构造，另一类签名通过Fiat-Shamir变换及拒绝采样技术进行构造。

典型的Hash-and-Sign签名，公钥是一个单向陷门函数$f(x)$，私钥是利用陷门可以高效计算的逆函数${f^{ - 1}}(x)$。签名一个消息$m$，首先将消息$m$哈希到函数$f$的值域上，即$y = H(m)$，然后输出签名$\sigma = {f^{ - 1}}(y)$。验签的时候需要检查条件$f(\sigma ) = H(m)$是否成立。最早利用Hash-and-Sign范式构造的签名是(Goldreich-Goldwasser-Halevi, GGH)方案^[1]，公钥选用格的一组“坏基”${{H}}$，私钥选取“好基”${{B}}$，签名的时候将消息哈希到实空间上的一点${{v}}$，利用好基${{B}}$通过Babai算法^[2]找到离${{v}}$最近的格向量，验签的时候利用坏基${{H}}$验证签名是否是一个格点，当格点离${{v}}$足够近，则判定签名合法。GGH签名的安全性建立在敌手无法由坏基多项式时间内恢复出好基以及敌手无法利用坏基高效求解最近向量问题(Closest Vector Problem, CVP)。将GGH所采用的一般格限制到NTRU格上衍生出了NTRUSign方案^[3]，这种签名方案有紧凑的密钥和签名长度。然而GGH型的签名易于遭受基本区域学习(learning a parallelepiped)攻击^[4]，其缺陷是签名会泄露私钥的统计信息，通过收集足够多的消息签名对可以勾勒出好基的形状。第1个具有可证安全的Hash-and-Sign签名是2008年提出的(Gentry-Peikert-Vaikuntanathan, GPV)签名方案^[5]，相较于GGH类签名直接在格中找离消息的哈希值$H({{m}})$最近的格点，GPV签名是在垂直格${\varLambda ^ \bot }$中找离${{{c}}_0}$近的格点${{s}}$，其中${{{c}}_0}$满足${{A}}{{{c}}_0} = H({{m}})$，这个格点服从中心在${{{c}}_0}$的离散高斯分布${{\cal D}_{{c_0} + {\varLambda ^ \bot },\sigma }}$，基本区域学习攻击不再能得到关于私钥的有效信息。GPV签名方案虽然在安全性上有了保障，但陷门采样过程效率较低且签名尺寸较大(达到了10⁶字节级别)。提交到美国国家标准与技术局(National Institute of Standards and Technology, NIST)后量子算法竞赛的基于格的NTRU上的快速傅里叶紧签名(FAst-fourier Lattice-based Compact signatures Over NTRU, FALCON)算法^[6]在陷门采样上做了改进，通过将GPV的一般格改为NTRU格得到了紧凑的公钥与签名尺寸。

Lyubashevsky^[7]在2009年以ring-SIS为底层困难问题给出了第1个Fiat Shamir格签名。这类签名从一个身份鉴别方案出发进行Fiat Shamir变换，将身份鉴别方案中的脚本(承诺commitment，挑战challenge，回应response)应用到签名的生成过程中，将身份鉴别方案中验证者最后一轮对回应的检查应用到签名方案的验签算法中，由此得到一个非交互的方案。身份鉴别方案中的回应作为签名的一个部分，其分布应独立于私钥才能保证方案的安全性。Lyubashevsky^[8]在2012年提出的Fiat Shamir签名方案，拒绝采样前的回应服从平移的离散高斯分布，平移量与私钥相关，他使用拒绝采样技术使得输出分布服从中心在原点的离散高斯分布，从而保证了签名方案是零知识的。双峰格签名方案(Bimodal LattIce Signature Scheme, BLISS)^[9]对回应的分布进行了改进，将平移的离散高斯分布变成了双峰高斯分布，这样处理能够减少签名算法中的采样迭代次数并且使得输出的签名尺寸更加紧凑，BLISS方案用NTRU格进行了实例化。

提交到NIST后量子算法竞赛的Dilithium算法^[10]也采用了Fiat-Shamir变换及拒绝采样技术，但避免了使用离散高斯采样，仅需均匀采样从而使签名方案更加易于实现。Dilithium方案的安全性基于模错误学习(Module Learning With Errors, MLWE)问题，其签名在选择消息攻击下具有存在不可伪造性。Dilithium使用的是一般格，要在保证Dilithium方案优点的基础上，进一步构造更加紧凑的签名方案，本文给出的一个解决思路是构造NTRU版的Dilithium签名。基于NTRU假设构造的后量子密码方案在工程上有很大的优势，其算法运行速度快，私钥尺寸非常小。尺寸较小的签名如文献[9,11]中的方案等都是基于NTRU假设，这些方案在签名过程中使用了需要高精度运算的离散高斯采样来生成秘密向量和错误向量，但生成服从离散高斯分布的样本在实现中比较复杂且容易遭到侧信道攻击^[12-14]。Dilithium在一般格上，采用文献[4,15,16]等方案的策略，选择均匀采样设计。本文给出了一个基于“Fiat-Shamir with Aborts”方法^[7]的高效格签名方案FatSeal(Fiat-shamir-transformation-based Signature algorithm with lattice), FatSeal签名的形式受到Dilithium签名的启发，但二者基于的问题不同。本文的方案基于NTRU假设进行设计，继承了Dilithium的简洁设计，签名过程简单，仅需均匀采样。由于使用了NTRU结构，FatSeal的公钥完全压缩，相较而言Dilithium需要进行额外压缩，FatSeal在密钥生成和验签算法上效率很高，方案的实用性很强。FatSeal的乘法运算在多项式环${{\mathbb Z}_q}[x]/({x^n} + 1)$中进行，参数的选取保证运算能用数论变换(Number-Theoretic Transform, NTT)技术进行加速。FatSeal方案参数的设定由实际攻击决定，FatSeal方案私钥的恢复可以归结为NTRU格上CVP问题的求解，也可以转换为LWE实例进行分析，签名的伪造可以归结为短整数解(Short Integer Solution, SIS)问题的求解。本文考虑了混合攻击、Primal攻击以及Dual攻击等具体攻击，由基本求解工具格基约化算法的计算复杂度确定FatSeal相应参数的安全级别，本文给出的两组参数能够使FatSeal签名方案在经典计算机下分别达到128 bit和256 bit安全性。综合来看，FatSeal签名方案在Fiat Shamir with Abort框架下创新地应用了高效的NTRU结构，同时保持了采样模块为均匀分布的简洁设计，能够抵抗已知的格攻击以达到安全目标，是一种非常高效简洁的格签名方案。

2.   数学准备

2.1   记号描述

(1) 环与环运算：令$q$为一个正整数，对于环$R$，定义${R_q}$为商环$R/qR$。本文选用商环${R_q} =$${{\mathbb Z}_q}[x]/({x^n} + 1)$，令$n$为2的次幂且$q$为奇素数满足$q = 1\;(od{\rm{ 2}}n)$。对于任意的$f = {f_0} + {f_1}x + ···$$+ {f_{n - 1}}{x^{n - 1}} \in {R_q}$，将多项式$f$与向量$({f_0},{f_1}, ···,$${f_{n - 1}}) \in {\mathbb Z}_q^n$等同，成立$x \cdot f = ( - {f_{n - 1}},{f_0}, ···,{f_{n - 2}})$, ${\rm{rot}}(f): = \left( \begin{array}{c}f\\xf\\ \vdots \\{x^{n - 1}}f\end{array} \right)$则对任意两个多项式$a,b \in {R_q}$进行乘法运算有$ab = a \cdot {\rm{rot}}(b)od q$。

(2) 剩余系：令$p$为$2$的某个小幂次，记正整数$\alpha = (q - 1)/p$，并令${{\mathbb Z}_\alpha } = \left\{ - \dfrac{\alpha }{2}, - \dfrac{\alpha }{2} + 1, ··· , \right.$$\left.\dfrac{\alpha }{2} - 1\right\}$。对任一整数$y$做${od ^\alpha }q$运算时，即$x = y\;{od ^\alpha }q$，令$x$为剩余系${{\mathbb Z}_q} = \left\{ - \dfrac{\alpha }{2}, - \dfrac{\alpha }{2} + 1, ···, \right.$$\left. q - 1 - \dfrac{\alpha }{2}\right\}$中与$y$相对应的元素，对$x$关于$\alpha$做带余除法，定义

记$k{\rm{ = quo}}(x)$，则$x \in {I_k} = k\alpha + {{\mathbb Z}_\alpha }$，这时有${{\mathbb Z}_q} = \left\{ q - 1 - \dfrac{\alpha }{2}\right\} \cup \cup _{k = 0}^{p - 1}{I_k}$。记号$x = y\;{od ^ \pm }q$表示$x$是剩余系${{\mathbb Z}_q} = \left\{ - \dfrac{{q - 1}}{2}, - \dfrac{{q{\rm{ + }}1}}{2},··· ,\dfrac{{q - 1}}{2}\right\}$中与$y$相对应的元素；记号$x = y\;{od ^ + }q$表示$x$是$y$在剩余系${{\mathbb Z}_q} = \{ 0,1,··· ,q - 1\}$里对应的唯一元素；模运算$y\;od \;q$表示元素所在的剩余系选择不影响运算结果，可以使用任一剩余系。

(3) 小系数多项式集合：集合$B_t^n$是${{\mathbb Z}_q}[x]/$$({x^n} + 1)$的一个子集，集合中任一多项式恰有$t$个系数为1，其余系数为0。集合$T(d + 1,d)$也是${{\mathbb Z}_q}[x]/$$({x^n} + 1)$的一个子集，集合的任一多项式恰有$d + 1$个系数为1, $d$个系数为–1，其余系数等于0。

(4) 元素的尺寸：对于任意$y \in {{\mathbb Z}_q}$，令${\left\| y \right\|_\infty }: = \left| {y{{od }^ \pm }q} \right|$。对于任意的$f = {f_0} + {f_1}x + ··· +$${f_{n - 1}}{x^{n - 1}} \in {R_q}^{}$，定义${\left\| f \right\|_\infty }: = {\max _i}{\left\| {{f_i}} \right\|_\infty }$。

2.2   格与格基约化算法

在数学中，欧式空间上的一个离散加法子群成为一个格。特别地，设行向量${{{b}}_1},{{{b}}_2}, ···,{{{b}}_m} \in {{\mathbb R}^n}$为${{\mathbb R}^n}$中的线性无关向量，记其对应的矩阵为${{B}}$, ${\cal L}({{B}}): = \left\{ \displaystyle\sum\nolimits_{i = 1}^m {{x_i}{{{b}}_i}} |{x_i} \in {\mathbb Z},i = 1,2, ··· ,m \right\}$构成一个${{\mathbb R}^n}$上的格。称${{B}}$为对应格的一组格基。以下是两种常用的格：

定义1 $q$-ary格：对于任意的正整数$m,n,q$和矩阵${{A}} \in {\mathbb Z}_q^{m \times n}(m \ge n)$，定义$m$维$q$-ary格为

定义2 NTRU格：对于任意$f,g \in T(d{\rm{ + }}1,d)$，其中$f$在${{\mathbb R}_q}$中可逆，则关于$h = {f^{ - 1}}g$的NTRU格定义为

格${{\cal L}_h}$也可以由矩阵$\left( {\begin{array}{*{20}{c}} {q{{{I}}_n}}&0 \\ {{\rm{rot}}({\rm{h}})}&{{{{I}}_n}} \end{array}} \right)$的行向量张成。

格基约化算法是分析格密码方案的实际困难性的重要工具。格基约化算法，包括(Lenstra–Lenstra–Lovász, LLL)算法^[17], (Block Korkine-Zolotareff, BKZ)算法^[18]等，其主要想法是将原有格基做垂直投影转化为低维格，在低维的投影格上利用最短向量问题(Shortest Vector Problem, SVP)求解算法找低维格的最短向量，再扩张到高维格上。例如，以块大小$b$为参数的BKZ算法首先调用$b$维SVP求解器去找${\pi _{i + 1}}({{{b}}_i}),{\pi _{i + 1}}({{{b}}_{i{\rm{ + }}1}}), ··· ,{\pi _{i + 1}}({{{b}}_j})\;(i \le n,j =$$\min(n,i{\rm{ + }}b))$上的最短格向量(其中${\pi _i}:{{\mathbb R}^n} \to$${\rm{span}}{({{{b}}_1},{{{b}}_2}, ··· ,{{{b}}_{i - 1}})^ \bot }$为投影映射)，之后将这组短向量扩展为高维格的一组格基，多次重复此过程进而求得一组较短的格基。关于BKZ约化基，有等比数列假设(Geometric Series Assumption, GSA)，BKZ约化基正交化后长度近似满足关系${\left\| {{{b}}_i^*} \right\|^2}/$${\left\| {{{b}}_1^*} \right\|^2} = {r^{i - 1}}$，这里$r$是$[3/4,\;1)$中的某个实数，称为GSA常数。

块大小$b$会影响输出格基的质量和算法总的运行时间，不同模型下的SVP求解算法有不同运行时间估计。一般而言运行时间约为${2^{{\rm c} \cdot b}}$，关于常数$\rm c$的估计有如下结果：

(1) Classical：目前已知最好的经典SVP求解算法^[19]取${\rm c} = {\log _2}\sqrt {3/2} \approx 0.292;$

(2) Quantum：目前已知最好的量子SVP求解算法^[20]取${\rm c} = {\log _2}\sqrt {13/9} \approx 0.265;$

(3) Plausible：密码学界猜测未来的算力可能会达到${\rm c} = {\log _2}\sqrt {4/3} \approx 0.2075$^[21]。

2.3   困难问题

FatSeal签名方案与以下格上的困难问题密切相关：

定义3 γ-SVP和uSVP：给定一个格${\cal L}$和一个近似因子$\gamma \ge 1$，在格中找一个不长于$\gamma \cdot {\lambda _1}({\cal L})$的非0向量叫做近似最短向量问题(γ-SVP)，这里${\lambda _1}({\cal L})$表示格中最短非0向量的长度。对于特定的存在唯一最短非0向量的格${{\cal L}^{{\rm{ '}}}}$，寻找该向量即为唯一最短向量问题(uSVP)。

定义4 γ-CVP：给定一个$n$维格${\cal L}$，一个目标向量${{t}} \in {{\mathbb R}^n}$和一个近似因子$\gamma \ge 1$，在格中寻找向量${{y}}$满足$\left\| {{{t}} - {{y}}} \right\| \le \gamma \cdot {\rm d} ({{t}},{\cal L})$的问题叫做近似最近向量问题(γ-CVP)，这里${\rm d} (t,{\cal L})$表示目标向量到格的距离。

定义5 ${\rm{SI}}{{\rm{S}}_{ {q,n,m,\beta} }}$问题：对于从${\mathbb Z}_q^{m \times n}(m \ge n)$中随机均匀选取的矩阵${{A}}$，求解短向量${{x}} \in {{\mathbb Z}^m}/\{ 0\}$使得 ${{xA}} = 0od q$且 ${\left\| {{x}} \right\|_\infty } \le \beta$。

这个问题也可以看成是${\varLambda ^ \bot }({{A}})$格上找非0短向量的问题。

3.   FatSeal签名方案

3.1   方案描述与正确性

在这个部分给出本文的新签名方案如表1、表2和表3所示及正确性证明。

表 1  FatSeal密钥生成算法

算法1 FatSeal.KeyGen()
输入：$n,q$
输出：公钥$h$，私钥$(f,g)$
(1) $f,g \leftarrow T(d{\rm{ + 1}},d)$
(2) 如果$f$在${R_q}$中不可逆，跳转(1)
(3) 计算$h = (g + \alpha ){f^{ - 1}}$
(4) 输出$pk = h$, $sk = (f,g)$

下载: 导出CSV 

| 显示表格

表 2  FatSeal签名算法

算法2 FatSeal.Sign()
输入：消息$M$，公钥$h$，私钥$(f,g)$
输出：消息$M$的签名$(z,c)$
(1) $r \leftarrow {{\mathbb Z}_\alpha }[x]/({x^n} + 1)$
(2) 计算$w = hr{od ^\alpha }q$
(3) 若$w$的某分量等于$q - 1 - \alpha /2$，跳转(1)
(4) 计算$c = H(M,{\rm{quo}}(w))$
(5) 计算$z = r + cf$
(6) 若${\left\| {cg} \right\|_\infty } \le \gamma ,\;{\left\| {cf} \right\|_\infty } \le \gamma ,\;{\left\| {cg + {\rm{rem}}(w)} \right\|_\infty } \le \alpha /2 - \gamma ,$　　 　${\left\| z \right\|_\infty } < \alpha /2 - \gamma$，输出$(z,c)$
(7) 否则，跳转步骤(1)

下载: 导出CSV 

| 显示表格

表 3  FatSeal验签算法

算法3 FatSeal.Verify()
输入：消息$M$，公钥$h$，签名$(z,c)$
输出：验证成功输出1，否则输出0
(1) 如果${\left\| z \right\|_\infty } \ge \alpha /2 - \gamma$或${w{'} } = hz - \alpha c{od ^\alpha }q$的某个分 　　　　量等于$q - 1 - \alpha /2$，输出0
(2) 否则
(3) 计算${c{'} } = H(M,{\rm{quo} }({w{'} }))$
(4) 如果${c{'} } = c$，输出1
(5) 否则，输出0

下载: 导出CSV 

| 显示表格

FatSeal的私钥是从$T(d{\rm{ + }}1,d)$中均匀选取的短多项式$f,g$，其中要求$f$在${R_q}$中可逆。公钥$h \in {R_q}$由$(g + \alpha ){f^{ - 1}}$计算得到。

签名者要对消息$M$进行签名，首先从${R_\alpha } =$${{\mathbb Z}_\alpha }[x]/({x^n} + 1)$中随机选取多项式$r$，即$r$的每个系数在$\{ - \alpha /2, - \alpha /2{\rm{ + }}1,··· ,\alpha /2 - 1\}$中均匀选取。然后计算$w = hr{od ^\alpha }q$，如果$w$的某个分量为$q - 1 - \alpha /2$，则重新选取$r$。计算$c = H(M,{\rm{quo}}(w)) \in B_t^n$，哈希值$c$是${R_q}$中的多项式，其中恰有$t$个系数为1，其余系数为0。接着计算$z = r + cf$，这里$cf$的系数绝对值的最大可能值是$t$，此时若直接输出$z$，则有可能泄露私钥的信息，FatSeal利用拒绝采样来保证签名算法是零知识的。对某个选定的正数$\gamma ( \le t)$，如果能同时满足以下4个条件：${\left\| {cg} \right\|_\infty } \le \gamma$, ${\left\| {cf} \right\|_\infty } \le \gamma$, ${\left\| {cg + {\rm{rem}}(w)} \right\|_\infty } \le \alpha /2 - \gamma$, ${\left\| z \right\|_\infty } < \alpha /2 - \gamma$，则输出签名$(z,c)$。输出的$z$在$(\gamma - \alpha /2,\;\alpha /2 - \gamma ) \cap {\mathbb Z}$上均匀分布，对于任意$x \in (\gamma - \alpha /2,\;\alpha /2 - \gamma ) \cap {\mathbb Z}, \;j \in$${\rm{\{ - }}\gamma {\rm{, - }}\gamma {\rm{ + }}1{\rm{,}}··· {\rm{,}}\gamma {\rm{\} }}$，有$- \alpha /2 + 1 \le x - j \le \alpha /2 - 1$，可以计算得

即${z_i}$取到$(\gamma - \alpha /2,\;\alpha /2 - \gamma ) \cap {\mathbb Z}$中各值的概率是均等的。

对于输入的签名$(z,c)$，验签算法检查了3个条件：

(1) ${\left\| z \right\|_\infty } < \alpha /2 - \gamma ;$

(2) 计算${w{'}} = hz - \alpha c{od ^\alpha }q$, ${w{'}}$的每一个分量都不等于$q - 1 - \alpha /2$；

(3) $c = H(M,{\rm{quo}}({w{'}}))$。

如果以上3个条件都能满足，则签名$(z,c)$通过验证。

对于合法签名$(z,c)$，条件(1)显然满足。计算$hz - \alpha c = hr + cg$，有

因为合法签名满足${\left\| {cg + {\rm{rem}}(w)} \right\|_\infty } \le \alpha /2 - \gamma$，故成立${\rm{quo}}({w{'}}) = {\rm{quo}}(w)$，进而条件(2)和条件(3)可满足。

3.2   签名迭代次数

对于计算$w = hr{od ^\alpha }q$，如果$w$的某个分量为$q - 1 - \alpha /2$，则算法重启，假设$w$各分量独立且在剩余系内均匀分布，则签名算法在这一步不重启的概率为${(1 - 1/q)^n}$。要输出一个签名，还需要满足${\left\| {cg} \right\|_\infty }\! \le\! \gamma$, ${\left\| {cf} \right\|_\infty } \!\le\! \gamma$, ${\left\| {cg + {\rm{rem}}(w)} \right\|_\infty } \!\le \! \alpha /2 - \gamma$, ${\left\| z \right\|_\infty } < \alpha /2 - \gamma$这4个条件。注意到

假设各分量独立，于是有$\Pr [||z|{|_\infty } < \alpha /2 -$$\gamma |{\left\| {cf} \right\|_\infty } \le \gamma | = {\left(\dfrac{{\alpha - 2\gamma - 1}}{\alpha }\right)^n} \approx {{\rm e}^{ - \frac{{2\gamma + 1}}{\alpha }n}}$。类似地，有$\Pr[{\left\| {cg + {\rm{rem}}(w)} \right\|_\infty } \le \alpha /2 - \gamma |{\left\| {cg} \right\|_\infty } \le \gamma ]$$\approx {{\rm e}^{ - \frac{{2\gamma - 1}}{\alpha }n}}$。

下面估计${\left\| {cf} \right\|_\infty } \le \gamma$的概率。由$c \in B_t^n$是一个公开的值，有$t$个分量为1，其余为0，而$cf = c \cdot {\rm{rot}}(f)$，则$cf$的各分量是$t$个$f$的系数相加(减)得到。其中$f$的系数取$1$的概率为$(d + 1)/n$，取$- 1$的概率为$d/n$，取$0$的概率为$(n - 2d - 1)/n$。为了便于分析，这里考虑$f$的系数取$1$和$- 1$的概率均为$d/n$，取$0$的概率为$(n - 2d)/n$。由于$f$的系数取1和取–1的概率相同，此时$cf$的各分量即可视为是$t$个$f$的系数相加。参数选取时若使$t$的值大于30，那么应用中心极限定理可知$cf$的各系数服从期望为0，方差为$2td/n$的正态分布，从而${\left\| {cf} \right\|_\infty } \le \gamma$的概率为${\rm{erf}}\left(\dfrac{\gamma }{{2\sqrt {td/n} }}\right)$。

综合上述分析，可以估计出同时满足${\left\| {cg} \right\|_\infty } \le \gamma$, ${\left\| {cf} \right\|_\infty } \le \gamma$, ${\left\| {cg + {\rm{rem}}(w)} \right\|_\infty } \le \alpha /2 - \gamma$, ${\left\| z \right\|_\infty } < \alpha /2 - \gamma$的概率为${{\rm{e}}^{ - \frac{{4\gamma }}{\alpha }n}} \cdot {\rm{erf}}{\left(\dfrac{\gamma }{{2\sqrt {td/n} }}\right)^{2n}}$。

4.   FatSeal的参数选取

本节给出FatSeal方案的实例化。对于NTRU系统，其私钥一般从小系数集合中选取，本文将小系数集合选为$T(d,d + 1)$。由于使用的多项式环为${{\mathbb Z}_q}[x]/({x^n} + 1)$, FatSeal方案中的多项式乘法运算可以利用NTT技术进行高效实现。为使用NTT，本文选择的模数$q$为素数，满足$q \equiv 1od 2n$，群${\mathbb Z}_q^*$中的$2n$阶元记为$w$。参数$\alpha$取为$(q - 1)/8$，此时整数关于$\alpha$的商需要3 bit来表示。表4列出了两组参数使得FatSeal在经典计算机下分别具有128 bit和256 bit安全性，同时也给出了相应的迭代概率$p$，期望迭代$1/p$次FatSeal.Sign()算法能返回一个合法签名。在这两组参数下，哈希函数值域规模分别大于${2^{256}}$和${2^{512}}$。

表 4  FatSeal签名方案的参数选取及迭代概率估计

$n$	$T(d + 1,d)$	$q$	$\omega$	$t$	$\alpha$	$\gamma$	迭代概率(%)
1024	T(257, 256)	286712	106	44	35840	20	10.2
2048	T(413, 412)	724993	287	87	90624	24	11.4

下载: 导出CSV 

| 显示表格

签名的尺寸由$z$主导，需要$n\left\lceil {\log{_2}(\alpha /2 - \gamma )} \right\rceil /8$Byte存储，公钥尺寸为$n\left\lceil {{\log_2}(q)} \right\rceil /8$Byte。表5给出FatSeal两套参数对应的规模，长度数据来源于FatSeal的参考实现。提交到NIST的基于格的Fiat-Shamir类型签名只有Dilithium和qTESLA^[22], Dilithuim方案在签名尺寸上比qTESLA的大，表5和表6的数据表明FatSeal作为Dilithium的NTRU变种在参数规模上优于同安全等级下的qTESLA方案。

表 5  FatSeal签名128 bit和256 bit安全强度下的参数大小(Byte)

体制	公钥长度	私钥长度	签名长度
FatSeal-1024	2321	385	2048
FatSeal-2048	4984	719	4352

下载: 导出CSV 

| 显示表格

表 6  qTESLA签名128 bit和256 bit安全强度下的参数大小(Byte)

体制	公钥长度	私钥长度	签名长度
qTESLA-Ⅱ	2336	1600	2144
qTESLA-Ⅴ	5024	3520	4640

下载: 导出CSV 

| 显示表格

5.   具体安全性分析

FatSeal签名方案的密钥恢复攻击与伪造签名攻击依赖于NTRU问题与无穷范数下的SIS问题的困难性；这两个问题均是格理论中的经典困难问题。

5.1   私钥恢复

FatSeal体制私钥的安全性与NTRU格上求解近似CVP问题紧密相关。若能求解短多项式对$\left( {f,g} \right) \in {R_q}$使得$hf = g + \alpha$，则可以恢复体制的私钥。矩阵$\left( {\begin{array}{*{20}{c}} {q{{{I}}_n}}&0 \\ {{\rm{rot}}\left( h \right)}&{{{{I}}_n}} \end{array}} \right)$行向量张成的NTRU格记为${L_h}$，则$\left( {g + \alpha ,f} \right) \in {L_h}$。如果能求解${L_h}$中离$\left( {\alpha ,0} \right) \in$$R_q^2$足够近的格向量，则可以恢复$\left( {f,g} \right)$。

混合攻击：考虑矩阵${{B}} \!=\! \left( {\begin{array}{*{20}{c}} {q{{{I}}_n}}&0&0 \\ {{\rm{rot}}\left( h \right)}&{{{{I}}_n}}&0 \\ \alpha &0&1 \end{array}} \right) \!=$$\left( {\begin{array}{*{20}{c}} {q{{{I}}_{{r_1}}}}&0&0 \\ *&{{{{L}}_1}}&0 \\ *&*&{{{{I}}_{{r_2}}}} \end{array}} \right) \in {{\mathbb Z}^{2n + 1}}$，其中${{{L}}_1} \in {{\mathbb Z}^{N \times N}}$。对${{{L}}_1}$进行格基约化，再对列向量进行Gram-Schmidt正交化，最后进行旋转变换得到下三角矩阵${{T'}}$，即${{T'}} = {{T'}}{{{L}}_1}{{Y'}}$，其中${{U'}}$是幺模矩阵，${{Y'}}$是正交阵。对${{B}}$进行变换使得子矩阵${{{L}}_1}$变为${{T'}}$，相应的矩阵${{B}}$变为矩阵${{T}}= {{UBY}}$，即

其中，$\left( {g,f, - 1} \right){{Y}}$是格${\cal L}\left( {{T}} \right)$中的一个向量。设${{T}}$对角线上的元素分别为${q^{{\alpha _1}}},{q^{{\alpha _2}}}, ··· ,{q^{{\alpha _{2n + 1}}}}$，有${\alpha _1} + {\alpha _2} + ···$$+{\alpha _{2n + 1}} = n$。当$1 \le i \le {r_1}$时，${\alpha _i} = 1$；当$2n + 1 -$${r_2} < i \le 2n + 1$时，${\alpha _i} = 0$；当${r_1} < i \le 2n + 1 - {r_2}$，根据GSA假设，${\alpha _i}$线性递减，满足

其中，$\delta$是根Hermite因子。由文献[23]中的引理1，当${{y}}={{uT}}+{{x}}$, ${{u}},{{x}} \in {{\mathbb Z}^{2n + 1}}$，若${{x}}$的各分量满足$- {T_{i,i}}/2 < {x_i} \le {T_{i,i}}/2$, $1 \le i \le 2n{\rm{ + }}1$，针对${{T}}$应用Babai算法约化${{y}}$可以恢复${{x}}$。对于${\cal L}\left( {\bf{B}} \right)$中的最短向量${{v}}$，若能保证${\alpha _{{r_2}}} > {\log _q}\left( {2{{\left| {\left| {{v}} \right|} \right|}_\infty }} \right)$，枚举${{v}}$的最后${r_2}$个分量，就能找到${{v}}$。攻击运行时间为格基约化时间加上枚举时间，利用Grover算法加速搜索，运行时间估计为${2^{c \cdot b}} + {3^{0.5 \cdot {r_2}}}$。通过平衡约化时间和搜索时间可以得到该攻击下的比特安全性，如表7所示。

表 7  混合攻击下的FatSeal比特安全性

模型	体制	$b$	$N$	${r_1}$	比特安全性
classical	FatSeal-1024	510	1770	91	150
quantum	FatSeal-1024	522	1799	75	139
plausible	FatSeal-1024	549	1865	40	115
classical	FatSeal-2048	1130	3440	240	331
quantum	FatSeal-2048	1157	3503	207	307
plausible	FatSeal-2048	1219	3646	132	253

下载: 导出CSV 

| 显示表格

Primal攻击：取${\rm{rot}}\left( h \right)$的任意$m$列得到矩阵${{A}} \in {{\mathbb Z}^{n \times m}}$，多项式$- g$和$f$对应的列向量分别记作${{e}} \in {{\mathbb Z}^m}$和${{s}} \in {{\mathbb Z}^n}$，令${{b}} = \left( {\alpha ,0, ··· ,0} \right) \in {{\mathbb Z}^m}$。考虑LWE实例$({{A}},{{b}}={{sA}}+{{e}})$，构造维数为$d = m + n + 1$的格

其中$\left( {{{s}},{{e}},1} \right)$是格$\varLambda$的一个短向量，长度近似为$\sigma \sqrt {m + n}$，这里$\sigma$为${{s}},{{e}}$的标准差。利用BKZ算法求解短向量，攻击能够生效当且仅当块大小$b$满足$\sigma \sqrt b \le {\delta ^{2b - d - 1}}{q^{\frac{m}{d}}}$，其中$\delta = {\left( {{{\left( {\pi b} \right)}^{\frac{1}{b}}}\dfrac{b}{{2\pi {\rm{e}}}}} \right)^{\frac{1}{{2\left( {b - 1} \right)}}}}$为根Hermite因子，该攻击运行时间约为${2^{c \cdot b}}$。调整$m$和$b$的大小使得运行时间最少，以此给出Primal攻击的具体复杂度估计。

Dual攻击：在对偶攻击的模型下，考虑LWE实例$({{A}},{{b}}={{sA}}+{{e}})$，可以构造$d = m + n$维格$\varLambda = \left\{ {\left( {{{x}},{{y}}} \right) \in {{\mathbb Z}^{m + n}}{\rm{|}}{{A}}{{{x}}^{\rm{T}}} = {{{y}}^{\rm{T}}}od \;q} \right\}$。由文献[24]中的结论，BKZ算法可以找到格$\varLambda$中的一个长度为$l = {\delta ^{d - 1}}{q^{n/d}}$的短向量${{v}}=\left( {{{x}},{{y}}} \right)$, ${{{v}}^{\rm{T}}}{{b}}$的分布和均匀分布的统计距离不超过$\epsilon= 4\exp \left( { - 2{\pi ^2}{\tau ^2}} \right)$，这里$\tau = l\sigma /q$。用这个攻击即可以优势$\varepsilon$打破判定性LWE问题。攻击的计算复杂度由BKZ算法给出，块大小取为$b$，重复运行筛法$R = \max \left( {1,\;1/\left( {\gamma {\varepsilon ^2}} \right)} \right)$次可以找到$1/{\epsilon}^2$个短向量，这里$\gamma = {\sqrt {4/3} ^b}$是筛法$b$维投影格里最短向量个数的估计。

NewHope模型下的Primal攻击和Dual攻击复杂度如表8所示。

表 8  NewHope攻击模型下的比特安全性

体制	攻击模型	m	b	classical	quantum	plausible
FatSeal-1024	primal	874	503	147	133	104
FatSeal-1024	dual	862	502	146	133	104
FatSeal-2048	primal	1671	1076	314	285	223
FatSeal-2048	dual	1697	1072	313	284	222

下载: 导出CSV 

| 显示表格

5.2   签名伪造

对于FatSeal体制的签名伪造，可以考虑求解SIS问题。给定公钥$h$，如果能对$v \in \{ 0,1, ···, p - 1\}$和消息$M$找到找到足够短的$({{z}},{{r}}) \in {{\mathbb Z}_q} \times {{\mathbb Z}_\alpha }$，使得$h{{z}} - {{r}} = (v + c)\alpha$成立，这里$c = H(M,v)$，则可以得到关于消息M的一个合法签名$({{z}},{{r}})$。

对$h{{z}} - {{r}} = (v + c)\alpha$的求解可以转化为SIS问题的求解，记${{A}} = \left( {\begin{array}{*{20}{c}} {{\rm{rot}}\left( h \right)} \\ {{{{I}}_n}} \\ {\left( {v + c} \right)\alpha } \end{array}} \right)$，考虑解齐次方程${{xA}} = 0od q$使得${\left\| {{x}} \right\|_\infty } < \alpha /2 - \gamma$。从矩阵${{A}}$中任选$w( > n)$行，余下的行对应的解分量取为0。对于这$w$行张成的格，求解其正交格的一组格基，经过BKZ算法约化后格基形为$\left( {\begin{array}{*{20}{c}} {q{{{I}}_{{r_1}}}}&0&0 \\ *&*&0 \\ *&*&{{{{I}}_{{r_2}}}} \end{array}} \right)$，其中$0 \le {r_1},{r_2} < w$。由GSA假设${\log _2}\left\| {{{b}}_i^*} \right\|({r_1} < i < w - {r_2})$满足斜率为$\dfrac{1}{{b - 1}}{\log _2}\left(\dfrac{b}{{2\pi {\rm{e}}}}{(\pi b)^{\frac{1}{b}}}\right)$的线性关系。利用SVP求解算法可以得到${\sqrt {4/3} ^b}$个${\pi _{{r_1}}}({\cal L})$上的向量，长度约为$\left\| {{\bf{b}}_{{r_1} + 1}^*} \right\|$。可假设这${\sqrt {4/3} ^b}$个向量的前${r_1}$个分量在${{\mathbb Z}_q}$上均匀分布，余下各分量满足中心等于0，方差等于${\left\| {{{b}}_{{r_1} + 1}^*} \right\|^2}/(w - {r_1} - {r_2})$的高斯分布。设向量前$w - {r_2}$个分量绝对值不超过$\alpha /2$的概率为$p$，那么总的运行时间等于${2^{c \cdot b}}/p$，利用此分析可以得到表9。

表 9  SIS攻击下的比特安全性

模型	体制	$b$	$w$	比特安全性
classical	FatSeal-1024	577	2048	181
quantum	FatSeal-1024	577	2048	166
plausible	FatSeal-1024	577	2048	132
classical	FatSeal-2048	1276	4039	379
quantum	FatSeal-2048	1278	4041	344
plausible	FatSeal-2048	1284	4049	270

下载: 导出CSV 

| 显示表格

6.   结束语

FatSeal签名方案在Dilithium签名方案的基础上融合了NTRU的优势，是一个新的基于NTRU格的Fiat-Shamir签名构造，相对于已有的Fiat-Shamir格签名得到了效率上的提升和参数规模的减小。FatSeal签名方案两套参数的设置能够抵抗现有已知最好的攻击，在经典计算机下分别能够达到128 bit安全性和256 bit安全性。未来的工作是继续研究FatSeal在量子RO模型下的可证安全性以及改进FatSeal的具体安全性评估模型。对于FatSeal的参考实现，在算法优化这一块尚有许多工作可以开展，如考虑基于AVX的多项式乘法加速，从而进一步提升FatSeal签名的实用性。