Group Key Establishment in a Quantum-Future Scenario

1Introduction

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 ( GAKE), which are cryptographic constructions allowing a group of n⩾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 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.11

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 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 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.

2Model

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 U is assumed to be of polynomial size (in the security parameter  1ℓ), and each user U∈U may execute a polynomial number of protocol instances concurrently. To refer to instance si of a user Ui∈U we use the notation Πisi ( i∈N).

Protocol instances. A single instance Πisi can be taken for a process executed by Ui. To each instance we assign seven variables:

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 A are made explicit through a number of oracles allowing A to communicate with protocol instances run by the users, and we use an oracle to capture future quantum capabilities of A:

3Tools

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).

4The Proposed Protocol

Let D be the (polynomial-size) password dictionary, and let G be a group of prime order q. We assume that D⊆G through some public and efficiently computable injection D↪G. For instance, if G=⟨g⟩ is the group of quadratic residues in Z2|G|+1 with a Sophie-Germain prime |G|, we can identify the binary representation of (length-restricted) passwords with elements in Z|G|, and then map passwords uniquely into G by raising the generator g to the appropriate power.44 Finally, let ℓ denote the security parameter and p(ℓ) denote the bit-length of session keys. We impose a Decisional Diffie Hellman assumption as follows:

4.1Protocol Specification

Let U0,U1,…,Un be the users running the protocol and assume they share password 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 U0 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 U0, 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, U0 broadcasts a group element, g0, obtained as an encoding of his password, which is his “Diffie-Hellman contribution” for the authentication tags. Any other user Ui broadcasts similarly a group element gi, and his freshly generated public key pki for the key encapsulation mechanism.

• • In Round II, user U0 generates for each user Uj 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 g0,j. Furthermore, users also broadcast confirmation tags pairwise. Namely, Ui and Uj extract two different MAC keys from the shared element gi,j, that is, Ui uses [gi,j]L for users “on his left” (i.e. for j>i) and [gi,j]R for users “on his right” ( i<j).

• • Finally, all tags are checked, and if they are successful then each Ui ( i>0) decapsulates the bitstring k and extracts from it the session key and its corresponding session identifier. Note that if a user Ui is inserting an invalid password, the two party Diffie Hellman key gi,j he will be able to construct will (with overwhelming probability) not match the one constructed by Uj, hence it will be detected as a tag-mismatch.

Remark 3.

Note that our solution is not contributory (for U0 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 gi-values in Round I, and exclusive-or these with the session key.

Fig. 1

Proposed password-based group-key establishment.

Fig. 2

Simplified description of our protocol with four users.

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 U0 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,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 Test-challenge in the spirit of the key secrecy definition from Section 2. We denote with Adv(A,Gi) the advantage of adversary A in the i-th game Gi.

Game 0. This first game corresponds to a real attack, in which all the parameters are chosen as in the actual scheme. By definition, Adv(A,G0)=AdvA.

Game 1. This game is identical to G0, except from the fact that it aborts with an adversarial win if 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:

Case 1: no QCom queries called by A

At this, we can argue that the tags ti,j can be replaced with bitstrings of the correct length chosen uniformly at random. Indeed, we may modify the Execute and Send oracle in such a way that all values gi from Round I are replaced with gi∗ chosen u.a.r. from G. The games G0 and G1 can only be distinguished one from the other if: • A correctly guesses pw and sends a properly computed value gi=pwβi to an instance of Uj on behalf of an instance of Ui. If this is the case, A may correctly verify the tag tj,i he gets from Uj in G0 while the verification will be unsuccessful in G1. • A, not using QCom checks offline, for each password in the dictionary D, whether the triplets (gi,gj,ti,j) are all consistent for a fixed password. It is easy to see that if A can actually check whether such triplets (gi,gj,ti,j) are consistent with a given password pw∗, the corresponding Decisional Diffie Hellman assumption in (G,D) cannot hold. Indeed, we may construct an adversary B using A in order to solve a corresponding Decisional Diffie Hellman challenge in (G,D). Let (g,x,y,z) be the input to B. In order to tell whether order to distinguish whether that is a triplet of the form (ga,gb,gab) or z is a randomly generated element in G, B presents A with a simulated transcript (using the password encoding by g for authentication) where for a certain pair of users Ui,Uj the authenticated tags ti,j and tj,i are constructed from z. Indeed, as the group elements gi have been chosen uniformly at random, the MAC keys derived in Round II are also uniformly at random selected bitstrings. Thus we have, |Adv(A,G1)−Adv(A,G0)|⩽ε(ℓ,q)+AdvDDH(G,D).

Case 2: A queried QCom after Execute or Send

If the 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 QCom; however, as he is not allowed making any 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 A |Adv(A,G1)−Adv(A,G0)|⩽ε(ℓ,q)+AdvDDH(G,D). Given that all MAC keys are at this point generated uniformly at random, this can only happen if A is able to produce a forgery for the MAC in use, and thus Adv(A,G1)=Adv(A,G0)⩽SuccA, where SuccA is the probability of an adversary winning in the UF-CMVA game described in Section 3, hence assumed to be negligible in ℓ.

Game 2. In this game the output of the Execute and Send oracles are modified as follows. For each j∈{1,…,n}, the value dj is replaced with dj∗ selected u.a.r. from {0,1}p(ℓ). Then, for the computation of each tag t0,j, m0,i is replaced with m0,i∗:=(di∗,ci) for i=1,…,n. Note that di is the XOR of k and the output ki of Encaps and that k is chosen u.a.r. by U0 and only used in the computation of the values di throughout a protocol run.

To argue that the only way an adversary is able to distinguish between G1 and G2 is breaking the IND-CPA security of the KEM, we depict how an IND-CPA adversary B for the KEM can be constructed from an adversary A who may distinguish between the two games.

Indeed, suppose we actually introduce the change in G1 step by step. Let A be an adversary distinguishing between G1 and the game resulting after step 1. Now, let B be presented with an IND-CPA challenge for the KEM used by user U1, i.e. with a value (KEY,C) where KEY is either a key encapsulated in C using pk1 or a string chosen uniformly at random. Now, fixing a session key k, fairly produce messages from Round I for each user (di,ci) for i=1,…,n and replace m0,l by m0,l∗=(KEY⊕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⊕k will also be. As a result, if A distinguishes between G1 and G2 he will violate the IND-CPA security of the KEM, so indeed, replicating this argument in a step by step fashion we have

|Adv(A,G2)−Adv(A,G1)|⩽AdvA,KEM.

Now note that no information correlated with the actual session key is involved in any message at this point; clearly we have Adv(A,G2)=0, which concludes the proof.  □

Remark 4.

Note that in the above proof it is crucial to restrict the QCom calls in the definition of freshness; otherwise an offline-guessing strategy can be mounted by solving the corresponding Diffie-Hellman instances (pw,pwβi,pwβj) for every pw∈D, and confronting the result with the messages tagged with ti,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 Send calls once QCom has been queried.

Remark 5.

We stress further that for the above proof (see Game 2) it is needed to impose that the KEM in use is post-quantum, as we do not restrict the usage of QCom when trying to tell apart the “real” di′s from randomly selected ones.

5Final 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.