# Publicly verifiable multi-user public key encryption

## Introduction

Public key encryption (PKE) is a standard tool used in many protocols with two parties -- sender and receiver. Sender uses receiver's public key to encrypt a secret message and receiver uses her private key to decrypt it. In modern (decentralized) protocols there's a third party -- verifier. Verifier acts as an arbiter, she verifies that both parties (sender and receiver) follow the protocol correctly. When there's a need for privacy a PKE scheme does not offer the verifier to do her job -- to get access to the encrypted message privacy property must be sacrificed.

To overcome this issue there's publicly verifiable public key encryption (PVPKE). In such a scheme the sender encrypts a message and proves certain useful properties about it such that the verifier can verify the proof (ie. that the properties do actually hold for the encrypted message without decrypting it) and the receiver can decrypt the message as usual.

Some useful properties about encrypted text might include the following:

- proof of decryptability, ie. that the receiver can indeed decrypt the message (and not claim that she can't, without revealing her private decryption key);
- proof of correct encryption, ie. that the sender has encrypted a valid message (and not some garbage).

Depending on the underlying platform (message space, key space) and provable properties there can be many approaches. In a general case encryption algorithm is represented as a circuit, then a proof system is used to construct a (non-interactive) proof for that circuit.

In this post we present an extension to multi-receiver ElGamal PKE extended with Bulletproofs-based proof of correct encryption and decryptability that can be used to construct a publicly verifiable secret sharing (PVSS) scheme and non-interactive threshold signature scheme (NITSS).

## TSS case study

To better illustrate our goal with PVPKE, lets consider a threshold Schnorr signature scheme (TSS). In TSS any subset of $t$-out-of-$n$ signers can produce a valid signature. In the simplest case $t$-out-of-$n$ property is achieved with a secret sharing scheme (SSS). In a distributed multi-party protocol it's done with distributed key generation (DKG). In TSS a DKG protocol is used to generate keys and nonce during signing round. A DKG is usually constructed as multiple VSS sessions where each signer gets to act as a secret dealer. The pseudocode for a DKG protocol is presented below.

1. $Commitments^i, Shares^i \gets \texttt{VSS.ShareRandom}()$
2. broadcast $Commitments^i$
3. $Good \gets \{\}$
4. for each $j$:
4.1. receive $Commitments^j$ from $Peer^j$
4.2. send $E^i_j = \texttt{PKE.Encrypt}[PK^j](Share^i(j))$ to $Peer^j$
4.3. receive $E^j_i$ from $Peer^j$
4.4. $Share^j(i) \gets \texttt{PKE.Decrypt}[sk^i](E^j_i)$
4.5. if $\texttt{VSS.Verify}(Commitment^j, Share^j(i))$ then $Good \gets Good \cup \{j\}$
4.6. else handle bad dealer $Peer^j$
5. $FinalShare^i \gets \sum_{j \in Good} Share^j(i)$
6. return $FinalShare^i$

In order for the protocol to be correct peers need to know which secret shares exactly (ie. the set $Good$) contribute to the final value (signing key, nonce, final signature). It's trivial if we consider that all peers are honest, ie. they won't try to disrupt the execution of the protocol, or forge a signature. This is not the case in real world and we have to account for that.

First, we need to assume asynchronous networking model. In it an adversary can block (but not reorder) some messages. That means that we have to communicate with all peers at once (and not sequentially as presented in the pseudocode). Next, the broadcast primitive must be reliable (ie. all honest nodes must receive the same commitments which is not true with an incorrect trivial "send-to-all" implementation of broadcast). Next, an adversary shall not be able to break a secure channel between peers (implemented with PKE in the pseudocode). Lastly, there should be a proper "handle bad dealer" procedure.

We shall focus on the last issue. Without PVPKE many DKG protocols do special "complaint-and-verify" rounds. In simple terms, the idea is for $Peer^k$ to decide which peer to trust in a dispute between $Peer^i$ and $Peer^j$ where $Peer^i$ complains that $Peer^j$ is bad and $Peer^j$ tries to prove otherwise. With PVPKE we can implement DKG as follows.

1. $Commitments^i, Shares^i \gets \texttt{PVSS.ShareRandom}()$
2. $EncryptedShares^i, Proofs^i \gets \texttt{PVPKE.ProveEncrypt}[\vec{PK}](Shares^i)$
3. broadcast $Commitments^i, EncryptedShares^i, Proofs^i$
4. $Good \gets \{\}$
5. for each $j$:
5.1. receive $Commitments^j, EncryptedShares^j, Proofs^j$ from $Peer^j$
5.2. if $\texttt{PVSS.Verify}[PK^j](Commitments^j, EncryptedShares^j, Proofs^j)$ then $Good \gets Good \cup \{j\}$
5.3. $Share^j(i) \gets \texttt{PVPKE.Decrypt}[sk^i](EncryptedShares^j_i)$
6. $FinalShare^i \gets \sum_{j \in Good} Share^j(i)$
7. return $FinalShare^i$

An obvious drawback is added complexity to generate and verify proofs and increased size of broadcasted messages.

## Overview

There is a number of well-known PKE/KEM systems such as [ElGamal encryption](https://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf), [DHIES](https://www.cs.ucdavis.edu/~rogaway/papers/dhies.pdf), [Paillier](https://link.springer.com/content/pdf/10.1007%2F3-540-48910-X_16.pdf), [Kurosawa-Desmedt](https://eprint.iacr.org/2013/765.pdf), [Cramer-Shoup](https://web.archive.org/web/20110722132623/http://knot.kaist.ac.kr/seminar/archive/46/46.pdf), [RSA](http://people.csail.mit.edu/rivest/Rsapaper.pdf). The usual approach to PVPKE is to extend a PKE system with a non-interactive zero-knowledge proof (NIZKP), for example [publicly verifiable ElGamal and RSA encryption](https://www.researchgate.net/publication/296738030_Publicly_verifiable_encryption_for_ElGamalRSA_encryption), [Paillier-based PVSS](http://www.selmer.uib.no/WCC2013/pdfs/Jhanwar.pdf), [Paillier-based IND-CCA secure PVPKE](https://link.springer.com/chapter/10.1007/978-3-540-45146-4_8), [pairing-based PVPKE](https://link.springer.com/chapter/10.1007/978-3-642-14654-1_32), [non-interactive DKG](https://eprint.iacr.org/2021/339). These constructions target different properties such as semantic or IND-CCA2 security, homomorphic property, threshold compatibility, forward secrecy, pairing or RSA friendliness.

Among others we require the following properties:

1. assumed hardness of DL/DH problems or their variant;
2. semantic encryption "in scalar";
3. proofs of decryptability and correct encryption;
4. multi-user encryption;
5. aggregation and batch verification of proofs.

The first requirement means compatibility with Ed25519/X25519; no pairings, RSA, composite/unknown order groups are allowed. The second and third requirements enable a simple application in PVSS, DKG, and TSS constructions; we do not need a stronger IND-CCA2 security. The last two requirements make implementations efficient.

The obvious candidate for a suitable PKE is ElGamal encryption. It satisfies requirements 1 and 4. In order to be able to decrypt a scalar we need to be able to compute a discrete logarithm. It's only possible for small scalars, hence we need to split a secret scalar to be encrypted into sufficiently small chunks.

For decryptability proof we need to prove that the owner of the private key corresponding to the encryption public key is able to decrypt an encrypted small chunk. This is done with a preimage proof (ElGamal encryption is additively homomorphic) and range proof (that the secret scalar chunk is sufficiently small). Proof of correct encryption is also a preimage proof (but for a combined scalar, not individual chunks).

Preimage proofs are easily doable with Schnorr sigma protocol generalized by [Maurer](https://www.crypto.ethz.ch/publications/files/Maurer09.pdf). Range proofs are much more difficult. To do that we use [Bulletproofs](https://eprint.iacr.org/2017/1066.pdf) -- a succinct proof system in DL setting. If we use a straightforward approach we wouldn't fulfill requirement 5. Fortunately, Bulletproofs range proof can be modified to support ElGamal commitments (instead of Pedersen commitments which is used initially), extended statement for chunking proofs, and efficient aggregation (due to use of multi-user ElGamal encryption).

## PVPKE & PVSS

Let $\overline{X} = \overline{x} \cdot G$ be receivers' public keys, then lifted ElGamal multi-user encryption is defined by the following two equations.

$$\overline{C}, R = \texttt{Enc}_{\overline{X}}(\overline{s},r) = \overline{s} \cdot H + r \cdot \overline{X}, r G$$
$$s_j = \texttt{Dec}_{x_j}(C_j,R) = \texttt{DL}_H(C_j - x_j R)$$

$\texttt{Enc}$ and $\texttt{Dec}$ have all the nice additively homomorphic properties allowing to use them in Bulletproofs.

$\texttt{DL}_H(s_j H)$ only works for $s_j \in [0..2^b)$ with small $b$. For *any* $s_j \in \mathbb{Z}_q$, $s_j = \sum_{l=0}^{m-1} 2^{bl} s_{j,l}$ we split it into $m$ chunks $s_{j,l} \in [0..2^b)$.

$$\overline{C}_l, R_l = \texttt{Enc}_{\overline{X}}(\overline{s}_l,r_l) = \overline{s}_l \cdot H + r_l \cdot \overline{X}, r_l G$$
$$s_{j,l} = \texttt{Dec}_{x_j}(C_{j,l},R_l) = \texttt{DL}_H(C_{j,l} - x_j R_l)$$

This effectively increases $m$ times the cipher text size.

In order to turn it into PVPKE we need to add some nice proofs.

**Decryptability** is the proof that the receiver *can decrypt* $s H = C - x R$ (ie. the owner of the private key $x$ is the actual receiver):

$$\texttt{Decryptability}\{(C,R; s,r): C, R = \texttt{Enc}_X(s,r)\}$$

It's possible to use $\texttt{Preimage}$ proof with $\texttt{Enc}_X(s,r)$ as one-way homomorphic map. *Formally* the proof means that the dealer knows $s, r$, but *semantically* it means the receiver's public key $X$ was used to encrypt $s$. It's possible to aggregate the final proof to account for $n$ receivers and $m$ chunks.

**Chunking** is the proof that the receiver *can bruteforce* DLog $s = \texttt{DL}_H(s H)$:

$$\texttt{Chunking}\{(C; s,r): C = s H + r X \wedge s \in [0..2^b)\}$$

We'll use a modified $\texttt{RangeProof}$ proof with $C, R$ as ElGamal commitment. Formally this proof does *also* prove knowledge of $s, r$. We need to make sure that it's safe to use public key $X$ and $H$ as CRS in ElGamal commitment.

We want to use our PVPKE scheme to construct a PVSS scheme. Let's recall Feldman's VSS:

1. The dealer generates random polynomial $f(x) = \sum_{k=0}^{t-1} x^k f_k$ such that $s = f_0 = f(0)$ is the dealer's secret.
2. Next, the dealer publishes commitment $F_k = f_k H$ to $f(x)$. $F_0$ is the dealer's public key and $F(x) = \sum_{k=0}^{t-1} x^k F_k$ is commitment polynomial.
3. Next, the dealer computes shares $s_j = f(j)$ and securely delivers them to each receiver.
4. Receivers can use Feldman's verification equation $s_j H \overset{?}{=} F(j)$ to verify their shares.
5. The shared secret can be recovered via interpolation polynomial $\hat f(x) = \sum_{j\in J} l_j^J(x) s_j$ where $l_j^J(x) = \prod_{i\in J,i\neq j} \frac{x - i}{j - i}$ is Lagrange polynomial. Then the recovered secret is $\hat s = \hat f(0)$.

In a PVSS scheme scalars to be encrypted are secret shares satisfying certain verification equation $s_j H = F(j)$. Thus we have to add a corresponding proof.

**Sharing** is the proof that encrypted share is correct, ie. $s_j H = F(j)$:

$$\texttt{Sharing}\{(F_k,C_{j,l},R_l,X_j; r_l): \\
\sum_l 2^{bl} C_{j,l} - F(j) = \sum_l 2^{bl} r_l X_j \wedge R_l = r_l G\}$$

Again, we use $\texttt{Preimage}$ proof of knowledge with $g_{X_j}(r_l) = (\sum_l 2^{bl} r_l X_j, r_l G)$ as one-way homomorphic map. *Formally* it means the knowledge of $r$ and equality of discrete logs. *Semantically* it means image of encrypted value is $F(j)$.

## Bulletproofs improved

Here we will specify in more detail Bulletproofs-based interactive protocol to support PVSS proofs. It can then be made non-interactive with Fiat-Shamir transform.

First, let's combine all the desired statements into one (secret share chunk here is $v_{j,l}$ to be more consistent with the Bulletproofs paper and avoid clash of names):

$$\texttt{PVSS}\{(F_k,C_{j,l},R_l,X_j; v_{j,l},r_l):
\\ C_{j,l}, R_l = \texttt{Enc}_{X_j}(v_{j,l},r_l) \wedge
\\ v_{j,l} \in [0..2^b) \wedge
\\ \sum_l 2^{bl} C_{j,l} - F(j) = \sum_l 2^{bl} r_l X_j \},
$$

where $k=0..t-1,j=1..n,l=1..m$.

Here the following notation will be used:

- $\vec{c}^n = (c^i)_{i=0}^{n-1} \in \mathbb{Z}_q^n$;
- $x \cdot \vec{a} = (x a_i)_{i=0}^{n-1}$;
- $\langle \vec{a}, \vec{b} \rangle = \sum_{i=0}^{n-1} a_i b_i$;
- $\vec{a} \circ \vec{b} = (a_i b_i)_{i=0}^{n-1}$;
- $\vec{x} \times \vec{b} = \|_{i=0}^{n-1} (x_i \cdot \vec{b})$;
- $v_j = \sum_{l=0}^{m-1} 2^{bl} v_{j,l}$, $v = \|_j (v_{j,l})_l$;
- $\texttt{VCommit}(a,b,c) = \langle a, \vec{G} \rangle + \langle b, \vec{H} \rangle + c K$.

**Step 1.**

The prover chooses nonces ${a_L}$, ${a_R}$ such that $v_{j,l} \in [0..2^b)$ can be rewritten as a system of $nm+2bnm$ scalar equations:

$$\langle {a_{L,j,l}}, \vec{2}^b \rangle = v_{j,l}, \forall j, \forall l \wedge
\\{a_L} = {a_R} + \vec{1}^{bnm} \wedge
\\{a_L} \circ {a_R} = \vec{0}^{bnm},$$

where ${a_L} = \|_{j=0}^{n-1} (\|_{l=0}^{m-1} {a_{L,j,l}})$.

The prover chooses a random ${\alpha}$ and publishes commitment ${A} = \texttt{VCommit}({a_L}, {a_R}, {\alpha})$.

**Step 2.**

The prover receives from the verifier challenge ${y}$ and aggregates the previous system into the following one with $nm+2$ scalar equations:

$$\langle a_{L,j,l}, \vec{2}^b \rangle = v_{j,l}, \forall j, \forall l \wedge
\\\langle a_L - a_R - \vec{1}^{bnm}, \vec{{y}}^{bnm} \rangle = 0 \wedge
\\\langle a_L, \vec{{y}}^{bnm} \circ a_R \rangle = 0.$$

**Step 3.**

The prover receives from the verifier challenge ${z}$ and further aggregates the system into $1$ scalar equation:

$${z}^2 \sum_{j=1}^n \sum_{l=0}^{m-1} {z}^{(j-1)m+l} \langle a_{L,j,l}, \vec{2}^b \rangle +
\\+ {z} \langle a_L - a_R - \vec{1}^{bnm}, \vec{y}^{bnm} \rangle +
\\+ \langle a_L, \vec{y}^{bnm} \circ a_R \rangle =
\\= {z}^2 \sum_{j=1}^n \sum_{l=0}^{m-1} {z}^{(j-1)m+l} v_{j,l}.$$

The same equation can be rewritten in inner-product form:

$$z^2 \langle {a_L}, \vec{z}^{nm} \times \vec{2}^b \rangle + z \langle {a_L}, \vec{y}^{bnm}\rangle + \langle {a_L}, \vec{y}^{bnm} \circ {a_R} \rangle -
\\- z \langle \vec{y}^{bnm}, {a_R} \rangle = z^2 \langle z^{nm}, {v} \rangle + z \langle \vec{y}^{bnm}, \vec{1}^{bnm} \rangle,$$

or in a folded form with only 1 inner product (the goal is to get inner product of $a_L$ and $a_R$):

$$\langle {a_L} - z \cdot \vec{1}^{bnm}, z^2 \cdot z^{nm} \times \vec{2}^b + \vec{y}^{bnm} \circ ({a_R} + z \cdot \vec{1}^{bnm}) \rangle =
\\= z^2 \langle z^{nm}, {v} \rangle + (z-z^2) \langle \vec{y}^{bnm}, \vec{1}^{bnm} \rangle - z^3 \langle \vec{1}^{bnm}, \vec{z}^{nm} \times \vec{2}^b \rangle =
\\= z^2 \langle z^{nm}, {v} \rangle + \delta(y, z).$$

**Step 4.**

In order to use inner-product argument (IPA) and make proof zero-knowledge prover needs to blind $a_L$ and $a_R$.

The prover chooses random nonces ${s_L}, {s_R}$, a random ${\rho}$, publishes commitment ${S} = \texttt{VCommit}({s_L}, {s_R}, {\rho})$.

**Step 5.**

The prover receives from the verifier challenge ${x}$ and constructs blindings:

$$l = {a_L} - z \cdot \vec{1}^{bnm} + {x} \cdot {s_L}$$
$$r = z^2 \cdot z^{nm} \times \vec{2}^b + \vec{y}^{bnm} \circ ({a_R} + z \cdot \vec{1}^{bnm} + {x} \cdot {s_R})$$

Note: $l$ and $r$ are polynomials in $x$ over $\mathbb{Z}_q^{bnm}$

$${t} = \langle l, r \rangle = t_0 + {x} t_1 + {x}^2 t_2$$

Equation $t_0 = z^2 \langle z^{nm}, v \rangle + \delta(y, z)$ ($t(x)$ evaluated at $x=0$) is equivalent (with high probability) to the initial system and the statement that $v_{j,l}$ is small.

Now, the prover can prove that $t = z^2 \langle z^{nm}, v \rangle + \delta(y, z) + x t_1 + x^2 t_2$ with IPA instead.

**Step 6.**

$t_1$, $t_2$ serve as blindings for $t_0$. The prover commits to $t_1, t_2$ with ElGamal commitment (${\texttt{Commit}}_X(s,r) = sG + rX, rG$) using random $\tau_1, \tau_2$:

$${T_i}, {Q_i} = {\texttt{Commit}}_{\overline{X}}({t_i}, {\tau_i}),\; \text{for}\; i=1,2,$$

so that the following holds:

$${t} G + {\tau_x} \overline{X} = z^2 \langle z^{nm}, {C} \rangle + \delta(y, z) G + x {T_1} + x^2 {T_2}.$$

We can use the equation above and the equations from the PVSS statement to deduce the form of the piece of proof ${\tau_x}$, the form of point $\overline{X}$ and necessary verification equations.

More concretely, we use the following equations:

$C_{j,l} = v_{j,l} G + {r_l} X_j$, $R_l = r_l G$

$\langle z^{nm}, {C} \rangle = \sum_{j=1}^n z^{(j-1)m} \sum_{l=0}^{m-1} z^l (v_{j,l} G + {r_l} X_j)$

$\sum_{j=1}^n z^{(j-1)m} \sum_{l=0}^{m-1} z^l {r_l} X_j = (\sum_{l=0}^{m-1} z^l {r_l}) (\sum_{j=1}^n z^{(j-1)m} X_j)$

Thus we get:

$${\overline{X}} = \sum_{j=1}^n z^{(j-1)m} X_j$$

$${\tau_x} = z^2 \sum_{l=0}^{m-1} z^l {r_l} + x {\tau_1} + x^2 {\tau_2}$$

The prover publishes commitments ${T_i}, {Q_i}$ for $i=1,2$ and ${\tau_x}$ as part of proof.

**Step 7.**

The verifier verifies:

$${t} G + {\tau_x} \overline{X} \overset{?}{=} z^2 \langle z^{nm}, {C} \rangle + \delta(y, z)G + x {T_1} + x^2 {T_2}$$

$${\tau_x} G \overset{?}{=} z^2 \langle z^m, {R} \rangle + x {Q_1} + x^2 {Q_2}$$

**Step 8.**

The prover chooses random $\eta$, published commitment ${N} = \eta G$.

**Step 9.**

The prover receives challenge ${u}$ from the verifier and publishes commitment ${M} = \eta \sum_{j=1}^n {u}^j X_j$.

**Step 10.**

The prover receives challenge ${w}$ from the verifier. The prover publishes proof: ${s} = \eta + {w} \sum_l {2^{bl} r_l}$

**Step 11.**

The verifier verifies:

$${s} (G + \sum_{j=1}^n {u}^j X_j) \overset{?}{=} {N} + {M} +
\\\quad\quad\quad\!+ {w} (\sum_l 2^{bl} R_l + \sum_{j=1}^n {u}^j (\sum_l 2^{bl} C_{j,l} - F(j))$$

**Step 12.**

In order to be able to use IPA, the prover computes the following commitment:

$$P = \texttt{IPACommit}(l,r) =
\\= (\langle {a_L}, \vec{G} \rangle + \langle \vec{y}^{bnm} \circ {a_R}, \vec{H'} \rangle + \alpha K) +
\\+ {x} (\langle {s_L}, \vec{G} \rangle + \langle \vec{y}^{bnm} \circ {s_R}, \vec{H'} \rangle + \rho K) -
\\ - (\alpha + {x} \rho) K - \langle z \cdot \vec{1}^{bnm}, \vec{G} \rangle + \langle z^2 \cdot z^{nm} \times \vec{2}^b + z \cdot \vec{y}^{bnm}, \vec{H'} \rangle$$

Let's denote $\vec{H'} = \vec{y}^{-bnm} \circ \vec{H}$, we can rewrite expression for $P$ as follows:

$$P = {A} + {x} {S} - {\mu} K - z \cdot \vec{G} + \langle \gamma(y,z), \vec{H'} \rangle$$

The prover publishes ${\mu} = \alpha + {x} \rho$ as part of proof (so that $P$ can be reconstructed by the verifier). The prover constructs and publishes IPA.

**Step 13.**

The verifier reconstructs commitment $P$ and verifies IPA.