1
$\begingroup$

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

$\endgroup$

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.