密码学中的可证明安全性-杨波-2014.11.11.pdf
《密码学中的可证明安全性-杨波-2014.11.11.pdf》由会员分享，可在线阅读，更多相关《密码学中的可证明安全性-杨波-2014.11.11.pdf（118页珍藏版）》请在冰点文库上搜索。
语义安全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。
挑战者随机选择b0,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。
挑战者随机选择b0,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。
挑战者随机选择b0,1，将mb加密，并将密文（称为目标密文）给敌手;3猜测：
敌手输出b，如果b=b,则敌手攻击成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择明文攻击下的不可区分性敌手的优势可定义为参数k的函数：
Adv,A（k）=|Prb=b12|其中k是安全参数，用来确定加密方案密钥的长度。
因为任一个不作为的敌手A，都能通过对b做随机猜测，而以12的概率赢得IND-CPA游戏。
而|Prb=b12|是敌手通过努力得到的，故称为敌手的优势。
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的生成元，随机选xZ*q,计算y=gxmodq.以x为秘密钥，（y,g,q）为公开钥。
2加密：
设消息mG,随机选一与p1互素的整数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,rRZq.变形：
做代换g1g,g2gx,u1gy,u2gxy,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（b0,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,C2），其中C2=C2m，解密询问后得到M=mm。
或者构造新的密文C=（C1,C2），其中C1=C1gk,C2=C2ykm，此时C1=gkgk=gk+k,C2=ykmykm=yk+kmm解密询问后仍得到M=mm。
再由Mmmodp，得到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的密文，其中随机值b0,1。
4猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分性（IND-CCA）IND游戏（称为IND-CCA游戏）如下：
1初始化：
挑战者产生系统，敌手A获得系统的公开钥。
2训练：
敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手。
3挑战：
敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文，其中随机值b0,1。
4猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分性（IND-CCA）IND游戏（称为IND-CCA游戏）如下：
1初始化：
挑战者产生系统，敌手A获得系统的公开钥。
2训练：
敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手。
3挑战：
敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文，其中随机值b0,1。
4猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分性以上攻击过程也称为“午餐时间攻击”或“午夜攻击”，相当于有一个执行解密运算的黑盒，掌握黑盒的人在午餐时间离开后，敌手能使用黑盒对自己选择的密文解密。
午餐过后，给敌手一个目标密文，敌手试图对目标密文解密，但不能再使用黑盒了。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分性第2步可以形象地看做是敌手发起攻击前，敌手对自己的训练（自学），这种训练可通过挑战者，也可通过解密谕言机。
谕言机也称为神谕、神使或传神谕者，神谕是古代希腊的一种迷信活动，由女祭祀代神传谕，解答疑难者的叩问，她们被认为是在传达神的旨意。
因为在IND-CCA游戏中，除了要求敌手是多项式时间的，我们不能对敌手的能力做如何限制，敌手除了自己有攻击IND-CCA游戏的能力外，可能还会借助于外力，这个外力是谁？
是他人还是神，我们不知道，所以统称为谕言机。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在选择密文攻击下的不可区分性敌手的优势可定义为参数k的函数：
AdvCCA,A（k）=|Prb=b12|Definition1.2如果对任何多项式时间的敌手A，存在一个可忽略的函数negl（k），使得AdvCCA,A（k）negl（k），那么就称这个加密算法在选择密文攻击下具有不可区分性，或者称为IND-CCA安全。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在适应性选择密文攻击下的不可区分性（IND-CCA2）1991年Rackoff和Simon提出了适应性选择密文攻击（AdaptiveChosenCiphertextAttack，简称为CCA2）的概念，其中敌手获得目标密文后，可以向网络中注入消息（可以和目标密文相关），然后通过和网络中的用户交互，获得与目标密文相应的明文的部分信息。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在适应性选择密文攻击下的不可区分性IND游戏（称为IND-CCA2游戏）如下：
1初始化：
挑战者产生系统，敌手获得系统的公开钥;2训练阶段1：
敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手;3挑战：
敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文cb，其中随机值b0,1;4训练阶段2：
敌手继续向挑战者（或解密谕言机）做解密询问（可多次），即取密文c（c=cb）给挑战者，挑战者解密后将明文给敌手;5猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在适应性选择密文攻击下的不可区分性IND游戏（称为IND-CCA2游戏）如下：
1初始化：
挑战者产生系统，敌手获得系统的公开钥;2训练阶段1：
敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手;3挑战：
敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文cb，其中随机值b0,1;4训练阶段2：
敌手继续向挑战者（或解密谕言机）做解密询问（可多次），即取密文c（c=cb）给挑战者，挑战者解密后将明文给敌手;5猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在适应性选择密文攻击下的不可区分性IND游戏（称为IND-CCA2游戏）如下：
1初始化：
挑战者产生系统，敌手获得系统的公开钥;2训练阶段1：
敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手;3挑战：
敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文cb，其中随机值b0,1;4训练阶段2：
敌手继续向挑战者（或解密谕言机）做解密询问（可多次），即取密文c（c=cb）给挑战者，挑战者解密后将明文给敌手;5猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在适应性选择密文攻击下的不可区分性IND游戏（称为IND-CCA2游戏）如下：
1初始化：
挑战者产生系统，敌手获得系统的公开钥;2训练阶段1：
敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手;3挑战：
敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文cb，其中随机值b0,1;4训练阶段2：
敌手继续向挑战者（或解密谕言机）做解密询问（可多次），即取密文c（c=cb）给挑战者，挑战者解密后将明文给敌手;5猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在适应性选择密文攻击下的不可区分性IND游戏（称为IND-CCA2游戏）如下：
1初始化：
挑战者产生系统，敌手获得系统的公开钥;2训练阶段1：
敌手向挑战者（或解密谕言机）做解密询问（可多次），即取密文c给挑战者，挑战者解密后，将明文给敌手;3挑战：
敌手输出两个长度相同的消息m0和m1，再从挑战者接收mb的密文cb，其中随机值b0,1;4训练阶段2：
敌手继续向挑战者（或解密谕言机）做解密询问（可多次），即取密文c（c=cb）给挑战者，挑战者解密后将明文给敌手;5猜测：
敌手输出b，如果b=b，则A成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约公钥加密方案在适应性选择密文攻击下的不可区分性敌手的优势可定义为参数k的函数：
AdvCCA2,A（k）=|Prb=b12|Definition1.3如果对任何多项式时间的敌手，存在一个可忽略的函数negl（k），使得AdvCCA2,A（k）negl（k），那么就称这个加密算法在适应性选择密文攻击下具有不可区分性，或者称为IND-CCA2安全。
在设计抗击主动敌手的密码协议时（如数字签名、认证、密钥交换、多方计算等），IND-CCA2安全的密码系统是有力的密码原语。
原语是指由若干条指令组成的，用于完成一定功能的一个过程。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约签名体制的语义安全性（EUF-CMA）签名体制=（KeyGen,Sign,Ver）一般由以下三个算法组成：
1密钥生成（KeyGen）：
该算法输入1k，输出密钥对（pk,sk）;2签名：
输入消息m，秘密钥sk，输出=Sign（m,sk）;3验证：
输入，消息m，公开钥pk，输出Ver（,m,pk）=T或。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约签名体制的语义安全性（EUF-CMA）签名体制=（KeyGen,Sign,Ver）一般由以下三个算法组成：
1密钥生成（KeyGen）：
该算法输入1k，输出密钥对（pk,sk）;2签名：
输入消息m，秘密钥sk，输出=Sign（m,sk）;3验证：
输入，消息m，公开钥pk，输出Ver（,m,pk）=T或。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约签名体制的语义安全性（EUF-CMA）签名体制=（KeyGen,Sign,Ver）一般由以下三个算法组成：
1密钥生成（KeyGen）：
该算法输入1k，输出密钥对（pk,sk）;2签名：
输入消息m，秘密钥sk，输出=Sign（m,sk）;3验证：
输入，消息m，公开钥pk，输出Ver（,m,pk）=T或。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约签名体制的语义安全性签名体制的语义安全性，由以下不可伪造（ExistentialUnforgeability）游戏（简称EUF游戏）来刻画。
1初始阶段：
挑战者产生系统的密钥对（pk,sk），敌手A获得系统的公开钥;2阶段1（签名询问）：
A执行以下的多项式有界次适应性询问;A提交mi，挑战者计算i=Sign（mi,sk）并返回给A;3输出：
A输出（m,），如果m不出现在阶段1且Ver（,m,pk）=T，则A攻击成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约签名体制的语义安全性签名体制的语义安全性，由以下不可伪造（ExistentialUnforgeability）游戏（简称EUF游戏）来刻画。
1初始阶段：
挑战者产生系统的密钥对（pk,sk），敌手A获得系统的公开钥;2阶段1（签名询问）：
A执行以下的多项式有界次适应性询问;A提交mi，挑战者计算i=Sign（mi,sk）并返回给A;3输出：
A输出（m,），如果m不出现在阶段1且Ver（,m,pk）=T，则A攻击成功。
杨波Cryptology语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约签名体制的语义安全性签名体制的语义安全性，由以下不可伪造（ExistentialUnforgeability）游戏（简称EUF游戏）来刻画。
1初始阶段：
挑战者产生系统的密钥对（pk,sk），敌手A获得系统的公开钥;2
升级会员 