公钥密码概述

什么是公钥密码？ (What is Public Key Cryptography?) 🔗

用于加密的密钥与用于解密的密钥不同。

常见方案有RSA、ElGamal和NTRU等。

优点：便于共享密钥，需要的密钥数量较少。

缺点：比对称密钥加密慢。

定义：公钥加密方案PKE由以下算法构成。

正确性

对于安全参数λ和所有明文M，如果以下等式成立，就称公钥加密方案PKE是正确的。

👨‍💻

Dec(sk, Enc(pk, M)) = M

其中，(pk, sk)是KeyGen(λ)的输出。

考虑挑战者C与攻击者A之间的一场游戏。

A的目标是破解公钥加密，也就是从密文中找到明文M。

Setup：挑战者C输入安全参数λ，输出(pk, sk)。

然后将其中的公钥pk交给A。
Phase1：A向C发送解密查询请求。

也就是说，A将任意密文 $C_i$ 发送给C，C返回 $Dec(sk, C_i) = M_i$ 。
Challenge：A选择两个明文 $M_0, M_1$ ，C从中选一个（ $b \in \{1, 2\}$ ），并返回 $Enc(pk, M_b) = C_b$ 。

此时，A猜测 $b$ ，判断密文对应的是哪一个明文。
Phase2：A向C发送解密查询请求。

也就是说，A将任意密文 $C_i$ 发送给C，C返回 $Dec(sk, C_i) = M_i$ 。

Adv_{PKE}(\lambda) = Pr[b = b'] - \frac{1}{2}

👍

如果攻击者无法在安全参数下获得不可忽略的优势，则称该公钥加密方案具有IND-XXX安全性。

XXX由攻击者可以访问的解密预言机决定。