Decryption Protocol

How the anonymity revoking key is generated, how decryption is performed, and how proofs of correct decryption are constructed.

In production, the anonymity revoking key is held by a Guardian Committee — a quorum of t out of n guardians operating as a threshold committee. No single guardian can decrypt on their own; cooperation of at least t guardians is required. However, the threshold setting builds directly on the single-guardian case. For educational purposes, this document first describes the protocol for a single guardian (Part 1), which covers the core cryptographic ideas — key generation, decryption, and proofs of correctness — without the added complexity of secret sharing. Part 2 then extends everything to the threshold setting, with frequent references back to Part 1.

This section focuses on the high-level cryptographic protocol. It does not address how to realize it securely on concrete hardware or via concrete software (e.g. key storage on HSMs, secure communication channels between guardians, software architecture of the guardian node). These operational and implementation details will be added in a subsequent iteration of this documentation.

---

Part 1: Single Guardian

Key Generation

The guardian generates a key pair on the Grumpkin curve:

1. Sample a random scalar ar_sk from the curve's scalar field. This is the anonymity revoking secret key.
2. Compute the corresponding public key: AR_PK = ar_sk·G, where G is the Grumpkin generator. This is the anonymity revoking public key — a Grumpkin point.

Element	Type	Visibility	Description
ar_sk	Scalar (element of the curve's scalar field)	Secret — known only to the guardian	The anonymity revoking private key.
AR_PK	Grumpkin point	Public — registered on-chain	The anonymity revoking public key: ar_sk·G.
G	Grumpkin point	Public — fixed system parameter	The generator of the Grumpkin curve.

The public key AR_PK is stored on-chain in the contract as arPK (see On-Chain Components: Anonymity Revoking Key) and is used by circuits to encrypt compliance payloads. The secret key ar_sk never leaves the guardian's secure environment.

Message Abstraction

Throughout this section, we treat the encrypted message as a group element M (a Grumpkin point) and describe how to recover M from its ciphertext. We intentionally ignore the fact that in our system M = m·G for some scalar m (the actual amount), because for the decryption protocol this is an irrelevant detail.

The decryption protocol outputs M. The additional step of extracting the scalar m such that M = m·G — solving a bounded discrete log — is handled by the discrete-log solver and belongs to a different layer of the system. The serialization (mapping scalars to group elements via m ↦ m·G before encryption) and deserialization (recovering m from M after decryption) are not discussed further here.

Decryption

Given a ciphertext (R, C) produced by ElGamal encryption:

• R = r·G — the ephemeral public key (where r is the random scalar chosen by the encryptor)
• C = M + r·AR_PK — the encrypted message

the guardian decrypts by computing:

D = ar_sk·R
M = C − D

Correctness. Since AR_PK = ar_sk·G, we have D = ar_sk·r·G = r·AR_PK, and therefore:

C − D = (M + r·AR_PK) − r·AR_PK = M

Why a Proof of Correct Decryption is Needed

The guardian could simply reveal M and claim it is the correct decryption. But how does anyone verify this? Given only the ciphertext (R, C) and a claimed plaintext M, there is no way to check correctness without either knowing the secret key or trusting the guardian blindly.

To make decryption publicly verifiable, the guardian must provide a proof of correct decryption — a zero-knowledge proof that the decryption share D was computed using the same secret key ar_sk that defines the public key AR_PK. Concretely, the guardian must prove:

log_G(AR_PK) = log_R(D)

i.e. there exists a scalar (namely ar_sk) such that AR_PK = ar_sk·G and D = ar_sk·R. This is the Discrete Log Equality (DLEQ) problem.

Discrete Log Equality (DLEQ)

The Problem

Given two base points P₁ and P₂, and two target points Q₁ and Q₂, prove that:

log_{P₁}(Q₁) = log_{P₂}(Q₂)

That is, there exists a scalar x such that Q₁ = x·P₁ and Q₂ = x·P₂, without revealing x.

The Chaum-Pedersen Protocol

The following non-interactive protocol (the Fiat-Shamir transform of the interactive Chaum-Pedersen protocol) proves DLEQ(P₁, Q₁, P₂, Q₂):

Prover (knows x such that Q₁ = x·P₁ and Q₂ = x·P₂):

1. Sample a random scalar k.
2. Compute commitments: A₁ = k·P₁ and A₂ = k·P₂.
3. Compute the challenge: e = Hash(P₁, Q₁, P₂, Q₂, A₁, A₂).
4. Compute the response: z = k − e·x mod q (where q is the curve order).
5. Output the proof π = (e, z).

Verifier (given P₁, Q₁, P₂, Q₂ and proof π = (e, z)):

1. Reconstruct the commitments:
   • A₁ = z·P₁ + e·Q₁
   • A₂ = z·P₂ + e·Q₂
2. Recompute the challenge: e' = Hash(P₁, Q₁, P₂, Q₂, A₁, A₂).
3. Accept if and only if e' = e.

Correctness. If the prover is honest (Q₁ = x·P₁, Q₂ = x·P₂, and z = k − e·x):

z·P₁ + e·Q₁ = (k − e·x)·P₁ + e·x·P₁ = k·P₁ = A₁  ✓
z·P₂ + e·Q₂ = (k − e·x)·P₂ + e·x·P₂ = k·P₂ = A₂  ✓

The reconstructed commitments match the originals, so the recomputed challenge equals e.

Soundness. If the prover does not know a common x (or uses different values for Q₁ and Q₂), they cannot produce a valid (e, z) pair, assuming Hash behaves as a random oracle.

Zero-knowledge. The proof reveals nothing about x beyond the fact that log_{P₁}(Q₁) = log_{P₂}(Q₂). The values e and z are uniformly distributed from the verifier's perspective.

Applying DLEQ to Decryption

To prove correct decryption of a ciphertext (R, C), the guardian instantiates the DLEQ proof with:

DLEQ parameter	Instantiation	Meaning
P₁	G	Grumpkin generator
Q₁	AR_PK	Public key ar_sk·G
P₂	R	Ephemeral key from ciphertext
Q₂	D	Decryption share ar_sk·R

The proof establishes that the same ar_sk relates AR_PK to G and D to R, which guarantees M = C − D is the correct plaintext.

Complete Single-Guardian Decryption

To decrypt a ciphertext (R, C) with public verifiability, the guardian:

1. Computes D = ar_sk·R.
2. Computes M = C − D.
3. Produces a DLEQ proof π proving DLEQ(G, AR_PK, R, D).
4. Publishes (M, π).

Any verifier can compute D = C − M from the published plaintext and the public ciphertext, then check the DLEQ proof using G, AR_PK, R, and D, confirming that the decryption is correct without learning anything about ar_sk.

---

Part 2: Threshold Committee (t-of-n)

In the threshold setting, the secret key ar_sk is never held by any single party. Instead, it is distributed across n guardians such that any t of them can cooperate to decrypt, but fewer than t learn nothing about the plaintext.

The core ideas are the same as Part 1 — decryption still reduces to computing D = ar_sk·R, and correctness is still proved via DLEQ. The difference is that D is assembled from partial shares contributed by individual guardians, each accompanied by its own DLEQ proof.

Notation

Symbol	Description
n	Total number of guardians.
t	Threshold — the minimum number of guardians required to decrypt.
f_i(x)	Guardian i's secret polynomial of degree t−1.
a_{i,k}	Coefficient k of guardian i's polynomial (k = 0, …, t−1).
A_{i,k}	Feldman commitment: A_{i,k} = a_{i,k}·G.
s_{i→j}	The share that guardian i sends to guardian j: s_{i→j} = f_i(j).
x_j	Guardian j's combined secret share: x_j = Σᵢ s_{i→j}.
VK_j	Guardian j's verification key: VK_j = x_j·G.
λ_j	Lagrange coefficient for guardian j in a given participating set.

Note that in Part 1 we used ar_sk for the single guardian's secret key. In the threshold setting, ar_sk still exists conceptually — it is the combined secret Σᵢ a_{i,0} — but no party ever holds it. Each guardian j only knows their share x_j.

Distributed Key Generation (DKG)

The DKG protocol generates the shared key pair (ar_sk, AR_PK) without any single party learning ar_sk. It is built from n parallel instances of Feldman's Verifiable Secret Sharing (VSS).

This protocol is non-robust: a single misbehaving guardian can cause the ceremony to abort (by sending invalid shares, publishing inconsistent commitments, or simply going offline). This is acceptable in our setting because the guardian set is small and explicitly appointed. A misbehaving guardian is identified during verification, can be replaced, and the ceremony restarted. A robust DKG (one that completes even when some parties misbehave) would add significant complexity without meaningful benefit for our use case.

Feldman VSS (Building Block)

Feldman's Verifiable Secret Sharing allows a single dealer to share a secret among n parties such that any t can reconstruct it, while every party can verify that their share is consistent with publicly committed values. In the DKG, every guardian acts as a dealer simultaneously — but it is easier to understand the building block first.

Setup. A dealer holds a secret a₀ (a scalar) and wants to share it among n parties with threshold t.

Step 1 — Choose polynomial. The dealer samples random scalars a₁, …, a_{t−1} and defines:

f(x) = a₀ + a₁·x + a₂·x² + … + a_{t−1}·x^{t−1}

The secret is f(0) = a₀. The polynomial has degree t−1, so any t evaluations uniquely determine it.

Step 2 — Publish commitments. The dealer computes and broadcasts the Feldman commitments:

A_k = a_k·G    for k = 0, 1, …, t−1

Note that A₀ = a₀·G is the public key corresponding to the secret. The commitments are group elements (Grumpkin points) — they reveal nothing about the scalar coefficients (under the discrete log assumption), but allow verification of shares.

Step 3 — Distribute shares. The dealer computes a share for each party j:

s_j = f(j)    for j = 1, 2, …, n

and sends s_j to party j over a private channel. Each share is a scalar.

Step 4 — Verify shares. Party j verifies their share by checking:

s_j·G  ==  Σ_{k=0}^{t−1} j^k · A_k

This works because the right-hand side equals:

Σ_{k=0}^{t−1} j^k · (a_k·G) = (Σ_{k=0}^{t−1} a_k · j^k)·G = f(j)·G = s_j·G

The verification is performed entirely with public values (the commitments A_k) and the private share s_j. It confirms that s_j is consistent with the committed polynomial, without revealing anything about other parties' shares.

If verification fails, party j broadcasts a complaint. In our non-robust setting, any complaint causes the protocol to abort.

DKG Protocol

The DKG is n parallel Feldman VSS instances: each guardian acts as a dealer sharing their own random secret, and simultaneously acts as a receiver for all other guardians' shares.

Round 1 — Share and Commit. Each guardian i (for i = 1, …, n):

1. Samples a random polynomial of degree t−1:

   f_i(x) = a_{i,0} + a_{i,1}·x + … + a_{i,t−1}·x^{t−1}

   where a_{i,0} is guardian i's secret contribution.

2. Broadcasts Feldman commitments:

   A_{i,k} = a_{i,k}·G    for k = 0, 1, …, t−1

3. Sends the share s_{i→j} = f_i(j) to each other guardian j over a private channel.

Round 2 — Verify. Each guardian j:

1. For each guardian i, verifies the received share:

   s_{i→j}·G  ==  Σ_{k=0}^{t−1} j^k · A_{i,k}

2. If any verification fails, broadcasts a complaint and the protocol aborts.

Output. If all shares verify, each guardian j computes their combined secret share:

x_j = Σ_{i=1}^{n} s_{i→j}

This is a scalar — the sum of all the individual shares that guardian j received.

The system-wide outputs are:

Output	Formula	Who knows it
Combined secret key ar_sk	Σ_{i=1}^{n} a_{i,0}	Nobody — never computed or reconstructed.
Public key AR_PK	Σ_{i=1}^{n} A_{i,0}	Everyone — computed from public commitments.
Guardian j's share x_j	Σ_{i=1}^{n} f_i(j)	Only guardian j.
Guardian j's verification key VK_j	x_j·G	Everyone — computable from public commitments (see below).

Public key. AR_PK = Σ_{i=1}^{n} A_{i,0} = Σ_{i=1}^{n} a_{i,0}·G = (Σ_{i=1}^{n} a_{i,0})·G = ar_sk·G. This is the same form as in the single-guardian case (Part 1), and is registered on-chain in the same way.

Verification keys. Each guardian j's verification key can be computed by anyone from the published Feldman commitments:

VK_j = Σ_{i=1}^{n} Σ_{k=0}^{t−1} j^k · A_{i,k}

This equals x_j·G because:

Σ_{i=1}^{n} Σ_{k=0}^{t−1} j^k · A_{i,k}  =  Σ_{i=1}^{n} Σ_{k=0}^{t−1} j^k · a_{i,k} · G  =  (Σ_{i=1}^{n} f_i(j)) · G  =  x_j · G

Equivalently, defining the combined commitments F_k = Σ_{i=1}^{n} A_{i,k}, the verification key simplifies to:

VK_j = Σ_{k=0}^{t−1} j^k · F_k

The verification keys play the same role in threshold decryption that AR_PK plays in the single-guardian case: they allow anyone to verify a guardian's partial decryption share using a DLEQ proof.

Why this produces a valid secret sharing. The combined polynomial F(x) = Σ_{i=1}^{n} f_i(x) has degree t−1, with F(0) = ar_sk and F(j) = x_j. By the properties of Shamir's secret sharing, any t evaluations of a degree t−1 polynomial uniquely determine it. Therefore any t shares {x_j} are sufficient to reconstruct F(0) = ar_sk (via Lagrange interpolation). Fewer than t shares reveal no information about ar_sk — this is information-theoretic security inherited from Shamir's scheme.

Threshold Decryption

Given a ciphertext (R, C), a subset S of at least t guardians cooperate to decrypt. The protocol closely mirrors the single-guardian case from Part 1: instead of one decryption share D = ar_sk·R, we assemble D from partial shares, each proved correct with a DLEQ proof.

Step 1: Partial Decryption

Each participating guardian j ∈ S:

1. Computes their partial decryption share: D_j = x_j·R.
2. Produces a DLEQ proof π_j proving:

   log_G(VK_j) = log_R(D_j)

   This is the same Chaum-Pedersen DLEQ proof from Part 1, instantiated with P₁ = G, Q₁ = VK_j, P₂ = R, Q₂ = D_j. It proves that guardian j used their genuine secret share x_j to compute D_j.
3. Sends (D_j, π_j) to the combiner.

Step 2: Verify and Combine

The combiner collects the partial shares and assembles the result. The combiner does not need to be trusted — everything it does is publicly verifiable.

1. Verify each proof π_j using the public values G, VK_j, R, D_j. If any proof fails, reject that guardian's contribution (and either abort or request a replacement share from another guardian, depending on operational policy).

2. Compute Lagrange coefficients for the participating set S. For each j ∈ S:

   λ_j = Π_{k ∈ S, k ≠ j}  k / (k − j)   mod q

   These are the standard Lagrange basis polynomials evaluated at x = 0. They depend only on the indices in S, not on any secret values.

3. Combine the partial decryption shares:

   D = Σ_{j ∈ S} λ_j · D_j

4. Recover the plaintext:

   M = C − D

Correctness

The combined decryption share equals:

D = Σ_{j ∈ S} λ_j · D_j = Σ_{j ∈ S} λ_j · (x_j · R) = (Σ_{j ∈ S} λ_j · x_j) · R

By the Lagrange interpolation theorem, since the x_j = F(j) are evaluations of a polynomial F of degree t−1, and |S| ≥ t:

Σ_{j ∈ S} λ_j · x_j = F(0) = ar_sk

Therefore D = ar_sk·R, exactly as in the single-guardian case, and:

M = C − D = (M + r·AR_PK) − ar_sk·R = M + r·ar_sk·G − ar_sk·r·G = M

Public Verifiability

The entire decryption is publicly verifiable. An observer who has access to the individual partial shares and verification keys can check each guardian's DLEQ proof π_j against VK_j, recompute the Lagrange combination, and verify M = C − D. This is the "full" verification path, useful for auditing the guardians' behavior.

However, an external verifier (e.g. a compliance officer or a court) may only know (R, C), AR_PK, and the claimed plaintext M — they do not know the individual guardians' verification keys or partial shares. For this setting, the combiner (or the guardian committee collectively) can produce a single aggregate proof of correct decryption: a DLEQ proof π proving

DLEQ(G, AR_PK, R, D)    where D = C − M

This is exactly the same single-guardian DLEQ proof from Part 1. To produce it without reconstructing ar_sk, the combiner assembles the proof from the partial DLEQ proofs as follows:

1. Each guardian j ∈ S produces their partial proof with commitment (A_{1,j}, A_{2,j}), challenge e_j, and response z_j as in the standard DLEQ protocol, but using a shared challenge. Concretely, the guardians first exchange commitments, then compute a common challenge:

   e = Hash(G, AR_PK, R, D, Σ_{j ∈ S} λ_j · A_{1,j}, Σ_{j ∈ S} λ_j · A_{2,j})

   and each guardian responds with z_j = k_j − e · x_j mod q.

2. The combiner aggregates:

   z = Σ_{j ∈ S} λ_j · z_j mod q

3. The final proof is π = (e, z).

Verification. Given only (R, C), AR_PK, M, and proof π = (e, z), the verifier:

1. Computes D = C − M.
2. Reconstructs A₁ = z·G + e·AR_PK and A₂ = z·R + e·D.
3. Checks e == Hash(G, AR_PK, R, D, A₁, A₂).

This is identical to verifying a single-guardian DLEQ proof. The verifier does not need to know t, n, S, the individual VK_j, or any detail of the threshold scheme — only the public key AR_PK and the ciphertext.

---

Key Rotation

Key rotation replaces the anonymity revoking key pair with a fresh one. This involves three steps:

1. New DKG ceremony. The guardians (possibly the same set, possibly a different one) run a new DKG to produce a fresh key pair (ar_sk', AR_PK').

2. On-chain key update. The contract's stored arPK is updated to AR_PK'. The mechanism for authorizing this update (e.g. multisig, governance vote) is an operational decision.

3. Transition period. Ciphertexts created before the rotation were encrypted under the old key AR_PK and can only be decrypted with the old key. Ciphertexts created after the rotation use the new key AR_PK'. The old key material (specifically, the guardians' shares of the old ar_sk) must be retained until there is no further need to decrypt historical compliance payloads encrypted under the old key.

The exact governance mechanism for triggering key rotation, the policy for retaining old key material, and the procedure for transitioning the guardian set are operational decisions not covered here.