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

We later mimic their approach, where adversaries are modelled differently in two well-defined attack stages, where the quantum/classical capabilities may differ.

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.

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: usedisi

indicates whether this instance is or has been used for a protocol run. The usedisi flag can only be set through a protocol message received by the instance due to a call to the Execute - or the Send -oracle (see below);

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 : Send(Ui,si,M)

This sends message M to the instance Πisi and returns the reply generated by this instance. If A queries this oracle with an unused instance Πisi and M being the string “ Start ”, the usedisi -flag is set, and the initial protocol message of Πisi is returned.

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

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

In view of Definition 1, simply squaring the password pw , seen as group element, has the downside that with any incorrect guess pw′ for pw , an adversary can exclude −pw′ , too.

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.