You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Group Key Establishment in a Quantum-Future Scenario

Abstract

In cryptography, key establishment protocols are often the starting point paving the way towards secure execution of different tasks. Namely, the parties seeking to achieve some cryptographic task, often start by establishing a common high-entropy secret that will eventually be used to secure their communication. In this paper, we put forward a security model for group key establishment ( GAKE) with an adversary that may execute efficient quantum algorithms, yet only once the execution of the protocol has concluded. This captures a situation in which keys are to be established in the present, while security guarantees must still be provided in the future when quantum resources may be accessible to a potential adversary.

Further, we propose a protocol design that can be proven secure in this model. Our proposal uses password authentication and builds upon efficient and reasonably well understood primitives: a message authentication code and a post-quantum key encapsulation mechanism. The hybrid structure dodges potential efficiency downsides, like large signatures, of some “true” post-quantum authentication techniques, making our protocol a potentially interesting fit for current applications with long-term security needs.

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

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 UU may execute a polynomial number of protocol instances concurrently. To refer to instance si of a user UiU we use the notation Πisi ( iN).

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

stateisi

keeps the state information needed during the protocol execution;

termisi

shows if the execution has terminated;

sidisi

denotes a possibly public session identifier that can serve as identifier for the session key skisi;

pidisi

stores the set of identities of those users that Πisi aims at establishing a key with—including Ui himself;2

accisi

indicates if the protocol instance was successful, i.e. the user accepted the session key;

skisi

stores the session key once it is accepted by Πisi. Before acceptance, it stores a distinguished null value.

For more details on the usage of the variables we refer to Bellare et al. (2000).

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.

Execute({Πu1su1,,Πuμsuμ})

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 Execute oracle is supposed to reflect a passive eavesdropping. In particular, no online-guess for the secret password can be implemented with this oracle.

Reveal(Ui,si)

yields the session key skisi along with its corresponding session identifier sidisi.

Test(Ui,si)

Only one query of this form is allowed for an active adversary A. Provided that skisi is defined, (i.e. accisi=true and skisiNULL), A can execute this oracle query at any time when being activated. Then with probability 1/2 the session key skisi and with probability 1/2 a uniformly chosen random session key is returned.

Corrupt(Ui)

This oracle returns all long-term secrets held by user Ui (e.g. a password or static keys for an authentication mechanism). The Corrupt-oracle’s only purpose is to model forward secrecy.

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.1Correctness, 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 Πisi, Πjsj as being partnered if both sidisi=sidjsj and accisi=accjsj=true.

To avoid trivial cases, we assume that an instance Πisi 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 P correct, if in the presence of a passive adversary A—i.e. A must not use the Send oracle—the following holds: for all i,j with both sidisi=sidjsj and accisi=accjsj=true, we have skisi=skjsjnull.

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 sidjsj hold identical session keys skjsj.

Next, for detailing the security definition, we will have to specify under which conditions a Test-query may be executed.

Freshness. A 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 Πisi is called fresh in case none of the events below occurred:

  • A Corrupt(Uj) query is executed before a query of the form Send(Uk,sk,) takes place. (One could consider to restrict to Uj,Ukpidisi, but as indicated in footnote 2, pidisi=U is the only case of interest.)

  • A Send query is performed, after a QCom query took place.

  • A Reveal(Uj,sj) query is executed with Πisi and Πjsj being partnered.

As usual, the idea is that revealing a session key from an instance Πisi trivially yields the session key of all instances partnered with Πisi, 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 Test queries to those sessions for which no quantum process has been executed during the actual protocol run.

In our construction we will focus on password-based authentication. Thus, we must assume users select their passwords from a given public dictionary 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 D for authentication. The security goal aimed at is defined in terms of the advantage AdvA of an adversary A in attacking protocol P. This advantage is a function in the security parameter , defined as

AdvA:=|2·Succ1|.
Here Succ is the probability that the adversary queries Test on a fresh instance Πisi and guesses correctly the bit b used by the Test oracle in a moment when Πisi is still fresh.
Definition 1.

A group key exchange protocol P provides quantum-future key secrecy, if for every dictionary D and every ppt adversary A querying the Send-oracle with at most q different protocol instances, the following inequality holds for some negligible function negl():

AdvA()ε(,q)+negl(),
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 q|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 Send-query).

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

3.1Key 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 K=(K.KeyGen,Encaps,Decaps), where:

  • The probabilistic key generation algorithm K.KeyGen(1) takes as input the security parameter and outputs a key pair (pk,sk).

  • The probabilistic encapsulation algorithm Encaps(pk,1) takes as input a public key pk and outputs a ciphertext c and a key k{0,1}p(), where p() is a polynomial function of the security parameter.

  • The deterministic decapsulation algorithm Decaps(sk,c,1) takes as input a secret key sk and a ciphertext c and outputs a key k or ⊥.

A KEM K is correct if for all (pk,sk)K.KeyGen(1) and (c,k)Encaps(pk,1), we have Decaps(sk,c,1)=k.

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 C generates (pk,sk)K.KeyGen(1) and (c,k0)Encaps(pk,1), chooses uniformly at random a key k1{0,1}p() and a bit b{0,1}. Then the adversary A, which is treated as a quantum algorithm, is given (pk,c,kb) and produces an output b{0,1} as the guess for b. With SuccA being the probability that A’s output equals b, we define AdvA,KEM:=|2·SuccA1| and say that the KEM is IND-CPA secure against fully quantum adversaries if for every polynomial-time bounded AdvA,KEM, the advantage AdvA,KEM is negligible.

3.2Message 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 M=(M.KeyGen,Tag,Vf) where:

  • The probabilistic key generation algorithm M.KeyGen(1) takes as input the security parameter and outputs a key k{0,1}m() for a suitable polynomial m().3

  • The probabilistic authentication algorithm Tag(k,M) takes as input a key k and a message M and outputs a tag t.

  • The deterministic verification algorithm 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 C generates kM.KeyGen(1) and the adversary A is granted oracle access to Tag(k,·) and Vf(k,·,·). The adversary wins if A makes a query (M,t) to Vf(k,·,·) such that the output is 1 and M has not been queried to Tag(k,·). The MAC is said to be UF-CMVA secure if for all ppt adversaries  A, the probability SuccA of the adversary winning the previous experiment is negligible in the security parameter .

If Tag is a deterministic algorithm, then Vf does not need to be explicitly defined, since it is specified by Vf(k,M,t)=1 if and only if Tag(k,M)=t.

3.3Deterministic 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 Z2|G|+1× 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 gG, 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 Fp 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.

4The Proposed Protocol

Let D be the (polynomial-size) password dictionary, and let G be a group of prime order q. We assume that DG through some public and efficiently computable injection DG. 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 Finally, let denote the security parameter and p() denote the bit-length of session keys. We impose a Decisional Diffie Hellman assumption as follows:

Assumption 1

Assumption 1(Decisional Diffie Hellman for (G,D)).

Let G be a finite group of prime order and D a dictionary with an efficient injection ι:DG. Then, the Decisional Diffie Hellman assumption for (G,D) states that, for every gι(D), the probability distributions (ga,gb,gab) for (a,b)Z|G|2 and (ga,gb,h) for (a,b,h)Z|G|2×G are computationally indistinguishable. In other words, no ppt algorithm can tell them apart with non-negligible probability in the security parameter .

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.

Proposed password-based group-key establishment.
Fig. 2

Simplified description of our protocol with four users.

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=(KEYk,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 KEYk 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 pwD, 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” dis from randomly selected ones.

4.2Performance

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.

  • Our protocol. In the first round, n+1 elements of G and n public keys of the KEM are broadcast, yielding a total of n2+n elements of G and n2 public keys to be transmitted. In the second round, n2 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 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 Rqˆ=Zqˆ[X]/(Xnˆ+1) is fixed, where qˆ is a prime and nˆ is a power of 2 such that qˆ1mod2nˆ. In the first two rounds, each user broadcasts an element of Rqˆ, for a total of 2(n2+n) elements. In the third round, each user runs the key recovery algorithm to get a pair (Kˆ,kˆ) and broadcasts 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.

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.

Table 1

Performance of our protocol compared to recent post-quantum solutions. Here, ADGK refers to the protocol in Apon et al. (2019) and ADGK is an authenticated version of ADGK, obtained by applying the Katz-Yung compiler. PSS refers to the solution in Persichetti et al. (2019).

RoundsCommunicationComputationAuthentication
Here2 n2+n elements in G, 2(n+1) exp. in G,Password+
n2 KEM public keys,n key enc. and dec.,MAC
n2 MAC tags, n2+n MAC tags
n KEM-encapsulated keys,
n masked ephem. keys
ADGK3 2(n2+n) Rqˆ-elements, 2(n+1)2 ops. in Rqˆ,Unauthent.
n2+n elements in the 2n key rec. calls
output space of the key
reconciliation algorithm
ADGK4As in ADGK, plusAs above, plusPKI+
n+1 nonces and 3(n2+n) sign.Signature
3(n2+n) signatures
PSS3n KEM public keys,n key enc. and dec.,PKI+
n KEM-encapsulated keys,n sign.Signature
n2+n masked ephem. keys
n2+n signatures

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.

Notes

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

2 Dealing with authentication through a shared password exclusively, we do not consider key establishments among strict subsets of U. With pidisi:=U being the only case of interest, in the sequel we do not make explicit use of pidisi when defining partnering, integrity, etc.

3 In the sequel, for the sake of simplicity, we will assume M.KeyGen(1) actually selects k uniformly at random in {0,1}m().

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.

References

1 

Abdalla, M., Bohli, J., Vasco, M.I.G., Steinwandt, R. (2007). (Password) Authenticated key establishment: from 2-party to group. In: Vadhan, S.P. (Ed.), Theory of Cryptography, 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21–24, 2007, Proceedings, Lecture Notes in Computer Science, Vol. 4392. Springer, Amsterdam, The Netherlands, pp. 499–514.

2 

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P. (2016). Post-quantum key exchange – a new hope. In: Holz, T., Savage, S. (Eds.), 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10–12, 2016. USENIX Association, pp. 327–343.

3 

Apon, D., Dachman-Soled, D., Gong, H., Katz, J. (2019). Constant-round group key exchange from the ring-LWE assumption. In: Ding, J., Steinwandt, R. (Eds.), Post-Quantum Cryptography – 10th International Conference PQCrypto 2019, Chongqing, China, May 8–10, 2019, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 11505. Springer, pp. 189–205.

4 

Aragon, N., Barreto, P., Bettaieb, S., Bidoux, L., Blazy, O., Deneuville, J.-C., Gaborit, P., Gueron, S., Guneysu, T., Melchor, C.A., Misoczki, R., Persichetti, E., Sendrier, N., Tillich, J.-P., Zémor, G. (2017). BIKE: bit flipping key encapsulation. hal-01671903.

5 

Azarderakhsh, R., Campagna, M., Costello, C., Feo, L., Hess, B., Jalali, A., Jao, D., Koziel, B., LaMacchia, B., Longa, P. et al. (2017). SIKE – Supersingular Isogeny Key Encapsulation. https://sike.org/.

6 

Bellare, M., Rogaway, P. (1994). Entitiy authentication and key distribution. In: Stinson, D.R. (Ed.), Advances in Cryptology – CRYPTO ’93, Lecture Notes in Computer Science, Vol. 773. Springer, pp. 232–249.

7 

Bellare, M., Pointcheval, D., Rogaway, P. (2000). Authenticated key exchange secure against dictionary attacks. In: Preneel, B. (Ed.), Advances in Cryptology – EUROCRYPT 2000, Lecture Notes in Computer Science, Vol. 1807. Springer, pp. 139–155.

8 

Benhamouda, F., Blazy, O., Ducas, L., Quach, W. (2018). Hash proof systems over lattices revisited. In: Abdalla, M., Dahab, R. (Eds.), Public-Key Cryptography – PKC 2018 – 21st IACR International Conference on Practice and Theory of Public-Key Cryptography. Rio de Janeiro, Brazil, March 25–29, 2018, Proceedings, Part II, Lecture Notes in Computer Science, Vol. 10770. Springer, pp. 644–674.

9 

Bernstein, D.J. (2005). The Poly1305-AES message-authentication code. In: Gilbert, H., Handschuh, H. (Eds.), Fast Software Encryption FSE 2005, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 3557. Springer, pp. 32–49.

10 

Bernstein, D., Chou, T., Lange, T., von Maurich I, Misoczki, R., Niederhagen, R., Persichetti, E., Peters, C., Schwabe, P., Sendrier, N., Szefer, J., Wang, W. (2017a). Classic McEliece. https://classic.mceliece.org/.

11 

Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C. (2017b). Reducing attack surface at low cost. In: Adams, C., Camenisch, J., (Eds.), Selected Areas in Cryptography – SAC 2017 – 24th International Conference, Ottawa, ON, Canada, August 16–18, 2017, Revised Selected Papers, Lecture Notes in Computer Science, Vol. 10719. Springer, pp. 235–260.

12 

Bindel, N., Herath, U., McKague, M., Stebila, D. (2017). Transitioning to a quantum-resistant public key infrastructure. In: Lange, T., Takagi, T. (Eds.), Post-Quantum Cryptography – 8th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26–28, 2017, Proceedings, Lecture Notes in Computer Science, Vol. 10346. Springer, pp. 384–405.

13 

Bindel, N., Brendel, J., Fischlin, M., Goncalves, B., Stebila, D. (2018). Hybrid key encapsulation mechanisms and authenticated key exchange. IACR Cryptology ePrint Archive, 2018, 903.

14 

Bohli, J.M., González Vasco, M.I., Steinwandt, R. (2007). Secure group key establishment revisited. International Journal of Information Security, 6(4), 243–254.

15 

Boneh, D., Glass, D., Krashen, D., Lauter, K.E., Sharif, S., Silverberg, A., Tibouchi, M., Zhandry, M. (2018). Multiparty non-interactive key exchange and more from isogenies on elliptic curves. CoRR. abs/1807.03038.

16 

Bos, J.W., Costello, C., Naehrig, M., Stebila, D. (2015). Post-quantum key exchange for the TLS protocol from the ring learning with errors problem. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17–21, 2015. IEEE Computer Society, pp. 553–570.

17 

Bos, J.W., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., Stebila, D. (2016). Frodo: take off the ring! Practical, quantum-secure key exchange from LWE. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (Eds.), Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24–28, 2016. ACM, pp. 1006–1018.

18 

Bos, J.W., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehlé, D. (2018). CRYSTALS – kyber: A CCA-secure module-lattice-based KEM. In: 2018 IEEE European Symposium on Security and Privacy, EuroS&P 2018, London, United Kingdom, April, 24–26, 2018. IEEE, pp. 353–367.

19 

Bresson, E., Chevassut, O., Pointcheval, D., Quisquater, J. (2001). Provably authenticated group Diffie-Hellman key exchange. In: Reiter, M.K., Samarati, P. (Eds.), CCS 2001, Proceedings of the 8th ACM Conference on Computer and Communications Security, Philadelphia, Pennsylvania, USA, November 6–8, 2001. ACM, pp. 255–264.

20 

Burmester, M., Desmedt, Y. (2005). A secure and scalable Group Key Exchange system. Information Processing Letters, 94(3), 137–143.

21 

Chevassut, O., Fouque, P., Gaudry, P., Pointcheval, D. (2006). The twist-augmented technique for key exchange. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (Eds.), Public Key Cryptography – PKC 2006 Proceedings. Lecture Notes in Computer Science, Vol. 3958. Springer, pp. 410–426.

22 

Ding, J., Xie, X., Lin, X. (2012). A simple provably secure key exchange scheme based on the learning with errors problem. IACR Cryptology ePrint Archive, 2012, 688.

23 

Ding, J., Gao, X., Takagi, T., Wang, Y. (2019a). One sample ring-LWE with rounding and its application to key exchange. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (Eds.), Applied Cryptography and Network Security – 17th International Conference, ACNS 2019, Bogota, Colombia, June 5–7, 2019, Proceedings, Lecture Notes in Computer Science, Vol. 11464. Springer, pp. 323–343.

24 

Ding, J., Schmitt, K., Zhang, Z. (2019b). A key exchange based on the short integer solution problem and the learning with errors problem. In: Carlet, C., Guilley, S., Nitaj, A., Souidi, E.M. (Eds.), Codes, Cryptology and Information Security – Third International Conference, C2S 2019, Rabat, Morocco, April 22–24, 2019, Proceedings – In Honor of Said El Hajji, Lecture Notes in Computer Science, Vol. 11445. Springer, pp. 105–117.

25 

Dodis, Y., Kiltz, E., Pietrzak, K., Wichs, D. (2012). Message authentication. In: Pointcheval, D., Johansson, T. (Eds.), Advances in Cryptology – EUROCRYPT 2012 – 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15–19, 2012, Proceedings, Lecture Notes in Computer Science, Vol. 7237. Springer, pp. 355–374.

26 

Katz, J., Yung, M. (2007). Scalable protocols for authenticated group key exchange. Journal of Cryptology, 20(1), 85–113.

27 

Katz, J., Vaikuntanathan, V. (2009). Smooth projective hashing and password-based authenticated key exchange from lattices. In: Matsui, M. (Ed.), Advances in Cryptology – ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6–10, 2009, Proceedings, Lecture Notes in Computer Science, Vol. 5912. Springer, pp. 636–652.

28 

National Institute of Standards and Technology (2019). Post-Quantum Cryptography; Round 2 Submissions. https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions.

29 

Persichetti, E., Steinwandt, R., Suárez Corona, A. (2019). From key encapsulation to authenticated group key establishment – a compiler for post-quantum primitives. Entropy, 21(12), 1183.