Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

2 Answers 2

up vote 2 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.

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

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

share|improve this answer
add comment

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
add comment

Your Answer

 
discard

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.