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

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

(1.哈爾濱工程大學(xué) 計(jì)算機(jī)科學(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é) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001； 2.哈爾濱工程大學(xué) 教務(wù)處，黑龍江 哈爾濱 150001； 3.哈爾濱工程大學(xué) 國家保密學(xué)院，黑龍江 哈爾濱 150001)

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

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

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

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

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

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

1.1 格的定義和SIS問題

1.2 同態(tài)簽名

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

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

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

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

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

輸出1代表驗(yàn)證通過，0代表驗(yàn)證失敗。

正確性：我們說一個(gè)電路同態(tài)簽名方案是正確的是指對(duì)于任意τ∈{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)者計(jì)算(σ1，σ2，…，σl)←Signsk(u1，…，ul)，并將簽名(σ1，…，σl)給敵手。

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

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

2.1 方案描述

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

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

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

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

①消息u對(duì)應(yīng)的簽名可由引理1.3中的左抽樣算法獲得：

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

②輸出σu

①異或門運(yùn)算：σz=σx+σy

③由于前一層門電路的輸出可以作為后一層門電路的輸入，所以通過迭代運(yùn)算后可以得到最終簽名σC∈Z2m×m。

①‖σC‖∞≤β

2.2 正確性

我們以具有兩個(gè)輸入和一個(gè)輸出的門電路的運(yùn)算為例，證明電路同時(shí)支持與門和異或門運(yùn)算，復(fù)雜電路的運(yùn)算可以通過對(duì)兩種電路進(jìn)行組合實(shí)現(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)由異或門運(yùn)算公式可得：σz=σx+σy，所以有Atσz=At(σx+σy)，即Atσz=Atσx+Atσy，又因?yàn)锳tσ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 安全性

①隨機(jī)抽取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)計(jì)接近于隨機(jī)均勻分布。因此該公鑰與真實(shí)方案中的公鑰統(tǒng)計(jì)不可以區(qū)分。

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

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

由右采樣定理可知：

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

④敵手偽造簽名σ*。

①隨機(jī)抽取U∈{-1，1}m×n并令：A=A′U-t*Bmodq，從分布(DZm,s2)2m中隨機(jī)抽取樣本σi，并且令

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

②將(Α，Α′，B，TB，Di)作為公鑰交給敵手。由引理1.3和引理1.4可知，該公鑰與真實(shí)方案中的公鑰統(tǒng)計(jì)不可以區(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)造了一個(gè)層次全同態(tài)簽名方案。該方案不同于線性同態(tài)簽名或者多項(xiàng)式同態(tài)簽名，允許對(duì)簽名數(shù)據(jù)進(jìn)行任意電路運(yùn)算。

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

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