第 3 课练习

给定整数 $x, m$ ，如果 $x$ 在模 $m$ 下是二次剩余，即存在整数 $s$ ，使得 $s^{2} \equiv x (mod m)$ ，则记作 $Q R (m, x) = 1$ ; 如果 $x$ 在模 $m$ 下不是二次剩余，则记作 $Q R (m, x) = 0$ 。

英文原文

Given integers $x, m$ , write $Q R (m, x) = 1$ if $x$ is a quadratic residue $mod m$ , i.e., there exists an integer $s$ such that $s^{2} \equiv x (mod m)$ ; write $Q R (m, x) = 0$ if $x$ is not a quadratic residue $mod m$ .

二次非剩余 Quadratic nonresidue

假定：证明者可以为所有 $m, x$ 计算 $Q R (m, x)$

公共输入：正整数 $m, x$

目标：证明者想要说服验证者 $Q R (m, x) = 0$

协议

Verifier 在与 $m$ 互质的元素中均匀地随机选取一个 $s \in Z_{m}$ ，同时抛硬币 $b \leftarrow_{R} {0, 1}$ 。设
$y \leftarrow {\begin{cases} s^{2} x & if b = 0, \\ s^{2} & if b = 1. \end{cases}$
Verifier 将 $y$ 发送给 Prover 并挑战 Prover 以确定 $b$ 。
Prover 计算 $Q R (m, y)$ 并将其值发送回 Verifier
如果 Verifier 从 Prover 收到的值确实等于 $b$ ，则 Verifier 接受；否则它拒绝。

您需要检查：

(a) 完备性：如果 $Q R (m, x) = 0$ 并且双方都按照协议行事，那么验证者总是接受。
(b) 可靠性：如果 $Q R (m, x) = 1$ ，那么无论 Prover 做什么（Prover 不必遵循协议），Verifer 都会以 $\geq 1 / 2$ 的概率拒绝

英文原文

ASSUMPTION: The Prover can compute $Q R (m, x)$ for all $m, x$

COMMON INPUT: positive integers $m, x$

GOAL: the Prover wants to convince the Verifer that $Q R (m, x) = 0$

PROTOCOL

The Verifier picks a random $s \in Z_{m}$ uniformly among elements relatively prime to $m$ , and also tosses a coin $b \leftarrow_{R} {0, 1}$ . Set

y \leftarrow {\begin{cases} s^{2} x & if b = 0, \\ s^{2} & if b = 1. \end{cases}

The Verifier sends $y$ to the Prover and challenges the Prover to determine $b$ .

The Prover computes $Q R (m, y)$ and sends its value back to the Verifier
The Verifier accepts if the value it received from the Prover is indeed equal to $b$ ; otherwise it rejects.

You are asked to check:

(a) Completeness: if $Q R (m, x) = 0$ and both parties behave according to the protocol, then the Verifier always accepts.
(b) Soundness: if $Q R (m, x) = 1$ , then no matter what the Prover does (the Prover does not have to follow the protocol), the Verifer rejects with probability $\geq 1 / 2$

二次剩余 Quadratic residue

公共输入：正整数 $m, x$ 且满足 $\gcd (m, x) = 1$

私有输入：证明者知道一个秘密整数 $s$ 使得 $s^{2} \equiv x mod m$

目标：证明者想要说服验证者 $Q R (m, x) = 1$ 而不透露有关 $s$ 的任何信息

（请注意，证明者可以通过向验证者发送 $s$ 轻松说服验证者 $Q R (m, x) = 1$ ，但这会完全暴露 $s$ 。）

协议

Prover 在与 $m$ 互质的剩余中随机选择一个均匀的 $t \in Z_{m}$ 。 Prover 将 $y \leftarrow x t^{2} mod m$ 发送给 Verifier。
Verifier 抛硬币 $b \leftarrow_{R} {0, 1}$ 并将 $b$ 发送给 Prover。
Prover 收到 $b$ 并将 $u$ 值发送给 Verifier
$u \leftarrow {\begin{cases} t & if b = 0, \\ s t & if b = 1. \end{cases}$
验证者接受证明如果
$y \equiv {\begin{cases} u^{2} x mod m & if b = 0, \\ u^{2} mod m & if b = 1. \end{cases}$
否则拒绝。

您需要检查：

(a) 完备性：如果双方都按照协议行事，那么 Verifier 总是接受。
(b) 可靠性：如果 $Q R (m, x) = 0$ （特别是，Prover 不知道任何有效的 $s$ ），那么无论 Prover 做什么，Verifier 都以 $\geq 1 / 2$ 的几率拒绝。
(b*) 知识可靠性：对于任何使得Verifier接受的证明算法，如果允许Verifier同时查询 $b \in {0, 1}$ 的两个值（对于相同的 $t$ )，则 Verifier 可以从 Prover 中提取秘密 $s$ 。（这里的重点是除非证明者“知道” $s$ ，否则证明者无法说服验证者。）
(c) 零知识：无论验证者做什么（验证者的行为可能与协议不同），验证者都可以在不与证明者交互的情况下自行模拟整个交互，这样如果验证者接受，那么记录下来的信息与实际交互几乎不可区分。
提示：想象模拟器自己生成一个随机的 $u$ 而不是从 Prover 获取 $u$ 。
（这部分有点棘手，因为允许对抗性验证器的行为与协议不同 - 请记住我们试图展示的是，无论验证器做什么，它都不会从证明者那里学到关于 $s$ 的信息验证者不可能简单地自行生成。如果您想查看解决方案，请参阅 Barak 笔记中的定理 13.6 的证明。）

英文原文

COMMON INPUT: positive integers $m, x$ with $\gcd (m, x) = 1$

PRIVATE INPUT: the Prover knows a secret integer $s$ such that $s^{2} \equiv x mod m$

GOAL: the Prover wants to convince the Verifier that $Q R (m, x) = 1$ without revealing any information about $s$

(Note that the Prover can easily convince the Verifier that $Q R (m, x) = 1$ by sending $s$ to the Verifier, but this would reveal $s$ completely.)

PROTOCOL

The Prover picks a random $t \in Z_{m}$ uniform among residues relatively prime to $m$ . The Prover sends $y \leftarrow x t^{2} mod m$ to the Verifier.
The Verifier flips a coin $b \leftarrow_{R} {0, 1}$ and sends $b$ to the Prover.
The Prover receives $b$ and sends to the Verifier the value of
$u \leftarrow {\begin{cases} t & if b = 0, \\ s t & if b = 1. \end{cases}$
The Verifier accepts if
$y \equiv {\begin{cases} u^{2} x mod m & if b = 0, \\ u^{2} mod m & if b = 1. \end{cases}$
and rejects otherwise.

You are asked to check:

(a) Completeness: If both parties behaves according to the protocol, then the Verifier always accepts.
(b) Soundness: If $Q R (m, x) = 0$ (in particular, the Prover does not know any valid $s$ ), then no matter what the Prover does, the Verifer rejects with probability $\geq 1 / 2$ .
(b*) Knowledge soundness: For any Prover algorithm that leads the Verifier to accept, if the Verifier is allowed to simultaneously query both values of $b \in {0, 1}$ (for the same $t$ ), then the Verifer can extract the secret $s$ from the Prover. (The point here is that the Prover cannot convince the Verifier unless the Prover "knows" $s$ .)
(c) Zero knowledge: No matter what the Verifier does (the Verifier could behave differently from the Protocol), the Verifier could have simulated the entire interaction on its own without interacting with the Prover and such that if the Verifier accepts, then the transcript is indistinguishable from the actual interaction.
Hint: imagine that the simulator generates a random $u$ on its own instead of getting $u$ from the Prover.
(This part is a little tricky, since the adversarial Verifier is allowed to behave differently from the protocol - remember what we are trying to show is that no matter what the Verifier does, it learns no information about $s$ from the Prover that the Verifier could not have simply generated on its own. See the proof of Theorem 13.6 in Barak's notes if you want to see the solution.)

双线性自映射意味着DDH的失效 Self-pairing implies failure of DDH

设 $G$ 和 $G_{T}$ 是相同素数阶 $q$ 的阿贝尔群（以加法写出）。设 $g \in G$ 为生成元。假设我们有一个可有效计算的非退化双线性对

e : G \times G \to G_{T}

给出一个有效的决策算法，给定 $α g, β g, y \in G$ （其中 $α, β \in Z_{q}$ 为未知)，判断是否 $α β g = y$ 。

提示：计算与 $g$ 的映射。

此练习表明确定性 Diffie-Hellman (DDH) 假设对于双线性自映射是错误的。

英文原文

Let $G$ and $G_{T}$ be abelian groups (written additively) of the same prime order $q$ . Let $g \in G$ be a generator. Suppose that we have an efficiently computable nondegenerate bilinear pairing

e : G \times G \to G_{T}

Give an efficient algorithm for deciding, given $α g, β g, y \in G$ (with unknown $α, β \in Z_{q}$ ), whether $α β g = y$ .

Hint: compute the pairing against $g$ .

This exercise shows that the Decisional Diffie-Hellman (DDH) assumption is false for groups with self-pairing.

BLS 签名聚合 BLS signature aggregation

设置

映射 Pairing $e : G_{0} \times G_{1} \to G_{T}$ ，其中 $G_{0}, G_{1}, G_{T}$ 是素数阶 $p$ 的阿贝尔群（以加法写出），生成元分别是 $g_{0}, g_{1}, g_{T}$
哈希函数 $H$ 在 $G_{1}$ 中取值

BLS签名方案定义为：

$KeyGen ()$ : 选择随机（私钥） $s k = α \leftarrow_{R} Z_{q}$ 并设置（公钥） $p k \leftarrow α g_{0} \in G_{0}$
$Sign (s k, m)$ : 输出 $σ \leftarrow α H (m) \in G_{1}$ 作为消息 $m$ 上的签名
$Verify (p k, m, σ)$ ：如果 $e (g_{0}, σ) = e (p k, H (m))$ ，则接受。

检查验证算法是否始终能接受正确签名。还争辩说，如果给伪造者的是 $p k$ 而不是 $s k$ ，那么为任何消息 $m$ （伪造者可以自由选择 $m$ ）想出一个伪造的签名 $σ$ 是计算上不可行的。这在选择的消息攻击下被称为存在不可伪造。你能指定一些计算难度假设吗？

请检查验证算法是否总是接受正确的签名。并论证：在给定 $p k$ 但没有 $s k$ 的情况下，（伪造者可以选择消息）对于任何消息 $m$ ，构造出一个伪造的签名 $σ$ 是计算上不可行的。这被称为 在选择消息攻击下的存在性不可伪造性 。您能找到一些计算难度假设吗？

签名聚合。给定三元组 $(p k_{i}, m_{i}, σ_{i})$ 其中 $i = 1, \dots, n$ （即来自 $n$ 个用户），我们可以聚合这些 $n$ 个签名 $σ_{1}, \dots, σ_{n}$ 通过简单地在 $G_{1}$ 中求和，将其合并为一个签名：

σ \leftarrow σ_{1} + \dots σ_{n} \in G_{1}

给定 $(p k_{1}, m_{1}), \dots, (p k_{n}, m_{n})$ 和聚合签名 $σ$ ，表明我们可以通过检查来验证确实所有 $n$ 用户都签署了他们的消息

e (g_{0}, σ) = e (p k_{1}, H (m_{1})) + \dots + e (p k_{n}, H (m_{n}))

注意：由于 恶意公钥攻击 ，上述签名聚合方案不安全。使方案安全的一种方法是确保所有消息 $m_{i}$ 是不同的，例如，要求每个 $m_{i}$ 以用户的公钥 $p k_{i}$ 开头。

有关 BLS 签名聚合的更多信息，请参阅 https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

英文原文

SETUP

Pairing $e : G_{0} \times G_{1} \to G_{T}$ , where $G_{0}, G_{1}, G_{T}$ are abelian groups (written additively) of prime order $p$ , with generators $g_{0}, g_{1}, g_{T}$ respectively
Hash function $H$ taking values in $G_{1}$

The BLS signature scheme is defined as:

$KeyGen ()$ : choose random (secret key) $s k = α \leftarrow_{R} Z_{q}$ and set (public key) $p k \leftarrow α g_{0} \in G_{0}$
$Sign (s k, m)$ : output $σ \leftarrow α H (m) \in G_{1}$ as the signature on the message $m$
$Verify (p k, m, σ)$ : accept if $e (g_{0}, σ) = e (p k, H (m))$ .

Check that the verification algorithm always accepts a correctly signed signature. Also argue that it is computational infeasible to come up with a forged signature $σ$ for any message $m$ (the forger is free to chose $m$ ) if the forger is given $p k$ but not $s k$ . This is called existentially unforgeable under a chosen message attack. Can you specify some computational hardness assumptions?

Signature aggregation. Given triples $(p k_{i}, m_{i}, σ_{i})$ for $i = 1, \dots, n$ (coming from $n$ users), we can aggregate these $n$ signatures $σ_{1}, \dots, σ_{n}$ into a single signature by simply taking their sum in $G_{1}$ :

σ \leftarrow σ_{1} + \dots σ_{n} \in G_{1}

Given $(p k_{1}, m_{1}), \dots, (p k_{n}, m_{n})$ and the aggregate signature $σ$ , show that we can verify that indeed all $n$ users have signed their messages by checking that

e (g_{0}, σ) = e (p k_{1}, H (m_{1})) + \dots + e (p k_{n}, H (m_{n}))

Note. The above signature aggregation scheme is not secure due to a rogue public key attack. One way to make the scheme secure is to ensure that all messages $m_{i}$ are distinct, for example, by requiring that each $m_{i}$ starts with the user's public key $p k_{i}$ .

For more on BLS signature aggregation, see https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

第 3 课 练习 ​

二次非剩余 Quadratic nonresidue ​

二次剩余 Quadratic residue ​

双线性自映射意味着DDH的失效 Self-pairing implies failure of DDH ​

BLS 签名聚合 BLS signature aggregation ​

第 3 课练习

二次非剩余 Quadratic nonresidue

二次剩余 Quadratic residue

双线性自映射意味着DDH的失效 Self-pairing implies failure of DDH

BLS 签名聚合 BLS signature aggregation