The core theorem treats a fixed set of n participants exchanging application messages and update messages over an asynchronous network with possible reordering and concurrent sender updates.

1. threat model

   Adaptive compromise and freshness

   defined

   Security games expose evolving participant state and message transcripts; freshness is expressed relative to compromise and recovery paths through the lattice rather than by one global epoch number.

   Concurrent group-messaging syntax and security setting · Key lattice, local views, KeyRoll, and directional security

A point in the integer lattice records how many key rolls are known along each participant's dimension, and each receiver maintains a local view sufficient to process reachable updates and messages.

1. security goal

   Forward secrecy as backward non-traversability

   formalized

   Deleting obsolete state should prevent a later compromise at a newer coordinate from traversing backward to derive protected earlier keys.

   Key lattice, local views, KeyRoll, and directional security
2. security goal

   Post-compromise security as forward recovery

   formalized

   A fresh honest update moves key state in a direction the adversary cannot traverse from compromised coordinates, restoring secrecy for later reachable states.

   Key lattice, local views, KeyRoll, and directional security

The construction composes an initial group key agreement, a group-random-messaging update layer, and AEAD-protected application payloads.

1. protocol component

   Initial group key agreement

   assumed primitive

   A secure asynchronous GKA establishes the initial shared state; its security is assumed by the group-messaging reduction rather than reconstructed by the key-lattice layer.

   Concurrent group-messaging syntax and security setting · Group-messaging reduction and concrete advantage bound
2. protocol component

   Group random messaging update

   constructed

   The concrete GRM sends evolving ephemeral public-key material and authenticated encrypted randomness, erasing obsolete decryption keys so updates can refresh the appropriate lattice direction.

   Group random messaging primitive and construction
3. protocol component

   AEAD payload protection

   constructed from primitive

   Application messages use the key at the relevant local lattice point and carry coordinate information needed for receivers to select or derive the matching state.

   Concurrent group-messaging construction

The source proves security by reductions to GKA, GRM, and AEAD and analytically derives constant payload and linear update overhead.

1. theorem

   GRM security

   proved conditionally

   Theorem 5.1 reduces security of the concrete evolving-key GRM construction to the stated public-key encryption, authenticated-encryption or MAC, and deletion assumptions.

   Group random messaging primitive and construction
2. theorem

   Group-messaging reduction

   proved conditionally

   Theorem 6.1 bounds the group-messaging adversary by 2 nS times GKA advantage, plus 2 nS n times GRM advantage, plus nS nq times AEAD CCA advantage, with nS and nq denoting the theorem's session and query bounds.

   Group-messaging reduction and concrete advantage bound
3. claim

   Constant payload, linear update

   analytically derived

   Application-message overhead is O(1) in group size and update-message overhead is O(n); the paper argues these asymptotics are optimal for the modeled functionality.

   Concurrency problem, lattice idea, contributions, and costs · Concurrent group-messaging construction

The core proof covers a static group and relies on secure primitives, key deletion, and state handling; fully asynchronous delivery creates an unavoidable correctness-versus-forward-secrecy storage tradeoff.

1. limitation

   Out-of-order window

   explicit tradeoff

   Retaining every obsolete key allows arbitrarily delayed decryption but defeats forward deletion; bounding the receive window preserves deletion but may make sufficiently delayed messages undecryptable.

   Out-of-order delivery, buffering, and bounded-window tradeoff
2. limitation

   Dynamic membership is not re-proved

   informal extension

   Section 8 sketches joins and removals as an extension, but the represented body does not restate and prove the full security theorem for dynamic groups; the formal core should therefore be read as static-group security.

   Informal dynamic-membership extension
3. limitation

   No implementation or operational evaluation

   not evaluated

   The source does not measure latency, storage growth, failed deliveries, state rollback, side channels, or deployment behavior under real messaging workloads.

   Concurrent group-messaging construction · Out-of-order delivery, buffering, and bounded-window tradeoff