# Non-Interactive Zero-Knowledge-Proof for discret Logarithm?

In a Non-Interactive $Zero-Knowledge-Proof$, the challenge is chosen by the Prover.

I am trying to find a Non-Interactive Zero-Knowledge-Proof based on the following problem:

DISCRETE LOGARITHM

Input: Prime number $p$, generator $g$ of $Z^{*}_{p}$ , and $y\in Z^{∗}_{p}$ .

Question: find $x \in \lbrace1, . . . , p − 1\rbrace$ with $y ≡ g^{x}\;mod\;p$?

• The problem statement is a bit strange. Proving existence of such an x is moot. If g is a generator of the full group, then by definition, such an x must exist. – Maeher Dec 5 '12 at 8:58
• @Kemo: Why do you have dollar signs around the first "Zero-Knowledge-Proof"? Is the "challenge" you refer to the same as the "common reference string" in the wikipedia article? – user991 Dec 5 '12 at 9:27

It seems, what you are looking for is a Non-Interactive Zero Knowledge Proof of Knowledge (NIZKPok) of a discrete logarithm.

The Schnorr identification scheme is an (interactive) ZKPoK and can be transformed in to a non interactive one (in the random oracle model) using the Fiat-Shamir transformation.

It works in any group, is perfectly sound and computationally zero knowledge under the discrete logarithm assumption for that group in the random oracle model.

http://publikationen.stub.uni-frankfurt.de/files/4280/schnorr.pdf

http://en.wikipedia.org/wiki/Schnorr_signature

• How can a simulator repoduce the proof in probabilistic polinomial time without actually know x in a non-interactive proof? – Onheiron Feb 22 '15 at 20:11
• the extractor that produces x does need to rewind the prover – relG Aug 29 '18 at 15:46
• Actually I'm looking for a reference that really proves Schnorr is a Nizk-PoK for discrete log in the RO model..anyone know one? – relG Aug 29 '18 at 15:46