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/cryptography%20%26%20mathematics/zero%20knowledge/Efficient%20Identification%20and%20Signatures%20for%20Smart%20Cards%20(1989)%20-%20Schnorr.pdf > [1]: > 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@moderncrypto.org > https://moderncrypto.org/mailman/listinfo/curves > -- "Man is born free, but everywhere he is in chains". --Rousseau. _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves