Introduction to Modern Cryptography Reading Notes

12 Public-Key Encryption

定义

A public-key encryption scheme is a triple of probabilistic polynomial-time algorithms \((\text{Gen}, \text{Enc}, \text{Dec})\) such that:

1. The key-generation algorithm \(\text{Gen}\) takes as input the security parameter \(1^n\) and outputs a pair of keys \((pk, sk)\). We refer to the first of these as the public key and the second as the private key. We assume for convenience that \(pk\) and \(sk\) each has length at least \(n\), and that \(n\) can be determined from \(pk\), \(sk\). The public key \(pk\) defines a message space \(\mathcal{M}_{pk}\).
2. The encryption algorithm \(\text{Enc}\) takes as input a public key \(pk\) and message \(m\in \mathcal{M}_{pk}\), and outputs a ciphertext \(c\); we denote this by \(c \leftarrow \text{Enc}_{pk}(m)\). (Looking ahead, \(\text{Enc}\) will need to be probabilistic in order to achieve meaningful security.)
3. The deterministic decryption algorithm \(\text{Dec}\) takes as input a private key \(sk\) and a ciphertext \(c\), and outputs a message \(m\) or a special symbol \(\perp\) denoting failure. We write this as \(m:=\text{Dec}_{sk}(c)\).

It is required that, except with negligible probability over the randomness of \(\text{Gen}\) and \(\text{Enc}\), we have \(\text{Dec}_{sk}(\text{Enc}_{pk}(m))=m\) for any message \(m\in \mathcal{M}_{pk}\).

下面定义与之对应的安全测试

The eavesdropping indistinguishability experiment \(\text{PubK}^{\text{eav}}_{\mathcal{A},\Pi(n)}\):

1. \(\text{Gen}(1^n)\) is run to obtain keys \((pk, sk)\).
2. Adversary \(\mathcal{A}\) is given \(pk\), and outputs a pair of equal-length messages \(m_0, m_1\in \mathcal{M}_{pk}\).
3. A uniform bit \(b\in \{0, 1\}\) is chosen, and then a ciphertext \(c \leftarrow \text{Enc}_{pk}(m_b)\) is computed and given to \(\mathcal{A}\). We call \(c\) the challenge ciphertext.
4. \(\mathcal{A}\) outputs a bit \(b'\). The output of the experiment is \(1\) if \(b' = b\), and \(0\) otherwise. If \(b' = b\) we say that \(\mathcal{A}\) succeeds.

还有安全定义

A public-key encryption scheme \(\Pi=(\text{Gen}, \text{Enc}, \text{Dec})\) has indistinguishable encryptions in the presence of an eavesdropper if for all probabilistic polynomial-time adversaries \(\mathcal{A}\) there is a negligible function \(\text{negl}\) such that \[\text{Pr}[\text{PubK}^{\text{eav}}_{\mathcal{A},\Pi(n)}=1]\leq \frac12+\text{negl}(n)\]

它是等价于于 CPA-secure 的。

接下来考虑到我们需要使用一个公钥进行多次加密

Introduction to Modern Cryptography Reading Notes

11 Key Management and the Public-Key Revolution

密钥分发和密钥管理

密钥加密主要会遇到三个问题

• key distribution
• storing and managing large numbers of secret keys
• inapplicability of private-key cryptography to open systems

密钥分发中心 KDC

密钥分发中心通常是一个可信的第三方。一种做法是，当新加入一个成员时，分发他与其他所有成员之间的密钥。

online 可能是更好的做法，当 \(A\) 需要和 \(B\) 通信时，向 KDC 发送请求，KDC 像 \(A\) 和 \(B\) 发送一个 session key（分别使用 \(k_A\) 和 \(k_B\) 加密），然后 \(A\) 和 \(B\) 通过 session key 交流。

Needham–Schroeder protocol \(A\) 发出请求后，KDC 把 \(\text{Enc}_{k_A}(k_{session})\) 和 \(\text{Enc}_{k_B}(k_{session})\) 发送给 \(A\)，\(A\) 将后者发送给 \(B\)。一般将 \(\text{Enc}_{k_B}(k_{session})\) 称为 ticket。

密钥交换和 Diffie-Hellman Protocol

Introduction to Modern Cryptography Reading Notes

10 *Algorithms for Factoring and Computing Discrete Logarithms

(skip)

Introduction to Modern Cryptography Reading Notes

9 Number Theory and Cryptographic Hardness Assumptions

关于群论的部分全部跳过。

离散对数问题和 CDH/DDH

用 \(\mathcal G\) 表示一个通用的、多项式时间的群生成算法，输入 \(1^n\)，输出一个阶为 \(q\)（其中 \(||q||=n\)） 的循环群 \(\mathbb G\) 的描述（description）和它的一个生成元 \(g\)。它将 \(\mathbb G\) 的每个元素都表示为一个比特串，并且要求存在多项式时间算法，能够验证一个任意比特串是否对应着 \(\mathbb G\) 中的一个元素，能执行群运算（我的理解是，输入两个对应着 \(g_1,g_2\in\mathbb G\) 的比特串，能计算 \(g_1\circ g_2\) 对应的比特串）。虽然所有阶为 \(q\) 的循环群都是同构的，但是不同的描述可能会导致不同的计算复杂度。

对于 \(g\in\mathbb G\)，存在一个唯一的 \(x\in\mathbb{Z}_q\) 使得 \(g^x=h\)，称 \(x\) 是 \(h\) 关于 \(g\) 的离散对数（discrete logarithm）。注意如果 \(g^{x'}=h\)，那么 \(\log_gh=[x'\mod q]\)。

我们和之前一样用测试的方式定义离散对数问题（discrete-logarithm problem）

The discrete-logarithm experiment \(\text{DLog}_{\mathcal{A},\mathcal G(n)}\):

1. Run \(\mathcal G(1^n)\) to obtain \((\mathbb G, q, g)\), where \(\mathbb G\) is a cyclic group of order \(q\) (with \(|q|=n\)), and \(g\) is a generator of \(\mathbb G\).
2. Choose a uniform \(h\in\mathbb G\).
3. \(\mathcal{A}\) is given \(\mathbb G, q, g, h\), and outputs \(x\in\mathbb{Z}_q\).
4. The output of the experiment is defined to be \(1\) if \(g^x=h\), and \(0\) otherwise.

根据上下文，书中的 \(\mathcal G\) 是一个随机算法。如果 \(\mathcal G\) 是确定性的，或者 \(\mathcal G\) 的随机性被 \(\mathcal{A}\) 所知，会发生什么事，我还没有想清楚。

如果对于任意的 PPT 算法 \(\mathcal{A}\)，都有 \(\text{Pr}[\text{DLog}_{\mathcal{A},\mathcal G(n)}=1]\leq\text{negl}(n)\)，则称离散对数问题是难的（relative to \(\mathcal G\)）。而离散对数假设就是存在一个 \(\mathcal G\) 使得离散对数问题是难的。

Introduction to Modern Cryptography Reading Notes

8 *Theoretical Constructions of Symmetric-Key Primitives

这章标了*，先跳过（

Introduction to Modern Cryptography Reading Notes

7 Practical Constructions of Symmetric-Key Primitives

流密码

Linear-Feedback Shift Registers(LFSR)

\(y_i=s_i^{(0)},i=0,...,n-1\)

\(y_i=\oplus_{j=0}^{n-1}c_jy_{i-n+j},i>n-1\)

\(n\) 称为 LFSR 的度数。

知道 \(2n\) 个输出后，可以得到 \(n\) 个方程（如果是max length的，这 \(n\) 个方程是独立的），然后可以解出所有系数 \(c\) 的值。

可以通过引入一些非线性函数（比如 AND 和 OR）来避免这种攻击，称为 FSR，比如将状态转移方程替换为一个非线性函数，或者将输出值替换为当前状态的一个非线性函数，或者使用多个 LFSR，将它们的输出的一个非线性函数作为输出。

Trivium

Introduction to Modern Cryptography Reading Notes

6 Hash Functions and Applications

哈希函数的定义

A hash function (with output length \(\ell(n)\)) is a pair of probabilistic polynomial-time algorithms \((\text{Gen}, H)\) satisfying the following:

• \(\text{Gen}\) is a probabilistic algorithm that takes as input a security parameter \(1^n\) and outputs a key \(s\). We assume that \(n\) is implicit in \(s\).
• \(H\) is a deterministic algorithm that takes as input a key \(s\) and a string \(x \in \{0, 1\}^∗\) and outputs a string \(H^s(x) \in \{0, 1\}^{\ell(n)}\) (where \(n\) is the value of the security parameter implicit in \(s\)).

If \(H^s\) is defined only for inputs \(x\) of length \(\ell'(n) > \ell(n)\), then we say that \((\text{Gen}, H)\) is a fixed-length hash function for inputs of length \(\ell'(n)\). In this case, we also call \(H\) a compression function.

在这里，攻击者往往会知道 \(s\) 的值，因此 \(s\) 放在 \(H\) 的上标。

The collision-finding experiment \(\text{Hash-coll}_{\mathcal{A},\mathcal{H}(n)}\) \((\mathcal{H}=(\text{Gen},H))\):

1. A key \(s\) is generated by running \(\text{Gen}(1^n)\).
2. The adversary \(\mathcal{A}\) is given \(s\), and outputs \(x, x'\) . (If \(H\) is a fixed-length hash function for inputs of length \(\ell'(n)\), then we require \(x, x' \in \{0, 1\}^{\ell'(n)}\).)
3. The output of the experiment is defined to be \(1\) if and only if \(x = x'\) and \(H^s(x) = H^s(x')\). In such a case we say that \(\mathcal{A}\) has found a collision.

如果 \(\text{Pr}[\text{Hash-coll}_{\mathcal{A},\mathcal{H}(n)}=1]\leq\text{negl}(n)\)，则称 \(\mathcal{H}\) 是collision resistant的。

下面给出两个其他关于哈希安全的概念。

• Second-preimage resistance 给出 \(s\) 和一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(x\neq x',H(x)=H(x')\)
• Preimage resistance 给出 \(s\) 和 \(y=H^s(x)\) 对于一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(H(x)=H(x')\) (\(x'\) 可以等于 \(x\))

Introduction to Modern Cryptography Reading Notes

5 CCA-Security and Authenticated Encryption

这一章讨论的是如何保证 “secrecy in the presence of an active adversary”。

选择密文攻击和 CCA 安全

攻击者生成一段密文并使接收者对其进行解密，这样的攻击行为称为选择密文攻击(chosen-ciphertext attack)。

Padding-Oracle Attacks

对于使用 PKSC #7 标准(如果消息需要填充 \(b\) 个 byte，则在消息后填充 \(0\text{x}\overbrace{bb...b}^{b\text{ times}}\)，其中 \(b>0\)) 的 CBC-mode 加密，如果接收者收到了一个不符合 PKSC #7 标准的消息，则会发出一个 “bad padding” 错误，如果攻击者能探知这个信息，就可以进行攻击。

比如，对于有两个 block 的 CBC，\(m_2=c_1\oplus F^{-1}_k(c_2)\)，那么通过发送 \((c_1\oplus\Delta,c_2)\)，解密后会得到 \((m_1',m_2\oplus \Delta)\)，那么通过枚举 \(\Delta\) 的每一个 byte，可以破解出 \(b\) 的值，然后可以用类似的方式破解出 \(m_2\), \(m_1\) 的值。

下面定义 CCA-secure

The CCA indistinguishability experiment \(\text{PrivK}^{\text{cca}}_{\mathcal{A},\Pi(n)}\):

1. A key \(k\) is generated by running \(\text{Gen}(1^n)\).
2. \(\mathcal{A}\) is given input \(1^n\) and oracle access to \(\text{Enc}_k(\cdot)\) and \(\text{Dec}_k(\cdot)\).It outputs a pair of equal-length messages \(m_0, m_1\).
3. A uniform bit \(b \in \{0, 1\}\) is chosen, and then a challenge ciphertext \(c \leftarrow \text{Enc}_k(m_b)\) is computed and given to \(\mathcal{A}\).
4. The adversary \(\mathcal{A}\) continues to have oracle access to \(\text{Enc}_k(\cdot)\) and \(\text{Dec}_k(\cdot)\), but is not allowed to query the latter on the challenge ciphertext itself. Eventually, \(\mathcal{A}\) outputs a bit \(b'\).
5. The output of the experiment is \(1\) if \(b' = b\), and \(0\) otherwise.If the output of the experiment is \(1\), we say that \(\mathcal{A}\) succeeds.

Introduction to Modern Cryptography Reading Notes

4 Message Authentication Codes

MAC的定义

我们需要保证消息可靠性(message integrity)，以应对攻击者可能会注入或修改信息的情况，为此需要引入新的机制 message authentication code (MAC)。

A message authentication code (or MAC) consists of three probabilistic polynomial-time algorithms \((\text{Gen},\text{Mac},\text{Vrfy})\) such that:

1. The key-generation algorithm \(\text{Gen}\) takes as input the security parameter \(1^n\) and outputs a key \(k\) with \(|k| \geq n\).
2. The tag-generation algorithm \(\text{Mac}\) takes as input a key \(k\) and a message \(m \in \{0, 1\}^*\), and outputs a tag \(t\). Since this algorithm may be randomized, we write this as \(t \leftarrow \text{Mac}_k(m)\).
3. The deterministic verification algorithm \(\text{Vrfy}\) takes as input a key \(k\), a message \(m\), and a tag \(t\). It outputs a bit \(b\), with \(b = 1\) meaning valid and \(b = 0\) meaning invalid. We write this as \(b := \text{Vrfy}_k(m, t)\).

It is required that for every \(n\), every key \(k\) output by \(\text{Gen}(1^n)\), and every \(m \in \{0, 1\}^∗\), it holds that \(\text{Vrfy}_k(m, \text{Mac}_k(m)) = 1\).

If there is a function \(\ell\) such that for every \(k\) output by \(\text{Gen}(1^n)\), algorithm \(\text{Mac}_k\) is only defined for messages \(m \in \{0, 1\}^{\ell(n)}\), then we call the scheme a fixed-length MAC for messages of length \(\ell(n)\).

接下来就是关于 MAC 的安全测试和安全定义。

The message authentication experiment \(\text{Mac-forge}_{\mathcal{A},\Pi(n)}\):

1. A key \(k\) is generated by running \(\text{Gen}(1^n)\).
2. The adversary \(\mathcal{A}\) is given input \(1^n\) and oracle access to \(\text{Mac}_k(\cdot)\).The adversary eventually outputs \((m, t)\). Let \(Q\) denote the set of all queries that \(\mathcal{A}\) submitted to its oracle.
3. \(\mathcal{A}\) succeeds if and only if (1) \(\text{Vrfy}_k(m, t) = 1\) and (2) \(m \notin Q\).In that case the output of the experiment is defined to be \(1\).

也就是说，\(\mathcal{A}\) 能多次访问黑盒 \(\text{Mac}_k\)，如果构造出任意一组能通过 \(\text{Vrfy}\) 验证的，且自己没有把明文输入给 \(\text{Mac}_k\) 的 \((m,t)\)，就算 \(\mathcal{A}\) 成功。注意到，如果通过 \(t\) 构造出一个 \(m\)，使得 \((m,t)\) 通过验证，那么 \(\mathcal{A}\) 也是通过该测试的。

对于安全的定义和之前类似，即通过测试的概率可忽略，就不再抄一遍了。

上面的定义并没有预防 replay attacks，即攻击者可以重复发送一条信息（比如，转账请求）。这种问题一般在应用层面进行解决，比如在消息中添加编号或时间戳这类信息。

hexo 自带的 markdown 渲染器太拉了，老是和 mathjax 冲突，包括但不限于把公式里的 / 和 _ 认成 markdown 语法

所以改用 pandoc 了

1. Hello
2. World

1

This is code

\(\binom{n}{m}=\frac{n!}{m!(n-m)!}\)

\[ c\leftarrow \text{Enc}_k(m) \]