Key Revocation & Recovery

The Problem This Page Solves

In a centralized social app, losing your phone is annoying but recoverable: you re-register with your phone number, the server recognizes you, and your contacts see a "security number changed" notice. The server is the root of trust.

In this app, you are your private key. There is no phone number, no server, no central authority. If your private key is gone or compromised, there is no fallback by default. This page analyzes the problem space and proposes a concrete, implementable strategy.

1. The Problem

What Changes When There Is No Server

In WhatsApp or Signal, the following happen automatically on device loss:

1. User re-installs app, re-registers phone number
2. Server authenticates via SMS
3. Server stores new public key
4. Contacts receive new key (Identity Key Change notification)
5. Old session state is invalidated server-side

Every one of those steps depends on a server. Remove the server and the entire mechanism collapses.

The Three Distinct Scenarios

Each scenario has different urgency and different cryptographic requirements. Loss/theft requires fast propagation of a revocation notice. Destruction requires establishing a new key with proof that it belongs to the same person. Voluntary rotation requires no emergency handling but still requires coordination with all contacts.

Why This Is Harder in an Offline-First Network

In an internet-connected decentralized system (e.g., blockchain, federated server), a revocation certificate can be broadcast globally in seconds. In our system:

• There is no broadcast channel
• There is no always-on relay (online mode is opt-in)
• Contacts may only be reachable via physical proximity
• Some contacts may live in other cities or countries
• A revocation certificate can only travel as fast as human movement

This is not a bug to be patched — it is a fundamental property of an offline-first, proximity-based network. Any design must accept this constraint and provide the best possible guarantees within it.

2. Revocation in Decentralized Systems — Prior Art

PGP / GPG Web of Trust

PGP's revocation model is the oldest in widespread use.

Revocation certificates: When a keypair is created, the user is encouraged to immediately generate a revocation certificate — a signed statement (sig type 0x20) declaring the key invalid. This certificate can later be published to key servers.

Key servers: Public key infrastructure built on SKS or modern Hockeypuck servers. Anyone can publish a revocation certificate to a key server, and it propagates across the server network. A verifier fetching the key sees the revocation.

Limitations for offline scenarios:

• Requires internet access to both publish and check revocation status
• Key servers have no authentication — anyone can submit garbage data (the SKS "certificate flooding" attack of 2019 poisoned many keys)
• WKD (Web Key Directory) is server-hosted per domain — not applicable to pseudonymous keys
• In a fully offline network, PGP's revocation model provides zero guarantees: there is no server to query

Lesson: The revocation certificate format (a signed self-assertion) is a valid primitive to adopt. The distribution mechanism (key servers) is completely inapplicable.

Signal

Signal uses the phone number as the recovery anchor. The server stores a registrationId and the current IdentityKey. When a new device registers:

1. Server validates phone number via SMS
2. Server stores new IdentityKey
3. When a contact next sends a message, the session negotiation reveals the key change
4. The app shows "Safety number changed" warning

On device loss: The user re-registers. The server automatically invalidates all sessions associated with the old registration. The attacker who has the old device loses the ability to receive new messages once the server registers the new key.

Limitations for our system: Signal's entire recovery model is the phone number + server combination. Neither is available. Signal explicitly acknowledges this: without the server as trust anchor, the "safety number" mechanism would be purely advisory.

Briar

Briar's documentation is honest: there is no key recovery mechanism. From their documentation and threat model analysis:

• A Briar identity is a single Ed25519 keypair
• If the device is lost or destroyed, the identity is lost
• There is no backup, no recovery, no migration path
• The recommendation is to treat a Briar identity as a throwaway — if lost, create a new one and tell contacts manually

This is the correct honest baseline. It is unusable for a social app where identity continuity matters.

Secure Scuttlebutt (SSB)

SSB's identity model creates a specific, well-documented problem known as the fork problem.

Each SSB identity is a keypair, and each user has an append-only, signed feed. The feed is a hash chain: each message references the hash of the previous one. To create a new identity after losing a device, you generate a new keypair and publish to a new feed.

The fork attack / reset problem: A malicious device holder (or an attacker who stole the phone) can continue publishing to the old feed. The network has no mechanism to distinguish "Alice on her new phone" from "attacker pretending to be Alice." Since SSB feeds are public and gossiped freely, both the legitimate new feed and the attacker-controlled old feed will propagate.

There is an SSB proposal (ssb-revocation) in draft status that would allow a new key to publish a signed statement linking back to the old key, but it requires:

• The user to have pre-registered the new key as a successor (not useful after unexpected device loss)
• Or some threshold of mutual contacts to co-sign the transition (the social recovery direction)

SSB's fork problem is instructive: a solution must cryptographically bind old and new keys in a way that is verifiable by contacts who never meet the user again.

MLS (RFC 9420)

MLS handles key rotation and member changes natively through its proposal-and-commit mechanism.

Update proposals: A member can propose a KeyUpdate — replacing their leaf key in the ratchet tree with a fresh key. Once the commit is applied, all group members derive new secrets that do not incorporate the old key material.

Remove + Add: If a member's key is believed compromised, any other group member can propose Remove(compromised_member). Once committed, the compromised member is excluded. The user can then be re-added with a new key via an Add proposal, which requires authentication (in our system, an in-person NFC exchange with a group member).

Forward secrecy restoration: MLS's post-compromise security guarantee means that once the compromised member is removed and a new epoch is committed, the attacker who held the old key can no longer decrypt new group messages. They can still decrypt all messages sent before their removal — this is unavoidable without key material from before the compromise.

Applicability: MLS's group-level mechanisms are directly usable. The harder problem is individual identity continuity across all contacts, not just within a specific group.

Smart Contract Social Recovery (Argent Wallet, EIP-4337)

Account abstraction wallets like Argent implement social recovery as a first-class feature. The pattern:

1. At setup, user designates guardians — other wallets (friends, a hardware device, a cloud service) that can authorize recovery
2. If the wallet is lost, a threshold of guardians (e.g., 3-of-5) sign a recovery transaction
3. The smart contract replaces the controlling key with a new one

This is implemented via a time-locked recovery process: guardians initiate recovery, a 48-hour window allows the legitimate owner to cancel if the recovery is fraudulent, then the new key takes effect.

EIP-4337 abstraction: Any signing scheme can be used, enabling multi-factor and social recovery as part of the account's validation logic.

Adapting to P2P: The smart contract becomes a distributed agreement among trusted contacts. The "contract" is a protocol run between devices rather than code deployed on a blockchain. The time-lock can be implemented by having guardians withhold share broadcasts for N hours, allowing cancellation by the legitimate user if reachable. The core insight — a threshold of trusted contacts can authorize a key transition without any central authority — transfers directly.

FIDO2 / Passkeys

FIDO2 credentials are device-bound by design, but the passkey extension (CTAP 2.1+) allows multi-device credentials. Apple and Google implement passkey sync via their respective cloud key vaults (iCloud Keychain, Google Password Manager):

1. Private key material is sealed with a hardware-backed key
2. The sealed blob is synced across the user's devices via end-to-end encrypted cloud sync
3. On a new device, the cloud service delivers the sealed blob, the hardware unseals it

Lessons for mobile key management:

• Cloud-backed key sync requires trusting the platform vendor's E2E encryption implementation
• The sync model works well for passkeys because the relying party (website) validates the public key, and any device in the sync group can produce valid signatures
• For our use case, the public key presented to contacts would need to change if we naively replicated this model — unless we wrap it: the contacts bind to a long-term public key that signs rotation certificates, and the actual signing key rotates via cloud sync

3. Revocation Propagation in Offline Networks

This is the hardest problem in the design. The cryptography of generating a revocation certificate is straightforward; ensuring it reaches all affected contacts in a network with no persistent connectivity is not.

The Gossip Problem

In an online network, gossip protocols converge quickly: a message sent to a few nodes spreads to all nodes in O(log n) rounds. But this assumes nodes are always reachable. In our system:

• Nodes are only reachable when physically proximate (~30m BLE range)
• A user's contacts may span multiple cities, countries
• Some contacts may not encounter anyone in the user's social graph for weeks or months
• A revocation certificate must still eventually reach them

This is the delayed gossip problem — equivalent to epidemic routing in delay-tolerant networking (DTN). The solution is store-carry-forward: nodes carry revocation notices on behalf of others and forward them when they encounter relevant nodes.

Revocation via Physical Encounter

The simplest case: Alice loses her phone, gets a new one, generates a new keypair. She meets Bob in person. They perform a fresh NFC exchange. Bob's device now has Alice's new public key.

But what about Carol?

Carol lives in another city. Alice and Carol met 8 months ago at a conference. They have not met since. Carol has no mechanism to learn about Alice's new key unless:

1. Alice and Carol meet in person again (potentially never)
2. Someone who knows both Alice and Carol acts as an intermediary
3. Alice and Carol both use online mode (Tor), in which case Alice can send a key-rotation message directly

In offline-only mode, the honest answer is: Carol will not know until she encounters someone who has Alice's new key. This is an inherent limitation. The design goal is to minimize propagation time without requiring internet access.

Store-Carry-Forward Revocation

When Bob receives Alice's revocation notice (either directly from Alice or via gossip), he stores it and forwards it to any contact who has Alice's old key in their contact list — the next time he encounters them.

Alice (new phone)  →  Bob  →  Dave (carries notice)  →  Carol
                                                      →  Eve

Implementation:

• A revocation notice is a signed message: { old_key_id, new_key, timestamp, signature_by_old_key? }
• If the old key is still accessible (voluntary rotation or migration with both phones present), the notice is signed by the old key for maximum verifiability
• If the old key is gone (device destroyed), the notice is signed by the new key plus a threshold of guardian attestations (see Section 5)
• Devices that receive a revocation notice store it in a small "revocation cache" and include it in BLE sync payloads to contacts who hold the affected old key

Privacy consideration: Carrying a revocation notice for Alice reveals to a third party that you know Alice. The notice should only be forwarded to contacts who demonstrably already know Alice (i.e., have her public key in their contact list). Bob checks Carol's contact list hash before forwarding — but this itself reveals information. A privacy-preserving alternative: include revocation notices in all sync payloads as a small bloom filter, allowing recipients to check locally without revealing who is being revoked.

Time-Bounded Key Expiry

An alternative approach borrowed from SSL/TLS certificate practice: every identity key has an expiry timestamp, e.g., valid_until: 2027-04-03. After expiry, the key is treated as invalid by all clients, forcing key rotation.

Advantages:

• No explicit revocation message needed for planned rotation
• Contacts with no connectivity eventually refuse to accept messages signed by an expired key
• Forces periodic re-verification of contacts (like re-meeting someone to update their certificate)

Disadvantages:

• Disruptive for users who have not planned a rotation: if Alice's key expires while she's off-grid, she temporarily cannot communicate with anyone
• Short expiry windows (< 1 year) reduce the window of attacker opportunity but increase operational friction
• Does not help with emergency revocation: if Alice's phone is stolen today and her key expires in 11 months, that is 11 months of possible impersonation

Recommendation: Use expiry as a soft backstop (2-year validity) rather than the primary revocation mechanism. Emergency revocation must be faster.

Trusted Revocation Delegates

A user pre-designates a small set of revocation delegates — typically 3–5 close contacts. Each delegate holds:

1. A copy of the user's revocation certificate (signed by the user's key, with the new_key field left blank, to be filled at revocation time) — a pre-signed partial revocation
2. Authorization to attest that a new key belongs to the user

How it works cryptographically:

At setup time, Alice generates a revocation token:

revocation_token = Sign(alice_private_key, {
  action: "delegate_revocation",
  delegate: bob_public_key,
  issued_at: timestamp,
  expires: timestamp + 2_years
})

Alice gives this token to Bob. Bob stores it locally.

When Alice needs to revoke (with or without her old key):

1. Alice contacts Bob in person (NFC tap on new device)
2. Alice presents her new public key
3. Bob verifies Alice's presence (physical meeting = sufficient in the physical-first trust model)
4. Bob signs an attestation: { alice_new_key, alice_old_key_id, timestamp, bob_signature, alice_revocation_token }
5. This attestation is stored on both devices and gossiped forward

When Carol encounters Bob or anyone carrying the attestation:

• Carol checks: do I trust Bob as a revocation delegate for Alice? (Carol may not know this unless pre-arranged)
• If yes: Carol updates Alice's key
• If no: Carol has a "key changed" warning, requiring manual verification

The trust graph problem: For delegate attestations to be useful, contacts must know who Alice designated as delegates. This information can be published in Alice's profile (signed by her key), making it available to all contacts before a revocation is needed.

Graph Reachability Problem

Even with store-carry-forward and delegates, some contacts may never receive a revocation notice in a sparse social graph.

Consider a scenario where Alice has 50 contacts. 30 of them live in the same city and encounter each other frequently. 20 are scattered across 10 countries. The revocation will reach the local cluster quickly (days). The remote contacts may take months or never receive it, depending on whether anyone who knows both groups travels between them.

Mitigation in online mode: If Alice's new device has internet access (opt-in Tor relay), she can push the revocation notice to her Tor hidden service inbox for each contact. Contacts who check their inboxes will receive it without physical meeting.

Honest assessment: For fully offline users in sparse networks, there is no guaranteed delivery time for revocations. This is a fundamental constraint, not a solvable implementation problem.

4. Device Backup Strategies

Encrypted Cloud Backup

The user's private key is encrypted with a strong symmetric key derived from a password, and the resulting ciphertext is stored in iCloud Keychain, Google Drive, or similar.

encrypted_key = AES-256-GCM(
  key = PBKDF2(user_password, salt, 600000_iterations),
  plaintext = ed25519_private_key
)
store(encrypted_key) → iCloud/Google Drive

When to use: Appropriate as a secondary backup tier for users who trust their platform vendor's E2E implementation (Apple's iCloud Keychain uses HSM-backed keys; Google's Titan chip backs Android Keystore). Not appropriate as the sole backup mechanism.

Mnemonic Seed Phrase (BIP39-Style)

A 12 or 24-word human-readable phrase is derived from the private key entropy using the BIP39 wordlist (2048 words). The user writes it on paper and stores it somewhere secure.

entropy (256 bits) → BIP39 → 24 words
e.g.: "abandon ability able about above absent absorb abstract..."

Recovery:
24 words → BIP39 → entropy → Ed25519 keypair

The BIP39 checksum catches transcription errors (last word encodes a checksum of the preceding entropy).

Enhancement: Steel plate engraving (physical tamper resistance), or storing the phrase in a sealed envelope with a trusted person, increases durability. The mnemonic itself is the only artifact — no devices, servers, or protocols required for recovery.

When to use: Required as the baseline minimum. Every user must generate a seed phrase at onboarding. It is the last-resort recovery mechanism when all others fail.

Shamir's Secret Sharing (SSS)

The private key (a 256-bit secret S) is split into N shares such that any K shares can reconstruct S, but K-1 shares reveal nothing about S. This is Shamir's Secret Sharing scheme, based on polynomial interpolation over a finite field.

Brief mathematical description:

Choose a prime p > S and a random polynomial f(x) of degree K-1 over GF(p) where f(0) = S:

f(x) = S + a₁x + a₂x² + ... + a(K-1)x^(K-1)  (mod p)

Shares are (i, f(i)) for i = 1..N. Given any K pairs, the unique polynomial can be reconstructed via Lagrange interpolation, revealing f(0) = S. Given K-1 pairs, S is information-theoretically hidden.

Example: 2-of-3 split. Alice generates 3 shares. She gives share 1 to Bob, share 2 to Carol, keeps share 3 on paper.

Alice's private key  →  SSS(K=2, N=3)
                         ├── Share 1  →  Bob's device (encrypted to Bob's key)
                         ├── Share 2  →  Carol's device (encrypted to Carol's key)
                         └── Share 3  →  Paper/offline storage

Recovery: Alice meets Bob → presents new device →
          Bob decrypts Share 1 from local storage →
          Alice recovers to get Share 1
          Alice meets Carol OR retrieves paper share 3 →
          Reconstruct private key from Share 1 + Share 2 (or 1 + 3)

When to use: Tier 2 backup — recommended for users with multiple trusted contacts. 2-of-3 or 3-of-5 are practical splits.

Social Recovery with Threshold Signatures

An extension of SSS that avoids revealing the old key at all during recovery. Instead of reconstructing the private key, guardians collectively sign an attestation that a new key is the legitimate replacement.

Using threshold signatures (e.g., FROST — Flexible Round-Optimized Schnorr Threshold Signatures):

At setup, Alice and her 3 guardians run a distributed key generation (DKG) protocol that produces:

• A joint verification key vk (known to all contacts as Alice's "recovery authority")
• Secret shares of a signing key, held by each guardian

At recovery time:

• Alice presents her new public key to any 2-of-3 guardians (via BLE)
• The 2 guardians run a threshold signing protocol: they collectively produce a valid signature under vk over the message { new_key, timestamp } — without any single guardian knowing the full signing key
• All contacts who have vk can verify the recovery authorization

Using ZK proofs (more complex): A more advanced variant uses a zero-knowledge proof to prove "I hold K of N shares from the original key setup" without revealing those shares — enabling privacy-preserving recovery authorization.

When to use: Tier 3 — advanced recovery for users who want maximum security. Implementation complexity is high; prototype should start with plain SSS and upgrade.

Hardware Backup

The simplest practical approach: before wiping or replacing a device, the user NFC-taps the old phone to the new phone to transfer the encrypted key material directly.

Old Phone  →  NFC tap  →  New Phone
             (encrypted key export, one-time use token)

The key export should be:

• Encrypted in transit (ephemeral ECDH between old and new devices)
• Authenticated (new device signs a "receive" request with ephemeral keypair, old device verifies)
• One-time only (invalidated after successful transfer)

This is the highest-assurance backup for the planned migration case. It requires both devices to be functional simultaneously.

5. Recommended Design

Multi-Tier Backup Architecture

┌─────────────────────────────────────────────────────────┐
│  TIER 1 — Minimum (Required at onboarding)              │
│  12-word BIP39 seed phrase                              │
│  User writes it down; app blocks first use until done   │
│  Covers: total device loss, no trusted contacts          │
└─────────────────────────────────────────────────────────┘
          ↓ Recommended upgrade
┌─────────────────────────────────────────────────────────┐
│  TIER 2 — Social Recovery (Recommended)                  │
│  Shamir 2-of-3 split among 3 trusted contacts           │
│  Each contact holds encrypted share on their device     │
│  Covers: device loss with 2+ trusted contacts reachable  │
└─────────────────────────────────────────────────────────┘
          ↓ Advanced option
┌─────────────────────────────────────────────────────────┐
│  TIER 3 — Revocation Authority (Advanced)               │
│  Pre-signed revocation token given to Tier 2 guardians  │
│  Guardians can broadcast revocation + attest new key    │
│  Covers: compromise scenario; user may be unreachable   │
└─────────────────────────────────────────────────────────┘

Tier 1: Mnemonic Backup

• Generated at first app launch before any contacts are established
• 12 words (128 bits of entropy + 4-bit checksum) using BIP39 English wordlist
• App displays words one at a time, requires user to confirm 4 randomly chosen words
• App does NOT store the seed phrase — derives the key from it only at generation time
• Re-entry of the seed phrase on a new device regenerates the same Ed25519 keypair

Implementation note: The BIP39 derivation path should be pinned (e.g., m/44'/0'/0'/0/0 using BIP32 derivation) so that the same phrase always produces the same key regardless of app version.

Tier 2: Shamir Social Recovery (2-of-3)

Alice selects 3 trusted contacts from her existing contact list. For each guardian:

1. Alice's app generates a share using SSS(K=2, N=3) over her private key
2. Each share is encrypted to the guardian's Ed25519 public key: Encrypt(guardian_pubkey, share_bytes)
3. Alice delivers the encrypted share to each guardian via BLE (next time they are proximate)
4. Guardian's device stores: { alice_key_id, encrypted_share, alice_pubkey, expiry }
5. Alice's device records which contacts are her guardians

Recovery flow (detailed in Section 6):

1. Alice installs app on new device → new ephemeral keypair for recovery session
2. Alice meets Guardian 1 (Bob) in person → BLE recovery request
3. Bob's device decrypts the stored share, re-encrypts to Alice's new recovery session key, transmits
4. Alice meets Guardian 2 (Carol) → same process
5. Alice's app combines 2 shares → reconstructs private key → re-establishes identity
6. Alice publishes a key-rotation notice signed by the recovered key

Tier 3: Pre-authorized Revocation

Each Tier 2 guardian also stores a partial revocation token:

partial_revocation = Sign(alice_private_key, {
  action: "authorize_revocation",
  guardian: guardian_pubkey,
  issued_at: timestamp,
  expiry: timestamp + 730_days
})

If Alice is unreachable (stolen phone, attacker is using it) and 2-of-3 guardians agree:

1. Guardians sign a joint revocation notice: { old_key: alice_old_pubkey, reason: "guardian_threshold", guardian_sigs: [sig1, sig2], partial_revocation_tokens: [tok1, tok2], timestamp }
2. This notice is gossiped to all contacts who hold Alice's old key
3. Recipients see: "Alice's key was revoked by 2 of her designated guardians" — they quarantine or reject the old key

No new key is asserted in this case — guardians cannot know Alice's new key unless she meets them. The notice only revokes the old one, preventing attacker impersonation while Alice arranges an in-person recovery.

Migration Flow: New Device

Step 1: Install app on new device
        ↓ App asks: "Recover existing identity or create new?"
        ↓ User selects "Recover"

Step 2a (if seed phrase available):
        ↓ User enters 12 words
        ↓ App reconstructs Ed25519 keypair
        → Jump to Step 4

Step 2b (if Tier 2 guardians available):
        ↓ App generates ephemeral recovery keypair
        ↓ App shows "Meet 2 of your 3 recovery contacts"

Step 3: Physical recovery meetings
        ↓ User meets Guardian 1 → BLE recovery protocol (see Section 6)
        ↓ Receives Share 1, encrypted to ephemeral key
        ↓ User meets Guardian 2 → same
        ↓ Receives Share 2
        ↓ App reconstructs private key from Share 1 + Share 2

Step 4: Key recovered
        ↓ App signs rotation notice: { new_key = old_key (same),
                                        recovery_method: "seed_phrase" | "guardian_threshold",
                                        timestamp,
                                        signature }
        ↓ (If key was compromised and new key needed): same but new_key ≠ old_key

Step 5: Rotation notice distribution
        ↓ App stores notice in outbox
        ↓ Every BLE contact encounter: notice is delivered
        ↓ Contacts with Tier 3 pre-auth: guardians additionally gossip the notice

ASCII Recovery Flow Diagram

  NEW DEVICE                    GUARDIAN 1 (Bob)           GUARDIAN 2 (Carol)
      │                               │                           │
      │  Generate ephemeral           │                           │
      │  recovery keypair             │                           │
      │  (eph_priv, eph_pub)          │                           │
      │                               │                           │
      │──── BLE: RECOVERY_REQ ───────►│                           │
      │     { eph_pub, alice_key_id } │                           │
      │                               │                           │
      │                     Verify alice_key_id exists            │
      │                     Decrypt alice_share_1                 │
      │                     Encrypt to eph_pub                    │
      │                               │                           │
      │◄─── BLE: RECOVERY_RESP ───────│                           │
      │     { Enc(eph_pub, share_1) } │                           │
      │                               │                           │
      │  Decrypt share_1              │                           │
      │  (need 1 more)                │                           │
      │                                                           │
      │──── BLE: RECOVERY_REQ ─────────────────────────────────►│
      │     { eph_pub, alice_key_id }                             │
      │                                                           │
      │                                           Verify + decrypt│
      │                                           Encrypt to eph  │
      │◄─── BLE: RECOVERY_RESP ────────────────────────────────│
      │     { Enc(eph_pub, share_2) }                             │
      │                                                           │
      │  Decrypt share_2                                          │
      │  Reconstruct: SSS.combine(share_1, share_2)              │
      │  → private_key                                            │
      │                                                           │
      │  Sign rotation notice                                     │
      │  Store in outbox                                          │
      │                                                           │
      │──── BLE: KEY_ROTATION_NOTICE ───────────────────────────►│
      │     (gossiped to all future encounters)                   │

6. Protocol Sketch for Contact-Assisted Recovery

This is not a full formal specification, but sufficient to guide implementation.

Share Generation (at Tier 2 setup time)

Input:  alice_private_key (32 bytes, Ed25519 scalar)
        guardian_list [bob_pubkey, carol_pubkey, dave_pubkey]
        K = 2, N = 3

1. SSS split:
   shares = shamir_split(alice_private_key, K=2, N=3)
   → [(1, share_1), (2, share_2), (3, share_3)]

2. For each guardian i:
   ephemeral_key = random_bytes(32)
   share_payload = {
     version: 1,
     owner_key_id: SHA256(alice_pubkey)[0:16],
     share_index: i,
     share_data: shares[i],
     issued_at: unix_timestamp,
     expiry: unix_timestamp + 2*365*86400
   }
   encrypted_share = HPKE_Seal(
     recipient_pubkey = guardian_pubkey,
     plaintext = CBOR(share_payload)
   )

3. Alice delivers encrypted_share[i] to guardian[i] via BLE
   Message type: SHARE_DEPOSIT
   Guardian stores: { alice_key_id, encrypted_share, alice_pubkey }

HPKE (Hybrid Public Key Encryption, RFC 9180) is recommended over raw ECIES — it is standardized, audited, and supports sender authentication.

Data Stored by Guardian

Each guardian stores a small record per principal they guard:

GuardianRecord {
  principal_key_id:     bytes[16]   // SHA256(alice_pubkey)[0:16]
  principal_pubkey:     bytes[32]   // Ed25519 public key
  encrypted_share:      bytes       // HPKE ciphertext
  issued_at:            uint64      // Unix timestamp
  expiry:               uint64      // Unix timestamp
  partial_revocation:   bytes       // Signed revocation token (Tier 3)
  guardian_index:       uint8       // This guardian's share index (1..N)
}

Total storage per guarded user: approximately 500–800 bytes. A user acting as guardian for 10 friends stores under 8KB.

Recovery Request over BLE

The recovery protocol runs over an authenticated BLE channel established after mutual discovery.

Message: RECOVERY_REQUEST
{
  type:           "recovery_request",
  version:        1,
  principal_key_id: bytes[16],       // Which identity to recover
  recovery_pubkey:  bytes[32],       // Ephemeral Ed25519 for this recovery session
  challenge:        bytes[32],       // Random nonce
  timestamp:        uint64
}

Message: RECOVERY_RESPONSE (from guardian)
{
  type:              "recovery_response",
  principal_key_id:  bytes[16],
  guardian_pubkey:   bytes[32],
  encrypted_share:   bytes,          // HPKE-encrypted to recovery_pubkey
  guardian_sig:      bytes[64],      // Ed25519 sig over {principal_key_id, recovery_pubkey, challenge, timestamp}
  timestamp:         uint64
}

The guardian's signature over the challenge prevents replay attacks. The challenge nonce ensures freshness.

Guardian authorization check: Before responding, the guardian verifies:

1. principal_key_id matches a stored GuardianRecord
2. The record has not expired
3. The physical presence condition is met (device is within BLE range — inherent from the BLE transport)

Revocation Notice Structure

RevocationNotice {
  version:         1,
  old_key_id:      bytes[16],        // SHA256(old_pubkey)[0:16]
  old_pubkey:      bytes[32],        // For verification
  new_pubkey:      bytes[32],        // May be null if key destroyed + not yet replaced
  reason:          enum { "rotation", "lost_device", "compromised", "guardian_threshold" }
  timestamp:       uint64,
  ttl_days:        uint16,           // How long to cache and forward this notice

  // Signature options (one or more):
  old_key_sig:     bytes[64]?,       // Present if old key is available
  new_key_sig:     bytes[64]?,       // Present if new key is available
  guardian_sigs:   [{ guardian_pubkey, sig, partial_revocation_token }]?
}

A notice signed by both old and new keys is the strongest form. A notice signed only by guardians is weaker but sufficient when the old key is unavailable.

Propagation to Other Contacts

When a device receives a valid RevocationNotice:

1. Verify signatures (at least 2 guardian sigs, or 1 key sig)
2. Check old_key_id against local contact list
3. If matched: mark the contact's key as status: revoked (or status: pending_update if new_pubkey is present)
4. Store the notice in a revocation_cache with expiry = received_at + ttl_days * 86400
5. On next BLE sync with any contact: include relevant revocation notices in the sync payload
   • "Relevant" = the contact has the revoked key in their contact list (checked via bloom filter or direct key ID exchange)
6. After TTL expires, remove from cache

7. MLS Group Implications

The Problem: Stale Group Membership

In an MLS group, each member is represented by a leaf in the ratchet tree. The leaf contains the member's current signing key and encryption key material. If a member's device is lost or their key is compromised, they continue to appear as a valid member in the tree.

The attacker who holds the old key can:

• Read all new group messages (until a key update is committed that removes their access to the group secrets)
• Send messages as the compromised member (impersonation within the group)
• Observe the group's forward ratchet (group epochs)

Update Proposal (Voluntary Rotation)

If the user still controls their key (voluntary rotation, or migration with both devices available):

1. User generates new leaf keys
2. User sends Update proposal to group: { new_leaf_key, signature_by_old_key }
3. Any group member can commit the proposal, triggering a new epoch
4. After commit: all group members derive new group secrets; the user's leaf now uses the new key
5. The attacker who held the old key loses access to all post-commit messages

This is the cleanest path — MLS was designed for this flow.

Remove + Add (Key Compromise)

If the key is compromised and the attacker may be actively monitoring:

1. Any group member (e.g., a trusted contact who receives the revocation notice) proposes Remove(compromised_leaf_index)
2. Once committed: the compromised key is removed from the group tree; a new epoch is derived without that key's contribution; the attacker can no longer read group messages
3. The legitimate user (with new device/key) requests re-admission
4. A group member who has verified the new key (via in-person NFC) proposes Add(new_leaf_key)
5. Once committed: the user rejoins with the new key

The gap between step 2 (remove) and step 5 (re-add) leaves the user unable to participate in the group. For a small, close-contact group, this gap should be short (days, not weeks). For sparse graphs, it may be significant.

Post-Compromise Security in MLS

MLS provides post-compromise security (PCS) via the TreeKEM protocol:

• Each Update or Commit operation derives a new group secret that is cryptographically independent of previous secrets
• After a compromised member is removed and a new epoch is committed by other members, the group secret no longer incorporates any key material from the compromised leaf
• Even if the attacker retains the old device, they cannot derive group secrets from the new epoch

What MLS cannot protect: Messages sent before the key update are not retroactively protected. If the attacker had the key and was reading messages in epoch N, they have those messages. MLS's PCS only applies to epoch N+1 and later.

Practical Handling Table

Group Admin vs. Leaderless Groups

MLS can operate without a designated admin. Any member can propose; any member can commit. However, in a leaderless group, coordinating a Remove for a compromised member requires consensus. In practice, a simple rule suffices: any member who holds a verified revocation notice for another member may commit a Remove proposal unilaterally, referencing the revocation notice in the commit AAD (Additional Authenticated Data).

The MLS group_event message type for handling key rotation in feeds is defined in Feed Format Spec.

8. Open Problems

Revocation in Fully Disconnected Networks

The core problem — ensuring a revocation reaches all affected contacts in a network with no persistent connectivity — remains an open research problem. There is no known algorithm that provides bounded delivery time guarantees in an arbitrary delay-tolerant network without a central rendezvous point. The approaches described in this document (store-carry-forward, delegates, time-bounded expiry) all have scenarios where they fail.

Relevant academic work:

• Epidemic routing (Vahdat & Becker, 2000): theoretical basis for store-carry-forward
• SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol (Das et al., 2002): gossip convergence analysis
• The delay-tolerant network architecture (Fall, 2003): formal treatment of DTN constraints

No practical solution achieves all of: fast revocation, offline operation, sparse graph coverage, privacy preservation. A production implementation must make explicit tradeoffs and document them to users.

The Legitimate Concurrent Key Problem

This is the most subtle open problem. When Carol receives a notice that Alice has a new key, she faces a decision:

• Is this legitimate? (Alice got a new phone)
• Or is this an attack? (Attacker replaced Alice's key)

The cryptographic evidence is:

• Both signatures (old + new): Strong evidence of legitimacy — an attacker who stole the phone and then lost it could not produce this. But if the device was destroyed, old signature is unavailable.
• Guardian threshold: Requires trusting Alice's guardian selection and the integrity of the guardian devices. A sophisticated attacker who compromised K guardians could authorize a malicious key transition.
• Physical presence in the future: If Carol later meets Alice and the keys match, the transition was legitimate. But "later" may be months away.

There is no purely cryptographic solution to this problem. Physical presence (the app's core trust model) is the only reliable resolution mechanism. The design should make it easy for users to re-verify contact keys in person and flag any unexpected key changes.

The First-Recovery Bootstrapping Problem

Tier 2 recovery requires that Alice already have trusted contacts who hold her shares. But what if Alice is new, has few contacts, or all her guardian-contacts are unreachable?

• New user with no contacts: only Tier 1 (seed phrase) is available
• User with 1 contact: cannot do 2-of-3; only 1-of-1 which provides no threshold security
• Guardians themselves may have lost devices: a guardian whose device is compromised may be unable to safely deliver their stored share

The bootstrapping problem is inherent. Design recommendation: the app should prompt users to establish Tier 2 after their 3rd contact is added, framing it as a mutual benefit ("you hold each other's recovery shares").

Revocation of Revocations

A subtle attack: an attacker who gains temporary access to Alice's device generates a revocation notice pointing to a key they control, then gossips it before Alice can issue a legitimate counter-notice.

Mitigations:

• Time-lock: revocations only take effect after a configurable window (e.g., 24 hours), during which Alice can issue a cancellation
• Sequence numbers: revocation notices carry a monotonic sequence number; contacts accept only the highest-sequence notice
• Guardian threshold: revocations not signed by the threshold of guardians are treated as advisory (trigger a warning) rather than definitive

The time-lock approach is the most practical. It requires that at least one of Alice's contacts be reachable within the lock window — which is not guaranteed in offline mode, but is a reasonable expectation for most scenarios.

No Perfect Solution

The tradeoffs across all approaches:

The design recommended in Section 5 stacks Tier 1 + Tier 2 + Tier 3 to cover the maximum range of scenarios while accepting that no combination achieves perfect security in all cases. Honest communication of these limitations to users is as important as the technical implementation.