Quiz【Lecture 1 】 Introduction to Zero Knowledge Interactive Proofs

[Demian101]

下方提交

[Pupil1999]

Student name: Walker

Q1

1. Which of the following are true about Interactive Proofs (IP)?
2. IP is a superset of NP - true
3. IP prover runs in probabilistic polynomial time - False
4. IP verifier runs in probabilistic polynomial time - True
5. IP verifier is only allowed to use public randomness, i.e., it reveals the randomness it samples -False

We can refer to the definitions:
==NP-Language==
$L$ is an NP language, if there is a $poly(|x|)$ time verifier $V$:
Completeness: If $x\in L$, there is a $poly(|x|)$-long witness $w\in\{0,1\}^*$, s.t. $V(x, w)=1$
Soundness: If $x\notin L$, there is no witness. That is, for all $w\in\{0,1\}$, $V(x, w)=0$

==IP-Language==
$L$ is an IP language, if there is an interactive proof system $(\mathcal{P}, \mathcal{V})$:
Completeness: If $x\in L$, $Pr[(\mathcal{P}, \mathcal{V})(x)=accept]\geq c$
Soundness: If $x\notin L$, for every $\mathcal{P}^*$, $Pr[(\mathcal{P}, \mathcal{V})(x)=accept]\leq \epsilon (n)$

Q2

How is IP different from NP?

1. IP prover is computationally more powerful than NP prover - False
2. IP verifier is computationally more efficient - False
3. There is interaction between prover and verifier in IP - True
4. IP Verifier is randomized - True
5. Soundness guarantee in IP is probabilistic - True

In the same way, please refer to the definitions for reasons.

Q3

The lecture discussed an IP for Quadratic Residuosity (QR), where the proof was divided into two parts. Which of the following are true about this IP proof?

1. Given both parts of a proof, the verifier is convinced that y is a quadratic residue with 100% certainty - True
2. Given one part of a proof, a computationally bounded verifier can not learn any information from this part about the witness, i.e., sqrt(y), but an unbounded verifier can - False
3. The verifier eventually learns both parts of the proof, which convinces it that the claim is correct - False
4. The verifier never learns both parts of a proof but the ability of the prover to show either part eventually convinces the verifier that the claim is correct - True
5. This IP proof is actually a proof of knowledge - True

Reasons:

1. Given two parts, the $\mathcal{V}$ can compute $x=(rx)/r$ to get the residue.
2. For proof content $r$, the value is randomly sampled thus the $\mathcal{V}$ knows nothing.
3. In each iteration, the $\mathcal{V}$ will get answer for a different $r$, so he won't get both parts of proof.
4. If $\mathcal{P}$ doesn't know the residue, he can pass each iteration with prob $\frac{1}{2}$. After $n$ iterations, he can only pass the check with negligible prob $\frac{1}{2^n}$.
5. $\exists E^\mathcal{P}(y, N)\{r, rx\}\rightarrow x: x^2 \equiv y \, mod\, N$.

Q4

Which of the following are true for the Graph 3-coloring IP discussed in the lecture?

1. This protocol is only honest verifier zero-knowledge because a malicious verifier can start piecing together information on the graph coloring with each iteration and break zero-knowledge - False
2. The protocol only offers computational zero-knowledge due to the use of commitments - True
3. Due to NP-completeness of graph 3-coloring, this protocol implies all of NP has a zero-knowledge IP - True

Reasons:

1. The malicious verifier can only extract knowledge after $|E|$ iterations instead of in a single iteration.
2. Unbounded computer is supposed to reverse the commitment and get the hidden values.
3. Each NP problem can be reduced to NPC problem, so.

Q5

Which of the following are true for simulation and extraction?

1. The simulator can create the view without the prover because it is computationally unbounded unlike the verifier - False
2. The simulator can simulate the view without the prover because it can sample the view out of order - True
3. The extractor can extract the witness only from successful provers - True
4. The extractor can extract the witness because it is computationally unbounded - False

Reasons:

1. Simulator is also in $PPT$ by definition.
2. Simulator only has access to the verifier.
3. Obviously, we cannot extract knowledge from idiots.
4. Extractor is also in $PPT$ by definition.

[Einstellung]

student name: 饭卡

1. Which of the following are true about Interactive Proofs(IP)?

   • IP is a superset of NP (true)

   在交互式证明系统中，Prover证明过程可以是非多项式时间的，这意味着他能解决NP问题，也可以解决NP超集问题。因此，IP是NP的超集。

   • IP prover runs in probabilistic polynomial time (False)

   证明者没有运行时间限制。我们关心证明者的证明或者说陈述的事实的正确性，而不关心其运行时间。

   • IP verifier runs in probabilistic polynomial time (True)

   我们希望验证过程是足够简洁的，只需要花费有限资源就可以验证结果。因此对Verifier而言，需要在概率多项式时间内验证结果。

   • IP verifier is only allowed to use public randomness, i.e, it reveals the randomness it samples. (False)

   prover并不会把他生成的的随机数本身暴露给verifier，会暴露出演算修改过后的值让verifier无法还原出原始的随机数。

2. How is IP different from NP

   • IP prover is computationally more powerful than NP prover (False)

   在交互式证明中IP是NP的超集，所以其计算能力要大于等于NP

   • IP verifier is computationally more efficient (False)

   IP 验证者和 NP 验证者在计算效率上并无明显区别。它们都需要在多项式时间内完成验证过程。

   • There is interaction between prover and verifier in IP (True)
   • IP Verifier is randomized (True)

   在交互式证明过程中，任何都可以充当验证者并向Prover发起证明挑战。

   • Soundness guarantee in IP is probabilistic (True)

   IP系统的健壮性也就是证明的有效性是通过交互次数保证的。通过交互n次我们可以在置信度区间内认为证明是正确的。但总是不能100%的保证，特别是如果交互次数n较小，可能会存在prover欺骗行为而无法被有效发现的情况。

3. The lecture discussed an IP for Quadratic Residuosity (QR), where the proof was divided into two parts. Which of the following are true about this IP proof?

   • Given both parts of a proof, the verifier is convinced that y is a quadratic residue with 100% certainty. (False)

   在交互式证明系统中，健全性（Soundness）是概率性的，而不是绝对确定的。即使证明者能提供所有部分的证明，验证者也不能100%确定y是平方剩余。

   • Given one part of a proof, a computationally bounded verifier can not learn any information from this part about the witness, i.e., sqrt(y), but an unbounded verifier can (False)

   对于计算能力有限的验证者，他不能从证明的任何一部分学到关于prover的信息。(Verifier有提取器，可以提取知识参考[读心术：从零知识证明中提取「知识」](https://secbit.io/blog/2019/08/28/extractor-and-proof-of-knowledge/))，verifier提取知识是靠作弊的方式

   • The verifier eventually learns both parts of the proof, which convinces it that the claim is correct (False)

   verifier不会了解所有的部分，prover只向verifier展示了witness部分

   • The verifier never learns both parts of a proof but the ability of the prover to show either part eventually convinces the verifier that the claim is correct (True)

   通过不断交互的过程让verifier最终相信prover确实掌握了知识。

   • This IP proof is actually a proof of knowledge (True)

4. Which of the following are true for the Graph 3-coloring IP discussed in the lecture?

   • This protocol is only honest verifier zero-knowledge because a malicious verifier can start piecing together information on the graph coloring with each iteration and break zero-knowledge. (False)

   • The protocol only offers computational zero-knowledge due to the use of commitments (True)

   • Due to NP-completeness of graph 3-coloring, this protocol implies all of NP has a zero-knowledge IP (True)

5. Which of the following are true for simulation and extraction?

• The simulator can create the view without the prover because it is computationally unbounded unlike the verifier (False)

模拟器是通过作弊的方式来来欺骗verifier，而不是通过无限计算能力。

• The simulator can simulate the view without the prover because it can sample the view out of order (True)

模拟器可以用类似时光倒流的作弊方式打破原来的顺序。

• The extractor can extract the witness only from successful provers (True)

提取器可以提取任何witness，但是如果prover进行欺骗行为，那么提取出来的witness可以认为是虚假无效的（和prover声明的prove不符），所以认为只能说是witness只能来自successful provers.

• The extractor can extract the witness because it is computationally unbounded (False)

提取器通过作弊的方式来提取知识而不是计算资源。