## 1 Introduction

## 2 Model

*M*to the instance ${\Pi _{i}^{{s_{i}}}}$ and returns the reply generated by this instance. If $\mathcal{A}$ queries this oracle with an unused instance ${\Pi _{i}^{{s_{i}}}}$ and

*M*being the string “$\mathsf{Start}$”, the ${\mathsf{used}_{i}^{{s_{i}}}}$-flag is set, and the initial protocol message of ${\Pi _{i}^{{s_{i}}}}$ is returned.

*c*(a quantum circuit) of a quantum computation that can be executed in polynomial time, e.g. computing a discrete logarithm. The oracle returns a classical value, representing the result of the specified quantum computation.

### 2.1 Correctness, Integrity and Secrecy

- • A $\mathsf{Corrupt}({U_{j}})$ query is executed before a query of the form $\mathsf{Send}({U_{k}},{s_{k}},\ast )$ takes place. (One could consider to restrict to ${U_{j}},{U_{k}}\in {\mathsf{pid}_{i}^{{s_{i}}}}$, but as indicated in footnote 2, ${\mathsf{pid}_{i}^{{s_{i}}}}=\mathcal{U}$ is the only case of interest.)
- • A $\mathsf{Send}$ query is performed, after a $\mathsf{QCom}$ query took place.
- • A $\mathsf{Reveal}({U_{j}},{s_{j}})$ query is executed with ${\Pi _{i}^{{s_{i}}}}$ and ${\Pi _{j}^{{s_{j}}}}$ being partnered.

*ℓ*. Groups are as a result defined by a set of users which use the same password in $\mathcal{D}$ for authentication. The security goal aimed at is defined in terms of the advantage ${\mathsf{Adv}_{\mathcal{A}}}$ of an adversary $\mathcal{A}$ in attacking protocol $\mathcal{P}$. This advantage is a function in the security parameter

*ℓ*, defined as Here $\mathsf{Succ}$ is the probability that the adversary queries $\mathsf{Test}$ on a fresh instance ${\Pi _{i}^{{s_{i}}}}$ and guesses correctly the bit

*b*used by the $\mathsf{Test}$ oracle in a moment when ${\Pi _{i}^{{s_{i}}}}$ is still fresh.

##### Definition 1.

*q*different protocol instances, the following inequality holds for some negligible function $\mathrm{negl}(\ell )$: where

*ℓ*is the security parameter and

*ε*is a function which is at most linear in $q.$

##### Remark 1.

*ε*is a constant multiple of $\frac{q}{|\mathcal{D}|}$ plus some negligible term (thus, it is assumed that passwords are chosen uniformly at random from the dictionary and that the adversary can test a constant number of passwords on each $\mathsf{Send}$-query).

## 3 Tools

### 3.1 Key Encapsulation Mechanisms

- • The probabilistic key generation algorithm $\mathcal{K}.\mathsf{KeyGen}({1^{\ell }})$ takes as input the security parameter and outputs a key pair $(pk,sk)$.
- • The probabilistic encapsulation algorithm $\mathsf{Encaps}(pk,{1^{\ell }})$ takes as input a public key $pk$ and outputs a ciphertext
*c*and a key $k\in {\{0,1\}^{p(\ell )}}$, where $p(\ell )$ is a polynomial function of the security parameter. - • The deterministic decapsulation algorithm $\mathsf{Decaps}(sk,c,{1^{\ell }})$ takes as input a secret key $sk$ and a ciphertext
*c*and outputs a key*k*or ⊥.

*b*. With ${\mathsf{Succ}_{\mathcal{A}}}$ being the probability that $\mathcal{A}$’s output equals

*b*, we define ${\mathsf{Adv}_{\mathcal{A},\text{KEM}}}:=|2\cdot {\mathsf{Succ}_{\mathcal{A}}}-1|$ and say that the KEM is IND-CPA secure against fully quantum adversaries if for every polynomial-time bounded ${\mathsf{Adv}_{\mathcal{A},\text{KEM}}}$, the advantage ${\mathsf{Adv}_{\mathcal{A},\text{KEM}}}$ is negligible.

### 3.2 Message Authentication Codes

- • The probabilistic key generation algorithm $\mathcal{M}.\mathsf{KeyGen}({1^{\ell }})$ takes as input the security parameter and outputs a key $k\in {\{0,1\}^{m(\ell )}}$ for a suitable polynomial $m(\ell )$.3
- • The probabilistic authentication algorithm $\mathsf{Tag}(k,M)$ takes as input a key
*k*and a message*M*and outputs a tag*t*. - • The deterministic verification algorithm $\mathsf{Vf}(k,M,t)$ takes as input a key
*k*, a message*M*and a tag*t*and outputs a decision: 1 (accept) or 0 (reject).

*ℓ*.

### 3.3 Deterministic Randomness Extraction

*G*in which the Decision-Diffie-Hellman assumption holds, and from (uniform random) elements in

*G*, we want to extract (uniform random) bit-strings. To realize this without the introduction of additional technical machinery or a random oracle, work in Chevassut et al. (2006) comes in handy. Specifically, if we let

*G*be the group of quadratic residues in ${\mathbb{Z}_{2|G|+1}^{\times }}$ with a Sophie-Germain prime $|G|$ close to a power of 2, simple truncation of the binary representation is an efficient extractor (Chevassut et al., 2006, Section 3.2). Subsequently, for a (uniform random) group element $g\in G$, we denote by $[g]$ (statistically close to uniform random) bits extracted deterministically from

*g*. When extracting two independent (half-length) bit-strings from

*g*, we take $[g]={[g]_{L}}||{[g]_{R}}$ as concatenation of two (half length) bit-strings.

##### Remark 2.

*p*being close to a power of 2, is provided by Chevassut et al.’s Twist-AUgmented (TAU) technique. When trying to optimize the performance of the protocol below, a possible adoption of the TAU approach is natural to explore. Similar to Chevassut et al. (2006, Fig. 1) one could—at the bandwidth cost of essentially two parallel Diffie-Hellman executions—try to work on a curve and its twist simultaneously, eventually leveraging the message authentication code to select the correct protocol outcome.

## 4 The Proposed Protocol

*G*be a group of prime order

*q*. We assume that $\mathcal{D}\subseteq G$ through some public and efficiently computable injection $\mathcal{D}\hookrightarrow G$. For instance, if $G=\langle g\rangle $ is the group of quadratic residues in ${\mathbb{Z}_{2|G|+1}}$ with a Sophie-Germain prime $|G|$, we can identify the binary representation of (length-restricted) passwords with elements in ${\mathbb{Z}_{|G|}}$, and then map passwords uniquely into

*G*by raising the generator

*g*to the appropriate power.4 Finally, let

*ℓ*denote the security parameter and $p(\ell )$ denote the bit-length of session keys. We impose a Decisional Diffie Hellman assumption as follows:

##### Assumption 1 (Decisional Diffie Hellman for $(G,\mathcal{D})$).

*G*be a finite group of prime order and $\mathcal{D}$ a dictionary with an efficient injection $\iota :\mathcal{D}\hookrightarrow G$. Then, the Decisional Diffie Hellman assumption for $(G,\mathcal{D})$ states that, for every $g\in \iota (\mathcal{D})$, the probability distributions $({g^{a}},{g^{b}},{g^{ab}})$ for $(a,b)\gets {\mathbb{Z}_{|G|}^{2}}$ and $({g^{a}},{g^{b}},h)$ for $(a,b,h)\gets {\mathbb{Z}_{|G|}^{2}}\times G$ are computationally indistinguishable. In other words, no ppt algorithm can tell them apart with non-negligible probability in the security parameter

*ℓ*.

### 4.1 Protocol specification

*k*being masked (for each of them) with an ephemeral key obtained from the key encapsulation. To ensure (password-based) authentication, in parallel each user establishes a Diffie-Hellman key with ${U_{0}}$, with the shared password fixing a generator for the Diffie-Hellman group. The latter keys are used to compute “after the fact” authentication tags on protocol messages. Once a player is convinced that all protocol messages are legitimate, the session key is accepted. More precisely:

- • In Round I, ${U_{0}}$ broadcasts a group element, ${g_{0}}$, obtained as an encoding of his password, which is his “Diffie-Hellman contribution” for the authentication tags. Any other user ${U_{i}}$ broadcasts similarly a group element ${g_{i}},$ and his freshly generated public key $p{k_{i}}$ for the key encapsulation mechanism.
- • In Round II, user ${U_{0}}$ generates for each user ${U_{j}}$ a KEM key, and masks with it a (freshly chosen for each run) bitstring
*k*(which will eventually be the session key). This message is authenticated using a bit-string extracted from ${g_{0,j}}$. Furthermore, users also broadcast confirmation tags pairwise. Namely, ${U_{i}}$ and ${U_{j}}$ extract two different MAC keys from the shared element ${g_{i,j}}$, that is, ${U_{i}}$ uses ${[{g_{i,j}}]_{L}}$ for users “on his left” (i.e. for $j>i$) and ${[{g_{i,j}}]_{R}}$ for users “on his right” ($i<j$). - • Finally, all tags are checked, and if they are successful then each ${U_{i}}$ ($i>0$) decapsulates the bitstring
*k*and extracts from it the session key and its corresponding session identifier. Note that if a user ${U_{i}}$ is inserting an invalid password, the two party Diffie Hellman key ${g_{i,j}}$ he will be able to construct will (with overwhelming probability) not match the one constructed by ${U_{j}}$, hence it will be detected as a tag-mismatch.

##### Remark 3.

##### Theorem 1.

##### Proof.

*i*-th game ${G_{i}}$.

*G*. The games ${G_{0}}$ and ${G_{1}}$ can only be distinguished one from the other if:

- • $\mathcal{A}$ correctly guesses $\mathsf{pw}$ and sends a properly computed value ${g_{i}}={\mathsf{pw}^{{\beta _{i}}}}$ to an instance of ${U_{j}}$ on behalf of an instance of ${U_{i}}$. If this is the case, $\mathcal{A}$ may correctly verify the tag ${t_{j,i}}$ he gets from ${U_{j}}$ in ${G_{0}}$ while the verification will be unsuccessful in ${G_{1}}$.
- • $\mathcal{A}$, not using $\mathsf{QCom}$ checks offline, for each password in the dictionary $\mathcal{D},$ whether the triplets $({g_{i}},{g_{j}},{t_{i,j}})$ are all consistent for a fixed password. It is easy to see that if $\mathcal{A}$ can actually check whether such triplets $({g_{i}},{g_{j}},{t_{i,j}})$ are consistent with a given password $p{w^{\ast }}$, the corresponding Decisional Diffie Hellman assumption in $(G,\mathcal{D})$ cannot hold. Indeed, we may construct an adversary $\mathcal{B}$ using $\mathcal{A}$ in order to solve a corresponding Decisional Diffie Hellman challenge in $(G,\mathcal{D})$. Let $(g,x,y,z)$ be the input to $\mathcal{B}.$ In order to tell whether order to distinguish whether that is a triplet of the form $({g^{a}},{g^{b}},{g^{ab}})$ or
*z*is a randomly generated element in*G*, $\mathcal{B}$ presents $\mathcal{A}$ with a simulated transcript (using the password encoding by*g*for authentication) where for a certain pair of users ${U_{i}},{U_{j}}$ the authenticated tags ${t_{i,j}}$ and ${t_{j,i}}$ are constructed from $z.$

*ℓ*.

*k*and the output ${k_{i}}$ of $\mathsf{Encaps}$ and that

*k*is chosen u.a.r. by ${U_{0}}$ and only used in the computation of the values ${d_{i}}$ throughout a protocol run.

*C*using $p{k_{1}}$ or a string chosen uniformly at random. Now, fixing a session key

*k*, fairly produce messages from Round I for each user $({d_{i}},{c_{i}})$ for $i=1,\dots ,n$ and replace ${m_{0,l}}$ by ${m_{0,l}^{\ast }}=(KEY\oplus k,C),$ while, for the rest, follow the protocol description. Now, if $KEY$ comes from the KEM, all messages will follow the protocol specification, while if it is selected uniformly at random indeed $KEY\oplus k$ will also be. As a result, if $\mathcal{A}$ distinguishes between ${G_{1}}$ and ${G_{2}}$ he will violate the IND-CPA security of the KEM, so indeed, replicating this argument in a step by step fashion we have

##### Remark 4.

### 4.2 Performance

- • Our protocol. In the first round, $n+1$ elements of
*G*and*n*public keys of the KEM are broadcast, yielding a total of ${n^{2}}+n$ elements of*G*and ${n^{2}}$ public keys to be transmitted. In the second round, ${n^{2}}$ tags,*n*KEM ciphertexts, and*n*masked ephemeral keys are sent. - • Apon et al. (2019). This scheme provides security against passive adversaries. In order to transform it into a $\mathsf{GAKE}$, the authors propose using the Katz-Yung compiler (Katz and Yung, 2007), which adds one round of communication (in which each participant broadcasts a nonce), and appends one signature to every sent message that should be taken into account. In the setup, a ring ${R_{\hat{q}}}={\mathbb{Z}_{\hat{q}}}[X]/({X^{\hat{n}}}+1)$ is fixed, where $\hat{q}$ is a prime and $\hat{n}$ is a power of 2 such that $\hat{q}\equiv 1\hspace{0.2em}\mathrm{mod} \hspace{0.2em}2\hat{n}$. In the first two rounds, each user broadcasts an element of ${R_{\hat{q}}}$, for a total of $2({n^{2}}+n)$ elements. In the third round, each user runs the key recovery algorithm to get a pair $(\hat{K},\hat{k})$ and broadcasts $\hat{K}$.
- • Persichetti et al. (2019). This scheme is also a compiler which invokes a KEM and a signature scheme. In the first round, each user sends a KEM public key to his right neighbour, while in the second one, each user sends a KEM ciphertext to his left neighbour. Finally, in the third round each user broadcasts a masked ephemeral key and a signature.

##### Table 1

Rounds | Communication | Computation | Authentication | |

Here | 2 | ${n^{2}}+n$ elements in G, | $2(n+1)$ exp. in G, | Password+ |

${n^{2}}$ KEM public keys, | n key enc. and dec., | MAC | ||

${n^{2}}$ MAC tags, | ${n^{2}}+n$ MAC tags | |||

n KEM-encapsulated keys, | ||||

n masked ephem. keys | ||||

ADGK | 3 | $2({n^{2}}+n)$ ${R_{\hat{q}}}$-elements, | $2{(n+1)^{2}}$ ops. in ${R_{\hat{q}}}$, | Unauthent. |

${n^{2}}+n$ elements in the | $2n$ key rec. calls | |||

output space of the key | ||||

reconciliation algorithm | ||||

ADGK${^{\dagger }}$ | 4 | As in ADGK, plus | As above, plus | PKI+ |

$n+1$ nonces and | $3({n^{2}}+n)$ sign. | Signature | ||

$3({n^{2}}+n)$ signatures | ||||

PSS | 3 | n KEM public keys, | n key enc. and dec., | PKI+ |

n KEM-encapsulated keys, | n sign. | Signature | ||

${n^{2}}+n$ masked ephem. keys | ||||

${n^{2}}+n$ signatures |