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

安致遠 溫雅敏 張方國

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

關鍵詞：秘密握手;隱私保護;格密碼;消息恢復簽名;可證明安全

中圖分類號： TP309 ? ? ? ? ?文獻標識碼：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 引言

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

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

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

2 預備知識

2.1 符號和定義

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

4 安全和效率分析

4.1 安全分析

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

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

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

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

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

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

定理5 ?若基礎的ID-MRS方案在隨機預言機模型下是EU-ACMA的，則本文提出的秘密握手方案滿足不可關聯性。

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

4.2 效率分析

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

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

由上可知，當安全參數為一些合理的數值（）時，運行一次秘密握手協議的計算總開銷約為。

與基于傳統困難問題的方案[3，6，7，8]相比，本文提出的方案不需要更加耗時的雙線性對運算（橢圓曲線上）和模指數運算，而只需進行向量間的加乘法，實踐中將更適用于現代并行式操作系統，但對應的是GA對于用戶群身份的儲存開銷變大，約為。

5 結束語

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

基金項目：

1.國家重點研發計劃（項目編號：2017YFB0802500）;

2.國家自然科學基金（項目編號：61672550，61972429）;

3.廣東省基礎與應用基礎研究重大項目（項目編號：2019B030302008）;

4.廣東省基礎與應用基礎研究基金（項目編號：2019A1515011797）。

參考文獻

[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] 王聞博，程慶豐，陸思奇，等.一種基于混沌映射的秘密握手協議 [J].信息網絡安全，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] 汪維家，李勇，劉云.一種短密鑰環境下多方秘密握手方法 [P].中國：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.