近年来，随着云计算的发展，具有同态性质的认证技术如同态消息认证码、同态委托计算、同态签名等引起了大家的广泛关注。这些技术主要应用于网络安全编码、传感网络、外包计算、可取回证明等领域。同态签名由于其公开可验证等特点，相对于其他几种技术具有更为广泛的应用空间。

同态签名的概念最早由Johson等在2002年正式提出，当时主要是为了解决网络路由编码中根节点路由对叶节点子网签名数据进行聚合的问题^[1]。同态签名可以简单描述为：已知消息元组m=(m₁，m₂, …, m_l)，公钥pk以及消息元组对应的签名元组σ=(σ₁，σ₂，…, σ_l)，同态签名算法能够在不知道私钥的情况下利用签名元组生成消息u=f(m₁，m₂, …, m_l)上的同态签名σ′，给定元组(σ′，u，f)，任何人可以公开验证签名σ′的有效性。

同态签名的发展具有几个标志性的阶段。第一个阶段是线性同态^[2-9]。文献[2-4]对基于离散对数困难问题提出了线性同态的哈希函数和签名，主要为了解决点对点内容发布系统中的网络优化及安全问题(抗污染攻击)。文献[5]提出了第一个基于RSA假设的线性同态签名。由于传统的困难问题将随着量子计算的发展而面临被攻破的危险，目前很多密码学领域专家已经开始利用新的困难问题来构造密码学方案。由于格具有：1) 格上运算简单(矩阵、向量的加和乘)；2) 格上困难问题能抗量子攻击；3) 格上最坏情况下和平均情况下的困难问题可以进行规约等特点。目前很多密码学原语都是基于格上困难问题构造的。基于格的线性同态签名中比较有代表性的是Boneh等人在2011年提出的一个具有弱内容隐藏，并且在随机预言机模型下可证安全的线性同态签名，该方案是首个基于标准格上的困难问题并建立在二元域上的线性同态签名^[6]。之后出现了很多改进方案，如Wang等对文献[6]进行了改进，通过引入一个哈希函数，使得方案具有更短的公钥和签名尺寸，同时由于不再需要使用盆景树算法，计算效率也得到了提高^[7]。Jing等在文献[7]的方案基础上提出一个适用于多用户的二元域上格基聚合签名方案，方案中聚合消息的签名可用一个通用公钥进行验证，与文献[7]的方案相比，具有更短签名长度，并且不受用户数量限制^[8]。第二个阶段是有限同态(以多项式同态为代表)。2011年Boneh等通过将线性签名进行扩展，用理想格代替标准格，构造了第一个能够对签名数据进行多项式运算的同态签名方案^[9]。对于常指数多项式，方案最终生成签名的尺寸取决于数据集尺寸的对数。类似的，文献[10-12]将多项式同态运用于消息认证。由于同态加密已经经历了从线性同态到部分同态再到全同态的发展历程，而同态签名正是借用了同态加密的思想而发展起来的，因此同态签名也将经历这样一个发展历程。但是目前国内外还没有相关的研究能够实现真正意义上的全同态签名。真正意义上的全同态签名能够实现对签名数据进行任意(电路)运算，不受电路尺寸和深度影响，并且支持公开认证，将成为签名技术发展的一个里程碑。本文基于格上SIS困难问题，利用异或门和与门构造了一个层次全同态签名方案，方案生成的新签名尺寸与电路尺寸以及被签名数据的尺寸无关，只受电路深度和安全参数影响，同时电路具有较高的计算效率，方案在标准模型下可证安全。

1 格上困难问题与同态签名 1.1 格的定义和SIS问题

定义1 格^[13]:令b₁，b₂，…，b_n为一组线性无关的向量，由b₁，b₂，…，b_n生成的格是指b₁，b₂，…，b_n整系数线性组合所构成的向量集合，任意一组用于生成格的线性无关的向量都可以称为格的基，格的维度是指格的基中向量的个数。由向量组b₁，b₂，…，b_n生成的格可以简单表示为$\boldsymbol{\Lambda} = \left\{ {\sum\limits_{i = 1}^n {{c_i}{b_i}:{c_i} \in \boldsymbol{Z}} } \right\} $。当向量b₁，b₂，…，b_n为整数向量时，我们称这些向量生成的格为整数格。整数格中还有一类特殊格，称为q模格，令n、m、q为正整数，A∈Z_q^m×n，则有：

$ \begin{gathered} \boldsymbol{\Lambda} _{\text{q}}^ \bot \left( \boldsymbol{A} \right) = \left\{ {\boldsymbol{x} \in {\boldsymbol{Z}^n}:\boldsymbol{Ax} = 0\;od \;q} \right\} \hfill \\ \boldsymbol{\Lambda} _{\text{q}}^{\text{u}}\left( \boldsymbol{A} \right) = \left\{ {\boldsymbol{x} \in {\boldsymbol{Z}^n}:\boldsymbol{Ax} = \boldsymbol{u}\;od \;q} \right\} \hfill \\ \end{gathered} $

不难发现，Λ_q^u(A)是Λ_q^⊥(A)的陪集。

定义2 格上的离散高斯分布^[14]：对于任意x，c∈Z^m，正实数σ，ρ_σ，c(x)=exp(-π‖x-c‖²/σ²)代表实数空间R^m上以c中心，以σ为参数的高斯函数。令${\rho _{\sigma, c}}\left( \boldsymbol{\Lambda} \right) = \sum\nolimits_{x \in \Lambda } {{\rho _{\sigma, c}}\left( x \right)} $，则对于格Λ上任意一点x，${D_{\Lambda, \sigma, c}}\left( x \right) = \frac{{{\rho _{\sigma, c}}\left( x \right)}}{{{\rho _{\sigma, c}}\left( \boldsymbol{\Lambda} \right)}} $代表格上的离散高斯分布，如果σ=1，s=0，通常将其省略，直接写作D_Λ(x)。

引理1 陷门生成算法^[15-16]令q≥2，m≥6nlogq，存在一个概率多项式时间算法TrapGen(q，n，m)，以一个很大的概率输出矩阵对(A∈Z_q^n×m，T_A∈Z_q^m×m)，使得A统计接近于Z_q^n×m中的随机矩阵，并且T_A是格Λ_q^⊥(A)的一个基，满足：‖T_A‖≤O(nlogq)，$\left\| {{\boldsymbol{{\tilde T}}_A}} \right\| \leqslant 0\left( {\sqrt {n\log q} } \right) $。

引理2 ^[17]存在一个有效算法SampleD：输入矩阵A∈Z_q^n×m及其陷门矩阵T_A和另一个矩阵U∈Z_q^n×m，输出一个矩阵R∈Z_q^m×m，使得：AR=U mod q并且‖R‖≤‖T_A‖×O(m)。

引理3^[18] 令q>2，m>(n+1) logq+ω(logn)，$s > \left\| {{\boldsymbol{{\tilde T}}_A}} \right\|\omega \sqrt {\log \left( {m + {m_1}} \right)} $，存在以下两个取样算法：

1) (左取样)e←SampleLeft(A，B，T_A，u，s)：输入A∈Z_q^n×m，格Λ_q^⊥(A)一个短格基T_A，一个矩阵B∈Z_q^n×m₁，一个向量u∈Z_qⁿ和一个高斯参数s，输出一个向量e∈Z^m+m₁，使得e∈Λ_q^u(F)，其中F=(A|B)，并且统计接近于D_Λq^u(F)，s。

2) (右取样)e←SampleRight(A，B，R，T_B，u，s)：输入A∈Z_q^n×m，R∈Z_q^m×n，一个矩阵B∈Z_q^n×n，格Λ_q^⊥(B)一个短格基T_B，一个向量u∈Z_qⁿ和一个高斯参数s，输出一个向量e∈Z_q^m+n，使得e∈Λ_q^u(F)，其中F=(A|AR+B)，并且统计接近于D_Λq^u(F)，s。

引理4^[18]假设m>(n+1) logq+ω(logn)，令R∈{-1，1}^m×k为随机均匀选择的一个矩阵(其中k=k(n))，A、B分别是从Z_q^n×m、Z_q^n×k中随机选取的矩阵，那么对于所有向量ω∈Z^m，以下两个分布统计接近：(A，AR，R^Tω)≈(A，B，R^Tω)

定义3 SIS问题^[17]给定一个整数q，一个随机的矩阵A∈Z_q^n×m和一个实数β。小整数解问题的目的是找到一个非零向量e，使得Ae=0(modq)且‖e‖≤β。

1.2 同态签名

定义：令消息空间为$\mathscr{M} $，允许电路集合为$\mathscr{C} $(允许电路在这里指能够保证电路输出签名噪声在控制范围内)，C:${\mathscr{M}^\ell } \to \mathscr{M} $代表$\mathscr{C} $中的一个电路，输入端最多同时接受$\ell $个输入，输出端为1个输出，同态签名可以表示为一个元组(Setup，Sign，Eval，Verify)

Setup(1^λ，1^l)：输入安全参数λ和该消息集的最大输入尺寸l，输出一个公钥pk和一个私钥sk。

Sign(sk，τ，i，u)：输入一个私钥sk，标签τ(唯一标识一个消息集合)，消息u∈{0，1}^λ及其索引i∈[l]，输出一个签名σ。

Eval(pk，τ，u=(u₁，…，u_l)，σ=(σ₁，…，σ_l)，C)：输入消息串u及对应的签名串σ，电路C∈$\mathscr{C} $，输出消息u′=C(u)的签名σ′。

Verify(pk，τ，u′，σ′，C)：输入消息u′及其签名σ′，电路C∈$\mathscr{C} $，输出0或者1。

输出1代表验证通过，0代表验证失败。

正确性：我们说一个电路同态签名方案是正确的是指对于任意τ∈{0，1}^λ，电路C∈$\mathscr{C} $，消息集合u∈${\mathscr{M}^\ell } $，以及任意索引i∈[l]，满足：Pr[Verify(pk，τ，u′，σ′，C)=1]=1。

选择性不可伪造安全游戏：敌手和挑战者之间展开以下游戏：

1) 挑战者生成prms←PrmsGen(1^λ，1^l)和(pk，sk)←KeyGen(1^λ，prms)，并将prms，pk给敌手。

2) 敌手选择数据u_¹，…u_^l∈$\mathscr{M} $并将其发送给挑战者。

3) 挑战者计算(σ₁，σ₂，…，σ_l)←Sign_sk(u^₁，…，u^_l)，并将签名(σ₁，…，σ_l)给敌手。

4) 敌手选择一个函数C^*:${\mathscr{M}^\ell } \to \mathscr{M} $和两个值u^*、σ^*，令u′=C(u)。敌手赢得游戏需要满足三个条件：① C^*是允许电路，② u^*≠u′，③ Pr[Verify(pk，u^*，σ^*，C)=1]=1。

2 层次全同态签名方案 2.1 方案描述

参数设置：方案中允许电路C(由若干与门和异或门组成)每次最多允许有l个输入(σ₁，σ₂，…，σ_l)，并假设门电路的输入为σ_x、σ_y(x，y为消息，σ_x、σ_y为消息对应的签名)，输出为σ_z，电路的最大深度为d_max。签名尺寸上限为β=β(n，d_max)∈Z，高斯参数s₁=s₁(n)，s₂=s₂(n)，消息集合对应的标签为t。方案分为四个环节：系统建立、签名、同态运算及验证。

1) 系统建立(1^λ)：

① 随机选取l+1个矩阵：A∈Z_q^n×m, D_i∈Z_q^n×m, (i=1，2，…，l)。

② 利用引理1生成两个矩阵对(Α′，T_Α′)和(B，T_B)，其中，T_Α′、T_B分别是Λ_q^⊥(A′)和Λ_q^⊥(B)的一个短基，方案中作为陷门使用。

③ 输出(Α，Α′，B，T_B，D_i)作为公钥pk，T_Α′作为私钥sk。

2) 签名(sk，t，i，u)：输入密钥sk，标签t，消息索引i和消息u，算法如下：

① 消息u对应的签名可由引理1.3中的左抽样算法获得：

σ_u←SampleLeft(Α′，Α+tB，T_A′，D_u+uB，s₂)，令Α_t=[Α′|Α+tB]，则有：Α_tσ_u=D--_u+uB。

② 输出σ_u

3) 同态运算($pk, t, \boldsymbol{\vec \mu}, \boldsymbol{\vec \sigma}, C $)：$\boldsymbol{\vec \mu } $为消息集合，$ \boldsymbol{\vec \sigma} $为签名集合，同态签名可以通过以下方法递归实现。

① 异或门运算：σ_z=σ_x+σ_y

② 与门运算：$ {\boldsymbol{\sigma} _z} = {\boldsymbol{\sigma} _y}{\boldsymbol{\tilde D}_x} + y{\boldsymbol{\sigma} _x}$其中${\boldsymbol{\tilde D}_x} =-{\boldsymbol{D}'_x}, {\boldsymbol{D}'_x} \leftarrow Sample{\text{D}}\left( {\boldsymbol{B}, {\boldsymbol{T}_{\text{B}}}, {\boldsymbol{D}_{\text{x}}}, {\boldsymbol{s}_1}} \right) \in {\boldsymbol{\text{Z}}}_q^{m \times n} $。

③ 由于前一层门电路的输出可以作为后一层门电路的输入，所以通过迭代运算后可以得到最终签名σ_C∈Z^2m×m。

4) 验证($pk, t, \boldsymbol{\vec \mu}, {\boldsymbol{\sigma} _C}, C $)：输入公钥、标签、消息、签名和电路，如果满足以下条件则通过验证。

① ‖σ_C‖_∞≤β

② A_tC=D_C+C($\boldsymbol{\vec \mu} $)B mod q

2.2 正确性

我们以具有两个输入和一个输出的门电路的运算为例，证明电路同时支持与门和异或门运算，复杂电路的运算可以通过对两种电路进行组合实现。

引理5：令σ_x、σ_y分别是x、y的签名，则有：A_tσ_x=D_x+xB，A_tσ_y=D_y+yB，如果令D_z=D_x+D_y，则有A_tσ_z=D_z+(xXORy)B，满足：‖σ_z‖≤‖σ_x‖+‖σ_y‖。

证明：1) 由异或门运算公式可得：σ_z=σ_x+σ_y，所以有A_tσ_z=A_t(σ_x+σ_y)，即A_tσ_z=A_tσ_x+A_tσ_y，又因为A_tσ_x=D_x+xB，A_tσ_y=D_y+yB，代入D_z=D_x+D_y，即可得到A_tσ_z=D_z+(xXORy)B。

2) 由σ_z=σ_x+σ_y直接可得‖σ_z‖≤‖σ_x‖+‖σ_y‖。

引理6：令σ_x、σ_y分别是x、y的签名，则有：A_tσ_x=D_x+xB，A_tσ_y=D_y+yB，如果令D_z=σ_y$\boldsymbol{\tilde D} $_x，σ_z=σ_y·$\boldsymbol{\tilde D} $_x+yσ_x则有A_tσ_z=D_z+(xANDy)B，并且满足：‖σ_z‖≤‖σ_y‖·poly(m)+‖σ_x‖。

证明：1) 由于D′_x←SampleD(B，T_B，D_x，s₁)∈Z_q^n×m，由引理2可得BD′_x=D_x。由与门运算得：σ_z=σ_y·$\boldsymbol{\tilde D} $_x+yσ_x，所以A_tσ_z=A_t(σ_y·$\boldsymbol{\tilde D} $_x+yσ_x)，即A_tσ_z=A_tσ_y·$\boldsymbol{\tilde D} $_x+yA_tσ_x，即可得到A_tσ_z=D_z+(xANDy)B。

2) 由‖$\boldsymbol{\tilde D} $_x‖≤poly(m)和σ_z=σ_y·$\boldsymbol{\tilde D} $_x+yσ_x，我们可以得到‖σ_z‖≤‖σ_y‖·poly(m)+‖σ_x‖。

由于与门和异或门可以组合成为完备电路，因此我们可以最终得出结论：A_tσ_C=D_C+C(u)B。

2.3 安全性

如果存在一个敌手$\mathscr{A} $能够赢得1.2节中提到的选择性不可伪造安全游戏，就可以构造另一个敌手$\mathscr{A} $^*能够破解由A′∈Z_q^n×m所定义的格上的SIS_q，m，β(t^*，$\overrightarrow {{\boldsymbol{u}^*}} $)困难问题，其中β=β(n，d_max)为签名的尺寸上界。假设(t^*，$\overrightarrow {{\boldsymbol{u}^*}} $)为敌手$\mathscr{A} $挑战的数据集标签和伪造所要用到的消息向量。根据(t^*，$\overrightarrow {{\boldsymbol{u}^*}} $)的不同可以分为两类伪造。伪造类型(Ⅰ)：$\overrightarrow {{\boldsymbol{u}^*}} $为空，敌手将不对t^*中的任何签名进行询问。伪造类型(Ⅱ)：假设q为最大签名询问次数，令v^*∈[q]为随机选择的询问猜测。敌手$\mathscr{A} $^*将运行以下两个模拟实验步骤：

1) 如果敌手不对t^*进行任何签名询问，则可以运行以下步骤，从而破解SIS_q，m，β(t^*，$\overrightarrow {{\boldsymbol{u}^*}} $)困难问题。

① 随机抽取U∈{-1，1}^m×n并令：

$ \boldsymbol{A} = \boldsymbol{A}' \cdot \boldsymbol{U}{t^*}Bod q $

D_i=A′·U_i，(B，T_B)通过引理1生成。

② 将(Α，Α′，B，T_B，D_i)作为公钥交给敌手。由引理1.3和引理1.4可证得A′U，A′U-tB，统计接近于随机均匀分布。因此该公钥与真实方案中的公钥统计不可以区分。

③ 由于敌手没有对t^*进行签名询问，我们就可以随机选择一个t，使得t-t^*≠0(t-t^*=0的概率可忽略不计)，然后通过陷门T_B进行右采样输出敌手所需的签名询问：

$ {\boldsymbol{\sigma} _i} \leftarrow {\text{SampleRight}}\left( {\boldsymbol{A}', \left( {t-{t^*}} \right)\boldsymbol{B}, \boldsymbol{U}, {\boldsymbol{T}_{{B^*}}}, {\boldsymbol{D}_i} + {u_i}\boldsymbol{B}, {s_2}} \right) $

由右采样定理可知：

$ \boldsymbol{F} \cdot {\boldsymbol{\sigma} _i} = \left( {\boldsymbol{A}'\left| {\boldsymbol{A}'\boldsymbol{U} + \left( {t-{t^*}} \right)\boldsymbol{B}} \right.} \right) \cdot {\boldsymbol{\sigma} _i} = {\boldsymbol{A}_t} \cdot {\boldsymbol{\sigma} _i} = {\boldsymbol{D}_i} + {u_i}\boldsymbol{B} $

④ 敌手伪造签名σ^*。

假设敌手成功伪造签名σ^*，则有:A_tσ^*=D_C+u^*B mod q，即：[A′|A′U-t^*B+t^*B]σ^*=D_C+u^*B，由于D_C可以表示成A′U_C+kB的形式，令${\boldsymbol{\sigma} ^{\text{*}}}{\text{ = }}\frac{{{\boldsymbol{\sigma} _1}}}{{{\boldsymbol{\sigma} _2}}} $所以有：A′(σ₁+σ₂U-U_C)=(k+u^*)B，如果k+u^*=0，则σ₁+σ₂U-U_C就是SIS困难问题的解，如果k+u^*≠0，则(σ₁+σ₂U-U_C)T_B就是SIS困难问题的解。

2) 假设对t^*进行了次数不超过q次的签名询问，则可以运行以下步骤，从而破解SIS_q，m，β(t^*，$\overrightarrow {{\boldsymbol{u}^*}} $)困难问题。

① 随机抽取U∈{-1，1}^m×n并令：A=A′U-t^*B mod q，从分布(D_Z^m, s₂)^2m中随机抽取样本σ_i，并且令

D_i=[A′|A′U_i]σ_i-u_i^*B，(B，T_B)通过引理1.1生成。

② 将(Α，Α′，B，T_B，D_i)作为公钥交给敌手。由引理1.3和引理1.4可知，该公钥与真实方案中的公钥统计不可以区分。

③ 敌手进行签名询问，由于D_i=[A′|A′U_i]σ_i-u_i^*B，所以[A′|A′U_i]σ_i=D_i+u_i^*B直接成立。

④ 敌手给出伪造签名σ^*。

假设敌手成功伪造签名σ^*，则有A_tσ^*=D_C+u^*B mod q，由于敌手对t^*进行了访问，所以必须保证C($\overrightarrow {{\boldsymbol{u}^*}} $)≠u^*，假设σ′是真正的签名，则有A_t(σ^*-σ′)=(C($\overrightarrow {{\boldsymbol{u}^*}} $)-u^*)B mod q。令${\boldsymbol{\sigma} ^{\text{*}}}{\text{-}}\boldsymbol{\sigma} '{\text{ = }}\frac{{{\boldsymbol{\sigma} _1}}}{{{\boldsymbol{\sigma} _2}}} $则有，A′(σ₁+σ₂U)T_B=(C($\overrightarrow {{\boldsymbol{u}^*}} $)B T_B mod q，因此(σ₁+σ₂U)T_B就是SIS困难问题的解。

2.4 方案分析

λ为安全参数，n=poly(λ)，：签名尺寸上限为B=ω(2^d_max)，令q=q(n)=n^O(d_max)>B，m=O(nlogq)，高斯参数${s_1} = O\left( {\sqrt {n\log q} } \right) $，为了让左取样和右取样统计不可区分，令${s_1} = \omega \left( {m\log q\sqrt {\log m} } \right) $，由左取样定义可知${\left\| {\text{e}} \right\|_\infty } \leqslant {s_2}\sqrt m $，又因为${\left\| {{\boldsymbol{{\tilde D}}_u}} \right\|_\infty } \leqslant {s_1}\sqrt m $，所以有‖D_w‖_∞≤O(s₁s₂m)，即‖D_w‖≤O(s₁s₂m³)，所以最终签名尺寸满足‖σ_C‖≤β=m^O(d_max)。

方案由于采用了与电路，使得两个与电路的输出电路公钥满足：${\boldsymbol{D}_{\text{w}}} = {\boldsymbol{D}_{\text{v}}}{\boldsymbol{\tilde D}_{\text{u}}} $，所以实现了1) 电路原理简单，电路容易实现。2) 最终电路公钥表达式可以化简成D_C=A×U_C，表达式只与各门电路电路公钥有关，因此支持离线(在签名数据输入之前就可以计算电路的最终公钥表达式)和分摊运算(对于在同一电路上进行不同签名消息的同态运算可以循环利用电路公钥)，这将大大提高最终签名的验证的速度。3) 可以运用一些约减技术对电路的噪声进行优化，便于进一步提高方案所允许的电路深度。

3 结论

1) 本文利用同态加密和签名研究中用到的陷门采样技术，首次利用与门和异或门构造了一个层次全同态签名方案。该方案不同于线性同态签名或者多项式同态签名，允许对签名数据进行任意电路运算。

2) 方案支持离线分摊运算(可以在接受原始签名数据之前预先计算电路(函数)公钥)，因此拥有更高的签名验证效率。任何人可以在不知道原始签名数据的情况下使用公钥进行公开验证。

3) 方案基于格上小整数解困难问题选择性不可伪造。虽然签名尺寸的增长速度得到了优化(随电路深度而不是电路尺寸呈多项式增长)，但是为了能够在实际中得到运用，方案的效率还有待进一步提高。如何运用哈希函数来减小公钥尺寸，并将同态加密中用到的方案优化手段运用到全同态签名中是一个值得研究的内容。