What I'd like to do is to have the Prover store a value x where x remains hidden.

From x, I'd like to extract one blob r1, and save it in the Verifier's database.

Later in the future, the same Prover who holds x should compute a new r2 from x, such that one cannot easily extract x from r2 and send it over to Verifier.

Verifier can compare that two distinct and different r1 and r2 and know that they came from the same x without revealing anything about x.

I hope I didn't misunderstand that this is what Fiat-shamir Heuristic tried to do.

I made a working example of this based on this code snippet structure:

p = Proof()
# k is random
p1.k = random()

# g is a prime number
p1.g = random_prime()

# where r is the commitment of Prover
p1.r = p1.g^p1.k

# Where y is the public key of x
p1.y = p1.g^p1.k

# Where c is the hash of the commitment
p1.c = Hash(p1.r)

# Where s is the output of the commitment algorithm
p1.s = p1.k + p1.c*x

# Now, the Verifier needs to store all of the above somewhere
# After X months, the same Prover makes another blob (call it p2) and wants to verify if p1 came from the same x as p2

(r1, r2) = (p1.g^p1.s * p1.y^p1.c, p2.g^p2.s * p2.y^p1.c)

What I'd like to know is the following:

  • Is there a known library or codebase that does this somewhere?
  • What is a safe bit-size for the prime numbers used (is 4096-bits realistically even possible?)
  • Assuming an attacker can sniff c and r and everything about p1 and p2. How realistically is it that they can A) forge a similar packet and B) extract x?

Much appreciated


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.