Introduction to Modern Cryptography Reading Notes
3 Private-Key Encryption
具体安全和渐进安全
安全有两种定义，具体的(concrete)和渐进的(asymasymptotic)。简单地说，具体安全依靠具体的数值，而渐进安全依靠关于 \(n\) 的函数。
对于具体安全的定义
A scheme is \((t, \varepsilon)\)-secure if any adversary running for time at most \(t\) succeeds in breaking the scheme with probability at most \(\varepsilon\).
在实际运用密码系统时往往需要一个具体的安全保障。
我们将 efficient adversaries 视为多项式时间随机算法(randomized algorithms running in time polynomial in \(n\))；将 small probabilities of success 视为不大于某一多项式的倒数(success probabilities smaller than any inverse polynomial in \(n\))，这样的概率成为可忽略的(negligible)。
PPT 表示 probabilistic polynomial-time。
对渐进安全进行定义：
A scheme is secure if any PPT adversary succeeds in breaking the scheme with at most negligible probability.
通过对参数进行取值，可以由渐进安全得到具体安全。
密钥加密及其安全定义
private-key encryption 的定义：
A private-key encryption scheme consists of three probabilistic polynomial-time algorithms (Gen, Enc, Dec) such that:
- The key-generation algorithm Gen takes as input \(1^n\) (i.e., the security parameter written in unary) and outputs a key \(k\); we write \(k \leftarrow \mathrm{Gen}(1^n)\) (emphasizing that Gen is a randomized algorithm). We assume without loss of generality that any key \(k\) output by \(\mathrm{Gen}(1^n)\) satisfies \(|k| \geq n\).
- The encryption algorithm Enc takes as input a key \(k\) and a plaintext message \(m \in \{0, 1\}^*\), and outputs a ciphertext \(c\). Since Enc may be randomized, we write this as \(c \leftarrow \mathrm{Enc}_k(m)\).
- The decryption algorithm Dec takes as input a key \(k\) and a ciphertext \(c\), and outputs a message \(m \in \{0, 1\}^*\) or an error. We denote a generic error by the symbol \(\perp\).
上面的定义是无记忆的(stateless)，即每次 Enc 都与之前的 Enc 无关。
攻击者无法区分试验 The adversarial indistinguishability experiment \(\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Sigma}(n)\)，给定明文 \(m_0,m_1\) 和密文 \(c\)，攻击者无法辨别 \(c\) 是由 \(m_0\) 还是 \(m_1\) 加密而来的。定义如下：
- The adversary \(\mathcal A\) is given input \(1^n\), and outputs a pair of messages \(m_0, m_1\) with \(|m_0| = |m_1|\).
- A key \(k\) is generated by running \(\mathrm{Gen}(1^n)\), and a uniform bit \(b \in \{0, 1\}\) is chosen. Ciphertext \(c \leftarrow \mathrm{Enc}_k(m_b)\) is computed and given to \(\mathcal A\). We refer to \(c\) as the challenge ciphertext.
- \(\mathcal A\) outputs a bit \(b'\).
- The output of the experiment is defined to be \(1\) if \(b'=b\), and \(0\) otherwise. If \(\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Sigma}(n)=1\), we say that \(\mathcal A\) succeeds.
攻击者无法以超过 \(\frac12+\mathrm{negl}(n)\) 的概率通过试验，这种性质称为不可分辨(indistinguishability)。
A private-key encryption scheme \(\Sigma = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})\) has indistinguishable encryptions in the presence of an eavesdropper, or is EAV-secure, if for all probabilistic polynomial-time adversaries \(\mathcal A\) there is a negligible function \(\mathrm{negl}\) such that, for all \(n\), \[\mathrm{Pr}[\mathrm{PrivK}^{\mathrm{eav}}_{\mathcal A,\Sigma}(n)=1]\leq \frac12+\mathrm{negl}(n)\]
一个等价的定义是，当给攻击者的密文是 \(\mathrm{Enc}(m_0)\) 或 \(\mathrm{Enc}(m_1)\) 时，行为相同（\(|\mathrm{Pr}[\mathrm{Output_0}=1]-\mathrm{Pr}[\mathrm{Output_1}=1]|\leq\mathrm{negl}(n)\)）。
接下来书上由indistinguishability推出两个较弱的结论。懒得抄了。
语义安全(semantic security)的定义
A private-key encryption scheme \((\text{Enc}, \text{Dec})\) is semantically secure in the presence of an eavesdropper if for every PPT algorithm \(\mathcal{A}\) there exists a PPT algorithm \(\mathcal{A}'\) such that for any PPT algorithm \(\mathrm{Samp}\) and polynomial-time computable functions \(f\) and \(h\), the following is negligible: \[|\text{Pr}[\mathcal{A}(1^n,\text{Enc}_k(m),h(m))=f(m)]-\text{Pr}[\mathcal{A}'(1^n,|m|,h(m))=f(m)]|\], where the first probability is taken over \(m\) output by \(\mathrm{Samp}(1^n)\), uniform choice of \(k \in \{0, 1\}^n\), and the randomness of Enc and \(\mathcal A\), and the second probability is taken over \(m\) output by \(\mathrm{Samp}(1^n)\) and the randomness of \(\mathcal A'\).
直观地说，这个定义描述了 \(\mathrm{Enc}_k(m)\) 不表露 \(|m|\) 以外的任何信息。
semantic secure 和 indistinguishability(EAV-secure) 是等价的。
伪随机
伪随机(pseudorandom)是真随机的一个 computational relaxation，即弱化了一些条件的真随机。
伪随机的定义：
Let \(\mathcal G\) be a deterministic polynomial-time algorithm such that for any \(n\) and any input \(s \in \{0, 1\}^n\), the result \(\mathcal G(s)\) is a string of length \(\mathcal l(n)\). \(\mathcal G\) is a pseudorandom generator if the following conditions hold:
- (Expansion.) For every \(n\) it holds that \(\mathcal l(n) > n\).
- (Pseudorandomness.) For any PPT algorithm \(\mathcal D\), there is a negligible function \(\mathrm{negl}\) such that \[|\mathrm{Pr}[\mathcal D(\mathcal G(s)) = 1] − \mathrm{Pr}[\mathcal D(r) = 1]| \leq \mathrm{negl}(n)\], where the first probability is taken over uniform choice of \(s \in \{0, 1\}^n\) and the randomness of \(\mathcal D\), and the second probability is taken over uniform choice of \(r \in \{0, 1\}^{\mathcal l(n)}\) and the randomness of \(\mathcal D\).
称 \(\mathcal l(n)\) 为 \(\mathcal G\) 的扩张因子(expansion factor)。
我们有比较强的理由相信，对于任意多项式扩张因子，都存在伪随机算法。（应该理解为，当 \(n\) 大于某个足够大的数 \(N\) 时，都有满足条件的伪随机算法）
多次加密
之前只讨论了窃听者只窃听到一个密文的情况，接下来考虑 Multiple Encryption，即需要多次传输密文的情况。
The multiple-message eavesdropping experiment \(\mathrm{PrivK}^{\mathrm{mult}}_{\mathcal A,\Pi(n)}\):
- The adversary \(\mathcal A\) is given input \(1^n\), and outputs a pair of equal-length lists of messages \(\overline{M_0}=(m_{0,1},...,m_{0,t})\) and \(\overline{M_1} = (m_{1,1},..., m_{1,t})\), with \(|m_{0,i}|=|m_{1,i}|\) for all \(i\).
- A key \(k\) is generated by running \(\mathrm{Gen}(1^n)\), and a uniform bit \(b \in \{0, 1\}\) is chosen. For all \(i\), the ciphertext \(c_i \leftarrow \mathrm{Enc}_k(m_{b,i})\) is computed and the list \(\overline C = (c_1, . . . , c_t)\) is given to \(\mathcal A\).
- \(\mathcal A\) outputs a bit \(b'\).
- The output of the experiment is defined to be \(1\) if \(b' = b\), and \(0\) otherwise.
注意每次加密使用的key都是一样的。
indistinguishablity 的定义和上面差不多。
选择密文攻击CPA
如果 Enc 是关于 \(k\) 和 \(m\) 的确定函数，那么将无法实现 indistinguishablity。因此我们必须让加密函数随机化。
在chosen-plaintext attack中，敌手可以通过一些方式影响被加密的明文。
对于chosen-plaintext attack，有对应的 CPA-security，它允许敌手可以随时以黑盒的方式调用 \(\mathrm{Enc}_k\) 函数。
The CPA indistinguishability experiment \(\mathrm{PrivK}^{\mathrm{cpa}}_{\mathcal A,\Pi(n)}\):
- A key \(k\) is generated by running \(\mathrm{Gen}(1^n)\).
- The adversary \(\mathcal A\) is given input \(1^n\) and oracle(黑盒) access to \(\mathrm{Enc}_k(\cdot)\), and outputs a pair of messages \(m_0, m_1\) of the same length.
- A uniform bit \(b \in \{0, 1\}\) is chosen, and then a ciphertext \(c \leftarrow \mathrm{Enc}_k(m_b)\) is computed and given to \(\mathcal A\).
- The adversary \(\mathcal A\) continues to have oracle access to \(\mathrm{Enc}_k(\cdot)\), and outputs a bit \(b'\).
- The output of the experiment is defined to be \(1\) if \(b' = b\), and \(0\) otherwise. In the former case, we say that \(\mathcal A\) succeeds.
此时 \(\mathrm{Enc}\) 通常不是一个确定性函数，否则将可以通过将 \(c\) 与 \(\text{Enc}(m_0)\) 和 \(\text{Enc}(m_1)\) 对比的方式来区分。
A private-key encryption scheme \(\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})\) has indistinguishable encryptions under a chosen-plaintext attack, or is CPA-secure, if for all probabilistic polynomial-time adversaries \(\mathcal A\) there is a negligible function \(\mathrm{negl}\) such that \[\mathrm{Pr}[\mathrm{PrivK}^{\mathrm{cpa}}_{\mathcal A,\Pi(n)}=1]\leq\frac12+\mathrm{negl}(n)\] where the probability is taken over the randomness used by \(\mathcal A\), as well as the randomness used in the experiment.
CPA-security 是当今加密系统需要满足的最小的安全要求。
我们将使用LR 函数(left-or-right)来定义允许多次加密的安全要求。\(\mathrm{LR}_{k,b}\) 是一个黑盒函数，接收两个相同长度的明文 \(m_0,m_1\)，返回 \(\mathrm{Enc}_k(m_b)\)。可以通过 LR 函数定义 LR-oracle experiment。
The LR-oracle experiment \(\mathrm{PrivK}^{\mathrm{LR-cpa}}_{\mathcal A,\Pi(n)}\):
- A key \(k\) is generated by running \(\mathrm{Gen}(1^n)\).
- A uniform bit \(b \in \{0, 1\}\) is chosen.
- The adversary \(\mathcal A\) is given input \(1^n\) and oracle access to \(\mathrm{LR}_{k,b}(\cdot, \cdot)\),as defined above.
- The adversary \(\mathcal A\) outputs a bit \(b'\).
- The output of the experiment is defined to be \(1\) if \(b' = b\), and \(0\) otherwise. In the former case, we say that \(\mathcal A\) succeeds.
可以通过 LR-oracle experiment 定义 indistinguishable multiple encryptions under a chosen-plaintext attack，或者叫 CPA-secure for multiple encryptions，和上面差不多就不抄了。
注意到 CPA-secure for multiple encryptions 比 CPA-secure 和 indistinguishable multiple encryptions in the presence of an eavesdropper 都要强。它和后者的区别是，CPA-secure for multiple encryptions 是支持在测试的任何阶段在线访问的。
事实上，CPA-secure 和 CPA-secure for multiple encryptions 是等价的，要证明这一点，只需要证明满足CPA-secure的加密系统也满足CPA-secure for multiple encryptions：
Any private-key encryption scheme that is CPA-secure is also CPA-secure for multiple encryptions.
伪随机函数
伪随机函数(pseudorandom function)的定义:
An efficient, length preserving, keyed function \(F:\{0, 1\}^*\times\{0, 1\}^*\to\{0, 1\}^*\) is a pseudorandom function if for all probabilistic polynomial-time distinguishers \(D\), there is a negligible function \(\text{negl}\) such that: \[\left|\text{Pr}[D^{F_k(\cdot)}(1^n) = 1] − \text{Pr}[D^{f(\cdot)}(1^n) = 1]\right| \leq \text{negl}(n)\], where the first probability is taken over uniform choice of \(k \in \{0, 1\}^n\) and the randomness of \(D\), and the second probability is taken over uniform choice of \(f \in \text{Func}_n\) and the randomness of \(D\).
其中 \(\text{Func}_n\) 表示 \(\{0,1\}^*\to\{0,1\}^*\) 的全体函数，\(F_k:=F(\cdot,k)\)。注意 \(D\) 并不知道 \(k\) 的值，只能黑盒(oracle)访问 \(F_k\)。
\(\text{Perm}_n \subset \text{Func}_n\) 表示 \(\text{Func}_n\) 中的 permutations (双射函数)。若对于任意 \(k\in\{0,1\}^{l_{key}(n)}\), 都满足 \(F_k\) 是双射函数，则称 \(F\) 是一个 keyed permutation。当 \(F\) 满足能被高效计算和能被高效求逆（给出 \(k\) 和 \(y\),在多项式时间内计算 \(x\)），才能被称为是高效的(efficient)。
random function 和 random permutation 是多项式时间不可区分的，因此如果pseudorandom permutation \(F\) 满足 \(l_{in}(n)\geq n\)，那么 \(F\) 也是 pseudorandom function。
strong pseudorandom permutation 要求在攻击者知道伪随机排列的逆（黑盒调用）的情况下，仍然不能区分伪随机排列和随机排列。
Let \(F : \{0, 1\}^∗ \times \{0, 1\}^∗ \to \{0, 1\}^∗\) be an efficient,length preserving, keyed permutation. \(F\) is a strong pseudorandom permutation if for all probabilistic polynomial-time distinguishers \(D\), there exists a negligible function \(\text{negl}\) such that: \[\left|\text{Pr}[D^{F_k(\cdot),F_k^{-1}(\cdot)}(1^n) = 1] − \text{Pr}[D^{f(\cdot),f^{-1}(\cdot)}(1^n) = 1]\right| \leq \text{negl}(n)\], where the first probability is taken over uniform choice of \(k \in \{0, 1\}^n\) and the randomness of \(D\), and the second probability is taken over uniform choice of \(f \in \text{Perm}_n\) and the randomness of \(D\).
通过伪随机函数，可以构造 CPA-secure 的加密方法
Let \(F\) be a pseudorandom function. Define a fixed-length, private-key encryption scheme for messages of length \(n\) as follows:
- \(\text{Gen}\): on input \(1^n\), choose uniform \(k \in \{0, 1\}^n\) and output it.
- \(\text{Enc}\): on input a key \(k \in \{0, 1\}^n\) and a message \(m \in \{0, 1\}^n\), choose uniform \(r \in \{0, 1\}^n\) and output the ciphertext \[c := \langle r, F_{k}(r) \oplus m\rangle\]
- \(\text{Dec}\): on input a key \(k \in \{0, 1\}^n\) and a ciphertext \(c = \langle r, s\rangle\) , output the message \[m := F_{k}(r) \oplus s\]
证明过程大概就是先通过反证法证明当 \(F\) 替换为真随机函数时，\(\mathcal A\) 的行为和替换前差不多；然后证明当 \(F\) 替换为真随机函数时，\(\mathcal A\) 无法通过 CPA 不可区分测试。
流密码
可以使用流密码(stream ciphers)技术来解决 pseudorandom generator 生成的伪随机数长度不够或者浪费的问题。
Formally, a stream cipher is a pair of deterministic algorithms \((\text{Init}, \text{Next})\) where:
- \(\text{Init}\) takes as input a seed \(s\) and an optional initialization vector \(IV\) , and outputs some initial state \(\text{st}\).
- \(\text{Next}\) takes as input a current state \(\text{st}\) and outputs a bit \(y\) along with updated state \(\text{st}'\) .
定义函数 \(\text{GetBits}\)，输入 \(\text{st}_0\) 和 \(1^{\ell}\)，
- 从 \(i=1\) 到 \(n\)，计算 \((y_i,\text{st}_i) := \text{Next}(\text{st}_{i−1})\)
- 返回 \(\ell\)-bit 串 \(y = y_1 \cdots y_{\ell}\) 和最终状态 \(\text{st}_{\ell}\)
Let \(F\) be a pseudorandom function. Define a stream cipher \((\text{Init}, \text{Next})\) as follows, where \(\text{Init}\) accepts a \(3n/4\)-bit initialization vector and \(\text{Next}\) outputs \(n\) bits in each call:
- \(\text{Init}\): on input \(s \in \{0, 1\}^n\) and \(IV \in \{0, 1\}^{3n/4}\), output \(\text{st} =(s, IV, 0)\).
- \(\text{Next}\): on input \(\text{st} = (s, IV, i)\), output \(y := F_s(IV || \langle i\rangle )\) and updated state \(\text{st}' = (s, IV, i + 1)\).
使用流密码加密任意长度的明文，分为两种模式：同步模式(synchronized mode)和异步模式(unsynchronized mode)
同步模式用来加密一系列从发送者 \(S\) 到接收者 \(R\) 的消息。
- Both parties call \(\text{Init}(k)\) to obtain the same initial state \(\text{st}_0\).
- Let \(\text{st}_S\) be the current state of \(S\). If \(S\) wants to encrypt a message \(m\), it computes \((y,\text{st}'_S):=\text{GetBits}(\text{st}_S, 1^{|m|})\), sends \(c:=m\oplus y\) to the receiver,and updates its local state to \(st_S'\).
- Let \(\text{st}_R\) be the current state of \(R\). When \(R\) receives a ciphertext \(c\) from the sender, it computes \((y,\text{st}'_R):=\text{GetBits}(\text{st}_R, 1^{|c|})\), outputs the message \(m:=c\oplus y\), and updates its own local state to \(\text{st}'_R\).
通过共享两个 key 可以实现双向通信。这种模式没有使用 \(IV\) 向量。
在异步模式，流密码使用 \(IV\) 向量，可以构造stateless encryption scheme。主要优势是可以处理任意长度的消息。
Let \((\text{Init}, \text{Next})\) be a stream cipher that takes an \(n\)-bit \(IV\) . Define a private-key encryption scheme for arbitrary-length messages as follows:
- \(\text{Gen}\): on input \(1^n\), choose a uniform \(k\in\{0, 1\}^n\) and output it.
- \(\text{Enc}\): on input a key \(k\in \{0, 1\}^n\) and a message \(m\in\{0, 1\}^∗\), choose uniform \(IV \in \{0, 1\}^n\), and output the ciphertext \[\langle IV, \text{GetBits}_1(\text{Init}(k, IV ), 1^{|m|}) \oplus m\rangle\]
- \(\text{Dec}\): on input a key \(k\in \{0, 1\}^n\) and a ciphertext \(\langle IV, c\rangle\), output the message \[m := \text{GetBits}_1(\text{Init}(k, IV ), 1^{|c|}) \oplus c\]
分组密码
block cipher 其实就是(强)伪随机排列的另一个名字，但是 block cipher 不支持任意长度的 key。
这里假设 \(m\) 的长度是 \(n\) 的倍数，\(m=m_1m_2...m_{\ell}\), 其中 \(m_i\in\{0,1\}^n\)。
Electronic Code Book (ECB) mode \[c=F_k(m_1)F_k(m_2)...F_k(m_{\ell})\] 但是它甚至不是 EAV-secure 的，因此不应该使用这种模式。
Cipher Block Chaining (CBC) mode \[c_0=IV,c_i=F_k(c_{i-1}\oplus m_i)\] \(IV\) 是初始向量。可以证明，当 \(F\) 是伪随机函数时，它是 CPA-secure 的。
chained CBC 是 CBC 的一个有记忆(stateful)变种，它将上次传递的最后一块密文作为这次加密的 \(IV\) 向量，这样就不用每次都传递 \(IV\) 向量了。但是 chained CBC 并不是 CPA-secure 的。
Output Feedback (OFB) mode \[y_0=IV,y_i=F_k(y_{i-1}),c_i=m_i\oplus y_i\] 和 \(CBC\) 一样，需要将 \(IV\) 作为密文的一部分以供解密。OFB 不要求 \(F\) 可逆。它的有记忆版本是安全的。
Counter (CTR) mode
(未完待续)