密码学中的随机预言模型与标准模型

摘 要：随机预言模型与标准模型是密码学可证明安全理论中非常重要的两类模型。在此对这两种模型进行了描述，并研究了运用它们证明密码方案或协议安全性时所采取的不同技术，包括随机预言模型在加密和数字签名方案中的应用研究，以及标准模型下可证明安全性理论在加密方案中的应用研究。此外对进一步研究方向进行了展望。

关键词：可证明安全性; 随机预言模型; 标准模型; 加密方案

中图分类号：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•|x|)，需要O(|x|)次f操作来加密，及O(|x|)次f－1操作来解密，可以看出以上方案是非常低效的。

再给出另一加密方案：

定理1：上述加密方案在随机预言机模型下是选择密文攻击安全的。

证明：利用反证法。令A=(F,A1)是攻破上述加密方案的攻击者，其成功概率为λ(k)(其量级为多项式倒数级)。构建一算法M(f,d,y)，其中(f,f－1,d)G(1k)；rd(1k);yf(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ωbF(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年出生，陕西西安人，讲师。主要从事计算机教学工作。