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.) 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
signature.asc
Description: Digital signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves