Post by Oleg Andreev Post by Tony Arcieri
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
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
If anyone knows of papers about this particular problem, I'd be very interested in reading them.
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