Aegon: How a Self-Auditable Key Transparency System Solves the Auditing Problem

In end-to-end encrypted messaging, servers are responsible for distributing public keys—but if a malicious server quietly swaps in an attacker's public key, the encryption remains "perfect" while private messages are sent to the wrong person. Key Transparency was created precisely to solve this problem. At the Cryptography Talk Series, Hossein Hafezi from the University of Cambridge presented his team's new work Aegon, a self-auditable key transparency system. It is the successor to the earlier IronDict, targeting the most expensive component of existing deployments (Signal, WhatsApp, iMessage): auditing.

The Core Contradiction of Key Transparency: Who Does the Auditing?

The basic model of key transparency is not complicated: the server divides time into epochs, and in each epoch publishes a directory commitment and state transition proofs on a public bulletin board. Clients do two things—query others' public keys (lookup), and prove that their own public key has not been tampered with from epoch i to epoch j (consistency proof).

The problem lies in how consistency proofs are constructed. The early Coniks scheme required clients to check every epoch one by one, with computation growing the longer a client stayed offline—impractical for ordinary users. The Seamless family of schemes introduced version numbers and an auditor role: version numbers increment only when a public key changes, and the auditor verifies each epoch whether the server has followed the rules. When a client returns, it only needs to compare the first and last version numbers, greatly reducing the burden. This approach has been adopted by Signal, WhatsApp, and iMessage.

But the auditor's burden is not light either. According to data given in the talk, the auditor for WhatsApp's key transparency must download and hash about 80MB of data per minute. This forces real deployments to rely on external auditing services—WhatsApp uses Cloudflare, and Signal uses Cloudflare and Trail of Bits. Hafezi also pointed out a role confusion problem: the bulletin board (which guarantees a consistent view) and auditing (computational verification) are logically distinct roles, yet are filled by the same organization. The bulletin board only needs to exchange a small number of authenticated Merkle roots and could involve a large number of nodes; auditing, meanwhile, can be done independently and in parallel.

Merkle trees are the most commonly used commitment structure in key transparency schemes. The server arranges all username–public key pairs as leaf nodes in some order, hashes them layer by layer to obtain a root hash, and publishes it. Any client holding the root hash and a path from a leaf to the root (about log n hash values) can verify that a given public key is indeed in the directory. Its advantages are that proof size grows logarithmically with the number of entries and verification is extremely fast; its disadvantage is that every update changes the root, and an auditor must confirm "the new root is the old root plus legitimate updates" requiring additional proofs, which accumulate and bloat with the volume of updates—this is precisely the root cause of WhatsApp needing to download tens of MB of audit data per epoch.

IronDict's Approach: Replacing Merkle Trees with Polynomial Commitments

Nearly all existing deployments are based on Merkle trees, which scale well but whose audit proofs bloat with the volume of updates. The algebraic route (such as VerSA) can compress proofs, but server costs struggle to support millions of entries or more. IronDict chose a middle path: building a transparent dictionary with polynomial commitments.

Specifically, a multilinear polynomial is uniquely determined by its values on the Boolean hypercube, so a table can be represented as a polynomial; after committing to it with a polynomial commitment scheme (PCS), opening at a Boolean point proves the value at a given position. In real scenarios, labels and values are arbitrary strings: values are mapped to field elements via a collision-resistant hash (with 0 reserved to indicate an empty slot); labels are assigned positions via open addressing—hashing the label with a counter generates a candidate sequence, probing the next slot when occupied, with about 4x overprovisioning needed for efficiency.

IronDict maintains two mappings: an index mapping that records the stable assignment of labels to internal positions, and a value mapping that records the value at the current position. Consistency proofs rely on a "randomized consistency mechanism": the difference vector between adjacent epochs is multiplied by a random challenge and then accumulated. The server must commit to updates before learning the challenge, so a change and its reversal cannot automatically cancel out—this precisely defends against the "ghost key" attack (temporarily replacing a key and then restoring it). Clients only need to compare the authenticated openings of the randomized vectors at the endpoints.

A polynomial commitment scheme (PCS) allows a committer to generate a short commitment C to a polynomial f, and later open f(x) at any point x with a proof; the verifier can use C and the proof to confirm that the value is correct without knowing the full coefficients of f. Security relies on cryptographic assumptions: an adversary cannot find two different polynomials that open to different values under the same commitment. Common instantiations include KZG (pairing-based, with constant-size commitments and proofs, but requiring a trusted setup) and Bulletproofs (transparent setup but larger proofs). In a transparent dictionary, the value of a PCS lies in encoding the entire table as a single polynomial and giving constant-size proofs for single-position queries, avoiding Merkle paths that accumulate with updates.

The ghost key attack refers to a malicious server temporarily replacing a user's public key with an attacker's public key, inducing others to encrypt messages to it, and then restoring the original public key before the next epoch so that consistency checks "look as if nothing ever changed." The randomized consistency mechanism defends against such attacks because the server must commit to updates first and only then receive the random challenge, so it cannot predict the challenge value to construct changes and reversals that cancel each other out; any temporary replacement leaves a trace in the randomly weighted difference vector, which clients detect when comparing endpoints.

Aegon's Three Modifications: From Usable to Deployable

IronDict's auditing is indeed efficient, but the server side has four bottlenecks: retaining a full snapshot every epoch (about 500GB per epoch for a billion-entry dictionary, with epochs lasting only 30 seconds); no horizontal scaling (a billion keys require about 2TB of RAM plus a 256GB SRS); a global sumcheck making proof generation linear in dictionary size, with epoch latency of about 15 minutes; and the aforementioned storage and setup issues.

Aegon makes three targeted changes:

First, replacing the global index check with label-level consistency checks. In open addressing, the resolution path of a label consists of several "prefix positions" and a final "allocation position." Aegon also applies the randomized mechanism to the index mapping, and the client verifies that all positions along the resolution path remain unchanged over the entire interval—prefix positions keep their original values, and the allocation position keeps returning that label. The server's computation therefore scales linearly only with the number of updates, no longer growing with dictionary size.

Second, dictionary sharding. A coordinator uses a verifiable random function (VRF) to deterministically route labels to independently running Aegon instances. A query only needs to involve the target shard, and the coordinator cannot forge VRF proofs to redirect it. Hafezi noted that this sharding architecture also applies to WhatsApp's AKD scheme.

Third, compact historical proofs replacing full snapshots. Each epoch stores only a small number of openings related to that update, so storage is proportional to the number of updates rather than dictionary size.

A verifiable random function (VRF) is a pseudorandom function with proofs: a coordinator holding a private key computes for an input x an output y = VRF_sk(x) and a proof π, and anyone with the public key can verify that y is indeed generated from x by this function and cannot be predicted or manipulated. In a sharded architecture, the coordinator uses a VRF to map labels to shard numbers, and clients can independently verify routing correctness, preventing a malicious coordinator from redirecting a label's query to a controlled shard and returning a forged public key. The determinism of the VRF also guarantees that the same label always falls into the same shard, maintaining query consistency.

Performance Comparison: Audit Proofs Drop from 80MB to 45KB

Aegon has an optimized codebase and was compared under the same settings as WhatsApp's key transparency (30-second epochs, 1250 updates per second). Results show that Aegon is better in query proof size, verification overhead, and server query latency, partly thanks to the sharded architecture. More importantly, the audit proof: Aegon's 45KB proof covers the entire key transparency history, can be verified in under a second, and clients can check weekly or monthly without being online every epoch. By contrast, WhatsApp's audit proof is about 80MB per epoch.

Aegon's construction is generic with respect to the polynomial commitment scheme; the concrete instantiation uses KZG, which is efficient but requires a powers of tau trusted setup and is only pre-quantum secure. The team is working on a post-quantum version, exploring two directions in parallel: replacing it with a post-quantum commitment scheme, and supporting identifier reuse—the current index dictionary saturates as usernames change frequently, so they plan to introduce a reclamation mechanism and formalize the "lifetime" concept proposed by Optics, using "authentication age" to let users judge how old or new a label they are contacting is. Hafezi also revealed that standardization discussions are being submitted to the IETF.

Privacy and Deployment Status

During the Q&A, Hafezi said Aegon's privacy is superior to the Seamless family of schemes, with privacy defined in a zero-knowledge sense that leaks no additional information. But he also acknowledged that without access control, metadata privacy is of limited practical significance—anyone who knows a phone number can query the public key. As for deployment, he only revealed that the WhatsApp team is internally "trying out Aegon"; whether it will go live is unknown.

From IronDict to Aegon, the value of this algebraic route lies in redrawing the boundary between trust and computation: auditing is no longer an expensive operation requiring dedicated infrastructure, but a self-audit that every client can perform independently. For communication platforms that handle billions of key queries every day, this may be a key step for key transparency to move from "deployable" to "sustainable."

One-line Summary

Aegon uses polynomial commitments to build a self-auditable key transparency system, reducing audit proofs from 80MB to 45KB.

Paragraph Summary

A team at the University of Cambridge proposes Aegon, a self-auditable key transparency system based on polynomial commitments, aimed at solving the excessive auditing costs in existing deployments of Signal, WhatsApp, and iMessage. Aegon inherits IronDict's algebraic route and, through three modifications—label-level consistency checks, VRF sharding, and compact historical proofs—makes server computation scale linearly only with the number of updates, cutting epoch latency from 15 minutes to under 30 seconds. Its audit proof is only 45KB and covers the entire history, verifiable by clients themselves, whereas WhatsApp needs about 80MB per epoch. The current KZG-based version requires a trusted setup and is only pre-quantum secure; the team is advancing a post-quantum version and an identifier reuse mechanism. WhatsApp is internally trying out Aegon.