Zero Knowledge

Question 1

What are the security properties of Zero Knowledge?

Answer 1

1- Completeness
If the prover knows the secret, then the proof succeeds with overwhelming probability.
2 - Soundness
There exists a polynomial-time knowledge extractor M, such that if an adversary can execute the protocol successfully with non-negligible probability, then M can be used to extract from Eve the knowledge to run the protocol successfully
Protecting the proof of knowledge against a dishonest prover
3- Zero-knowledge
To prove smth is zero-knowledge We construct a simulator that does not have access to the secret or the prover. Simulator needs to come up with a transcript thats exactly the same as the real zero knowledge proof

Question 2

How does the Schnorr Key Generation work?

Answer 2

1 - Create a cyclic group G, that is a subgroup of (Zp)* with generator g with a prime order q
2 - Choose random x in Zq
3 -Compute y = g^x (mod q)

output:
pk = (G, q, g, y)
sk = (G, q, g, x)

Question 3

For a schnorr identification protocol:
p = 48731
q = 443
g = 11444
x = 357 # private key
y = 45776 # public key

Commitment: r = 274, t = g^r mod p

Challenge c = 129

Whats the response? and the verification?

Answer 3

s = 255
26233 = 26233
sagemath
p = 48731
q = 443
g = 11444
x = 357 # private key
y = 45776 # public key

r = 274
t = (g**r) % p

c = 129

s = (r + c*x) % q
print(s)
print((gs) % p )
print((t*(yc)) % p)

Question 4

What is the difference between Multi-round schnorr protocol and the schnorr identification protocol?

Answer 4

The key differences between the two protocols seem to be:

1 - Number of Rounds: The Multi-Round protocol involves several iterations to reduce the error probability, whereas the Schnorr Identification Protocol is described as a single-round process.
2 - Challenge Set: In the Multi-Round protocol, the challenge is chosen from a smaller set {0,1}, while in the Schnorr Identification Protocol, the challenge appears to be chosen from a larger set {0,1}^ t, indicating that the challenge can be more complex (potentially a binary string of length t).

Question 5

Which are properties of Zero-Knowledge Proofs of Knowledge?

Answer 5

-> Completeness
->Soundness
-> Zero-Knowledge

Question 6

You are asked to prove that the Schnorr identification protocol is zero-knowledge by creating a simulator. The group setup is prime modulus p=587, generator g=12 with order q=293. The public key is y=516.
In one step of the simulation, the simulator chose
a random challenge c = 103
a random response s = 115
What is the correct witness t to complete a forged transcript of a zero-knowledge proof?

Answer 6

343

sagemath
p = 587
q = 293
g = 12
y = 516 # public key
#Challenge
c = 103
s = 115
t = ((gs) / (yc)) % p
t

Question 7

Alice and Bob engage in a Zero-knowledge proof, in which Alice convinces Bob that she knows the secrets x and r such that C = g^x h^r (mod p), where C, g, h, and p are public pieces of information. What does Bob learn?

Answer 7

→ Bob learns that Alice statement is valid. Nothing else.

Question 8

Alice and Bob engage in a multi-round Schnorr identification protocol, in which the challenge is just 1 uniformly chosen random bit. To reach an error probability of 2-45, that is, the probability that the adversary can convince the verifier without knowing the secret, how many rounds of the 3-move Schnorr protocol must be executed?

Answer 8

→ 45
Correct. Each round has an error probability of 1/2. To reach a probability of 1/245 based on independent challenges, one needs to repeat the experiment 45 times.

Question 9

To transform a Schnorr identification protocol in a signature scheme, how must the message be integrated in the scheme?

Answer 9

→ Hash the message together with the witness as challenge for the scheme: c = H(m||t)

Correct. We combine the message and the witness under a cryptographically strong hash function.

Question 10

To answer this question successfully, be sure to read the slides on the Zero-Knowledge proof notation introduced in the lecture and especially the PK Compilation Rules.
A complex zero-knowledge proof system is set up with the following parameters:
Modulus N = 95477, generators S=961, Z=22581, R=52302.
The user was issued a signature (A, e, v) =(5315, 13, 19758) for a message m = 23.
Your task is to analyze a proof of knowledge in the Camenisch-Stadler notation introduced in the lecture: PK{(m, e, v):
Z = R^m S^v A^e (mod N) }
If the randomnesses were chosen as rm = 59; re = 39; rv = 117; yielding a commitment C=68943, and the challenge c selected as 213, what is the response sm produced for message m?

Answer 10

4958

Well done. Remember: for each secret we are choosing a random exponent corresponding to it. Once we received the challenge c, we compute a response for each secret. For example, for secret message m we have the
response sm = rm + cm.
So literally
rm = 59
c = 213
m = 23
rm + c *m

Question 10

What trick enables a Simulator without access to a secret to create a valid transcript of a zero- knowledge proof indistinguishable from a real protocol run?

Answer 10

-> Computing the transcript “backwards” starting from random challenge and responses.
Correct. One can compute the transcript if one does not adhere to the protocol order.

Question 11

What are PK Compilation rules?
For
PK{(x):

y = g^x(mod p)
}

Answer 11

• For each declared secret x , choose a corresponding randomness rx
• Compute the commitments in the same structure as the proven equation t = g ^ (rx) (mod p)
• Replace each secret x with the corresponding randomness rx
• For each secret x, compute a response sx = rx + cx

Question 12

You are asked to prove that the Schnorr identification protocol is zero-knowledge by creating a simulator. The group setup is prime modulus p=48731, generator g=11444 with order q=443. The public key is y=45776.
In one step of the simulation, the simulator chose
a random challenge c = 129
a random response s = 255
What is the correct witness t to complete a forged transcript of a zero-knowledge proof?

Answer 12

t = g^s/ y^c (mod p)
37123
sagemath
p = 48731
q = 443
g = 11444
y = 45776 # public key

c = 129
s = 255

t = ((gs)/ (yc))% p
t

Question 13

How is Schnorr also a signature scheme?

Answer 13

Signing Process:

The signer chooses a random number r from the group Z q
They compute a commitment t = g^r modp.
Then, the signer computes a challenge c by hashing the concatenation of the message m and the commitment t. The hash function H produces a fixed-size output which acts as the challenge.
The signer computes the response s as
s = r−cx mod q, where x is the signer’s private key.
The signature is the pair
σ=(s,c).

Verifying:
The verifier computes a term tv using the signature and the signer’s public key y as
g ^s y^c mod p.
The verifier then checks if the challenge c matches the hash of the concatenation of the message m and the term tv. If c equals H(m∥t v ), the signature is valid.