2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Maeher Dec 5 '12 at 8:58
  • $\begingroup$ @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? $\endgroup$ – user991 Dec 5 '12 at 9:27
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How can a simulator repoduce the proof in probabilistic polinomial time without actually know x in a non-interactive proof? $\endgroup$ – Onheiron Feb 22 '15 at 20:11
  • $\begingroup$ the extractor that produces x does need to rewind the prover $\endgroup$ – relG Aug 29 '18 at 15:46
  • $\begingroup$ 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? $\endgroup$ – relG Aug 29 '18 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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