密碼學中的隨機預言模型與標準模型

摘 要：隨機預言模型與標準模型是密碼學可證明安全理論中非常重要的兩類模型。在此對這兩種模型進行了描述，并研究了運用它們證明密碼方案或協議安全性時所采取的不同技術，包括隨機預言模型在加密和數字簽名方案中的應用研究，以及標準模型下可證明安全性理論在加密方案中的應用研究。此外對進一步研究方向進行了展望。

關鍵詞：可證明安全性; 隨機預言模型; 標準模型; 加密方案

中圖分類號：TN918.1-34 文獻標識碼：A

文章編號：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 引 言

隨機預言模型和標準模型在密碼學的可證明安全性中扮演著重要角色。

隨機預言模型是指所有的協議參與方(包括攻擊者)都有對公共的隨機預言機的訪問權(這里的隨機預言機是指對某個輸入x，其返回某個隨機預言f(x))。一般方法：設計協議時首先設計在隨機預言機下的安全協議PR，然后適當選擇可實際計算的函數h來代替R。

標準模型下的密碼方案其實就是在不借助任何假想模型下所設計的方案。由于標準模型沒有任何安全證明環節上的假想存在，安全性僅僅建立在一些已被廣泛接受的假設基礎上，所以其安全性值得高度信賴。

1 基于隨機預言模型加密方案的可證安全性

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

再給出另一加密方案：

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

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

先考慮真實環境中的攻擊者A，令Ak表示事件a‖ω‖b←F(E)，A做過一些預言機詢問G(r)及H(ru)，其中f(r)=a。令Lk表示事件A1向預言機DG，H詢問過a‖ω‖b，其中b=H(f－1(a)‖ω⊕G(f－1(a))，但是A1從來沒有向H詢問過f－1(a)‖ω⊕G(f－1(a))。令n(k)表示預言機所做的總的詢問次數，容易驗證Pr［Lk］≤n(k)2－k。很容易看到：

現在回到M對A的模擬，注意到M對A模擬失敗的最高概率為Pr［Lk］，因此有

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

2 基于隨機預言模型的簽名方案的可證安全性

首先選定一陷門置換發生器G*，令H:{0，1}*→{0，1}k表示通常的隨機哈希函數，G*以1k為輸入計算(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，當且僅當f(σ)=H(m)。

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

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

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

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

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

令(m，σ)是F的輸出，如果m≠mt，那么M終止并輸出失敗，否則如果f(σ)=m，那么M輸出σ并終止，否則它承認失敗。令Sk表示事件F在這個實驗中成功，注意到F是成功的，它的輸出(m，δ)滿足m=mt，并且mt被定義為沒有向簽名預言機詢問過，那么有:

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

3 基于標準模型的可證安全的加密方案

下面介紹標準模型下著名的Cramer-Shoup體制，體會在標準模型下設計密碼方案的技巧性。為了更容易理解，將分層次構造Cramer-Shoup體制，即先介紹DDH假設，再構造IND-CPA安全的加密方案，然后構造IND-CCA1的加密方案，最后構造IND-CCA2安全的Cramer-Shoup加密方案。

定義1：考慮以下兩種分布：第一種類型為(g1，g2，gr1，gr2)，第二種類型為(g1，g2，gr11，gr22)。其中q是一大素數，g1，g2，r，r1，r2是在Z*q中隨機選擇的元素。到目前為止，沒有任何多項式時間運行的算法可以以不可忽略的概率區分以上兩種分布，因此假設以上兩種分布是不可分辨的(對多項式運行時間的攻擊者)。這就是Decisional Diffle-Hellman 假設，簡稱DDH假設。 3.1 修改的ELGAMAL算法(IND-CPA安全)

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

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

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

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

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

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

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

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

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

公鑰參數：隨機生成的大素數q，2個隨機選擇的生成元(g1，g2)及h=gz11gz22和c=gx11gx22；

私鑰參數：4個在z*q中隨機選擇的參數z1，z2及x1，x2；

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

解密算法：首先驗證v=cr=ux11ux22，然后計算消息m=e/uz11uz22。

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

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

命題3：攻擊者不能以不可忽略的概率成功詢問非法密文的解密。

因此攻擊者并不能借助于解密預言機獲得幫助，即午餐攻擊對攻擊者沒有任何幫助，定理得證。

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

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

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

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

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

4 結 論

隨機預言模型提供了在密碼理論與密碼實踐之間聯系的橋梁。因此，基于隨機預言模型設計的方案一般都很高效。標準模型下的密碼方案其實就是在不借助任何假想模型下所設計的方案。由于標準模型沒有任何安全證明環節上的假想存在，安全性僅僅建立在一些已被廣泛接受的假設基礎上，所以其安全性值得高度信賴。顯然，如何設計在隨機預言模型下高效的方案及如何更多地設計出在標準模型下安全的方案將是下一步研究的重點。

參 考 文 獻

［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.

作者簡介：

王曉生 男，1975年出生，陜西西安人，講師。主要研究方向為計算機教學。

李 莉 女，1976年出生，陜西西安人，講師。主要從事計算機教學工作。