1 Introduction
The advent of quantum computing has had a great effect in cryptographic developments, giving rise to different active lines of work. Some efforts focus on finding new constructions exploiting the great potential of quantum technology (Quantum Key Distribution schemes being the flagship example), while others target design strategies transitioning from classical to quantum resistant schemes.
In this contribution, we focus on group key exchange protocols ($\mathsf{GAKE}$), which are cryptographic constructions allowing a group of $n\geqslant 2$ participants to agree upon a high-entropy secret key. Communication is carried out over an insecure channel, and thus legitimate participants need to authenticate themselves (if not necessarily as specific individuals, at least as legitimate group members). It is typical to assume in this context that the network is fully under adversarial control, and thus a potential adversary may not only eavesdrop, but also delay, suppress, or insert messages at will. On top of the standard security challenges encountered in this framework, significant difficulties arise when considering adversaries that have access to quantum computing—the so-called post-quantum setting. Basic building blocks behind a post-quantum $\mathsf{GAKE}$ (such as encryption or commitment schemes) should be proven secure in this new restricted scenario, where primitives based on the hardness of factoring or computing discrete logarithms in certain groups can no longer be trusted. While a number of primitives for post-quantum cryptographic tasks are available, restricting to this kind of tools comes at a prize in terms of computational cost, memory, bandwidth, etc. The question arises whether it is possible to put off some of the cost that comes with an immediate transition to a “full-fledged post-quantum design” without jeopardizing the long-term security of established session keys. This is where a future-quantum scenario comes in.
Related work
Two-party constructions. A number of two-party key establishment protocols have been proposed taking into account quantum adversaries with diverse security models and levels of formalism. Many of these proposals are not contributory key exchange protocols, but key encapsulation mechanisms (KEMs), allowing one party to send a high-entropy key to another one, which can be later used to secure their two-party communication; submissions to NIST’s ongoing standardization effort provide various examples of current candidates for post-quantum KEMs National Institute of Standards and Technology (2019).
When it comes to secure joint key generation of two-party keys, fewer proposals are available in the literature. In Bos et al. (2015), an unauthenticated Diffie-Hellman-like key exchange protocol is proposed, based on the ring learning with errors (RLWE) problem, and the authors demonstrate its practicality, integrating it in TLS cipher suits. Their protocol is only secure for passive adversaries, and classical (non-quantum resistant) authentication means—such as RSA signatures—are suggested in order to dodge active attacks by standard adversaries. Also considering different levels of quantum-precautions with respect to authentication, Bindel et al. (2018) builds a hybrid key exchange protocol, in the two party scenario, which uses (post-quantum) KEMs as a fundamental building block. More precisely, they present a compiler for authenticated key exchange that can be built from a passively secure KEM, a signature scheme, a message authentication code and a secure key derivation function. Depending on the security of these building blocks, different guarantees are proven with respect to two-stage adversaries.1
Ding et al.’s recent work Ding et al. (2019b) is worth mentioning, too. They gave a somewhat informal proposal for two-party key exchange constructions based on the short integer solution problem and learning with errors. In a similar fashion, two-party constructions using the ring learning with errors problem as a base can be found in Ding et al. (2019a). Finally, in a paper presented at PKC 2018, Benhamouda et al. (2018) refine prior work by Katz and Vaikuntanathan (2009) to obtain a very strong type of smooth projective hash functions over lattices. As a byproduct, they present a one-round two-party password-authenticated key establishment.
Group constructions. Already Ding et al. (2012) gave a proposal for mimicking Diffie-Hellman constructions for key exchange using different variants of the learning with errors problem. However, no security proof was provided for the group version of their protocol. Recently, in Apon et al. (2019), a constant-round protocol for group key exchange is proposed and proven secure in a passive scenario. Using a post-quantum signature scheme this construction can be made secure in the presence of active adversaries, by means of a well known compiler from Katz and Yung (see Katz and Yung, 2007). This construction adapts to the Ring-LWE scenario a well known circular design introduced by Burmester and Desmedt (2005). While being a major contribution, this proposal carries over many of the hardships of a lattice-based construction; in particular, a bound on the number of maximum parties the protocol may support for both correctness and security (depending on the ring, the noise distributions and the security parameters). Finally, here the (unfortunately, only theoretical) work of Boneh et al. (2018) should be mentioned, where first steps towards a post-quantum secure group key establishment construction based on isogenies are taken.
Going from 2-party to group. Instead of using a direct design like ours, one possible approach for deriving group key establishment with some security guarantees in the presence of a quantum adversary is to use the compiler of Abdalla et al. (2007) from a secure two-party construction. However, complexity drawbacks of a post-quantum authentication method can make such a construction rather inefficient. As it is password-based, a compiled protocol from the two-party PAKE of Benhamouda et al. (2018) will not be hindered by this, while due to the (rather sophisticated) tools used in this construction, a thorough analysis would be needed to be able to understand the efficiency of such a design. For other two-party schemes, such as the one presented in Bindel et al. (2018, Section 4), it is the round-efficiency where our construction surpasses this compiling approach.
Our contribution
In this work we focus on a scenario that tries to capture today’s reality: Participants engage in a $\mathsf{GAKE}$ execution today, assuming no quantum-adversary is present, and establish a common secret key that should remain secure even if, in the future, an adversary eventually obtains access to quantum computing capabilities. We adapt the (by now standard) security model for $\mathsf{GAKE}$ to capture this kind of evolution of adversarial capabilities, and put forward a protocol design that can be proven secure in this model. Our proposal uses password-based authentication and builds on rather non-expensive primitives: a message authentication code and a post-quantum key encapsulation mechanism.
2 Model
Our modelling and construction follow the approach of recent work by Bindel et al. for signature schemes (Bindel et al., 2017) and KEMs (Bindel et al., 2018), who consider security against adversaries with different levels of quantum-computing capabilities over time. Our adversaries will be merely classical during the protocol run, but may take advantage of quantum computing once the execution under attack is finished and accepted by the involved participant. Users are modelled as probabilistic polynomial time (ppt) Turing machines. We build on classical models for group key establishment as introduced in Bellare and Rogaway (1994), Bellare et al. (2000), Bresson et al. (2001). The potential set of users $\mathcal{U}$ is assumed to be of polynomial size (in the security parameter ${1^{\ell }}$), and each user $U\in \mathcal{U}$ may execute a polynomial number of protocol instances concurrently. To refer to instance ${s_{i}}$ of a user ${U_{i}}\in \mathcal{U}$ we use the notation ${\Pi _{i}^{{s_{i}}}}$ ($i\in \mathbb{N}$).
Protocol instances. A single instance ${\Pi _{i}^{{s_{i}}}}$ can be taken for a process executed by ${U_{i}}$. To each instance we assign seven variables:
For more details on the usage of the variables we refer to Bellare et al. (2000).
${\mathsf{used}_{i}^{{s_{i}}}}$
indicates whether this instance is or has been used for a protocol run. The ${\mathsf{used}_{i}^{{s_{i}}}}$ flag can only be set through a protocol message received by the instance due to a call to the $\mathsf{Execute}$- or the $\mathsf{Send}$-oracle (see below);
${\mathsf{state}_{i}^{{s_{i}}}}$
keeps the state information needed during the protocol execution;
${\mathsf{term}_{i}^{{s_{i}}}}$
shows if the execution has terminated;
${\mathsf{sid}_{i}^{{s_{i}}}}$
denotes a possibly public session identifier that can serve as identifier for the session key ${\mathsf{sk}_{i}^{{s_{i}}}}$;
${\mathsf{pid}_{i}^{{s_{i}}}}$
stores the set of identities of those users that ${\Pi _{i}^{{s_{i}}}}$ aims at establishing a key with—including ${U_{i}}$ himself;2
${\mathsf{acc}_{i}^{{s_{i}}}}$
indicates if the protocol instance was successful, i.e. the user accepted the session key;
${\mathsf{sk}_{i}^{{s_{i}}}}$
stores the session key once it is accepted by ${\Pi _{i}^{{s_{i}}}}.$ Before acceptance, it stores a distinguished null value.
Communication network. Arbitrary point-to-point (peer-to-peer) connections among the users are assumed to be available. Thus, the network topology is that of a complete graph. We assume the network to be non-private, however, and fully asynchronous. More specifically, it is controlled by the adversary, who may alter, delay, insert, and delete messages at will.
Adversarial capabilities. Our adversaries are only capable of executing tasks in probabilistic polynomial time, and they are restricted to classical algorithms. The capabilities of an adversary $\mathcal{A}$ are made explicit through a number of oracles allowing $\mathcal{A}$ to communicate with protocol instances run by the users, and we use an oracle to capture future quantum capabilities of $\mathcal{A}$:
$\mathsf{Send}({U_{i}},{s_{i}},M)$
This sends message M to the instance ${\Pi _{i}^{{s_{i}}}}$ and returns the reply generated by this instance. If $\mathcal{A}$ queries this oracle with an unused instance ${\Pi _{i}^{{s_{i}}}}$ and M being the string “$\mathsf{Start}$”, the ${\mathsf{used}_{i}^{{s_{i}}}}$-flag is set, and the initial protocol message of ${\Pi _{i}^{{s_{i}}}}$ is returned.
$\mathsf{Execute}(\{{\Pi _{{u_{1}}}^{{s_{{u_{1}}}}}},\dots ,{\Pi _{{u_{\mu }}}^{{s_{{u_{\mu }}}}}}\})$
This executes a complete protocol run among the specified unused instances of the respective users. The adversary obtains a transcript of all messages sent over the network. A query to the $\mathsf{Execute}$ oracle is supposed to reflect a passive eavesdropping. In particular, no online-guess for the secret password can be implemented with this oracle.
$\mathsf{Reveal}({U_{i}},{s_{i}})$
yields the session key ${\mathsf{sk}_{i}^{{s_{i}}}}$ along with its corresponding session identifier ${\mathsf{sid}_{i}^{{s_{i}}}}$.
$\mathsf{Test}({U_{i}},{s_{i}})$
Only one query of this form is allowed for an active adversary $\mathcal{A}$. Provided that ${\mathsf{sk}_{i}^{{s_{i}}}}$ is defined, (i.e. ${\mathsf{acc}_{i}^{{s_{i}}}}=\mathsf{true}$ and ${\mathsf{sk}_{i}^{{s_{i}}}}\ne \text{NULL}$), $\mathcal{A}$ can execute this oracle query at any time when being activated. Then with probability 1/2 the session key ${\mathsf{sk}_{i}^{{s_{i}}}}$ and with probability 1/2 a uniformly chosen random session key is returned.
$\mathsf{Corrupt}({U_{i}})$
This oracle returns all long-term secrets held by user ${U_{i}}$ (e.g. a password or static keys for an authentication mechanism). The $\mathsf{Corrupt}$-oracle’s only purpose is to model forward secrecy.
$\mathsf{QCom}(c)$
This oracle is used to capture future quantum computation abilities. It accepts a polynomial-size description c (a quantum circuit) of a quantum computation that can be executed in polynomial time, e.g. computing a discrete logarithm. The oracle returns a classical value, representing the result of the specified quantum computation.
2.1 Correctness, Integrity and Secrecy
Before we define correctness, integrity, and secrecy, we introduce partnering to express which instances are associated in a common protocol session.
Partnering. We adopt the notion of partnering from Bohli et al. (2007). Namely, we refer to instances ${\Pi _{i}^{{s_{i}}}}$, ${\Pi _{j}^{{s_{j}}}}$ as being partnered if both ${\mathsf{sid}_{i}^{{s_{i}}}}={\mathsf{sid}_{j}^{{s_{j}}}}$ and ${\mathsf{acc}_{i}^{{s_{i}}}}={\mathsf{acc}_{j}^{{s_{j}}}}=\mathsf{true}$.
To avoid trivial cases, we assume that an instance ${\Pi _{i}^{{s_{i}}}}$ always accepts the session key constructed at the end of the corresponding protocol run if no deviation from the protocol specification occurs. Moreover, all users in the same protocol session should come up with the same session key, and we capture this in the subsequent notion of correctness.
Correctness. We call a group key establishment protocol $\mathcal{P}$ correct, if in the presence of a passive adversary $\mathcal{A}$—i.e. $\mathcal{A}$ must not use the $\mathsf{Send}$ oracle—the following holds: for all $i,j$ with both ${\mathsf{sid}_{i}^{{s_{i}}}}={\mathsf{sid}_{j}^{{s_{j}}}}$ and ${\mathsf{acc}_{i}^{{s_{i}}}}={\mathsf{acc}_{j}^{{s_{j}}}}=\mathsf{true}$, we have ${\mathsf{sk}_{i}^{{s_{i}}}}={\mathsf{sk}_{j}^{{s_{j}}}}\ne $null.
Key integrity. Correctness takes only passive attacks into account, whereas key integrity does not restrict the adversary’s oracle access: a correct group key establishment protocol fulfills key integrity, if with overwhelming probability all instances of users that have accepted with the same session identifier ${\mathsf{sid}_{j}^{{s_{j}}}}$ hold identical session keys ${\mathsf{sk}_{j}^{{s_{j}}}}$.
Next, for detailing the security definition, we will have to specify under which conditions a $\mathsf{Test}$-query may be executed.
Freshness. A $\mathsf{Test}$-query should only be allowed to those instances holding a key that is not for trivial reasons known to the adversary. To this aim, an instance ${\Pi _{i}^{{s_{i}}}}$ is called fresh in case none of the events below occurred:
As usual, the idea is that revealing a session key from an instance ${\Pi _{i}^{{s_{i}}}}$ trivially yields the session key of all instances partnered with ${\Pi _{i}^{{s_{i}}}}$, and hence this kind of “attack” will be excluded in the security definition. Similarly, if an adversary eventually succeeds in corrupting a legitimate group member and controls him fully while the protocol is being executed, he will of course know the resulting session key, and that situation is also excluded through our freshness definition. Further, this definition formalizes our exclusion of on-line quantum attacks; namely, we also restrict $\mathsf{Test}$ queries to those sessions for which no quantum process has been executed during the actual protocol run.
-
• A $\mathsf{Corrupt}({U_{j}})$ query is executed before a query of the form $\mathsf{Send}({U_{k}},{s_{k}},\ast )$ takes place. (One could consider to restrict to ${U_{j}},{U_{k}}\in {\mathsf{pid}_{i}^{{s_{i}}}}$, but as indicated in footnote 2, ${\mathsf{pid}_{i}^{{s_{i}}}}=\mathcal{U}$ is the only case of interest.)
-
• A $\mathsf{Send}$ query is performed, after a $\mathsf{QCom}$ query took place.
-
• A $\mathsf{Reveal}({U_{j}},{s_{j}})$ query is executed with ${\Pi _{i}^{{s_{i}}}}$ and ${\Pi _{j}^{{s_{j}}}}$ being partnered.
In our construction we will focus on password-based authentication. Thus, we must assume users select their passwords from a given public dictionary $\mathcal{D},$ of polynomial size in the security parameter ℓ. Groups are as a result defined by a set of users which use the same password in $\mathcal{D}$ for authentication. The security goal aimed at is defined in terms of the advantage ${\mathsf{Adv}_{\mathcal{A}}}$ of an adversary $\mathcal{A}$ in attacking protocol $\mathcal{P}$. This advantage is a function in the security parameter ℓ, defined as
Here $\mathsf{Succ}$ is the probability that the adversary queries $\mathsf{Test}$ on a fresh instance ${\Pi _{i}^{{s_{i}}}}$ and guesses correctly the bit b used by the $\mathsf{Test}$ oracle in a moment when ${\Pi _{i}^{{s_{i}}}}$ is still fresh.
Definition 1.
A group key exchange protocol $\mathcal{P}$ provides quantum-future key secrecy, if for every dictionary $\mathcal{D}$ and every ppt adversary $\mathcal{A}$ querying the $\mathsf{Send}$-oracle with at most q different protocol instances, the following inequality holds for some negligible function $\mathrm{negl}(\ell )$:
where ℓ is the security parameter and ε is a function which is at most linear in $q.$
Remark 1.
The above definition follows the standard approach in password authenticated key exchange, where typically the function ε is a constant multiple of $\frac{q}{|\mathcal{D}|}$ plus some negligible term (thus, it is assumed that passwords are chosen uniformly at random from the dictionary and that the adversary can test a constant number of passwords on each $\mathsf{Send}$-query).
3 Tools
Our construction invokes two well-studied cryptographic primitives: a key encapsulation mechanism (KEM) and a message authentication code (MAC). We use them in a black-box way, in the sense that specific details of the primitives do not affect our security claims, as long as the required security properties are fulfilled. The KEM needs to be resistant against quantum adversaries and NIST’s ongoing standardization effort offers various candidates (National Institute of Standards and Technology, 2019), whose security relies on the intractability of several families of mathematical problems. For instance, CRYSTALS-Kyber (Bos et al., 2018), Frodo (Bos et al., 2016), NewHope (Alkim et al., 2016) or NTRU Prime (Bernstein et al., 2017b) are lattice-based KEMs, BIKE (Aragon et al., 2017) or Classic McEliece (Bernstein et al., 2017a) are code-based, while SIKE (Azarderakhsh et al., 2017) is an isogeny-based proposal. On the other hand, for the choice of the MAC one can rely on a popular construction like Poly1305 (Bernstein, 2005).
3.1 Key Encapsulation Mechanisms
Key encapsulation mechanisms are public key algorithms suited for the generation and transfer of a high entropy key for later use. To achieve this, first, a pair of keys is generated, one of them being public while the other must be kept secret. Any entity holding the public key is able to run an encapsulation algorithm, which outputs a fresh, high entropy, key and a ciphertext which “encapsulates” it. The user holding the secret key can, upon reception of this ciphertext, run a decapsulation algorithm, which outputs the same fresh key, shared, from that moment, between both users.
More formally, a key encapsulation mechanism (KEM) is a triple of algorithms $\mathcal{K}=(\mathcal{K}.\mathsf{KeyGen},\mathsf{Encaps},\mathsf{Decaps})$, where:
A KEM $\mathcal{K}$ is correct if for all $(pk,sk)\gets \mathcal{K}.\mathsf{KeyGen}({1^{\ell }})$ and $(c,k)\gets \mathsf{Encaps}(pk,{1^{\ell }})$, we have $\mathsf{Decaps}(sk,c,{1^{\ell }})=k$.
-
• The probabilistic key generation algorithm $\mathcal{K}.\mathsf{KeyGen}({1^{\ell }})$ takes as input the security parameter and outputs a key pair $(pk,sk)$.
-
• The probabilistic encapsulation algorithm $\mathsf{Encaps}(pk,{1^{\ell }})$ takes as input a public key $pk$ and outputs a ciphertext c and a key $k\in {\{0,1\}^{p(\ell )}}$, where $p(\ell )$ is a polynomial function of the security parameter.
-
• The deterministic decapsulation algorithm $\mathsf{Decaps}(sk,c,{1^{\ell }})$ takes as input a secret key $sk$ and a ciphertext c and outputs a key k or ⊥.
As a security requirement, we adopt IND-CPA security against fully quantum adversaries from Bindel et al. (2017). This intuitively means that any eavesdropper, that may have access to quantum computation, is unable to obtain any information about the shared fresh key, which is, from its point of view, indistinguishable from a key chosen uniformly at random from the key space. In more detail, an IND-CPA experiment is defined, where a challenger $\mathcal{C}$ generates $(pk,sk)\gets \mathcal{K}.\mathsf{KeyGen}({1^{\ell }})$ and $({c^{\ast }},{k_{0}^{\ast }})\gets \mathsf{Encaps}(pk,{1^{\ell }})$, chooses uniformly at random a key ${k_{1}^{\ast }}\in {\{0,1\}^{p(\ell )}}$ and a bit $b\in \{0,1\}$. Then the adversary $\mathcal{A}$, which is treated as a quantum algorithm, is given $(pk,{c^{\ast }},{k_{b}^{\ast }})$ and produces an output ${b^{\prime }}\in \{0,1\}$ as the guess for b. With ${\mathsf{Succ}_{\mathcal{A}}}$ being the probability that $\mathcal{A}$’s output equals b, we define ${\mathsf{Adv}_{\mathcal{A},\texttt{KEM}}}:=|2\cdot {\mathsf{Succ}_{\mathcal{A}}}-1|$ and say that the KEM is IND-CPA secure against fully quantum adversaries if for every polynomial-time bounded ${\mathsf{Adv}_{\mathcal{A},\texttt{KEM}}}$, the advantage ${\mathsf{Adv}_{\mathcal{A},\texttt{KEM}}}$ is negligible.
3.2 Message Authentication Codes
A message authentication code is a symmetric key primitive whose purpose is to preserve information integrity. To achieve this, whenever two users holding the same secret key wish to communicate, the one sending the message produces an authentication tag computed from the message and the secret key. When the other user receives the message together with the tag, the secret key allows him to check the validity of the tag with respect to the message. This procedure protects against an adversary modifying the message without being detected, because if the MAC is secure he will be unable to produce a valid tag for any different message.
More formally, a message authentication code (MAC) (Dodis et al., 2012) is a triple of algorithms $\mathcal{M}=(\mathcal{M}.\mathsf{KeyGen},\mathsf{Tag},\mathsf{Vf})$ where:
-
• The probabilistic key generation algorithm $\mathcal{M}.\mathsf{KeyGen}({1^{\ell }})$ takes as input the security parameter and outputs a key $k\in {\{0,1\}^{m(\ell )}}$ for a suitable polynomial $m(\ell )$.3
-
• The probabilistic authentication algorithm $\mathsf{Tag}(k,M)$ takes as input a key k and a message M and outputs a tag t.
-
• The deterministic verification algorithm $\mathsf{Vf}(k,M,t)$ takes as input a key k, a message M and a tag t and outputs a decision: 1 (accept) or 0 (reject).
The standard security notion for a MAC is unforgeability under chosen message and chosen verification queries attack (UF-CMVA) (Dodis et al., 2012). This essentially means that an adversary cannot produce a valid tag for a message of his choice, even if he has access to tags of other messages of his choice and is able to check validity of pairs message-tag (via the so called verification oracle). To formally capture this notion, an experiment is defined where a challenger $\mathcal{C}$ generates $k\gets \mathcal{M}.\mathsf{KeyGen}({1^{\ell }})$ and the adversary $\mathcal{A}$ is granted oracle access to $\mathsf{Tag}(k,\cdot )$ and $\mathsf{Vf}(k,\cdot ,\cdot )$. The adversary wins if $\mathcal{A}$ makes a query $({M^{\ast }},{t^{\ast }})$ to $\mathsf{Vf}(k,\cdot ,\cdot )$ such that the output is 1 and ${M^{\ast }}$ has not been queried to $\mathsf{Tag}(k,\cdot )$. The MAC is said to be UF-CMVA secure if for all ppt adversaries $\mathcal{A}$, the probability ${\mathsf{Succ}_{\mathcal{A}}}$ of the adversary winning the previous experiment is negligible in the security parameter ℓ.
If $\mathsf{Tag}$ is a deterministic algorithm, then $\mathsf{Vf}$ does not need to be explicitly defined, since it is specified by $\mathsf{Vf}(k,M,t)=1$ if and only if $\mathsf{Tag}(k,M)=t$.
3.3 Deterministic Randomness Extraction
In the protocol to be discussed in Section 4, we use a prime order group G in which the Decision-Diffie-Hellman assumption holds, and from (uniform random) elements in G, we want to extract (uniform random) bit-strings. To realize this without the introduction of additional technical machinery or a random oracle, work in Chevassut et al. (2006) comes in handy. Specifically, if we let G be the group of quadratic residues in ${\mathbb{Z}_{2|G|+1}^{\times }}$ with a Sophie-Germain prime $|G|$ close to a power of 2, simple truncation of the binary representation is an efficient extractor (Chevassut et al., 2006, Section 3.2). Subsequently, for a (uniform random) group element $g\in G$, we denote by $[g]$ (statistically close to uniform random) bits extracted deterministically from g. When extracting two independent (half-length) bit-strings from g, we take $[g]={[g]_{L}}||{[g]_{R}}$ as concatenation of two (half length) bit-strings.
Remark 2.
An elegant and more efficient approach to randomness extraction, which enables the use of elliptic curves over prime fields ${\mathbb{F}_{p}}$ with p being close to a power of 2, is provided by Chevassut et al.’s Twist-AUgmented (TAU) technique. When trying to optimize the performance of the protocol below, a possible adoption of the TAU approach is natural to explore. Similar to Chevassut et al. (2006, Fig. 1) one could—at the bandwidth cost of essentially two parallel Diffie-Hellman executions—try to work on a curve and its twist simultaneously, eventually leveraging the message authentication code to select the correct protocol outcome.
4 The Proposed Protocol
Let $\mathcal{D}$ be the (polynomial-size) password dictionary, and let G be a group of prime order q. We assume that $\mathcal{D}\subseteq G$ through some public and efficiently computable injection $\mathcal{D}\hookrightarrow G$. For instance, if $G=\langle g\rangle $ is the group of quadratic residues in ${\mathbb{Z}_{2|G|+1}}$ with a Sophie-Germain prime $|G|$, we can identify the binary representation of (length-restricted) passwords with elements in ${\mathbb{Z}_{|G|}}$, and then map passwords uniquely into G by raising the generator g to the appropriate power.4 Finally, let ℓ denote the security parameter and $p(\ell )$ denote the bit-length of session keys. We impose a Decisional Diffie Hellman assumption as follows:
Assumption 1 (Decisional Diffie Hellman for $(G,\mathcal{D})$).
Let G be a finite group of prime order and $\mathcal{D}$ a dictionary with an efficient injection $\iota :\mathcal{D}\hookrightarrow G$. Then, the Decisional Diffie Hellman assumption for $(G,\mathcal{D})$ states that, for every $g\in \iota (\mathcal{D})$, the probability distributions $({g^{a}},{g^{b}},{g^{ab}})$ for $(a,b)\gets {\mathbb{Z}_{|G|}^{2}}$ and $({g^{a}},{g^{b}},h)$ for $(a,b,h)\gets {\mathbb{Z}_{|G|}^{2}}\times G$ are computationally indistinguishable. In other words, no ppt algorithm can tell them apart with non-negligible probability in the security parameter ℓ.
4.1 Protocol Specification
Let ${U_{0}},{U_{1}},\dots ,{U_{n}}$ be the users running the protocol and assume they share password $\mathsf{pw}$. Further, we will assume that every user is aware of his index and the indices of the rest of participants. Our construction is depicted in Fig. 1, while in Fig. 2 we give a somewhat simplified description for the case of four users.
The basic idea is a simple key transport from ${U_{0}}$ to all the other parties, with the actual session key k being masked (for each of them) with an ephemeral key obtained from the key encapsulation. To ensure (password-based) authentication, in parallel each user establishes a Diffie-Hellman key with ${U_{0}}$, with the shared password fixing a generator for the Diffie-Hellman group. The latter keys are used to compute “after the fact” authentication tags on protocol messages. Once a player is convinced that all protocol messages are legitimate, the session key is accepted. More precisely:
-
• In Round I, ${U_{0}}$ broadcasts a group element, ${g_{0}}$, obtained as an encoding of his password, which is his “Diffie-Hellman contribution” for the authentication tags. Any other user ${U_{i}}$ broadcasts similarly a group element ${g_{i}},$ and his freshly generated public key $p{k_{i}}$ for the key encapsulation mechanism.
-
• In Round II, user ${U_{0}}$ generates for each user ${U_{j}}$ a KEM key, and masks with it a (freshly chosen for each run) bitstring k (which will eventually be the session key). This message is authenticated using a bit-string extracted from ${g_{0,j}}$. Furthermore, users also broadcast confirmation tags pairwise. Namely, ${U_{i}}$ and ${U_{j}}$ extract two different MAC keys from the shared element ${g_{i,j}}$, that is, ${U_{i}}$ uses ${[{g_{i,j}}]_{L}}$ for users “on his left” (i.e. for $j>i$) and ${[{g_{i,j}}]_{R}}$ for users “on his right” ($i<j$).
-
• Finally, all tags are checked, and if they are successful then each ${U_{i}}$ ($i>0$) decapsulates the bitstring k and extracts from it the session key and its corresponding session identifier. Note that if a user ${U_{i}}$ is inserting an invalid password, the two party Diffie Hellman key ${g_{i,j}}$ he will be able to construct will (with overwhelming probability) not match the one constructed by ${U_{j}}$, hence it will be detected as a tag-mismatch.
Remark 3.
Note that our solution is not contributory (for ${U_{0}}$ fully determines the session key established by the execution). Still, as it often happens in this type of construtions users are assumed to be honest and thus the security definition does not impose that all parties influence the value of the session key. Moreover, if a contributory solution is preferred, one could, e.g. deterministically extract random bits from the ${g_{i}}$-values in Round I, and exclusive-or these with the session key.
The following theorem establishes security of the proposed protocol in the sense of Definition 1. In our formal analysis, the fact that legitimate users are authenticated as such comes from the strength of the MAC, as can be seen in Game 1 in the proof below. Note also that MAC keys are generated using passwords as fresh inputs for Diffie-Hellman exponents, thus we also take into account the probability of a password guess and the hardness of the Decisional Diffie Hellman problem in our reduction. Further, note that the session key is freshly generated (uniformly at random) by ${U_{0}}$ on each execution (in the proof, this results in the fact that Game 1 and Game 2 are indistinguishable unless the security of the underlying KEM is compromised).
Theorem 1.
The protocol described in Fig. 1 achieves quantum-future key secrecy, under the Decisional Diffie Hellman Assumption in $(G,\mathcal{D})$ and assuming it is instantiated with a UF-CMVA-secure message authentication code and an IND-CPA-secure (post-quantum) key encapsulation mechanism.
Proof.
The proof is set up in terms of several experiments or games, where a challenger interacts with the adversary confronting it with a counterfeit $\mathsf{Test}$-challenge in the spirit of the key secrecy definition from Section 2. We denote with $\mathsf{Adv}(\mathcal{A},{G_{i}})$ the advantage of adversary $\mathcal{A}$ in the i-th game ${G_{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}$. This game is identical to ${G_{0}}$, except from the fact that it aborts with an adversarial win if $\mathcal{A}$ succeeds in producing a valid MAC for a message he has constructed (i.e. which is adversarially-generated) in Round II. There are two cases we should distinguish:
Game $\mathbf{2}$. In this game the output of the $\mathsf{Execute}$ and $\mathsf{Send}$ oracles are modified as follows. For each $j\in \{1,\dots ,n\}$, the value ${d_{j}}$ is replaced with ${d_{j}^{\ast }}$ selected u.a.r. from ${\{0,1\}^{p(\ell )}}$. Then, for the computation of each tag ${t_{0,j}}$, ${m_{0,i}}$ is replaced with ${m_{0,i}^{\ast }}:=({d_{i}^{\ast }},{c_{i}})$ for $i=1,\dots ,n$. Note that ${d_{i}}$ is the XOR of k and the output ${k_{i}}$ of $\mathsf{Encaps}$ and that k is chosen u.a.r. by ${U_{0}}$ and only used in the computation of the values ${d_{i}}$ throughout a protocol run.
Case 1: no ${\bf\sf QCom}$ queries called by $\pmb{\mathcal{A}}$
At this, we can argue that the tags ${t_{i,j}}$ can be replaced with bitstrings of the correct length chosen uniformly at random. Indeed, we may modify the $\mathsf{Execute}$ and $\mathsf{Send}$ oracle in such a way that all values ${g_{i}}$ from Round I are replaced with ${g_{i}^{\ast }}$ chosen u.a.r. from G. The games ${G_{0}}$ and ${G_{1}}$ can only be distinguished one from the other if:
Indeed, as the group elements ${g_{i}}$ have been chosen uniformly at random, the MAC keys derived in Round II are also uniformly at random selected bitstrings. Thus we have,
-
• $\mathcal{A}$ correctly guesses $\mathsf{pw}$ and sends a properly computed value ${g_{i}}={\mathsf{pw}^{{\beta _{i}}}}$ to an instance of ${U_{j}}$ on behalf of an instance of ${U_{i}}$. If this is the case, $\mathcal{A}$ may correctly verify the tag ${t_{j,i}}$ he gets from ${U_{j}}$ in ${G_{0}}$ while the verification will be unsuccessful in ${G_{1}}$.
-
• $\mathcal{A}$, not using $\mathsf{QCom}$ checks offline, for each password in the dictionary $\mathcal{D},$ whether the triplets $({g_{i}},{g_{j}},{t_{i,j}})$ are all consistent for a fixed password. It is easy to see that if $\mathcal{A}$ can actually check whether such triplets $({g_{i}},{g_{j}},{t_{i,j}})$ are consistent with a given password $p{w^{\ast }}$, the corresponding Decisional Diffie Hellman assumption in $(G,\mathcal{D})$ cannot hold. Indeed, we may construct an adversary $\mathcal{B}$ using $\mathcal{A}$ in order to solve a corresponding Decisional Diffie Hellman challenge in $(G,\mathcal{D})$. Let $(g,x,y,z)$ be the input to $\mathcal{B}.$ In order to tell whether order to distinguish whether that is a triplet of the form $({g^{a}},{g^{b}},{g^{ab}})$ or z is a randomly generated element in G, $\mathcal{B}$ presents $\mathcal{A}$ with a simulated transcript (using the password encoding by g for authentication) where for a certain pair of users ${U_{i}},{U_{j}}$ the authenticated tags ${t_{i,j}}$ and ${t_{j,i}}$ are constructed from $z.$
Case 2: $\pmb{\mathcal{A}}$ queried ${\bf\sf QCom}$ after ${\bf\sf Execute}$ or ${\bf\sf Send}$
If the $\mathsf{QCom}$ oracle calls are only restricted as stated in the freshness definition, indeed it may be the case that the MAC keys are known to the adversary who has queried $\mathsf{QCom}$; however, as he is not allowed making any $\mathsf{Send}$ query, he will of course not produce any valid forgery, as a result, only Case 1 is to be taken into account when bounding the distinguishing probability of $\mathcal{A}$
\[ |\mathsf{Adv}(\mathcal{A},{G_{1}})-\mathsf{Adv}(\mathcal{A},{G_{0}})|\leqslant \varepsilon (\ell ,q)+{\mathsf{Adv}_{DDH}}(G,\mathcal{D}).\]
Given that all MAC keys are at this point generated uniformly at random, this can only happen if $\mathcal{A}$ is able to produce a forgery for the MAC in use, and thus
\[ \mathsf{Adv}(\mathcal{A},{G_{1}})=\mathsf{Adv}(\mathcal{A},{G_{0}})\leqslant {\mathsf{Succ}_{\mathcal{A}}},\]
where ${\mathsf{Succ}_{\mathcal{A}}}$ is the probability of an adversary winning in the UF-CMVA game described in Section 3, hence assumed to be negligible in ℓ.To argue that the only way an adversary is able to distinguish between ${G_{1}}$ and ${G_{2}}$ is breaking the IND-CPA security of the KEM, we depict how an IND-CPA adversary $\mathcal{B}$ for the KEM can be constructed from an adversary $\mathcal{A}$ who may distinguish between the two games.
Indeed, suppose we actually introduce the change in ${G_{1}}$ step by step. Let $\mathcal{A}$ be an adversary distinguishing between ${G_{1}}$ and the game resulting after step 1. Now, let $\mathcal{B}$ be presented with an IND-CPA challenge for the KEM used by user ${U_{1}}$, i.e. with a value $(KEY,C)$ where $KEY$ is either a key encapsulated in C using $p{k_{1}}$ or a string chosen uniformly at random. Now, fixing a session key k, fairly produce messages from Round I for each user $({d_{i}},{c_{i}})$ for $i=1,\dots ,n$ and replace ${m_{0,l}}$ by ${m_{0,l}^{\ast }}=(KEY\oplus k,C),$ while, for the rest, follow the protocol description. Now, if $KEY$ comes from the KEM, all messages will follow the protocol specification, while if it is selected uniformly at random indeed $KEY\oplus k$ will also be. As a result, if $\mathcal{A}$ distinguishes between ${G_{1}}$ and ${G_{2}}$ he will violate the IND-CPA security of the KEM, so indeed, replicating this argument in a step by step fashion we have
\[ \big|\mathsf{Adv}(\mathcal{A},{G_{2}})-\mathsf{Adv}(\mathcal{A},{G_{1}})\big|\leqslant {\mathsf{Adv}_{\mathcal{A},\texttt{KEM}}}.\]
Now note that no information correlated with the actual session key is involved in any message at this point; clearly we have $\mathsf{Adv}(\mathcal{A},{G_{2}})=0$, which concludes the proof. □Remark 4.
Note that in the above proof it is crucial to restrict the $\mathsf{QCom}$ calls in the definition of freshness; otherwise an offline-guessing strategy can be mounted by solving the corresponding Diffie-Hellman instances $(pw,p{w^{{\beta _{i}}}},p{w^{{\beta _{j}}}})$ for every $pw\in \mathcal{D},$ and confronting the result with the messages tagged with ${t_{i,j}},$ i.e. a quantum adversary may get the password from the transcript and thus we should make clear we do not allow for subsequent $\mathsf{Send}$ calls once $\mathsf{QCom}$ has been queried.
4.2 Performance
Let us compare the performance of the above protocol with two state-of-the-art fully post-quantum solutions for group key establishment (Apon et al., 2019; Persichetti et al., 2019). For clarity, we assume that the number of users is $n+1$ for every protocol. Table 1 summarizes important characteristics.
In the table we also included a column on the authentication tools used – differing from the other mentioned protocols, we opted for password-based authentication and do not assume a PKI for signatures. In terms of performance, the reduced number of rounds in our protocol is attractive. Compared to PSS, we pay a cost for the MAC tag computations and transmissions, but, as we do not involve a PKI to handle signatures and MAC computations tend to be fast, this cost seems quite reasonable.
-
• Our protocol. In the first round, $n+1$ elements of G and n public keys of the KEM are broadcast, yielding a total of ${n^{2}}+n$ elements of G and ${n^{2}}$ public keys to be transmitted. In the second round, ${n^{2}}$ tags, n KEM ciphertexts, and n masked ephemeral keys are sent.
-
• Apon et al. (2019). This scheme provides security against passive adversaries. In order to transform it into a $\mathsf{GAKE}$, the authors propose using the Katz-Yung compiler (Katz and Yung, 2007), which adds one round of communication (in which each participant broadcasts a nonce), and appends one signature to every sent message that should be taken into account. In the setup, a ring ${R_{\hat{q}}}={\mathbb{Z}_{\hat{q}}}[X]/({X^{\hat{n}}}+1)$ is fixed, where $\hat{q}$ is a prime and $\hat{n}$ is a power of 2 such that $\hat{q}\equiv 1\hspace{0.2em}\mathrm{mod} \hspace{0.2em}2\hat{n}$. In the first two rounds, each user broadcasts an element of ${R_{\hat{q}}}$, for a total of $2({n^{2}}+n)$ elements. In the third round, each user runs the key recovery algorithm to get a pair $(\hat{K},\hat{k})$ and broadcasts $\hat{K}$.
-
• Persichetti et al. (2019). This scheme is also a compiler which invokes a KEM and a signature scheme. In the first round, each user sends a KEM public key to his right neighbour, while in the second one, each user sends a KEM ciphertext to his left neighbour. Finally, in the third round each user broadcasts a masked ephemeral key and a signature.
Table 1
| Rounds | Communication | Computation | Authentication | |
| Here | 2 | ${n^{2}}+n$ elements in G, | $2(n+1)$ exp. in G, | Password+ |
| ${n^{2}}$ KEM public keys, | n key enc. and dec., | MAC | ||
| ${n^{2}}$ MAC tags, | ${n^{2}}+n$ MAC tags | |||
| n KEM-encapsulated keys, | ||||
| n masked ephem. keys | ||||
| ADGK | 3 | $2({n^{2}}+n)$ ${R_{\hat{q}}}$-elements, | $2{(n+1)^{2}}$ ops. in ${R_{\hat{q}}}$, | Unauthent. |
| ${n^{2}}+n$ elements in the | $2n$ key rec. calls | |||
| output space of the key | ||||
| reconciliation algorithm | ||||
| ADGK† | 4 | As in ADGK, plus | As above, plus | PKI+ |
| $n+1$ nonces and | $3({n^{2}}+n)$ sign. | Signature | ||
| $3({n^{2}}+n)$ signatures | ||||
| PSS | 3 | n KEM public keys, | n key enc. and dec., | PKI+ |
| n KEM-encapsulated keys, | n sign. | Signature | ||
| ${n^{2}}+n$ masked ephem. keys | ||||
| ${n^{2}}+n$ signatures |
5 Final Remarks
We present in this work a group key exchange that can be proven secure in the sense of Definition 1. As we only consider quantum adversaries to be active once the protocol execution has ended, and, moreover, our building blocks are very simple tools, we accomplish a clean and efficient design. It is indeed worth exploring other approaches towards thwarting general quantum attacks. A promising avenue is to investigate the viability of a compiled construction derived from applying the design sketched in Appendix C of Benhamouda et al. (2018) and the compiler from Abdalla et al. (2007). While being fully quantum resistant, such a design would involve sophisticated lattice-based primitives, for which, moreover, investigating the attained post-quantum security level is still a topic of active research.
