[curves] Non-interactive zero knowledge proofs of discrete log equivalence
philipp at jovanovic.io
Thu Feb 16 00:43:37 PST 2017
> On 16 Feb 2017, at 00:05, Tony Arcieri <bascule at gmail.com> wrote:
> 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:
> 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!
> 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:
Thanks for the advertisement. :) And yes I am at EPFL.
> 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  (to be presented at IEEE S&P’17 in May), which in particular uses public verifiable secret sharing (PVSS)  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 
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems - Amos Fiat and Adi Shamir 
- Unique Ring Signatures: A Practical Construction - Matthew Franklin and Haibin Zhang 
In particular,  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,
More information about the Curves