歐陽衛(wèi)平， 馬春光， 李增鵬，杜剛

(1.哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001； 2.哈爾濱工程大學(xué) 教務(wù)處，黑龍江 哈爾濱 150001； 3.哈爾濱工程大學(xué) 國家保密學(xué)院，黑龍江 哈爾濱 150001)

?

基于標(biāo)準(zhǔn)格的層次全同態(tài)簽名

歐陽衛(wèi)平1，2， 馬春光1，3， 李增鵬1，杜剛1

(1.哈爾濱工程大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001； 2.哈爾濱工程大學(xué) 教務(wù)處，黑龍江 哈爾濱 150001； 3.哈爾濱工程大學(xué) 國家保密學(xué)院，黑龍江 哈爾濱 150001)

為了支持任意電路上簽名數(shù)據(jù)同態(tài)運算，本文利用陷門采樣技術(shù)，基于與門和異或門構(gòu)造了一個只受電路深度和安全參數(shù)影響的層次全同態(tài)簽名方案。電路生成的新簽名具有公開可驗證性，新簽名尺寸與電路尺寸以及原簽名數(shù)據(jù)的尺寸無關(guān)。方案在標(biāo)準(zhǔn)模型下基于格上最短整數(shù)解困難問題可證安全。用戶可以在不知道私鑰的情況下進(jìn)行指定簽名集合中簽名的層次全同態(tài)運算，已有的研究還主要集中在線性同態(tài)方案和多項式同態(tài)方案。

簽名；層次全同態(tài)；格；不可偽造；任意電路；與門；異或門

近年來，隨著云計算的發(fā)展，具有同態(tài)性質(zhì)的認(rèn)證技術(shù)如同態(tài)消息認(rèn)證碼、同態(tài)委托計算、同態(tài)簽名等引起了大家的廣泛關(guān)注。這些技術(shù)主要應(yīng)用于網(wǎng)絡(luò)安全編碼、傳感網(wǎng)絡(luò)、外包計算、可取回證明等領(lǐng)域。同態(tài)簽名由于其公開可驗證等特點，相對于其他幾種技術(shù)具有更為廣泛的應(yīng)用空間。

同態(tài)簽名的概念最早由Johson等在2002年正式提出，當(dāng)時主要是為了解決網(wǎng)絡(luò)路由編碼中根節(jié)點路由對葉節(jié)點子網(wǎng)簽名數(shù)據(jù)進(jìn)行聚合的問題[1]。同態(tài)簽名可以簡單描述為：已知消息元組m=(m1，m2,…,ml)，公鑰pk以及消息元組對應(yīng)的簽名元組σ=(σ1，σ2，…,σl)，同態(tài)簽名算法能夠在不知道私鑰的情況下利用簽名元組生成消息u=f(m1，m2,…,ml)上的同態(tài)簽名σ′，給定元組(σ′，u，f)，任何人可以公開驗證簽名σ′的有效性。

同態(tài)簽名的發(fā)展具有幾個標(biāo)志性的階段。第一個階段是線性同態(tài)[2-9]。文獻(xiàn)[2-4]對基于離散對數(shù)困難問題提出了線性同態(tài)的哈希函數(shù)和簽名，主要為了解決點對點內(nèi)容發(fā)布系統(tǒng)中的網(wǎng)絡(luò)優(yōu)化及安全問題(抗污染攻擊)。文獻(xiàn)[5]提出了第一個基于RSA假設(shè)的線性同態(tài)簽名。由于傳統(tǒng)的困難問題將隨著量子計算的發(fā)展而面臨被攻破的危險，目前很多密碼學(xué)領(lǐng)域?qū)＜乙呀?jīng)開始利用新的困難問題來構(gòu)造密碼學(xué)方案。由于格具有：1)格上運算簡單(矩陣、向量的加和乘)；2)格上困難問題能抗量子攻擊；3)格上最壞情況下和平均情況下的困難問題可以進(jìn)行規(guī)約等特點。目前很多密碼學(xué)原語都是基于格上困難問題構(gòu)造的?；诟竦木€性同態(tài)簽名中比較有代表性的是Boneh等人在2011年提出的一個具有弱內(nèi)容隱藏，并且在隨機預(yù)言機模型下可證安全的線性同態(tài)簽名，該方案是首個基于標(biāo)準(zhǔn)格上的困難問題并建立在二元域上的線性同態(tài)簽名[6]。之后出現(xiàn)了很多改進(jìn)方案，如Wang等對文獻(xiàn)[6]進(jìn)行了改進(jìn)，通過引入一個哈希函數(shù)，使得方案具有更短的公鑰和簽名尺寸，同時由于不再需要使用盆景樹算法，計算效率也得到了提高[7]。Jing等在文獻(xiàn)[7]的方案基礎(chǔ)上提出一個適用于多用戶的二元域上格基聚合簽名方案，方案中聚合消息的簽名可用一個通用公鑰進(jìn)行驗證，與文獻(xiàn)[7]的方案相比，具有更短簽名長度，并且不受用戶數(shù)量限制[8]。第二個階段是有限同態(tài)(以多項式同態(tài)為代表)。2011年Boneh等通過將線性簽名進(jìn)行擴(kuò)展，用理想格代替標(biāo)準(zhǔn)格，構(gòu)造了第一個能夠?qū)灻麛?shù)據(jù)進(jìn)行多項式運算的同態(tài)簽名方案[9]。對于常指數(shù)多項式，方案最終生成簽名的尺寸取決于數(shù)據(jù)集尺寸的對數(shù)。類似的，文獻(xiàn)[10-12]將多項式同態(tài)運用于消息認(rèn)證。由于同態(tài)加密已經(jīng)經(jīng)歷了從線性同態(tài)到部分同態(tài)再到全同態(tài)的發(fā)展歷程，而同態(tài)簽名正是借用了同態(tài)加密的思想而發(fā)展起來的，因此同態(tài)簽名也將經(jīng)歷這樣一個發(fā)展歷程。但是目前國內(nèi)外還沒有相關(guān)的研究能夠?qū)崿F(xiàn)真正意義上的全同態(tài)簽名。真正意義上的全同態(tài)簽名能夠?qū)崿F(xiàn)對簽名數(shù)據(jù)進(jìn)行任意(電路)運算，不受電路尺寸和深度影響，并且支持公開認(rèn)證，將成為簽名技術(shù)發(fā)展的一個里程碑。本文基于格上SIS困難問題，利用異或門和與門構(gòu)造了一個層次全同態(tài)簽名方案，方案生成的新簽名尺寸與電路尺寸以及被簽名數(shù)據(jù)的尺寸無關(guān)，只受電路深度和安全參數(shù)影響，同時電路具有較高的計算效率，方案在標(biāo)準(zhǔn)模型下可證安全。

1 格上困難問題與同態(tài)簽名

1.1 格的定義和SIS問題

1.2 同態(tài)簽名

定義：令消息空間為M，允許電路集合為C(允許電路在這里指能夠保證電路輸出簽名噪聲在控制范圍內(nèi))，C:M→M代表C中的一個電路，輸入端最多同時接受個輸入，輸出端為1個輸出，同態(tài)簽名可以表示為一個元組(Setup，Sign，Eval，Verify)

Setup(1λ，1l)：輸入安全參數(shù)λ和該消息集的最大輸入尺寸l，輸出一個公鑰pk和一個私鑰sk。

Sign(sk，τ，i，u)：輸入一個私鑰sk，標(biāo)簽τ(唯一標(biāo)識一個消息集合)，消息u∈{0，1}λ及其索引i∈[l]，輸出一個簽名σ。

Eval(pk，τ，u=(u1，…，ul)，σ=(σ1，…，σl)，C)：輸入消息串u及對應(yīng)的簽名串σ，電路C∈C，輸出消息u′=C(u)的簽名σ′。

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

輸出1代表驗證通過，0代表驗證失敗。

正確性：我們說一個電路同態(tài)簽名方案是正確的是指對于任意τ∈{0，1}λ，電路C∈C，消息集合u∈M，以及任意索引i∈[l]，滿足：Pr[Verify(pk，τ，u′，σ′，C)=1]=1。

選擇性不可偽造安全游戲：敵手和挑戰(zhàn)者之間展開以下游戲：

1)挑戰(zhàn)者生成prms←PrmsGen(1λ，1l)和(pk，sk)←KeyGen(1λ，prms)，并將prms，pk給敵手。

2)敵手選擇數(shù)據(jù)u1，…ul∈M并將其發(fā)送給挑戰(zhàn)者。

3)挑戰(zhàn)者計算(σ1，σ2，…，σl)←Signsk(u1，…，ul)，并將簽名(σ1，…，σl)給敵手。

4)敵手選擇一個函數(shù)C*:M→M和兩個值u*、σ*，令u′=C(u)。敵手贏得游戲需要滿足三個條件：①C*是允許電路，②u*≠u′，③Pr[Verify(pk，u*，σ*，C)=1]=1。

2 層次全同態(tài)簽名方案

2.1 方案描述

參數(shù)設(shè)置：方案中允許電路C(由若干與門和異或門組成)每次最多允許有l(wèi)個輸入(σ1，σ2，…，σl)，并假設(shè)門電路的輸入為σx、σy(x，y為消息，σx、σy為消息對應(yīng)的簽名)，輸出為σz，電路的最大深度為dmax。簽名尺寸上限為β=β(n，dmax)∈Z，高斯參數(shù)s1=s1(n)，s2=s2(n)，消息集合對應(yīng)的標(biāo)簽為t。方案分為四個環(huán)節(jié)：系統(tǒng)建立、簽名、同態(tài)運算及驗證。

1)系統(tǒng)建立(1λ)：

③輸出(Α，Α′，B，TB，Di)作為公鑰pk，TΑ′作為私鑰sk。

2)簽名(sk，t，i，u)：輸入密鑰sk，標(biāo)簽t，消息索引i和消息u，算法如下：

①消息u對應(yīng)的簽名可由引理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 正確性

我們以具有兩個輸入和一個輸出的門電路的運算為例，證明電路同時支持與門和異或門運算，復(fù)雜電路的運算可以通過對兩種電路進(jìn)行組合實現(xiàn)。

引理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‖。

由于與門和異或門可以組合成為完備電路，因此我們可以最終得出結(jié)論：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ǒng)計接近于隨機均勻分布。因此該公鑰與真實方案中的公鑰統(tǒng)計不可以區(qū)分。

③由于敵手沒有對t*進(jìn)行簽名詢問，我們就可以隨機選擇一個t，使得t-t*≠0(t-t*=0的概率可忽略不計)，然后通過陷門TB進(jìn)行右采樣輸出敵手所需的簽名詢問：

σ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可知，該公鑰與真實方案中的公鑰統(tǒng)計不可以區(qū)分。

③敵手進(jìn)行簽名詢問，由于Di=[A′|A′Ui]σi-ui*B，所以[A′|A′Ui]σi=Di+ui*B直接成立。

④敵手給出偽造簽名σ*。

2.4 方案分析

3 結(jié)論

1)本文利用同態(tài)加密和簽名研究中用到的陷門采樣技術(shù)，首次利用與門和異或門構(gòu)造了一個層次全同態(tài)簽名方案。該方案不同于線性同態(tài)簽名或者多項式同態(tài)簽名，允許對簽名數(shù)據(jù)進(jìn)行任意電路運算。

2)方案支持離線分?jǐn)傔\算(可以在接受原始簽名數(shù)據(jù)之前預(yù)先計算電路(函數(shù))公鑰)，因此擁有更高的簽名驗證效率。任何人可以在不知道原始簽名數(shù)據(jù)的情況下使用公鑰進(jìn)行公開驗證。

3)方案基于格上小整數(shù)解困難問題選擇性不可偽造。雖然簽名尺寸的增長速度得到了優(yōu)化(隨電路深度而不是電路尺寸呈多項式增長)，但是為了能夠在實際中得到運用，方案的效率還有待進(jìn)一步提高。如何運用哈希函數(shù)來減小公鑰尺寸，并將同態(tài)加密中用到的方案優(yōu)化手段運用到全同態(tài)簽名中是一個值得研究的內(nèi)容。

[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，F(xiàn)IORE 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.

本文引用格式：

歐陽衛(wèi)平， 馬春光， 李增鵬，等. 基于標(biāo)準(zhǔn)格的層次全同態(tài)簽名[J]. 哈爾濱工程大學(xué)學(xué)報， 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.

國家自然科學(xué)基金項目(61170241，61472097).

歐陽衛(wèi)平(1982-)，男，博士研究生； 馬春光(1974-)，男，教授，博士生導(dǎo)師.

歐陽衛(wèi)平，E-mail：ouyangweiping@hrbeu.edu.cn.

10.11990/jheu.201602046

TP309

A

1006-7043(2017)05-0766-05

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20170426.1041.020.html