I've been reading up on Sigma Protocols and Fiat-Shamir Heuristic. There is a small problem I see here that is possibly already solved, but I'd like to know if it has a solution.

  • Peggy wants to prove to Victor that she has $x$
  • They both agree on a constant $g$ and a prime number $p$, as well as a "puzzle", usually in the form of a discrete logarithm $g^x$.

For any verifier, there must be, as semi-public knowledge, the value of $g^x$.

In my head, the value of $g^x$ is constant and it could be used as an identifier against Peggy.

Is there a way to have a dynamic value of $g^x$ that would work just as good to solve the puzzle of proving Peggy's ownership without having it being a constant value, that can be used as a user identifier?

P.S: I do realize that one can utilize a public/private keypair to represent $x$ and $g^x$ respectively. This still means that a public key is user identifiable.

P.S.S: The objective of my research is to prove the equality of two $x$'s, with two separate owners, without sharing a $g^x$ public "puzzle" of $x$. I have a feeling that a Diffie-Hellman tuple could be used here for a one-time-session shared secret, but I am having a hard time understanding how to place all the pieces together...

Many thanks

  • 1
    $\begingroup$ Your last paragraph sounds like you might want to Google "socialist millionaires' problem". $\endgroup$ Aug 10, 2019 at 17:40
  • $\begingroup$ Password authenticated key exchange for an interactive protocol, as well as ECC derived keypairs like what's used for Bitcoin hardened hierarchical deterministic wallets if you want to allow it to be asynchronous + "stealth addresses". $\endgroup$
    – Natanael
    Aug 11, 2019 at 0:09


Your Answer

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