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

语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案 密码学中的可证明安全性 杨波 陕西师范大学计算机学院 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案 目录 1 语义安全 IND-CPA IND-CCA IND-CCA2 EUF-CMA 规约 2 IBE的背景 3 IBE的安全性 双线性映射 BDH假设 4 选择明文安全的IBE方案 5 选择密文安全的IBE方案 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 单向加密–One way encryption 如果敌手已知某个密文， 不能得出所对应的明文的完 整信息， 该公钥加密方案称为单向加密（One way encryption， 简称OWE） ， 是一个很弱的安全概念， 因为不能 防止敌手得到明文的部分信息 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 语义安全 语义安全（Semantic scurity）的概念 由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规约 语义安全 思维实验(（thought experiment）)是用来考察某种假设、 理论或原理的结果而假设的一种实验， 这种实验可能在现 实中无法做到， 也可能在现实中没有必要去做思维实验和 科学实验一样， 都是从现实系统出发， 建立系统的模型， 然 后通过模型来模拟现实系统。

杨波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′] − 1 2| 其中k是安全参数， 用来确定加密方案密钥的长度因 为任一个不作为的敌手A， 都能通过对b做随机猜测， 而 以1 2的概率赢得IND-CPA游戏而|Pr[b = b ′] −1 2|是敌手通过 努力得到的， 故称为敌手的优势 Defi nition 1.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/cx 1modq. 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 例：ElGamal加密算法 安全性基于 Diffi e-Hellman判定性问题： 设G是阶为大素 数q的群，g1,g2为G的生成元。

没有多项式时间的算法区分 以下2个分布： 随机4元组R = (g1,g2,u1,u2) ∈ G4的分布； 4元组D = (g1,g2,u1,u2) ∈ G4的分布， 其 中u1= gr 1,u2 = gr 2,r ∈R Zq. 变形： 做代换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) = (gkmod p,ykmbmod p) 如果b = 0， 则 (C1,y,C2/m0) = (gkmod p,gxmod p,gkxmod p) 为 Diffi e-Hellman3元组。

如果b = 1， 则 (C1,y,C2/m1) = (gkmod p,gxmod p,gkxmod p) 为 Diffi e-Hellman3元组 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择明文攻击下的不可区分性 例：ElGamal加密算法 然而，IND CPA安全仅仅保证敌手是完全被动情况时 （即仅做监听）的安全， 不能保证敌手是主动情况时（例如 向网络中注入消息）的安全例如敌手收到密文 为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′ 再由 M m′ mod p， 得到C的 明文m。

可见，ElGamal加密算法不能抵抗主动攻击 杨波Cryptology 语义安全IBE的背景IBE的安全性选择明文安全的IBE方案选择密文安全的IBE方案IND-CPAIND-CCAIND-CCA2EUF-CMA规约 公钥加密方案在选择密文攻击下的不可区分性(IND-CCA) 为了描述敌手的主动攻击，1990年Naor和Yung提出了 （非适应性）选择密文攻击（Chosen Ciphertext Attack， 简称 为CCA）的概念， 其中敌手在获得。