Can you create a ciphertext that can be decrypted if the polynomial inside a polynomial commitment has a particular evaluation? Yes and it turns out to not be that complicated…

Today we will look at the construction from our recent Asiacrypt 2024 paper, which enables just that for standard KZG commitments. So come along and let’s dive into the world of Witness Encryption for KZG commitments.

Introduction to Witness Encryption (WE)

In public key encryption schemes, there are two types of keys: a public key and a secret key. Encryption takes a public key and a message and produces a ciphertext:

$$ \mathsf{ct} \gets \mathsf{Enc}(\mathsf{pk}, \mathsf{msg}) $$

While decryption requires the secret key:

$$ \mathsf{msg} \gets \mathsf{Dec}(\mathsf{sk}, \mathsf{ct}) $$

Without knowledge of the secret key, the ciphertext hides the message.

Witness encryption is similar, but instead of having the public/secrets keys being generated by a $(\mathsf{pk}, \mathsf{sk}) \gets \mathsf{KeyGen}()$ algorithm, the “public key” is a statement $\mathsf{x}$ and the secret key is a witness $\mathsf{w}$ for that statement (“why it is true”) i.e. $(\mathsf{x}, \mathsf{w}) \in \mathcal{R}$. Meaning you can “encrypt” to statements, without knowing the witness or even if the statement is true.

For instance, you could encrypt to the statements/relations such as:

Encrypt to Sudoku: $\mathsf{w}$ is a solution to this Sudoku puzzle $\mathsf{x}$.

Encrypt to Hash: $\mathsf{w}$ is preimage of the SHA3 hash $\mathsf{x}$, i.e. $\mathsf{SHA3}(\mathsf{w}) = \mathsf{x}$.

Technically, what we require is extractable witness encryption, where, not only is $\mathsf{x}$ in the language (e.g. the Sudoku puzzle has a solution), but the decryptor is garuenteed to know the witness $\mathsf{w}$ (e.g. the Sudoku solution).

Witness encryption for all of NP from standard assumptions is ongoing research, but we can construct it efficiently for specific languages and today we are going to show how to construct a witness encryption scheme for a particular language, namely opening proofs of KZG commitments:

$$ \mathcal{R} = \{ (\mathsf{x} = (\mathsf{com}, x, y), \mathsf{w} = \pi) \mid \mathsf{Verify}(\mathsf{com}, x, y, \pi) = 1 \} $$

In other words: you can encrypt to a KZG commitment and “evaluation claim” $(\mathsf{com}, x, y)$, which can only be decrypted if the decryptor knows a valid KZG opening proof $\pi$, i.e. the polynomial “inside” the commitment evaluates to $y$ at $x$.

Witness Encryption for KZG Openings

The construction is actually surprisingly simple (and pretty elegant), although the security proof is more involved. Let us briefly recall how the pairing-based KZG commitment scheme works:

1. Setup: the setup consistens of “powers of tau”: $$ ( [\tau]_2, [\tau]_1, [\tau^2]_1, [\tau^3]_1, \ldots, [\tau^d]_1) $$ Where we use the notation $[v]_1$ to denote $v = G_1^v$ where $G_1$ is a generator of $\mathbb{G}_1$ and $[v]_2$ to denote $v = G_2^v$ where $G_2$ is a generator of $\mathbb{G}_2$.

2. Commit: a commitment is formed by homomorphically evaluating the polynomial $f(X)$ at $\tau$: $$ f(X)= \sum_{i=0}^{d} f_i X^i $$ $$ \mathsf{com} = f(\tau) = \sum_{i=0}^{d} \left[f_i \cdot \tau^i\right]_1 = \sum_{i=0}^{d} f_i \cdot [\tau^i]_1 $$ The inuition is essentially Swartz-Zippel + “encryption” of $\tau$: to find a collision between commitments he must find two polynomials that agree at $\tau$ – but that is hard because the exponentiation $[\tau^i]_1 = G_1^v$ hides the evaluation point $\tau$.

3. Open: opening at $x$ to $y$ is done by committing to the quotient polynomial: $$g(X) = \frac{f(X) - y}{X - x}$$ $$\pi \gets \mathsf{Commit}(g)$$ This follows from the simple observation that if $f(x) = y$ then $f(x) - y = 0$ aka. $f(X) - y$ has a root at $x$. This is equivalent to $(X - x)$ dividing $f(X) - y$. So $g(X)$ is a polynomial (as opposed to a rational function) if and only if $f(x) = y$.

4. Verify: the pairing can be used to multiply committed polynomials by degree 1 polynomials. This is exploited to “multiply out” the denominator of the quotient polynomial and check for equality. Concretely, the verifier checks:

$$ e(\pi, [\tau]_2 - [x]_2) = e(\mathsf{com} - y, [1]_2) $$

Here $[\tau]_2 - [x]_2$ is a commitment to the degree 1 polynomial $X - x$ in the second group.

Encryption Time!

The trick to constructing witness encryption for KZG commitments is to look at the final verification equation and try to randomize one side of the equation. The verification equation is:

$$ e(\pi, [\tau]_2 - [x]_2) = e(\mathsf{com} - y, [1]_2) $$

If we pick $r \in \mathbb{Z}_{p}$ and raise both sides to $r$, the relation still holds:

$$ e(\pi, [\tau]_2 - [x]_2)^r = e(\mathsf{com} - y, [1]_2)^r $$

We can move the exponents inside the pairing:

$$ \color{red}{e(\pi, r \cdot ([\tau]_2 - [x]_2)) } = \color{green}{e(\mathsf{com} - y, [r]_2)} $$

To build public key encryption, the observation is that the encryptor can pick an $r$ and compute the green part without knowing $\pi$. At the same time, even if you are given $s = r$ $\cdot ([\tau]_2 $ - $ [x]_2)$ $ \in \mathbb{G}_2$ it is hard to compute the red part without knowing $\pi$. We show in the paper that finding $\pi$ st. $e(\pi, s) = e(\mathsf{com} - y, [r]_2)$ is equivalent to computing a KZG opening proof in a model called “the algebraic group model” AGM which is the same model commonly used to prove extractability of KZG commitments themselves.

Putting everything together, we can construct the encryption scheme as follows:

Encryption:

1. Pick a random $r \in \mathbb{Z}_p$.
2. Compute $s \gets r \cdot ([\tau]_2 - [x]_2)$.
3. Compute $k \gets \mathsf{Hash}\left(e(\mathsf{com} - y, [r]_2)\right)$ to get a symmetric key $k$.
4. Encrypt the message $\mathsf{msg}$ with the symmetric key $k$: $\mathsf{c} = \mathsf{Enc}_{k}(\mathsf{msg})$.
5. Output $\mathsf{ct} = (s, \mathsf{c})$.

Decryption:

1. Compute the KZG opening proof $\pi$ as normal.
2. Compute $k \gets \mathsf{Hash}\left(e(\pi, s)\right)$.
3. Decrypt the ciphertext $\mathsf{c}$ with the symmetric key $k$: $\mathsf{msg} = \mathsf{Dec}_{k}(\mathsf{c})$.
4. Output $\mathsf{msg}$.

As you can see, encrypting and decryption from/to a KZG opening is essentially the same cost as KZG itself. Even though the scheme is pretty simple, there are some more/less surprising applications. Maybe you can think of some yourself?

Let us look at an easy one.

Application: Laconic Oblivious Transfer

In an Oblivious Transfer (OT) protocol, there are two parties: a sender and a receiver. The sender has two messages $m_0$ and $m_1$ and the receiver has an bit $b \in \{0, 1\}$. The goal is for the receiver to learn his chosen message $m_b$ without the sender learning $b$ or the receiver learning the other message $m_{1-b}$. Basically a “chose one-of-two messages without telling me”-protocol.

Oblivious transfer has been especially useful in the context of secure multi-party computation.

Laconic Oblivious Transfer is a variant of Oblivious Transfer (OT) but where the communication complexity is reduced: the receiver (Bob in the diagram) can commit to many different choices $b_1, b_2, \ldots, b_n \in \{0, 1\}$ using a very short commitment $\mathsf{com}$. The sender (Alice in the diagram) can then encrypt messages $m_0, m_1$ to any position $i$ such that Bob only learns $m_{b_i}$ without Alice learning $b_i$. With our new KZG witness encryption scheme, we can easily construct an efficient laconic OT protocol as follows:

• Commit: Bob interpolates a polynomial $f(X)$ such that $f(i) = b_i$. He then commits to the polynomial $f(X)$ using a KZG commitment $\mathsf{com}$.

• Encrypt: Alice uses the KZG witness encryption scheme to encrypt $m_0$ and $m_1$ to $\mathsf{x} = (\mathsf{com}, i, 0)$ and $\mathsf{x} = (\mathsf{com}, i, 1)$ respectively. Obtaining ciphertexts $\mathsf{ct}_0$ and $\mathsf{ct}_1$, corresponding to the two contractory claims that $f(i) = 0$ and $f(i) = 1$ respectively.

• Decrypt: Bob can compute the KZG opening proof $\pi$ for the evaluation $f(i) = b_i$. Using the KZG opening he can decrypt the ciphertext $\mathsf{ct}_{b_i}$ to obtain $m_{b_i}$. If he could decrypt the other ciphertext $\mathsf{ct}_{1-b_i}$ he would have broken binding of the commitment.

In the paper, we observe that this simple scheme is actually very competitive with the state-of-the-art laconic OT protocols. In particular the communication complexity is very low.

Conclusion

We looked at what witness encryption is and how to construct it efficiently for the language of KZG openings. The Laconic OT scheme has been implemented and benchmarked, the code is publicly available here. If you are interested in learning more about these topics one of my co-authors gave a presentation at the study club of the Ethereum Privacy & Scaling Explorations: