密码学中的可证明安全性-杨波-2014.11.11

语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案密码学中的可证明安全性杨波陕西师范大学计算机学院杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案目录1语义安全IND-CPAIND-CCAIND-CCA2EUF-CMA规约2IBE的背景3IBE的安全性双线性映射BDH假设4选择明文安全的IBE方案5选择密文安全的IBE方案杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约单向加密–Onewayencryption如果敌手已知某个密文，不能得出所对应的明文的完整信息，该公钥加密方案称为单向加密（Onewayencryption，简称OWE），是一个很弱的安全概念，因为不能防止敌手得到明文的部分信息。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约语义安全语义安全（Semanticscurity）的概念由Goldwasser和Micali于1984年提出，即敌手即使已知某个消息的密文，也得不出该消息的任何部分信息,即使是1比特的信息。这一概念的提出开创了可证明安全性领域的先河，奠定了现代密码学理论的数学基础，将密码学从一门艺术变为一门科学。获得2012年度图灵奖。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约语义安全加密方案语义安全的概念由不可区分性(Indistinguishability)游戏（简称IND游戏）来刻画，这种游戏是一种思维实验，其中有2个参与者，一个称为挑战者（challenger)，另一个是敌手。挑战者建立系统，敌手对系统发起挑战，挑战者接受敌手的挑战。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约语义安全思维实验(（thoughtexperiment）)是用来考察某种假设、理论或原理的结果而假设的一种实验，这种实验可能在现实中无法做到，也可能在现实中没有必要去做。思维实验和科学实验一样，都是从现实系统出发，建立系统的模型，然后通过模型来模拟现实系统。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约科学实验与思维实验图1-1:科学实验与思维实验杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约科学实验与思维实验图1-2:科学实验与思维实验杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约科学实验与思维实验图1-3:薛定谔的猫系统是真空的、无光的杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性(IND-CPA)公钥加密方案在选择明文攻击下的IND游戏（称为IND-CPA游戏）如下：1初始化：挑战者产生系统ℰ，敌手获得系统的公开钥;2挑战：敌手输出两个长度相同的消息m0和m1。挑战者随机选择b∈{0,1}，将mb加密，并将密文（称为目标密文）给敌手;3猜测：敌手输出b′，如果b′=b,则敌手攻击成功。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性(IND-CPA)公钥加密方案在选择明文攻击下的IND游戏（称为IND-CPA游戏）如下：1初始化：挑战者产生系统ℰ，敌手获得系统的公开钥;2挑战：敌手输出两个长度相同的消息m0和m1。挑战者随机选择b∈{0,1}，将mb加密，并将密文（称为目标密文）给敌手;3猜测：敌手输出b′，如果b′=b,则敌手攻击成功。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性(IND-CPA)公钥加密方案在选择明文攻击下的IND游戏（称为IND-CPA游戏）如下：1初始化：挑战者产生系统ℰ，敌手获得系统的公开钥;2挑战：敌手输出两个长度相同的消息m0和m1。挑战者随机选择b∈{0,1}，将mb加密，并将密文（称为目标密文）给敌手;3猜测：敌手输出b′，如果b′=b,则敌手攻击成功。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性敌手的优势可定义为参数k的函数：Advℰ,A(k)=|Pr[b=b′]−12|其中k是安全参数，用来确定加密方案密钥的长度。因为任一个不作为的敌手A，都能通过对b做随机猜测，而以12的概率赢得IND-CPA游戏。而|Pr[b=b′]−12|是敌手通过努力得到的，故称为敌手的优势。Definition1.1如果对任何多项式时间的敌手A，存在一个可忽略的函数negl(k)，使得AdvCPAℰ,A(k)≤negl(k)，那么就称这个加密算法在选择明文攻击下具有不可区分性，或者称为IND-CPA安全。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性如果敌手通过mb的密文能得到mb的一个比特，则有可能区分mb是m0还是m1，因此IND游戏刻画了语义安全的概念;定义中敌手是多项式时间的，否则因为它有系统的公开钥，可得到m0和m1的任意多个密文，再和目标密文逐一进行比较，即可赢得游戏;杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性如果加密方案是确定的，如RSA算法、Rabin密码体制等，每个明文对应的密文只有一个，敌手只需重新对m0和m1加密后，与目标密文进行比较，即赢得游戏。因此语义安全性不适用于确定性的加密方案。与确定性加密方案相对的是概率性的加密方案，在每次加密时，首先选择一个随机数，再生成密文。因此同一明文在不同的加密中得到的密文不同，如ElGamal加密算法。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性例：ElGamal加密算法1密钥产生：设G是阶为大素数q的群,g为G的生成元，随机选x∈Z*q,计算y=gxmodq.以x为秘密钥，(y,g,q)为公开钥。2加密：设消息m∈G,随机选一与p−1互素的整数k，计算c1=gkmodq,c2=ykmmodq密文为c=(c1,c2).3解密：m=c2/cx1modq.杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性例：ElGamal加密算法安全性基于Diffie-Hellman判定性问题：设G是阶为大素数q的群，g1,g2为G的生成元。没有多项式时间的算法区分以下2个分布：随机4元组R=(g1,g2,u1,u2)∈G4的分布；4元组D=(g1,g2,u1,u2)∈G4的分布，其中u1=gr1,u2=gr2,r∈RZq.变形：做代换g1→g,g2→gx,u1→gy,u2→gxy,2个分布变为：3元组R=(gx,gy,gz)∈G3的分布；3元组D=(gx,gy,gxy)∈G3的分布.杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性例：ElGamal加密算法在ElGamal加密算法的IND-CPA游戏中，敌手输出两个长度相同的消息m0、m1，挑战者加密mb(b∈{0,1})，得C=(C1,C2)=(gkmodp,ykmbmodp)。如果b=0，则(C1,y,C2/m0)=(gkmodp,gxmodp,gkxmodp)为Diffie-Hellman3元组。如果b=1，则(C1,y,C2/m1)=(gkmodp,gxmodp,gkxmodp)为Diffie-Hellman3元组。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性例：ElGamal加密算法然而，INDCPA安全仅仅保证敌手是完全被动情况时（即仅做监听）的安全，不能保证敌手是主动情况时（例如向网络中注入消息）的安全。例如敌手收到密文为C=(C1,C2)，构造新的密文C′=(C1,C′2)，其中C′2=C2m′，解密询问后得到M=mm′。或者构造新的密文C′′=(C′′1,C′′2)，其中C′′1=C1gk′′,C′′2=C2yk′′m′，此时C′1=gkgk′′=gk+k′′,C′′2=ykmyk′′m′=yk+k′′mm′解密询问后仍得到M=mm′。再由Mm′modp，得到C的明文m。可见，ElGamal加密算法不能抵抗主动攻击。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分性(IND-CCA)为了描述敌手的主动攻击，1990年Naor和Yung提出了（非适应性）选择密文攻击（ChosenCiphertextAttack，简称为CCA）的概念，其中敌手在获得目标密文以前，可以访问解密谕言机(Oracle)。敌手获得目标密文后，希望获得目标密文对应的明文的部分信息。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分性(IND-CCA)IND游戏（称为IND-CCA游戏）如下：1初始化：挑战者产生系统ℰ，敌手A获得系统的公开钥。2训练：敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手。3挑战：敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文，其中随机值b∈{0,1}。4猜测：敌手输出b′，如果b′=b，则A成功。杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分