密码学原理

可证明安全理论

---

公钥加密算法的安全性定义

基本概念

1. 安全参数与多项式时间

   安全参数 λ（Security Parameter）：衡量攻击者破解密码方案的难度。λ越大，系统越安全。

   例子 ：λ=128时，攻击者至少需要2¹²⁸步操作才能破解（相当于宇宙中原子总数的量级）。

   安全参数的两种类型 ：

   • 计算安全参数 ：破解所需的计算量。例如分解大整数n的难度≈$2^{log n}$，若n是2048位，计算量≈$2^{1024}$。
   • 统计安全参数 ：攻击成功的概率。例如暴力破解128位密钥的概率是$\frac{1}{2^{128}}$，几乎为0。

   ---

   λ的多项式大小：存在常数c和某个λ’，当λ足够大时，任何多项式函数poly(λ) ≤ λᶜ。

   例如，poly(λ)=$λ^{1.5}$ 或$ 4λ^{10}+λ^3+1$，它们最终都会被某个λᶜ（如λ¹¹）超过。

   在密码学中，多项式增长（即λ^n）被视为“可接受”，指数增长（如2^λ）则不可接受。

   多项式时间算法：算法运行时间是输入长度 的多项式，而非输入数值 的多项式。

   输入长度 ：例如输入是数字x，其二进制位数是log₂|x|（即输入长度）。

   例子 ：

   • 若输入是n位二进制数，算法运行时间是O(n³)，则属于多项式时间。
   • 若运行时间是O(2ⁿ)，则是指数时间（不可行）。

   多项式时间算法的两种类型 ：

   • 确定性多项式时间（DPT） ：算法每一步确定，无随机性。例如计算哈希值。
   • 概率性多项式时间（PPT） ：算法可抛硬币（随机选择），但运行时间仍是多项式。例如生成随机密钥。

   ---

   很好的类比：

   • 安全参数λ ：像保险箱的密码位数。位数越多（λ越大），小偷试遍所有组合（2^λ次）越难。
   • 计算安全 ：小偷需要撬开保险箱的时间（计算量）。
   • 统计安全 ：小偷蒙对密码的概率（1/2^λ）。
   • 多项式时间 ：快递员送n个包裹，时间与n²成正比（可接受）；若时间与2ⁿ成正比（n=100时比宇宙年龄还长），则不可接受。

2. 可忽略概率和压倒性概率

   可忽略概率（Negligible Probability）：一种“小到可以忽略不计”的概率，记作negl(λ)。当安全参数λ增大时，它下降的速度比任何多项式函数的倒数都快。

   即对任意多项式poly(λ)，存在某个λ’，当λ足够大时，negl(λ) ≤ 1/poly(λ)。

   • negl(λ) = $2^{-\lambda}$：λ=128时，概率是1/2¹²⁸（比地球上的沙子总数分之一还小）。
   • negl(λ) = $\lambda^{-\lambda}$：当λ=100时，概率是1/100¹⁰⁰（比宇宙中的原子数分之一还小）。

   密码学中，攻击成功的概率如果是可忽略的，就认为方案是安全的。比如破解密钥的概率是2⁻¹²⁸，相当于“不可能”。

   ---

   压倒性概率（Overwhelming Probability）：压倒性概率是可忽略概率的补集，即 overwhelm(λ) = 1 - negl(λ)。当λ足够大时，它无限接近1。

   overwhelm(λ) =$ 1 - 2^{-\lambda}$：当λ=256时，概率是1 - 1/2²⁵⁶，小数点后76个9。

   密码学中，协议成功的概率如果是压倒性的，就认为它“几乎总是有效”。比如密钥协商成功的概率是1 - 2⁻¹²⁸。

   ---

   非可忽略概率（Non-Negligible）：如果存在某个多项式poly(λ)，使得概率 > 1/poly(λ)，则称为非可忽略概率。

   它虽然可能很小，但下降速度不够快，实际中可能被攻击者利用。就像“买彩票中头奖”的概率。虽然很小（比如1/1亿），但如果攻击者尝试1亿次，可能成功一次。

3. 布尔不等式

   设 E1, …,Ep 为 p 个事件(它们之间可以任意相关), 则Pr[ E1 ∨ … ∨ Ep ] ≤ Pr[ E1 ] + … + Pr[ Ep ] 。

   想象你有多个可能发生的事件（比如抛硬币正面、下雨等），不管它们之间有没有关联，其中至少一个事件发生的概率，不会超过每个事件单独发生概率的总和。例如，事件A有10%的概率，事件B有20%的概率，那么至少发生A或B的概率最多是30%（实际可能更低，比如两者有重叠时）。

   • **推论1（多次小概率事件）：**假设你重复做某件事多项式次（比如λ²次，λ是安全参数），每次失败的概率都极低（可忽略，比如1/2^λ）。那么，即使尝试很多次，至少失败一次的概率仍然极低。
   • **推论2（多次高概率事件）：**如果某件事每次成功的概率极高（压倒性概率，比如1 - 1/2^λ），那么重复多项式次后，所有次都成功的概率仍然极高。

4. 全概率公式

   若事件 A1， A2, … , 𝐴𝑛 构成一个完备事件组， 即它们两两互不相容，且其和为全集， 且都有正概率，则对任意一个事件 B， 有如下公式成立：𝑃(𝐵) = 𝑃 (𝐵 ∧ 𝐴1) + 𝑃 (𝐵 ∧ 𝐴2) + ⋯ + 𝑃 (𝐵 ∧ 𝐴𝑛)= 𝑃 (𝐵 |𝐴1) 𝑃 (𝐴1) + 𝑃 (𝐵 |𝐴2) 𝑃 (𝐴2) + ⋯ + 𝑃 (𝐵 |𝐴𝑛) 𝑃(𝐴𝑛)此公式即为全概率公式。

   特别地，对于任意两随机事件A和B， 有如下成立： 𝑃 (𝐵) = 𝑃 (𝐵|𝐴) 𝑃(𝐴) + 𝑃 (𝐵|¬𝐴) P(¬𝐴)其中A和¬𝐴为对立事件。

   贝叶斯公式：设 A、 B为两个事件，则𝑃 (A⋀𝐵) = 𝑃 (A|𝐵) 𝑃(B)

5. 可证明安全性

   • **精确刻画攻击者（敌手）的能力：**考虑敌手的输入（敌手已知的公开信息）、敌手的攻击能力（计算能力有限）、敌手的攻击方式（主动攻击和被动攻击）

     • 被动攻击：只偷听信息，不干扰通信。例如，你通过公共Wi-Fi发送加密邮件，黑客截获了密文，但无法解密内容，只能知道你在发邮件。
     • 主动攻击：篡改、伪造或干扰通信。例如，黑客截获你的登录请求，篡改密码后发送给服务器，试图以你的身份登录。

   • **精确刻画安全目标：**刻画不希望被攻破的目标

   • 密码算法/协议 ∏ 的X-Y安全定义(template) :任意概率多项式时间敌⼿在 Y安全模型 中攻破密码算法/协议 ∏ 的 X安全目标 的概率是可忽略的。例如，公钥加密算法的IND-CPA安全性，数字签名算法的EUF-CMA安全性。

   ---

   通俗解释：

   想象你要设计一个防盗保险箱，你必须先明确：（精确刻画攻击者（敌手）的能力）

   • 小偷能拿到什么信息？ （比如保险箱的外观、锁的类型，对应密码学中的“公开参数”或“公钥”）。
   • 小偷有什么工具？ （比如他只能用普通电钻，不能带激光切割机；对应密码学中“敌手只能在多项式时间内计算”，即不能暴力穷举）。
   • 小偷能怎么动手？ （比如只能偷看保险箱周围，不能直接撬锁；对应“被动攻击”或“主动攻击”等安全模型）。

   明确你要保护什么，比如：（精确刻画安全目标）

   • 保险箱里的东西绝对保密 （对应加密算法的“保密性”）。
   • 保险箱不能被伪造 （对应数字签名的“不可伪造性”）。

公钥加密算法

通过公钥加密算法进行信息传输的流程：

⼀个公钥加密算法 (public-key encryption) PKE 包含三个PPT(概率多项式时间)算法 (Gen, Enc, Dec)：

• 密钥⽣成算法 (PK, SK) ← Gen($1^\lambda$)： ⼀般为概率性算法，生成钥匙的过程可能需要随机性
• 加密算法 C ← Enc(PK, M)： M ∈ M ，其中 M 为消息空间
• 解密算法 M’← Dec(SK, C)：⼀般为确定性算法（同一把私钥和密文，结果永远一致）， M’ ∈ M ∪ {⊥}，其中 ⊥ 代表解密失败

正确性要求 (correctness)：

对于 ∀ (PK, SK) ← Gen($1^\lambda$)， ∀ M ∈ M， ∀ C ← Enc(PK, M), ⼀定有Dec(SK, C) = M

---

按照密码算法/协议 ∏ 的X-Y安全定义模板来分析公钥加密算法：

• 敌⼿攻击能力 (以被动攻击的敌⼿为例)

  • 运行时间：概率多项式时间

  • 输入：公钥PK和在公开信道中传输的密文C

  • 攻击方式：被动攻击

    

• 安全目标（刻画不希望该密码算法被攻破目标）

  • SK-hiding (SKH) 安全目标：如果 output = SK，则攻破该⽬标
  • Plaintext-hiding（PH ） 安全⽬标： 即如果 output = M ， 则攻破该⽬标
  • Plaintext- first- bit- hiding ( PFbH)安全⽬标： 即如果 output = M[1]（密文的第一bit信息） ， 则攻破该⽬标

公钥加密算法的 SKH/PH/PFbH-PA安全性 定义:任意概率多项式时间敌⼿在PA安全模型中攻破SKH/PH/PFbH安全⽬标的概率是可忽略的。

---

しかし、即使加密算法满足了上述三种安全目标也并不能真正保证加密的安全性：

• 加密算法Enc(PK, M) =M：

  从 (PK, C) 中难以恢复出 SK， 因此该算法满⾜SKH-PA安全性定义。但是该加密算法显然是不安全的，因为得到的密文和明文一致

• Enc(PK, M) = (C, M[1])：

  从 (PK, C) 中难以恢复出整个 M ， 因此该算法满⾜PH-PA安全性定义。但是该加密算法泄漏了 M的第⼀⽐特 M[1] ， 显然是不安全的。

• Enc(PK, M) = (C, M[2])：

  从 (PK, C) 中难以恢复出 M[1]， 因此该算法满⾜PFbH-PA安全性定义。但是该加密算法泄漏了 M的第⼆⽐特 M[2] ， 显然是不安全的。

下面介绍能够衡量公钥加密算法安全的方式：IND-CPA安全性

公钥加密算法IND-CPA安全性

首先，挑战者通过密钥生成算法生成公私钥，并将公钥提供给敌手；然后敌手提供两个已知明文M0和M1给挑战者用于加密；挑战者会随机选取M0或者是M1去加密（这里用b的取值来表示选哪个），将得到的密文C*提供给敌手；最后敌手根据C*和公钥判断挑战者加密的到底是M0还是M1。

• 敌手的CPA攻击能力（选择明文攻击）

  • 运行时间：概率多项式时间
  • 输入：公钥PK和在公开信道中传输的密文C*
  • 攻击方式：选择明文攻击，即敌手可以提供/决定/影响加密使用的明文

• IND安全目标（不可区分性）

  敌手无法区分密文C*到底是由M0还是M1加密而来，即如果 output = b， 则攻破该⽬标。

• 公钥加密算法的 IND-CPA安全性定义 :

  任意概率多项式时间敌⼿在CPA安全模型中攻破 IND 安全⽬标的优势(advantage) 是可忽略的，也即$| Pr[output = b] -\frac{1}{2} | =negl(𝜆)$。这是因为敌手如果随便猜一个那猜中的概率也是$\frac{1}{2}$，所以要考虑优势这一块。

• 等价定义：

  任意概率多项式时间敌⼿在CPA安全模型中攻破IND安全⽬标的优势

  $$| Pr[output = * | b = 0] - Pr[output = * | b = 1] |\text{，其中*可取1或0}$$

  是可忽略的。

• 可以通过反证法证明公钥加密算法的 IND-CPA安全性 ⇒ SKH-PA安全性、PH-PA安全性、PFbH-PA安全性。IND-CPA是公钥加密算法的基本安全性要求，其安全性可以保证公钥PK和密⽂C隐藏：私钥SK，明⽂M ，明⽂ M的第⼀⽐特M[1]，明⽂M的任⼀⽐特M[i]， 明⽂M的校验值 M[1] ⊕ M[2] ⊕ … ⊕ M[n], …

公钥加密算法的IND-mCPA安全性

• 敌手的mCPA攻击能力（多挑战-选择明文攻击）

  • 运行时间：概率多项式时间
  • 输入：公钥PK和在公开信道中传输的多项式个密文$C^{(j)*}$
  • 攻击方式：选择明文攻击，即敌手可以提供/决定/影响加密使用的多项式个明文

• IND安全目标（不可区分性）

  敌手无法区分密文$C^{(j)*}$到底是由$M_{0}^{(j)}$还是$M_{1}^{(j)}$加密而来，即如果 output = b， 则攻破该⽬标。

• 公钥加密算法的 IND-mCPA安全性定义 :

  任意概率多项式时间敌⼿在mCPA安全模型中攻破 IND 安全⽬标的优势(advantage) 是可忽略的，也即$| Pr[output = b] -\frac{1}{2} | =negl(𝜆)$。

---

IND-mCPA实际上与IND-CPA等价，由IND-mCPA$\Rightarrow$IND-CPA是显然的，下面采用混合论证来说明IND-CPA$\Rightarrow$IND-mCPA

首先，

ElGamal 加密算法的安全性证明

离散对数问题

**定义：**对于a∈G和b∈〈a〉，若b = aˣ，则x称为b相对于a的离散对数，记为DLOGₐ(b)。

x的范围为{0, 1, …, ord(a)-1}。

数字签名算法的EUF-CMA安全

作业答案供参考

---

HM1

Solution1

解密步骤：

由 $$c_1^x = (g^y)^x = g^{xy}$$，则

• 若 $$c_1^x = c_2$$，则明文为 $$0$$（因为此时 $$c_2 = h^y = g^{xy}$$）。
• 若 $$c_1^x \neq c_2$$，则明文为 $$1$$（此时 $$c_2 = g^z$$，且 $$z$$ 独立于 $$y$$，故 $$g^z \neq g^{xy}$$ 的概率极高）。

正确性分析：

• 当 $$b = 0$$ 时，$$c_2 = h^y = g^{xy}$$，必然满足 $$c_1^x = c_2$$。
• 当 $$b = 1$$ 时，$$c_2 = g^z$$，若 $$z \neq xy \mod q$$（概率为 $$1 - \frac{1}{q}$$），则 $$c_1^x \neq c_2$$。由于 $$q$$ 为大素数，$$\frac{1}{q}$$ 可忽略。

---

CPA 安全性证明：

假设存在多项式时间敌手 $$\mathcal{A}$$ 能以不可忽略的优势 $$\epsilon$$ 攻破该加密方案的 CPA 安全性。

安全性证明步骤如下：

\mathcal{D}$$ 接收 DDH 实例 $$(g, g^a, g^b, T)$$，需判断 $$T = g^{ab}$$ 或 $$T = g^c$$（随机）。$$\mathcal{D}$$ 生成公钥 $$pk = (G, q, g, h = g^a)$$。私钥 $$x = a$$，但 $$\mathcal{D}$$ 并不知道 $$a$$。当 $$\mathcal{A}$$ 提交挑战比特 $$b_0 = 0$$ 和 $$b_1 = 1$$ 时，$$\mathcal{D}$$ 构造挑战密文为 $$(c_1, c_2) = (g^b, T)$$。$\mathcal{D}$ 将公钥 $pk$ 和挑战密文 $(c_1, c_2)$ 发送给 $\mathcal{A}$$。$$\mathcal{A}$ 输出猜测结果 $$b'$$（认为密文对应 $$b' \in \{0, 1\}$$）。 - 若 $$\mathcal{A}$$ 猜测 $$b' = 0$$，则 $$\mathcal{D}$$ 判定 $$T = g^{ab}$$（即 DDH 元组为真）。 - 若 $$\mathcal{A}$$ 猜测 $$b' = 1$$，则 $$\mathcal{D}$$ 判定 $$T = g^c$$（即随机元组）。 则 - 当 $$T = g^{ab}$$ 时，挑战密文为 $$(g^b, g^{ab}) = (g^b, h^b)$$，对应加密 $$b = 0$$。 - 当 $$T = g^c$$ 时，挑战密文为 $$(g^b, g^c)$$，对应加密 $$b = 1$$。 $$\mathcal{D}$$ 的成功概率与 $$\mathcal{A}$$ 的优势相同。若 $$\mathcal{A}$$ 的优势不可忽略，则 $$\mathcal{D}$$ 可破解 DDH 假设，矛盾。因此在 DDH 问题困难的假设下，该加密方案是 CPA 安全的。 ### Solution2 **e次根问题困难$\Rightarrow$Plain RSA满足PH-PA安全**: 假设存在多项式时间敌手 $A$ 能以不可忽略概率 $\epsilon$ 攻破PH-PA安全，即：

\Pr[A(N, e, C) = M] = \epsilon

构造算法 $B$ 解决e次根问题：输入为$(N, e, C)$，其中 $C = M^e \mod N$，$M \xleftarrow{R} \mathbb{Z}_N^*$。随后调用 $A(N, e, C)$ 得到输出 $M'$。若 $M'^e \equiv C \mod N$，则返回 $M'$，否则失败。 若 $A$ 成功，则 $B$ 直接解决e次根问题。成功概率满足 $\Pr[B \text{ 成功}] = \Pr[A \text{ 成功}] = \epsilon$。根据e次根问题的困难性假设，$\epsilon$ 必为可忽略，矛盾。故Plain RSA满足PH-PA安全。 --- **Plain RSA满足PH-PA安全$\Rightarrow$e次根问题困难：** 假设存在多项式时间算法 $B$ 能以不可忽略概率 $\delta$ 解决e次根问题，即：

\Pr[B(N, e, C) = M] = \delta

构造敌手 $A$ 攻破PH-PA安全：输入为公钥 $(N, e)$ 和密文 $C = M^e \mod N$。随后调用 $B(N, e, C)$ 得到输出 $M'$。 若 $B$ 成功，则 $A$ 直接恢复明文 $M$。成功概率满足 $\Pr[A \text{ 成功}] = \Pr[B \text{ 成功}] = \delta$。根据PH-PA安全性假设，$\delta$ 必为可忽略，矛盾。故e次根问题困难。 ### Solution3 构造一个多项式时间敌手 $A$ 如下： + 敌手 $A$ 选择两个不同明文 $m_0, m_1 \in \mathbb{Z}_N^*$，满足 $m_0 \neq m_1$，然后将 $(m_0, m_1)$ 提交给挑战者 + 挑战者收到挑战密文 $c = Enc(pk, m_b) = m_b^e \mod N$，计算 $c_0 = m_0^e \mod N$。若 $c_0 = c$，输出 $b' = 0$；否则输出 $b' = 1$ 对于该加密算法而言：

\Pr[b’ = b] =
\begin{cases}
1 & \text{若 } c = m_0^e \mod N \
1 & \text{若 } c = m_1^e \mod N
\end{cases}

$$因此敌手优势为：$$

\left| \Pr[\text{IND-CPA}(A) = 1] - \frac{1}{2} \right| = \left| 1 - \frac{1}{2} \right| = \frac{1}{2}

由于敌手 $A$ 具有不可忽略的优势 $\frac{1}{2}$，Plain RSA加密方案不满足IND-CPA安全。 ### Solution4 假设存在一个公钥加密方案 $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$，满足：对任意PPT攻击者 $\mathcal{A}$，存在可忽略函数 $\text{negl}(\cdot)$，使得： $$\left| \Pr[\text{CPA}_{\mathcal{A},\Pi}(1^\lambda) = 1] - \frac{1}{2} \right| \leq \text{negl}(\lambda)$$。且对于安全参数 $\lambda$，密文长度为 $k = O(\log \lambda)$。 对于攻击者 $\mathcal{A}$，其输入为公钥 $pk$，提交挑战明文 $m_0 = 0$ 和 $m_1 = 1$。请求加密 $m_0$ 多项式次（如 $T = \lambda^c$ 次），得到密文集 $\mathcal{C}_0 = \{\text{Enc}(pk, 0)\}_{i=1}^T$；请求加密 $m_1$ 同样次数，得到密文集 $\mathcal{C}_1 = \{\text{Enc}(pk, 1)\}_{i=1}^T$。 最后接收挑战密文 $c^* = \text{Enc}(pk, m_b)$，其中 $b \in \{0,1\}$。若 $c^* \in \mathcal{C}_0$，输出 $b' = 0$；否则，输出 $b' = 1$。 - 当 $b=0$ 时：$c^*$ 服从 $\mathcal{D}_0$，则 $c^* \in \mathcal{C}_0$ 的概率为： $$\Pr[c^* \in \mathcal{C}_0 \mid b=0] \geq 1 - \left(1 - \frac{1}{\text{poly}(\lambda)}\right)^{\text{poly}(\lambda)} \approx 1 - e^{-1} \approx 0.63.

• 当 $b=1$ 时：$c^*$ 服从 $\mathcal{D}_1$，若 $\mathcal{D}_0$ 和 $\mathcal{D}_1$ 的统计距离 $\Delta(\mathcal{D}_0, \mathcal{D}_1)$ 不可忽略，则存在某些 $c$ 使得 $c \notin \mathcal{C}_0$ 但 $c \in \mathcal{C}_1$，从而 $\Pr[c^* \notin \mathcal{C}_0 \mid b=1]$ 不可忽略。

攻击者优势：

$$\left| \Pr[b'=b] - \frac{1}{2} \right| \geq \text{non-negl}(\lambda),$$

这与 $\Pi$ 的CPA安全性矛盾。由于假设密文长度 $k = O(\log \lambda)$ 导致攻击者优势不可忽略，因此原假设不成立。故密文长度必须满足 $k = \omega(\log \lambda)$，即超对数。

HM2

Solution1

假设存在攻击者 $\mathcal{A}$ 能以不可忽略的概率 $\epsilon$ 破坏DSA的UI-PA安全性，则构造算法 $\mathcal{B}$ 利用 $\mathcal{A}$ 解决DL问题。

• 算法 $\mathcal{B}$ 接收DL问题实例 $(p, q, g, y)$，为了找到 $x$ 使得 $y = g^x \mod p$。$\mathcal{B}$ 将 $(p, q, g, y)$ 作为公钥发送给 $\mathcal{A}$。

• 当 $\mathcal{A}$ 请求观察 $t$ 次合法交互时，$\mathcal{B}$ 生成合法记录 $\{(r_i, e_i, s_i)\}_{i=1}^t$。此时对每个 $i$，随机选择 $s_i \in \mathbb{Z}_q^*$ 和 $e_i \in \mathbb{Z}_q$，由 $u_i = s_i^{-1} \mod q$，$v_{1,i} = u_i \cdot e_i \mod q$，$v_{2,i} = u_i \cdot r_i \mod q$，有

  $$r_i = \left( g^{v_{1,i}} y^{v_{2,i}} \mod p \right) \mod q$$

  最后 $\mathcal{A}$得到的是$(r_i, e_i, s_i)$。

• $\mathcal{B}$ 运行 $\mathcal{A}$ 至其输出一次有效的冒充 $(r, e, s)$时，就重置 $\mathcal{A}$ 到某次挑战前的状态，替换挑战为 $e' \neq e$，重新运行 $\mathcal{A}$ 得到 $(r, e', s')$。

• 根据重置状态前后的两次响应，联立方程：

  $$s = k^{-1}(e + x r) \mod q, \quad s' = k^{-1}(e' + x r) \mod q$$

  消去 $k$ 后得到：

  $$x = \frac{s \cdot e' - s' \cdot e}{r \cdot (s' - s)} \mod q$$

  当$s' \neq s$ 且 $r \neq 0$时，$\mathcal{B}$ 的输出为 $x$。

若 $\mathcal{A}$ 的成功概率为 $\epsilon$，则 $\mathcal{B}$ 的成功概率约为 $\epsilon^2 / q$。若DL问题是困难的，则 $\epsilon$ 必须可忽略，从而DSA识别方案是UI-PA安全的。

Solution2

明文可以伪造

在这种攻击方式下，攻击者可以构造任意有效的签名 $(r, s)$ 并生成对应的消息 $M$，无需知道私钥 $x$。

攻击者选择任意 $s \in \mathbb{Z}_q^*$ 和 $r \in \mathbb{Z}_q^*$，则有

$$M = s k - x r \mod q$$

攻击者定义 $M$ 为上述计算结果，则根据DSA验证方程：

$$\begin{aligned} u &= s^{-1} \mod q, \\ v_1 &= u \cdot M \mod q, \\ v_2 &= u \cdot r \mod q, \\ r' &= \left( g^{v_1} y^{v_2} \mod p \right) \mod q \end{aligned}$$

代入 $M = s k - x r$ 后，验证方程恒成立：

$$r' = \left( g^{k} \cdot g^{-x r} \cdot y^{r} \mod p \right) \mod q = r$$

$M$ 直接出现在签名方程中，使得攻击者可以自由选择 $(r, s)$ 并构造对应的 $M$，这是不安全的。

---

私钥可被恢复

若攻击者能获取两个不同消息 $M_1, M_2$ 的签名 $(r, s_1)$ 和 $(r, s_2)$，则

$$\begin{cases} s_1 = k^{-1}(M_1 + x r) \mod q \\ s_2 = k^{-1}(M_2 + x r) \mod q \end{cases}$$

$$\text{1式减去2式解得，} k = \frac{M_1 - M_2}{s_1 - s_2} \mod q$$

则

$$x = \frac{s_1 k - M_1}{r} \mod q$$

在本题中允许通过线性方程直接恢复私钥，这显然是不安全的。

Solution3

假设存在敌手 $\mathcal{A}$ 以不可忽略的优势 $\epsilon$ 攻破IND-CPA安全性，则构造算法 $\mathcal{B}$ 利用 $\mathcal{A}$ 解决e次根问题。

• 算法 $\mathcal{B}$ 接收e次根问题实例 $(N, e, y)$，将公钥 $(N, e)$ 发送给 $\mathcal{A}$。
• $\mathcal{B}$ 维护表 $\text{HT}$ 记录所有对 $H$ 的查询 $(r, h)$，其中 $h \in \{0,1\}^n$ 为随机值。
• 当 $\mathcal{A}$ 查询 $H(r)$ 时，若 $r$ 已在 $\text{HT}$ 中，返回对应的 $h$；否则，随机生成 $h \leftarrow \{0,1\}^n$，将 $(r, h)$ 存入 $\text{HT}$，返回 $h$。
• 在挑战阶段时，$\mathcal{A}$ 提交 $M_0, M_1$。$\mathcal{B}$ 设置 $C_1^* = y$（即挑战密文的 $r^*$ 需满足 $(r^*)^e \equiv y \mod N$），随机选择 $b \in \{0,1\}$ 和 $h^* \leftarrow \{0,1\}^n$，计算 $C_2^* = h^* \oplus M_b$，发送 $(C_1^*, C_2^*)$ 给 $\mathcal{A}$。
• 在猜测阶段时，$\mathcal{A}$ 输出 $b'$，若 $b' = b$，则 $\mathcal{B}$ 遍历 $\text{HT}$，寻找满足 $r^e \equiv y \mod N$ 的 $r$，输出 $r$ 作为e次根的解。

若$\mathcal{A}$ 未查询过 $r^*$，由于 $H$ 是随机预言机，$\mathcal{A}$ 对 $H(r^*)$ 的值完全未知，$C_2^* = h^* \oplus M_b$ 的分布与均匀随机串不可区分。因此，$\mathcal{A}$ 的优势 $\epsilon$ 可忽略。

若$\mathcal{A}$ 查询过 $r^*$，$\mathcal{B}$ 在 $\text{HT}$ 中能找到 $r^*$，从而直接解决e次根问题。若 $\mathcal{A}$ 的优势 $\epsilon$ 不可忽略，则 $\mathcal{B}$ 成功概率至少为 $\epsilon / q_H$（$q_H$ 为哈希查询次数），与e次根问题困难性矛盾。

HM3

Solution1

对于点$P(2,7)$，满足

$$7^2~mod~11=5\\ (2^3+2+6)~mod ~11=5$$

则点$P$在椭圆曲线上。

对于点$Q(5,2)$，满足

$$2^2~mod~11=4\\ 5^3+5+6~mod~11=4$$

则点$Q$在椭圆曲线上。

则斜率为

$$\begin{aligned} m&=\frac{2-7}{5-2}~mod~11\\ &=\frac{6}{3}=6\cdot3^{-1}\\ &=6\cdot4~mod ~11\\ &=2 \end{aligned}$$

则$P+Q=(x_R,y_R)$的坐标为：

$$x_R=(2^2-2-5)~mod~11=8\\ y_R=(2\cdot(2-8)-7)~mod~11=3$$

即$P+Q=(8,3)$。

Solution2

对于点$P(3,2)$，满足

$$2^2~mod~5=4\\ (3^3+3+4)~mod ~5=4$$

则点$P$在椭圆曲线上。

则斜率为

$$\begin{aligned} m&=\frac{3\cdot3^2+1}{2\cdot2}~mod~5\\ &=\frac{3}{4}=3\cdot4^{-1}\\ &=3\cdot4~mod ~5\\ &=2 \end{aligned}$$

则$2P=(x_R,y_R)$的坐标为：

$$x_R=(2^2-2\cdot3)~mod~5=3\\ y_R=(2\cdot(3-3)-2)~mod~5=3$$

验证$2P$在椭圆曲线上：

$$3^2~mod~5=4\\ (3^3+3+4)~mod~5=4$$

$P$的逆元$-P$为

$$-P=(3,-2)~mod~5=(3,3)$$

故$2P=-P$，即$3P=O$，故$P$是椭圆曲线上的一个 3-torsion 点。

Solution3

由 $x^3 + a x + b \equiv 0 \pmod{p}$ 有三个不同的根，记为 $r_1, r_2, r_3 \in \mathbb{Z}_p$。则椭圆曲线上存在三个二阶点： $$P_1 = (r_1, 0), \quad P_2 = (r_2, 0), \quad P_3 = (r_3, 0),$$ 以及无穷远点 $O$。

对于集合$H={O,P_1,P_2,P_3}$，其是椭圆曲线群 $(\mathcal{E}, +)$ 的子群，证明如下：

• 封闭：对任意$P_i, P_j \in H$，有
  • $P_i+P_j=P_k~(k\neq i,j)$。因为连接$ P_i$ 和 $P_j$的直线垂直于$x$轴，与曲线交于第三个根对应的点 $P_k$。
  • $P_i+P_i=O$
• 结合律和交换律：由于椭圆曲线群的加法满足交换律，故$H$是阿贝尔群。

群$H$与$\mathbb{Z}_2 \times \mathbb{Z}_2$同构，证明如下：

• $H$ 的非单位元阶均为 2
• 运算规则满足： $$P_1 + P_2 = P_3, \quad P_1 + P_3 = P_2, \quad P_2 + P_3 = P_1,$$ 这与克莱因四元群 $\mathbb{Z}_2 \times \mathbb{Z}_2$ 的结构一致，故 $H \cong \mathbb{Z}_2 \times \mathbb{Z}_2$。

由于$(\mathcal{E}, +)$ 是循环群，则其所有子群也必须是循环群。但是$\mathbb{Z}_2 \times \mathbb{Z}_2$非循环群，而$H$与其同构，故$H$也不是循环群，这与$H$是$(\mathcal{E}, +)$子群矛盾。因此$(\mathcal{E}, +)$ 不是循环群。

Solution4

若 $P$ 的阶为 3，则 $2P = -P$。根据椭圆曲线点加法规则：

• $2P = (x_3, y_3)$，其中 $x_3 = m^2 - 2x_1 \pmod{p}$，$y_3 = m(x_1 - x_3) - y_1 \pmod{p}$，
• $-P = (x_1, -y_1)$。

由 $2P = -P$，得：

$$\begin{cases} x_3 = x_1 \pmod{p}, \\ y_3 = -y_1 \pmod{p}. \end{cases}$$

斜率 $m$ 为：

$$m = \frac{3x_1^2 + a}{2y_1} \pmod{p}.$$

将 $x_3 = x_1$ 代入点加倍公式：

$$x_1 = m^2 - 2x_1 \pmod{p} \implies m^2 = 3x_1 \pmod{p}.$$

将 $m$ 的表达式代入：

$$\left(\frac{3x_1^2 + a}{2y_1}\right)^2 = 3x_1 \pmod{p}.$$

即

$$(3x_1^2 + a)^2= 12x_1 y_1^2 \pmod{p}.$$

代入椭圆曲线方程 $y_1^2 \equiv x_1^3 + a x_1 + b \pmod{p}$得

$$(3x_1^2 + a)^2 = 12x_1 (x_1^3 + a x_1 + b) \pmod{p}.$$

即

$$3x_1^4 + 6a x_1^2 + 12b x_1 - a^2 = 0 \pmod{p}.$$

---

对于曲线方程 $3x^4 + 6a x^2 + 12b x - a^2 \equiv 0 \pmod{p}$ ，其是 $\mathbb{F}_p$ 上的四次多项式方程，在域中最多有 4 个根。

对于每个根 $x_1$，由椭圆曲线方程 $y^2 \equiv x_1^3 + a x_1 + b \pmod{p}$，若 $x_1$ 有效，则 $y$ 有两个解（$y$ 和 $-y$），除非 $y = 0$。 但若 $y = 0$，则 $P = (x_1, 0)$ 的阶为 2（因 $2P = \mathcal{O}$），与三阶矛盾。因此，每个 $x_1$ 对应两个非零 $y$。

因此三阶点总数为$2\cdot 4=8$个。

Solution5

由 $g + h \in G_1$，则 $e(g + h, g + h) = 1$。

由$e(a + b, c + d) = e(a, c) \cdot e(a, d) \cdot e(b, c) \cdot e(b, d)$，将 $a = g$, $b = h$, $c = g$, $d = h$ 代入：

$$e(g + h, g + h) = e(g, g) \cdot e(g, h) \cdot e(h, g) \cdot e(h, h).$$

由于 $e(g, g) = 1$ 和 $e(h, h) = 1$，等式化简为：

$$1 = 1 \cdot e(g, h) \cdot e(h, g) \cdot 1 \implies e(g, h) \cdot e(h, g) = 1.$$

即在群 $G_T$ 中，若 $e(g, h) \cdot e(h, g) = 1$，则：

$$e(g, h) = e(h, g)^{-1}.$$

Solution6

设 $g_1$ 为 $G_1$ 的生成元，$h$ 为 $G_2$ 中给定元素，$g_T = e(g_1, h) \in G_T$。则需要证明：给定 $g_t \in G_T$ 和 $h \in G_2$，找到 $g \in G_1$ 使得 $e(g, h) = g_t$。

对任意 $g \in G_1$，可表示为 $g = g_1^x$（$x \in \mathbb{Z}$），则：

$$e(g, h) = e(g_1^x, h) = e(g_1, h)^x = g_T^x.$$

因此，配对反演问题等价于找到 $x$ 使得：

$$g_T^x = g_t.$$

若存在算法可解 $G_T$ 中的离散对数问题（即给定 $g_T, g_t \in G_T$，找到 $x$ 满足 $g_T^x = g_t$），则直接应用该算法即可得到 $x$，进而计算 $g = g_1^x$。则配对反演问题可多项式时间归约到 $G_T$ 中的离散对数问题，因此其难度不超过后者。

Solution7

由双线性性得：

$$\begin{aligned} e(aP + bQ, cP + dQ) &= e(aP, cP) \cdot e(aP, dQ) \cdot e(bQ, cP) \cdot e(bQ, dQ) \\ &= e(P, cP)^a \cdot e(P, dQ)^a \cdot e(Q, cP)^b \cdot e(Q, dQ)^b. \end{aligned}$$

由交替性 $e(P, P) = 1$ 和 $e(Q, Q) = 1$，得：

$$e(P, cP) = e(P, P)^c = 1^c = 1, \quad e(Q, dQ) = e(Q, Q)^d = 1^d = 1.$$

由反对称性 $e(Q, P) = e(P, Q)^{-1}$，得：

$$e(Q, cP) = e(Q, P)^c = \left(e(P, Q)^{-1}\right)^c = e(P, Q)^{-c}.$$

原式化简为：

$$\begin{aligned} e(aP + bQ, cP + dQ) &= 1^a \cdot e(P, dQ)^a \cdot e(P, Q)^{-c \cdot b} \cdot 1^b \\ &= e(P, Q)^{a d} \cdot e(P, Q)^{-b c} \\ &= e(P, Q)^{ad - bc}\\ &= e(P, Q)^{\begin{vmatrix} a & b \\ c & d \end{vmatrix} \mod N} \end{aligned}$$

Solution8

对任意 $G_2$ 中的 DDH 实例 $(P_2, a P_2, b P_2, c P_2)$，应用 $\phi$ 映射到 $G_1$：

$$\phi(P_2) = P_1, \quad \phi(a P_2) = a P_1, \quad \phi(b P_2) = b P_1, \quad \phi(c P_2) = c P_1.$$

下面判断 $G_1$ 中是否满足 $c P_1 = ab P_1$。

利用双线性配对 $e$，攻击者可以绕过同构直接验证：

$$e(\phi(a P_2), b P_2) = e(a P_1, b P_2) = e(P_1, P_2)^{ab}\\ e(\phi(P_2), c P_2) = e(P_1, c P_2) = e(P_1, P_2)^c$$

若 $c \equiv ab \pmod{N}$，则：

$$e(P_1, P_2)^{ab} = e(P_1, P_2)^c \implies ab \equiv c \pmod{N}.$$

由于 $\phi$ 和配对 $e$ 均可高效计算，攻击者无需解决离散对数问题即可验证 $c \equiv ab \pmod{N}$，导致 DDH 问题在 $G_2$ 上不再是困难问题。

HM4

Solution1

假设存在一个EUF-CMA敌手$\mathcal{A}$，成功概率为$\epsilon$，则可构造算法$\mathcal{B}$解决CDH问题。

$\mathcal{B}$接收CDH输入$(g, g^a, g^b)$，设置公钥$pk = g^a$。维护一个哈希表$\text{HT}$，记录随机预言机$H$的查询与应答。随机选择一个索引$k \in \{1, 2, \dots, Q_H\}$，假设敌手在第$k$次哈希查询中询问$m^*$。

对第$i$次$H(m_i)$查询：若$i = k$，设置$H(m_i) = g^b$（即$c_i = b$），记录$(m_i, c_i, h_i)$。否则，随机选择$c_i \in \mathbb{Z}_q$，设置$h_i = g^{c_i}$，记录$(m_i, c_i, h_i)$。

对消息$m_i$的签名请求：若$m_i$对应哈希查询$i = k$，则$\mathcal{B}$中止（因无法计算$g^{ab}$）。否则，查询$H(m_i)$得到$h_i = g^{c_i}$，计算签名$\sigma_i = (g^a)^{c_i} = g^{a c_i}$，返回$\sigma_i$。

伪造阶段：敌手$\mathcal{A}$输出伪造$(m^*, \sigma^*)$，且$m^* \notin \text{签名查询列表}$。若$m^*$对应的哈希查询不是第$k$次，则$\mathcal{B}$失败。否则，$\sigma^* = (g^a)^b = g^{ab}$，$\mathcal{B}$输出$\sigma^*$作为CDH解。

敌手$\mathcal{A}$成功伪造签名，概率为$\epsilon$。$\mathcal{B}$正确猜测敌手在第$k$次哈希查询中选择了$m^*$，概率为$\frac{1}{Q_H}$。故总成功概率：$\epsilon \cdot \frac{1}{Q_H}$。若$\epsilon$不可忽略，则$\mathcal{B}$解决CDH问题的概率为$\epsilon/Q_H$，仍不可忽略，与CDH问题的困难性假设矛盾。因此，BLS签名算法是EUF-CMA安全的。

Solution2

$$\|u\| = \sqrt{3^2 + 7^2} = \sqrt{9 + 49} = \sqrt{58}$$

$$\|v\| = \sqrt{5^2 + 10^2} = \sqrt{25 + 100} = \sqrt{125} = 5\sqrt{5}$$

---

$3u - 2v = (9-10, 21-20) = (-1, 1)$，范数为：

$$\|3u - 2v\| = \sqrt{(-1)^2 + 1^2} = \sqrt{2}$$

是最短向量。

Solution3

$$\mathbf{u}_1 = \mathbf{v}_1 = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$$

计算$\mathbf{v}_2$在$\mathbf{u}_1$上的投影，并减去该投影：

$$\mu_{21} = \frac{1 \cdot 1 + 2 \cdot 1 + 3 \cdot 1}{1^2 + 1^2 + 1^2} = 2$$

$$\mathbf{u}_2 = \mathbf{v}_2 - \mu_{21} \mathbf{u}_1 = \begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix} - 2 \cdot \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix}$$

计算$\mathbf{v}_3$在$\mathbf{u}_1$和$\mathbf{u}_2$上的投影，并减去这些投影：

$$\mu_{31} = \frac{1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1}{3}$$

$$\mu_{32} = \frac{1 \cdot (-1) + 0 \cdot 0 + 1 \cdot 1 = 0}{\|\mathbf{u}_2\|^2} = 0$$

$$\mathbf{u}_3 = \mathbf{v}_3 - \mu_{31} \mathbf{u}_1 - \mu_{32} \mathbf{u}_2 = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} - \frac{2}{3} \cdot \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} = \begin{pmatrix} \frac{1}{3} \\ -\frac{2}{3} \\ \frac{1}{3} \end{pmatrix}$$

正交化后的基向量为：

$$\mathbf{u}_1 = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}, \quad \mathbf{u}_2 = \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix}, \quad \mathbf{u}_3 = \begin{pmatrix} \frac{1}{3} \\ -\frac{2}{3} \\ \frac{1}{3} \end{pmatrix}$$

Solution4

设$\mathbf{b}_i^*$为Gram-Schmidt正交化向量，则：

$$\det(L) = \prod_{i=1}^n \|\mathbf{b}_i^*\|$$

LLL约简基满足对任意$j < i$：

$$\|\mathbf{b}_i^*\|^2 \geq \left( \delta - \mu_{i,j}^2 \right) \|\mathbf{b}_{j}^*\|^2$$

其中$\mu_{i,j} = \frac{\langle \mathbf{b}_i, \mathbf{b}_j^* \rangle}{\|\mathbf{b}_j^*\|^2}$，且$|\mu_{i,j}| \leq 1/2$。取$\delta = 3/4$，可得：

$$\|\mathbf{b}_i^*\|^2 \geq \frac{1}{2} \|\mathbf{b}_{i-1}^*\|^2 \quad \Rightarrow \quad \|\mathbf{b}_i^*\| \geq 2^{-(i-1)/2} \|\mathbf{b}_1^*\|$$

$$\det(L) = \prod_{i=1}^n \|\mathbf{b}_i^*\| \geq \|\mathbf{b}_1^*\|^n \prod_{i=1}^n 2^{-(i-1)/2} = \|\mathbf{b}_1\|^n \cdot 2^{-n(n-1)/4}$$

因此：

$$\|\mathbf{b}_1\| \leq 2^{(n-1)/4} \cdot \det(L)^{1/n}$$

---

定义投影算子$\pi_1: \mathbb{R}^m \to \text{span}(\mathbf{b}_1)^\perp$，则投影后的格$L' = \pi_1(L)$是$n-1$维格，其行列式满足：

$$\det(L') = \frac{\det(L)}{\|\mathbf{b}_1\|}$$

在子格$L'$中，$\pi_1(\mathbf{b}_2), \dots, \pi_1(\mathbf{b}_n)$构成LLL-δ约简基，首向量满足：

$$\|\pi_1(\mathbf{b}_2)\| \leq 2^{(n-2)/4} \cdot \det(L')^{1/(n-1)}$$

由于$\|\mathbf{b}_2\| \leq \sqrt{\|\pi_1(\mathbf{b}_2)\|^2 + \mu_{2,1}^2 \|\mathbf{b}_1\|^2} \leq \|\pi_1(\mathbf{b}_2)\| + \frac{1}{2} \|\mathbf{b}_1\|$，结合$\det(L') = \det(L)/\|\mathbf{b}_1\|$，最终可得：

$$\|\mathbf{b}_2\| \leq 2^{n/4} \cdot \left( \frac{\det(L)}{\|\mathbf{b}_1\|} \right)^{1/(n-1)}$$

HM5

Solution1

假设存在区分器$\mathcal{D}$能以优势$\epsilon$区分$H_i$与$H_{i+1}$，则构造算法A，其输入为决策LWE挑战样本$(\mathbf{a}, b^*)$，需判断$b^* = \mathbf{a}^T \mathbf{s} + e$或均匀随机。

随机选择$i \in \{0, \dots, t-1\}$，生成$\mathbf{s}_1, \dots, \mathbf{s}_t \gets \mathbb{Z}_q^n$和$e_1, \dots, e_t \gets \chi$。对$j \leq i$，设置$b_j$为均匀随机；对$j > i+1$，设置$b_j = \mathbf{a}^T \mathbf{s}_j + e_j$（$b_{i+1} = b^*$）。

不同$\mathbf{s}_j$和$e_j$独立生成，保证混合分布中未被替换的$b_j$仍为合法LWE样本。每一步仅替换一个$b_j$，通过决策LWE的困难性保证不可区分性。若$\mathcal{D}$的优势为$\epsilon$，则$\mathcal{A}$的优势为$\epsilon/t$，在$t$为多项式时仍不可忽略。

若决策LWE是困难的，则$\epsilon$必须可忽略，因此$H_0$与$H_t$不可区分，即在决策LWE问题的困难性假设下，多秘密LWE分布与均匀随机分布计算不可区分。

Solution2

设安全参数为$\lambda$，定义以下参数：

• 维度：$n = \text{poly}(\lambda)$
• 模数：$q = \text{poly}(\lambda)$（通常取素数）
• 错误分布：$\chi$为$\mathbb{Z}_q$上的离散高斯分布，标准差$\sigma = \alpha q$（$\alpha \in (0,1)$）
• 消息空间：$\mathcal{M} = \{0,1\}^k$（$k$为多比特长度）

---

密钥生成

输入：安全参数$\lambda$
输出：公钥$pk$，私钥$sk$

1. 生成LWE矩阵：

   $$\mathbf{A} \gets \mathbb{Z}_q^{n \times m}, \quad \mathbf{s} \gets \chi^n, \quad \mathbf{e} \gets \chi^m$$

   其中$m = O(n \log q)$。

2. 计算公钥矩阵：

   $$\mathbf{B} = \mathbf{A}^T \mathbf{s} + \mathbf{e} \mod q \in \mathbb{Z}_q^m$$

3. 设置密钥：公钥：$pk = (\mathbf{A}, \mathbf{B})$；私钥：$sk = \mathbf{s}$

---

加密

输入：公钥$pk = (\mathbf{A}, \mathbf{B})$，消息$\mathbf{m} \in \{0,1\}^k$
输出：密文$(c_0, c_1, \dots, c_k)$

1. 生成随机向量：

   $$\mathbf{r} \gets \{0,1\}^m$$

2. 计算基础密文分量：

   $$c_0 = \mathbf{A} \mathbf{r} \mod q \in \mathbb{Z}_q^n$$

3. 计算消息加密分量：

   $$\forall i \in \{1, \dots, k\}: \quad c_i = \mathbf{B}^T \mathbf{r} + \lfloor \frac{q}{2} \rfloor m_i + e_i' \mod q \in \mathbb{Z}_q$$

   其中$e_i' \gets \chi$为新增错误项。

---

解密

输入：私钥$sk = \mathbf{s}$，密文$(c_0, c_1, \dots, c_k)$
输出：消息$\mathbf{m} \in \{0,1\}^k$

1. 计算中间量：

   $$\forall i \in \{1, \dots, k\}: \quad d_i = c_i - \mathbf{s}^T c_0 \mod q$$

2. 解码消息比特：

   $$m_i = \begin{cases} 0, & \text{若 } |d_i| \leq \lfloor \frac{q}{4} \rfloor \\ 1, & \text{若 } |d_i| \geq \lfloor \frac{3q}{4} \rfloor \end{cases}$$

---

对每个消息比特$m_i$，解密时：

$$d_i = (\mathbf{B}^T \mathbf{r} + \lfloor \frac{q}{2} \rfloor m_i + e_i') - \mathbf{s}^T \mathbf{A} \mathbf{r} \mod q$$

当总错误项绝对值$< \lfloor \frac{q}{4} \rfloor$时，解密正确。

Solution3

Game0：挑战者生成真实公钥$pk = (\mathbf{A}, \mathbf{B})$，其中$\mathbf{A} \gets \mathbb{Z}_q^{n \times m}$，$\mathbf{s} \gets \chi^n$，$\mathbf{B} = \mathbf{A}^T \mathbf{s} + \mathbf{e} \mod q$（$\mathbf{e} \gets \chi^m$）；敌手$\mathcal{A}$选择消息$\mathbf{m}_0, \mathbf{m}_1 \in \{0,1\}^k$。

挑战者随机选择$b \gets \{0,1\}$，生成密文：

$$c_0 = \mathbf{A} \mathbf{r} \mod q, \quad c_i = \mathbf{B}^T \mathbf{r} + \lfloor q/2 \rfloor m_{b,i} + e_i' \mod q$$

其中$\mathbf{r} \gets \{0,1\}^m$，$e_i' \gets \chi$。敌手输出猜测$b'$，若$b' = b$则获胜。

Game1：在Game0情况下，$\mathbf{B} \gets \mathbb{Z}_q^m$为均匀随机向量（而非$\mathbf{B} = \mathbf{A}^T \mathbf{s} + \mathbf{e}$）。

Game2：在Game1情况下，$c_0 \gets \mathbb{Z}_q^n$和$c_i \gets \mathbb{Z}_q$均为均匀随机值。

---

证明Game0 ≈ Game1：假设存在敌手$\mathcal{A}$能区分Game0与Game1，则可构造算法$\mathcal{B}$解决决策LWE问题：

输入为决策LWE样本$(\mathbf{A}, \mathbf{B}^*)$，需判断$\mathbf{B}^* = \mathbf{A}^T \mathbf{s} + \mathbf{e}$或均匀随机。将$\mathbf{A}$作为公钥矩阵，$\mathbf{B}^*$作为公钥向量。当$\mathcal{A}$提交$\mathbf{m}_0, \mathbf{m}_1$时，生成密文：

$$c_0 = \mathbf{A} \mathbf{r}, \quad c_i = (\mathbf{B}^*)^T \mathbf{r} + \lfloor q/2 \rfloor m_{b,i} + e_i'$$

若$\mathcal{A}$正确区分，则$\mathcal{B}$判定$\mathbf{B}^*$为LWE样本；否则判定为均匀随机。

---

证明Game1 ≈ Game2：设$\mathbf{A} \gets \mathbb{Z}_q^{n \times m}$为均匀随机矩阵，$\mathbf{r} \gets \{0,1\}^m$，则当$m \geq (n + \omega(\log \lambda)) \log q$时，分布$(\mathbf{A}, \mathbf{A} \mathbf{r})$与均匀分布$(\mathbf{A}, \mathbf{u})$的统计距离可忽略。

对于密文分量$c_0 = \mathbf{A} \mathbf{r}$：由LHL，$(\mathbf{A}, c_0)$与均匀分布$(\mathbf{A}, \mathbf{u})$统计接近；对于密文分量$c_i = \mathbf{B}^T \mathbf{r} + \lfloor q/2 \rfloor m_{b,i} + e_i'$：由于$\mathbf{B}$均匀随机且$\mathbf{r} \gets \{0,1\}^m$，$\mathbf{B}^T \mathbf{r}$接近均匀分布，加性错误$e_i'$和消息项$\lfloor q/2 \rfloor m_{b,i}$不影响均匀性。因此在Game1中，密文$(c_0, c_1, \dots, c_k)$与均匀随机分布计算不可区分。

---

因此在决策LWE问题的困难性假设和剩余哈希引理下，双重Regev多比特加密方案满足IND-CPA安全。

HM6

Solution1

假设存在不全为零的标量$y_0, y_1, \dots, y_{d-1} \in \mathbb{Q}$，使得：

$$\sum_{i=0}^{d-1} y_i \cdot \Sigma(a \cdot X^i) = \mathbf{0} \in \mathbb{Q}^d$$

由于$\Sigma$是$\mathbb{Q}$-线性同态，可将线性组合转化为多项式乘法后的嵌入：

$$\Sigma\left( a \cdot \sum_{i=0}^{d-1} y_i X^i \right) = \mathbf{0} \in \mathbb{Q}^d$$

因为$\Sigma$是双射（作为$\mathbb{Q}$-向量空间的同构），当且仅当对应的多项式为零：

$$a \cdot \left( \sum_{i=0}^{d-1} y_i X^i \right) = 0 \in K$$

由于$K$是域且$a \neq 0$，则$a$在$K$中可逆。两边同乘$a^{-1}$得：

$$\sum_{i=0}^{d-1} y_i X^i = 0 \in K$$

在$K$中，$\{X^i\}_{i=0}^{d-1}$是$\mathbb{Q}$-基，因此多项式$\sum_{i=0}^{d-1} y_i X^i = 0$当且仅当所有系数$y_i = 0$。 但这与假设（$y_i$不全为零）矛盾。

Solution2

$R$作为$\mathbb{Z}$-模是自由模，基为$\{1, X, X^2, \dots, X^{d-1}\}$，故$\text{rank}_\mathbb{Z}(R) = d$。系数嵌入$\Sigma$将多项式$a = \sum_{i=0}^{d-1} a_i X^i$映射为向量$(a_0, a_1, \dots, a_{d-1})$，是$\mathbb{Z}$-模同构。

设$I \subset R$为非零理想，则存在非零元素$a \in I$。由理想对乘法的封闭性，对任意$i \in \{0,1,\dots,d-1\}$，有$a \cdot X^i \in I$。

根据前一问题的结论，$\{\Sigma(a \cdot X^i)\}_{i=0}^{d-1}$在$\mathbb{Q}^d$中线性无关。由于$a \cdot X^i \in R$，其系数为整数，故$\Sigma(a \cdot X^i) \in \mathbb{Z}^d$。这$d$个向量在$\mathbb{Z}^d$中也是$\mathbb{Z}$-线性无关的。

$\Sigma(I)$包含$d$个$\mathbb{Z}$-线性无关的向量$\{\Sigma(a \cdot X^i)\}$。作为$\mathbb{Z}$-子模，$\Sigma(I)$的秩至少为$d$；但$\Sigma(I) \subset \mathbb{Z}^d$，而$\mathbb{Z}^d$的秩为$d$，故$\text{rank}_\mathbb{Z}(\Sigma(I)) = d$。

$\Sigma(I)$是$\mathbb{Z}^d$的加法子群，自然在$\mathbb{R}^d$中离散，秩为$d$的离散子群即为$\mathbb{R}^d$中的格。

Solution3

定义元素$s_i \in I$为：

$$s_i = s \cdot X^{i-1} \quad \text{对} \ 1 \leq i \leq d$$

由于$I$是理想且$s \in I$，根据理想对乘法的封闭性，$s_i \in I$。

设$s = \sum_{k=0}^{d-1} a_k X^k$，则其系数嵌入向量为$\Sigma(s) = (a_0, a_1, \dots, a_{d-1})$，范数为：

$$\|\Sigma(s)\| = \sqrt{\sum_{k=0}^{d-1} a_k^2}$$

根据环结构$X^d \equiv -1$，$s \cdot X^{i-1}$的系数是原系数的循环移位并伴随符号变化。

循环移位和符号变化不改变平方和，因此：

$$\|\Sigma(s_i)\| = \sqrt{\sum_{k=0}^{d-1} a_k^2} = \|\Sigma(s)\|$$

由$K = \mathbb{Q}[X]/(X^d + 1)$是域，非零元$s \in I$在$K$中可逆。根据前题结论，$\{\Sigma(s \cdot X^{i-1})\}_{i=1}^d$在$\mathbb{Q}^d$中线性无关，进而在$\mathbb{R}^d$中线性无关。