Group Key Establishment in a Quantum-Future Scenario
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 ( ) 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.
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 ( ), which are cryptographic constructions allowing a group of 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 (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.
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.
In this work we focus on a scenario that tries to capture today’s reality: Participants engage in a 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 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 is assumed to be of polynomial size (in the security parameter ), and each user may execute a polynomial number of protocol instances concurrently. To refer to instance of a user we use the notation ( ).
Protocol instances. A single instance can be taken for a process executed by . To each instance we assign seven variables:
indicates whether this instance is or has been used for a protocol run. The flag can only be set through a protocol message received by the instance due to a call to the - or the -oracle (see below);
keeps the state information needed during the protocol execution;
shows if the execution has terminated;
denotes a possibly public session identifier that can serve as identifier for the session key ;
stores the set of identities of those users that aims at establishing a key with—including himself;22
indicates if the protocol instance was successful, i.e. the user accepted the session key;
stores the session key once it is accepted by 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 are made explicit through a number of oracles allowing to communicate with protocol instances run by the users, and we use an oracle to capture future quantum capabilities of :
This sends message M to the instance and returns the reply generated by this instance. If queries this oracle with an unused instance and M being the string “ ”, the -flag is set, and the initial protocol message of is returned.
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 oracle is supposed to reflect a passive eavesdropping. In particular, no online-guess for the secret password can be implemented with this oracle.
yields the session key along with its corresponding session identifier .
Only one query of this form is allowed for an active adversary . Provided that is defined, (i.e. and ), can execute this oracle query at any time when being activated. Then with probability 1/2 the session key and with probability 1/2 a uniformly chosen random session key is returned.
This oracle returns all long-term secrets held by user (e.g. a password or static keys for an authentication mechanism). The -oracle’s only purpose is to model forward secrecy.
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 , as being partnered if both and .
To avoid trivial cases, we assume that an instance 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 correct, if in the presence of a passive adversary —i.e. must not use the oracle—the following holds: for all with both and , we have 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 hold identical session keys .
Next, for detailing the security definition, we will have to specify under which conditions a -query may be executed.
Freshness. A -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 is called fresh in case none of the events below occurred:
• A query is executed before a query of the form takes place. (One could consider to restrict to , but as indicated in footnote 2, is the only case of interest.)
• A query is performed, after a query took place.
• A query is executed with and 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 of polynomial size in the security parameter ℓ. Groups are as a result defined by a set of users which use the same password in for authentication. The security goal aimed at is defined in terms of the advantage of an adversary in attacking protocol . This advantage is a function in the security parameter ℓ, defined as
A group key exchange protocol provides quantum-future key secrecy, if for every dictionary and every ppt adversary querying the -oracle with at most q different protocol instances, the following inequality holds for some negligible function :
The above definition follows the standard approach in password authenticated key exchange, where typically the function ε is a constant multiple of 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 -query).
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 , where:
• The probabilistic key generation algorithm takes as input the security parameter and outputs a key pair .
• The probabilistic encapsulation algorithm takes as input a public key and outputs a ciphertext c and a key , where is a polynomial function of the security parameter.
• The deterministic decapsulation algorithm takes as input a secret key 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 generates and , chooses uniformly at random a key and a bit . Then the adversary , which is treated as a quantum algorithm, is given and produces an output as the guess for b. With being the probability that ’s output equals b, we define and say that the KEM is IND-CPA secure against fully quantum adversaries if for every polynomial-time bounded , the advantage 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 where:
• The probabilistic key generation algorithm takes as input the security parameter and outputs a key for a suitable polynomial .33
• The probabilistic authentication algorithm takes as input a key k and a message M and outputs a tag t.
• The deterministic verification algorithm 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 generates and the adversary is granted oracle access to and . The adversary wins if makes a query to such that the output is 1 and has not been queried to . The MAC is said to be UF-CMVA secure if for all ppt adversaries , the probability of the adversary winning the previous experiment is negligible in the security parameter ℓ.
If is a deterministic algorithm, then does not need to be explicitly defined, since it is specified by if and only if .
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 with a Sophie-Germain prime 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 , we denote by (statistically close to uniform random) bits extracted deterministically from g. When extracting two independent (half-length) bit-strings from g, we take as concatenation of two (half length) bit-strings.
An elegant and more efficient approach to randomness extraction, which enables the use of elliptic curves over prime fields 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 be the (polynomial-size) password dictionary, and let G be a group of prime order q. We assume that through some public and efficiently computable injection . For instance, if is the group of quadratic residues in with a Sophie-Germain prime , we can identify the binary representation of (length-restricted) passwords with elements in , and then map passwords uniquely into G by raising the generator g to the appropriate power.44 Finally, let ℓ denote the security parameter and denote the bit-length of session keys. We impose a Decisional Diffie Hellman assumption as follows:
Assumption 1(Decisional Diffie Hellman for ).
Let G be a finite group of prime order and a dictionary with an efficient injection . Then, the Decisional Diffie Hellman assumption for states that, for every , the probability distributions for and for are computationally indistinguishable. In other words, no ppt algorithm can tell them apart with non-negligible probability in the security parameter ℓ.
Let be the users running the protocol and assume they share password . 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 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 , 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, broadcasts a group element, , obtained as an encoding of his password, which is his “Diffie-Hellman contribution” for the authentication tags. Any other user broadcasts similarly a group element and his freshly generated public key for the key encapsulation mechanism.
• In Round II, user generates for each user 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 . Furthermore, users also broadcast confirmation tags pairwise. Namely, and extract two different MAC keys from the shared element , that is, uses for users “on his left” (i.e. for ) and for users “on his right” ( ).
• Finally, all tags are checked, and if they are successful then each ( ) decapsulates the bitstring k and extracts from it the session key and its corresponding session identifier. Note that if a user is inserting an invalid password, the two party Diffie Hellman key he will be able to construct will (with overwhelming probability) not match the one constructed by , hence it will be detected as a tag-mismatch.
Note that our solution is not contributory (for 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 -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 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).
The protocol described in Fig. 1 achieves quantum-future key secrecy, under the Decisional Diffie Hellman Assumption in and assuming it is instantiated with a UF-CMVA-secure message authentication code and an IND-CPA-secure (post-quantum) key encapsulation mechanism.
The proof is set up in terms of several experiments or games, where a challenger interacts with the adversary confronting it with a counterfeit -challenge in the spirit of the key secrecy definition from Section 2. We denote with the advantage of adversary in the i-th game .
Game . This first game corresponds to a real attack, in which all the parameters are chosen as in the actual scheme. By definition,
Game . This game is identical to , except from the fact that it aborts with an adversarial win if 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 queries called by
At this, we can argue that the tags can be replaced with bitstrings of the correct length chosen uniformly at random. Indeed, we may modify the and oracle in such a way that all values from Round I are replaced with chosen u.a.r. from G. The games and can only be distinguished one from the other if:
Indeed, as the group elements have been chosen uniformly at random, the MAC keys derived in Round II are also uniformly at random selected bitstrings. Thus we have,
Case 2: queried after or
If the 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 ; however, as he is not allowed making any 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
To argue that the only way an adversary is able to distinguish between and is breaking the IND-CPA security of the KEM, we depict how an IND-CPA adversary for the KEM can be constructed from an adversary who may distinguish between the two games.
Indeed, suppose we actually introduce the change in step by step. Let be an adversary distinguishing between and the game resulting after step 1. Now, let be presented with an IND-CPA challenge for the KEM used by user , i.e. with a value where is either a key encapsulated in C using or a string chosen uniformly at random. Now, fixing a session key k, fairly produce messages from Round I for each user for and replace by while, for the rest, follow the protocol description. Now, if comes from the KEM, all messages will follow the protocol specification, while if it is selected uniformly at random indeed will also be. As a result, if distinguishes between and he will violate the IND-CPA security of the KEM, so indeed, replicating this argument in a step by step fashion we have
Note that in the above proof it is crucial to restrict the calls in the definition of freshness; otherwise an offline-guessing strategy can be mounted by solving the corresponding Diffie-Hellman instances for every and confronting the result with the messages tagged with i.e. a quantum adversary may get the password from the transcript and thus we should make clear we do not allow for subsequent calls once has been queried.
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 when trying to tell apart the “real” from randomly selected ones.
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 for every protocol. Table 1 summarizes important characteristics.
• Our protocol. In the first round, elements of G and n public keys of the KEM are broadcast, yielding a total of elements of G and public keys to be transmitted. In the second round, 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 , 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 is fixed, where is a prime and is a power of 2 such that . In the first two rounds, each user broadcasts an element of , for a total of elements. In the third round, each user runs the key recovery algorithm to get a pair and broadcasts .
• 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.
|Here||2||elements in G,||exp. in G,||Password+|
|KEM public keys,||n key enc. and dec.,||MAC|
|MAC tags,||MAC tags|
|n KEM-encapsulated keys,|
|n masked ephem. keys|
|ADGK||3||-elements,||ops. in ,||Unauthent.|
|elements in the||key rec. calls|
|output space of the key|
|ADGK†||4||As in ADGK, plus||As above, plus||PKI+|
|PSS||3||n KEM public keys,||n key enc. and dec.,||PKI+|
|n KEM-encapsulated keys,||n sign.||Signature|
|masked ephem. keys|
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.
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 . With being the only case of interest, in the sequel we do not make explicit use of when defining partnering, integrity, etc.
3 In the sequel, for the sake of simplicity, we will assume actually selects k uniformly at random in .
4 In view of Definition 1, simply squaring the password , seen as group element, has the downside that with any incorrect guess for , an adversary can exclude , too.
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.
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.
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.
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.
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/.
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.
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.
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.
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.
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/.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Burmester, M., Desmedt, Y. ((2005) ). A secure and scalable Group Key Exchange system. Information Processing Letters, 94: (3), 137–143.
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.
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.
Ding, J., Gao, X., Takagi, T., Wang, Y. ((2019) a). 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.
Ding, J., Schmitt, K., Zhang, Z. ((2019) b). 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.
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.
Katz, J., Yung, M. ((2007) ). Scalable protocols for authenticated group key exchange. Journal of Cryptology, 20: (1), 85–113.
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.
National Institute of Standards and Technology (2019). Post-Quantum Cryptography; Round 2 Submissions. https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions.
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.