Quiz【Lecture 4】 Interactive Proofs (IP)

[luckyyang]

Quiz 链接: https://docs.google.com/forms/d/e/1FAIpQLSdoSIqGrrXzgh7wQRkgaNgd6IUNiUvBU1qk-J38cRnT1ip12Q/viewform

Quiz 解析

1. Knowledge soundness is a meaningful notion when a prover claims that there are no satisfying assignments to a system of constraints
   False
   Knowledge soundness 的前提是 system of constraints 存在 witness 并且 prover 知道 witness。NP 问题才有 Knowledge soundness，而题目表示的问题是 unsatisfiable 问题，它不属于 NP，所以没有 witness，也就没有 Knowledge soundness

2. Knowledge soundness is a meaningful notion for the sumcheck protocol
   False
   因为没有 witness

3. Knowledge soundness (as defined in lecture 2) implies soundness
   True
   knowledge soundness is "stronger" than soundness, the prover MUST know the existing witness.

4. Non-interactive implies publicly verifiable
   False
   两者没有直接的关系，Non-interactive & private verifiable 是存在的

5. Vector commitments are as expressive as polynomial commitments
   False
   https://eprint.iacr.org/2022/1515
   Vector commitments and their generalizations to polynomial commitments and functional commitments are key building blocks for many cryptographic protocols.

6. Polynomial extensions are distance amplifying encodings
   True
   If there are any disagreeing inputs such that their evaluations on f and g are not equal, then the MLEs of these functions f​,g​ will disagree on almost all the points within their domain!
   The multilinear extensions "blow up & amplify" the tiny differences between f,g, so that you can see the resulting extreme differences in the extensions f​,g​
   distance amplifying encodings：距离放大编码

7. Multivariate polynomial encoding reduces the total degree by an exponential factor compared to univariate polynomial encoding
   True
   Multivariate polynomial encoding: 整数 d 可以表示至少 2^d 个参数
   univariate polynomial encoding: 整数 d 可以表示至多 d-1 个参数

8. The verifier in the sum-check protocol is oblivious to the polynomial g whose evaluations are being summed until the last step
   True
   最后一步才用 g 求值，之前的步骤 verifier 对 g 是 oblivious（无感知的）

9. The uniqueness of multilinear extensions is crucial for the soundness of the sumcheck protocol
   False
   sumcheck 协议本身不需要 multilinear。某些情况需要使用将一个 function 转化为 MLE，然后做 sumcheck。比如课程中的例子 Counting Triangles in a Graph。
   sumcheck 的 soundness 取决于 set 的大小

10. The claim f(x) = g(x) for all k-bit inputs, where f and g are low degree polynomials over a large field, can be reduced to the following sumcheck claim: $\sum_{x \in {0,1}^k} (f(x)-g(x)) = 0$
    False
    sumcheck 只能证明和为 0，不能证明每个值的相减都为 0。加个平方就可以做 sumcheck 了: $\sum_{x \in {0,1}^k} (f(x)-g(x))^2 = 0$
    或者 Can be reduced to $f(x) - g(x) = q(x) * z_H(x)$

11. The polynomial IOP for SAT (from lecture 4) can be transformed into a SNARK with verifier complexity independent of circuit size
    False
    V runs in time $O(log S)$

12. The polynomial IOP for SAT (from lecture 4) has optimal prover complexity
    True
    Interactive Proofs: P runtime is O(d×2l×eval)
    polynomial IOP for SAT: P performs O(S) field operations given a witness w.
    因为 prover 能达到的最优的复杂度就是 linear (O(S))

13. Extending the polynomial IOP for SAT in the natural way to support gates with n inputs will result in a sumcheck protocol over (n+1) * logS variables
    True
    S 是门的数量
    如果 2 个输入，1 个输出，那么 sumcheck 要检查所有的（2 个输入 + 1 个输出）= 3，sumcheck 要检查 logS^3 = 3 logS
    这里每个门有 n 个输入，结果为 (n+1)logS