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

[Tony Arcieri]

Hello all,

We have just published a blog post on how we have attempted to harden a
system we're developing (a "blockchain"-based money-moving system) against
certain types of post-quantum attacks, and also provide a contingency plan
for post-quantum attacks:

https://blog.chain.com/preparing-for-a-quantum-future-45535b316314#.jqhdrrmhi

Personally I'm not too concerned about these sorts of attacks happening any
time soon, but having a contingency plan that doesn't hinge on still
shaky-seeming post-quantum algorithms seems like a good idea to me. If you
have any feedback on this post, feel free to ping me off-list or start
specific threads about anything we've claimed here that may be bogus.

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

If anyone knows of papers about this particular problem, I'd be very
interested in reading them.

[Oleg Andreev]

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

Post by Tony Arcieri
Hello all,
https://blog.chain.com/preparing-for-a-quantum-future-45535b316314#.jqhdrrmhi <https://blog.chain.com/preparing-for-a-quantum-future-45535b316314#.jqhdrrmhi>
Personally I'm not too concerned about these sorts of attacks happening any time soon, but having a contingency plan that doesn't hinge on still shaky-seeming post-quantum algorithms seems like a good idea to me. If you have any feedback on this post, feel free to ping me off-list or start specific threads about anything we've claimed here that may be bogus.
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.
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.
--
Tony Arcieri

[isis agora lovecruft]

[snip]

Post by Oleg Andreev

Post by Tony Arcieri
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
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.

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,

[Watson Ladd]

On Thu, Feb 23, 2017 at 5:31 PM, isis agora lovecruft

Post by isis agora lovecruft
[snip]

Post by Oleg Andreev

Post by Tony Arcieri
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
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.

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
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
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')
C' ← H(state') (mod q),
then checks that C == C', thus proving h = g^x without knowledge of x.
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.

Post by isis agora lovecruft
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
https://moderncrypto.org/mailman/listinfo/curves

[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

Post by Watson Ladd
On Thu, Feb 23, 2017 at 5:31 PM, isis agora lovecruft

Post by isis agora lovecruft
[snip]

Post by Oleg Andreev

Post by Tony Arcieri
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
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.

DLEQ proves that two curve points P and Q share the _same_
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
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
  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')
  C' ← H(state') (mod q),
then checks that C == C', thus proving h = g^x without knowledge of x.
       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.

Post by isis agora lovecruft
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
https://moderncrypto.org/mailman/listinfo/curves

[Tony Arcieri]

On Thu, Feb 23, 2017 at 5:31 PM, isis agora lovecruft <

Post by isis agora lovecruft
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!

Awesome, thanks for the pointers, Iris!

[Philipp Jovanovic]

Hi Toni,

Post by Tony Arcieri
Hello all,
https://blog.chain.com/preparing-for-a-quantum-future-45535b316314#.jqhdrrmhi
Personally I'm not too concerned about these sorts of attacks happening any time soon, but having a contingency plan that doesn't hinge on still shaky-seeming post-quantum algorithms seems like a good idea to me. If you have any feedback on this post, feel free to ping me off-list or start specific threads about anything we've claimed here that may be bogus.

Interesting idea, thanks for sharing!

Post by Tony Arcieri
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.
https://github.com/dedis/crypto/blob/master/proof/dleq.go#L104

Thanks for the advertisement. :) And yes I am at EPFL.

Post by Tony Arcieri
If anyone knows of papers about this particular problem, I'd be very interested in reading them.

To provide some context: We’ve been using NIZK DLEQ proofs for our decentralized randomness beacon project [1] (to be presented at IEEE S&P’17 in May), which in particular uses public verifiable secret sharing (PVSS) [2] as one core building block. In my investigations around that project, I found three papers that are relevant for NIZK DLEQ proofs (mostly by the usual suspects):

- Wallet Databases with Observers - David Chaum and Torben Pryds Pedersen [3]
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems - Amos Fiat and Adi Shamir [4]
- Unique Ring Signatures: A Practical Construction - Matthew Franklin and Haibin Zhang [5]

In particular, [5] gives a summary of NIZK DLEQ proofs in Section 3 (also referring to Chaum’s paper) that I used as a basis for the above code.

Hope this helps.

All the best,
Philipp

[1] https://eprint.iacr.org/2016/1067
[2] https://www.win.tue.nl/~berry/papers/crypto99.pdf
[3] http://www.cs.elte.hu/~rfid/chaum_pedersen.pdf
[4] http://www.math.uni-frankfurt.de/~dmst/teaching/SS2012/Vorlesung/Fiat.Shamir.pdf
[5] http://fc13.ifca.ai/proc/5-1.pdf

[Trevor Perrin]

On Thu, Feb 16, 2017 at 12:43 AM, Philipp Jovanovic

Post by Philipp Jovanovic
Hi Toni,

Post by Tony Arcieri
One of the many things discussed in this post is non-interactive zero knowledge proofs of discrete log equivalence ("DLEQ")

[...]

Post by Philipp Jovanovic

Post by Tony Arcieri
I was particularly curious if there were any papers about this idea.

This is the "Chaum-Pedersen" idea used by discrete-log VRFs
("Verifiable Random Functions") or "unique signatures", based on a
generator g and key pair (x, g^x):
- map some input to a generator h
- calculate an output = h^x
- calculate an accompanying Schnorr-style
proof-of-discrete-log-equivalence between g^x and h^x

So in that form, this is part of proposals like CONIKS [1], VXEdDSA
[2], and NSEC5 [3].

Philipp had some good references, here's a couple more:

"Efficient Signature Schemes with Tight Reductions to the
Diffie-Hellman Problem" [4]

"Proof Systems for General Statements about Discrete Logarithms" [5].

Trevor

[1] https://coniks.cs.princeton.edu/research.html
[2] https://whispersystems.org/docs/specifications/xeddsa/
[3] https://eprint.iacr.org/2016/083.pdf
[4] https://www.cs.umd.edu/~jkatz/papers/dh-sigs-full.pdf
[5] ftp://ftp.inf.ethz.ch/pub/crypto/publications/CamSta97b.pdf