1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Your last paragraph sounds like you might want to Google "socialist millionaires' problem". $\endgroup$ – Ilmari Karonen Aug 10 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 at 0:09

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.