[curves] Non-interactive zero knowledge proofs of discrete log equivalence

[Tim Ruffing]

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
> <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:
> > 
> > [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 at moderncrypto.org
> > https://moderncrypto.org/mailman/listinfo/curves
> > 
> 
> 
>