Quiz 4 - Interactive Proofs (IP)
Sign in to Google to save your progress. Learn more
Email *
True/False *
13 points
Knowledge soundness is a meaningful notion when a prover claims that there are *no* satisfying assignments to a system of constraints
Knowledge soundness is a meaningful notion for the sumcheck protocol
Knowledge soundness (as defined in lecture 2) implies soundness
Non-interactive implies publicly verifiable
Vector commitments are as expressive as polynomial commitments
Polynomial extensions are distance amplifying encodings
Multivariate polynomial encoding reduces the total degree by an exponential factor compared to univariate polynomial encoding
The verifier in the sum-check protocol is oblivious to the polynomial g whose evaluations are being summed until the last step
The uniqueness of multilinear extensions is crucial for the soundness of the sumcheck protocol
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
The polynomial IOP for SAT (from lecture 4) can be transformed into a SNARK with verifier complexity independent of circuit size
The polynomial IOP for SAT (from lecture 4) has optimal prover complexity
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
Clear form
This form was created inside of UC Berkeley. Report Abuse