Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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$?

share|improve this question
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
up vote 3 down vote accepted

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.

share|improve this answer
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 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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.