具有否認(rèn)認(rèn)證的SM9標(biāo)識(shí)加密算法

趙晨陽，柯品惠，林昌露

1.福建師范大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，福州 350117

2.福建師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，福州 350117

標(biāo)識(shí)加密算法（identity-based encryption，IBE）是一種特殊類型的公鑰加密算法，它允許用戶使用任意標(biāo)識(shí)作為公鑰，例如電子郵件地址、電話號(hào)碼和身份證號(hào)碼等。在IBE算法中，數(shù)據(jù)發(fā)送者不必獲得接收者的公鑰證書，即不需要公鑰基礎(chǔ)設(shè)施（public key infrastructure，PKI）。2001年，Boneh和Franklin[1]提出第一個(gè)實(shí)用且可證明安全的基于雙線性對(duì)的標(biāo)識(shí)加密方案。隨后，研究者對(duì)標(biāo)識(shí)加密算法進(jìn)行了深入研究，基于雙線性對(duì)提出了更多實(shí)用的IBE 算法[2-4]。雖然標(biāo)識(shí)加密算法研究取得了積極進(jìn)展，但標(biāo)識(shí)加密算法大多以國外算法為主。為實(shí)現(xiàn)信息自主可控，我國自主設(shè)計(jì)了一系列中國國家標(biāo)識(shí)密碼標(biāo)準(zhǔn)。SM9[5]就是其中一個(gè)有代表性的密碼標(biāo)準(zhǔn)，它包括3 個(gè)組成部分：數(shù)字簽名算法、密鑰協(xié)商算法和標(biāo)識(shí)加密算法。SM9標(biāo)識(shí)加密算法于2016年成為我國商用密碼標(biāo)準(zhǔn)，2020 年成為國家標(biāo)準(zhǔn)。隨著SM9 算法在密碼技術(shù)領(lǐng)域占據(jù)愈來愈重要的國際地位，我國學(xué)者對(duì)SM9算法進(jìn)行了深入研究，如文獻(xiàn)[6-10]。

雖然SM9-IBE 是一個(gè)標(biāo)準(zhǔn)算法，但在一些特殊場景中，比如電子郵件系統(tǒng)、電子投標(biāo)、電子投票和網(wǎng)上選舉等，它不能很好地保護(hù)發(fā)送者的身份隱私。基于此，本文結(jié)合SM9算法添加否認(rèn)認(rèn)證協(xié)議，提出具有否認(rèn)認(rèn)證的SM9 標(biāo)識(shí)加密算法，保護(hù)發(fā)送者的身份隱私，滿足上述應(yīng)用場景的現(xiàn)實(shí)需要。

與傳統(tǒng)的認(rèn)證協(xié)議相比，否認(rèn)認(rèn)證協(xié)議具有以下兩個(gè)特點(diǎn)：（1）協(xié)議主體可以在協(xié)議運(yùn)行后否認(rèn)自己的參與，只有目標(biāo)接收者可以驗(yàn)證給定消息的來源；（2）即使接收者與第三方充分合作，也不能使任何第三方相信消息是由特定的發(fā)送者發(fā)出的。

1998年，Dwork等人[11]首先提出了一個(gè)基于零知識(shí)的否認(rèn)認(rèn)證協(xié)議。之后，Aumann和Rabin[12]提出了另一個(gè)基于因子分解的方案，它需要一個(gè)通信雙方都信任的公共目錄。2001年，Deng等人[13]在Aumann和Rabin定義的模型下，分別提出了兩個(gè)基于因式分解和離散對(duì)數(shù)問題的否認(rèn)認(rèn)證協(xié)議。2005年，Cao等人[14]利用雙線性對(duì)提出了一個(gè)高效的非交互式、基于身份的否認(rèn)認(rèn)證協(xié)議。此外，該方案通過使用對(duì)稱加密算法實(shí)現(xiàn)了保密性。然而，在2006 年，Chou 等人[15]指出Cao 等人的方案易遭受密鑰泄露偽裝（key compromise impersonation，KCI）攻擊。隨后Chou 等人提出了一種新的基于身份的否認(rèn)認(rèn)證協(xié)議，并聲稱該協(xié)議是安全的。然而，2007 年，Lim 等人[16]證明Chou等人的方案仍易受KCI攻擊，其也是不安全的；此外，他們提出了一個(gè)增強(qiáng)的方案。然而在2009年，Tian等人[17]指出，Lim等人修復(fù)的協(xié)議在特殊的攻擊下仍然不安全。2014年，Li等人[18]提出了一種高效的基于身份的否認(rèn)認(rèn)證協(xié)議。更重要的是，他們給出了其協(xié)議的安全模型和形式化證明，并聲稱他們的協(xié)議滿足批量驗(yàn)證的要求，而且比所有已知的基于身份的否認(rèn)認(rèn)證協(xié)議更快。2015年，Wu等人[19]提出了一種高效的基于身份的否認(rèn)認(rèn)證加密方案，該方案在不可否認(rèn)性、保密性和否認(rèn)認(rèn)證性均得以保證。2019年，Huang等人[20]提出了一種有效的保護(hù)隱私的否認(rèn)認(rèn)證加密方案，該方案在不可否認(rèn)性、機(jī)密性和否認(rèn)認(rèn)證性的基礎(chǔ)上對(duì)數(shù)據(jù)的完整性也提供了保證。2020 年，Kar[21]提出了一個(gè)無證書環(huán)境下的否認(rèn)認(rèn)證加密方案，該方案既沒有密鑰托管問題，也不需要公鑰證書。

為了達(dá)到一定的安全性，上述方案大多基于安全參數(shù)較大的對(duì)稱雙線性對(duì)，并且在方案中多次使用雙線性對(duì)，導(dǎo)致方案的計(jì)算效率下降。而SM9-IBE算法采用安全參數(shù)小的非對(duì)稱雙線性對(duì)，用戶的公鑰和私鑰分別由兩個(gè)不同的循環(huán)群生成，因此安全強(qiáng)度更高。

本文工作：首先定義SM9-DAIBE（SM9 identitybased encryption of deniable authentication）算法的安全模型，然后利用雙線性對(duì)提出具體的SM9-DAIBE算法。接下來，在DBDH（decisional bilinear Diffie-Hellman）困難問題假設(shè)下，在隨機(jī)預(yù)言模型中給出了算法的安全性證明。相對(duì)SM9-IBE 算法，本文提出的SM9-DAIBE算法可同時(shí)具有以下特性：

（1）保密性：該屬性確保只有目標(biāo)接收者可以與發(fā)送者共享所傳輸?shù)南?，任何第三方都不能獲得所傳輸?shù)拿芪摹?/p>

（2）否認(rèn)性：消息的發(fā)送者可以在之后否認(rèn)其曾傳輸過該消息，甚至否認(rèn)參與了通信。同時(shí)，目標(biāo)接收者可以識(shí)別給定消息的真實(shí)來源，但是接收者不能向任何其他第三方證明這一事實(shí)。

（3）否認(rèn)認(rèn)證性：該屬性確保發(fā)送消息主體實(shí)際上是真正的發(fā)送者，而不是另一個(gè)第三方或?qū)κ帧?/p>

1 基礎(chǔ)知識(shí)

1.1 符號(hào)說明

設(shè)A和B為比特串，A⊕B表示A和B的按位異或運(yùn)算，A||B表示A和B的級(jí)聯(lián)。zP表示加法群中元素P的z倍，gr表示乘法群中元素g的r次冪。如果A是一個(gè)概率算法，那么y←A(x)表示輸入x，將算法A的輸出賦值給y。

表1 給出了SM9 算法中用到的密碼函數(shù)的符號(hào)表示。

表1 SM9算法的函數(shù)使用說明Table 1 Description of use of functions for SM9 algorithm

1.2 雙線性群

設(shè)N為素?cái)?shù)，令G1和G2為兩個(gè)N階加法循環(huán)群，GT為N階乘法循環(huán)群，P1和P2分別是群G1和G2的生成元。定義為雙線性對(duì)映射，則應(yīng)滿足以下三條性質(zhì)：

（1）雙線性性。對(duì)于?a,b∈[1,N-1]，都有

（2）非退化性。若P1和P2不是單位元，則也不是單位元。

（3）可計(jì)算性。對(duì)于?P1,P2，存在一個(gè)高效的多項(xiàng)式時(shí)間算法計(jì)算

特別地，若G1=G2，稱為對(duì)稱雙線性群；否則稱為非對(duì)稱雙線性群。SM9標(biāo)識(shí)密碼算法以非對(duì)稱雙線性群為構(gòu)造基礎(chǔ)。令G(1λ)表示一個(gè)雙線性配對(duì)群生成算法。該算法以安全參數(shù)1λ作為輸入，以元組作為輸出。

1.3 基于雙線性對(duì)的困難問題及假設(shè)

DBDH假設(shè)：對(duì)于任意一個(gè)概率多項(xiàng)式時(shí)間攻擊者A，計(jì)算DBDH問題的概率都是可以忽略不計(jì)的，即Pr[0 ←A(Y)|γ=0]-Pr[0 ←A(Y)|γ=1]是可以忽略不計(jì)的。

1.4 SM9-IBE算法

本節(jié)回顧SM9-IBE 算法，該算法由以下幾個(gè)步驟構(gòu)成：

（2）密鑰提取。給定用戶的身份標(biāo)識(shí)ID，密鑰中心計(jì)算用戶密鑰deID=

（3）消息加密。對(duì)于消息M和身份標(biāo)識(shí)ID，選擇一個(gè)隨機(jī)元素r∈，首先計(jì)算QB=Ppub-e+[H(ID)]P1，再計(jì)算密文C1=[r]QB，C2=K1⊕M，C3=Hv(C2||K2)，其中K1||K2=KDF(Hv,C1||t||ID,|M|+v)，t=ur。

（4）密文解密。對(duì)于密文(C1,C2,C3)，首先根據(jù)私鑰deID計(jì)算，再根據(jù)KDF 計(jì)算K1||K2=KDF(Hv,C1||t′||ID,|M|+v)。

若Hv(C2||K2)=C3，則返回消息M=K1⊕C2；否則，返回錯(cuò)誤符號(hào)▲。

2 具有否認(rèn)認(rèn)證的SM9標(biāo)識(shí)加密算法

2.1 SM9-DAIBE算法的系統(tǒng)模型

SM9-DAIBE算法的系統(tǒng)模型包含以下三個(gè)實(shí)體（見圖1）：

圖1 SM9-DAIBE系統(tǒng)模型Fig.1 System model for SM9-DAIBE

（1）密鑰生成中心（key generation center，KGC）：負(fù)責(zé)生成系統(tǒng)參數(shù)和主私鑰，同時(shí)為用戶（包括數(shù)據(jù)發(fā)送者和數(shù)據(jù)接收者）提供私鑰。

（2）數(shù)據(jù)發(fā)送者（data sender，DS）：對(duì)消息進(jìn)行否認(rèn)認(rèn)證加密，形成認(rèn)證器密文發(fā)送給數(shù)據(jù)接收者。

（3）數(shù)據(jù)接收者（data receiver，DR）：從收到的認(rèn)證器密文中計(jì)算出原始消息，并能確認(rèn)消息的來源。

2.2 SM9-DAIBE算法的形式化定義

本節(jié)給出新的SM9-DAIBE 算法，該算法由以下四個(gè)算法組成：

（1）系統(tǒng)參數(shù)生成算法Setup（1λ）。該算法由密鑰生成中心負(fù)責(zé)執(zhí)行。輸入一個(gè)安全參數(shù)λ，通過運(yùn)行算法返回系統(tǒng)參數(shù)param和系統(tǒng)主私鑰ke。密鑰生成中心秘密保存系統(tǒng)主私鑰ke，公開系統(tǒng)參數(shù)param。

（2）用戶密鑰提取算法Extract（ID）。該算法由用戶和密鑰生成中心交互執(zhí)行。用戶將自己的身份標(biāo)識(shí)ID發(fā)送給密鑰生成中心，密鑰生成中心對(duì)收到的身份標(biāo)識(shí)ID進(jìn)行合法性驗(yàn)證，驗(yàn)證通過后用系統(tǒng)主私鑰計(jì)算身份標(biāo)識(shí)ID對(duì)應(yīng)的私鑰deID并通過安全信道發(fā)送給用戶。同時(shí)，用戶根據(jù)系統(tǒng)公開參數(shù)計(jì)算自己的公鑰并公開。

（3）否認(rèn)認(rèn)證加密算法DAEnc(M,deS,IDS,IDR)。該算法由數(shù)據(jù)發(fā)送者負(fù)責(zé)執(zhí)行。根據(jù)消息M、發(fā)送者私鑰deS、發(fā)送者和接收者的身份標(biāo)識(shí)IDS和IDR，數(shù)據(jù)發(fā)送者計(jì)算消息M的認(rèn)證器密文δ后將其發(fā)送給數(shù)據(jù)接收者。

（4）否認(rèn)認(rèn)證解密算法DADec(δ,deR,IDR)。該算法由數(shù)據(jù)接收者負(fù)責(zé)執(zhí)行。收到數(shù)據(jù)發(fā)送者發(fā)送的認(rèn)證器密文δ后，數(shù)據(jù)接收者根據(jù)自己的私鑰deR和身份IDR，恢復(fù)出消息M，同時(shí)確認(rèn)消息是否為數(shù)據(jù)發(fā)送者發(fā)送。若是，接收消息M；否則，輸出錯(cuò)誤符號(hào)▲。

2.3 SM9-DAIBE算法的安全模型

（1）SM9-DAIBE算法的保密性

SM9-DAIBE算法的保密性的安全性概念稱為抗適應(yīng)性選擇密文攻擊的密文不可區(qū)分性（ciphertext indistinguishability against adaptive chosen ciphertext attacks，IND-DAIBE-CCA）。下面給出IND-DAIBECCA的游戲定義。

初始化階段算法B 輸入一個(gè)安全參數(shù)λ，運(yùn)行系統(tǒng)參數(shù)生成算法Setup（1λ），返回系統(tǒng)參數(shù)param和系統(tǒng)主私鑰ke，其中系統(tǒng)參數(shù)param發(fā)送給攻擊者A，系統(tǒng)主私鑰ke秘密保存。

詢問階段1A以如下自適應(yīng)方式執(zhí)行多項(xiàng)式有界數(shù)量的用戶密鑰提取查詢、否認(rèn)認(rèn)證加密查詢和否認(rèn)認(rèn)證解密查詢。

①用戶密鑰提取查詢。當(dāng)攻擊者A要查詢標(biāo)識(shí)ID的私鑰時(shí)，挑戰(zhàn)者B 運(yùn)行用戶密鑰提取算法Extract（ID）獲取對(duì)應(yīng)用戶的私鑰deID，并將其發(fā)送給攻擊者A。

②否認(rèn)認(rèn)證加密查詢。攻擊者A選擇一個(gè)發(fā)送者的身份標(biāo)識(shí)IDi、一個(gè)接收者的身份標(biāo)識(shí)IDj、一個(gè)明文M，并將它們發(fā)送給挑戰(zhàn)者B。挑戰(zhàn)者B 首先運(yùn)行用戶密鑰提取算法Extract（ID）獲得發(fā)送者IDi的私鑰，然后運(yùn)行否認(rèn)認(rèn)證加密算法DAEnc(M,deS,IDS,IDR)，將計(jì)算結(jié)果發(fā)送給攻擊者A。

③否認(rèn)認(rèn)證解密查詢。攻擊者A 提交一個(gè)DAEnc 認(rèn)證器密文δ和一個(gè)接收者的身份標(biāo)識(shí)IDj給挑戰(zhàn)者B。挑戰(zhàn)者B 首先運(yùn)行用戶密鑰提取算法Extract（ID）獲得接收者IDj的私鑰，然后運(yùn)行否認(rèn)認(rèn)證解密算法DADec(δ,deR,IDR)，將計(jì)算結(jié)果發(fā)送給攻擊者A。

挑戰(zhàn)在攻擊者A決定詢問階段1 結(jié)束時(shí)，攻擊者A輸出兩個(gè)等長的明文M0、M1，以及之前沒有做過用戶密鑰提取查詢的兩個(gè)標(biāo)識(shí)IDS、IDR一并發(fā)送給挑戰(zhàn)者B。挑戰(zhàn)者B 從0 和1 中隨機(jī)選擇一位記為γ，將δ=DAEnc(Mγ,deS,IDS,IDR)的計(jì)算結(jié)果發(fā)送給攻擊者A作為挑戰(zhàn)。

詢問階段2攻擊者A可以像詢問階段1一樣發(fā)出更多的多項(xiàng)式有界查詢，但是在這個(gè)階段，攻擊者A不能對(duì)身份標(biāo)識(shí)IDS和IDR進(jìn)行用戶密鑰提取查詢。同時(shí)，攻擊者A也不能對(duì)挑戰(zhàn)δ進(jìn)行否認(rèn)認(rèn)證解密查詢。

猜測最終，攻擊者A輸出一比特γ′作為對(duì)γ的猜測。如果γ′=γ，表明游戲獲勝。

如果對(duì)于任意多項(xiàng)式時(shí)間攻擊者A，其游戲獲勝的優(yōu)勢是可忽略的，即，其中negl(λ)為可忽略函數(shù)，則SM9-DAIBE算法滿足保密性。

（2）SM9-DAIBE算法的否認(rèn)認(rèn)證性

此處借用數(shù)字簽名中抵抗適應(yīng)性選擇消息攻擊的不可偽造性的概念來定義SM9-DAIBE 算法的否認(rèn)認(rèn)證性的安全概念。然而，SM9-DAIBE 算法中的安全概念與數(shù)字簽名算法的安全概念有本質(zhì)的不同。這是因?yàn)樵跀?shù)字簽名中，只有具有正確私鑰的發(fā)送方才有能力生成有效的簽名，而在SM9-DAIBE算法中，發(fā)送方和接收方都有能力生成有效的SM9-DAIBE 認(rèn)證器密文。SM9-DAIBE 算法的不可偽造性的安全性概念稱為抗適應(yīng)性選擇消息攻擊的否認(rèn)認(rèn)證性（deniable authentication against adaptive chosen messages attacks，DA-DAIBE-CMA）。下面給出DADAIBE-CMA的游戲定義。

初始化階段算法B 輸入一個(gè)安全參數(shù)λ，運(yùn)行系統(tǒng)參數(shù)生成算法Setup(1λ)，返回系統(tǒng)參數(shù)param和系統(tǒng)主私鑰ke，其中系統(tǒng)參數(shù)param發(fā)送給攻擊者X，系統(tǒng)主私鑰ke秘密保存。

攻擊階段和前面的IND-DAIBE-CCA的游戲定義一致，攻擊者X 以自適應(yīng)方式執(zhí)行多項(xiàng)式有界數(shù)量的用戶密鑰提取查詢、否認(rèn)認(rèn)證加密查詢和否認(rèn)認(rèn)證解密查詢。

偽造階段攻擊者X 輸出一個(gè)DAEnc 認(rèn)證器δ?和兩個(gè)身份標(biāo)識(shí)IDS和IDR。如果同時(shí)滿足以下三個(gè)條件，視為攻擊者X 游戲獲勝。

①δ?是一個(gè)對(duì)于發(fā)送方IDS和接收方IDR有效的認(rèn)證器，也就是說，DADec(δ?,deR,IDR)的結(jié)果不是一個(gè)錯(cuò)誤符號(hào)▲。

②攻擊者X 沒有對(duì)IDS和IDR做過用戶密鑰提取查詢。

③攻擊者X 沒有對(duì)消息M?和身份標(biāo)識(shí)IDS和IDR做過否認(rèn)認(rèn)證加密查詢。

這里把攻擊者X 的優(yōu)勢定義為它在游戲中獲勝的概率。為了實(shí)現(xiàn)SM9-DAIBE算法的否認(rèn)性，在以上條件的第二步需要攻擊者X 對(duì)IDS和IDR均沒有做過用戶密鑰提取查詢，原因是接收者也可以生成一個(gè)有效的DAEnc認(rèn)證器密文。

2.4 SM9-DAIBE算法的構(gòu)造

SM9-DAIBE算法的具體構(gòu)造如下：

（1）系統(tǒng)參數(shù)生成算法Setup（1λ）。在輸入安全參數(shù)λ后，該算法執(zhí)行以下操作：

③密鑰生成中心生成系統(tǒng)參數(shù)param=(G,Ppub-e,H,hid)并公開，同時(shí)秘密保存系統(tǒng)主私鑰ke。

（2）用戶密鑰提取算法Extract(ID)。在輸入用戶標(biāo)識(shí)ID后，該算法執(zhí)行以下操作：

①給定用戶標(biāo)識(shí)ID，密鑰生成中心計(jì)算用戶的私鑰deID=[ke+H(ID)]P2。

②密鑰生成中心通過安全信道將用戶私鑰deID發(fā)送給用戶。

③用戶ID根據(jù)系統(tǒng)公開參數(shù)計(jì)算自己公鑰QID=Ppub-e+[H(ID)]P1。

注：本文假定發(fā)送者和接收者的公私鑰對(duì)分別是(QS,deS)和(QR,deR)。

（3）否認(rèn)認(rèn)證加密算法DAEnc(M,deS,IDS,IDR)。在輸入消息M、發(fā)送者私鑰deS、發(fā)送者和接收者的身份標(biāo)識(shí)IDS和IDR后，該算法執(zhí)行以下操作：

②利用密鑰派生函數(shù)KDF，計(jì)算K1||K2=KDF(Hv,C1||t||IDR,|M||IDS|+v)，其中K1和K2的長度分別為|M||IDS|比特和v比特。

③數(shù)據(jù)發(fā)送者計(jì)算C2=K1⊕(M||IDS)，C3=Hv(C2||K2)。

④數(shù)據(jù)發(fā)送者將DAEnc認(rèn)證器密文δ=(C1,C2,C3)發(fā)送給數(shù)據(jù)接收者。

（4）否認(rèn)認(rèn)證解密算法DADec(δ,deR,IDR)：在輸入認(rèn)證器密文δ、接收者私鑰deR、接收者的身份IDR后，該算法執(zhí)行以下操作：

①數(shù)據(jù)接收者根據(jù)自己的私鑰deR計(jì)算t′=

②數(shù)據(jù)接收者利用KDF 計(jì)算出K1||K2=KDF(Hv,C1||t′||IDR,|M||IDS|+v)。

③若Hv(C2||K2)=C3，返回M||IDS=K1⊕C2，從而恢復(fù)出消息M；否則，返回錯(cuò)誤符號(hào)▲。

正確性分析：由于C1=[r]QS，QID=Ppub-e+[H(ID)]P1，deID=[ke+H(ID)]P2，有

因此，數(shù)據(jù)接收者可以計(jì)算出正確的中間密鑰K1和K2，進(jìn)而恢復(fù)出原始消息M。

3 SM9-DAIBE算法的安全性分析

3.1 否認(rèn)性

本算法實(shí)現(xiàn)了否認(rèn)性，由于接收者也可以生成有效的DAEnc 認(rèn)證器密文，而該認(rèn)證器密文無法與發(fā)送者的認(rèn)證器密文進(jìn)行區(qū)分，原因如下：

（1）在收到發(fā)送者發(fā)來的DAEnc 認(rèn)證器密文δ=(C1,C2,C3)后，接收者通過運(yùn)行否認(rèn)認(rèn)證解密算法，獲得恢復(fù)后的消息M。之后接收者可以執(zhí)行以下操作：

3.2 保密性

本文所提SM9-DAIBE 算法在隨機(jī)預(yù)言模型下滿足抗適應(yīng)性選擇密文攻擊的密文不可區(qū)分性。

定理1在隨機(jī)預(yù)言模型下，若攻擊者A能以優(yōu)勢贏得密文不可區(qū)分性游戲（至多進(jìn)行qH次哈希詢問），則存在一個(gè)算法B 能利用A 以的優(yōu)勢解決DBDH問題。

證明可以通過2.3 節(jié)中定義的密文不可區(qū)分性IND-DAIBE-CCA 游戲來證明本文算法的保密性。若存在一個(gè)攻擊者A可以破解這個(gè)算法，則可構(gòu)造一個(gè)算法B 來解決DBDH問題。不妨設(shè)算法B 要解決的一個(gè)DBDH 實(shí)例元組為：Y=(P1,[x]P1,[y]P1,P2,[y]P2,[z]P2,Z)。在下面的游戲中，B 扮演攻擊者A的挑戰(zhàn)者。

初始化階段算法B 輸入一個(gè)安全參數(shù)λ，運(yùn)行系統(tǒng)參數(shù)生成算法Setup（1λ），生成系統(tǒng)參數(shù)param=(G,Ppub-e,H,hid)，其中為雙線性配對(duì)群，Ppub-e=[ke]P1且ke未知。挑戰(zhàn)者將系統(tǒng)參數(shù)param發(fā)送給A。

詢問階段1A執(zhí)行多項(xiàng)式有界次數(shù)的以下查詢，B 對(duì)A的查詢做如下回答：

（1）哈希查詢OH(IDi)。首先，B 維持一個(gè)形如(IDi,ni)、初始為空集的二元列表LH。其次，B 選擇兩個(gè)不同的數(shù)N1,N2∈{1,2,…,qH}。如果IDi是A的第N1(i=N1)次詢問，則B 回答QN1=Ppub-e+[x]P1。如果IDi是A 的第N2(i=N2) 次詢問，則B 回答對(duì)于一個(gè)由A給定的標(biāo)識(shí)IDi(i∈{1,2,…,qH}且i?{N1,N2})，B 首先檢查列表LH是否存在元素(IDi,ni)。

（2）KDF 查詢OK(IDi,ti,li)。首先B 建立一個(gè)形如(IDi,ti,Ki)、初始為空集的列表LK。當(dāng)A 詢問(IDi,ti,li)的輸出結(jié)果時(shí)，B 首先檢查LK中是否存在形如(IDi,ti,Ki)的三元組。

①若存在，當(dāng)|Ki|≥li時(shí)，返回Ki的前l(fā)i比特。否則，隨機(jī)選取li-|Ki|長度的比特串K，返回Ki||K給A，同時(shí)替換(IDi,ti,Ki)為(IDi,ti,Ki||K)。

②若不存在，則B 詢問列表L1（見用戶密鑰提取查詢）中的每個(gè)元素對(duì)應(yīng)的哈希列表元素(IDi,dei)。根據(jù)dei的取值，B 隨機(jī)選取長度為li的比特串Ki，返回給A，并將(IDi,ti,Ki)添加至列表LK中。

（3）用戶密鑰提取查詢。首先，B 建立一個(gè)形如(IDi,dei)、初始為空集的二元哈希列表L1。其次，B選擇一個(gè)隨機(jī)元素r∈。當(dāng)A詢問身份標(biāo)識(shí)IDi的私鑰時(shí)，B 首先查詢列表L1中是否存在元素(IDi,dei)，并以如下形式返回對(duì)應(yīng)的dei給A。

①若存在，則B 將dei返回給A。

②若不存在：

如果IDi是第N1或N2(i∈{N1,N2})次詢問，則游戲失敗終止。

否則，B 首先詢問OH(IDi)對(duì)應(yīng)的哈希列表是否包含元素(IDi,ni)。若包含，則B 計(jì)算dei=[r+ni]P2，將結(jié)果返回給A，并將(IDi,dei)更新至列表L1中。

若不包含，則B 執(zhí)行哈希查詢OH(IDi)，選擇一個(gè)隨機(jī)數(shù)ni∈，將dei=[r+ni]P2的計(jì)算結(jié)果返回給A，同時(shí)更新LH、L1兩個(gè)列表。

（4）否認(rèn)認(rèn)證加密查詢。A向B 提交發(fā)送者的身份標(biāo)識(shí)IDj、接收者的身份標(biāo)識(shí)IDk和明文M。如果j?{N1,N2}，B 通過查詢列表L1獲得身份標(biāo)識(shí)IDj對(duì)應(yīng)的私鑰，若不存在，則通過用戶密鑰提取查詢和哈希查詢OH(IDi)生成用戶IDj的公私鑰對(duì)，接著運(yùn)行否認(rèn)認(rèn)證加密算法，計(jì)算δ=DAEnc(M,dej,IDj,IDk)的結(jié)果發(fā)送給A。如果j∈{N1,N2}，游戲失敗終止。

（5）否認(rèn)認(rèn)證解密查詢。A 向B 提交一個(gè)DAEnc 認(rèn)證器δ=(C1,C2,C3) 和接收者的身份標(biāo)識(shí)IDk。如果k?{N1,N2}，B 查詢列表L1是否存在標(biāo)識(shí)IDk的私鑰dek。若不存在，則通過用戶密鑰提取查詢和哈希查詢OH(IDi)生成用戶IDk的私鑰，運(yùn)行否認(rèn)認(rèn)證解密算法，將恢復(fù)出的消息M發(fā)送給A。如果k∈{N1,N2}，游戲失敗終止。

挑戰(zhàn)在A決定詢問階段1結(jié)束時(shí)，A輸出兩個(gè)等長的明文M0、M1以及之前沒有做過密鑰提取查詢的兩個(gè)身份標(biāo)識(shí)IDS、IDR一并發(fā)送給B。如果A在游戲中向B 詢問過IDS和IDR的私鑰，則B 失敗，游戲終止。同時(shí)，若IDS和IDR均不是(S,R?{N1,N2})，則B 仍失敗，游戲終止。為了計(jì)算DAEnc認(rèn)證器密文，B 執(zhí)行以下操作：

（1）B 通過用戶密鑰提取查詢和哈希查詢OH(IDi)生成身份標(biāo)識(shí)IDS的私鑰。

詢問階段2類似于詢問階段1，A允許繼續(xù)詢問私鑰和密文解密等，但A不能對(duì)身份標(biāo)識(shí)IDS和IDR做用戶密鑰提取查詢。與此同時(shí)，A也不能對(duì)挑戰(zhàn)δ做否認(rèn)認(rèn)證解密查詢。

猜測最終A輸出一位。如果B 輸出0，否則輸出1。

用F表示A對(duì)挑戰(zhàn)身份的猜測不正確，此時(shí)模擬會(huì)終止。

3.3 否認(rèn)認(rèn)證性

本文所提SM9-DAIBE 算法在隨機(jī)預(yù)言模型下滿足抗適應(yīng)性選擇消息攻擊的否認(rèn)認(rèn)證性。

定理2在隨機(jī)預(yù)言模型下，若攻擊者X 在一定時(shí)間內(nèi)贏得DA-DAIBE-CMA游戲，則存在一個(gè)高效的多項(xiàng)式時(shí)間算法解決DBDH問題。

證明此處通過2.3節(jié)定義的挑戰(zhàn)者B 和攻擊者X 之間的DA-DAIBE-CMA 游戲證明本文算法的否認(rèn)認(rèn)證性。如果存在一個(gè)攻擊者X 可以打破這個(gè)算法，那么可以使用攻擊者X 來構(gòu)造一個(gè)算法B，進(jìn)而解決DBDH問題。類似定理1中保密性的證明，游戲的過程描述如下：

初始化階段算法B 輸入一個(gè)安全參數(shù)λ，運(yùn)行系統(tǒng)參數(shù)生成算法Setup（1λ），返回系統(tǒng)參數(shù)param=(G,Ppub-e,H,hid)，其中為雙線性配對(duì)群，Ppub-e=[ke]P1且ke未知。X 將系統(tǒng)參數(shù)param發(fā)送給攻擊者X 。

攻擊階段與定理1 證明中詢問階段1 的查詢一致，X 執(zhí)行多項(xiàng)式有界數(shù)量的哈希查詢、KDF 查詢、用戶密鑰提取查詢、否認(rèn)認(rèn)證加密查詢和否認(rèn)認(rèn)證解密查詢等。

目前沒有公認(rèn)的解決DBDH困難問題的有效算法，因此實(shí)際上不存在這樣的攻擊者X，證明該算法具有否認(rèn)認(rèn)證性。證畢。

4 性能分析

本章從理論分析和實(shí)驗(yàn)分析兩方面出發(fā)，將本文所設(shè)計(jì)的SM9-DAIBE 算法與文獻(xiàn)[5，19，21]中算法進(jìn)行比較。

4.1 理論分析

表2 比較了4 個(gè)算法的參數(shù)大小和主要運(yùn)算時(shí)間。符號(hào)說明：N表示用戶的密文數(shù)量，“Exp”表示指數(shù)運(yùn)算，“Pairing”表示雙線性對(duì)運(yùn)算。在比較各算法所需的運(yùn)算操作次數(shù)時(shí)，忽略了除指數(shù)運(yùn)算和配對(duì)運(yùn)算之外的操作。SM9-DAIBE 與文獻(xiàn)[5，19，21]中的算法運(yùn)算均需基于雙線性對(duì)運(yùn)算。不妨假定|G1|=|G2|=|GT|=1 024 bit，|ID|=160 bit，|M|=160 bit以及哈希值|H|=160 bit，因此可計(jì)算出文獻(xiàn)[19]的通信規(guī)模為|ID|+|G1|+|M|+|G2|=2 368 bit，文獻(xiàn)[21]的通信規(guī)模為|ID|+|G1|+|M|+|G2|+|H|=2 528 bit，文獻(xiàn)[5]和本文算法的通信規(guī)模為|ID|+|G1|+|M|+|G2|+|GT|=3 392 bit。圖2給出了這4個(gè)算法通信規(guī)模的具體條形圖。

圖2 通信規(guī)模比較Fig.2 Comparison of communication scale

表2 性能比較Table 2 Performance comparison

通過表2 和圖2 的比較可以看到，本文SM9-DAIBE 算法保持了原始SM9-IBE 算法[5]的系統(tǒng)公鑰和私鑰的選取方式。與文獻(xiàn)[19,21]相比，對(duì)于用戶加密和解密算法，文獻(xiàn)[19]共需要4次雙線性配對(duì)運(yùn)算，文獻(xiàn)[21]共需要3 次雙線性配對(duì)運(yùn)算，而本文僅需要2次雙線性配對(duì)運(yùn)算。一般來講，雙線性配對(duì)運(yùn)算較其他運(yùn)算耗時(shí)較多。因此，本文算法相比文獻(xiàn)[19,21]的算法在用戶加密和解密等方面具有一定的優(yōu)勢。并且本文算法采用安全參數(shù)小的非對(duì)稱雙線性對(duì)，用戶的公私鑰分別由兩個(gè)不同的循環(huán)群生成，安全強(qiáng)度更高。正因此，本文算法中增加了乘法循環(huán)群GT，這使得該算法在通信開銷上相較于文獻(xiàn)[19,21]中的算法會(huì)有所增加。

4.2 實(shí)驗(yàn)分析

本節(jié)通過仿真實(shí)驗(yàn)將本文算法與文獻(xiàn)[5,19,21]在發(fā)送方計(jì)算成本（CS）和接收方計(jì)算成本（CR）兩方面進(jìn)行對(duì)比。實(shí)驗(yàn)環(huán)境為榮耀筆記本（3.20 GHz的64 位AMD Ryzen 7 5800H with Radeon Graphics處理器、16 GB內(nèi)存（RAM）、Windows 10操作系統(tǒng)），使用PBC庫[23]中的A型配對(duì)實(shí)現(xiàn)了4個(gè)算法，并獲得圖3所示的實(shí)驗(yàn)結(jié)果。A型配對(duì)構(gòu)造在嵌入度為2的曲線y2≡x3+x(modp)上（其中p≡3 mod 4 且為素?cái)?shù)）。

圖3 主要計(jì)算成本對(duì)比Fig.3 Comparison of main calculation cost

從圖3 可以看到：對(duì)于文獻(xiàn)[5]，CS 是45.809 ms，CR 是41.953 ms；對(duì)于文獻(xiàn)[19]，CS 是67.953 ms，CR是54.074 ms；對(duì)于文獻(xiàn)[21]，CS 是78.613 ms，CR 是30.024 ms；對(duì)于本文算法，CS 是45.681 ms，CR 是42.706 ms。本文算法與原始SM9-IBE算法的發(fā)送方和接收方的計(jì)算成本相當(dāng)；相對(duì)于文獻(xiàn)[19]的算法，發(fā)送方和接收方的總計(jì)算成本減少了28%；相對(duì)于文獻(xiàn)[21]的算法，發(fā)送方和接收方的總計(jì)算成本減少了18%，計(jì)算性能更優(yōu)。

5 結(jié)束語

本文將國密SM9 算法和否認(rèn)認(rèn)證協(xié)議相結(jié)合，提出SM9-DAIBE 算法，證明算法同時(shí)滿足否認(rèn)性、保密性和否認(rèn)認(rèn)證性。結(jié)果表明，該算法所具有的否認(rèn)認(rèn)證屬性，對(duì)發(fā)送者的身份隱私保護(hù)具有很高的實(shí)用性。但由于提出的解決方案是基于非對(duì)稱雙線性對(duì)，雖然基于非對(duì)稱雙線性對(duì)安全強(qiáng)度更高，但是相應(yīng)也增加了通信開銷。在后續(xù)工作中，可以考慮進(jìn)一步減小通信開銷。