【密码学】9. 可证明安全

可证明安全

语义安全的公钥密码体制的定义

1. 语义安全的核心概念
   语义安全指敌手无法通过密文获取明文的任何信息（即使 1 比特），由 Goldwasser 和 Micali 于 1984 年提出，通过不可区分性（IND）游戏刻画，即敌手无法区分两个明文对应的密文。
2. IND 游戏分类（基于敌手能力）
   • 选择明文攻击（IND-CPA）：
     • 游戏流程：挑战者生成密钥对，敌手可多项式次获取明文加密结果；敌手输出两个等长消息$M_0,M_1$，挑战者随机加密其中一个（目标密文）；敌手猜测加密的是$M_0$还是$M_1$。
     • 敌手优势：KaTeX parse error: Double superscript at position 31: …A}(λ) = |Pr[β'̲=β] - 1/2|，其中${\hat{I}}^2$是挑战者选择的比特，KaTeX parse error: Double superscript at position 3: β'̲是敌手猜测的比特。
     • 安全定义：若任何多项式时间敌手的优势可忽略，则方案是 IND-CPA 安全的。
   • 选择密文攻击（IND-CCA）：
     • 敌手在获得目标密文前，可多项式次询问解密谕言机（输入密文获取明文）；其余流程同 IND-CPA。
     • 安全定义：敌手优势可忽略则为 IND-CCA 安全。
   • 适应性选择密文攻击（IND-CCA2）：
     • 敌手在获得目标密文后，仍可询问解密谕言机（但不可询问目标密文）；其余流程同 IND-CCA。
     • 安全定义：敌手优势可忽略则为 IND-CCA2 安全（最强安全级别）。
3. 关键假设与问题
   • 离散对数问题（DLP）：给定群$G$的生成元$g$和$h\in G$，求$x$使得$h=g^x$，假设其在多项式时间内不可解。
   • 判定性 Diffie-Hellman（DDH）假设：区分$(g,g^a,g^b,g^{ab})$（DH 四元组）与$(g,g^a,g^b,g^c)$（随机四元组）在计算上不可行，其中$a,b,c$是随机数。
   • ElGamal 加密的 IND-CPA 安全性：在 DDH 假设下，ElGamal 加密方案是 IND-CPA 安全的（通过归约证明：若存在攻击 ElGamal 的敌手，则可构造攻击 DDH 的敌手）。

语义安全的 RSA 加密方案

1. RSA 问题与假设
   • RSA 问题：已知$n=pq$（大素数乘积）、$e$（满足$gcd(e,\ddot{I}†(n))=1$）和$y\in {\mathbb{Z}}_n^{\ast }$，求$x$使得$y=x^e\mathrm{mod}n$。
   • RSA 假设：RSA 问题在多项式时间内不可解。
2. 选择明文安全的 RSA 方案（RSA-CPA）
   • 构造：
     • 密钥生成：生成$n=pq$、$e,d$（$ed\equiv 1\mathrm{mod}\ddot{I}†(n)$），公钥$(n,e)$，私钥$d$。
     • 加密：对消息$M$，选随机数$r\in {\mathbb{Z}}_n^{\ast }$，计算$C=(r^e\mathrm{mod}n,H(r)\oplus M)$（$H$为哈希函数，视为随机谕言机）。
     • 解密：用$d$解出$r=(C_1{)}^d\mathrm{mod}n$，计算$H(r)\oplus C_2$得$M$。
   • 安全性：在随机谕言机模型下，若 RSA 问题困难，则 RSA-CPA 是 IND-CPA 安全的（归约证明：敌手攻击 RSA-CPA 可转化为攻击 RSA 问题）。
3. 选择密文安全的 RSA 方案（RSA-CCA）
   • 构造：结合 IND-CCA 安全的对称加密方案，加密为$C=(r^e\mathrm{mod}n,En{c}_{H(r)}(M))$，解密时验证哈希值后解密。
   • 安全性：在随机谕言机模型下，若 RSA 问题困难且对称加密是 IND-CCA 安全，则 RSA-CCA 是 IND-CCA 安全的。

Paillier 公钥密码系统

1. 基础：合数幂剩余类
   • 设$n=pq$（大素数），${\mathbb{Z}}_{n^2}^{\ast }$中元素$z$是$n$次剩余若存在$y$使得$z=y^n\mathrm{mod}{n}^2$。
   • 引理：$n$次剩余构成${\mathbb{Z}}_{n^2}^{\ast }$的子群，阶为$n\ddot{I}†(n)$；单位元 1 的$n$次根为$1+tn$（$t=0,1,...,n-1$）。
2. Paillier 系统构造
   • 密钥生成：选$p,q$，$n=pq$，私钥$\hat{I}»=lcm(p-1,q-1)$，公钥$n,g$（$g$是${\mathbb{Z}}_{n^2}^{\ast }$中满足$g^n\mathrm{mod}{n}^2$的阶为$n$的元素）。
   • 加密：对$M\in {\mathbb{Z}}_n$，选$r\in {\mathbb{Z}}_n^{\ast }$，计算$C=g^M\cdot r^n\mathrm{mod}{n}^2$。
   • 解密：计算$L(C^{\hat{I}}»\mathrm{mod}{n}^2)\cdot \hat{I}¼\mathrm{mod}n$，其中$L(x)=(x-1)/n$，$\hat{I}¼=(L(g^{\hat{I}}»\mathrm{mod}{n}^2){)}^{-1}\mathrm{mod}n$。
3. 安全性：基于合数幂剩余判定问题，在标准模型下可证明 IND-CPA 安全（不依赖随机谕言机）。

Cramer-Shoup 密码系统

1. 核心机制：结合 ElGamal 加密与哈希验证，实现 IND-CCA2 安全。
   • 密钥生成：选群$G$（阶为素数$q$）、生成元$g_1,g_2$，私钥$x_1,x_2,y_1,y_2,z_1,z_2$，公钥$c=g_1^{x_1}{g}_2^{x_2}$，$d=g_1^{y_1}{g}_2^{y_2}$，$h=g_1^{z_1}{g}_2^{z_2}$。
   • 加密：对$M$，选$r\in {\mathbb{Z}}_q$，计算$u_1=g_1^r$，$u_2=g_2^r$，$e=M\cdot h^r$，$\hat{I}\pm =H(u_1,u_2,e)$，$v=c^r\cdot d^{r\hat{I}\pm }$，密文$(u_1,u_2,e,v)$。
   • 解密：验证$v=u_1^{x_1+y_1\hat{I}\pm }\cdot u_2^{x_2+y_2\hat{I}\pm }$，通过则计算$M=e\cdot (u_1^{z_1}{u}_2^{z_2}{)}^{-r}$。
2. 安全性：在 DDH 假设和哈希函数防碰撞性下，是 IND-CCA2 安全的（归约证明：敌手攻击可转化为攻击 DDH 问题）。

RSA-FDH 签名方案

1. RSA 签名的缺陷：标准 RSA 签名不满足 EUF-CMA 安全（敌手可伪造签名）。
2. FDH 改进：使用全域哈希函数（FDH），将消息哈希后再签名。
   • 密钥生成：同 RSA 加密，公钥$(n,e)$，私钥$d$。
   • 签名：对消息$M$，计算$\ddot{I}ƒ=H(M{)}^d\mathrm{mod}n$（$H$输出与$n$同长）。
   • 验证：检查$\ddot{I}{ƒ}^e\mathrm{mod}n=H(M)$。
3. 安全性：在随机谕言机模型下，若 RSA 问题困难，则 RSA-FDH 是 EUF-CMA 安全的（归约证明：敌手伪造签名可转化为解决 RSA 问题）。
   • 改进：定理 9-12 给出更紧的归约，优势为$Ad{v}_B^{RSA}\ge (Ad{v}_A^{EUF-CMA}{)}^2/(4q_H)$（$q_H$为哈希询问次数）。

BLS 短签名方案

1. 基础：双线性映射与间隙群
   • 双线性映射：$e:G_1\times G_1\to G_2$，满足$e(g^a,g^b)=e(g,g{)}^{ab}$。
   • 间隙群：DDH 问题易解但 CDH 问题难解的群（如超奇异椭圆曲线点群）。
2. BLS 方案构造
   • 密钥生成：选间隙群$G_1$（生成元$g$），私钥$x\in {\mathbb{Z}}_q$，公钥$y=g^x$。
   • 签名：对$M$，计算$\ddot{I}ƒ=H(M{)}^x\in G_1$（$H$为全域哈希）。
   • 验证：检查$e(\ddot{I}ƒ,g)=e(H(M),y)$。
3. 安全性：在随机谕言机模型下，若间隙群上 CDH 问题困难，则 BLS 是 EUF-CMA 安全的。
   • 改进：使用第二类双线性映射（$e:G_1\times G_2\to G_T$），签名长度可缩短至 168 比特（椭圆曲线实现）。

基于身份的密码体制（IBE）

1. 核心思想：以用户身份（如邮箱）作为公钥，无需证书，简化 PKI 管理。
2. IBE 的四个算法
   • 初始化：生成系统参数$params$和主密钥$msk$。
   • 加密：用接收方身份$ID$加密消息$M$，得密文$C$。
   • 密钥生成：用$msk$和$ID$生成对应私钥$d_{ID}$。
   • 解密：用$d_{ID}$解密密文$C$得$M$。
3. Boneh-Franklin（BF）方案
   • 基于 BDH 问题（双线性 Diffie-Hellman 问题）：给定$g,g^a,g^b,g^c$，计算$e(g,g{)}^{abc}$。
   • 安全性：在随机谕言机模型下，BF 方案是 IND-ID-CPA 安全的（归约到 BDH 问题）。
4. 安全模型
   • IND-ID-CPA：敌手可询问多个身份的私钥，挑战时无法区分两个消息的加密结果。
   • IND-ID-CCA：敌手可询问解密谕言机（除挑战身份），安全性更强。

分叉引理

1. 适用场景：需多个相关伪造签名破解困难问题的方案（如 ElGamal、Fiat-Shamir 签名）。
2. 引理内容：若敌手以优势$\hat{I}\mu$输出一个有效签名$(m,\ddot{I}{ƒ}_1,h,\ddot{I}{ƒ}_2)$，且最多进行$q_H$次哈希询问，则存在概率至少$\hat{I}\mu (\hat{I}\mu -2/q_H)$输出两个签名$(m,\ddot{I}{ƒ}_1,h,\ddot{I}{ƒ}_2)$和$(m,\ddot{I}{ƒ}_1,h^{\prime },\ddot{I}{ƒ}_2^{\prime })$（$h\ne h^{\prime }$）。
3. 应用
   • ElGamal 签名：基于分叉引理，若离散对数问题困难，则 ElGamal 是 EUF-CMA 安全的。
   • Fiat-Shamir 签名：基于分叉引理，若大整数分解问题困难，则 Fiat-Shamir 是 EUF-CMA 安全的。