基于格的后量子秘密握手方案

安致遠(yuǎn) 溫雅敏 張方國(guó)

摘 ? 要：秘密握手協(xié)議作為一種新型的密碼學(xué)應(yīng)用，允許屬于同一組織的個(gè)體在保護(hù)隱私的前提下進(jìn)行秘密的雙向認(rèn)證。目前針對(duì)秘密握手的方案多基于一些傳統(tǒng)困難問(wèn)題，這些問(wèn)題在量子算法攻擊下都不再安全。文章通過(guò)修改已有的基于身份的消息恢復(fù)簽名[1]，提出了一個(gè)基于格上小整數(shù)解問(wèn)題的秘密握手協(xié)議，其在隨機(jī)預(yù)言機(jī)模型下可證明安全，協(xié)議雙方協(xié)商得到的會(huì)話密鑰長(zhǎng)度適中，整體效率也具有可實(shí)踐性。

關(guān)鍵詞：秘密握手;隱私保護(hù);格密碼;消息恢復(fù)簽名;可證明安全

中圖分類號(hào)： TP309 ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： Secret handshake scheme allows the members of a certain organization to conduct a two-way authentication under the premise of privacy protection. At present， most secret handshake schemes are based on some traditional difficult problems， which are not secure when faced with quantum computers' attacks. Based on an identity-based message recovery signature[1]， this paper proposes a secret handshake scheme whose security is under lattices short integer solution assumption. Its provably secure in the random oracle model， the length of the private session key negotiated by both participants is suitable for communication， runtime performance is also practically acceptable.

Key words： secret handshake; privacy protection; lattice cryptography; message recovery signature; provable securit

1 引言

秘密握手方案是一種滿足隱私保護(hù)安全需求的雙向認(rèn)證協(xié)議，最早是由Balfanz等人[2]在2003年提出，它允許屬于同一組織的不同成員可以進(jìn)行秘密的認(rèn)證而不泄露彼此的隱私信息，當(dāng)且僅當(dāng)協(xié)議雙方擁有相同的組織公鑰證書(shū)時(shí)，認(rèn)證過(guò)程才能成功，而如果通信雙方屬于不同組織，則認(rèn)證過(guò)程不會(huì)暴露雙方彼此的組織信息。在當(dāng)今互聯(lián)網(wǎng)迅猛發(fā)展的時(shí)代，大量用戶認(rèn)證和接入服務(wù)尤其需要滿足用戶的隱私保護(hù)需求，這使得秘密握手的應(yīng)用前景變得非常廣泛，一個(gè)典型的例子就是網(wǎng)上辦公的兩名公司員工在傳輸公司高級(jí)機(jī)密時(shí)的秘密雙向認(rèn)證。

近些年有許多兩方/多方秘密握手方案被提出[3～11]，但這些基于傳統(tǒng)困難問(wèn)題（離散對(duì)數(shù)，平方根剩余等）的方案在量子攻擊下不再安全。而隨著量子計(jì)算的飛速發(fā)展，具有抗量子攻擊特性的格密碼體制則受到更多的青睞。

本文通過(guò)借鑒一種通用構(gòu)造：將基于身份的消息恢復(fù)簽名（Identity-based Message Recovery Signature， ID-MRS）轉(zhuǎn)化為基于一次性偽名的秘密握手方案[3]，修改格上的ID-MRS[1]設(shè)計(jì)了一個(gè)后量子的兩方秘密握手方案，該方案在隨機(jī)預(yù)言機(jī)模型下可證明安全，協(xié)議會(huì)話密鑰適中，整體運(yùn)行效率具有可實(shí)踐性。

2 預(yù)備知識(shí)

2.1 符號(hào)和定義

文中正整數(shù)n均表示秘密握手方案中的安全參數(shù)，，表示整數(shù)集合，表示實(shí)數(shù)集合。令，，對(duì)任意，表示多項(xiàng)式c的第i個(gè)系數(shù)，滿足。比特函數(shù)的功能是計(jì)算由多項(xiàng)式c的系數(shù)中的最高有效位組成的比特字符串，即為1，當(dāng)且僅當(dāng)，否則為0。黑體小寫(xiě)字母如代表列向量，為的轉(zhuǎn)置;黑體大寫(xiě)字母如代表矩陣。向量的歐幾里得范數(shù)記為。表示矩陣的第i列向量，。滿秩方陣的Gram-Schmidt正交化矩陣為。文中所有對(duì)數(shù)函數(shù)底數(shù)都為2。

4 安全和效率分析

4.1 安全分析

文獻(xiàn)[1]中已經(jīng)證明了在SIS困難問(wèn)題前提下，本文運(yùn)用的ID-MRS方案在隨機(jī)預(yù)言機(jī)模型下是EU-ACMA的，類似文獻(xiàn)[3]中的證明思路，下面給出本文秘密握手方案的安全證明。

定理3 ?若基礎(chǔ)的ID-MRS方案在隨機(jī)預(yù)言機(jī)模型下是EU-ACMA的，則本文提出的秘密握手方案滿足防偽造性。

證明：秘密握手方案的防偽造性是通過(guò)攻擊者和挑戰(zhàn)者實(shí)施的一個(gè)攻擊游戲來(lái)形式化定義的，詳細(xì)的攻擊游戲描述可參考文獻(xiàn)[17]。若存在一個(gè)適應(yīng)性攻擊者試圖偽造為一名合法成員，與屬于同一組織的某一個(gè)誠(chéng)實(shí)用戶B（偽名為）進(jìn)行一次秘密握手協(xié)議，且可以在多項(xiàng)式時(shí)間界限t內(nèi)以一個(gè)不可忽略的概率驗(yàn)證成功，則在協(xié)議過(guò)程中一定向B發(fā)送了正確的回應(yīng)標(biāo)簽，其中是由和恢復(fù)出來(lái)的共同計(jì)算得到的。也就是說(shuō)被B驗(yàn)證通過(guò)了，則一定事先向預(yù)言機(jī)詢問(wèn)了關(guān)于的映射結(jié)果。為了使得與B通過(guò)發(fā)送的ID-MRS（）恢復(fù)出來(lái)的計(jì)算得到的會(huì)話密鑰相同，本文可以得知，在秘密握手第一輪步驟中由發(fā)送的ID-MRS（）是在沒(méi)有組織證書(shū)前提下偽造的可驗(yàn)證成功的消息恢復(fù)簽名，因此挑戰(zhàn)者可以利用構(gòu)造一個(gè)算法來(lái)攻擊上述ID-MRS的適應(yīng)性存在不可偽造性。

若企圖攻破秘密握手方案的防偽造性，則可以自適應(yīng)的訪問(wèn)關(guān)于秘密握手方案的預(yù)言機(jī)，這些預(yù)言機(jī)對(duì)應(yīng)模擬方案中的算法CreateGroup，AddMember，Handshake以及所有哈希函數(shù)，參考文獻(xiàn)[1]中指出這些預(yù)言機(jī)的模擬類似ID-MRS方案中的Setup，Extract Queries，Sign Queries以及Verify Queries。因此，攻擊者的成功蘊(yùn)含了挑戰(zhàn)者B可以成功攻破ID-MRS的EU-ACMA，這樣可以將文中提出的秘密握手方案的防偽造性歸約到ID-MRS的安全性，由于本文所采用的ID-MRS方案基于格上SIS困難問(wèn)題證明是EU-ACMA安全的，因此，本文提出的秘密握手方案在隨機(jī)預(yù)言機(jī)模型下滿足防偽造性。

定理4 ?若基礎(chǔ)的ID-MRS方案在隨機(jī)預(yù)言機(jī)模型下是EU-ACMA的，則本文提出的秘密握手方案滿足防偵測(cè)性。

證明：定理證明思路類似定理3。若存在一個(gè)攻擊者可以以不可忽略的概率攻破秘密握手方案的防偵測(cè)性，則敵手可以利用產(chǎn)生一個(gè)算法以一個(gè)不可忽略的概率偽造出可驗(yàn)證成功的消息恢復(fù)簽名，這就攻破了ID-MRS方案的EU-ACMA。秘密握手方案防偵測(cè)性的形式化安全證明通過(guò)和攻擊者完成一個(gè)攻擊游戲?qū)崿F(xiàn)，攻擊游戲的詳細(xì)說(shuō)明可參考文獻(xiàn)[17]。類似于防偽造性證明，攻擊者 以不可忽略的概率優(yōu)勢(shì)成功贏得游戲勝利（也就是秘密握手方案的防偵測(cè)性）可以歸約到ID-MRS的安全性。由于本文采用的ID-MRS方案基于格上SIS困難問(wèn)題證明是EU-ACMA安全的，因此，本文提出的秘密握手方案滿足防偵測(cè)性。

定理5 ?若基礎(chǔ)的ID-MRS方案在隨機(jī)預(yù)言機(jī)模型下是EU-ACMA的，則本文提出的秘密握手方案滿足不可關(guān)聯(lián)性。

證明：一般來(lái)說(shuō)，本文可以通過(guò)使用一次性偽名證書(shū)來(lái)達(dá)到不可關(guān)聯(lián)性，也就是說(shuō)，若一個(gè)攻擊者作為某一個(gè)組織的合法成員執(zhí)行了兩次不同的秘密握手協(xié)議，那么在每次協(xié)議中它所使用的身份信息是不相同的，這就保證了兩次秘密握手協(xié)議的內(nèi)容之間是不可關(guān)聯(lián)的。與防偵測(cè)性和防偽造性的安全證明類似，不可關(guān)聯(lián)性的形式化安全證明通過(guò)一個(gè)攻擊游戲定義，完整的攻擊游戲和預(yù)言機(jī)定義可參考文獻(xiàn)[17]，攻擊者以不可忽略的概率優(yōu)勢(shì)成功區(qū)分兩次握手協(xié)議是否來(lái)自于同一個(gè)用戶也依賴于攻擊者能否成功攻破握手方案中的ID-MRS的安全性。由于本文采用的ID-MRS方案基于格上SIS困難問(wèn)題證明是EU-ACMA安全的，因此，本文提出的秘密握手方案滿足不可關(guān)聯(lián)性。

4.2 效率分析

通信復(fù)雜度：假設(shè)協(xié)議雙方所需的組織證書(shū)，已由GA事先頒發(fā)，則協(xié)議用戶發(fā)送一個(gè)簽名的比特長(zhǎng)度為，產(chǎn)生的消息驗(yàn)證碼的比特長(zhǎng)度為，運(yùn)行一次協(xié)議總的通信復(fù)雜度（比特長(zhǎng)度）為 。對(duì)于一些合理的安全參數(shù)，例如，令，參考[18]中公共參數(shù)取值：，，，，，，可知，這表明方案需要的通信負(fù)載量是具有可實(shí)踐性的。

計(jì)算復(fù)雜度：方案只在CreateGroup和AddMember階段用到了兩種抽樣技術(shù)，在一個(gè)實(shí)時(shí)在線的秘密握手系統(tǒng)中，可以將所有的抽樣操作線下完成，這樣系統(tǒng)在線的計(jì)算操作只包括矩陣/向量之間的乘法和加法，此外，本文使用SHA-512作為方案中的哈希函數(shù)。將與生成簽名相關(guān)的一次矩陣/向量之間的乘法（如或）記為，則，加/減法（如）記為，則將與消息驗(yàn)證相關(guān)的一次矩陣/向量之間的乘法（如）記為，則加/減法（例如）記為，則，其中是中兩個(gè)多項(xiàng)式相乘的計(jì)算開(kāi)銷，而是中兩個(gè)多項(xiàng)式相加的計(jì)算開(kāi)銷。協(xié)議生成一次成功簽名重復(fù)次數(shù)的期望值為M[19]。綜上執(zhí)行一次秘密握手協(xié)議的計(jì)算復(fù)雜度如表所1示。

由上可知，當(dāng)安全參數(shù)為一些合理的數(shù)值（）時(shí)，運(yùn)行一次秘密握手協(xié)議的計(jì)算總開(kāi)銷約為。

與基于傳統(tǒng)困難問(wèn)題的方案[3，6，7，8]相比，本文提出的方案不需要更加耗時(shí)的雙線性對(duì)運(yùn)算（橢圓曲線上）和模指數(shù)運(yùn)算，而只需進(jìn)行向量間的加乘法，實(shí)踐中將更適用于現(xiàn)代并行式操作系統(tǒng)，但對(duì)應(yīng)的是GA對(duì)于用戶群身份的儲(chǔ)存開(kāi)銷變大，約為。

5 結(jié)束語(yǔ)

本文提出了一個(gè)格上后量子的兩方秘密握手方案，在隨機(jī)預(yù)言機(jī)模型下可證明安全，且通信復(fù)雜度和計(jì)算開(kāi)銷具有可實(shí)踐性。為了實(shí)現(xiàn)簡(jiǎn)便的可追蹤和可撤回性，方案在用戶身份信息的管理上使用了一次性偽名證書(shū)。作為格上的方案，研究也為使用其他困難問(wèn)題構(gòu)造秘密握手方案提供了新的思路。未來(lái)的工作包括探尋如何使用可重用證書(shū)來(lái)構(gòu)造后量子的秘密握手方案，以及如何將本文構(gòu)造拓展成多方用戶參與的方案。

基金項(xiàng)目：

1.國(guó)家重點(diǎn)研發(fā)計(jì)劃（項(xiàng)目編號(hào)：2017YFB0802500）;

2.國(guó)家自然科學(xué)基金（項(xiàng)目編號(hào)：61672550，61972429）;

3.廣東省基礎(chǔ)與應(yīng)用基礎(chǔ)研究重大項(xiàng)目（項(xiàng)目編號(hào)：2019B030302008）;

4.廣東省基礎(chǔ)與應(yīng)用基礎(chǔ)研究基金（項(xiàng)目編號(hào)：2019A1515011797）。

參考文獻(xiàn)

[1] Tian Miaomiao， Huang Liusheng. Identity-based signatures from lattices： Simpler， Faster， Shorter [J]. Fundamenta Informaticae， 2016， 145（2）： 171-187.

[2] Balfanz D ， Durfee G ， Shankar N ， et al. Secret handshakes from pairing-based key agreements [C]. Symposium on Security & Privacy. Berkeley， CA： IEEE， 2003. 180-196.

[3] Wen Yamin， Zhang Fangguo， Xu Lingling. Secret handshakes from id-based message recovery signatures： a new generic approach [J]. Computers and Electrical Engineering， 2012， 38（1）： 96-104.

[4] Wen Yamin， Zhang Fangguo， Wang Huaxiong， et al. A new secret handshake scheme with multi-symptom intersection for mobile healthcare social networks [J]. Information Sciences， 2020， 520： 142-154.

[5] Wen Yamin， Zhang Fangguo. A new revocable secret handshake scheme with backward unlinkability [C]. EUROPKI 2010. Berlin， Heidelberg： Springer， 2010. 45-56.

[6] Hou Lin， Lai Junzuo， Liu Lixian. Secret handshakes with dynamic expressive matching policy [C]. Australasian Conference on Information Security and Privacy. Berlin： Springer， 2016. 461–476.

[7] 王聞博，程慶豐，陸思奇，等.一種基于混沌映射的秘密握手協(xié)議 [J].信息網(wǎng)絡(luò)安全，2015， （11）： 40-46.

[8] Tian Yangguang， Li Yingjiu， Deng R H， et al. A new construction for linkable secret handshake [J]. The Computer Journal， 2020， 63（4）： 536-538.

[9] Panja S， Dutta S， Sakurai K. Deniable secret handshake protocol - revisited. [C]. Advanced Information Networking and Applications. Cham： Springer， 2019. 1266-1278.

[10] Jarecki S， Kim J， Tsudik G. Group secret handshakes or affiliation-hiding authenticated group key agreement [C]. Topics in Cryptology – CT-RSA 2007. Berlin， Heidelberg： Springer， 2007. 287-308.

[11] 汪維家，李勇，劉云.一種短密鑰環(huán)境下多方秘密握手方法 [P].中國(guó)：101908961A， 2010-12-08.

[12] Lyubashevsky V. Lattice signatures without trapdoors [C]. Advances in Cryptology-EUROCRYPT 2012. Berlin， Heidelberg： Springer， 2012. 738-755.

[13] Ajtai M. Generating hard instances of lattice problems [C]. Proc. STOC 1996. New York： ACM， 1996. 99-108.

[14] Alwen J，Peikert C. Generating shorter bases for hard random lattices [J]. Theory of Computing Systems， 2011， 48（3）： 535–553.

[15] Zhang Fangguo， Willy Susilo， Mu Yi. Identity-based partial message recovery signatures （or how to shorten id-based signatures） [C]. Financial Cryptography and Data Security. Berlin， Heidelberg： Springer， 2005. 45–56.

[16] Jing Zhengjun，Gu Chunsheng，Yu Zhimin， et al. Cryptanalysis of lattice-based key exchange on small integer solution problem and its improvement [J]. Cluster Computing， 2019， 22（1）： 1717-1727.

[17] Yutaka Kawai， Kazuki Yoneyama， Kazuo Ohta. Secret handshake： strong anonymity definition and construction [C]. Information Security Practice and Experience， 5th International Conference. Berlin， Heidelberg： Springer， 2009. 219–229.

[18] Micciancio D， ?Regev O. Worst-case to average-case reductions based on gaussian measures [J]. SIAM Journal on Computing， 2007， 37（1）： 267– 302.

[19] Von Neumann J. Various techniques used in connection with random digits [J]. Journal of Research of the National Bureau of Standards， 1951， 12（1）： 36-38.