密碼學(xué)中的隨機(jī)預(yù)言模型與標(biāo)準(zhǔn)模型

摘 要：隨機(jī)預(yù)言模型與標(biāo)準(zhǔn)模型是密碼學(xué)可證明安全理論中非常重要的兩類(lèi)模型。在此對(duì)這兩種模型進(jìn)行了描述，并研究了運(yùn)用它們證明密碼方案或協(xié)議安全性時(shí)所采取的不同技術(shù)，包括隨機(jī)預(yù)言模型在加密和數(shù)字簽名方案中的應(yīng)用研究，以及標(biāo)準(zhǔn)模型下可證明安全性理論在加密方案中的應(yīng)用研究。此外對(duì)進(jìn)一步研究方向進(jìn)行了展望。

關(guān)鍵詞：可證明安全性; 隨機(jī)預(yù)言模型; 標(biāo)準(zhǔn)模型; 加密方案

中圖分類(lèi)號(hào)：TN918.1-34 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X(2011)17-0098-03

Random Oracle Model and Standard Model in Cryptography

WANG Xiao-sheng1， LI Li2

(1.Shaanxi Youth Vocatinal College， Xi’an 710068， China; 2.Primary Education College， Xi’an University of Arts and Sciense， Xi’an 710001， China)

Abstract： The random oracle model and standard model are two important ones in the theory of provable security in cryptography. These two models are described and the different technique for proving cryptographic scheme and protocol security when using these models is researched. The application research on the random oracle model in encryption and digital signature schemes， and the theory of provable security under standard model in encryption scheme was carried out. The further research direction is pointed out.

Keywords： provable security; random oracle model; standard model; encryption scheme

0 引 言

隨機(jī)預(yù)言模型和標(biāo)準(zhǔn)模型在密碼學(xué)的可證明安全性中扮演著重要角色。

隨機(jī)預(yù)言模型是指所有的協(xié)議參與方(包括攻擊者)都有對(duì)公共的隨機(jī)預(yù)言機(jī)的訪(fǎng)問(wèn)權(quán)(這里的隨機(jī)預(yù)言機(jī)是指對(duì)某個(gè)輸入x，其返回某個(gè)隨機(jī)預(yù)言f(x))。一般方法：設(shè)計(jì)協(xié)議時(shí)首先設(shè)計(jì)在隨機(jī)預(yù)言機(jī)下的安全協(xié)議PR，然后適當(dāng)選擇可實(shí)際計(jì)算的函數(shù)h來(lái)代替R。

標(biāo)準(zhǔn)模型下的密碼方案其實(shí)就是在不借助任何假想模型下所設(shè)計(jì)的方案。由于標(biāo)準(zhǔn)模型沒(méi)有任何安全證明環(huán)節(jié)上的假想存在，安全性?xún)H僅建立在一些已被廣泛接受的假設(shè)基礎(chǔ)上，所以其安全性值得高度信賴(lài)。

1 基于隨機(jī)預(yù)言模型加密方案的可證安全性

沒(méi)有使用隨機(jī)預(yù)言模型的可證明安全的加密方案：如果令Bf表示對(duì)f的核心斷言，那么語(yǔ)義安全可以通過(guò)令E(x)=f(r1)‖…‖f(r|x|) 來(lái)取得。其中，每一個(gè)ri在f的定義域隨機(jī)選取，限制條件是Bf(ri)=xi，可以看到密文的長(zhǎng)度為O(k#8226;|x|)，需要O(|x|)次f操作來(lái)加密，及O(|x|)次f－1操作來(lái)解密，可以看出以上方案是非常低效的。

再給出另一加密方案：

定理1：上述加密方案在隨機(jī)預(yù)言機(jī)模型下是選擇密文攻擊安全的。

證明：利用反證法。令A(yù)=(F，A1)是攻破上述加密方案的攻擊者，其成功概率為λ(k)(其量級(jí)為多項(xiàng)式倒數(shù)級(jí))。構(gòu)建一算法M(f，d，y)，其中(f，f－1，d)←G(1k)；r←d(1k);y←f(r)，它們將以較大的概率輸出f－1(y)。算法M首先運(yùn)行F(E)，其中E通過(guò)已知的f如上面方案中那樣定義。F需要三個(gè)預(yù)言機(jī)G，H及DG，H，M通過(guò)如下方式來(lái)模擬：如果對(duì)G的詢(xún)問(wèn)滿(mǎn)足f(r)=y，那么M輸出r，并終止模擬，否則返回隨機(jī)選擇合適長(zhǎng)度的字符串。如果對(duì)H的詢(xún)問(wèn)，rx滿(mǎn)足f(r)=y，那么M輸出r，并終止模擬，否則返回隨機(jī)選擇合適長(zhǎng)度的字符串。為了回答對(duì)DG，H的詢(xún)問(wèn)，a‖ω‖b，M首先查看是否有詢(xún)問(wèn)r被提交給了G及詢(xún)問(wèn)ru被提交給了H。其中，a=f(r)及ω=G(r)⊕u，如果是這樣，返回u，否則返回“非法密文”。當(dāng)M運(yùn)行完F(E)后，隨機(jī)選擇定義域內(nèi)的明文(m0，m1)←FG(E)，現(xiàn)在M運(yùn)行A1(E，m0，m1，α)。其中，α=y‖ω‖b，ω←{0，1}|m0|及b←{0，1}k，同樣的M按照上面的模擬方式來(lái)模擬G，H和DG，H。

先考慮真實(shí)環(huán)境中的攻擊者A，令A(yù)k表示事件a‖ω‖b←F(E)，A做過(guò)一些預(yù)言機(jī)詢(xún)問(wèn)G(r)及H(ru)，其中f(r)=a。令Lk表示事件A1向預(yù)言機(jī)DG，H詢(xún)問(wèn)過(guò)a‖ω‖b，其中b=H(f－1(a)‖ω⊕G(f－1(a))，但是A1從來(lái)沒(méi)有向H詢(xún)問(wèn)過(guò)f－1(a)‖ω⊕G(f－1(a))。令n(k)表示預(yù)言機(jī)所做的總的詢(xún)問(wèn)次數(shù)，容易驗(yàn)證Pr［Lk］≤n(k)2－k。很容易看到：

現(xiàn)在回到M對(duì)A的模擬，注意到M對(duì)A模擬失敗的最高概率為Pr［Lk］，因此有

Pr［M在y點(diǎn)成功求出f的逆］≥λ(k)－n(k)2－k+1，其仍然是不可忽略的。這與f是單向函數(shù)相矛盾。

2 基于隨機(jī)預(yù)言模型的簽名方案的可證安全性

首先選定一陷門(mén)置換發(fā)生器G*，令H:{0，1}*→{0，1}k表示通常的隨機(jī)哈希函數(shù)，G*以1k為輸入計(jì)算(f，f－1，d)←G*(1k)，令PK=f及SK=f－1，輸出(PK，SK)簽名方案是(G，SignH，VerifyH)SignH(f－1，m)=f－1(H(m))VerifyH(f，m，σ)=1，當(dāng)且僅當(dāng)f(σ)=H(m)。

定理2：上述簽名方案是選擇明文攻擊安全的。

證明：利用反證法。令F是攻擊簽名方案成功的攻擊者，其成功的概率為λ(k)(為不可忽略函數(shù))，構(gòu)建一算法M(f，d，y)，使得:

是不可忽略的。這與G*是一陷門(mén)置換生成器的事實(shí)矛盾。M(f，d，y)以如下方式工作：令PK=f，它替F拋擲硬幣，開(kāi)始運(yùn)行F(PK)。假設(shè)F對(duì)H作了n(k)次詢(xún)問(wèn)，均不相同，并假設(shè)F對(duì)m作簽名詢(xún)問(wèn)之前，其一定已經(jīng)詢(xún)問(wèn)過(guò)H。M隨機(jī)的選擇t∈{1，2，…，n(k)}，它對(duì)這些詢(xún)問(wèn)的回答如下：

(1) 令mi記為F做的對(duì)H的第i次詢(xún)問(wèn)，如果i=t，那么M返回y，否則隨機(jī)選擇ri←{0，1}k，并且返回yi=f(ri)

(2) 假設(shè)F作簽名詢(xún)問(wèn)m，如果m=mt，那么M終止，模擬失敗，否則，M回答ri，對(duì)于i≠t滿(mǎn)足m=mt。

令(m，σ)是F的輸出，如果m≠mt，那么M終止并輸出失敗，否則如果f(σ)=m，那么M輸出σ并終止，否則它承認(rèn)失敗。令Sk表示事件F在這個(gè)實(shí)驗(yàn)中成功，注意到F是成功的，它的輸出(m，δ)滿(mǎn)足m=mt，并且mt被定義為沒(méi)有向簽名預(yù)言機(jī)詢(xún)問(wèn)過(guò)，那么有:

由于t是隨機(jī)選擇的，有Pr［SkΛ(m=mt)］ ≥(λ(k)－2－k)/n(k)，那么有ε(k)≥ (λ(k)－2－k)/n(k)仍是不可忽略的，這與f是陷門(mén)置換相矛盾。

3 基于標(biāo)準(zhǔn)模型的可證安全的加密方案

下面介紹標(biāo)準(zhǔn)模型下著名的Cramer-Shoup體制，體會(huì)在標(biāo)準(zhǔn)模型下設(shè)計(jì)密碼方案的技巧性。為了更容易理解，將分層次構(gòu)造Cramer-Shoup體制，即先介紹DDH假設(shè)，再構(gòu)造IND-CPA安全的加密方案，然后構(gòu)造IND-CCA1的加密方案，最后構(gòu)造IND-CCA2安全的Cramer-Shoup加密方案。

定義1：考慮以下兩種分布：第一種類(lèi)型為(g1，g2，gr1，gr2)，第二種類(lèi)型為(g1，g2，gr11，gr22)。其中q是一大素?cái)?shù)，g1，g2，r，r1，r2是在Z*q中隨機(jī)選擇的元素。到目前為止，沒(méi)有任何多項(xiàng)式時(shí)間運(yùn)行的算法可以以不可忽略的概率區(qū)分以上兩種分布，因此假設(shè)以上兩種分布是不可分辨的(對(duì)多項(xiàng)式運(yùn)行時(shí)間的攻擊者)。這就是Decisional Diffle-Hellman 假設(shè)，簡(jiǎn)稱(chēng)DDH假設(shè)。 3.1 修改的ELGAMAL算法(IND-CPA安全)

公鑰參數(shù)：隨機(jī)生成的大素?cái)?shù)q，兩個(gè)隨機(jī)選擇的生成元(g1，g2)及h=gz11gz22，即(q，g1，g2，gz11gz22)私鑰參數(shù)：兩個(gè)在Zq*中隨機(jī)選擇的(z1，z2)；加密算法：E(m，r)=(gr1，gr2，hrm)=(u1，u2，e)；解密算法：D(u1，u2，e)=eu1z1u2z2=hrmgrz11grz22=m。

定理3：修改的ELGAMAL加密算法是IND-CPA安全的。

證明：利用歸約思想，假設(shè)存在對(duì)該加密算法IND-CPA性質(zhì)的攻擊者，以不可忽略的概率成功，記為ADV，這里將以其為子程序，構(gòu)建對(duì)DDH難題，以不可忽略概率分辨成功的算法。

若DDH難題的輸入為(g1，g2，u1，u2)，構(gòu)建與上述加密算法相同的公私鑰參數(shù)。以(g1，g2)為公鑰，并且構(gòu)建公鑰h=g1z1g2z2，私鑰為兩隨機(jī)在Zq*中選擇的(z1，z2)。該算法發(fā)送一消息給ADV，且ADV返回兩消息m0和m1，隨機(jī)選擇其中一消息mb，并且發(fā)送u1，u2及e=hrmb給ADV作為挑戰(zhàn)密文，然后ADV輸出猜測(cè)g，該算法檢測(cè)g=b成立的概率，這個(gè)概率成立的大小將直接與

(g1，g2，u1，u2)=(g1，g2，gr11，gr22)是否是四元Diffle-Hellman組相關(guān)。

命題1：如果r1=r2，那么g=b的概率將超過(guò)1/2+1/poly(k);

命題2：如果r1≠r2，那么g=b的概率將等于1/2+1/2-k。

這樣，該算法就能以不可忽略的概率區(qū)分四元Diffle-Hellman組與非四元Diffle-Hellman組，與DDH假設(shè)矛盾。

3.2 IND-CCA1安全的Cramer-Shoup體制

公鑰參數(shù)：隨機(jī)生成的大素?cái)?shù)q，2個(gè)隨機(jī)選擇的生成元(g1，g2)及h=gz11gz22和c=gx11gx22；

私鑰參數(shù)：4個(gè)在z*q中隨機(jī)選擇的參數(shù)z1，z2及x1，x2；

加密算法E(m，r)=(gr1，gr2，hrm，cr=ux11ux22)=(u1，u2，e，v)；

解密算法：首先驗(yàn)證v=cr=ux11ux22，然后計(jì)算消息m=e/uz11uz22。

定理4：提高的修改ELGAMAL加密方案是IND-CCA1安全的。

證明：同樣假設(shè)存在對(duì)上述方案IND-CCA1性質(zhì)攻擊成功的攻擊者，不妨記為ADV。在此將利用此攻擊者成功攻擊DDH假設(shè)，這樣就歸約出了矛盾。假設(shè)給了(g1，g2，u1，u2)，將使用g1，g2作為公鑰，并且令h=gz11gz22及c=gx11gx22也為公鑰。密鑰將由4個(gè)在Zq*中隨機(jī)選擇的元素(z1，z2，x1，x2)組成。該算法給ADV發(fā)送某消息，ADV將發(fā)送某密文，該算法將給其解密，這樣進(jìn)行多次，直到某時(shí)ADV發(fā)送兩消息m0和m1作為挑戰(zhàn)明文，該算法隨機(jī)選擇其中的某一明文，再發(fā)送(u1，u2，e=uz11uz22mb，ux11ux22)給ADV，然后ADV返回猜測(cè)g，算法檢測(cè)g=b，這個(gè)概率成立的大小將直接與(g1，g2，u1，u2)=(g1，g2，gr11，gr22)是否是四元Diffle-Hellman組相關(guān)。

命題3：攻擊者不能以不可忽略的概率成功詢(xún)問(wèn)非法密文的解密。

因此攻擊者并不能借助于解密預(yù)言機(jī)獲得幫助，即午餐攻擊對(duì)攻擊者沒(méi)有任何幫助，定理得證。

3.3 IND-CCA2安全的Cramer-Shoup體制

公鑰參數(shù)：隨機(jī)生成的大素?cái)?shù)q，兩個(gè)隨機(jī)選擇的生成元(g1，g2)及h=gz11gz22，c=gx11gx22，d=gy11gy22和抗碰撞的公開(kāi)的哈希函數(shù)H；私鑰參數(shù)：6個(gè)在Zq*隨機(jī)選擇的參數(shù)(z1，z2，x1，x2，y1，y2)；加密算法：E(m，r)=(gr1，gr2，hrm，crdαr)=(u1，u2，e，v)；解密算法：首先計(jì)算α=H(u1，u2，e)，然后做密文正確性檢測(cè)v=ux1+αy11ux2+αy22，如果檢測(cè)沒(méi)有通過(guò)，那么輸出“非法密文”，若通過(guò)，計(jì)算m=euz11uz22，輸出m。

定理5：Cramer-Shoup加密方案是IND-CCA2安全的。

證明：假設(shè)存在對(duì)上面方案IND-CCA2性質(zhì)攻擊成功的攻擊者，不妨記為ADV。在此將利用此攻擊者成功攻擊DDH假設(shè)，這樣就歸約出了矛盾。 此時(shí)密文的正確性檢測(cè)所給出的限制為：

密文正確性檢測(cè)限制給出了一“平面”，兩公鑰的限制又給出了另一“平面”，而這兩“平面”僅僅能交到一條“線(xiàn)”上。攻擊者能夠偽造密文必須要用到α，要么是新的α，要么用老的α，在這兩種情況下攻擊者偽造合法密文的概率都是可忽略的。第一種情況：攻擊者使用以前的α，但是四元組(u1，u2，e，v)的前3項(xiàng)卻與以前的不同。根據(jù)哈希函數(shù)H的性質(zhì)可知道，這種概率可以忽略。第二種情況：攻擊者使用新的α。那么構(gòu)造的密文參數(shù)除非剛好落在所交的那條“線(xiàn)”上，否則將被拒絕，而落在“交”的那條線(xiàn)上的概率卻是可以忽略不計(jì)的。所以攻擊者可以偽造合法密文的概率是可以忽略不計(jì)的，即證方案是IND-CCA2安全的。

4 結(jié) 論

隨機(jī)預(yù)言模型提供了在密碼理論與密碼實(shí)踐之間聯(lián)系的橋梁。因此，基于隨機(jī)預(yù)言模型設(shè)計(jì)的方案一般都很高效。標(biāo)準(zhǔn)模型下的密碼方案其實(shí)就是在不借助任何假想模型下所設(shè)計(jì)的方案。由于標(biāo)準(zhǔn)模型沒(méi)有任何安全證明環(huán)節(jié)上的假想存在，安全性?xún)H僅建立在一些已被廣泛接受的假設(shè)基礎(chǔ)上，所以其安全性值得高度信賴(lài)。顯然，如何設(shè)計(jì)在隨機(jī)預(yù)言模型下高效的方案及如何更多地設(shè)計(jì)出在標(biāo)準(zhǔn)模型下安全的方案將是下一步研究的重點(diǎn)。

參 考 文 獻(xiàn)

［1］BELLARE M，ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocals [C]// Proceedings of First ACM Conf. on Computer and Communications Security. New York， USA: ACM Press， 1993: 168588-168596.

［2］BELLARE M. Practice-oriented provable security [M]. Berlin: Springer-Verlag， 1997.

［3］CRAMER R， SHOUP V. Universal hash proofs and a pa-radigm for adaptive chosen ciphertext secure public-key encryption [M]. Berlin: Springer-Verlag， 2002: 45-64

［4］CANETTI R， GOLDREICH O， HALEVI S. The random oracle methodology， revisited [C]// Proceedings of the 30th Annual ACM Symposium on the Theory of Computing. New York， USA: ACM Press， 1998: 209-218.

［5］KOBLITZ N， MENEZES A. Another look at \"provable security\" [J]. Journal of Cryptology， 2004， 20 (1): 3-37.

［6］CANETTI R. Selected Topics in Cryptograhy [M]. USA: MIT， 2004.

作者簡(jiǎn)介：

王曉生 男，1975年出生，陜西西安人，講師。主要研究方向?yàn)橛?jì)算機(jī)教學(xué)。

李 莉 女，1976年出生，陜西西安人，講師。主要從事計(jì)算機(jī)教學(xué)工作。