基于標準格的層次全同態簽名

歐陽衛平， 馬春光， 李增鵬，杜剛

(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