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

Improve this question
$\endgroup$
2
  • 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
    Commented Dec 5, 2012 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
    Commented Dec 5, 2012 at 9:27

1 Answer 1

Reset to default
2
$\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

Improve this answer
$\endgroup$
3
  • $\begingroup$ How can a simulator repoduce the proof in probabilistic polinomial time without actually know x in a non-interactive proof? $\endgroup$
    – Carlo Moretti
    Commented Feb 22, 2015 at 20:11
  • $\begingroup$ the extractor that produces x does need to rewind the prover $\endgroup$
    – relG
    Commented Aug 29, 2018 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
    Commented Aug 29, 2018 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.