**Home Edition**

# Discussion notes #7: SAVER: Snark-friendly, Additively-homomorphic, and Verifiable Encryption and decryption with Rerandomization
Presenter: Jiwon Lee

Authors:
- Jiwon Lee
- Jaekyoung Choi
- Jihye Kim
- Hyunok Oh

To be presented on 2020-05-11.

Resources:
* [Latest PDF version](https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-saver.pdf)
* [Miro Whiteboard](https://zkproof.org/workshop3-board)
* [SoK Working Group](https://community.zkproof.org/g/WG_SAVER)
* [Additional related links](https://hackmd.io/@HtwXZr-PTFCniCs7fWFSmQ/B1AwbdI_8)

----

## Real-time notes
_Note taker: Daira Hopwood_.

> Others are welcome to augment/annotate using notes. Add your name. ---MyName

Problem statement:

zk-SNARK + encryption: encrypt while proving arbitrary properties of the message.

Motivating examples:
* E-commerce: electronic product (e.g. movie) satisfies properties on metadata, copyrights, ...
* Contracting: contract must satisfy constraints on type, data, deposit...
* Voting: can also validate properties linked to the message, e.g. that a ballot was encrypted by a key tied to a voter's voting right.

Encryption in the circuit:
* is it efficient enough?
* RSA-OAEP-2048 in Groth16 libsnark encryption has 8.9s proving time, 216 MB CRS

Solution:
* Detach encryption from the circuit, encrypt outside but maintain connectivity, i.e. same message for encryption and in zk-SNARK.
* Message is input/output of the SNARK.
* Linear encodings g^m look like ElGamal ciphertext g^m . h^y.
* Extension of cc-SNARK from LegoSNARK to encryption.
* 

Details:
* Used Groth16, but could use any preprocessing SNARK.
* After setup, use CRS as ingredient to encryption public key.
* Split message into n small blocks.
* Mix randomness to I/O shaped message.
* 

Other functionalities:
* additively homomorphic (like ElGamal)
* verifiable decryption (plaintext awareness?) without secret key

Example application: Vote SAVER.
* Encrypt the vote, also prove voting right.
* Zerocash-based protocol, uses blockchain.
* Properties: non-malleable; receipt-free; voter can individually verify; anyone can check tally; voter anonymity; non-repudiation.
* Daira: how does it compare to other e2e-verifiable voting protocols?
* Daira: did you fix the bugs in Zerocash? (See )

* 
* 

* Implemented with Ajtai hash tree of height 16.
* Daira: why Ajtai and not Pedersen? there was a paper breaking it for some parameters recently. I know this is independent of the rest of the protocol.

Contributions:
* Universal verifiable encryption
* SNARK-friendly
* Extra functionalities...

Lifting extension, can it be applied to other encryptions such as [H]IBE or ABE? Looks possible but what about interaction with other features of the encryption. Connect these to the SNARK so that we can make constraints depend on them.

Debate whether to standardize general lifting technique or more specific instantiation(s).

Is it compatible with other (universal) pairing-based SNARKs? Yes
* open problem for other groups (DARK, FRI, DL?)

Focus on connectivity between SNARK and X (for X = encryption, signing, verification, membership test, ...)

Questions:
* Can validity be of committed plaintext?
* didn't catch answer, maybe could use Commit-and-Prove?
* Tamara: is something added to the setup?
* yes, when the encryption is happening, we have to modify the proof in order to cancel the randomization
* Tamara: can voter in Vote SAVER cancel their vote?
* Jihye Kim: no, is non-repudiable
* Karim: can do encryption by SNARK as Commit-and-Prove. Have discussed in the introduction of https://eprint.iacr.org/2019/480.pdf as well.
* Abilash: for Vote SAVER, the miner could modify some of the components. What about attacks by miners, e.g. by modifying serial number?
* Modifying sn would break soundness of the zk-SNARK?
* Guillaume: don't understand how you can achieve receipt-freeness. Voter can prove they have a witness.
* sn is deterministic but does not indicate the vote. Randomization is handled by the miner. But not coercion-resistant because we can rubber-hose the secret key from a voter.
* Daira: did you fix the bugs in Zerocash? They're described in the Zcash protocol spec. (A few errors in the proofs, and the [InternalH bug in their SHA-256-based commitments](https://zips.z.cash/protocol/protocol.pdf#internalh). Also the "faerie gold" bug which I'm not sure is applicable to Vote SAVER.)
* wasn't aware of those bugs, but just using the membership proof really.
* Daira: why Ajtai hashes, not Pedersen? We rejected Ajtai for Zcash because it's not clear what parameters are concretely secure.
* agreement.

Degree of generality:
* Daniel: can specify more than one scheme, but what can we standardize in general?
* Daira: notes similarity of pairing-based IBE SNARK-friendly encryption to PC_AGM in the accumulation scheme paper .

Daira: application to strengthening selective transparency in Zcash, by verifying note encryption in the circuit.

Hugo Krawczyk: use for publically verifiable secret sharing. Prove that encrypted shares are consistent with one polynomial. If we were to standardize MPC then we would want this.

Karim: Did you consider UC security for this setting. If you use a nonmalleable proof e.g. GM17 then you have blackbox extractibility and proved nonmalleability.
* but this loses randomization. Can tweak by g^(a.delta) can only rerandomize but not malleate.

Karim: another version of Groth (Gabizon, or Lipmaa?) can get nonmalleability.
* have considered UC but is open question.

Daniel: are we standardizing a functionality or specific schemes?
* personal opinion: standardize concept.

Daira: are security properties crisply defined? Also for X != encryption.
Daniel: have some of this for Commit-and-Prove.

Daira: should this be rolled into the Commit-and-Prove WG?
* Jiwon: personal opinion yes
* tried to do poll, could not for technical reasons
* there were no objections to merging.

> Distinguish between:
> * **intra-SNARK** primitives where the bulk of computation is done inside the constraint system (e.g., MiMC)
> * **SNARK-adjacent** or **SNARK-bound** primitives where the bulk of computation is done outside the constraint system but is wired to it (e.g., commit-and-prove, this talk, RedDSA as used for authorization in Zcash)
>
> and form 1 working group for each class? ---EranTromer

----
Charter Ideas

Goals:

-

Milestones:

-

----

## Discussion topics

_Suggestions welcome! Please append at the end, and the moderators will incorporate into the schedule._

~15 minutes each, by default.