基于标准格的层次全同态签名

欧阳卫平， 马春光， 李增鹏，杜刚

(1.哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001； 2.哈尔滨工程大学 教务处，黑龙江 哈尔滨 150001； 3.哈尔滨工程大学 国家保密学院，黑龙江 哈尔滨 150001)



基于标准格的层次全同态签名

欧阳卫平1，2， 马春光1，3， 李增鹏1，杜刚1

(1.哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001； 2.哈尔滨工程大学 教务处，黑龙江 哈尔滨 150001； 3.哈尔滨工程大学 国家保密学院，黑龙江 哈尔滨 150001)

为了支持任意电路上签名数据同态运算，本文利用陷门采样技术，基于与门和异或门构造了一个只受电路深度和安全参数影响的层次全同态签名方案。电路生成的新签名具有公开可验证性，新签名尺寸与电路尺寸以及原签名数据的尺寸无关。方案在标准模型下基于格上最短整数解困难问题可证安全。用户可以在不知道私钥的情况下进行指定签名集合中签名的层次全同态运算，已有的研究还主要集中在线性同态方案和多项式同态方案。

签名；层次全同态；格；不可伪造；任意电路；与门；异或门

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

同态签名的概念最早由Johson等在2002年正式提出，当时主要是为了解决网络路由编码中根节点路由对叶节点子网签名数据进行聚合的问题[1]。同态签名可以简单描述为：已知消息元组m=(m1，m2,…,ml)，公钥pk以及消息元组对应的签名元组σ=(σ1，σ2，…,σl)，同态签名算法能够在不知道私钥的情况下利用签名元组生成消息u=f(m1，m2,…,ml)上的同态签名σ′，给定元组(σ′，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.2 同态签名

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

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

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

Eval(pk，τ，u=(u1，…，ul)，σ=(σ1，…，σl)，C)：输入消息串u及对应的签名串σ，电路C∈C，输出消息u′=C(u)的签名σ′。

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

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

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

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

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

2)敌手选择数据u1，…ul∈M并将其发送给挑战者。

3)挑战者计算(σ1，σ2，…，σl)←Signsk(u1，…，ul)，并将签名(σ1，…，σl)给敌手。

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

2 层次全同态签名方案

2.1 方案描述

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

1)系统建立(1λ)：

③输出(Α，Α′，B，TB，Di)作为公钥pk，TΑ′作为私钥sk。

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

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

σu←SampleLeft(Α′，Α+tB，TA′，Du+uB，s2)，令Αt=[Α′|Α+tB]，则有：Αtσu=D--u+uB。

②输出σu

①异或门运算：σz=σx+σy

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

①‖σC‖∞≤β

2.2 正确性

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

引理5：令σx、σy分别是x、y的签名，则有：Atσx=Dx+xB，Atσy=Dy+yB，如果令Dz=Dx+Dy，则有Atσz=Dz+(xXORy)B，满足：‖σz‖≤‖σx‖+‖σy‖。

证明：1)由异或门运算公式可得：σz=σx+σy，所以有Atσz=At(σx+σy)，即Atσz=Atσx+Atσy，又因为Atσx=Dx+xB，Atσy=Dy+yB，代入Dz=Dx+Dy，即可得到Atσz=Dz+(xXORy)B。

2)由σz=σx+σy直接可得‖σz‖≤‖σx‖+‖σy‖。

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

2.3 安全性

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

A=A′·Ut*Bmodq

Di=A′·Ui，(B，TB)通过引理1生成。

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

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

σi←SampleRight(Α′，(t-t*)B，U，TB*，Di+uiB，s2)

由右采样定理可知：

F·σi=(Α′|Α′U+(t-t*)B)·σi=Αt·σi=Di+uiB

④敌手伪造签名σ*。

①随机抽取U∈{-1，1}m×n并令：A=A′U-t*Bmodq，从分布(DZm,s2)2m中随机抽取样本σi，并且令

Di=[A′|A′Ui]σi-ui*B，(B，TB)通过引理1.1生成。

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

③敌手进行签名询问，由于Di=[A′|A′Ui]σi-ui*B，所以[A′|A′Ui]σi=Di+ui*B直接成立。

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

2.4 方案分析

3 结论

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

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

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

[1]JOHNSON R， MOLNAR M， SONG X， et al. Homomorphic signature schemes[C]∥Berlin， Springer， 2002: 18-22.

[2]KROHN M， FREEDMAN M， MAZIERES D.On-the-y verication of rateless erasure codesfor efcient content distribution[C]∥Proc of IEEE Symposium on Security and Privacy， 2004: 226-240.

[3]ZHAO F， KALKER T， M′EDARD M， et al. Signatures for content distribution with network coding[C]∥Proc Intl Symp Info Theory (ISIT), 2007.

[4]CHARLES D， JAIN K， LAUTER K. Signatures for network coding[J]. International journal of information and coding theory 1(1)， 2009: 3-14.

[5]BONEH D， FREEMAN D， KATZ J, et al. Signing a linear subspace: signature schemes for network coding[C]∥PKC, 2009: 68-87.

[6]BONEH D， FREEMAN D. Linearly homo-morphic signatures over binaryelds and new tools for lattice-based signatures[C]∥PKC 2011: 1-16.

[7]WANG F， HU Y， WANG B. Lattice-based linearly homomorphic signature scheme over binary field[J]. Science China information sciences， 2013: 1-9.

[8]JING Z J. An efficient homomorphic aggregate signature scheme based on lattice[J]. Mathematical problems in engineering， 2014.

[9]BONEH D， FREEMAN D M. Homomorphic signatures for polynomial functions[C]∥Proceedings of Eurocrypt Berlin SpringerVerlag， 2011: 149-168.

[10]BACKES M， FIORE D， RAPHAEL R. Ver-iable delegation of computation on outsourced data[C]∥Conference on Computer and Communications Security， 2013: 863-874.

[11]CATALANO D，FIORE D. Practical homo-morphic macs for arithmetic circuits[C]∥In Johansson and Nguyen，2013: 336-352.

[12]CATALANO D， FIORE D， GENNARO R， et al. Generalizing homomorphic macs for arithmetic circuits[C]∥In Hugo Krawczyk， volume 8383 of Lecture Notes in Computer Science， 2014: 538-555.

[13]MICCIANCIO D， GOLDWASSER S. Complex-ity of lattice problems: a cryptographic perspective[M]. Springer, 2002.

[14]MICCIANCIO D， REGEV O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM journal on computing， 2007: 267-302.

[15]GENTRY C， PEIKERT C， VAIKUNTANA-THAN V. Trapdoors for hard lattices and new cryptographic constructions[C]∥Proceedings of the 40th Annual ACM Symposium on Theory of Computing. ACM， 2008: 197-206.

[16]ALWEN J，PEIKERT C. Generating shorter bases for hard random lattice [C]∥Proceeding of26thInternational Symposium on Theoretical Aspectsof Computer Science. Springer， 2009: 535-553.

[17]MICCIANCIO D， PEIKERT C. Trapdoors for lattices: Simpler， tighter， faster， smaller[M]. Advances in cryptology eurocrypt 2012. Springer Berlin Heidelberg， 2012: 700-718.

[18]AGRAWAL S， BONEH D， BOYEN X. Efficient lattice (H) IBE in the standard model[M]. Advances in cryptology eurocrypt 2010. Springer Berlin Heidelberg， 2010: 553-572.

[19]GENTRY C.Fully homomorphic encryption using ideal lattices[C]∥Proceedings of the 41st annual ACM symposium on Theory of computing. Bethesda， ACM， 2009: 169-178.

[20]BRAKERSKI Z， VAIKUNTANATHAN V. Fully HomomorphicEncryption from Ring-LWE and Security for key dependent messages [C]∥Springer Berlin Heidelberg, 2011: 505-524.

[21]BRAKERSKI Z，VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]∥Proceeding of IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011: 97-106.

[22]BRAKERSKI Z， GENTRY C，VAIKUNT V. (Leveled) fully homomorphic encryption without bootstrapping[C]∥Proceedings ofthe 3rd Innovations in Theoretical Computer Science Conference. Massachusetts; ACM, 2012: 309-325.

[23]BONEH D， GENTRY C， GORBUNOV S， et al. Fully key-homomorphic encryption， arithmetic circuit abe and compact garbled circuits[C]∥Lecture Notes in Computer Science， 2014: 533-556.

本文引用格式：

欧阳卫平， 马春光， 李增鹏，等. 基于标准格的层次全同态签名[J]. 哈尔滨工程大学学报， 2017， 38(5)： 766-770.

OUYANG Weiping， MA Chunguang， LI Zengpeng， et al. Leveled fully homomorphic signatures based on standard lattices[J]. Journal of Harbin Engineering University， 2017， 38(5)： 766-770.

Leveled fully homomorphic signatures based on standard lattices

OUYANG Weiping1，2， MA Chunguang1，3，LI Zengpeng1，DU Gang1

(1.College of Computer Science and Technology， Harbin Engineering University， Harbin 150001， China; 2.Academic Affairs Office，Harbin Engineering University， Harbin 150001， China; 3.College of National Secrecy， Harbin Engineering University， Harbin 150001， China)

To construct a homomorphic scheme that supports the homomorphic computation of signatures in certain signature sets on arbitrary circuits， we used trapdoor sampling technology to construct a leveled fully homomorphic signature scheme based on the AND and XOR gates， which can support homomorphic computation on arbitrary circuits. In addition， the size of the new signature is independent of the circuit size and initial signature sizes， but depends on the depth of the circuits and security parameters. We verified the security of this scheme using the random oracle model based on the difficulty of finding small integer solutions (SIS) in lattices. Users can conduct leveled homomorphic computation on a designated signature set despite not knowing the secret key. Published research has also focused on linear and polynomial homomorphic schemes.

signature; leveled fully homomorphic; lattice; unforgeability; arbitrary electric circuit; AND gate; XOR gate

2016-02-29.

日期：2017-04-26.

国家自然科学基金项目(61170241，61472097).

欧阳卫平(1982-)，男，博士研究生； 马春光(1974-)，男，教授，博士生导师.

欧阳卫平，E-mail：ouyangweiping@hrbeu.edu.cn.

10.11990/jheu.201602046

TP309

A

1006-7043(2017)05-0766-05

网络出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170426.1041.020.html