From Key Encapsulation to Authenticated Group Key Establishment—A Compiler for Post-Quantum Primitives †

Assuming the availability of an existentially unforgeable signature scheme and an (IND- CCA secure) key encapsulation mechanism, we present a generic construction for group key establishment. The construction is designed with existing proposals for post-quantum cryptography in mind. Applied with such existing proposals and assuming their security, we obtain a quantum-safe three-round protocol for authenticated group key establishment that requires only one signature per protocol participant.


Introduction
To enable confidential communication among a group of two or more users over an insecure network, cryptography provides group key establishment procotols. Dealing with a non-trusted communication infrastructure, the question of authenticating protocol participants naturally arises in this context as well. The resulting cryptographic protocols are commonly application-agnostic and focus only on the task of establishing a shared high-entropy secret among the legitimate users, not mandating any particular usage of that secret key in subsequent applications. The resulting task, authenticated group key establishment (AGKE), is fairly well-understood, even though there is a remarkable diversity in the details of security models in use. A standard technique to derive an AGKE solution is to apply some form of protocol compiler or generic framework to a passively secure solution. If a public-key infrastructure is available, signatures provide an adequate mechanism. This results commonly in protocols with a substantial number of signatures being computed, transmitted, and verified:

•
In the Katz-Yung compiler [1], for each message sent in the original protocol, a signature has to be computed and transmitted (and verified). For instance, Apon et al. [2] propose the application of this compiler for their unauthenticated group key establishment solution.  Bohli's framework for robust group key agreement [4] targets two-round protocols, and in each round each participant sends a signed message (and verifies signatures by all other participants).
For our purposes, the KEM needs to be perfectly correct, i.e., we require that for all key pairs (pk, sk) generated by KeyGen the following correctness condition holds: if (K, C) is an output of Encaps(pk), then Decaps sk (C) = K.
The most relevant notion to capture the security of a KEM is that of indistinguishability under chosen-ciphertext attacks (also defined in [12]), which is once again similar to the usual one for PKEs, except that the adversary is now asked to distinguish between an honestly encapsulated key and a pseudorandom value. We provide a formal definition below.
Definition 2 (IND-CCA Security). A KEM is IND-CCA secure if the advantage of any probabilistic polynomial time adversary A in the game described in Figure 1, as a function in the security parameter, is negligible. Here the advantage of an adversary A is defined as Adv IND-CCA Setup: the challenger C runs the key generation KeyGen to obtain a key pair (pk, sk) and hands the public key pk to the adversary A. Queries: the adversary A is given access to a decapsulation oracle, which, when queried on an encapsulation C, returns its corresponding decapsulated symmetric key K. Challenge: the challenger C computes (K 0 , C * ) ← Encaps(pk) and selects uniformly at random K 1 from the symmetric key space. Then C selects a bit b ∈ {0, 1} uniformly at random and hands (K b , C * ) to A. Queries: the adversary A is given access to a decapsulation oracle, which, when queried on an encapsulation C, returns its corresponding decapsulated symmetric key K. The challenge encapsulation C * must not be queried by the decapsulation oracle. Guess: the adversary outputs b ∈ {0, 1} and wins if and only if b = b , and C * was not queried by the decapsulation oracle.

Signature Scheme
To formalize a signature scheme, we follow the usual approach.

Definition 3 (Signature).
A signature is a triple of polynomial time algorithms (SigKeyGen, Sign, Verify) as follows: • SigKeyGen is probabilistic. Given the security parameter , it generates a pair of public and secret keys (vk, sigk). • Sign is probabilistic. Given a secret key sigk and a message M it generates a signature σ. • Verify is deterministic. Given a public key vk, a signature σ, and a message M, this algorithm outputs 1 if the signature is valid and 0 otherwise.
We require that for all key pairs (vk, sigk) generated by SigKeyGen and for all messages M the following correctness condition holds: If σ is an output of Sign(sigk, M), then Verify vk (σ, M) = 1.
The security notion usually required for signatures is existential unforgeability under chosen message attacks, and we capture it by the following definition.
Definition 4 (EUF-CMA security). A signature scheme is EUF-CMA secure if the advantage of any probabilistic polynomial time adversary A in the game described in Figure 2 is negligible. Here the advantage of an adversary A is defined as the function Adv EUF-CMA is the event that A wins.

•
Setup: the challenger C runs the key generation SigKeyGen to obtain a key pair (vk, sigk) and hands the public key vk to A. • Queries: the adversary A is given access to a signing oracle. When queried for message m, the challenger runs algorithm Sign on input m and sigk and returns the corresponding output σ to the adversary. • Forgery: the adversary A outputs a pair (µ, σ) and wins if and only Verify vk (σ, µ) = 1 and no query for a signature on µ was asked.

Security Model and Security Goals
The security model we use follows the oracle-based approach to capture adversarial capabilities-this approach is also used by Katz and Yung [1], for instance, building on the work of Bresson et al., work [13].

Protocol Participants
Given a security parameter , we assume that the set of protocol participants U is polynomial in . We model each user U ∈ U as a probabilistic polynomial time algorithm which is allowed to execute a polynomial number of protocol instances Π s U (s ∈ N) concurrently. We assume user identities to be bitstrings of identical length and to keep notation simple, throughout we will use U referring to both the bitstring identifying a user U and the algorithm U itself. Let Π s U be a protocol instance, the following seven variables are associated with it: pid s U : stores the identities of those users in U with which a key is to be established a particular instance aims at establishing a key with, including U (this ensures being partnered is thus a reflexive relation); sid s U : stores a session identifier, i.e., a non-secret public identifier for the session key sk s U ; sk s U : stores a distinguished NULL value and after a successful protocol run holds the session key; acc s U : is set to TRUE if the session key stored in sk s U has been accepted; state s U : keeps state information needed while executing the protocol (e.g., the secret scalars used as ephemeral Diffie-Hellman keys); term s U : is set to TRUE if this protocol execution has terminated; used s U : indicates if this instance is used, i.e., currently involved in a protocol execution.

Initialization
Before actual protocol executions take place, we allow an optional trusted initialization phase without adversarial interference. During this phase, for each user public and private key pairs (pk U , ak U ) can be generated and distributed accordingly. These private and public keys can include the ones corresponding to a KEM, a signature scheme, etc. The initialization phase can also be used to issue (possibly needed) further public parameters.

Adversarial Capabilities and Communication Network
The adversary A is represented as a probabilistic polynomial time algorithm with full control over the communication network. The network is, therefore, fully asynchronous, non-private, allowing arbitrary point-to-point connections among users. More specifically, we express the capabilities of the adversary through the following oracles: Send(U, s, M) : This oracle can be used in two ways.

•
The adversary can initialize a protocol execution; sending the special message M = {U i 1 , . . . , U i r } ⊆ U to an unused instance Π s U with U ∈ M initializes a protocol run among U i 1 , . . . , U i r . After such a query, Π s U sets pid s U := {U i 1 , . . . , U i r }, used s U := TRUE, and processes the first step of the protocol. • The message M is sent to instance Π s U . The oracle returns the protocol message output by Π s U after receiving M. Reveal(U, s) : returns the stored session key sk s U if acc s U = TRUE and a NULL value otherwise. Corrupt(U) : for a user U ∈ U this query returns U's long-term secret key ak U .
Notice that, unlike Reveal, Corrupt refers to a user instead of to an individual protocol instance. We consider an adversary to be active if it has access to all of the above oracles. To capture a passive adversary, we can replace access to Send oracle with access to an Execute oracle, which returns a complete protocol transcript among the specified unused instances. An active adversary can simulate this Execute oracle using Send in the natural way.
For technical reasons, we introduce one more oracle, Test, and A must submit exactly one query of the form Test(U, s) with an instance Π s U that has accepted a session key, i.e., with acc s U = TRUE. In response to such a query, a bit b ← {0, 1} is sampled uniformly at random. For the case b = 1, the established session key stored in sk s U is returned. For b = 0 the output is a uniformly random element sampled from the space of session keys. The idea is that for a secure group key establishment protocol, no efficient adversary can distinguish between the cases b = 0 and b = 1. To turn this idea into a definition, we exclude trivial cases and focus on correct group key establishment protocols: Correctness refers to a scenario where no attack takes place; to formulate security guarantees we need to specify the circumstances under which a correct guess for the random bit used by the Test oracle constitutes a possible attack. For this we use the following notions of partnering and freshness.
Based on this notion, we can determine what a fresh instance is, i.e., an instance where the adversary does not know the session key for trivial reasons.
The following formulation allows an adversary A to reveal all secret keys without violating freshness, provided A does not send any "relevant" messages afterwards. Therefore, security in the sense of Definition 8 below implies forward secrecy: For some U j ∈ pid s i i a Corrupt(U j ) query was executed before a query of the form Send(U k , s k , * ) has taken place where U k ∈ pid s i i .

•
A query Reveal(U j , s j ) with Π s i i and Π s j j being partnered occurred.
We write Succ ke A for the event that A queries Test with a fresh instance according to Definition 7 and outputs a correct guess for the Test oracle's bit b.

Definition 8 (Semantic security).
A key establishment protocol is said to be semantically secure, if the advantage Adv ke A = |2 · Pr[Succ ke A ] − 1| is negligible for all probabilistic polynomial time algorithms A.
To make explicit that adversaries are considered to be active, i.e., have access to the Send oracle, it is common to refer to a group key establishment protocol as authenticated. On the other hand, we speak of unauthenticated group key establishment if the adversaries are passive.

Proposed Construction
The proposed generic construction for designing an authenticated group key establishment for n users U 0 , . . . , U n−1 is shown in Figure 3. It builds on an available key encapsulation mechanism and a signature scheme. The following theorem shows that the proposed construction offers a provable security guarantee, if the underlying primitives meet standard security requirements.
Set up: A pair of keys (vk i , sigk i ) for the signature scheme S is generated for each U i , which gets the secret key sigk i while vk i is publicized.

Round 1: Computation.
Each U i generates an ephemeral pair of keys for E : Broadcast. Each U i sends to his right a neighbor the message (pk i , U i+1 ) Round 2: Computation. Each U i , using the ephemeral public key he has received, computes an encapsulation for that key: Broadcast. Each U i does sends to his left neighbor the message (C i−1 , U i−1 ) Round 3: Computation. Each U i does the following: • Using his ephemeral secret key, decapsulates the received key K i ← KeyDecaps sk i (C i ); • Using the encapsulated key he sent before, computes Computes a signature σ i on pk 0 , . . . , pk n−1 , C 0 , . . . , C n−1 , X i , pid i Broadcast. Each U i broadcasts (X i , σ i ) Key Computation. Check. Each U i checks all the signatures, equality of pids, X 0 ⊕ · · · ⊕ X n−1 = 0; if any check fails, aborts. Computation. Each U i does the following: Sets the session identifier sid i to pk 0 , . . . , pk n−1 , C 0 , . . . , C n−1 , X 0 , . . . , X n−1 , pid i .; • Accepts K 0 as session key.
a The ordering can be determined by means of lexicographic ordering of user identifiers, for instance, and the users are assumed to be in a circle, i.e., U 0 and U n−1 are neighbours Figure 3. A compiler achieving authenticated group key establishment from a secure key encapsulation mechanism (KEM) and a secure signature scheme. Theorem 1. Assuming S is an EUF-CMA secure signature scheme and E is an IND-CCA secure KEM, the protocol from Figure 3 is correct and semantically secure.
Proof. We can easily verify the protocol correctness: if all the participants follow the protocol description and there is no active adversarial interference, then all checks will succeed and every participant will set the same pid and sid. Moreover every participant will receive the correct {X j } n−1 j=0 and consequently they will be able to compute the same session key K 0 .
To illustrate the security of our compiler, we use the "game hopping" technique, where we let the adversary A interact with a simulator B. We denote by Adv(A, G i ) the advantage of the adversary in Game i. The security parameter is denoted by . Further, we denote by q e and q s the maximum number of queries made by the adversary to the Execute and Send oracles, respectively.
Game 0. This game is identical to the original attack game, with all the oracles being simulated as in the real protocol. Therefore, Adv(A, G 0 ) = Adv ke A ( ).

Game 1. Let
Forge be the event that the adversary succeeds in forging an authenticated message pk 0 , . . . , pk n−1 , C 0 , . . . , C n−1 , X i , pid i , σ i of at least one party U i without having queried Corrupt(U i ) and where all the values signed involved pk 0 , . . . , pk n−1 , C 0 , . . . , C n−1 , X i , pid i , σ i were not output by a same U i 's instance. Any time this event occurs, we abort and mark this as success for the adversary.
An adversary A that can achieve Forge can be used to construct an adversary A that forges a signature in the EUF-CMA game: the given public key is assigned randomly to U i , one of the users; all other participants are initialized as the protocol indicates; afterwards all the queries in the security game are answered faithfully and when a signature by the chosen user is needed, the signing oracle of the EUF-CMA game is queried to produce it.
The probability of the adversary choosing U i when assigning the public key for the signature is at least 1/|U |, and with |U | being polynomial size, this is non-negligible: for a polynomial bound poly Forge on |U |. Game 2. This game is exactly as Game 1 except that a session t is chosen uniformly at random. If the Test query does not occur in the t-th session the game aborts, and we count it as win for the adversary. As the number of active protocol instances is polynomially bounded, we have for a polynomial bound poly Test on the number of protocol sessions activated. Game 3. This game is identical to the previous game, except that the simulation of the Send, Execute and Test oracles is modified as follows. The symmetric key K 0 output by Encaps(pk 0 ) in the Test instance Π t 0 is replaced with a random key K * chosen from {0, 1} . In order to bound the difference in the advantages between Games 2 and 3, we will build, from an adversary A ble to distinguish between both games, an adversary B attacking the key encapsulation mechanism E such that where Adv IND-CCA B ( ) denotes the advantage of a probabilistic polynomial time adversary B attacking KE M.To establish this bound, we assume that B, which runs A as an auxiliary algorithm, can access a simulation of KE M. Further, B executes the key generation algorithm of S for each user U i , thus obtaining a pair of keys (vk i , sigk i ) for the signature scheme. Adversary B also executes the key generation algorithm of KE M for user U 0 , and obtains the public key corresponding to users U 1 , . . . , U n . Our adversary B obtains a challenge (C * , K 0 , K 1 ) as described in Definition 1, and we have to describe how B answers to A's queries: • Whenever a query Corrupt(U i ) is made by A, B generates the keys for the signature and returns sigk i as answer to A. • To answer a Send query for Round 2 involving U 0 , B uses the challenge encapsulation C * . The rest of the answers are generated as in a real execution of the protocol.

•
To answer an Execute query by A, our adversaryB modifies the messages as described for the simulation of the Send oracle. • A Reveal query by A is answered in a similar way as a Send or Execute query. Notice that a Reveal query cannot be made on t or any partnered instance. To answer any other Reveal query B uses the decapsulation oracle of its IND-CCA game.

•
Finally, to answer a Test query, a bit b is chosen by B when starting the simulation. B will return the key K b received from the KEM challenger to A.
At some point A will output a bit b as a guess for b which will determine the output b of B for the KEM challenge. Specifically, B outputs b = 0 if and only if b = b . Taking into account that the view of A is identical to Game 2, if the answers of B's simulation of Test are real keys and to Game 3 if the answers of B's simulation of Test are random ones, we obtain that |Adv(A, To conclude the proof, we can see that the advantage of the adversary in Game 3 equals 0, as the session keys are chosen uniformly at random in {0, 1} κ . Collecting all the advantages, we can see that Adv ke A is indeed negligible.

Remark
We would like to point out that our scheme, as described above, meets precisely the security criteria described in Section 3. It would be possible to adjust our construction to capture additional security notions, for instance introducing contributory properties. In this case, only a minor modification becomes necessary. In fact, since all of K 0 , . . . , K n−1 are available to each legitimate user, one could choose K 0 ⊕ · · · ⊕ K n−1 as session key, rather than just K 0 . The proof would then be amended accordingly, as follows: in Game 3, after replacing K 0 with K * , produce a pseudorandom session key as K * ⊕ · · · ⊕ K n−1 . The pseudorandomness follows immediately from the fact that K * is chosen uniformly at random in {0, 1} .

Instantiation
To instantiate the above AGKE construction, there are various natural options both for KEMs and signature schemes. Some possible candidates for quantum-safe KEMs include [14][15][16][17]. Moreover, examples for candidates of post-quantum signature schemes are offered by [9,18]. The particular choice of schemes can be made taking into account their efficiency or the assumption their security relies on. Different applications may have different preferences for prioritizing, e. g., public-key size over signature size.

Conclusions
The protocol compiler presented here offers a convenient approach to systematically design authenticated group-key establishment protocols in a post-quantum scenario. Keeping the number of signatures needed low (one per user), gives a protocol designer flexibility in the type of post-quantum signature signature scheme to be deployed. With three rounds, the round complexity that is achievable with currently available key encapsulation mechanisms appears quite attractive, too.
Funding: This research was funded in part by the NATO Science for Peace and Security Programme under grant G5448 and through research project MTM2017-83506-C2-2-P by the Spanish MICINN.