1 Introduction
To cope with the potential of cryptanalytically-relevant quantum computers, two lines of research are actively pursued: quantum cryptography aims at leveraging results from quantum physics to establish security guarantees, and post-quantum cryptography makes use of purely classical constructions built from hardness assumptions that take into account quantum cryptanalysis.1 In this paper, we look at one of the fundamental cryptographic tasks—establishing a common secret key among a set of $n\geqslant 2$ participants in an authenticated manner. This task is commonly referred to as authenticated group key establishment $(\mathsf{GAKE})$. The common approach when aiming at quantum-resistant $\mathsf{GAKE}$, is to either consider a solution relying entirely on quantum cryptography, specifically quantum key distribution (QKD), or a pure post-quantum protocol, e.g. leveraging a post-quantum key encapsulation mechanism (KEM), which is a public-key design through which one party generates and transports securely a cryptographic key to a designated peer.
While large-scale QKD networks remain unavailable, non-trivial local QKD infrastructures have been implemented. An incomplete list of examples are testbeds in the Chicago area in the U.S. (see Wu et al., 2021), in the Madrid area in Spain (see Cid et al., 2021), and in the Berlin area in Germany (see Braun and Geitz, 2021). However, existing communication networks are not easy to combine/integrate with these quantum infrastructures, and the security guarantees for the complete network provided by establishing pairwise QKD keys are limited without other cryptographic solutions (most notably, for authentication, but also for refreshing keys or synchronizing multiple nodes). Toward this goal, connecting local QKD network infrastructures remains an active research topic (see Brauer et al., 2024).
On the post-quantum side, there is a lot of recent work on the design, implementation, and verification of two-party key exchange protocols, mostly built from generic transformations applied to encryption schemes or KEMs. An overview of existing solutions is offered by Alagic et al. (2022), which summarizes the results of the third evaluation round of the NIST process toward standardizing post-quantum cryptographic solutions. In the group setting, $\mathsf{GAKE}$ proposals can already be found in the literature, for instance by Apon et al. (2019), Escribano Pablos et al. (2020), or Escribano Pablos et al. (2022), although these types of constructions have not been intensively analysed and little is known for instance, about implementation-dependent attacks.
From a pragmatic perspective, it is desirable to be able to leverage both existing quantum and post-quantum infrastructures, a scenario that is not well understood yet.
Our contribution. We present a construction and security analysis for a flexible quantum-safe $\mathsf{GAKE}$ that leverages available “local” solutions for (group) key establishment, e.g. post-quantum KEMs or QKD-based designs. Depending on the guarantees provided by the contributing local solutions, the resulting $\mathsf{GAKE}$ offers information-theoretic or computational guarantees. It is possible to use our design with classical primitives, QKD connections, or in a hybrid network.
We follow a well-established technique of defining a compiler, i.e. a metaprotocol using one or more $\mathsf{GAKE}$s as embedded subroutines, which can be proven secure provided that a certain level of security is achieved by the basic building blocks involved. The flexibility of our design appears to be very useful with the current state-of-the art, as some quantum and post-quantum designs are still under cryptanalytic exploration.
To be able to capture a hybrid classical/quantum communication infrastructure, we build on a versatile security model proposed by Mosca et al. (2013), introducing some small adaptations. We believe this model to be of interest for exploring (group) key establishment over hybrid classical-quantum networks, independent of our specific $\mathsf{GAKE}$ construction.
Paper Roadmap. We begin this work with a brief overview of the related literature in Section 2, followed by an introduction to the security model we propose to evaluate our construction in Section 3. Section 4 provides a detailed description of our proposal, starting with an outline of the rationale behind the construction, and concluding with a formal security analysis in the final subsection. Given the various choices available for concrete implementation in our design, we discuss different options in Section 5. We conclude with a brief summary of the paper’s main contributions and suggest potential directions for future research in the Conclusion section.
2 Related Work
In the literature, several works can be found exploring different ways of establishing secure keying material through the combination of quantum and classical technologies (see the summarizing Table 1 below).
Table 1
Comparison of (hybrid) quantum resistant key exchange constructions.
| Protocol | Type | Contributing parties | Q-parties | PQ-parties |
| Dowling et al. (2020) | Hybrid AKE | 2 | 2 | 2 |
| Bruckner et al. (2023) | Hybrid AKE | 2 | 2 | 2 |
| Viksna et al. (2023) | QKD distribution/management | 2 | 2 | $n\leqslant 2$ |
| Kozlovics et al. (2023) | QKD distribution/management | 2 | 2 | $n\leqslant 2$ |
| Geitz et al. (2023) | QKD distribution/management | 2 | 2 | $n\leqslant 2$ |
| James et al. (2023) | QKD distribution/management | 2 | 2 | $n\leqslant 2$ |
| Our work | GAKE | $n\geqslant 2$ | any j in $\{2,n\}$ | any j in $\{2,n\}$ |
A number of research contributions look at different ways to derive (two-party) cryptographic keys by combining keys established through different implementations of quantum, post-quantum, or traditional key exchange protocols (see, for instance, Dowling et al., 2020; Bruckner et al., 2023). This hybrid approach differs from ours, as it assumes that each party has access to all involved key sources, while in our scenario nodes have potentially different capabilities, e.g. we may have only few (or no) QKD connections available.
Also, in the last few years, several authors have explored the combination of classical and quantum resources in order to build secure networks, considering the QKD nodes to be the main source of keying material. For instance, in Viksna et al. (2023), Kozlovics et al. (2023), parties use QKD as a service to obtain secure keying material, which is accessed through (classical, post-quantum) TLS links. There, it is however assumed that there exist perfectly secure direct links between users and devices establishing QKD keys, which is a strong assumption. In Geitz et al. (2023), a high-level key management system is described through which all network nodes may access keying material (coming from a QKD, a post-quantum key exchange protocol, or a combination of those). Different protocols within these systems have been implemented in the OpenQKD testbed in Berlin. Similarly, in James et al. (2023), the authors explore different options for building a secure Key Management System in order to scale up from link-to-link quantum key generation to large key distribution networks.
While all these approaches are in a way related to ours, their main goal is to establish two-party keys taking advantage of QKD installations and reinforcing them through PQC. Thus, they could in principle be implemented with “only” two actors involved in the key generation (through a QKD execution). We aim at a contributory scenario, i.e. a general protocol solution where $n\geqslant 2$ users leverage classical and/or quantum techniques in order to (jointly) generate keying material from both sources to establish a secure key for the whole group.
3 Security Model
In this section, we present a novel security model to enable a formal analysis of our proposal. While established models exist in the literature for group key establishment in the classical setting, we are not aware of any prior definition that formalizes the interaction between classical and quantum entities.
As a starting point, we base our work on a proposal by Mosca et al. (2013) and make some small changes to better capture some subtleties of special relevance to the group setting. For the special case of a two-party Authenticated Key Establishment (AKE), our model specializes to Mosca et al.’s. This “downward compatibility” enables us to compile a $\mathsf{GAKE}$ from existing popular two-party QKD (or classical key exchange) protocols that are already known to be secure in Mosca et al.’s framework.
Parties. We follow the formalization in Mosca et al. (2013) based on classical and quantum Turing machines, but make some tweaks to better align with classical group key exchange models (see, e.g. Bohli et al., 2007). By $\overline{\mathcal{P}}$ we denote a finite set of potential protocol participants, each of them labelled by a public identifier. Each party can be seen as a dual entity consisting of an interactive Turning machine that communicates through a classical tape $(e)$ with a coupled quantum Turing machine. Parties communicate through an input-output classical communication channel $(c)$—established between their “classical” parts. In turn, the quantum Turing machines from each party communicate through a quantum chanel $(q)$. The classical Turing machine has also access to a randomness source (through a specific tape denoted r).
All classical information held by a specific party is stored in its memory, consisting of a collection of value pairs of the form $(x,X)$ where x is assumed to be private and X to be public—often referred to as a label of the secret value x.
Session. A protocol can be seen as a well-defined sequence of classical and quantum interactions that will produce a private output to all involved parties, which is either a shared secret or an error message. Specific executions of the protocol are referred to as sessions. Memory pairs held by a party may either be ephemeral, i.e. linked to a specific session, or static, that is, used across multiple sessions.
Each protocol participant $P\in \overline{\mathcal{P}}$ may execute several sessions in parallel. We will refer to a session of P with the notation ${\Pi _{P}^{\psi }}$, where Ψ is a unique protocol session identifier.2 Each such session may be taken for a process executed by P and has assigned several variables to it: ${\mathsf{state}_{P}^{\psi }}$, ${\mathsf{sid}_{P}^{\psi }}$, ${\mathsf{pid}_{P}^{\psi }}$, and ${\mathsf{sk}_{P}^{\psi }}$, These variables are used as follows.
${\mathsf{state}_{P}^{\psi }}$ keeps the state information during the protocol execution, i.e. it stores all memory pairs defined above, and mantains two vectors u, v defined as follows:
-
• $\mathbf{v}=({\mathbf{v}_{0}},{\mathbf{v}_{1}}\dots )$ is a vector of public values or labels, whose components are vectors themselves. E.g., a vector ${\mathbf{v}_{i}}$ can store the ordered public values contributed by an involved participant in the session;
-
• $\mathbf{u}=({\mathbf{u}_{0}},{\mathbf{u}_{1}}\dots \hspace{0.1667em})$ is a vector storing in each component public values linked to an involved participant, yet these values are linked to the authentication process (thus, u will be referred to as the authentication vector).
${\mathsf{sid}_{P}^{\psi }}$ denotes a (non-secret) global session identifier that can serve as the name for the session key ${\mathsf{sk}_{P}^{\psi }}$.
${\mathsf{pid}_{P}^{\psi }}$ stores, as unordered sequence, the public identifiers of those participants that ${\Pi _{P}^{\psi }}$ aims at establishing a key with—not including P itself. We will further denote by ${\bar{\mathsf{pid}}_{P}^{\psi }}$ the unordered sequence of identifiers involved in a concrete execution, namely, the set of identifiers contained in ${\mathsf{pid}_{P}^{\psi }}$ along with the identifier ${\textit{id}_{P}}$.
${\mathsf{sk}_{P}^{\psi }}$ stores the session key once it is accepted by the session ${\Pi _{P}^{\psi }}$. Before acceptance, it stores a distinguished ⊥ value.
We assume that a session ${\Pi _{P}^{\psi }}$ must accept the session key constructed at the end of the corresponding protocol session if no deviation from the protocol specification occurs, resulting in a non-⊥ value of ${\mathsf{sk}_{P}^{\psi }}$. In the sequel, sessions and session variables may be written without sub- or superscripts, if the context renders them unnecessary. The ${\mathsf{state}_{P}^{\psi }}$ variable mentioned above is merely a convenient notation to refer to multiple locally stored values. Otherwise, our terminology follows by and large Mosca et al. (2013) with the following generalizations:
We now rephrase (Mosca et al., 2013, Definition 1) in terms of the session identifier:
-
• In the model of Mosca et al., each session has associated a $\mathsf{pid}$ value to store the identifier of the (one) peer with whom the session is executed. We allow the $\mathsf{pid}$ to be an unordered non-empty sequence of peer identifiers instead. The authentication vector u now captures the information used to identify all peers included in the $\mathsf{pid}$ of the session. Further, as noted above, we will denote by $\bar{\mathsf{pid}}$ the set of all identities involved in the execution (namely, those in $\mathsf{pid}$ and that from party P itself).
-
• The classical Turing machine’s output in Mosca et al. (2013) after a sucessful procotol completion is a tuple $(\mathsf{sk},\mathsf{pid},\mathbf{v},\mathbf{u})$. Here, we allow an optional global session identifier $\mathsf{sid}$ to be included, i.e. the output may have the form $(\mathsf{sk},\mathsf{pid},\mathbf{v},\mathbf{u},\mathsf{sid})$, where the first component—$\mathsf{sk}$—is private output and the vector $(\mathsf{pid},\mathbf{v},\mathbf{u},\mathsf{sid})$ is public output. If $\mathsf{sid}$ is not explicitly specified, it defaults to $\mathsf{sid}=\mathbf{v}$.
Definition 1 (Correctness).
A key exchange protocol is said to be correct if, when all protocol messages are relayed faithfully, without changes to content or ordering, the peer parties output the same session key $\mathsf{sk}$ and the same session identifier $\mathsf{sid}$.
For 2-party key exchange protocols as discussed in Mosca et al. (2013), which do not define an explicit session identifier, this specializes to correctness as used in Mosca et al. (2013). However, for our purposes, the ability to specify a separate session identifier will be convenient: we want to use existing, e.g. 2-party, protocols as building blocks of a protocol involving a larger number of participants. Here, the separation of v from the session identifier frees us from the problem of having to make “local” v-values of a 2-party protocol available to other protocol participants, just to ensure correctness of the overall protocol.
Communication. Following Mosca et al. (2013), the classical Turing machine will have two incoming-outgoing classical communication channels (e and c). Communication through these channels is modelled through oracle queries:3
-
• $\mathsf{SendC}(\textit{params},\mathsf{pid})$: this query is received by a party $P\in \bar{\mathsf{pid}}$ through the c-channel and directs P to begin a new protocol execution, assigning to it a chosen internal protocol session identifier ψ and setting up ${\mathsf{pid}_{P}^{\psi }}=\mathsf{pid}$.
-
• $\mathsf{SendC}(\psi ,m)$: the party receiving this query will receive the classical message m over the c-channel.
-
• $\mathsf{Q}\mathsf{2}\mathsf{C}(m)$: this models internal communication from the quantum to the classical Turing machine of a party; the classical Turing machine receives the message m.
-
• $\mathsf{SendQ}(\rho )$: the party receiving this query will receive the quantum message ρ over the q-channel, activating its quantum Turing machine, which will return any outgoing quantum message over the q-channel and any classical message over the e-channel (towards the classical Turing machine).
-
• $\mathsf{C}\mathsf{2}\mathsf{Q}(m)$: this models internal communication from the classical to the quantum Turing machine of a party; the latter receives the classical message m and may output an outgoing quantum message on the q-channel or a classical message on the e-channel.
For further details on these oracle queries, we refer to Mosca et al. (2013).
Adversarial model. To a large extent, the communication network is controlled by the adversary (following the typical modelling in classical group key exchange). We assume arbitrary point-to-point connections among users to be available, involving for each party the aforementioned classical (c) and quantum (q) channels. With respect to these channels, the network is non-private and fully asynchronous: The adversary may delay, eavesdrop, insert, and delete messages at will, only limited—with regard to the q-channel—by the laws of quantum mechanics. However, the adversary has no control over the communication between the classical and quantum subcomponents of a party, which takes place over the e-channel; neither will he have access to any information concerning the randomness obtained through the r-channel. In addition to the $\mathsf{SendC}$ and $\mathsf{SendQ}$ oracles, the adversary may also issue the following two types of queries to parties:
Non-internal oracle calls (namely, $\mathsf{SendC},\mathsf{SendQ},\mathsf{RevealNext},\mathsf{Partner}$) should, in order to avoid ambiguity, include $(P,\psi )$ as part of the input to clarify which party and which corresponding session are being addressed.
-
• $\mathsf{RevealNext}$; this query allows the adversary to get the public tag X of a freshly generated memory entry $(x,X)$ by the addressed party.
-
• $\mathsf{Partner}(X)$; when addressed to a certain party, if the pair $(x,X)$ exists in its memory, it forwards to the adversary the secret value x. $\mathsf{Partner}(\psi )$ returns the secret key for the corresponding session, if it exists (thus modelling so-called session-key reveals).
Security. As customary, a special $\mathsf{Test}$ oracle is introduced in order to model a real attack and be able to define security:
Indeed, the security model must rule out trivial attacks, i.e. those for which the adversary will know the established session key from its interaction with the involved parties. This is done in Mosca et al. (2013) by introducing the following definition of freshness:
-
• $\mathsf{Test}(P,\psi )$, when called by the adversary, will return ⊥ if a corresponding session key ${\mathsf{sk}_{P}^{\psi }}$ has not been established. Otherwise, the oracle selects uniformly at random a bit $b\stackrel{\mathrm{\$ }}{\gets }\{0,1\}$ and will output ${\mathsf{sk}_{P}^{\psi }}$ if $b=1$ and a randomly selected bitstring (of the same length as ${\mathsf{sk}_{P}^{\psi }}$) if $b=0$. The adversary may call this oracle only once.
Definition 2 (Mosca et al., 2013, 2).
A session ψ of a party P is fresh provided that, if $\mathsf{out}=(\mathsf{pid},\mathbf{v},\mathbf{u},\mathsf{sid})$ is the corresponding public output vector, the following hold:
-
• for every component ${\mathbf{v}_{i}}$ of v there is at least one public label X in ${\mathbf{v}_{i}}$ such that the adversary never queried $\mathsf{Partner}(X)$, and
-
• no query of the form $\mathsf{Partner}({\psi ^{\prime }})$ has been made by the adversary on a session ${\psi ^{\prime }}$ with the same output vector $\mathsf{out}$,4 and
-
• at the time of session completion, for every component ${\mathbf{u}_{i}}$ from u, there was at least one public label X in ${\mathbf{u}_{i}}$, such that the adversary did not query $\mathsf{Partner}(X)$.
Note that all authentication-related private values may be revealed after protocol completion (the above definition only ensures there will be at least one private value the adversary ignores at all times, which is linked to the vector v). This definition of freshness is geared towards including forward security in the model; leakage of authentication keys should not endanger previously established session keys.
Now, the definition of security must establish a corresponding bound on the adversary’s advantage when querying the $\mathsf{Test}$ oracle. Let $\lambda \in \mathbb{N}$ be a fixed security parameter. The advantage ${\mathsf{Adv}_{\mathcal{A}}}(\lambda )$ of an adversary $\mathcal{A}$ in attacking the given protocol is a function in the security parameter λ, defined as
Here, ${\mathsf{Succ}_{\mathcal{A}}}$ is the probability that the adversary queries $\mathsf{Test}$ on a fresh instance and guesses correctly the bit b used by the $\mathsf{Test}$ oracle.
In the above definition, following Mosca et al. (2013), the classical running time of adversaries is assumed to be bounded, and so are the quantum runtime and the quantum memory. We consider here only the case of a polynomially bounded adversary, which is common in classical group key establishment models. However, in connection with quantum key distribution it makes sense to consider so-called long-term security, introduced by Müller-Quade and Unruh (2010), capturing the feature of a protocol that it will remain secure even if all hardness assumptions made no longer hold after the execution has finished. Following Mosca et al. (2013), we capture this as follows:
Definition 4.
A protocol is long-term secure if, for any unbounded quantum Turing machine $\mathcal{M}$ acting on a classical and quantum transcript produced by a bounded adversary $\mathcal{A}$, the advantage of $\mathcal{M}$ in guessing the bit b chosen by the $\mathsf{Test}$ oracle is negligible in the security parameter.
3.1 Adding Integrity to a Secure Key Exchange
To analyse the protocol design proposed below, it will be helpful to adopt a notion of integrity as introduced by Bohli et al. (2007) in the context of classical $\mathsf{GAKE}$. Formally, note that the given definition of freshness allows the adversary to reveal keys from sessions which have different output vectors; as a result, if two completed sessions holding different session identifiers result in the same session key, the adversary trivially wins the $\mathsf{Test}$ challenge by construction. On top of this, integrity guarantees correctness and usability in adversarial environments (for users know who they share the session key with and how to address it).
Definition 5 (Integrity).
We say that a correct (group) key exchange protocol fulfills integrity, if, with overwhelming probability, for all sessions of honest parties that have completed with the same session identifier in their output ($\ne \perp $), the session keys and parties associated with the session key (i.e. the partner identifier combined with the identifier of the party itself, denoted by $\bar{\mathsf{pid}}$) are identical.
In the quantum random oracle model, the following simple observation enables us to augment a given secure $\mathsf{AKE}$ so that it fulfills integrity, in case it does not come with this guarantee already. Note that this approach also preserves long-term security, which is particularly desirable when working with QKD-based solutions.
Lemma 1.
Let $\mathsf{GAKE}$ be a correct and secure key establishment protocol, and write $(\mathsf{sk},\mathsf{pid},\mathbf{u},\mathbf{v},\textsf{sid})$ for the output of a successfully completed session for party P. Assume that $\mathsf{sk}$ is a bitstring of length $\geqslant 9\lambda $, where λ is the security parameter, and write $\mathsf{sk}[:\lambda ]$ for the λ left-most bits of $\mathsf{sk}$, and $\mathsf{sk}[\lambda :]$ for the remaining bits of $\mathsf{sk}$. With a random oracle $H:{\{0,1\}^{\ast }}\longrightarrow {\{0,1\}^{\lambda }}$, the following protocol ${\mathsf{GAKE}^{\prime }}$ is correct, secure and fulfills integrity. ${\mathsf{GAKE}^{\prime }}$ is identical to $\mathsf{GAKE}$, but in case of a successful session completion outputs
\[ \big(\mathsf{sk}[:\lambda ],\mathsf{pid},\mathbf{u},\mathbf{v},H\big(\bar{\mathsf{pid}},\mathsf{sk}[:\lambda ],\textit{\textsf{sid}},\mathsf{sk}[\lambda :]\big)\big).\]
Namely, it sets the output secret key as $\mathsf{sk}[:\lambda ]$, and the corresponding session identifier as
Moreover, if $\mathsf{GAKE}$ is long-term secure, then ${\mathsf{GAKE}^{\prime }}$ is long-term secure.
Proof.
The correctness of ${\mathsf{GAKE}^{\prime }}$ follows immediately from the correctness of $\mathsf{GAKE}$. To see that ${\mathsf{GAKE}^{\prime }}$ is secure, note that $H(\bar{\mathsf{pid}},\mathsf{sk}[:\lambda ],\textsf{sid},\mathsf{sk}[\lambda :])$ implements a statistically hiding commitment on $(\bar{\mathsf{pid}},\mathsf{sk}[:\lambda ],\mathsf{sk}[\lambda :],\textsf{sid})$ in the quantum oracle model— this follows from (Unruh, 2022, Lemma 17), which attributes the result to (Pass, 2004, Lemma 9). So any successful adversary on ${\mathsf{GAKE}^{\prime }}$ could immediately be turned into a successful adversary on $\mathsf{GAKE}$. And as the hiding property of this commitment scheme does not rely on a computational assumption, long-term security is preserved.
4 The Proposed Construction – A Compiler
In this section, we give a detailed description of our proposal. We start by sketching the main idea behind our design and then give the details of the protocol steps. We then state and prove the main result (Theorem 1) stating the security of our construction.
Let $\mathcal{P}\subseteq \overline{\mathcal{P}}$ be the set of parties that seek to establish a common key in a concrete execution, and let
be a partition of $\mathcal{P}$ into non-empty subsets or “clusters”—an important special case is the partition where each ${\mathcal{P}^{(i)}}$ contains only a single party. For each ${\mathcal{P}^{(i)}}$, we fix a cluster leader ${\hat{P}^{(i)}}\in {\mathcal{P}^{(i)}}$, and assume that
-
• for each $i=0,\dots ,n-1$, a secure ${\mathsf{GAKE}^{(i)}}$ solution among the parties from cluster i is available, which we denote by ${\mathsf{GAKE}^{(i)}}$. We write $(\mathbf{c}{\mathsf{sk}_{P}^{(i)}},{\mathbf{c}\mathsf{pid}_{P}^{(i)}},{\mathbf{cv}_{P}^{(i)}},{\mathbf{cu}_{P}^{(i)}},\mathbf{c}{\textsf{sid}_{P}^{(i)}})$ for the output vector of a party P of an execution of ${\mathsf{GAKE}^{(i)}}$;
-
• for $i=0,\dots n-1$, a secure 2-${\mathsf{AKE}^{(i)}}$ protocol can be executed among the leaders ${\hat{P}^{(i)}}\in {\mathcal{P}^{(i)}}$ and ${\hat{P}^{((i+1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}\in {\mathcal{P}^{((i+1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}$. We write $({\mathsf{sk}_{\hat{P}}^{(i)}},{\bar{\mathsf{pid}}_{\hat{P}}^{(i)}},{\mathbf{v}_{\hat{P}}^{(i)}},{\mathbf{u}_{\hat{P}}^{(i)}},{\mathsf{sid}_{\hat{P}}^{(i)}})$ for the corresponding output vector of a cluster leader $\hat{P}$.
4.1 High-Level Description
Fig. 1
Step A in a 3-cluster configuration with two clusters of size two and one cluster of size four, invoking protocols based on post-quantum (PQ) cryptography and quantum key distribution (QKD).
We start with a high-level description of our compiler and fill in the details in Fig. 4 in the next section. First, we note that for the “trivial” case when each cluster consists of a single party, this protocol follows a “standard” Burmester-Desmedt rationale, through which two-party keys established in pairs in a ring configuration are combined in order to derive a group key. The general case can be broken down into three steps:
Step A. During a first phase, all parties within each cluster ${\mathcal{P}^{(i)}}$ execute ${\mathsf{GAKE}^{(i)}}$ to set up a shared “cluster key” $\mathbf{c}{\mathsf{sk}^{(i)}}$ among all parties in that cluster. This value will play the role of an ephemeral masking value for this execution. Also, possibly in parallel to the ${\mathsf{GAKE}^{(i)}}$ execution, each leader ${\hat{P}^{(i)}}$ executes two sessions in parallel of the two-party key establishment, 2-${\mathsf{AKE}^{(i)}}$ and 2-${\mathsf{AKE}^{((i-1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}$, in order to establish two keys, shared with its “counterclockwise neighbour” ${\hat{P}^{((i+1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}$ and “clockwise neighbour” ${\hat{P}^{((i-1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}$ respectively. We denote these two keys by ${\mathsf{sk}_{{\hat{P}^{(i)}}}^{\circlearrowleft }}$ and ${\mathsf{sk}_{{\hat{P}^{(i)}}}^{\circlearrowright }}$, respectively. From this point on, cluster leaders will act on behalf of all participants in the cluster and will be the only ones to send/receive messages to/from outside the cluster. Figure 1 illustrates an example setup for Step A.
Step B. Now, each cluster leader ${\hat{P}^{(i)}}$ commits (using a public random oracle H) to the exclusive-or ${X_{i}}$ of the two keys shared with neighbouring leaders. This commitment is contained in a first message (Step B1) ${M_{i}^{B}}$, while ${\hat{P}^{(i)}}$ sends in Step B2 the actual value ${X_{i}}$, together with the randomness needed to open the commitment (see Fig. 2).
Step C. In a final phase, each cluster leader recovers all two-party keys exchanged throughout the ring of leaders (namely, ${\mathsf{sk}_{{\hat{P}^{(0)}}}^{\circlearrowright }},{\mathsf{sk}_{{\hat{P}^{(1)}}}^{\circlearrowright }},\dots ,{\mathsf{sk}_{{\hat{P}^{(n-1)}}}^{\circlearrowright }}$) and derives a group key and a corresponding session identifier from them (see Fig. 3). Again, the public random oracle H is leveraged here. Finally, each cluster leader broadcasts within its cluster the $\mathsf{sk}$, masked with the lower bits from the key $\textbf{c}{\mathsf{sk}^{(i)}}$ and authenticated with the upper bits of this cluster key, using an unconditionally secure message authentication code (MAC) .
Fig. 3
Step C2: key transport inside cluster ${\mathcal{P}^{(1)}}$ (for ${\mathcal{P}^{(0)}}$ and ${\mathcal{P}^{(2)}}$ this step is analogous).
Remark 2.
One could consider alternative approaches for the final key transport, e.g. using a computationally secure AEAD primitive (authenticated encryption with associated data). The protocol security would then, of course, be conditioned on the security of the specific AEAD primitive.
Remark 3.
The primary communication bottleneck in our construction is the number of involved clusters, as this significantly influences both the number of exchanged messages and the local computations performed by cluster leaders. These exchanges are vulnerable to failures and depend on synchronization and network reliability, which may not always be guaranteed in certain application scenarios. Furthermore, leaders must maintain awareness of their index or position to correctly identify their clockwise and counterclockwise neighbuors. These constraints present major challenges when considering dynamic groups of participants, making our construction unsuitable for such scenarios.
4.2 Detailing the Protocol Steps
Let us look more closely at the individual steps of the proposed compiler. The individual steps are shown in Fig. 4, and we are left with specifying the vectors v and u output at the end of Step C2.
For the pertinent session of each protocol participant $P\in {\mathcal{P}^{(i)}}$ ($i=0,\dots ,n-1$), we let
\[\begin{aligned}{}& \mathbf{u}=\left\{\begin{array}{l@{\hskip4.0pt}l}{\mathbf{cu}_{P}^{(i)}}||{\mathbf{u}_{P}^{((i-1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}||{\mathbf{u}_{P}^{(i)}}||((\ell (\textbf{c}{\mathsf{sk}^{(i)}}[\mathrm{length}(\mathsf{sk}):]))),\hspace{1em}& \text{if}\hspace{2.5pt}P\hspace{2.5pt}\text{is the cluster leader of}\hspace{2.5pt}{\mathcal{P}^{(i)}},\\ {} {\mathbf{cu}_{P}^{(i)}}||((\ell (\textbf{c}{\mathsf{sk}^{(i)}}[\mathrm{length}(\mathsf{sk}):]))),\hspace{1em}& \text{else};\end{array}\right.\\ {} & \mathbf{v}=\left\{\begin{array}{l@{\hskip4.0pt}l}{\mathbf{cv}_{P}^{(i)}}||{\mathbf{v}_{P}^{((i-1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}||{\mathbf{v}_{P}^{(i)}}||{(({r_{j}}),({X_{j}}),(H(\mathtt{0},{X_{j}},{r_{j}})))_{j=0,\dots ,n-1}}\hspace{1em}\\ {} \hspace{1em}||(({c^{(i)}}),({t^{(i)}}),\dots \dots ,(\ell (\textbf{c}{\mathsf{sk}^{(i)}}[:\mathrm{length}(\mathsf{sk})]))),\hspace{1em}& \text{if}\hspace{2.5pt}P={\hat{P}^{(i)}},\\ {} {\mathbf{cv}^{(i)}}||(({c^{(i)}}),({t^{(i)}}),(\ell (\textbf{c}{\mathsf{sk}^{(i)}}[:\mathrm{length}(\mathsf{sk})]))),\hspace{1em}& \text{else}.\end{array}\right.\end{aligned}\]
Following the notation in Mosca et al. (2013), here $\ell (\cdot )$ is a unique public label for a private value (chosen independent of any private value, e.g. with a counter).
Correctness. Correctness of the protocol in Fig. 4 follows from the correctness of ${\mathsf{GAKE}^{(0)}},\dots ,{\mathsf{GAKE}^{(n-1)}}$ and 2-${\mathsf{AKE}^{(0)}},\dots ,\text{2-}{\mathsf{AKE}^{(n-1)}}$. Before going into the security analysis, it is worth noting that the GAKE in Fig. 4 does in general not ensure strong entity authentication—which is not a standard security goal: by design, only the cluster leads have to send messages in Steps B and C. This is attractive from the pespective of communication complexity, but as a consequence it is not clear that every party in $\mathcal{P}$ does indeed have possession of the established session key $\mathsf{sk}$.
4.3 Security Analysis
The goal of this section is to establish the following result, which we prove by adapting the security analysis of a Kyber-based $\mathsf{GAKE}$ by Escribano Pablos et al. (2020), which builds on Abdalla et al. (2007). Analogously as Escribano Pablos et al. (2020), we impose integrity of the underlying 2-$\mathsf{AKE}$ and $\mathsf{GAKE}$ protocols to defend against an attack as considered by Nam et al. (2011).
Theorem 1.
Let λ be the security parameter and $\mathrm{MAC}$ an information-theoretically secure message authentication code with secret-key length $m(\lambda )$ for some polynomial $m(\lambda )\in \Omega (\lambda )$. Assume further that $2\textit{-}{\mathsf{AKE}^{(0)}},\dots ,2\textit{-}{\mathsf{AKE}^{(n-1)}}$ and ${\mathsf{GAKE}^{(0)}},\dots ,{\mathsf{GAKE}^{(n-1)}}$ are secure key exchange protocols satisfying integrity, and each $2\textit{-}{\mathsf{AKE}^{(i)}}$ $(i=0,\dots ,n-1)$ outputs a session key of length $p(\lambda )$ for some polynomial $p(\lambda )\geqslant 8\lambda $, while the output key of each ${\mathsf{GAKE}^{(i)}}$, for $i=0,\dots ,n-1$, has bitlength $m(\lambda )+p(\lambda )$. Then, in the quantum random oracle model, the protocol in Fig. 4 is a secure key exchange protocol fulfilling integrity.
Moreover, if all of $2\textit{-}{\mathsf{AKE}^{(0)}},\dots ,2\textit{-}{\mathsf{AKE}^{(n-1)}},{\mathsf{GAKE}^{(0)}},\dots ,{\mathsf{GAKE}^{(n-1)}}$ are long-term secure, then the protocol in Fig. 4 is long-term secure, too.
Proof.
Before establishing security, we want to establish integrity of the proposed protocol.
Integrity. From (Zhandry, 2015, Theorem 3.1) and (Unruh, 2022, Footnote 13) we obtain that the quantum random oracle H is collison-resistant. As a result, if two output vectors have coinciding $\mathsf{sid}$s, then the corresponding inputs to H must, with overwhelming probability, coincide, namely, they both share the same $\bar{\mathsf{pid}}$ and the same ${\mathsf{sk}_{{\hat{P}^{(0)}}}^{\circlearrowright }},\dots ,{\mathsf{sk}_{{\hat{P}^{(n-1)}}}^{\circlearrowright }}$. By construction, with overwhelming probability, these two sessions must have identical values for the secret key $\mathsf{sk}=H(\mathtt{10},\bar{\mathsf{pid}},{\mathsf{sk}_{{\hat{P}^{(0)}}}^{\circlearrowright }},\dots ,{\mathsf{sk}_{{\hat{P}^{(n-2)}}}^{\circlearrowright }})$.
Security. To establish security of the proposed protocol, we follow to a large extent the game-based reasoning in the proofs of (Abdalla et al., 2007, Theorem 1) and (Escribano Pablos et al., 2020, Theorem 3), making some necessary adaptations. We assume the adversary is interacting with a simulator, which is simulating all oracles and sessions for the adversary.
We proceed in a sequence of games, starting with the real attack against the key secrecy of the group key exchange protocol and ending in a game in which the adversary’s advantage is 0. From game to game the simulator’s behaviour is modified, in a way that allows us to bound the difference in the adversary’s advantage between any two consecutive games. We omit the security parameter in the discussion, namely, writing ${\mathsf{Adv}_{\mathcal{A}}}(\lambda )$ from Definition 3 simply as ${\mathsf{Adv}_{\mathcal{A}}}$. Furthermore, following standard notation, we denote by ${\mathsf{Adv}_{\mathcal{A}}}({G_{i}})$ the advantage of the adversary $\mathcal{A}$ in Game i.
Game $\mathbf{0}$. This first game corresponds to a real attack, in which all the parameters are chosen as in the actual scheme. By definition, ${\mathsf{Adv}_{\mathcal{A}}}({G_{0}})={\mathsf{Adv}_{\mathcal{A}}}$.
Game $\mathbf{1}$. In this game, for $i=0,\dots ,n-1$, we modify the simulation of the $\mathsf{SendC}$ and $\mathsf{SendQ}$ oracles so that, whenever a session ψ is still considered fresh after Step A1, the corresponding keys $\textbf{c}{\mathsf{sk}^{(i)}}$ shared by the involved users are replaced with random bitstrings of the appropriate size.
It is easy to see that the distance between this game and the previous one is bounded by the probability that the adversary breaks the security of any of the underlying ${\mathsf{GAKE}^{(i)}}$ protocols.
As a result, it holds
\[ \big|{\mathsf{Adv}_{\mathcal{A}}}({G_{1}})-{\mathsf{Adv}_{\mathcal{A}}}({G_{0}})\big|\leqslant {\underset{i=0}{\overset{n-1}{\max }}}{\mathsf{Adv}_{\mathcal{A}}^{{\mathsf{GAKE}^{(i)}}}}.\]
Here, ${\mathsf{Adv}_{\mathcal{A}}^{{\mathsf{GAKE}^{(i)}}}}$ denotes the advantage of $\mathcal{A}$ against ${\mathsf{GAKE}^{(i)}}$, which should be a function of the security parameter λ and the number of different involved sessions (i.e. sessions for which either $\mathsf{SendC}$ or $\mathsf{SendQ}$ have been queried by $\mathcal{A}$).
Game $\mathbf{2}$. In this game, for $i=0,\dots ,n-1$, we modify the simulation of the $\mathsf{SendC}$ and $\mathsf{SendQ}$ oracles so that, whenever a session ψ is still considered fresh after Step A2, the corresponding keys ${\mathsf{sk}_{{\hat{P}^{(i)}}}^{\circlearrowleft }}$ shared by the cluster leaders ${\hat{P}^{(i)}}$ and ${\hat{P}^{((i+1)\hspace{0.2em}\mathrm{mod} \hspace{0.2em}n)}}$ for $i=0,\dots ,n-1$ are replaced with n elements selected uniformly at random from the intended key space.
It is easy to see that the distance between this game and the previous one is bounded by the probability that the adversary breaks the security of any of the underlying 2-${\mathsf{AKE}^{(i)}}$ protocols.
As a result, it holds
\[ \big|{\mathsf{Adv}_{\mathcal{A}}}({G_{2}})-{\mathsf{Adv}_{\mathcal{A}}}({G_{1}})\big|\leqslant 2\cdot {\underset{i=0}{\overset{n-1}{\max }}}{\mathsf{Adv}_{\mathcal{A}}^{\text{2-}{\mathsf{AKE}^{(i)}}}}.\]
Here, ${\mathsf{Adv}_{\mathcal{A}}^{\text{2-}{\mathsf{AKE}^{(i)}}}}$ denotes the advantage of $\mathcal{A}$ against a concrete session of 2-${\mathsf{AKE}^{(i)}}$ (note that two sessions, i.e. two test queries, each corresponding to one of the involved leaders, are to be linked to each actual execution, thus the factor 2 in the bound above). Again, this advantage is a function of the security parameter λ and the number of different queries to the involved sessions.
Game $\mathbf{3}$. In this game, we change the simulation of the $\mathsf{SendC}$ oracle so that a fresh instance ψ does not accept in Step C1 whenever for some i a message ${M_{i}^{B2}}$ was not faithfully simulated (as would have been generated in that same session by the intended cluster leader).
Note that the adversary will only notice the difference if both the message ${M_{i}^{B2}}$ is being fabricated or replayed from another execution in a way that it is consistent with ${M_{i}^{B1}}$ (i.e. the hash $H(\mathtt{0},{X_{i}},{r_{i}})$ is consistent with the ${X_{i}}$ value from ${M_{i}^{B2}}$) and, moreover, the bitstring ${X_{0}}\oplus \cdots \oplus {X_{n-1}}$ is the all-zero bitstring. Given that, at this point, these ${X_{i}}$-values are distributed uniformly at random and independent of previous messages, the probability that the replayed/fabricated messages involve a matching ${X_{i}}$ is negligible.
Game $\mathbf{4}$. This game reproduces the modification also for the commitments in Step B1: The simulation of the $\mathsf{SendC}$ oracle changes so that a fresh instance ψ does not accept in Step C1 whenever one value $H(\mathtt{0},{X_{j}},{r_{j}})$ for $j\ne i$ is not faithfully simulated. The adversary will only notice the difference if the simulator can fabricate a matching value on the range of H that is actually equal to $H(\mathtt{0},{X_{j}},{r_{j}})$. Due to the preimage resistance of the (quantum) random oracle H (cf. Yamakawa and Zhandry, 2021, Corollary 4.13), the adversary’s advantage diverges only negligibly from the previous game:
Game $\mathbf{5}$. Note that, at this point, all messages produced in Step B are faithfully generated by the simulator. Now, in the simulation of the $\mathsf{SendC}$ oracle we modify how the values in the first component of ${c^{(i)}}$ are generated: they are simply bitstrings of the appropriate length, chosen uniformly at random. Indeed, as these values were one-time pad encryptions (with one-time keys, chosen uniformly at random) of the session key, they should again be indistinguishable from random, as a result
Game $\mathbf{6}$. We now modify the simulation of the $\mathsf{SendC}$ oracle at the point of computing the session key and the corresponding session identifier. At this, the simulator chooses a session key $\mathsf{sk}\in {\{0,1\}^{\lambda }}$ uniformly at random and does the same with the $\mathsf{sid}$.
Note that the (quantum) random oracle outputs are indistinguishable from random, so, indeed,
Moreover, as the session key is now chosen uniformly at random (independently of any other value the adversary may have access to), it holds that
which concludes the proof.
Long-term security. Suppose that an adversary has access to a protocol transcript and faces the challenge of distinguishing the corresponding established secret key from a random bitstring of the same length. More specifically, he has access to a public output vector
and needs to decide whether a bit string ${\mathsf{sk}^{\ast }}$ has been chosen uniformly at random (in the appropriate space) or is the actual session key established in that session. We may assume, without loss of generality, that the output vector comes from a cluster leader ${\hat{P}^{(i)}}$. That is
and
We can again follow a game-based structure where the adversary interacts with a simulator providing him with the transcript. Note that in this case, we are considering a passive attack when the adversary just gets the public output vector and cannot interact with any party involved in the actual session.
Game $\mathbf{0}$. Again, we start with a game corresponding to the real attack, in which the transcript is faithfully simulated. By definition, ${\mathsf{Adv}_{\mathcal{A}}}({G_{0}})={\mathsf{Adv}_{\mathcal{A}}}$.
Game $\mathbf{1}$. Now, we replace the ${X_{j}}$-values in the v-vector with a bitstring of the same length, yet chosen uniformly at random. If we assume that all involved 2-${\mathsf{AKE}^{(i)}}$s produce two-party keys that are indistinguishible from values selected uniformly at random (in a long-term sense), so are the corresponding exclusive-or-values of each neighbouring pair of keys, i.e. ${X_{i}}={\mathsf{sk}_{{\hat{P}^{(i)}}}^{\circlearrowleft }}\oplus {\mathsf{sk}_{{\hat{P}^{(i)}}}^{\circlearrowright }}$. As a result,
Game $\mathbf{2}$. Now, replace each of the left-most components of the values ${c^{(i)}}$ with a uniformly at random chosen value from the corresponding key space. Assuming the ${\mathsf{GAKE}^{(i)}}$s are long-term secure, this should not be noticeable, for each session key is one-time pad encrypted with a bitstring that is indistinguishable from one selected uniformly at random, thus:
\[ \big|{\mathsf{Adv}_{\mathcal{A}}}({G_{2}})-{\mathsf{Adv}_{\mathcal{A}}}({G_{1}})\big|\leqslant {\underset{i=0}{\overset{n-1}{\max }}}{\mathsf{Adv}_{\mathcal{A}}^{{\mathsf{GAKE}^{(i)}}}}.\]
Moreover, note that the session identifier
\[ \mathsf{sid}=H\big(\mathtt{11},\bar{\mathsf{pid}},{\mathsf{sk}_{{\hat{P}^{(0)}}}^{\circlearrowright }},\dots ,{\mathsf{sk}_{{\hat{P}^{(n-1)}}}^{\circlearrowright }}\big)\]
leaks nothing about the established session key, for it can be seen as a statistically hiding commitment on the values ${\mathsf{sk}_{{\hat{P}^{(0)}}}^{\circlearrowright }},\dots ,{\mathsf{sk}_{{\hat{P}^{(n-2)}}}^{\circlearrowright }}$ using as randomness the value ${\mathsf{sk}_{{\hat{P}^{(n-1)}}}^{\circlearrowright }}$ (which is, by assumption, long-term secure).5 Design Choices
We have provided a general compiled protocol that can be constructed using various concrete cryptographic tools, following the principles of cryptoagility, which aims for modular designs that can be easily updated if any of the underlying tools need to be replaced. In this section, we offer guidance on how to make appropriate choices for the building blocks of our protocol.
There are many candidates in the literature for deriving the 2-$\mathsf{AKE}$ and $\mathsf{GAKE}$ constructions needed for our design. Prominent two-party quantum-key distribution protocols as analysed by Mosca et al. (2013) offer QKD building blocks, which we can now combine to $\mathsf{GAKE}$ solutions in a flexible manner.
For post-quantum cryptography, one can try to leverage known techniques to build 2-party authenticated key-exchange protocols from simpler cryptographic primitives, e.g. from a given Key Encapsulation Mechanism (KEM) (cf., for instance, Hövelmanns et al. (2020)). A high-level description of such a 2-AKE construction is shown in Fig. 5. At this, both parties have a pair of long-term authentication keys. In the figure, ${P_{i}}$ initiates the key exchange by executing an initiation algorithm $\mathrm{Init}$ and sending a message M to ${P_{j}}$, which through a key derivation algorithm $\mathrm{De}{r_{resp}}$ computes the key ${K^{\prime }}$ and a message ${M^{\prime }}$. Upon receipt of ${M^{\prime }}$, the receiver ${P_{i}}$ is able to obtain the key K with a respective key derivation algorithm $\mathrm{De}{r_{init}}$.
If the key exchange is successful, $K={K^{\prime }}$. In the quantum random oracle model, many such constructions (e.g. derived from Kyber, McEliece, or NTRU) are proven to be secure in a suitable sense. Moreover, as the key derivation algorithms involved are not deterministic, it is often the case that (some flavour of) forward security is attained – thus paving the way for long-term security in our setting. To this aim, often the $\mathrm{Init}$ algorithm involves a fresh key generation for a KEM, so that there will be an encapsulated key involved in the final output key that cannot be retrieved from the static long term keys of the involved participants.
For the classical group setting, solutions building on these two-party designs are available and may be implemented from different code- or lattice-based cryptographic building blocks (see Escribano Pablos et al., 2020, 2022). It is a natural topic for follow-up research to try to establish general statements that enable an automatic lifting of security guarantees in one of the popular classical security frameworks for $2\text{-}\mathsf{AKE}$ or $\mathsf{GAKE}$ protocols to security guarantees in our model.
6 Conclusion
In this paper, we have proposed the first (to our knowledge) construction of a group key establishment protocol including entities that may have access to quantum or classical technologies. In particular, we integrate clusters of users that may obtain keying material through quantum technologies (i.e. may execute QKD protocols in pairs) and clusters (of $n\geqslant 2$ entities) that are able to establish secure keys through post-quantum protocols. All keying material can be combined to establish a group key shared by all involved entities.
Our construction is proven secure in a formal model including adversaries that have access to quantum resources, thus attaining a very high security level. The security model introduced in this paper is based on Mosca et al. (2013), one of the few works exploring formal models of security for hybrid scenarios. We believe that this work is a step forward towards these kinds of formalization efforts, which are needed in order to derive sound security proofs in any scenario where quantum/classical technologies are combined.
Furthermore, we believe our construction could be adapted to support diverse network infrastructures. In particular, refining it to function effectively in scenarios with communication constraints would be especially valuable (e.g. to prevent aborts if some leaders from an initially designated cluster fail to complete the protocol). Exploring such a dynamic adaptation of our construction would be a promising avenue for future research.
