Solving the O(N) Envelope Bottleneck in Group Chats: Forward Secrecy & Dynamic Key Rotation

Chapter 1: The Honeymoon Phase & The Meltdown

Building 1-on-1 encrypted chat was deceivingly smooth. User A computes a shared secret with User B, encrypts the message with AES-256-GCM, and sends it off. Everything felt instant, sleek, and battery-friendly.

Then came our first 50-person group test.

Someone posted a 15MB recorded demo video into the chat room. Within seconds, the test device froze, the Flutter UI isolate stuttered, and the phone's temperature spiked. Looking at our network profiler revealed a horrific reality:

The mobile client was attempting to upload 750 MB of duplicate ciphertext payloads over a flaky cellular connection.

Chapter 2: The Math of the Bottleneck — $O(N)$ Pairwise Dilemma

In our naive early architecture, sending a message to a group of $N$ members forced the sender's phone to iterate through every single participant:

1. Perform $N - 1$ distinct symmetric encryption operations.
2. Derive $N - 1$ individual X25519 Diffie-Hellman envelope secrets.
3. Transmit an array containing $N - 1$ full ciphertexts to the backend.

For text messages, a few extra kilobytes went unnoticed. But for high-resolution images and videos, $O(N)$ multiplication was suicidal for mobile devices.

To make matters worse, history was permanently fractured: if a new classmate joined the group next week, they could never read historical messages because those ciphertexts were never sealed with the newcomer's public key.

We needed an architectural breakthrough.

Chapter 3: The Breakthrough — One Key to Rule the Group

The epiphany was realizing that the payload and the access control do not need to be coupled together.

Instead of encrypting a large video $N$ times, what if we encrypted the video exactly once using a single ephemeral symmetric key, and only distributed that tiny 32-byte key to the group members?

Enter the Shared Group Chat (GC) Key Architecture:

[Group Creation Event]
       │
       ▼
Admin generates random GC Key (32 bytes)
       │
       ▼
Encrypts GC Key once for Member 1 (X25519)
Encrypts GC Key once for Member 2 (X25519)
Encrypts GC Key once for Member N (X25519)
       │
       ▼
Saves groupKeyMap on Server: { userId -> encryptedGcKey }

How Sending Works Now:

1. Alice fetches the group's current 32-byte GC_Key from secure local storage.
2. Alice encrypts the 15MB video exactly once via AES-256-GCM.
3. Alice transmits a single ciphertext payload to POST /conversation/group/{id}/message.
4. The backend broadcasts this single payload across the STOMP WebSocket topic /topic/group.{id}.

Bandwidth dropped from 750 MB down to 15 MB. The isolate remained butter-smooth, and device thermals barely budged.

Chapter 4: The Eviction Drama & Forward Secrecy

The architecture felt complete—until we asked ourselves an uncomfortable security question:

*"What happens when an admin kicks a member out of the group?"*

If the group continues using the same shared GC_Key, the evicted user could still listen on the WebSocket topic or inspect encrypted backups and continue reading every single future message! This completely violates Forward Secrecy.

To solve this, we designed an automated Dynamic Key Rotation Protocol:

Admin removes Member X
       │
       ▼
Admin generates brand new GC_Key_v2
       │
       ▼
Re-encrypts GC_Key_v2 for remaining members ONLY
       │
       ▼
Publishes keyVersion: 2 to server
(Member X is permanently locked out)

1. Trigger: An Admin removes Member X (DELETE /conversation/group/{id}/members/{x}).
2. Key Generation: The Admin's device immediately generates a brand new 256-bit key: GC_Key_v2.
3. Re-encryption: The Admin encrypts GC_Key_v2 for all remaining legitimate members using their X25519 public keys.
4. Key Rotation Publish: The Admin submits the new groupKeyMap alongside a version increment (keyVersion: 2).
5. Revocation: Because Member X was excluded from the re-encryption step, Member X never receives GC_Key_v2 and is cryptographically locked out of all future messages.

Chapter 5: Taming the Real World — Out-of-Order Packets

In distributed mobile networks, WebSocket packets arrive out of order all the time. If Alice sends a message with keyVersion: 1 right before Member X is removed, but Bob receives the rotation announcement (keyVersion: 2) first, Bob's client must not fail or drop messages.

We implemented a local Key Ring cache on the mobile client:

class GroupKeyStore {
  // Store historical key versions indexed by groupId and version number
  final Map<String, Map<int, SecretKey>> _groupKeyRing = {};

  Future<SecretKey> getKeyForMessage({
    required String groupId,
    required int version,
  }) async {
    final ring = _groupKeyRing[groupId];
    if (ring != null && ring.containsKey(version)) {
      return ring[version]!;
    }
    // Fallback: Fetch specific historic encrypted envelope from server
    return await _fetchAndDecryptHistoricalKey(groupId, version);
  }
}

This guarantees seamless message decoding during transitions while strictly locking out unauthorized members.

Epilogue: The Core Takeaways

1. Never multiply heavy payloads on mobile: Asymmetric encryption is for key negotiation; symmetric encryption is for data. Keep payload transfer at $\mathcal{O}(1)$.
2. Forward secrecy requires active protocol design: Shared keys require dynamic rotation upon group membership mutations.
3. Hardware-friendly cryptography matters: By respecting mobile memory isolates and radio bandwidth, security doesn't have to come at the expense of a delightful user experience.