Zero Knowledge Proofs and Sigma Protocols

Question 1

Definition of language

Question 2

Definition of complexity class

Question 2

Definition of decision problem and relation with search problem

Question 3

Examples of complexity classes

Question 4

Definition of NP complexity class

Question 5

NP-complete problems and relation between P and NP

Question 6

Examples of NP-complete problems

Question 7

P vs NP wrt one-way functions

Question 8

Definition of k-round interaction

Question 9

Definition of IP complexity class

Question 10

IP class with respect to PSPACE class and NP class with example

Question 11

Definition of graph and of graph isomorphism

Question 12

GNI and IP

Question 13

Prove that GNI belongs to IP

Question 14

Definition of Zero Knowledge Proof

Question 15

Definition of Honest-Verifier Zero Knowledge

Question 16

GI and PKZ

Question 17

Prove that GI belongs to PZK

Question 18

Prove that if there exists a one-way function then NP belongs / equal to CZK

Question 19

Definition of proof of knowledge

Answer 19

cheating is as difficult as crafting a witness + formal def with p and k

Question 20

Definition of Zero-Knowledge Proof of Knowledge

Question 21

GI and PZKPoK

Question 22

Prove that GI belongs to PZKPoK

Question 23

Definition of Sigma Protocol: what is it, what is it made of and which properties does it have

Question 24

Sigma protocol for Graph Isomorphism: construction, proof and soundness error

Question 25

Sigma protocol for Discrete Logarithm: construction, proof and soundness error

Question 26

Sigma protocol for Square Root Problem: construction, proof and soundness error

Answer 26

resp = x^c * r

Question 27

Definition of Identification Scheme

Answer 27

4 algo gen, P1 p2 v gen prende 1^lambda e genera pk e sk

Question 28

Experiment for Identification Scheme

Question 29

Definition of Secure Identification Scheme

Question 30

Theorem: Sigma protocols as secure identification schemes and proof

Answer 30

**Theorem** Let L be language in NP and assume that there exists no PPT adversary that given x ∈ L finds a witness for x with non-negligible probability. Let Π be a Σ-protocol for a ZKPoK for L, together with an algorithm to generate pairs (x , w ) with x ∈ L and w a witness of this fact. Then Π is a secure identification protocol, where the prover has public key x and secret key w. **Proof**. The completeness of Π implies that Π is indeed an identification protocol. The special soundness of Π implies that an adversary A can fool the verifier only by finding the secret key w, which is infeasible by hypothesis. Finally, the honest verifier zero-knowledge of Π implies that the adversary A gains no information from the oracle Transsk, since the transcripts that it produces can be simulated by an oracle that does not know sk.

Question 31

Security parameter lambda for an identification protocol

Answer 31

* in order to achieve a security level λ, the parameters must be selected so that solving the search problem for L (with the best known algorithms) has average-case complexity proportional to 2λ. * Moreover, to achieve a security level λ, the number R of rounds should be at least λ/log(1/p), where p is the soundness error of the Σ-protocol and log is the logarithm in base 2. This ensures that the probability that a cheater passes the identification is less than 2−λ, and protects from brute-force attacks.

Question 32

Communication cost

Question 33

Construction and proof of Schnorr Identification Protocol

Answer 33

= sigma protocol per DL parte tutto da un gruppo e i parametri x e c vengono presi da Z p