Some Intuition on Witness Encryption

DISCLAIMER: I am not a cryptographer. This is purely intuition. Some of it might be wrong.

Recall that informally, a witness encryption (WE) scheme with respect to an NP language

$\mathcal{L}$ gives us a way to encrypt messages with respect to instances

$x$ such that if

$x\in \mathcal{L}$, then anyone with a satisfying witness

$w$ for

$x$ can decrypt the ciphertext. Here are a few immediate observations:

• The main appeal of witness encryption is that we can encrypt a message without knowing a satisfying witness. In fact, we can encrypt a message without knowing if a satisfying witness even exists! If the encryptor needed to know a witness, then they might as well just encrypt with that witness directly (maybe this isn't good enough if you want a decryptor holding a different witness to be able to decrypt, but afaik we're not at that point). Furthermore, this property also means that witness encryption is non-interactive, i.e., someone who knows a witness doesn't need to interact with the encryptor - they just decrypt and move on.
• There are multiple ways you could define security here. The initial WE paper required that for any
  $x\notin \mathcal{L}$, the encryptions of different messages (of the same length) be indistinguishable. It gave no security conditions on the case
  $x\in \mathcal{L}$. Since in practice the language
  $\mathcal{L}$ is trivial, we'll want the stronger notion of extractable security. Informally, extractable security implies that any PPT adversary who can distinguish between a ciphertext encrypted under instance
  $x$ and a ciphertext encrypted under a random key can also extract a satisfying witness
  $w$ for
  $x$.

We will not discuss witness encryption constructions using multilinear maps or iO.

BLS Signature Witness Encryption

First, let's recall how BLS signatures work.

BLS Signature Scheme

Consider groups

$({\mathbb{G}}_1,{\mathbb{G}}_2,{\mathbb{G}}_T)$ over

${\mathbb{F}}_q$ with pairing

$e:{\mathbb{G}}_1\times {\mathbb{G}}_2\to {\mathbb{G}}_T$, as well as a hash function

$H_1:\mathcal{M}\to {\mathbb{G}}_1$. The private signing key is a random

$x\leftarrow {\mathbb{F}}_q$, and the public verification key is

$g_2^x$ (where

$g_2$ is generator of

${\mathbb{G}}_2$). Then, to sign any message

$m\in \mathcal{M}$, the signer computes and sends

$\sigma =H_1(m{)}^x$. To verify the signature, it suffices to check

$$e(H_1(m),g_2^x)=e(\sigma ,g_2).$$

Here are three observations for this signature scheme:

• BLS is deterministic. This is incredibly powerful and unique to BLS. We will later see how this requirement seems to prevent us from building WE for other non-deterministic signature schemes.
• Intuitively, BLS is just "moving" the secret exponent
  $x$ around using the pairing. We'll try to leverage a similar trick later on.
• The hash function
  $H_1$ should be cryptographically secure. In particular, it should not do something explicit like
  $H(m)=g_1^m$. However, in the case that
  ${\mathbb{G}}_1\ne {\mathbb{G}}_2$ (an asymmetric pairing), I believe that using a weak hash function like this is actually okay, the point being that an adversary should not be able to compute
  $\sigma =g_1^{mx}$ given only
  $m$ and
  $g_2^x$.

Witness Encryption from BLS

In addition to the BLS scheme setup, define a hash function

$H_2:{\mathbb{G}}_T\to \{0,1{\}}^n$. Then, to encrypt a message

$m\in \{0,1{\}}^n$ with respect to some verification key

$vk$ and signed message

$T$,

1. sample a random
   $r\leftarrow {\mathbb{F}}_q$.
2. compute and send the ciphertext
   
   $$c=(g_2^r,H_2(e(H_1(T),v{k}^r))\oplus m).$$

Anyone who holds a signature

$\sigma$ of

$T$ under the corresponding signing key

$x$ can decrypt as follows:

1. using the first part of the ciphertext, compute
   
   $$e(\sigma ,g_2^r)=e(H_1(T{)}^x,g_2^r)=e(H_1(T),v{k}^r).$$
2. hash this value and XOR to extract the message.

Note: there is also a WE scheme for threshold BLS signatures (see here).

Intuition

This WE scheme from BLS signatures is incredibly elegant and simple, so what's really going on here?

First, notice that we need to sample some randomness

$r$. This makes sense: since BLS signatures are deterministic, if we want any hope of semantic security, the encryption scheme had better have randomness. However, we also use this randomness in a fairly nontrivial way. In particular, we are hiding the randomness through

$g_2^r$. This is a crucial point: if an adversary could recover

$r$, then they could just simulate the role of the encryptor to decrypt the message. Of course, a natural place to hide the randomness is in the exponent, and this also plays in nicely with properties of the pairing.

Next, notice that we are essentially computing the same thing as in BLS signatures, just raised to the power of

$r$. In particular, our pairing value is

$$e(H_1(T),v{k}^r)=e(H_1(T),g_2{)}^{xr}=e(H_1(T{)}^x,g_2^r).$$

By "splitting" the exponent as such, it forces so that only someone who knows

$\sigma =H_1(T{)}^x$ can decrypt.

This kind of gives us a general formula for building similar kinds of WE schemes:

1. Take the "public" part of the verification equation and randomize it. Then hash this random value, XOR it with the message, etc.
2. Additionally, provide just enough hints to the randomness, e.g.,
   $g_2^r$ above, such that someone who knows a witness can use these hints to decrypt, but nobody else can.

Attempting to Construct WE

Let's use what we learned above to try construct WE for various NP languages.

Attempt 1 - DLOG ✅

Here's an almost trivial example. Consider the DLOG problem. An instance is a group element

$y$, and the witness is the scalar value

$x$ such that

$y=g^x$. Using the step-by-step formula above, we can encrypt a message as follows:

1. sample randomness
   $r$.
2. compute and send
   
   $$c=(g^r,H(y^r)\oplus m).$$

It's not hard to see that only someone holding the discrete log

$x$ can decrypt the message.

Attempt 2 - any BLS signature ✅

Suppose that I want to encrypt a message so that anyone who holds any signature from some particular signer can decrypt. In particular, the signed message

$T$ is no longer fixed.

We will assume a BLS signature scheme setup where

${\mathbb{G}}_1\ne {\mathbb{G}}_2$ (formally, a type 3 pairing). Furthermore, we will define our hash function to be

$H_1(T)=g_1^T$ (see above for why this should be okay). Then, to encrypt a message

$m$ with respect to verification key

$vk$,

1. sample randomness
   $r$.
2. compute and send
   
   $$c=(g_2^r,H_2(e(g_1,v{k}^r))\oplus m).$$

For anyone holding a signature

$\sigma =H_1(T{)}^x=g_1^{Tx}$,

1. compute
   ${\sigma }^{T^{-1}}=g_1^x$.
2. compute the pairing
   $e(g_1^x,g_2^r)$ and decrypt.

Note that here, we rely on the fact that

$H_1$ "preserves" the structure of

$T$, which allows us to then cancel

$T$ out out by raising

$\sigma$ to the

$T^{-1}$. Because of this, we also need the signature scheme to be instantiated using a type 3 pairing.

Attempt 3 - commitment schemes❓

Here's something that would be nice: encrypt a message to some commitment so that only someone who knows the underlying committed value can decrypt.

In fact, we kind of already achieved this for Pedersen commitments! Recall that a Pedersen commitment to

$m$ is just a scalar point multiplication

$\text{Com}=g^m{h}^r$. If we ignore the randomization term

$h^r$, then we already did this above. However, this randomization term turns out to be a key problem.

To see why, recall that we want two properties for commitment schemes: hiding and binding. To provide hiding, we need to bake in some sort of randomness into the commitment, e.g.,

$h^r$ above. Then, this randomness actually becomes part of the witness, i.e., the witness in our NP language for a commitment is the underlying committed value and the randomness used to generate the commitment. This presents a problem, because this means that only the person who generated the commitment can decrypt because they are the only person who knows the randomness. If we ditched the randomness, then we wouldn't have a hiding commitment.

Well what about KZG commitments? KZG commitments, as they are typically used, are indeed deterministic (given a fixed CRS), and hence are not hiding (though they can be easily made hiding). So, we could do something like this given a KZG commitment

$C$:

1. sample randomness
   $r$.
2. compute and send
   
   $$c=(g_1^r,g_1^{r\tau },g_1^{r{\tau }^2},\dots ,H(C^r)\oplus m).$$

Then, only someone who knows the underlying committed polynomial can decrypt the message.

Something else you can do is support KZG opening proofs as witnesses, i.e., for some fixed

$a$ and

$b$, anyone who holds an opening proof

$\pi$ that

$p(a)=b$, where

$p$ is the committed polynomial, can decrypt. See this paper for a construction. Note that their construction does use a hiding version of KZG commitments, but the randomness that is used needs to become known to the decryptor, which is the same problem we ran into above.

What goes wrong if we just ditch hiding for commitment schemes? For example, in practice KZG commitments are not hiding - we like them because they provide succinct proofs. Then, it no longer becomes clear why we are using WE in the first place. Intuitively, if we want to encrypt a message to some commitment

$x$, then

$x$ had better be hiding its underlying witness!

There are still some pretty interesting things we can do while requiring

$r$ to be part of the witness. This paper supports witness encryption for a specific set of languages relating to functional commitment schemes. In particular, we can encrypt a message to some commitment

$C$, a function

$f$, and an output

$b$ such that anyone with an opening proof

$\pi$ that

$C$ opens to

$a$ and

$f(a)=b$ can decrypt. Unfortunately, most functions

$f$ are not supported, but linear functions are, and in particular, the identity function works. So, we can encrypt a message to some commitment

$C$ and an output

$b$ such that anyone with an opening proof

$\pi$ that

$C$ opens to

$b$ can decrypt. So, you can imagine:

1. Alice publishes commitments to several values (maybe this is people Alice is interested in).
2. Bob encrypts a message (maybe this message is "Bob likes Alice") multiple times, each one using a different commitment Alice sent, along with
   $b=$ Bob.
3. If Alice committed to Bob, she can decrypt one of the messages. Otherwise, she can't decrypt any of them.

This is basically an oblivious transfer, done WE-style. See here for what this looks like fully built out.

Attempt 4 - groth16 proofs ❌

The dream would be to get witness encryption for groth16 proofs. That is, for any NP language, we encrypt a message with respect to some instance

$x$ such that anyone holding a groth16 proof that they know a satisfying witness

$w$ can decrypt the ciphertext.

There is some reason to think this could be possible. Like BLS, the verification equation just consists of several pairings (borrowing some notation from here):

$$e(A,B)=g_T^{\alpha \beta }\cdot e(L^{\prime },g_2^{\gamma })\cdot e(C,g_2^{\delta }).$$

If we rearrange so that private values are on the left and public values are on the right, this becomes

$$e(A,B)\cdot e(C,g_2^{-\delta })=g_T^{\alpha \beta }\cdot e(L^{\prime },g_2^{\gamma }).$$

Note that

$L^{\prime }$ is public because it consists of public inputs to the R1CS.

Here are some immediate things you could try that don't work:

• Copy the strategy from BLS signatures: sample randomness
  $r$ and raise the RHS to the power of
  $r$, then provide sufficient powers of
  $g_1^r$ and
  $g_2^r$ so that anyone holding a proof can decrypt. It turns out this isn't secure, i.e., anyone can decrypt.
• Try something a little smarter: sample randomness
  $r$ and
  $s$ and raise the RHS to the power of
  $rs$, then provide sufficient powers of
  $g_1^r$ and
  $g_2^s$ so that anyone holding a proof can decrypt. It turns out this still isn't secure, i.e., anyone can decrypt.

Intuition:
Both these approaches seem to fail for a fairly fundamental reason. In the BLS-based WE, the public value had a secret value

$x$ baked into the public

$vk$, which is then randomized. In the case of groth16, however, the RHS doesn't really have some "secret" within it that we can utilize. Alternatively, we can think of the public

$vk$ as a "hint" to the secret

$x$, but in groth16, the RHS doesn't contain any hint to the witness.

Because of this, when you try either of the strategies above, you realize that if you're given terms like

$g_1^r,g_1^{r\tau },\dots ,g_2^s,g_2^{s\tau },\dots$, you can pair these terms to get

$g_T^{rs},g_T^{rs\tau },\dots$. This, and some other terms, is enough to completely derive the randomized RHS unfortunately.

Another failed idea:
There are some more interesting ways you can try bake in the randomness. One way is to modify the circuit by adding in a dummy public input

$w_0$ and a dummy constraint

$w_0\cdot 0=0$. Then, we will sample

$w_0$ randomly and compute the new RHS of the verification equation. Because

$w_0$ is random, this group element will also be random. Moreover, although

$w_0$ is technically a "public" input, we cannot publish its value, as that would destroy the randomness. Instead, the idea is that we publish enough hints to

$w_0$, e.g., through terms like

$g_1^{w_0}$, etc. such that only someone who holds a valid proof can suitably augment their proof using these terms to then decrypt the ciphertext. I tried this for a while but couldn't get it to work, and it might be failing due to a similar reason as the above.

Some observations:
Due to the nature of witness encryption, there are some slightly surprising and powerful things you can do while trying to construct WE for groth16 proofs. It's not super clear to me how they can be used, but they seem useful 🤷‍♂️:

• The encryptor can construct the CRS. That is, it's fine if they know
  $\alpha$,
  $\beta$, etc. In particular, this means that if the encryptor needs to send "hints" for secret random values, these hints can use
  $\alpha$,
  $\beta$, etc. in non-trivial ways.
• The decryptor can fix the randomness they use, e.g., set
  $r=s=1$ in groth16. This is just because the decryptor never needs to publish their proof, so it doesn't need to be zero-knowledge. In particular, this means that an encryptor can send fewer hints, knowing that the decryptor is fixing
  $r=s=1$.
• In general, we probably don't want the hints to mix
  ${\mathbb{G}}_1$ and
  ${\mathbb{G}}_2$ terms. This stops an adversary from pairing these terms together to get potentially useful
  ${\mathbb{G}}_T$ terms. Ideally, for example, all the hints could be
  ${\mathbb{G}}_2$ elements, meaning that an adversary could only pair these elements with
  ${\mathbb{G}}_1$ elements in the CRS to get potentially useful
  ${\mathbb{G}}_T$ terms.
• Section 5.2 of this paper seems to give some ideas on how to construct this. I don't pretend to understand it though.

Witness Encryption from Other Signatures Schemes?

BLS is super nice, but can we also get witness encryption from ECDSA or Schnorr? I don't know, but it's probably got to look very different from BLS-based WE. One of the immediate problems with ECDSA and Schnorr is that they lack any structure, relying heavily on hash functions. I guess this highlights just how amazing BLS signatures are - they're elegant, deterministic, and exploit the pairing structure really nicely.