[curves] Non-interactive zero knowledge proofs of discrete log equivalence
isis agora lovecruft
isis at patternsinthevoid.net
Thu Feb 23 17:31:29 PST 2017
Oleg Andreev transcribed 5.9K bytes:
> > On 15 Feb 2017, at 15:48, Tony Arcieri <bascule at gmail.com> wrote:
> > One of the many things discussed in this post is non-interactive zero
> > knowledge proofs of discrete log equivalence ("DLEQ"): proving that two
> > curve points are ultimately different scalar multiples of the same curve
> > point without revealing the common base point or the discrete logs
> > themselves.
> > I was particularly curious if there were any papers about this idea. I
> > had come across similar work (h/t Philipp Jovanovic) in this general
> > subject area (I believe by EPFL?) but I have not specifically found any
> > papers on this topic:
> > https://github.com/dedis/crypto/blob/master/proof/dleq.go#L104 <https://github.com/dedis/crypto/blob/master/proof/dleq.go#L104>
> > If anyone knows of papers about this particular problem, I'd be very interested in reading them.
> DLEQ proves that two curve points P and Q share the _same_ discrete log with respect to two different bases:
> P = x*G
> Q = x*J
Oleg's description is correct.
The particular scheme I think you're looking for is also sometimes referred
to as a Schnorr sigma protocol, and it's described in a 1989 paper with the
not-so-helpful title: "Efficient Identification and Signatures for
A scheme I'm working on right now for Tor bridge distribution with Henry de
Valence also needs DLEQ for proving knowledge of a signature, as does George
Tankersley for proving that a user has already recently solved Cloudflare's
The Schorr sigma protocol is variously spread throughout the paper, it's
kind of the "Identification Protocol" in §2 and kind of the signature
protocol that's later on. The non-interactive form of that protocol in
ECDLP for a curve E(𝔽_q) with additive notation is NIPK(x; h = g x (mod q))
for some group generators g and h, and x, a scalar in 𝕫/l𝕫 where l is the
order of the basepoint:
To create a proof, one takes w, a random element of prime-order group G with
order q, and multiplies by (some group generator, see below for impact of
choice) g to create point W
W ← g w
state ← (g,h,m,W),
where m is the message. (The message in the context of (EC)DLEQ is usually
an empty string.) Next one hashes the state:
C ← H(state) (mod q).
Finally, the prover creates
R ← w - C x (mod q),
where x is the scalar one wants to prove knowledge of; the proof is then (C, R).
The verifier checks by doing
W' ← g R + h C,
state' ← (g,h,m,W')
and hashes it:
C' ← H(state') (mod q),
then checks that C == C', thus proving h = g^x without knowledge of x.
Proof that C = C' iff h = g^x (mod q):
H(s) = H(s')
s = s' [assuming second-preimage resistance]
(g,h,m,W) = (g,h,m,W')
W = W'
gw = g R + h C
= g(w - x C) + h C
= g w - g x C + h C
= g w - g x H(s) + h H(s)
= g w - g x H(s) + g x H(s) [assuming h = g x]
= g w
Schnorr notes in his original paper that "the protocol is not zero knowledge
because the tripel" (W',R,C) "may be a particular solution to the equation"
W' = g R + h C, however, with randomly chosen basepoints each time the
protocol is run (i.e. the prover chooses a new g and h each time and sends
these along with the proof), I don't see the issue. (I might just be missing
Another paper worth reading is (1988) "Zero Knowledge Proofs of Identity" by
Feige, Fiat, and Shamir. 
Hopefully that helps!
♥Ⓐ isis agora lovecruft
Current Keys: https://fyb.patternsinthevoid.net/isis.txt
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 1240 bytes
Desc: Digital signature
More information about the Curves