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

[Watson Ladd]

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



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.