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

[isis agora lovecruft]

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.)

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 1240 bytes
Desc: Digital signature
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20170224/50394872/attachment.sig>