2
$\begingroup$

I have been going through some old lecture notes of mine and found this interesting question.

Assuming we reduce the challenge space for the verifier from $\mathbb ℤ_q$ to $\mathbb ℤ_{\log(𝑞)}$, does security still hold for Schnorr's verifier?

My thought process so far is that it does. While the probability of guessing a challenge is considerably higher, it doesn't necessarily mean that it compromises the security of the verifier.

$\endgroup$

2 Answers 2

2
$\begingroup$

It all depends on what "reducing the challenge space" means. The most direct interpretation of the question is that we consider a normal 3-round Schnorr protocol, with the only modification being that the challenge space is much smaller. Well, guessing a challenge allows the attacker to forge proof. There's already a question and corresponding answers.

But let's see if we can get some numbers here based on the information provided in the question. Assuming the verifier has good randomness, the probability of a good guess has a geometric distribution. Consequently, the expected number of guesses to match the challenge is $\log q$. For practical applications, q is about $2^{256}$. So, we expect a good guess in about 178 attempts. This is far from a "cryptographically significant" number.

The sagemath below simulates a forgery attempt. (De)comment the appropriate lines in the while loop, you can get a feel for how long it takes to forge a proof when using either the full or a partial challenge space. Changing the challenge in a round need not be the end of the world. As the other answer describes, parallel repetition may still make the "effective" challenge space larger while preserving soundness.

# Schnorr ID protocol over secp256k1
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
K = GF(p)
a = K(0x0000000000000000000000000000000000000000000000000000000000000000)
b = K(0x0000000000000000000000000000000000000000000000000000000000000007)
E = EllipticCurve(K, (a, b))
G = E(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
E.set_order(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 * 0x1)
q = E.order()
Fq = GF(q)
qq = ceil(log(q))
print("qq = {}".format(qq))
# secret dlog value
x = Fq.random_element()
X = x * G
solved = False
counter = 0
while not solved:
   # e = Fq.random_element()
   # e_guess = Fq.random_element()
   e = randint(0, qq)
   e_guess = randint(0, qq)
   solved = (e_guess == e)
   counter += 1
print("Solved in {} iterations".format(counter))
# Forge a a proof of knowledge of the discrete logarithm of X
s = Fq.random_element()
R = s * G - e_guess * X 
assert s * G == R + e * X
print("Forged!")
$\endgroup$
1
$\begingroup$

For special-sound $\Sigma$-protocols (such as Schnorr's ID scheme), the challenge length can be changed arbitrarily. E.g. to increase the challenge length from $t$ to $2t$, run the protocol twice in parallel. To decrease the challenge space to $t'<t$, append $t'-t$ zeros to the length $t'$ challenge. For a challenge length $t$, the soundness error (the probability of accepting a false statement) is $2^{-t}$. Details can be found in Ivan Damgård's lecture notes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.