# Witness-Encryption from Groth16

We present a witness-encryption (WE) scheme built from **Groth16**. It starts from the exact R1CS/QAP form, then spells out:

* **CRS / public parameters** (including exactly which group elements exist),
* **Encrypt (arm)**: what the encryptor *publishes*,
* **Decrypt (decap)**: what a party with a witness *does*, and
* **Correctness and security posture** (including the subtle holes and how we close them).

This write-up incorporates two defenses from previous specification:

* **Defense 1 (MUST)**: *never* publish separate masks for the public $B$-columns; publish only the **single aggregated public right-leg** $B_{\mathrm{pub}}$ masked by $\rho$;
* **No $\rho$ reuse (MUST)**: $\rho$ is fresh per $(vk,x)$ (or deterministically derived per-instance from a salt bound into the domain string).

(An optional **Defense 2**—make every public input have $C_i \not\equiv 0$—is noted at the end.)

---

## 0) Relation and QAP

Let an R1CS instance be encoded as a QAP over $\mathbb{F}_r$:

$$
\left(\sum_{i=0}^m a_i u_i(X)\right) \cdot \left(\sum_{i=0}^m a_i v_i(X)\right) \equiv \left(\sum_{i=0}^m a_i w_i(X)\right) \pmod{t(X)}
$$

with $a_0 = 1$, public inputs $a_1, \ldots, a_\ell$, witness $a_{\ell+1}, \ldots, a_m$, where $u_i, v_i, w_i$ have degree $\leq n-1$ and $t(X)$ has degree $n$. WLOG, $t(X) = X^n - 1$.

---

## 1) Groth16 keys and notation

Work in asymmetric Type-3 bilinear groups $(G_1, G_2, G_T, e)$ of prime order $r$.

**Notation.** We write $G_1, G_2$ **additively** (group law "+", scalar mult "$[\lambda]P$" or "$\lambda \cdot P$"), and $G_T$ **multiplicatively**. When we write $P^\rho$ for $P \in G_2$, it means the scalar multiple $[\rho]P$.

The **Groth16 setup** (for the fixed circuit/QAP) samples trapdoors $\alpha, \beta, \gamma, \delta, \tau \in \mathbb{F}_r$ and publishes:

* **Verifying key** $vk$:
$$
\alpha_1 \in G_1, \quad \beta_2, \gamma_2, \delta_2 \in G_2, \quad \gamma_{abc}[0..\ell] \in G_1
$$
where $\mathrm{IC}(x) := \gamma_{abc}[0] + \sum_{i=1}^{\ell} x_i \cdot \gamma_{abc}[i] \in G_1$.

* **Proving key** $pk$ (items we use below):
$$
A_i(\tau) \in G_1, \qquad B_i(\tau) \in G_2 \quad \text{for } i = 0, \ldots, m
$$

A Groth16 proof $\pi = (A \in G_1, B \in G_2, C \in G_1)$ verifies iff

$$
e(A, B) = e(\alpha_1, \beta_2) \cdot e(\mathrm{IC}(x), \gamma_2) \cdot e(C, \delta_2) \tag{G16}
$$

For the prover's $B$-element it is convenient to split

$$
B_{\mathrm{pub}} := \beta_2 + \sum_{i=0}^{\ell} x_i \cdot B_i(\tau), \quad
B_{\mathrm{wit}} := \sum_{i>\ell} a_i \cdot B_i(\tau), \quad
B = B_{\mathrm{pub}} + B_{\mathrm{wit}} + s \cdot \delta_2
$$

for some prover randomness $s \in \mathbb{F}_r$.

---

## 2) Public parameters / CRS for WE

The WE construction uses only **statement-only** material:

* The curve parameters $(G_1, G_2, G_T, e)$ and encodings.
* The Groth16 $vk$ and **$pk$**. *(After setup, both $vk$ and $pk$ are public; the encryptor needs $pk$ (specifically $B_i(\tau)$ for $i \leq \ell$) to compute $B_{\mathrm{pub}}$; decappers need $pk$ to produce a proof.)*
* A collision-resistant hash $H$ and a KDF (e.g., HKDF-SHA-256).
* The **right-leg descriptor** for the instance $(vk, x)$:
$$
Y' = \big(B_{\mathrm{pub}}, B_{\ell+1}(\tau), \ldots, B_m(\tau), \delta_2\big)
$$
where $B_{\mathrm{pub}}$ is computed from $vk, pk, x$.

**Right-leg discipline (Defense 1, MUST).** The public $B$-subspace is armed **only** as the single aggregate $B_{\mathrm{pub}}$. We do **not** arm $\beta_2^\rho$, any $B_i(\tau)^\rho$ for $i \leq \ell$, **or any alternate $G_2$ basis (e.g., monomials $g_2^{\tau^k}$) that linearly spans** the public subspace.

---

## 3) Domain binding

Define a domain string

$$
d := H\big(\mathrm{ser}(vk) \,|\, \mathrm{ser}(x) \,|\, \mathrm{ser}(Y') \,|\, \mathrm{salt}\big)
$$

where $\mathrm{ser}(Y')$ commits to the exact **ordered** list $(B_{\mathrm{pub}}, B_{\ell+1}(\tau), \ldots, B_m(\tau), \delta_2)$ and $\mathrm{salt}$ is a per-instance 256-bit nonce chosen by the encryptor.

---

## 4) Algorithms

### 4.1 Encrypt (arm) — input: $(vk, pk, x)$

1. **Compute** $B_{\mathrm{pub}} := \beta_2 + \sum_{i=0}^{\ell} x_i \cdot B_i(\tau) \in G_2$. Fix $Y'$ and $d$ as above.

2. **Sample** fresh $\rho \leftarrow \mathbb{F}_r^*$. (**MUST NOT** reuse the same $\rho$ for a different $x$ with the same $vk$.)

3. **Publish the masks**:
$$
D_{\mathrm{pub}} := B_{\mathrm{pub}}^\rho, \quad
D_j := B_j(\tau)^\rho \text{ for } j > \ell, \quad
D_\delta := \delta_2^\rho
$$
No other right-legs are masked or published.

4. **Define the anchor**
$$
R(vk, x) := e(\alpha_1, \beta_2) \cdot e(\mathrm{IC}(x), \gamma_2) \in G_T
$$
and the **KEM key**
$$
M := R(vk, x)^{\rho} \in G_T, \qquad
K := \mathrm{KDF}\big(\mathrm{ser}_{G_T}(M) \,|\, d\big)
$$

5. Optionally, **encrypt** a payload under $K$ with an AEAD and publish the ciphertext alongside the masks.

**Arming header** (hdr): $(D_{\mathrm{pub}}, \{D_j\}_{j>\ell}, D_\delta, d)$.

> **MUST:** $\rho$ is fresh **per instance** $(vk, x)$. Reusing $\rho$ across different inputs $x^{(k)}$ lets colluding decappers solve a linear system to recover the separate $\beta_2^\rho$ and $B_i(\tau)^\rho$ for public $i$, which re-opens the original algebraic attack.

### 4.2 Decrypt (decap) — input: hdr and a **witness** $w$

A party who knows a Groth16 witness for $(vk, x)$ proceeds as follows (they need $pk$ to run Groth16.Prove):

1. **Run Groth16.Prove** on $(vk, pk, x, w)$ to obtain a proof $\pi = (A, B, C)$ and the implicit scalars $\{a_i\}_{i>\ell}$ and $s$ such that
$$
B = B_{\mathrm{pub}} + \sum_{i>\ell} a_i \cdot B_i(\tau) + s \cdot \delta_2
$$
*(The decapper must **run Prove** and retain $\{a_i\}_{i>\ell}$ and $s$; verifying someone else's proof does not expose these.)*

2. **Compute**:
$$
\tilde{M} := e(A, D_{\mathrm{pub}}) \cdot \prod_{i>\ell} e(a_i \cdot A, D_i) \cdot e(s \cdot A - C, D_\delta)
$$

3. **Derive** $K' = \mathrm{KDF}\big(\mathrm{ser}_{G_T}(\tilde{M}) \,|\, d\big)$ and use it to decrypt the payload.

(If a *publicly verifiable* decap is desired, the decapper can additionally publish a GS proof with DLREP ties that the $\{A, \{a_i\}, s, C\}$ used above are consistent with a valid Groth16 proof; this is optional and not required for decryption.)

---

## 5) Correctness

By bilinearity and the decomposition of $B$,

$$
\begin{align}
\tilde{M} &= e(A, B_{\mathrm{pub}}^\rho) \cdot \prod_{i>\ell} e(a_i \cdot A, B_i(\tau)^\rho) \cdot e(s \cdot A, \delta_2^\rho) \cdot e(-C, \delta_2^\rho) \\
&= e\big(A, [\rho](B_{\mathrm{pub}} + B_{\mathrm{wit}} + s\cdot\delta_2)\big) \cdot e(-C, [\rho]\delta_2) \\
&= e(A, B)^\rho \cdot e(-C, \delta_2)^\rho \\
&= \big(e(A, B) \cdot e(-C, \delta_2)\big)^\rho \\
&= \big(e(\alpha_1, \beta_2) \cdot e(\mathrm{IC}(x), \gamma_2)\big)^\rho \\
&= R(vk, x)^\rho
\end{align}
$$

where the penultimate equality applies (G16): $e(A, B) = e(\alpha_1, \beta_2) \cdot e(\mathrm{IC}(x), \gamma_2) \cdot e(C, \delta_2)$. Hence $K' = K$.

---

## 6) Security posture

### Adversary model

An adversary sees $vk, x$, the ordered right-leg descriptor $Y'$, the masks $(D_{\mathrm{pub}}, \{D_j\}_{j>\ell}, D_\delta)$, and $R(vk, x)$. It **does not** see $\beta_2^\rho$, $B_i(\tau)^\rho$ for public $i \leq \ell$, or $\gamma_2^\rho$. The adversary's WE goal is to compute $M = R(vk, x)^\rho$ **without** a witness.

### Defense rationale

* The original break exploited **per-basis masks** $\beta_2^\rho$ and $B_i(\tau)^\rho$ for public $i$, together with the identity (for public inputs with $C_i \equiv 0$):
$$
e(\gamma_{abc}[i], \gamma_2)^\rho = e(A_i(\tau), \beta_2^\rho) \cdot e(\alpha_1, B_i(\tau)^\rho)
$$
Summing over $i \leq \ell$ gave $e(\mathrm{IC}(x), \gamma_2)^\rho$ without a witness, and hence $R^\rho$.

* **Defense 1** removes those handles: the only public $B$-side mask is the **aggregate**
$D_{\mathrm{pub}} = B_{\mathrm{pub}}^\rho$.
There is no way to extract $\beta_2^\rho$ or individual $B_i(\tau)^\rho$ from $D_{\mathrm{pub}}$ alone.

* **No $\rho$ reuse** prevents recovering the separate $\beta_2^\rho$ and $B_i(\tau)^\rho$ by solving a linear system across different $x$.

Under this discipline, the "algebraic factorization" path is closed.

### Core hardness (no-witness decap)

With only $(Y', Y'^\rho, R)$ available and $R(vk,x)$ fixed by $(vk,x)$ and **independent** of $\rho$, any method to compute $R^\rho$ (or to choose $\{X\} \in G_1$ so that $\prod e(X, Y'^\rho) = R^\rho$) would solve a standard **external-power** problem in bilinear groups. This is captured by the usual **SXDH/DDH-in-$G_2$** flavor: informally, given $(Y, Y^\rho)$ and an independent $R \in G_T$, one cannot compute $R^\rho$ or program $\{X\}$ so that $\prod e(X, Y^\rho) = R^\rho$ in polynomial time.

> **Takeaway:** For an attacker who **skips DLREP/GS entirely** and just tries to "decap as a prover", the problem reduces to deriving $R^\rho$ from the masked right-legs—which is exactly what Defense 1 + "no $\rho$ reuse" are designed to block under SXDH/AGM-style assumptions.

### Optional public verifiability

If we *also* want a public proof that a decapper used a genuine Groth16 witness, require a **GS proof with DLREP ties** that pins
$(X_{\mathrm{pub}}, \{X_j\}_{j>\ell}, X_\delta, C) = (A, \{a_j A\}, s A, C)$ and attests

$$
e(A, B) \cdot e(C, \delta_2) = e(\alpha_1, \beta_2) \cdot e(\mathrm{IC}(x), \gamma_2)
$$

Any accepting GS witness for that statement (binding setting) gives a valid Groth16 proof; there is no "$G_T$-mixing" overhang once the single-$A$ linkage and the native Groth16 equation are enforced.

### Optional circuit hardening (Defense 2)

To add extra margin, we may compile the circuit so that every public input (and the 1-wire) has $C_i \not\equiv 0$ (e.g., a tiny copy-to-output gadget). Then even if an implementation mistake were to expose additional public-subspace masks, the clean factorization used in the original attack no longer holds.

---

## 7) Hygiene and edge cases

* **Fresh $\rho$ per $(vk, x)$ (MUST):** never reuse $\rho$ across different inputs for the same $vk$. If we derive $\rho$ deterministically, include a per-instance salt in $d$.

* **Right-leg discipline (MUST):** publish *only*
$D_{\mathrm{pub}} = B_{\mathrm{pub}}^\rho$, $D_j = B_j(\tau)^\rho$ for $j > \ell$, $D_\delta = \delta_2^\rho$.
Do **not** publish $\beta_2^\rho$ or $B_i(\tau)^\rho$ for $i \leq \ell$, **nor any alternate $G_2$ basis (e.g., monomials $g_2^{\tau^k}$) that linearly spans** the public subspace with known coefficients.

* **Domain binding (MUST):** bind the exact ordered list $Y'$ into $d$; reject any header whose descriptor does not match.

* **Group hygiene (MUST):** subgroup checks/cofactor clearing on all published points; canonical encodings; reject if $R(vk, x) = 1_{G_T}$ (degenerate anchor).

* **If we adopt Defense 2:** require $C_i \not\equiv 0$ for every public input in the compiled circuit (one-time per-circuit choice; new circuit $\Rightarrow$ new SRS).

---

### Summary

This scheme:
* Defines the **R1CS/QAP** with standard Groth16 notation and assumptions
* **CRS / public parameters** are enumerated (including that encryptor needs $pk$)
* **Encryptor (arming)**: exactly which masked right-legs are published; how $d$ is computed; how $M$ and $K$ are derived
* **Decryptor**: exactly how a holder of a witness computes $\tilde{M}$ (must run Prove themselves); optional public verifiability via GS+DLREP
* **Security**: Holds by publishing only the aggregated public mask $D_{\mathrm{pub}}$ and enforcing fresh $\rho$ per instance, with $R(vk,x)$ independent of $\rho$, reducing security to standard external-power assumptions (SXDH/DDH-in-$G_2$)