# Proving equivalence of discrete logarithms over a modulus of unknown factorization

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.

• 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$?
– fgrieu
Jul 5 at 6:49
• 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. Jul 5 at 8:18
• @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$.
– Nic
Jul 5 at 14:58
• @fgrieu: the quarter-baked idea doesn't work; what if they pick $b, x$ arbitrarily, and set $a = b(gh^{-1})^x$... Jul 5 at 15:27
• 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. Jul 6 at 8:42