Commit-and-Prove, Encrypt-and-Prove working group

[jlee]

Hi all,

In the commit-and-prove and SAVER WG (merged), we recently had an active discussion on deciding the concept of encrypt-and-prove as an extension of commit-and-prove. We’d like to share the agenda by providing the abstract background and summary of our discussion; it would be nicer to gather everyone’s opinion to be more productive!

If you’re already familiar with the terminologies from 3rd workshop, you can just skip it and look at the summary.

1. Backgrounds

what’s different from commit-and-prove?
The main difference of both encrypt-with-prove/encrypt-and-prove is that they can avoid including the encryption in the SNARK circuit. Let us suppose that we want to encrypt the message, and also prove some properties of the message (with or without encryption in advance).

Refer to the figure on the left. If we face the situation with commit-and-prove, here’s what we can do: we can 1) commit the message, 2) prove the encryption with SNARK, 3) prove the property with SNARK, 4) then connect them all with CP-SNARK. But notice that it requires a SNARK proving phase for the encryption: we cannot avoid including encryption in the SNARK with just commit-and-prove. That’s the main reason why we need encrypt-with-prove/encrypt-and-prove. Like the figure on the right, encrypt-with-prove/encrypt-and-prove let the ciphertext connectable to the SNARK proof, which can avoid “proving encryption in the circuit”.

encrypt-with-prove vs. encrypt-and-prove

means that we have the CRS generated from SNARK setup before the encryption. In this case, we can use the CRS as an ingredient for the public key (it can be also viewed as “extending the ciphertext to work as SNARK I/O”), and let them verified together at once in the SNARK verification.

In encrypt-and-prove, what we want is to encrypt ahead of time (without knowing what to prove) and prove any arguments later. In this case, we need a connectivity check to guarantee that the ciphertext and proof shares a same message (in the viewpoint of commit-and-prove, it can be also viewed as “extending the commitment to the ciphertext”), in addition to the original SNARK verification.

2. Summary of discussion

Our first main agreement was that the encrypt-with-prove is not appropriate for the standard. However, we agreed that the encrypt-and-prove can be a good extension for the commit-and-prove standard, and the discussion was mostly about defining the encrypt-and-prove framework.

The position of SAVER scheme
In the 3rd workshop, we presented the SAVER as an encrypt-with-prove scheme (which is sufficient for the concept of universal verifiable encryption). But recently, when we looked at it again, it turns out that the SAVER scheme already satisfies the encrypt-and-prove concept as well. The simple reason for this is that the ciphertext in SAVER already includes a parameter which is equivalent to the Pedersen vector commitment of CP-SNARK. Thus, if we want to encrypt first and argue later (enc-and-prove), we can simply encrypt with SAVER (assuming empty circuit), and use SAVER’s commitment as an input to the CP-SNARK.

New terminology: commit-carrying encryption
For the encryption system, if there exists an efficient function f(x) that can output f(CT)=Ped.commitment, we’d like to say that the encryption system is a commit-carrying encryption. The commit-carrying encryption implies encrypt-and-prove, since the commitment can be used as an input to the CP-SNARK. SAVER is a good example of the commit-carrying encryption: in case of SAVER, f(CT) is just simply “using the commitment in CT”.

Issue: how to define encrypt-and-prove?

There are two approaches to define the concept of encrypt-and-prove:

First one (framework 1) is to define the encrypt-and-prove equivalent to the commit-carrying encryption (cc-encryption), i.e., if the encryption is a cc-encryption, then we call it encrypt-and-prove. Currently, SAVER protocol can be a representative example for the efficient cc-encryption.

Second one (framework 2) is to define encrypt-and-prove in more general way. If we come up with a linking scheme (which does not exist yet) that can connect the ciphertext and commitment, then we call it encrypt-and-prove. This definition is more general than framework 1; now the restriction for the encryption scheme is mitigated.

Direction: scope for the standard
Our first step conclusion was that it seems good enough to include both framework 1 and 2 in the standard. But then, it seemed better to share this idea with others who might as well be interested: if you have any comments or opinions on this, please feel free to join the group and talk to us.

Another individual issue was about including the concrete protocol (ex: CP-SNARK, Pedersen Commitment, SAVER) in the standard. In the current status, we all agreed to first provide the general framework, and then also include the concrete protocol as a good example for those frameworks.

Future plans
We discussed this issue in the telegram group of the merged WG, and we all agreed that now we’re ready to publish the group on public. To be more productive, we’d like to proceed a (roughly) monthly online discussion to check the status and comments.

For more technical details, refer to 4.3 of the revised SAVER paper, and please do not hesitate to post replies.
Also, please refer to the post from @dariofiore for the commit-and-prove document links!

[lovesh]

Hi,

I was looking at verifiable encryption and I came across your SAVER paper. It’s an interesting read, thank you for this paper.
I did a PoC implementation in Rust. I implemented using both Groth16 and LegoGroth16 (LegoSNARK paper, Figure 22). I had 2 questions:

Q1. The encryption outputs a commitment psi (Algorithm 2 of the paper) not to the message m but a decomposition m1, m2, … of m. But I wanted a commitment to m such that for some G and H, commitment J = m*G + r*H because I need to prove the equality of its opening with another commitment Q which comes from another protocol. Is there a way to do it?

What I could come up with (as described here) was to create J as

J = m_1*G_1 + m_2*G_2 + ... + m_n*G_n + r'*H

where G_i = {b^{n-i}}*G so G_1 = {b^{n-1}}*G, and so on.

The commitment to the decomposition, i.e. psi as described in the paper is

psi = m_1*Y_1 + m_2*Y_2 + ... + m_n*Y_n + r*P_2

Now using Schnorr protocol and I can prove the equality of opening of both commitments J and psi and J is same as m*G + r'*H because

m_1*G_1 + m_2*G_2 + ... + m_n*G_n + r'*H
= m_1*{b^{n-1}}*G + m_2*{b^{n-2}}*G + ... + m_n*G + r'*H
= ( m_1*{b^{n-1}} + m_2*{b^{n-2}} + ... + m_n ) * G + r'*H
= m*G + r'*H

Q2. Is there something wrong if the encryption ( Enc in Algorithm 2) outputs sum r*X_1 + r*X_2 + .. + r*X_n as well? I asked because I needed this sum to make verification work with LegoGroth16. Here is the verification in case you are interested.

My motivation for looking at SAVER was to use it for verifiable encryption in anonymous credentials.