Accumulator-Indexed Broadcast Encryption (AIBE): O(1) Broadcast Encryption for Dynamic Groups via Bilinear Accumulators

Encrypted group broadcasting has to satisfy five demands at once: only members can read a message, the relaying server learns nothing even with full database access, the author encrypts once rather than per-member, the scheme scales to millions, and revocation takes effect instantly without the author having to re-contact every remaining member.

No prior design hits all five. Per-member (pairwise) encryption is O(N) to send and produces O(N) headers. Group-key rotation gives O(1) sends but O(N) joins and revokes. MLS/TreeKEM improves those to O(log N). Boneh-Gentry-Waters (2005) achieves O(1) ciphertext but is a static system with no dynamic revocation. AIBE is the first to be O(1) across send, join, revoke, and header size together.

AIBE encodes the entire member set S into a single bilinear accumulator Acc(S) = g_1^(prod over s in S of (alpha + s)), a 48-byte point on BLS12-381 regardless of whether the group has 4 or 4 million members. The master secret alpha stays with the author; the accumulator itself stays private on the author's device, and only the verification target tau = e(Acc(S), g_2) in the target group is published. Each member i holds a witness w_i, which is the accumulator with member i's own factor removed.

To post a message, the author draws a random 256-bit post key K_p and a fresh blinding factor r, then publishes a three-element header (H_1 = g_2^r, H_1' = g_2^(alpha r), H_2 = K_p XOR mask), where the mask is derived by hashing the pairing value tau^r; the content is sealed with an AEAD under K_p. A member combines the header into g_2^(r(alpha+i)) and pairs it against their own witness. By bilinearity the (alpha+i) factors cancel, so every member independently recovers the identical pairing value e(Acc(S), g_2)^r and hence the same K_p - which is why one constant-size header decrypts for everyone.

The headline result is that every hot-path operation is O(1). The header is exactly three header values (two G₂ points plus a 32-byte masked key) - 224 bytes - independent of group size, and encrypt and decrypt each perform a fixed amount of work. Server blindness follows from keeping Acc(S) in G_1 private and publishing only tau in the target group G_T: target-group elements cannot be fed back into a pairing, so the server, holding only tau and g_2^r, cannot reconstruct tau^r without solving a discrete log.

Revocation is where the accumulator structure pays off. When member j leaves, any remaining member i updates their own witness with the purely local computation w_i' = (w_i - w_j)/(j - i), scalar-multiplying by the inverse of (j - i). The author publishes only a revocation notice - j's ID, j's old witness encrypted under AIBE itself so the server never sees the raw G_1 value, and the new target tau' - and remaining members self-update without any direct message. The revoked witness provably fails against the new target. As a bonus, because each witness is unique it acts as an implicit fingerprint, giving inherent traitor tracing.

Security rests on the q-Strong Diffie-Hellman assumption, and the paper derives concrete bounds on BLS12-381 (128-bit security level, scalar field order above 2^254). Accumulator forgery reduces via Schwartz-Zippel to at most |S|/r, below 2^-224 for groups up to a billion. Adaptive IND-CPA is proven through dual system encryption, yielding roughly 96-bit CCA2 security at 2^30 members (the IND-CPA bound is 97-bit).

Every core property is formalized in Lean 4 with Mathlib across 13 files and 100+ theorems, with zero sorry and zero custom axiom declarations. The proofs cover pairing bilinearity, witness correctness, uniform decryption (all members recover the same key), invalid-witness rejection, the cleared-denominator self-update identity, revocation forward secrecy, collusion structure, and a nine-property litmus test. Concrete bounds are checked by native_decide in a BLS12381 module that bridges the abstract algebra to the real field parameters.

AIBE is implemented in three languages sharing the same algebra/accumulator/encryption/protocol layout: Rust (arkworks + chacha20poly1305, 28 tests), TypeScript (@noble/curves + AES-256-GCM via Web Crypto, 31 tests), and Swift (native BLS12-381 pairing + ChaChaPoly, 28 tests targeting iOS, macOS, and server-side Swift).

Benchmarks confirm flat scaling from 4 to 100,000 members: encrypt stays in the 1,914-2,076 microsecond band, decrypt around 1 millisecond (997-1,436 microseconds), header size a constant 224 bytes, witness self-update near 100 microseconds, and revocation roughly 210 microseconds for groups of 100 or more, rising to 307 microseconds at N=4. The five-user litmus test (Alice authoring; Bob, Charlie, Diana, Eve as members; Frank a non-member) passes all nine checks, including revoking Eve, the three remaining members self-updating without Alice, and the server being unable to decrypt.

The main caveat is that batch witness issuance is O(N), but this is a one-time setup cost off the per-message critical path - in the incremental-growth model each new member is a single O(1) addition. Other limitations: BLS12-381 pairings are not post-quantum, and like any end-to-end scheme AIBE cannot stop a member from re-sharing decrypted plaintext, which traitor tracing only deters.