基于多接收者加密算法的可否認環(huán)認證協(xié)議

(西華大學數(shù)學與計算機學院，四川 成都 610039)

·計算機軟件理論、技術與應用·

基于多接收者加密算法的可否認環(huán)認證協(xié)議

曾晟珂，何明星，唐明偉

(西華大學數(shù)學與計算機學院，四川 成都 610039)

可否認的環(huán)認證協(xié)議允許消息的發(fā)送者匿名地認證某消息，而在認證的同時，消息接收方卻不能夠向第三方揭示此次認證的發(fā)生，即消息發(fā)送方可以否認該認證。針對這一問題，提出一種新的基于多接收者加密算法的可否認環(huán)認證協(xié)議。消息接收者運行基于多接收者的加密算法對認證碼進行加密，并將結果發(fā)送給消息發(fā)送方。發(fā)送方解密后得到認證碼，并利用該認證碼對消息進行認證。該協(xié)議構造簡單，僅需要2輪通信。多接收者加密算法保護了發(fā)送者的隱私，且其可否認性在并發(fā)環(huán)境中成立。

并發(fā)可否認性；可否認的環(huán)認證；多接收者加密

認證協(xié)議是網(wǎng)絡通信中的重要協(xié)議。通過認證協(xié)議，消息接收方能夠確信消息得到了指定發(fā)送方的認證。數(shù)字簽名算法是實現(xiàn)消息認證的最直接的方法。給定簽名，消息接收者可以通過簽名者的公鑰驗證該消息是否為發(fā)送方發(fā)出；然而，數(shù)字簽名算法具有公開可驗證性。任何驗證者都能夠通過數(shù)字簽名算法中輸入的公鑰得到消息發(fā)送方的身份且發(fā)送方無法否認。在一些場景中，發(fā)送方希望在認證某消息的同時保護自己的隱私，或者不希望自己因為對某消息的認證而陷入某種困境中；因此，數(shù)字簽名算法的公開可驗證性不適合提供可否認的認證。在可否認的認證協(xié)議里，消息接收方在接受發(fā)送方對某消息認證的同時，卻不能夠向第三方展示該消息被發(fā)送方認證過的證據(jù)；因此，認證協(xié)議的可否認性保護了消息發(fā)送方的隱私，即發(fā)送方在第三方面前可以否認對某消息的認證。然而，發(fā)送方在做認證時，其身份對于接收方來說是公開的。可否認的環(huán)認證協(xié)議實現(xiàn)了對接收方的匿名認證，即將發(fā)送方的身份隱藏于一組成員當中，使得接收方無法判斷這組成員中誰是真正的認證者。此外，發(fā)送方可以在第三方面前否認此次認證。

可否認的認證協(xié)議最早是由Dolev等[1]提出的，此后Dwork等[2]對可否認的認證進行形式化的研究，模型化認證協(xié)議的“可否認性”，即存在對誠實雙方真實認證副本的仿真副本，且2種副本不可區(qū)分。對于可否認的認證協(xié)議，學者陸續(xù)提出了相關方案[3-6]。Jiang[7]利用時限加密提出一種可否認認證的密鑰交換協(xié)議。Li等[8]提出一種非交互式的基于身份的可否認的認證協(xié)議。該協(xié)議雖然實現(xiàn)了非交互式，但僅達到了半可否認性，即發(fā)送方可以否認參與了認證，這是因為接收方能夠仿真發(fā)送方的認證副本。也就是說，該認證過程留下了證據(jù)使得至少有參與者不能夠否認參與了認證。Naor[9]將可否認的認證與環(huán)簽名進行結合，提出了可否認的環(huán)認證協(xié)議，即消息發(fā)送方隱藏在一組成員中，接收方無法判斷發(fā)送方的真實身份；然而，該協(xié)議需要在“時間假設”下滿足并發(fā)環(huán)境中的可否認性，且通信輪數(shù)為6輪。Dowsley等[10]根據(jù)文獻[9]的模型提出一種可否認的環(huán)認證協(xié)議，將通信輪數(shù)降低到了4輪；然而，文獻[10]的可否認性仍然需要“時間假設”來滿足并發(fā)環(huán)境。文獻[11]使用時限承諾構造了通信輪數(shù)為2輪的全可否認性環(huán)認證方案，該方案的并發(fā)可否認性不需要使用“時間假設”；然而由于采用基于效率較低的非交互式零知識證明系統(tǒng)，其效率不高。綜上，本文提出一種新的可否認的環(huán)認證協(xié)議，該認證過程不會留下任何證據(jù)，因此所有參與者可以否認參與了此次認證，達到了全可否認性。該協(xié)議的可否認性在并發(fā)環(huán)境中成立，且不需要“時間假設”。也就是說，盡管若干次認證通信被攻擊者隨意交錯執(zhí)行，認證的副本仍然可以被仿真。本文提出的可否認的環(huán)認證協(xié)議僅需要2輪，其構造是基于多接收者加密算法的，該加密算法需要滿足明文可意識性(plaintext awareness)。

1 預備知識

1.1多接收者加密算法

假定接收者集合R={pk1,pk2,…,pkn}。使用接收者集合中的所有公鑰R={pk1,pk2,…,pkn}對消息m加密，生成的加密結果Ci被發(fā)送給集合R中對應的成員。收到Ci后，用戶i使用自己的私鑰ski對密文Ci進行解密，得到明文m。這種加密算法被稱為多接收者加密算法[12]。一個對于消息m的多接收者加密算法Σ=(KGen,Enc,Dec)由以下算法組成。

1)密鑰生成算法KGen(1γ)：給定安全參數(shù)γ，返回每個成員i的公私鑰對(pki,ski)←KGen(1γ)。

2)加密算法Enc(R,m)：給定成員集合R={pk1,pk2,…,pkn}以及消息m，返回密文C=(c1,c2,…,cn)←Enc(R,m)。

3)解密算法Dec(R,ci;ski)：給定密文ci，接收者公鑰集合R={pk1,pk2,…,pkn}以及某個接收者私鑰ski，返回m←Dec(R,ci;ski)。

如果一個多接收者加密算法Σ是CCA2安全的，那么攻擊者F不會有超過1/2的概率獲得下面游戲的勝利。

1)F發(fā)布公鑰詢問。挑戰(zhàn)者運行密鑰生成算法(pki,ski)←KGen(1γ)，并設置公鑰集合R={pk1,pk2,…,pkn}。集合R作為此次詢問的返回結果。

3)F任意選取2個長度一樣的明文(m0,m1)以及一個接收者集合R*∈R，F(xiàn)發(fā)布對于(m0,m1)和R*的挑戰(zhàn)詢問。挑戰(zhàn)者隨機選取b←{0,1}，返回此次詢問的結果C*←Enc(R*,mb)。

5)F輸出它的猜測b′。如果b′=b，那就說攻擊者F在此次的游戲中獲得了勝利。

1.2明文可意識性(plaintext awareness)

明文可意識性要求密文擁有者必須知道該密文對應的明文，該概念是由Bellare等[13]提出的。這里分別介紹PA1和PA2這2種層次的明文可意識性。說一個加密算法是PA1安全的，也就是說攻擊者F利用公鑰pk生成了一個有效的密文c，那么存在F′可以在不用訪問解密預言機的情況下得到c對應的明文。很明顯，要使這種情況成立，F(xiàn)′其實可以被當作是攻擊者F本身。由于攻擊者知道他所要詢問的密文所對應的明文，那么這就意味著解密預言機對它來說是無用的。Bellare等[14]指出PA1+CPA≠CCA2而PA2+CPA=CCA2。PA2加強了PA1的安全性，因為PA2允許攻擊者F監(jiān)聽密文。也就是說，PA2性質(zhì)允許F獲得加密預言機，盡管如此，它也不能得到一個不知道其明文的密文。在PA2中，同樣存在一個F′可以在不用訪問解密預言機的情況下輸出由F生成的密文c對應的明文；但是對于F從加密預言機中得到的密文c，F(xiàn)′無法得到c對應的明文。

2 安全模型

為實現(xiàn)消息發(fā)送者的身份對接收者匿名，可否認的環(huán)認證采用環(huán)簽名算法的思想，將發(fā)送者的身份隱藏在一組成員中；因此，可否認的環(huán)認證協(xié)議由發(fā)送者、接收者和一組其他成員組成，所有成員組成了可否認的環(huán)認證協(xié)議的參與者。假定所有參與者的公鑰可以被任何人訪問，發(fā)送者隨意選擇一些成員組成群體R，然后按照可否認的環(huán)認證協(xié)議，對m進行認證。協(xié)議結束后，接收方要么接受此次認證并確信群體R中的某成員對m進行了認證(但不知道具體是哪位成員)，要么拒絕該認證。盡管接收方接受了此次認證，但是它不能夠使第三方相信m被R中成員認證了的事實，即R中成員可以否認此次認證。一個在并發(fā)環(huán)境下安全的可否認的環(huán)認證協(xié)議需要滿足完整性、健壯性、消息源匿名性以及并發(fā)可否認性。

1)完整性。對于要認證的消息m和群體R，如果發(fā)送者A(A的公鑰pkA∈R)與接收者B誠實執(zhí)行協(xié)議，那么接收者B將以壓倒性優(yōu)勢接受此次認證。

2)健壯性(不可偽造性)。敵手F可以得到對于任何消息m1,m2,…關于R的認證副本。如果F使得B接受消息m*?{mi}i=1,2…被環(huán)R*(R*中的所有成員的私鑰都未被F獲得)中的某個成員認證的事實，那么，攻擊者F破壞了可否認的環(huán)認證協(xié)議的健壯性。如果F成功的概率可忽略，那么協(xié)議滿足健壯性。

3)消息源匿名性。盡管F可以獲得R中所有成員的私鑰，F(xiàn)也無法從認證副本中得知該認證是由群體R中的哪位成員執(zhí)行的。

4)并發(fā)可否認性。如果接收方B不能使第三方相信A對m進行了認證，那么該認證協(xié)議滿足可否認性。即存在一個仿真副本(該仿真副本沒有使用認證者的私鑰)，該仿真副本與真實副本是不可區(qū)分的。在并發(fā)環(huán)境里，F(xiàn)與A運行并發(fā)的多次認證通信且這些通信可以被任意的交錯執(zhí)行。如果在這種環(huán)境下，F(xiàn)與A的認證副本同樣存在不可區(qū)分的仿真副本，該協(xié)議滿足并發(fā)可否認性。把F與A之間被模擬的認證記為Γsim，而F與A之間進行的真實的認證記為Γreal。如果存在區(qū)分者D，使得|Pr[D(view(F,Γsim))=1]-Pr[D(view(F,Γreal))]=1|可以忽略，那么并發(fā)可否認性成立。

3 可否認的環(huán)認證協(xié)議Auth

新的可否認的環(huán)認證協(xié)議Auth是基于多接收者加密算法Σ的。如果Σ是一個可驗證的對單一消息的加密算法，那么認證協(xié)議Auth的消息源匿名性是可以實現(xiàn)的。如果Σ滿足PA2安全，那么認證協(xié)議的并發(fā)可否認性是成立的。本文提出的協(xié)議Auth僅需要2輪，而在相同模型下，Naor協(xié)議[9]需要6輪，Dowsley協(xié)議[10]需要4輪。

協(xié)議Auth的執(zhí)行思路是接收方B希望群體R中的成員對消息m進行認證。B首先利用多接收者加密算法Σ對隨機數(shù)k進行加密，并將加密結果flow1發(fā)送給群體R。當收到flow1后，R中的某個成員A首先檢查flow1是否是對單一消息的加密。如果不是，那么A將放棄此次認證；如果是，A對flow1解密并獲得隨機數(shù)k。A利用k對消息m進行認證。協(xié)議Auth的具體執(zhí)行如下。

1)初始化階段。群體R={pk1,pk2,…,pkn}中的公鑰事先注冊并已公開，Σ是一個具有PA2安全的多接收者加密算法，m是需要被認證的消息，H:{0,1}*→{0,1}λ是一個抗碰撞的哈希函數(shù)，MAC是一個安全的消息認證碼算法。

2)協(xié)議執(zhí)行階段。

第1階段，B→A。接收方B選擇一個隨機數(shù)k0并生成k=H(m,R)‖k0。B運行多接收者加密算法Σ=(KGen,Enc,Dec)，對k進行加密，并將flow1=Enc(k)發(fā)送給群體R。

第2階段，A→B。假設群體R中的成員A將要對m進行認證。A首先檢查是否是對單一消息的加密。如果不是，A將放棄此次認證；否則，A再檢查flow1的前λ位是否與H(m,R)相等。如果不等，A將拒絕繼續(xù)認證；如果相等，A對flow1解密得到值k′，并從k′中獲得值k0′。A計算flow2=MACk0′(m,R)，并將認證結果flow2發(fā)送給B。如果flow2=MACk0(m,R)，B將接受此次認證。

如果加密算法Σ是CCA2安全的，那么協(xié)議的可否認性僅在驗證者是誠實的前提下實現(xiàn)；因為，此時的認證副本是通過加密算法Σ生成的密文。該密文也可以由接收者來生成，因此發(fā)送者A可以否認。如果存在一個惡意接收者B*及仿真者M，M收到flow1=Enc(k)；但是它不能仿真MACk0(m,R)，因為M不能解密flow1而得到k0。由于無法仿真這樣的認證副本，發(fā)送者無法否認此次認證；因此，如果Σ僅是CCA2安全的則無法實現(xiàn)協(xié)議Auth的可否認性。

4 安全性分析與性能比較

4.1安全性分析

按照安全模型，對所構造的可否認的環(huán)認證協(xié)議Auth進行消息源匿名性、健壯性以及并發(fā)可否認性等方面的安全性分析。

4.1.1 消息源匿名性

如果Σ是一個可驗證的對單一消息的多接收者加密算法，那么發(fā)送者A的身份就不會在認證中被暴露。因為R中的任何成員收到的密文都是對相同認證密鑰k0的加密，即使R中的所有成員都被俘獲(即Big Brother[9-10])，消息接收者也無法判斷flow2是由R中哪位成員生成的。也就是說，消息認證源滿足了匿名性。

4.1.2 健壯性(不可偽造性)

假設存在破壞協(xié)議Auth健壯性的攻擊者F，F(xiàn)可以得到對于任何消息m1,m2,…關于R的認證副本。如果F可以使B接受消息m*?{mi}i=1,2,…被R*中某個成員認證的事實，那么協(xié)議Auth的健壯性就被破壞。協(xié)議Auth的健壯性由多接收者加密算法Σ的安全性保證。由于Σ是PA2安全的，因此，Bellare在文獻[14]中指出PA2+CPA=CCA2。如果多接收者加密算法Σ滿足PA2和CPA是安全的(即Σ滿足CCA2安全)，那么F成功破壞協(xié)議Auth的健壯性的概率是可忽略的。

定理1：如果MAC是一個安全的消息認證碼算法且多接收者加密算法Σ滿足CCA2安全，那么協(xié)議Auth滿足健壯性。

4.1.3 并發(fā)可否認性

并發(fā)環(huán)境中的仿真器M可以為攻擊者F模擬一個與真實認證副本不可區(qū)分的仿真認證副本，因此，發(fā)送方能夠成功否認對該消息進行過認證。定理2將證明協(xié)議Auth滿足并發(fā)可否認性。

定理2：如果多接收者加密算法Σ滿足PA2和CPA，那么協(xié)議Auth的并發(fā)可否認性成立。

證明：采取仿真技術，通過討論仿真器與攻擊者之間的通信副本并說明該副本與真實通信副本存在不可區(qū)分性來證明協(xié)議Auth滿足可否認性。假定敵手F的目的是攻擊協(xié)議Auth的可否認性，構造一個仿真器M以及2個游戲Γreal和Γsim。游戲Γreal運行的是F與真實發(fā)送者A的通信副本，游戲Γsim運行的是F與仿真器M的通信副本。對于可否認性，需要證明這2個通信副本是不可區(qū)分的，即view(F,Γreal)與view(F,Γsim)是不可區(qū)分的。

討論F與仿真器M的通信副本。首先F向M發(fā)送flow1=c。由于F是惡意的攻擊者，這里有3種情況需要考慮。第1種情況，c是由F生成的有效密文；第2種情況，c是由F生成的無效密文；第3種情況，c是F截獲的誠實接收方與真實發(fā)送方之間交互的副本。在第3種情況中，F(xiàn)并不知道密文c對應的明文。需要討論的是在這3種情況下仿真器M所做的回應并指出view(F,Γreal)≈view(F,Γsim)。

對于第1種情況，c是由F生成的有效密文。由于協(xié)議Auth使用的多接收者加密算法Σ是PA2安全的，那么存在F′可以在不需要訪問解密預言機的情況下為M輸出F生成的密文c所對應的明文，也就是說在這種情況下，M可以得到認證碼k0；因此， M對flow1的回應flow2完全等同于F與真實發(fā)送者之間進行的認證副本。

對于第2種情況，F(xiàn)向M發(fā)送的是無效密文。在這種情況下，M選擇一個隨機數(shù)rk作為認證碼并向F回應flow2=MACrk(m,R)。由于c是無效的密文，這種情況下，無論是仿真的通信還是真實的通信，向MAC碼輸入的認證密鑰都是隨機選取的；因此， F與M的仿真的通信副本分布等同于F與真實發(fā)送者之間進行的認證副本分布。

對于第3種情況，c是F轉(zhuǎn)發(fā)的由誠實接收者向真實發(fā)送者發(fā)送的有效密文，在這種情況下F′無法為M提取c對應的明文。為此，M選擇一個隨機數(shù)rk并向F回應flow2=MACrk(m,R)。在真實的認證中，flow2=MACk0(m,R)，其中k0是密文c中加密的數(shù)據(jù)。在仿真的認證中，flow2是由隨機數(shù)rk生成。由于多接收者加密算法Σ滿足CCA2安全(PA2+CPA=CCA2)，因此區(qū)分者無法分辨c中加密的是rk還是k0，即flow2=MACrk(m,R)與flow2=MACk0(m,R)的分布同樣是不可區(qū)分的。

因此，對于這3種情況，F(xiàn)在與真實發(fā)送者之間的通信副本和在與仿真器交互的副本都是不可區(qū)分的，即view(F,Γreal)≈view(F,Γsim)。故協(xié)議Auth滿足可否認性。由于在證明中，并沒有使用“rewinding”技術[2]，也就是說，即使在多次認證通信可以被攻擊者任意交錯執(zhí)行的并發(fā)環(huán)境中，本文的證明過程仍然是有效的，協(xié)議Auth的并發(fā)可否認性成立。

4.2性能比較

Naor按照“可否認的認證”模型[2]，結合環(huán)簽名思想，提出第一個可否認的環(huán)認證協(xié)議[9]。該協(xié)議在big brother(即所有成員都暴露了私鑰)的情況下，通信輪數(shù)為6。Dowsley等[10]構造了一種基于可驗證的廣播加密算法的可否認的環(huán)認證協(xié)議，該協(xié)議的通信輪數(shù)為4。文獻[9-10]的并發(fā)可否認性都需要“時間假設”。Li等[8]構造了一個基于身份的可否認的認證協(xié)議，該協(xié)議滿足非交互式，即通信輪數(shù)為1，效率很高；然而文獻[8]僅實現(xiàn)了半可否認性，從安全性的角度來說，其方案不及文獻[9-10]。文獻[11]提出一種通信輪數(shù)為2的可否認的環(huán)認證協(xié)議，該協(xié)議滿足big brother情況，且不需要“時間假設”就能實現(xiàn)并發(fā)可否認性；然而，文獻[11]是基于效率較低的非交互式零知識證明系統(tǒng)的。本文構造了一種通信輪數(shù)為2的可否認的環(huán)認證協(xié)議，該協(xié)議滿足big brother情況，實現(xiàn)了全可否認性，且該可否認性在并發(fā)環(huán)境中成立并不需要“時間假設”。表1是從通信輪數(shù)、可否認性的強度等方面對幾個相關的可否認的認證協(xié)議進行比較的結果。

表1 幾個相關協(xié)議的性能比較

5 結論

本文提出了一種新的可否認的環(huán)認證協(xié)議，該協(xié)議構造簡單，通信輪數(shù)僅為2。該認證協(xié)議基于滿足PA2安全的多接收者加密算法。由于利用了可驗證的對單一消息加密的多接收者加密算法，該環(huán)認證協(xié)議滿足消息源匿名性。多接收者加密算法的PA2安全性保證了該環(huán)認證協(xié)議在并發(fā)環(huán)境中仍然可以滿足可否認性。

[1]Dolev D, Dwork C, Naor M. Non-malleable Cryptography[J]. SIAM Journal on Computing,2000, 30(2): 391-437.

[2]Dwork C, Naor M, Sahai A. Concurrent Zero-knowledge[C]//Proceedings of The 30thAnnual ACM Symposium on the Theory of Computing (STOC 1998). Dallas, USA：[s.n.], 1998: 409-418.

[3]Pass R. On Deniability in the Common Reference String and Random Oracle Model[C]//Proceedings of 23rdAnnual International Cryptology Conference (Crypto 2003). Santa Barbara, USA：[s.n.], 2003: 316-337.

[4]Di Raimondo M, Gennaro R, Krawczyk H. Deniable Authentication and Key Exchange[C]//Proceedings of 13thACM Conference on Computer and Communications Security (CCS 2006). Alexandria, USA：[s.n.], 2006: 400-409.

[5]Di Raimondo M, Gennaro R, Naor M. New Approaches for Deniable Authentication[J]. Journal of Cryptology: 2009, 22(4) : 572-615.

[6]Dodis Y, Katz J, Smith A. Composability and on-line Deniability of Authentication[C]//Proceedings of 6thTheory of Cryptography Conference (TCC 2009). SanFrancisco：[s.n.], 2009: 146-162.

[7]Jiang S. Timed Encryption with Application to Deniable Key Exchange[J]. Theoretical Computer Science,2014, 560: 172-189.

[8]Li F, Xiong P, Jin C. Identity-based Deniable Authentication for Ad Hoc Networks[J]. Computing,2014, 96(9): 843-853.

[9]Naor M. Deniable Ring Authentication[C]//Proceedings of 22ndAnnual International Cryptology Conference (Crypto 2002).Santa Barbara, USA：[s.n.], 2002:481-498.

[10]Dowsley R, Hanaoka G., Imai H, et al. Round-optimal Deniable Ring Authentication in the Presence of Big Brother[C]//Proceedings of 11thInternational Workshop on Information Security Applications (WISA 2010).Jeju Island, Korea：[s.n.], 2011: 307-321.

[11]曾晟珂，秦志光. 并發(fā)環(huán)境下可否認的環(huán)認證協(xié)議[J]. 計算機應用研究,2013,30(12): 3745-3748.

[12]Bellare M, Boldyreva A, Micali S. Public-key Encryption in a Multi-user Setting: Security Proofs and Improvements[C]//Proceedings of International Conference on the Theory and Application of Cryptographic Techniques (Eurocrypt 2000). Bruges, Belgium：[s.n.], 2000:259-274.

[13]Bellare M, Rogaway P. Optimal Asymmetric Encryption[C]//Proceedings of Workshop on the Theory and Application of Cryptographic Techniques (Eurocrypt 1994). Perugia, Italy：[s.n.], 1995:92-111.

[14]Bellare M, Palacio A. Towards Plaintext-aware Public-key Encryption without Random Oracles[C]//Proceedings of 10thInternational Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt 2004).Jeju Island, Korea：[s.n.], 2004:48-62.

(編校：饒莉)

DeniableRingAuthenticationBasedonMulti-receiverEncryption

ZENG Sheng-ke, HE Ming-xing, TANG Ming-wei

(SchoolofMathematicsandComputerEngineering,XihuaUniversity,Chengdu610039China)

Deniable ring authentication protocol allows a sender to deny an authentication and his identity is anonymous to the receiver. In this work, we propose a new deniable ring authentication protocol based on the multi-receiver encryption scheme. The receiver encrypts an authentication key with multi-receiver encryption scheme and sends it to the sender. The sender decrypts it using his private key to obtain the authentication key and uses this key to authenticate messages. This protocol only requires two communication rounds and its deniability holds in the concurrent setting without requiring timing assumption due to the multi-receiver encryption.

concurrent deniability； deniable ring authentication；multi-receiver encryption

2014-10-15

國家自然科學基金 (61402376，U1433130)；數(shù)字空間安全保障四川省高校重點實驗室開放課題 (szjj2014-078)；教育部春暉計劃(Z2014051)；四川省科技廳項目(2013JY0089)；四川省教育廳重點項目(13ZA0019)；西華大學重點項目(Z1222623, Z1322622)。

曾晟珂(1982—)，女，講師，博士，主要研究方向為信息安全與密碼學。

TP309

：A

：1673-159X(2015)02-0001-5

10.3969/j.issn.1673-159X.2015.02.001