# 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? –  Ricky Demer 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

-

The challenge length algorithm: $\:$ return 0

The Prove algorithm: $\:$ return the empty string

The Verify algorithm: $\:$ return True

The Simulator: $\:$ return the empty string as both the challenge and the proof

-
sorry, i mean the prover has the value of the discrete logarithm $x$, and he want to convenes the verifier that he knows the value of $x$ without giving the verifier this value .. –  Sam Dec 5 '12 at 9:13
the question is edited. –  Sam Dec 5 '12 at 9:21