公钥加密方案的选密安全性证明方法及2次根识别方案在同步攻击下的安全性证明

摘要

1991年，Damgard在[16]中提出了两种简单的公钥加密方案．其中之一是基于Diffie-Hellman/ElGamal体制的，其安全性依赖于有限域上计算离散对数的困难性．该方案似乎是抗非适应性选择密文攻击的，但Zheng和Seberry在[49]中指出，该方案至少不是抗适应性选择密文攻击的，并提出采用单向散列函数来完善它．Soldera分别于2001年和2002年在[46,47]中同时指出，Zheng和Seberry[49]中的方案仍然不是抗适应性选择密文攻击的； Zheng也于1994年在[50]中通过在消息之后并置一个随机值改进了[49]中的方案，得到了所谓的抗内部攻击的单向散列方案．该方案被认为是抗适应性选择密文攻击的实用方案之一，但缺乏严格的安全性证明． 该方案描述如下： 公钥产生阶段：x∈R{1，…，p-1}，令y=g<'x>modp，则PK=(y，p)，SK=x．加密阶段：任给消息m∈{0，1}<'p(K)>，∈R{1，…，p-1}，C<,1>=g<'T>modp；C<,2>={m||H(m||y<'T>modp)} G(y<'T>modp)；则密文就是(C<,1>，C<,2>)．解密阶段：任给密文(c<,1>，C<,2>)，s=C<,1><,x>modp；t=C<,2>[p(k)+1，…，p(k)+l(k)]；m=C<,2>[1，…，p(k)] G(s)；若H(m||s)=t，则输出m；否则，输出”Reject”． 可以看到，在该方案中，在加密阶段，G(y<'T>modp)的作用是进行掩盖．其实，H(m||y<'T>modp)作为一个标签，只是对解密的消息进行确认，根本没必要保密，因为无论m还是r的改变都会引起此标签的变化．因此，除非攻击者同时知道(m，r)，否则根本无法制造在解密阶段能通过全部验证的有效密文．因此，我们在该方案的基础上加以改进，得到了一个新的方案．新加密方案描述如下：公钥产生阶段：x∈R{1，…，p-1}，令y=g<'x>modp，则PK=(y，p)，SK=x．加密阶段：任给消息m∈{0，1}p(k)，r ∈R{1．…，p-1)，C<,1>=g<'r>modp； C<,2>=m G(y<'r>modp)； C<,3>=H(m‖y<'r>modp)；则密文就是(C<,1>，C<,2>，C<,3>)．解密阶段；任给密文(C<,1>，C<,2>，C<,3>)， s=C<,1><'x>modp； m=C<,2> G(s)；若H(m‖s)=C<,3>，则输出m；否则，输出”Reject”．在CDH假设下，我们分别运用归约法和游戏序列法证明了它是抗适应性选择密文攻击的． 在运用归约法证明其安全性时，我们将该方案的安全性归约为求解CDH问题的困难性． 定理1.4.1设A=(A<,1>，A<,2>)是一个选择密文攻击的敌手，在时间t内，它提了不超过qD次解密请求，向随机预言机G和H分别询问了不超过qG次和qH次且攻破该加密方案的优势为∈，则存在一个算法B，利用它成功解决CDH问题的概率∈'≥2∈/qG-qD/QG[ε(H)+2<'-l(k)]；运行时间上界t'≤t+qHT(C<,2>)+[qG+qH+qD·qH]O(1)，其中ε(H)为找到散列函数H的一对碰撞的概率．T(C<,2>)为加密时计算C<,2>的时间． 在分析整个归约算法的概率时，我们得到了一个用来估计敌手询问G(u<'r*>)的概率的结果．该结果比Boneh在[8]中的结果更精确且前者缺乏严格的证明．定理1.4.2设A是一个选择密文攻击敌手，在真实的攻击中攻破方案的优势为Adv(A)，则 Pr<,real>[AskG]≥2.AdV(A)． 注解：Boneh在[8]中的结果为Pr<,real>[AskG]≥Adv(A)；此结论对于方案OAEP，OAEP<'+>，SAEP，SAEP<'+>都适用． 关于2<'m>次根方案的安全性，Shoup在[40]中证明了若分解整数是困难的，则它能抗主动攻击．Bellare和Palacio在[7]中提出了同步攻击的概念并证明了它是主动攻击的一种推广．本文在第三部分考虑了2<'m>次根方案在同步攻击下的安全性．我们首先推广了Bellare和Palacio在[7]中的“重复挑战引理”，将那儿的实数域内不同的两次挑战推广到mod 2<'l+1>范围内的不同． 令acc(SK，PK)表示当私钥和公钥分别为SK和PK时，证明者使验证者接受的概率． 令res(SK，PK)表示当私钥和公钥分别为SK和PK时，面对验证者在模2<'l(k)+1>下内的两个不同挑战证明者均能使验证者接受的概率．则由新的重复挑战引理，我们将2<'m>次根方案的安全性归约为找n的非平凡因子问题． 定理3.4.2设ID=(K，P,V)是一个2<'m>次根方案，公共模为n．假设存在一个同步攻击敌人(V，p)使得它能以ε(K)的成功概率攻击ID，则存在一个算法A来分解n且对每一个k其成功概率其中，l(k)为满足不等式2<'m>>2<'l(k)>≥1/ε(k)的最小正整数． Shoup在[40]中讨论n的分解算法的成功概率时，只讨论了3/4重行上的1所占比例的影响，我们将此推广到了任意亡重行． (1)对于固定的h，SK，PK而言，d<,1>=1位于t重行的概率至少为1-t． (2)如果d<,1>=1位于t重行，则在t重行上选到CH<,1>≠CH<,2>mod2<'l(k+1>的概率ε′≥t acc(h，SK，PK)-2-<'-l(k)-1>． (3)对于满足acc(h，sK，PK)≥ε(k)的h，sK，PK而言，如果重复与交互至次，一旦成功，固定p的随机选择，再重复与p交互至[t acc(h，SK，PK)-2<'-l(k)-1>]<'-1>]次，则重复挑战实验成功的概率至少为(1-t)(1-1/e)<'2>．

目录

文摘

英文文摘

论文说明：符号

原创性声明及关于学位论文使用授权的声明

Chapter 1 新选择密文安全的公钥加密方案

§1.1引言

§1.2相关的困难假设

§1.3新公钥加密方案

§1.4新方案的安全性在归约方式下的证明

§1.5新方案安全性在游戏序列方式下的证明

Chapter 2 ZS抗内部攻击的单向散列方案的选择密文安全性证明

§2.1 ZS方案在归约方式下的证明

§2.2 ZS方案在游戏序列方式下的证明

Chapter 3 2m 次根识别方案在同步攻击下的安全性证明

§3.1引言

§3.2定义

§3.3新重复挑战引理

§3.4 2m 次根识别方案在同步攻击下的安全性

Bibliography

致谢

自我简介