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

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

　　中圖分類號： 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 引言

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

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

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

　　2 預備知識

　　2.1 符號和定義

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

　　4 安全和效率分析

　　4.1 安全分析

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

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

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

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

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

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

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

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

　　4.2 效率分析

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

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

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

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

　　5 結(jié)束語

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

　　基金項目：

　　1.國家重點研發(fā)計劃（項目編號：2017YFB0802500）；

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

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

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

　　安致遠 溫雅敏 張方國

關(guān)注讀覽天下微信， 100萬篇深度好文， 等你來看……