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

[Trevor Perrin]

On Thu, Feb 16, 2017 at 12:43 AM, Philipp Jovanovic
<philipp at jovanovic.io> wrote:
> Hi Toni,
>
>> On 16 Feb 2017, at 00:05, Tony Arcieri <bascule at gmail.com> wrote:
>
>> One of the many things discussed in this post is non-interactive zero knowledge proofs of discrete log equivalence ("DLEQ")
[...]
>> 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