Discussion:
question regarding proofs of knowledge v/s proofs of membership
Amitabh Saxena
2006-06-23 13:19:28 UTC
This may be a trivial question.. but I would appreciate if someone
could clear my confusion.

Suppose we are working in the field F_q, with g being a generator (let
q=2p+1, p prime so that testing generators is easy). We assume that
computing discrete logs in F_q is hard.. Now consider the language

L={h \in F_q | exists x \in Z*_q such that h=g^x}

Clearly L is in P because for all h \in F_q, such an x exists.

however, since computing discrete logs is hard, how do I express the
concept of "knowing the discrete log" using a language outside BPP..
(i.e. I want to prove knowlede of discrete logs in F_q, rather than
just prove that such a discrete log exists)

I understand that the problem of "computing discrete logs" is not in P,
since there is no PPT algorithm.. so if a protocol proves "knowledge of
discrete log", then this is definitely a proof of a language outside
BPP. (yes or no?)

best,
Amitabh
David Wagner
2006-06-27 08:08:50 UTC
Post by Amitabh Saxena
however, since computing discrete logs is hard, how do I express the
concept of "knowing the discrete log" using a language outside BPP..
concept in theoretical cryptography that addresses exactly what you want
to know. You should be able to find some discussion in a serious textbook
on crypto theory. Also, I seem to recall that either Oded Goldreich or
Mihir Bellare had some kind of introductory survey article on the subject.

You can find a very concise introduction to ZK proofs of knowledge in
Section 3 of these scribe notes for a crypto course I've co-taught:
http://www.cs.berkeley.edu/~luca/cs276/notes/lecturezk2.ps
2006-07-06 07:51:41 UTC
Hi,

If I got you right, you want to prove to someone that you actually know
the discrete log x of g^x in F_q. Maybe consider the following ZK
protocol: P -prover , V- verifier

Common input : g^x where x is the prover "secret"
1. V - chooses r,y at random from F_q. Compute c=y*(g^x)^r and sends it
to the prover
2. P - Computes y'=(c^(1/x))/g^r. sends y' to the verifier.
3. V accepts if y'=y.

If I am not wrong (and please correct me if I do)
This is a IP ZK under the DDH assumption.
Amitabh Saxena
2006-07-10 09:52:43 UTC
Actually, I am not looking for a new proof of knowledge of discrete
log.. I just want to understand more clearly the concept of "proof of
knowledge" vs "proof of membership"

From Wagner's mail (and previous research), I found that this idea is
generally defined using "extractors" and "knowledge tightness", which
is what I am trying to understand now.

According to me, a Proof of knowledge is based on a Search problem,
while a proof of membership is based on a decision problem..
Hi,
If I got you right, you want to prove to someone that you actually know
the discrete log x of g^x in F_q. Maybe consider the following ZK
protocol: P -prover , V- verifier
Common input : g^x where x is the prover "secret"
1. V - chooses r,y at random from F_q. Compute c=y*(g^x)^r and sends it
to the prover
2. P - Computes y'=(c^(1/x))/g^r. sends y' to the verifier.
3. V accepts if y'=y.
If I am not wrong (and please correct me if I do)
This is a IP ZK under the DDH assumption.
Perhaps I misunderstood your idea, but AFAIK, this proof if wrong..

c= y*g^(xr)
Thus y'=c^(1/x)/g^r = y^(1/x) which is not equal to y.

Also, for ZK you must show a simulator of some sort
Amitabh Saxena
2006-08-15 18:07:10 UTC
Can anyone give an example of "proof of membership" that is NOT a
"proof of knowledge". (The proofs of Quadratic Residue, Graph
Isomorphism, Hamiltonian cycle, etc are all proofs of membership and
proofs of knowledge at the same time.)

In other words, I want an example of a proof that enables a verifier to
be "convinced" that a given graph has a hamiltonian cycle, yet at the
same time does not allow the verifier to extract the cycle even after

The same could be done for Quadratic residues (i.e. being convinced
that a given x is indeed a QR mod n, yet at the same time, not allowing
extraction of the sq. root of x)
Nick Hopper
2006-08-17 06:04:01 UTC
Post by Amitabh Saxena
Can anyone give an example of "proof of membership" that is NOT a
"proof of knowledge". (The proofs of Quadratic Residue, Graph
Isomorphism, Hamiltonian cycle, etc are all proofs of membership and
proofs of knowledge at the same time.)
In other words, I want an example of a proof that enables a verifier to
be "convinced" that a given graph has a hamiltonian cycle, yet at the
same time does not allow the verifier to extract the cycle even after
The same could be done for Quadratic residues (i.e. being convinced
that a given x is indeed a QR mod n, yet at the same time, not allowing
extraction of the sq. root of x)
"Resettable ZK proofs" are proof systems that are ZK even when you can
rewind the prover (so are by definition not proofs of knowledge). See:

http://www.wisdom.weizmann.ac.il/~oded/p_cggm.html

For a construction of rZK proofs for any language in NP.

-Nick
Susan
2006-08-17 06:04:24 UTC
In Chapter 18 of "Modern cryptography: theory and practice " by Wenbo
Mao, there
exists an example of such proof: protocol 18.6, in the protocol, prover
can prove two dis log are equal, but can not gurantee he knows the dis
log.

Amitabh Saxena =E5=86=99=E9=81=93=EF=BC=9A
Post by Amitabh Saxena
Can anyone give an example of "proof of membership" that is NOT a
"proof of knowledge". (The proofs of Quadratic Residue, Graph
Isomorphism, Hamiltonian cycle, etc are all proofs of membership and
proofs of knowledge at the same time.)
In other words, I want an example of a proof that enables a verifier to
be "convinced" that a given graph has a hamiltonian cycle, yet at the
same time does not allow the verifier to extract the cycle even after
The same could be done for Quadratic residues (i.e. being convinced
that a given x is indeed a QR mod n, yet at the same time, not allowing
extraction of the sq. root of x)
Ertugrul Soeylemez
2006-08-17 06:04:15 UTC
Post by Amitabh Saxena
Can anyone give an example of "proof of membership" that is NOT a
"proof of knowledge". (The proofs of Quadratic Residue, Graph
Isomorphism, Hamiltonian cycle, etc are all proofs of membership and
proofs of knowledge at the same time.)
If I understood your question, a few very basic ones: You can prove a
number to be composite without knowing anything about its factors (and
being practically unable to discover anything about them). You can
prove certain functions to be invertible, without being able to actually
invert them (practically).

The problem is: To be able to prove membership without proving
knowledge, naturally there is no knowledge needed to prove this
(otherwise you would prove knowledge at the same time). In other words:
Your help, probably as the knower, isn't needed for the proof of
membership. One can do it alone.

Well, one other example: You can prove a number to _not_ be a quadratic
residue. This is a proof of membership. However, there is no knowledge
to prove in this case, so I think, this isn't what you're looking for.

Regards,
E.S.