# 第 3 课 练习 ​

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

1. Verifier 在与 $m$ 互质的元素中均匀地随机选取一个 $s\in {\mathbb{Z}}_{m}$，同时抛硬币 $b{←}_{R}\left\{0,1\right\}$。 设

Verifier 将 $y$ 发送给 Prover 并挑战 Prover 以确定 $b$

2. Prover 计算 $QR\left(m,y\right)$ 并将其值发送回 Verifier

3. 如果 Verifier 从 Prover 收到的值确实等于 $b$，则 Verifier 接受； 否则它拒绝。

• (a) 完备性：如果 $QR\left(m,x\right)=0$ 并且双方都按照协议行事，那么验证者总是接受。

• (b) 可靠性：如果 $QR\left(m,x\right)=1$，那么无论 Prover 做什么（Prover 不必遵循协议），Verifer 都会以 $\ge 1/2$ 的概率拒绝

ASSUMPTION: The Prover can compute $QR\left(m,x\right)$ for all $m,x$

COMMON INPUT: positive integers $m,x$

GOAL: the Prover wants to convince the Verifer that $QR\left(m,x\right)=0$

PROTOCOL

1. The Verifier picks a random $s\in {\mathbb{Z}}_{m}$ uniformly among elements relatively prime to $m$, and also tosses a coin $b{←}_{R}\left\{0,1\right\}$. Set

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

1. The Prover computes $QR\left(m,y\right)$ and sends its value back to the Verifier

2. The Verifier accepts if the value it received from the Prover is indeed equal to $b$; otherwise it rejects.

• (a) Completeness: if $QR\left(m,x\right)=0$ and both parties behave according to the protocol, then the Verifier always accepts.

• (b) Soundness: if $QR\left(m,x\right)=1$, then no matter what the Prover does (the Prover does not have to follow the protocol), the Verifer rejects with probability $\ge 1/2$

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

1. Prover 在与 $m$ 互质的剩余中随机选择一个均匀的 $t\in {\mathbb{Z}}_{m}$。 Prover 将 $y←x{t}^{2}modm$ 发送给 Verifier。

2. Verifier 抛硬币 $b{←}_{R}\left\{0,1\right\}$ 并将 $b$ 发送给 Prover。

3. Prover 收到 $b$ 并将$u$值发送给 Verifier

4. 验证者接受证明如果

否则拒绝。

• (a) 完备性：如果双方都按照协议行事，那么 Verifier 总是接受。

• (b) 可靠性：如果 $QR\left(m,x\right)=0$（特别是，Prover 不知道任何有效的 $s$ ），那么无论 Prover 做什么，Verifier 都以 $\ge 1/2$ 的几率拒绝。

• (b*) 知识可靠性：对于任何使得Verifier接受的证明算法，如果允许Verifier同时查询$b\in \left\{0,1\right\}$的两个值（对于 相同的 $t$ )，则 Verifier 可以从 Prover 中提取秘密 $s$。 （这里的重点是除非证明者“知道”$s$，否则证明者无法说服验证者。）

• (c) 零知识：无论验证者做什么（验证者的行为可能与协议不同），验证者都可以在不与证明者交互的情况下自行模拟整个交互，这样如果验证者接受，那么记录下来的信息与实际交互几乎不可区分。

提示：想象模拟器自己生成一个随机的 $u$ 而不是从 Prover 获取 $u$

（这部分有点棘手，因为允许对抗性验证器的行为与协议不同 - 请记住我们试图展示的是，无论验证器做什么，它都不会从证明者那里学到关于 $s$ 的信息 验证者不可能简单地自行生成。如果您想查看解决方案，请参阅 Barak 笔记中的定理 13.6 的证明。）

COMMON INPUT: positive integers $m,x$ with $\mathrm{gcd}\left(m,x\right)=1$

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

GOAL: the Prover wants to convince the Verifier that $QR\left(m,x\right)=1$ without revealing any information about $s$

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

PROTOCOL

1. The Prover picks a random $t\in {\mathbb{Z}}_{m}$ uniform among residues relatively prime to $m$. The Prover sends $y←x{t}^{2}modm$ to the Verifier.

2. The Verifier flips a coin $b{←}_{R}\left\{0,1\right\}$ and sends $b$ to the Prover.

3. The Prover receives $b$ and sends to the Verifier the value of

4. The Verifier accepts if

and rejects otherwise.

• (a) Completeness: If both parties behaves according to the protocol, then the Verifier always accepts.

• (b) Soundness: If $QR\left(m,x\right)=0$ (in particular, the Prover does not know any valid $s$ ), then no matter what the Prover does, the Verifer rejects with probability $\ge 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 \left\{0,1\right\}$ (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 ​

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

$e:\mathbb{G}×\mathbb{G}\to {\mathbb{G}}_{T}$

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

$e:\mathbb{G}×\mathbb{G}\to {\mathbb{G}}_{T}$

Give an efficient algorithm for deciding, given $\alpha g,\beta g,y\in \mathbb{G}$ (with unknown $\alpha ,\beta \in {\mathbb{Z}}_{q}$), whether $\alpha \beta 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 ​

1. 映射 Pairing $e:{\mathbb{G}}_{0}×{\mathbb{G}}_{1}\to {\mathbb{G}}_{T}$，其中${\mathbb{G}}_{0},{\mathbb{G}}_{1},{\mathbb{G}}_{T}$ 是素数阶 $p$ 的阿贝尔群（以加法写出），生成元分别是 ${g}_{0},{g}_{1},{g}_{T}$

2. 哈希函数 $H$${\mathbb{G}}_{1}$ 中取值

BLS签名方案定义为：

• $\mathrm{KeyGen}\left(\right)$: 选择随机（私钥）$sk=\alpha ←{}_{R}{\mathbb{Z}}_{q}$ 并设置（公钥）$pk←\alpha {g}_{0}\in {\mathbb{G}}_{0}$
• $\mathrm{Sign}\left(sk,m\right)$: 输出 $\sigma ←\alpha H\left(m\right)\in {\mathbb{G}}_{1}$ 作为消息 $m$ 上的签名
• $\mathrm{Verify}\left(pk,m,\sigma \right)$ ：如果 $e\left({g}_{0},\sigma \right)=e\left(pk,H\left(m\right)\right)$，则接受。

$\sigma ←{\sigma }_{1}+\cdots {\sigma }_{n}\in {\mathbb{G}}_{1}$

$e\left({g}_{0},\sigma \right)=e\left(p{k}_{1},H\left({m}_{1}\right)\right)+\cdots +e\left(p{k}_{n},H\left({m}_{n}\right)\right)$

SETUP

1. Pairing $e:{\mathbb{G}}_{0}×{\mathbb{G}}_{1}\to {\mathbb{G}}_{T}$, where ${\mathbb{G}}_{0},{\mathbb{G}}_{1},{\mathbb{G}}_{T}$ are abelian groups (written additively) of prime order $p$, with generators ${g}_{0},{g}_{1},{g}_{T}$ respectively

2. Hash function $H$ taking values in ${\mathbb{G}}_{1}$

The BLS signature scheme is defined as:

• $\mathrm{KeyGen}\left(\right)$: choose random (secret key) $sk=\alpha ←{}_{R}{\mathbb{Z}}_{q}$ and set (public key) $pk←\alpha {g}_{0}\in {\mathbb{G}}_{0}$
• $\mathrm{Sign}\left(sk,m\right)$: output $\sigma ←\alpha H\left(m\right)\in {\mathbb{G}}_{1}$ as the signature on the message $m$
• $\mathrm{Verify}\left(pk,m,\sigma \right)$ : accept if $e\left({g}_{0},\sigma \right)=e\left(pk,H\left(m\right)\right)$.

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 $\sigma$ for any message $m$ (the forger is free to chose $m$ ) if the forger is given $pk$ but not $sk$. This is called existentially unforgeable under a chosen message attack. Can you specify some computational hardness assumptions?

Signature aggregation. Given triples $\left(p{k}_{i},{m}_{i},{\sigma }_{i}\right)$ for $i=1,\dots ,n$ (coming from $n$ users), we can aggregate these $n$ signatures ${\sigma }_{1},\dots ,{\sigma }_{n}$ into a single signature by simply taking their sum in ${\mathbb{G}}_{1}$ :

$\sigma ←{\sigma }_{1}+\cdots {\sigma }_{n}\in {\mathbb{G}}_{1}$

Given $\left(p{k}_{1},{m}_{1}\right),\dots ,\left(p{k}_{n},{m}_{n}\right)$ and the aggregate signature $\sigma$, show that we can verify that indeed all $n$ users have signed their messages by checking that

$e\left({g}_{0},\sigma \right)=e\left(p{k}_{1},H\left({m}_{1}\right)\right)+\cdots +e\left(p{k}_{n},H\left({m}_{n}\right)\right)$

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