[curves] Non-interactive zero knowledge proofs of discrete log equivalence
watsonbladd at gmail.com
Thu Feb 23 21:16:10 PST 2017
On Thu, Feb 23, 2017 at 5:31 PM, isis agora lovecruft
<isis at patternsinthevoid.net> wrote:
> 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
> Hello Toni,
> 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
> Smartcards." 
> 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
> Then, set
> 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,
> and creates
> 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
> something obvious.)
It's not obvious at all, but sigma protocols are honest verifier
zero-knowledge, which is different from zero-knowledge. The
Fiat-Shamir transform converts these to noninteractive zero-knowledge
protocols in the ROM, so in practice this is good enough.
> Another paper worth reading is (1988) "Zero Knowledge Proofs of Identity" by
> Feige, Fiat, and Shamir. 
> Hopefully that helps!
> : https://github.com/isislovecruft/library--/blob/master/cryptography%20%26%20mathematics/zero%20knowledge/Efficient%20Identification%20and%20Signatures%20for%20Smart%20Cards%20(1989)%20-%20Schnorr.pdf
> : https://github.com/isislovecruft/library--/blob/master/cryptography%20%26%20mathematics/zero%20knowledge/Zero-Knowledge%20Proofs%20of%20Identity%20%281988%29%20-%20Feige%2C%20Fiat%2C%20Shamir.pdf
> Best regards,
> ♥Ⓐ isis agora lovecruft
> OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
> Current Keys: https://fyb.patternsinthevoid.net/isis.txt
> Curves mailing list
> Curves at moderncrypto.org
"Man is born free, but everywhere he is in chains".
More information about the Curves