To add yet another paper: "On Σ-protocols" by Ivan Damgård http://www.cs.au.dk/~ivan/Sigma.pdf
is a very nice primer on Σ-protocols in general. It explains some background on the mentioned honest-verifier zero-knowledge and the Fiat-Shamir transform. The protocol for dlog equivalence is mentioned in Section 5 as an exercise. Best, Tim On Thu, 2017-02-23 at 21:16 -0800, Watson Ladd wrote: > On Thu, Feb 23, 2017 at 5:31 PM, isis agora lovecruft > <i...@patternsinthevoid.net> wrote: > > Oleg Andreev transcribed 5.9K bytes: > > > > On 15 Feb 2017, at 15:48, Tony Arcieri <basc...@gmail.com> > > > > wrote: > > > > [snip] > > > > > > 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. > > > > > > Correction: > > > > > > 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." [0] > > > > 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 > > CAPTCHAs. > > > > 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. [1] > > > > Hopefully that helps! > > > > [0]: https://github.com/isislovecruft/library--/blob/master/cryptog > > raphy%20%26%20mathematics/zero%20knowledge/Efficient%20Identificati > > on%20and%20Signatures%20for%20Smart%20Cards%20(1989)%20- > > %20Schnorr.pdf > > [1]: https://github.com/isislovecruft/library--/blob/master/cryptog > > raphy%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@moderncrypto.org > > https://moderncrypto.org/mailman/listinfo/curves > > > > > _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves