Aegon: Self-Auditable Key Transparency at Global Scale

The talk opens with the basic motivation for key transparency in end-to-end encrypted messaging. If Cersei wants to message Jaime, she must trust that the server returns Jaime’s real public key. A malicious server could substitute an attacker’s key, and encryption would still work perfectly, just with the wrong recipient. Manual verification of safety numbers does not scale, so key transparency automates these checks by having the server commit to its directory in each epoch on a public bulletin board, along with proofs of transitions between epochs.

Consistency proofs and why endpoints are not enough

A key transparency scheme needs two core operations: lookup (fetching another user’s key) and proof of consistency, which shows that a client’s own key did not change over an interval of epochs. Endpoint checks are insufficient, because a server could swap a key while a client is offline and restore it before the client returns. The client therefore needs assurance over every intervening epoch.

The speaker organizes prior work into three families. CONIKS has clients check every epoch individually, which becomes costly for clients who are offline for long periods. Seamless, Parakeet, and Optics use version numbers that must increment whenever a key changes, so clients only compare endpoints, but a separate auditor must verify each epoch’s transition, and that work is performed globally. Iron Dict and Aegon use randomized versioning, described below.

The self-auditability problem

In seamless-style systems, the audit proof grows with the number of updates per epoch. For WhatsApp key transparency, an auditor must download and hash roughly 80 MB per minute, which is why deployments rely on external auditors such as Cloudflare for WhatsApp and Cloud and Trail of Bits for Signal. General-purpose SNARKs over standard hash functions have been explored as a compression path, but the cost of hashing inside circuits limits their scalability.

The speaker also argues that the roles of bulletin board and auditor are logically distinct. A bulletin board needs availability and consistency of published roots, which is cheap and could be distributed widely, whereas auditing is computational and can be performed independently by anyone who has the same publication history. The model should keep these roles separate.

Iron Dict foundations

Iron Dict, the precursor, builds a transparent dictionary from multilinear polynomials and polynomial commitment schemes (PCS). A table of field elements indexed by boolean vectors defines a unique multilinear polynomial, so the dictionary can be committed to and opened at points. Arbitrary string labels and values are mapped through collision-resistant hashing, and labels are assigned to positions via open addressing with roughly 4x overprovisioning. Lookups therefore have two stages: resolve the label to an index, then open the value at that index. The index map must give each label a stable, unique position, while the value map may change over time but must support proofs that a value has been constant across an interval.

Consistency uses a randomized linear combination. Between epochs, the difference vector of the dictionary is multiplied by a fresh random challenge and accumulated into a randomized vector. A malicious change followed by its reversal would sum to zero, which is the ghost-key attack, but with random weights the two updates almost certainly do not cancel. The server must commit to updates before the challenge is revealed, so it cannot tailor them. The auditor only checks the recurrence on homomorphic commitments using a constant number of operations, rather than scanning entries.

Iron Dict, however, has four practical bottlenecks. First, it stores a full snapshot of the dictionary every epoch, roughly 500 GB per epoch at large scale, with epochs as short as 30 seconds. Second, it does not distribute the dictionary across machines, so a billion-key deployment needs around 2 TB of RAM, and a 4-billion-entry deployment would need about 8 TB. Third, it uses a global sum check over the index map, which costs work linear in the dictionary size even when few entries change. Fourth, the resulting epoch latency is about 15 minutes for a billion entries, incompatible with the 30-second latency that WhatsApp requires.

An audience member asked whether a larger hash output could replace the boolean-domain mapping. The speaker explained that the PCS setup for KZH is linear in the hypercube size, so the domain must stay modest, and sparse polynomial commitments exist but are inefficient for this setting.

What Aegon changes

Aegon keeps Iron Dict’s algebraic structure but makes three changes: it replaces the global index check with label-specific consistency checks, it partitions the dictionary into independently operating instances, and it retains compact historical proofs instead of full snapshots.

The key idea is applying the randomized consistency mechanism to the index map as well as the value map. A client who registered a label after probing occupied positions needs assurance that the earlier positions in the probing sequence still hold the same values, and that the final position still holds the label’s tag. These are checked with endpoint openings in the randomized index map, so the server’s work becomes linear in the number of updates rather than the dictionary size.

During a Q&A, the speaker clarified an important asymmetry. A lookup requires only the current opening of the label’s probing path, with no history. The owner of a key, however, must monitor the entire probing path across time to ensure that their index has not been tampered with. If the server cheats, the owner is the one who detects it.

For scaling, a coordinator uses a verifiable random function (VRF) to assign each label deterministically to one of many dictionary instances. Each instance runs Aegon independently, which provides horizontal scalability and reduces per-instance memory and setup size. The speaker notes this sharding architecture could also be applied to AKD and WhatsApp’s deployment. The coordinator cannot silently redirect labels because VRF proofs bind the routing decision.

An audience member raised the question of how commitments from all shards are published. Each instance commitment is a single group element, so publishing them is cheap, and they could be committed under a Merkle tree. The speaker explained a distinction: a lookup only needs a Merkle path to the relevant shard, but auditing needs all shard commitments because the audit runs over the entire system inside a zero-knowledge SNARK circuit. Another participant suggested that auditors could audit only their own shard, which the speaker considered worth exploring.

For storage, Aegon no longer keeps a full snapshot each epoch. For each update, it stores only the openings needed for later lookup and consistency proofs of that specific update. Storage therefore scales with the number of updates rather than with the dictionary size. Unlike seamless’s append-only history, operators can decide which parts of history to discard.

Results

The implementation is production-grade Rust, and the comparison with WhatsApp key transparency (AKD) uses the same 30-second epoch latency and the same throughput of 1,250 updates per second. Aegon’s lookup proof size, verification time, and server lookup latency compare favorably, largely due to partitioning, and the speaker suggested that applying the same architecture to AKD would improve its numbers too. The headline result is the audit proof: about 45 KB (the abstract reports under 30 KB) that verifies in about a second, covering the entire history rather than a single epoch. Audits can therefore run weekly or monthly instead of every epoch. By contrast, WhatsApp’s per-epoch audit proof is roughly 80 MB. Epoch latency is under 30 seconds, compared with 15 minutes for Iron Dict.

The construction is generic over any PCS, but the concrete instantiation uses KZH, which needs a trusted setup (powers-of-tau ceremony) and is not post-quantum. The speaker is working on a post-quantum version and on reusable identifiers. Usernames can saturate the index dictionary when people change them frequently, so the team wants a recycling mechanism and a notion of authenticated label age, inspired by Optics. An audience member pointed out that the same problem exists for key rotation and usernames being reclaimed, since Signal allows usernames to be taken after seven days, and that a label’s age could itself be a useful trust signal, though it raises privacy concerns about revealing when someone registered.

On privacy, the speaker argued that Aegon is zero-knowledge in its guarantees and therefore stronger than seamless and Parakeet. An audience member countered that without access control, anyone holding a phone number can fetch the corresponding public key, so practical privacy requires access control layered on top. The speaker agreed that access control matters in deployment and noted that the zero-knowledge properties hold independently of it. The zero-knowledge version carries only a small overhead relative to the non-ZK version, which was already efficient.

The speaker mentioned that the work will be published soon, that the team is contributing to IETF standardization discussions about key transparency, and that WhatsApp engineers are reportedly experimenting with Aegon, though deployment is not confirmed.

• Tags:
• Feature
• Zero-Knowledge Proofs
• Post-Quantum Cryptography
• Key Transparency
• End-to-End Encryption
• Polynomial Commitments
• Multilinear Polynomials
• Authenticated Dictionaries
• Randomized Consistency
• Sharding
• KZG Commitments
• WhatsApp
• Iron Dict
• Aegon