HackMD
#4 Home Edition
Proposal: Commit-and-Prove Zero-Knowledge Proof Systems and Extensions
Moderator: Daira Hopwood
Presenters: Jiwon Lee
Authors:
- Daniel Benarroch
- Matteo Campanelli
- Dario Fiore
- Jihye Kim
- Jiwon Lee
- Hyunok Oh
- Anaïs Querol
To be presented on 2021-04-29.
Resources:
Real-time notes
Note Taker: Anaïs Querol and Matteo Campanelli
Commit-and-Prove WG started on the first Workshop. So this talk is a summary of the work that has been done eversince.
What is CP?
Related to ZK
ZK: trust properties claimed by someone else on thata that you have not seen
CPZK: ZK + data you can point to
CP: General Applications:
Compressing/Fingerprinting: delegate storage and computation, verifier keeps the fingerprint, prove data-related computation
Commit ahead of time: commit first, prove later. First commit enable multiple arguments, useful for stabile data
Modular composition:
CP: More Specific Applications:
Federated Learning: central server keeps ML model and users train model with their own data. But could be malicious users that break model, so want them to share commitments of their data, and proof of correct training
Self Sovereign Identity (anonymous credentials): alice uploads personal info, gov certifies it is correct, then in the future she can prove her credentials to another party
Blockchains: many situations to prove about circuits, ownership of coin, may want to combine proofs
That was a summary of 3rd Workshop
This year:
Extension: Encrypt and Prove (Asymmetric here)
Difference: instead of commitment to data, encryption to message. Can be pointed to a ciphertext that can be decrypted if someone has the key.
EP: General Applications:
Same usability as CP + additional: Verifiable encryption: proof guarantees encryption itself. encrypt while proving properties
Privacy differentiation: encryption reveals different information depending on the receiver. Decryptor gets whole message, public only sees properties hold
EP: More Specific Applications:
E-commerce: product satisifies certain prperties (metadata, copyrights…): movie valid rental period?
Digital contract: contract satisfies properties (date, deposit, etc). support mortgage loaners in 2020 whose deposit under x
Voting: voter linked to m is within the membership. vote is valid (sum is integer 1, only one ballot)
Construction
Exploit cc-snark: lifting ElGamal to work with SNARK
if encryption can output or contain a commitment it can be plugged into the CP as a commitment input
Example: SAVER, CT in SAVER contains Pedersen com of the message for knowledge soundness
-> Commit carrying encryption
Use Case: What's different?
Main difference: CP only verifier checks proof. In EP, public verifies properties, and another party can decrypt.
If only modularity is enough, then CP. If need extra properties, then encrypt.
Standardization Status.
General C-or-E-and-prove syntax
Reference doc available at proposal-commit.pdf
Working group available at WG_COMMIT_PROVE
Next steps:
Agree on specific constructions
CP:
ready to proceed
- commitment scheme
- commit and prove scheme
EP:
gather ideas
- what encryption scheme
- what encrypt and prove scheme
Commitment candidates
Pedersen
- what distribution? uniform? lagrange polys?
Snark friendly commitments - adhoc scheme specific commitments (pedersen on jubjub?)
Non algebraic commitments - collision resistant hash (sha256?)
CP candidates
Sigma protocols (but need to agree on syntax, what do we do with interaction, or random coins, forming lemma, do we like crs)
groth sahai
groth16 with snark friendly hash/commitments
legogroth16 from legosnark paper
Encryption candidates (gather ideas)
ElGamal
- exponential version because similar to pedersen, but may need more definitions on preliminaries. Add knowledge soundness? elgamal doesnt care about it but the snark does
Saver LCKO19 - based on ElGamal. Maybe want to trim out some unnecessary features (rerandomization, perhaps not needed)
Snark friendly encryption - algebraic elgamal, c0c0
EP candidates
Basically similar to CP candidates but refine definitions for encryption
SAVER+LegoGroth16?
Chat
Mathias
I want to learn more about modular composition! any references you recommend/share?
Antonio Faonio
LEGOsnark?
Abida Haque
https://eprint.iacr.org/2019/142
Mathias
thanks!!
Matteo Campanelli
On modular composition: another paper proposing this approach is the one below
https://eprint.iacr.org/2018/557.pdf
Matteo Campanelli
To anticipate a potential question:
sometimes "commit-and-prove" is used to mean something slightly different. There is ambiguity in literature. This write-up by Justin Thaler discusses this on page 166 (footnote 114)
http://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
Abida Haque
Meaning: common reference string vs random oracle version?
Matteo Campanelli
Abida, you mean between the two meanings of commit-and-prove? If you mean that. I think the distinctions go beyond that.
Abida Haque:
I meant on the agreement of syntax for Sigma protocols (currently up on the right hand side of the slide) because you can either do crs or rom, if I understand correctly
Eduardo Morais
Maybe a poll for Poseidon?
Mathias:
not enough knowledge xD cannt vote
JB
Not enough knowledge to vote also
Thomas Kerber
I think all are good - but I think Pedersen commitments should be the priority.
Matteo
Related to what Daniel said, can we also do a poll on what we should standardize first?
But maybe the poll results answered that already indeed
Abida Haque
Yeah I think the percentage indicates it already :)
JB
Do you mind showing up for that?
DISCUSSION
- Applications? make sense to create recipes to explain usual applications
- Encryption? candidate of encryption? do we want commit carrying encryption? because it is a way to obtain EP
- Extension? add functionalities to encryption. perhaps IBE-and-prove? some finer grain
- X-and-prove: think about other extensions. sign and prove? accumulate and prove?
–
- Daniel Benarroch: something more general. what components we need for a standard? What is the next step for a commit and prove standard
- Daira Hopwood: useful to have a std encrypt and prove system for saling or zcash protocols because we do encrypt notes but not checked in the circuit. but can potentially be useful if we can prove that is correct
- Mary Maller: very expensive to do properly when ElGamal (range proofs, etc). sounds like should be simple but turns out to have plenty of nuances that perhaps prevents people from using elgamal
- Mikhail Volkhov: if sapling had some … two families of EP . one is saver . solve exponentiation to decrypt. second wich is rsa not really snark friendly (coco?) . do we have something in the middle?
- Daira: also rsa was proof of concept. How much can you encrypt on scalar operation multiplication? in Saver
- Jiwon Lee: one block enough for 4 8 bits maybe but can concatenate multiple blocks
Mikhail: What you want is probably strong-simulability (?)
We should be able to do that efficiently in theory.
You want to encrypt 50 bits and you split them with EG.
Each exponent is 5-6 bits. One EC point per each 5-6 bits which is quite a overhead
Daira: ECIS approach viable? Agree on a shared secret and then use secret key encryption stuff.
Mikhail: What is the real state of efficiency of EP? (?)
Daira: security properties of EP for (?) ? could there be any obstacles in encrypt and prove?
Jiwon: As I said on the presentation, elgamal does not really care about knowledge soundess, but the snark will. If you encode the encryption insidea snark there is no problem. If you do that out of a circuit maybe you need some type of knowledge soundness for the enc system too.
Antonio Faonio: the notion'd be some type of non-equivocability.
Mikhail: robustness?
Matteo: binding?
Jiwon and Antonio: okay, maybe binding.
Antonio: in the sk setting, however, there may be troubles. You need a property that holds for an adv that has the sk.
Daira: could there be a generic way to commit to …
Daira: encrypt and prove. perhaps to go back to cp? Commitments first. need to be specific to the commit and prove scheme? would like to std com scheme.
Jiwon: good time now to gather opinions this
Mary: uniform is more standard than lagrange for pedersen commitments but there are good reasons for lagrange. uniform just looks more natural.
Daira: some applications need homomorphic properties, so in any case we may want to standardize pedersen
Mikhail: What about SNARK-friendly primitives standardization efforts? that would be helpful to people to reason about circuits.
Daira: sha 256 non algebraic are interesting to use for pedersen commitments or do people think they are expensive for pedersen commitments?
Mary: symmetric schemes … perhaps makes more sense?
Daira: harmony .. plonk using custom gates specific to one proof system. disadvantage of algebraic commitments is that specific to one group so if there is a problem with the group (breakthrough with dlog) then cannot rely on those commitments
Thomas: value on having non algebraic commitments . main use if want to use .. .for long time you dnt know (post quantum) what will happen then still can use them . advantage on that side, much more scrutinized already. higher standard of security than perhaps poseidon or these new schemes. never know what cryptanalysis will loke like in 7 years
Daira: interest in std all three options: adhoc, non algebraic and pedersen.
Mary: maybe snark friendly commitments more for other discussions, but yes
Matteo Campanelli: agree on everything being said so far (post quantum, interest, etc) 1. strategy standardize as soon as possible 2. standardize at some point. if need to make a choice given how hard it is to converge to work on this. Propose that if only one of them chosen for next year, which one.
Mikhail: if I want to use pedersen what'd I do is read zcash spec, find academic papers, etc. However, are there any good spec pedersen commitments that is indep of that? I think that is not the case, there is nothing else that i can read.
Daira: prime order group, then spec (also hashing group) … curve
Mikhail: hash into the curve
Daira: Most papers use pedersen hashes try to avoid that part
Daira: suggest standardizing all three these things. an algebraic hash, pedersen commitments, how to use a hash function ,
POLL:
- Pedersen Commitments 94 YES 6 NO
- SNARK friendly algebraic hash commitments (commitments based on algebraic snark-friendly hashes (poseidon) ) 55 YES 45 NO
- conventional hash, e.sha256 (how to instantiate them as commitments) 77 YES 23 NO
(Up to the working group decide which of them (poseidon etc) to propose)
Daniel: perhaps at this point someone else will like to collaborate with the specification of these candidates
Daira: engagement effort. Pedersen first, hashes later
Daniel: perhaps Michele can give some words about merging sigma protocols with this effort.
Michele Orrù: right now I wouldn't know if it could make sense
Daira: it could make sense to have the groups not stepping on each other's toes
Daniel: we could have a potential talk with both working groups and see how it flows
(Agreed on having a meeting)
Daniel: what about groth sahai? are they being used now at all?
Jiwon: hackmd notes last year. not a main candidate, it was proposed last year but we can remove it unless someone has some opinion
Daira: about groth16 (compatibility), legogroth16 has additional features. differences? likely single implementation for both? extensions to get legogroth16 from groth 16
Matteo: there are ways to obtain legogroth16 from an implementation of groth16 with a few tweaks, so a single implementation could work for both
Daira: trusted setup in groth16 so one reason not to use it, but not sure if that is a reason for not standardizing it
Antonio: you mean in commit and prove? or the groth16 algorithm itself?
Daira: i meant the algorithm itself, but if we did the cp version at all, perhaps would make sense to standardize first the plain groth.
Matteo: in that case compatibility between them, then its the groups they are working on. would require to standardize specific points (bls, jubjub etc)
(Summary of last points: there seems to be some agreement on standardizing Groth16 and LegoGroth16)
Daniel: will be shareing telegram group of the working group so you can join.
