A prover has a secret exponent $x$, two public bases $g$ and $h$, and a public RSA modulus $N$ of which no party knows the totient/factors. All inputs other than $N$ are coprime with $N$ with overwhelming probability. She publishes $a = g^x\bmod N$ and $b = h^x\bmod N$, but she needs an NIZK that she used the same exponent for both $a$ and $b$. How can she create a proof (assuming access to randomness beacons and commitments)? The proof doesn't need to be truly zero-knowledge as long as finding x is still hard.

This is similar the problem solved by Schnorr's proof of knowledge of a discrete logarithm, but the difference is the RSA modulus, who's factors are unknown and not guaranteed to be safe primes.

Update: A modification of Chaum-Pedersen is used on page 215 of Shoup 00 that looks promising. In the context, the RSA modulus is known to be composed of safe primes, but I am unclear as to what the actual requirements are. The paper for Diogenes claims to apply that method to an RSA number that is composed of primes congruent to $3\mod4$, but it doesn't explain how this is done.

  • 1
    $\begingroup$ Quarter-baked idea [update: that does not work, see refutation by poncho]: what if prover made a NIZK proof that they know $x$ with $a\,b^{-1}\equiv(g\,h^{-1})^x\pmod N$? $\endgroup$
    – fgrieu
    Jul 5 at 6:49
  • 1
    $\begingroup$ I think that Chaum-Pedersen is a more precise analogy than Schnorr. The issue is that we cannot select blinding values and responses uniformly modulo an unknown group order and a significant obstruction to providing a zero-knowledge simulator. $\endgroup$
    – Daniel S
    Jul 5 at 8:18
  • $\begingroup$ @DanielS But what if we allow the leaking of trivial information about $x$? $x$ is already a pseudo-random integer that I don't know the exact distribution of yet, but the number of possible values is at least on the order of $2^4096$. $\endgroup$
    – Nic
    Jul 5 at 14:58
  • 2
    $\begingroup$ @fgrieu: the quarter-baked idea doesn't work; what if they pick $b, x$ arbitrarily, and set $a = b(gh^{-1})^x$... $\endgroup$
    – poncho
    Jul 5 at 15:27
  • 1
    $\begingroup$ What about proving that if we take a generator $g'$ such that $h=g'^y$ and $g=g'^w$ then $ab^{-1}=g^{w+x+y-x}=g^{w-y}=gh^{-1}$? I haven't really thought about it, though. $\endgroup$
    – JAAAY
    Jul 6 at 8:42


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.