Implement needed anonymous credentials in library

[dbosk]

We might have use of the code from Anon-Pass and adapt it to handle NIZK proofs. This relates to #27 . The paper P-signatures and Noninteractive Anonymous Credentials has a theoretical solution that might work for us, but probably no implementation.

ZeroCoin and ZeroCash both use zero-knowledge proofs, or to be exact zkSNARKs (zero-knowledge Succint Non-interactive ARguments), which should work for us.

[dbosk]

Maybe there are some things from IBM Idemix.

[HePineau]

It should be noted that ZeroCash is an evolution of the ZeroCoin protocol, and was introduced in 2014 as such.

The ZeroCash implementation of zkSNARKS is based on the following paper which is a collaboration between the MIT and the Zero team. We can find the code they've used on their Zcash GitHub.

I'll try to go deeper into the Zcash implementation this week.

[HePineau]

Also concerning NIZK, a standalone library was created based on the proofs invented by Groth and Sarai that might be of interest to us.

[dbosk]

Very much indeed, great work!

On Wed 29 Nov 2017 16:09:21 GMT, HePineau wrote:

Also concerning NIZK, a standalone library was created based on the proofs invented by Groth and Sarai that might be of interested to us.

[dbosk]

We must look into what the zkSNARKs of Zcash etc. requires.

On Fri 08 Dec 2017 22:52:05 GMT, Pierre-Louis Roman wrote:

Mailing it so I don't forget on Monday.

Remember I said there is some magic numbers for zcash? It's not a problem of implementation but of usage of zk-SNARKs all together. This is from the recent bulletproof paper [1]:

Current proposals for confidential transactions zero-knowledge proofs [PBF ] have either been prohibitively large or required a trusted setup. Neither is desirable. While one could use succinct zero-knowledge proofs (SNARKs) [BSCG 13], they all require a trusted setup, which means that everyone needs to trust that the setup was performed correctly.

So if you're not ok with having a trusted setup in your system, I guess zk-SNARKs, and zcash, is not the way to go. On the other hand, Monero doesn't use zk-proofs and will switch to bulletproofs since they're more efficient than their current design [2]. And Monero is developed by a community, not a company (of former researchers) like zcash.

And here is the jubjub elliptic curve [3] I was talking about for zcash. They still need a trusted setup but at least transactions won't be a pain in the ass to check. Updates to be made live in September 2018 [4].

PLR

[1] https://eprint.iacr.org/2017/1066 [2] https://getmonero.org/2017/12/07/Monero-Compatible-Bulletproofs.html [3] https://z.cash/blog/cultivating-sapling-faster-zksnarks.html [4] https://z.cash/blog/roadmap-update-2017-12.html

Maybe the P-signatures paper is a better approach, but then I don't think there is any existing implementation. (But maybe there is.)

[dbosk]

The zkSNARKs used in Zcash require a global setup. Which is cumbersome and not something desirable. If this and this can be avoided, that would probably be better.

[dbosk]

We can use the Idemix protocol and combine this with a distance-bounding version of Schnorr. The details are currently in Section 6 of the paper.

[dbosk]

From the Anon-Pass paper:

While the protocols of Damgård et al. [12] were cryptographically heavy, Camenisch et al. [4] gave asymptotic improvements resulted in a more practical scheme. Neither protocol, however, was implemented. Our aim is to design and implement an anonymous subscription system which is practical and deployable for existing subscription services.

[dbosk]

From Camenisch:

The relevant Idemix code is available from the P2ABCengine. However, the PRFs are not implemented out of the box. (But we'll probably go for Anon-Pass for that.)

There is also Charm: A tool for rapid cryptographic prototyping, which might be useful for implementing the crypto parts.