# Threshold Decryption in TEEs

## Problem Statement

Traditional encryption systems face a fundamental dilemma: either a single party controls the decryption key (creating a single point of failure and trust), or the key must be split among multiple parties (requiring complex key management and risking key reconstruction attacks).

In high-stakes environments—financial systems, healthcare data, government communications—neither approach is acceptable. We need a system where:
- **No single entity** can decrypt data alone
- **No single entity** ever possesses the complete decryption key
- **Threshold cooperation** is required for any decryption
- **Malicious participants** cannot compromise the system

## High-Level Approach

Our solution combines three cryptographic primitives: **Distributed Key Generation (DKG)** creates a public key without any party knowing the private key, **threshold ElGamal encryption** protects a symmetric key using the distributed public key, and **Trusted Execution Environments (TEEs)** coordinate threshold decryption while maintaining confidentiality. The result is a system where `t` out of `n` key servers must cooperate to decrypt data, but the actual decryption happens in a secure enclave that never sees individual key shares.

### TL;DR (Technical Summary)

Let **n** servers jointly run a DKG to derive a public key **PK** (no one ever sees the full secret).
A client hybrid‑encrypts: `c_a = Enc_sym(s, M)` and `k = Enc_asym(PK, s)`.
A TEE gathers ≥ t verifiable partial decryptions `{k_i}` from key servers, reconstructs **s** via Lagrange interpolation, and unlocks **M**—all without any single party holding **SK**.

Let's examine each component in detail.

“Wait… who actually knows the private key?”
**Answer:** No one, ever. That’s the point of DKG. Let’s show it.

## 1. Key‑pair creation (Threshold / DKG style)

**Setup:** Work in a cyclic group $\mathbb{G}$ of prime order $q$ with generator $g$ and independent generator $h$.
We want a threshold $t = 2$ out of $n = 3$ nodes. We'll work in a toy setting with small prime $q = 17$.

### 1.1 Each node’s secret polynomial and blinding polynomial

The first step in our DKG protocol is for each node to generate its contribution to the eventual shared key. Rather than generating the key directly, each node creates a polynomial whose coefficients will be combined with other nodes' polynomials.

Each node $i \in \{1, 2, 3\}$ selects:
- A degree-$(t-1)$ secret polynomial $f_i(x) = a_{i,0} + a_{i,1}x$
- A degree-$(t-1)$ blinding polynomial $r_i(x) = b_{i,0} + b_{i,1}x$

Example setup:

- Node 1:
- $f_1(x) = 4 + 6x$
- $r_1(x) = 3 + 2x$
- Node 2:
- $f_2(x) = 5 + 7x$
- $r_2(x) = 4 + 1x$
- Node 3:
- $f_3(x) = 2 + 3x$
- $r_3(x) = 6 + 5x$

### 1.2 Commitments to ensure honesty

Each node publishes **Pedersen commitments**:

$$
C_{i,\ell} = g^{a_{i,\ell}} h^{b_{i,\ell}} \mod q, \quad \ell = 0, 1
$$

These Pedersen commitments prove honesty without revealing secrets—critical for trustless distributed keygen.

Using $g = 3$, $h = 5$, $q = 17$:

- Node 1:
- $C_{1,0} = 3^4 \cdot 5^3 = 13 \cdot 6 = 78 \mod 17 = 10$
- $C_{1,1} = 3^6 \cdot 5^2 = 15 \cdot 8 = 120 \mod 17 = 1$
- Node 2:
- $C_{2,0} = 3^5 \cdot 5^4 = 11 \cdot 13 = 143 \mod 17 = 7$
- $C_{2,1} = 3^7 \cdot 5 = 11 \cdot 5 = 55 \mod 17 = 4$
- Node 3:
- $C_{3,0} = 3^2 \cdot 5^6 = 9 \cdot 2 = 18 \mod 17 = 1$
- $C_{3,1} = 3^3 \cdot 5^5 = 10 \cdot 6 = 60 \mod 17 = 9$

### 1.3 Share distribution + verification
With commitments published, nodes can now safely exchange their polynomial evaluations. The key insight is that each share comes with cryptographic proof of correctness—if a node tries to cheat, the verification will fail.

Once shares are verified, each node aggregates what it received to compute their local private share.

Each node evaluates $f_i(j)$ and $r_i(j)$ for each $j \neq i$.

**Node 1 → Node 2:**
- $s_{1→2} = f_1(2) = 4 + 6 \cdot 2 = 16$
- $\rho_{1→2} = r_1(2) = 3 + 2 \cdot 2 = 7$

**Node 1 → Node 3:**
- $s_{1→3} = f_1(3) = 4 + 6 \cdot 3 = 22 \mod 17 = 5$
- $\rho_{1→3} = r_1(3) = 3 + 6 = 9$

**Verification by receiver:**

$$
g^{s_{i→j}} h^{\rho_{i→j}} \stackrel{?}{=} \prod_{\ell=0}^{t-1} C_{i,\ell}^{j^\ell} \mod q
$$

**Example: Verify Node 1’s share to Node 2:**
- LHS = $g^{16} \cdot h^7 = 1 \cdot 10 = 10$
- RHS = $C_{1,0}^1 \cdot C_{1,1}^2 = 10 \cdot 1 = 10$ ✅

### 1.4 Final shares and joint key

Each node computes:

$$
SK_j = \sum_{i=1}^n f_i(j) \mod q
$$

Results:
- $SK_1 = 10$
- $SK_2 = 9$
- $SK_3 = 8$

The global secret:

$$
SK = a_{1,0} + a_{2,0} + a_{3,0} = 4 + 5 + 2 = 11
$$

Public key:

$$
PK = g^{SK} = 3^{11} \mod 17 = 7
$$

✅ Final state: each node holds a unique $SK_j$, and the network knows $PK$.

Now we have our distributed key infrastructure in place. The next question is: how does a client actually use this system to encrypt sensitive data? The client needs to encrypt their message in a way that only the coordinated effort of multiple key servers can decrypt it—without any single server ever seeing the full decryption key.*

---

## 2. Client-side hybrid encryption

The client uses a hybrid approach that combines the speed of symmetric encryption with the security properties of our threshold public key system.

### 2.1 Why hybrid encryption?

Pure threshold ElGamal encryption would require encrypting the entire message $M$ directly, which is computationally expensive for large messages and reveals message length patterns. Instead, we use the threshold system only to protect a small symmetric key.

### 2.2 The encryption process

1. Generate random symmetric key $s$
2. Encrypt message:

$$
c_a = \text{Enc}_{sym}(s, M)
$$

3. Encrypt $s$ using ElGamal under $PK$:
r ← random(ℤ_q)
$$
k = (u, v) = (g^r, s \cdot PK^r)
$$

The randomness $r$ ensures that even identical symmetric keys produce different ciphertexts, preventing pattern analysis.

Send $(c_a, k)$ to the TEE.

At this point, the client has sent encrypted data to the TEE, but the TEE faces a challenge: it needs to decrypt the symmetric key $s$ from the ElGamal ciphertext $k$, but it doesn't have the private key $SK$.

Instead, it must orchestrate a threshold decryption process across multiple key servers, each holding only a fragment of the decryption capability.

## 3. Threshold decryption inside TEE

Since each node only reveals a blinded exponentiation and never its full share, and the TEE never sees individual keys, this maintains threshold security even if some nodes or the TEE are compromised.

Each node computes partial decryption:

$$
k_j = u^{SK_j}
$$

and sends it with a ZK proof.

TEE waits for ≥ t valid $k_j$ values and reconstructs:

$$
u^{SK} = \prod_{j \in S} k_j^{\lambda_j(0)}
$$

$$
\lambda_j(0) = \prod_{\ell \in S \setminus \{j\}} \frac{-\ell}{j - \ell}
$$
$\lambda_j(0)$ are computed over the field $\mathbb{F}_q$

Decrypt:

$$
s = \frac{v}{u^{SK}}, \quad M = \text{Dec}_{sym}(s, c_a)
$$

The mathematical protocol above shows how threshold decryption works in theory. But moving from cryptographic primitives to a production system raises additional questions about security assumptions, performance trade-offs, and practical attack vectors that weren't addressed in the academic literature.

## 4. From Concept to Production

| What you said | What we do |
| --- | --- |
| “Trusted dealer creates PK” | Use DKG; no single party holds SK |
| “Shamir secret shares” | Yes, plus verifiable Pedersen commitments |
| “Delete key and shards” | Keys never assembled; shares stored in sealed state |
| “Nodes send decrypted key” | They send $k_j$ with ZK proofs |
| “TEE decrypts inside enclave” | Yes, using Lagrange interpolation |
| “Random symmetric key at client” | Yes, ensures AEAD encryption and speed |
| “Replay?” | Use ciphertext binding and request rate limits |

---

## Notation

- $\mathbb{G}$ — prime-order group
- $g$, $h$ — generators
- $q$ — group order
- $f_i(x)$ — secret polynomial
- $r_i(x)$ — blinding polynomial
- $s_{i→j}$ — share sent to node $j$
- $SK_j$ — private key share of node $j$
- $PK$ — joint public key
- $k_j$ — partial decryption
- $\lambda_j(0)$ — Lagrange coefficient
- $u^{SK}$ — reconstructed exponentiation
- $s$ — recovered symmetric key