Guilhem Castagnos

Céline Chevalier

Patrick Towa Nguenewou

Damien Vergnaud

Jacques Beigbeder

Lise-Marie Bivard

Stéphane Emery

Nathalie Gaudechoux

Joëlle Isnard

Sophie Jaudon

Valérie Mongiat

Mes Et Bien Évidemment

Collègues

Aurélien, Chloé, Dahmun, Fabrice, Florian, Geoffroy, Houda, Julia, Jérémy, Louiza Alain Anca

Pierrick, Pooya, Rafaël, Răzvan, Romain Michele O Sonia

Thierry Sylvain

Corentin (kangz Arnaud ( Nonal

Florian Guilhem

Guillaume ( Campi

Gueust Jean-Baptiste Henri

Ioonag Pascal

Sarah ( Goinfrex

Victor ( Levans

Drynn ) Yann

François Guillaume P Je Mentionne Aussi Baptiste

Maxime Matthieu Meredith

Stéphane Olivier

Jean-Claude Sifre

Dominique Zann

Keywords: authentication, cryptography, fuzzy password, key exchange, password, public-key

Authenticated key exchange is probably the most widely deployed asymmetric cryptographic primitive, notably because of its inclusion in the TLS protocol. Its cousin, passwordauthenticated key exchange -where the authentication is done using a low-entropy password -while having been studied extensively as well has been much less used in practice. It is, however, a primitive much closer to actual authentication when at least one party is human.

In this thesis, we consider advanced primitives based on password-authenticated key exchange, with an eye toward practical applications. Specifically, we introduce fuzzy passwordauthenticated key exchange, where the authentication succeeds as long as the two passwords are close enough, and not necessarily equal. We provide a security model in the UC framework, as well as a construction based on regular password-authenticated key exchanges and robust secret-sharing schemes.

Secondly, we consider the practical problem of password leakage when taking into account sessions conducted on a corrupted device. As there is intrinsically no hope with regular password authentication, we extend the BPR security model to consider low-entropy challenge responses instead. We then provide several instantiations, some based on human-compatible function families, where the operation required to answer the challenge are simple enough to be conducted in one's head, allowing the actual authentication to be directly performed by the human being.

iii -

Résumé

L'échange de clef authentifié est probablement la primitive asymétrique la plus utilisée, notamment du fait de son inclusion dans le protocole TLS. Pour autant, son cousin, l'échange de clef authentifié par mot de passe, où l'authentification s'effectue par comparaison de mot de passe, l'est bien moins, bien qu'ayant déjà fait l'objet d'études considérables. C'est pourtant une primitive finalement bien plus proche d'une authentification réelle, dès lors qu'une des parties est humaine.

Dans cette thèse, nous considérons des primitives avancées fondées sur l'échange de clef authentifié par mot de passe, en gardant à l'oeil ses applications pratiques. Spécifiquement, nous introduisons une nouvelle primitive, l'échange de clef authentifié par mot de passe approximatif, où la condition de succès de l'authentification est désormais d'avoir une distance suffisamment faible entre les deux mots de passe, et plus nécessairement l'égalité parfaite. Nous fournissons un modèle de sécurité dans le cadre du modèle de composabilité universelle (UC) ainsi qu'une construction reposant sur un partage de secret robuste et des échanges de clefs authentifiés par mot de passe exact.

Dans une seconde partie, nous considérons le problème pratique de la perte du mot de passe dès lors qu'une session est conduite sur un terminal compromis. Étant donné qu'il s'agit d'un problème intrinsèque à l'authentification par mot de passe, nous étendons le modèle BPR habituel pour prendre en compte, en lieu et place du mot de passe, des questions-réponses, toujours de faible entropie. Nous fournissons plusieurs protocoles dans ce modèle, dont certains reposent sur des familles de fonctions compatibles avec les humains, dans lesquelles les opérations requises pour dériver la réponse depuis la question sont suffisamment simples pour être faites de tête, permettant donc à l'humain de s'identifier directement.

v -En tout premier lieu, je tiens à adresser mes plus vifs remerciements à mon directeur de thèse, David Pointcheval. Les innombrables heures passées dans ton bureau à discuter marqueur en main des dernières difficultés découvertes dans nos travaux sont certainement le meilleur souvenir que je garderai de ces années de thèse. Il est certain que sans ton expertise et ta profonde maitrise de tant de sous-domaines de la cryptographie, cette thèse n'aurait jamais pu voir le jour.

Je témoigne également toute ma reconnaissance à mes deux rapporteurs, Pierre-Alain Fouque et Benoît Libert, pour avoir accepté d'entreprendre la lourde tâche de relire, mais surtout d'étudier ce manuscrit avec un oeil frais et critique. Leurs remarques précises et nombreuses auront grandement contribué à le rendre plus clair et plus cohérent.

Je voudrais aussi remercier les autres examinateurs ayant accepté de prendre part à mon jury : Céline Chevalier et Michel Abdalla, avec qui j'ai eu plaisir à partager mon quotidien à l'ENS, Guillaume Poupard, mon illustre prédécesseur, ainsi que Cyrille Wiedling, qui a accepté au pied levé de représenter au sein de ce jury DGA MI. Je tiens par la même occasion à remercier la DGA elle-même, et plus particulièrement la commission de la recherche, qui m'a permis de dédier intégralement mes premières années d'Ingénieur de l'Armement à cette thèse, sans aucune contrepartie. Un grand merci à Julien Devigne, qui a assuré mon suivi scientifique, ainsi qu'à Philippe Leriche, mon unique point de contact au sein de la DGA pendant toutes ces années. Je souhaiterais en outre remercier Raphaël Bost, qui a contribué à m'aiguiller lors de mes débuts dans le monde de la cryptologie, et Bruno Bouzy, pour m'avoir confié une charge d'enseignement à l'université.

During this thesis, it was a great pleasure to collaborate with many talented researchers, and I therefore express my sincere thanks to my coauthors: Sasha (Alexandra Boldyreva), Shan Chen, Julia Hesse, David Pointcheval, Leonid Reyzin and Sophia Yakoubov. Among them a special thanks goes to Julia

Introduction

At its beginning, cryptography was mainly about the design -and breaking -of ciphers, which we nowadays call symmetric encryption schemes. Basically, this refers to the ability to communicate a message without it being understood by anyone but its intended recipient. A prerequisite for all schemes is to have agreed upon some sort of the secret with the receiver at the beginning (be it the cipher itself or a smaller part of it, the key). While schemes got more and more secure and complicated as time went by, nothing much changed about this basic assumption until the age of the Internet.

In the last half-century, however, with the advent of computers and widely available remote communications, this basic setting has been changing. Not only do we require more and more security properties from the cryptographic scheme, but the prerequisite of initially sharing a common secret became a much bigger problem. How can I initially share a secret with every possible entity I will be communicating with?

Then came asymmetric cryptography, or public-key cryptography, in which there are still secrets but they no longer have to be shared with anybody. In an asymmetric encryption scheme, the receiver would simply generate a key pair, comprised of one public key and one private key. He would keep the private key for himself, and share the public key with not just the sender, but anybody. The security properties of the scheme would guarantee that, even knowing the public key, intercepting a message that had been encrypted by it would give no clue as to the actual message. Obviously the receiver would not be able to reply using the same key pair, for the sender could not read the response, but this can easily be solved by using another key pair, this time generated by the initial sender, for the reverse direction.

This leads to the first really new challenge of modern cryptography: authentication. Since now anyone can securely write to me, how do I know that the one I'm actually communicating with is who he pretends to be? With symmetric cryptography, this was quite easy, since he must be one that knows the shared secret 1 , but not so much now. And, similarly, how do I know that the public key that is being presented to me as the one of my intended recipient, and therefore with which I'll send my message, is actually the correct one. Fortunately, asymmetric cryptography also holds the answer, in the form of cryptographic signatures, a primitive by which one does not protect the content of the message from being read, but protects the identity of its author, as well as the message's integrity, from being manipulated.

Obviously it does need a source of trust, but we'll talk about that a bit later.

Asymmetric cryptography, for all its advantages, unfortunately comes with one drawback: it is very slow. This is due to the fact that, at its core, it works on a different kind of assumption. Symmetric cryptography iterates many rounds of quite simple operations (some linear, other non-linear). Asymmetric cryptography works on a hard mathematical problem, which typically involves one very complex operation (e.g. exponentiating a number). This simply does not scale up with the amount of data that need to be secured. This is why most online communications actually compose an asymmetric primitive, called authenticated key exchange (AKE), with a symmetric encryption scheme. An AKE is an interactive protocol where two parties sharing an authentication means get, at the end, a shared secret, especially suitable to be used in a symmetric encryption scheme. This allows to mitigate the slowness of asymmetric cryptography, since it is only used at the beginning of the protocol on a fixed amount of data, regardless of the size of the data thereafter exchanged, while not requiring that the particular two parties involved actually initially share a secret, which is not practical.

As noted previously, asymmetric cryptography does not completely free one of having some trusted data beforehand. Indeed, without trusting anything a priori, it is not possible to do anything meaningful. In practice, the trust one must have is in the public-key infrastructure (PKI), a somewhat complex system of authorities, that can authenticate the fact that a public key is indeed associated with the entity you know of. On the Internet, this typically means bridging the gap between the website's name (e.g. www.example.org) and its public key (that will subsequently be used to secure the communication with it). This is done through a concept of trust store, where the public keys of some of those entities are populated by the vendor of the software used (typically, the browser or the operating system). This mechanism is usually not symmetric, in the sense that while websites are authenticated by the PKI, users are not and, whenever a website needs to know who one of its users is, it uses an ad hoc system to do it (such as registration, and a login/password field), completely independent of the actual cryptography involved.

This PKI is also, unfortunately, one of the biggest failure points of the security of the Internet as a whole. Repeatedly, malicious parties have proven able to obtain trusted certificates, either by corrupting an authority or by taking advantage of insufficiently validated credentials. Even when everything works as it should, it is easy to obtain a certificate for a domain close enough for an unsuspecting user to be oblivious to.

A different approach that does not require any PKI is undertaken in password authenticated key exchange (PAKE), a variant of AKE where the authentication means is a passwordthat is, some secret information that both parties know in advance. Basically, assuming both parties hold a password (of low entropy) at the beginning, a PAKE is an interactive process through which they will each receive a session key (of high entropy) that will -assuming they did input the same password -be identical, while no-one else can learn it. Since by definition there is a small but non-negligible chance of simply guessing the password, this translates into a small but non-negligible probability of defeating PAKE security.

The main advantage of a PAKE is that the authentication is symmetric. From the server's point of view, the user will be authenticated while at the same time the server itself is authenticated from the user's point of view. No external trust is required and the password does not need to be handed over to the server, it has to know it already.

From a cryptographic perspective, the PAKE primitive has been studied extensively, beginning with the seminal paper [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF] to the first formal models of [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF][START_REF] Boyko | Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman[END_REF] and eventually its formalization in the generic universal composability (UC) model [START_REF] Canetti | Universally Composable Security: A New Paradigm for Cryptographic Protocols[END_REF][START_REF] Canetti | Universally Composable Password-Based Key Exchange[END_REF]. Numerous constructions exist, but only the original EKE construction from [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF] is of particular interest to this thesis.

While a PAKE guarantees that -if the same password was entered -the generated session key is the same for both parties, it is not necessarily the case that they know at the end of the protocol whether it is so or not. A PAKE is said to have explicit authentication when the party knows, at the end, if the protocol succeeded or not, and implicit authentication if they don't. Most applications actually care about explicitly authenticated PAKE, but fortunately, one can turn an implicitly authenticated PAKE into an explicitly authenticated PAKE, at the cost of one additional flow (basically to demonstrate knowledge of the correct key by encrypting/decrypting some value, see [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF]).

One could wonder, however, if there aren't situations where the uncertainty of implicitly authenticated PAKE isn't useful. This is usually not considered by regular PAKE models, that allow the adversary to learn whether authentication succeeded or not, even though no actual user has that capability. Hence we introduce implicit-only password authenticated key exchange (iPAKE), which formalizes a PAKE where even the adversary remains oblivious to the fact that authentication succeeded or not, and show that the seminal EKE construction [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF] satisfies this functionality. Obviously, this is only useful if we find applications where an iPAKE is used as a building block, but a careful approach is taken regarding the generated session keys, so as not to leak whether authentication succeeded or not. We introduce such an application next.

Taking a look back at PAKE, a natural extension would be to consider an authentication mechanism that would succeed if the two passwords were close enough, instead of equal. We call it a fuzzy password authenticated key exchange (fPAKE). This is especially useful for biometric authentication, since its process of secret reconstruction is naturally imprecise. Quite an easy way to do it would be to use a fuzzy extractor [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF][START_REF] Boyen | Reusable Cryptographic Fuzzy Extractors[END_REF] to reconstruct a deterministic secret from the fuzzy data, and to compose a regular PAKE with it. However, the fuzzy extractor requires some information to reconstruct the secret, and this information must be provided publicly, which reduces drastically the actual entropy of the password.

Assuming that this closeness of passwords is measured by the Hamming distance, two passwords are close enough if they only differ on a few number of characters. This reminds of error-correcting code (ECC), which can correct transmission errors or, in the case of secret values, of robust secret sharing (RSS). Hence we'll propose a fPAKE construction where we use a secret sharing to reconstruct a secret, while secret shares are actually masked by many session keys created through iPAKE protocols. For each character in the password, an independent iPAKE instance is run. When the iPAKE succeeded, you can remove the mask and hence learn the correct share, but shares at positions where the iPAKE failed are completely masked. Note that for this to work, it is essential that the positions where the iPAKE succeeded are not known in advance, otherwise more efficient RSS reconstruction algorithms exist. Hence a regular PAKE would not provide good-enough security guarantees.

Another issue we tackle with PAKE is the fact that, while the password-based authentication has the nice property of directly involving the actual (human) user, who has to remember it, it also means that this password could be used on potentially insecure devices. Consider the situation where one logs in on a public computer, which is potentially insecure. Since the computer (which we'll call the terminal) learns the password, were it to be malicious not only is this session compromised, but no security could be offered even on future sessions. This is called a strong corruption, where the adversary learns all secrets. It seems that nothing can be done cryptographically, because the long-term secret -the password -was leaked to the adversary. But what if the long-term secret was not what was entered in the terminal? We therefore extend PAKE into a primitive called human authenticated key exchange (HAKE), where we consider three actual parties: the human, the (potentially malicious) terminal and the server. The goal is to allow the human to establish a secure communication with the server whenever the terminal is honest, assuming not too many sessions have been previously conducted on malicious terminals. Instead of directly using the password, the authentication will be conducted via a challenge-response mechanism, keyed by a long-term secret.

This can be achieved either using a trusted device such as the physical tokens used by 2-Auth mechanism, or directly by the human himself using a human-computable function, i.e. a function simple enough to be computed in one's head, yet secure enough to prevent the forging of answers to other queries. Though quite a challenging topic, recent breakthrough allow to begin to consider it. Notably, the paper by Blocki et al. [START_REF] Blocki | Towards Human Computable Passwords[END_REF], based on the hardness arguments from [START_REF] Feldman | On the Complexity of Random Satisfiability Problems with Planted Solutions[END_REF], provides a first idea on how to achieve this.

Personal contributions 1.Contributions in this thesis

While this thesis is not purely a compilation of papers, it is mainly based on two publications, which are briefly described below.

[BCDP17] This paper deals with the hard task of maintaining security of a passwordbased authentication while, in practice, a user may occasionally use it in a non-secure setting (typically, a computer he does not own). This is called strong corruption and, by design, the long-term secret used in PAKE (the password) is compromised, and thus no security can be offered from future sessions. By replacing the password with a challenge-response function, whose responses can be easily computed, we achieve some security for future sessions, as long as not too many sessions were compromised. We invite interested readers to go to Chapter 5, which includes most of those results.

[DHP+18] In this paper, we consider how to extend the classical PAKE into a fPAKE functionality, where the authentication will succeed as long as the passwords are close enough according to some metric. A natural way to construct it would have been to compose a fuzzy extractor [DRS04; Boy04] and a regular PAKE, but the fuzzy extractor leaks a lot of information thus reducing the actual password entropy drastically. In this paper, we offer two constructions that achieve our fPAKE functionality in the UC model. The first construction based on Yao's garbled circuits achieves it for any efficiently computable metric. The second construction, based on PAKE and RSS, is more efficient but limited to the Hamming distance metric. We present the latter construction in this thesis, on Chapter 4. We direct readers interested in the former construction to the actual paper.

Other contribution

In addition to the work presented in this thesis, and outlined above, we also worked during our thesis on functional encryption, which led to the publication below.

[DP17] In this paper, we consider practical trade-offs related to the inner-product functional encryption primitive. While recent papers, notably [START_REF] Abdalla | Simple Functional Encryption Schemes for Inner Products[END_REF], have shown how to construct it quite efficiently, the functionality itself leaks much information on the ciphertext, which restricts the number of functional keys that can be generated. Indeed, if you hold the key for a vector f , you can (by the functionality) learn f • x for all plaintext x, and therefore colluding with n other key holder for different functions is typically enough to completely reveal a plaintex of size n. We therefore introduce an additional online player called the helper, that will have to be interacted with for any decryption query. We let it learn just the minimum required to guarantee the confidentiality of the database (in particular, not the result of the decryption). This allows to distribute many functional keys, while preventing too many of them from being used on the same data, which would breach privacy.

Organization of this thesis

This thesis is organized in six chapters, each of which is briefly presented below.

Chapter 2 introduces notations and recalls all preliminaries necessary to understand the thesis.

Chapter 3 presents a slightly stronger notion of PAKE, called iPAKE, in which the outcome of the key exchange is not directly linked to the adversary. It also introduces a label version, labeled implicit-only password authenticated key exchange (liPAKE), where an additional information can be added by each party during the execution of the PAKE, to be authenticated as well. Lastly, it shows that a well-known PAKE construction, EKE2, actually satisfies this liPAKE notion, in an idealized model.

Chapter 4 presents a more general notion of PAKE, called fPAKE, where the password equality requirement for the authentication success is replaced by a password closeness notion. It also shows how construct a secure fPAKE protocol, using a liPAKE construction as well as a RSS.

Chapter 5 takes a step back on the choice of passwords as the authentication method to consider how to achieve some kind of security in a setting where passwords can sometimes be compromised. By introducing a challenge response answered directly by the actual human user (with or without help from an external device), it allows to maintain some security for future sessions, as long as not too many sessions occurred on a corrupted machine.

Lastly, Chapter 6 concludes this thesis by offering a brief summary of what was achieved and stating some related questions that are still open for investigation.

Chapter 2 Preliminaries

Universal composability framework

In the following, we will often discuss cryptographic primitives presented in several models. Historically, primitives are often presented in ad hoc models that fall into two categories: game-based models and simulation-based models. In this thesis, we will make use of both of them.

A game-based model (or indistinguishability-based model) provides the adversary with a way to interact with an instance of the protocol, as well as ad hoc goals for each desired security property. A simulation-based model provides an idealized protocol that has all the desired security properties and allows to show how interacting with a real instance of the protocol is indistinguishable from interacting with the idealized protocol.

Among simulation-based models, the universal composability (UC) framework holds a particular place because of its generic composability property, allowing for an easy re-use of a cryptographic primitive. While most of the framework is fixed, a component called the ideal functionality F captures the precise properties the idealized instance should have.

Proving that a construction is secure in the UC framework means exhibiting a simulator S such that, anything an adversary A could do against honest players in the real protocol could be achieved by the same adversary A against the ideal functionality F, with the simulator S as an interface between A and F. But the ideal functionality is secure, by definition, and the combination of S and A cannot do anything harmful against the honest players using F. As a consequence, A cannot do anything harmful against the honest players in the real protocol execution.

The security of a UC protocol is thus measured by the advantage a distinguisher Z could get in distinguishing the real world (the interactive protocol between honest players with an adversary A) and the ideal world (the honest players directly dealing with the ideal functionality F, while the simulator S makes the interface with the adversary A).

Composability. The UC framework allows for composability. This means that once a construction has been proven secure in the UC framework, using it as a building block becomes easier.

Indeed, it is possible to substitute the construction itself with the ideal functionality in the broader proof. Since the simulator S allows to convert an adversary designed for the construction to an adversary against the ideal functionality, the broader proof can likewise -7 -be generically converted to a proof using all the actual constructions.

It is therefore possible to use the ideal functionality itself as a building block in future proofs, which is way easier.

Password authenticated key exchange

An authenticated key exchange (AKE) protocol is an interactive protocol between two parties who share an authentication means. At the end of the protocol, the parties should output a session key, a session id and partner id. The correctness requires that any honest AKE execution results in the parties outputting the same session key and session id, and the partner id being the identity of the other party. The goal of the protocol is to guarantee privacy and authentication of the session key in the presence of an attacker.

A password authenticated key exchange (PAKE) is a specific AKE where the authentication means is a common low entropy secret (called the password). It essentially allows to generate a high entropy key from a low entropy secret, interactively. Given the low-entropy nature of the password, it can be guessed, which constitutes a trivial attack against the protocol. Hence the security should only show that one cannot do better than this trivial attack.

Implicit or explicit authentication

AKE protocols have been widely described as having an implicit or explicit authentication. The simplest form is the implicit authentication where, at the end of the protocol, it is unclear if a party knows whether the authentication succeeded or not. We will present in Chapter 3 a new notion, called implicit-only password authenticated key exchange (iPAKE), where no-one can know this without comparing the two sessions keys. The usual goal, however, is explicit authentication where every party involved learns whether the authentication succeeded or not. An implicit AKE can be generically turned into an explicit AKE, at the cost of one additional key confirmation flow [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF].

PAKE in the UC framework

Historical functionality. The original PAKE functionality has been defined by Canetti et al. in [START_REF] Canetti | Universally Composable Password-Based Key Exchange[END_REF]. To distinguish it from the simplified functionnality we'll introduce next, we denote it by F H pake and recall it in Figure 2.1. Three queries are used to model the ideal world: NewSession is used to demonstrate willingness by one of the parties P i to participate in the PAKE. If the adversary S lets the protocol complete, NewKey should be called and the session key sent to the corresponding party. However, the adversary S may also take advantage of the session to try to guess the password itself instead, using the TestPwd query. It may also have corrupted one of the parties, which may change the output of NewKey.

We stress that while this functionality models implicit authentication, it also immediately leaks the result of the TestPwd-query to the adversary: when the adversary tries a password, it learns whether the guess was correct or not but a regular party does not. We will discuss in Chapter 3 a functionality that is less permissive.

The main idea is the following: If neither party is corrupted and the adversary does not attempt any password guess, then the two players both end up with either the same uniformly distributed session key if the passwords are the same, or uniformly distributed independent

The functionality F H pake is parameterized by a security parameter k. It interacts with an adversary S and a set of parties P 1 ,. . . ,P n via the following queries:

• Upon receiving a query (NewSession, sid, P i , P j , pw, role) from party P i :

Send (NewSession, sid, P i , P j , role) to S. If this is the first NewSession query, or if this is the second NewSession query and there is a record (sid, P j , P i , pw ), then record (sid, P i , P j , pw) and mark this record fresh.

• Upon receiving a query (TestPwd, sid, P i , pw ) from the adversary S: If there is a record of the form (P i , P j , pw) which is fresh, then do: If pw = pw , mark the record compromised and reply to S with "correct guess". If pw = pw , mark the record interrupted and reply with "wrong guess".

• Upon receiving a query (NewKey, sid, P i , sk) from the adversary S: If there is a record of the form (sid, P i , P j , pw), and this is the first NewKey query for P i , then:

-If this record is compromised, or either P i or P j is corrupted, then output (sid, sk) to player P i .

-If this record is fresh, and there is a record (P j , P i , pw ) with pw = pw, and a key sk was sent to P j , and (P j , P i , pw) was fresh at the time, then output (sid, sk ) to P i .

-In any other case, pick a new random key sk of length k and send (sid, sk ) to P i .

Either way, mark the record (sid, P i , P j , pw) as completed. session keys if the passwords are distinct. However, if one party is corrupted (the adversary was given the password), or if the adversary successfully guessed the player's password (the session is then marked as compromised), the adversary is granted the right to fully determine its session key. In case of wrong guess (the session is then marked as interrupted), the two players are given independently chosen random keys. A session that is neither compromised nor interrupted is called fresh, which is its initial status.

Remember than in the UC framework, security is determined by how a distinguisher can distinguish the construction from the ideal functionality. Adv pake pake (S, A, Z) thus denotes the advantage the distinguisher Z can get in distinguishing the two worlds. Note that in the ideal functionnality's description, S is described as the adversary and A doesn't appear. This is because it is described from the point of view of the ideal world's security game. However in the distinguishing game S -while still acting as an adversary against the ideal functionnality -is a simulator, A is the real-world adversary and Z is the distinguisher that should be fooled.

When using a UC-PAKE in black box, we will usually assume the existence of a simulator S which makes this advantage negligible for any adversary A, and any distinguisher Z, for the ideal functionality F H pake recalled in Figure 2.1.

The functionality F pake is parameterized by a security parameter λ. It interacts with an adversary S and the (dummy) parties P 0 and P 1 via the following queries:

• Upon receiving a query (NewSession, sid, pw i ) from party P i : -Send (NewSession, sid, P i ) to S;

-If this is the first NewSession query, or if this is the second NewSession query and there is a record (sid, P 1-i , pw 1-i ), then record (sid, P i , pw i ) and mark this record fresh.

• Upon receiving a query (TestPwd, sid, P i , pw i ) from S : If there is a fresh record (sid, P i , pw i ), then do:

-If pw i = pw i , mark the record compromised and reply to S with "correct guess".

-If pw i = pw i , mark the record interrupted and reply with "wrong guess".

• Upon receiving a query (NewKey, sid, P i , sk) from S, where |sk| = λ: If there is no record of the form (sid, P i , pw i ) or this is not the first NewKey query for P i , ignore this query. Otherwise:

-If the record is compromised, P i is corrupted or both P 1-i is corrupted and there is a record (sid, P 1-i , pw 1-i ) with pw i = pw 1-i , then output (sid, sk) to player P i .

-If the record is fresh, both parties are honest and a key sk was sent to P 1-i , at which time there was a fresh record (sid, P 1-i , pw 1-i ) with pw i = pw 1-i , then output (sid, sk ) to P i .

-In any other case, pick a new random key sk of length λ and send (sid, sk ) to P i .

Either way, mark the record (sid, P i , pw i ) as completed. Note that the classical EKE [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF] protocol that encrypts a Diffie-Hellman key exchange, using the password as encryption key, is UC-secure [START_REF] Abdalla | Efficient Two-Party Password-Based Key Exchange Protocols in the UC Framework[END_REF], under the computationnal Diffie-Hellman (CDH) assumption in the ideal cipher (IC) model. In addition, it is quite efficient. But other constructions also exist in the standard model [CHK+05; ACP09], under the decisional Diffie-Hellman (DDH) assumption.

Simpler functionality. The Canetti et al. functionality can actually be simplified in several ways.

The first simplification concerns the role notion. While many protocols actually require a party to be identified as the initiator (or client) and another as the responder (or server), this is actually of little importance. It is perfectly acceptable for the UC functionality not to have this information (which is then actually masked by the simulator S). This gives slightly less power to the adversary, but does not have much impact.

The second simplification concerns the setting. The F H pake functionality is defined as a two-party protocol operating in a setting with n parties. However, the n-party setting is not required, as the composability property is enough to allow to extend the functionality to such a setting. With only two parties, the functionality is slightly simpler.

Lastly, we introduce another change in the functionality, by restricting the power of the adversary to fully determine the key for a party when it has corrupted the other party to the instances for which he holds the correct password. Indeed, it makes no sense for the adversary to be able to select it (and, thus, defeat the authentication) otherwise. Note that this makes our final functionality not strictly equivalent to the one from Canetti et al. [START_REF] Canetti | Universally Composable Password-Based Key Exchange[END_REF], though it shouldn't have a large impact.

We present in Figure 2.2 a simplified PAKE functionality, denoted F pake , that will be used in all the following.

PAKE in the BPR model

The UC framework, for all its usefulness, can be difficult to prove 1 , and a simpler model can allow more efficient constructions to be shown. It is also often a good first step to prove a construction in a gamed-based model and then to try to show it is also secure in the UC framework.

Description. The most well-known game-based model for PAKE is the BPR model first introduced in [BPR00]. While we do not make use of it directly, we will define in Chapter 5, a notion of human authenticated key exchange (HAKE), whose security will be based on it. We thus present it succinctly here.

In the BPR model, the adversary is being given access to oracles representing the parties through the following queries:

• Execute The adversary receives a complete honest session between the two parties (passive network adversary)

• Send The adversary can forge messages to one party (active network adversary)

• Reveal (not allowed if Test was queried on the same session) The adversary receives the final session key (representing a leakage from the subsequent use of the session key).

• Test (not allowed if Reveal was queried on the same session) The adversary is being given either the session key or a random value (depending on a choice bit) and must distinguish.

The goal of the adversary is to either have a non-negligible advantage in distinguishing the two cases for the Test query (privacy property) or to make one oracle think it succeeded the protocol while the other didn't participate (authentication property).

Several variants exist, and notably the real-or-random technique allows to combine the Reveal and Test queries by allowing more than one Test query, with the same choice bit.

The Execute query problem. As one can note from the brief description above, the Execute query is perfectly simulable with Send queries. It actually only represents a commitment on the adversary's part to let an entire session run passively.

This distinction exists for counting purposes only. A passive session is much less dangerous and less costly to achieve than a session where some flows can be modified, and therefore a PAKE should be able to resist more of them.

However, it is actually hard to predict when the adversary is going to be passive and some adversaries may want to adaptively decide to modify flows, depending on the first flows. As such, Execute queries are not very well-suited to correctly count those requests, as this commitment to passivity may not exist in practice2 . In Chapter 5, our BPR-based notion will not rely on Execute queries, but instead determines if a session is active or not (for counting purposes) after the session has occurred.

Other building blocks

Commitment scheme

In several constructions, we will make use of a commitment scheme, a primitive that allows the user to commit on a value x so that the receiver does not learn any information about

x until a later point, but with the guarantee that the user will not be able to change his mind at that later point. UC-secure constructions for commitment scheme exist, but we'll instead introduce a weaker game-based model that will allow more efficient constructions in our protocols.

Syntax.

A (non-interactive) commitment scheme CS is defined by Setup that defines the global public parameters, and two other algorithms:

• Com(x): on input a message x, and some internal random coins, it outputs a commitment c together with an opening value s;

• Open(c, s): on input a commitment c and then opening value s, it outputs either the committed value x or ⊥ in case of invalid opening value.

The correctness condition requires that for every x, if (c, s) = Com(x), then Open(c, s) outputs x.

Game-based security. The usual security notions for commitment schemes are the hiding property, which says that x is hidden from c, and the binding property, which says that once c has been sent, no adversary can open it in more than one way. We respectively denote Adv hiding CS (A) (we will actually never use this one) and Adv binding CS (A) the advantages an adversary may get against these two notions.

Two quite usual additional notions are the extractability and the equivocality properties which state that the simulator, using specially constructed setups, can defeat either the hidding or the binding properties, respectively. For those, we need trapdoors generated by an alternative setup algorithm and privately given to the simulator. And then, the hiding and binding properties are more delicate to be satisfied, hence the additional (probabilistic) algorithms: after a setup phase Setup that defines the global public parameters available to everybody, with additional trapdoors we consider in the global private parameters, available to the simulator, we have:

• SimCom(), that takes as input the trapdoor and outputs a pair (c, eqk) where c is a fake commitment and eqk is the equivocation key;

• OpenCom(c, eqk, m) that takes as input a fake commitment, its equivocation key and a message, and outputs an opening value s;

• ExtCom(c) that takes as input a non-fake commitment and outputs the message m it commits to.

These algorithms must first satisfy the two following properties:

• In the trapdoor setting (when Setup is used), the adversary is not given the trapdoors but just oracle access to the equivocation and extraction capabilities:

• GenEquivCommit() generates (c, eqk) $
← SimCom(), stores (c, eqk) ∈ Ψ, and outputs c;

• OpenEquivCommit(c, m) first looks whether c ∈ Ω in which case it outputs ⊥, otherwise it searches for (c, •) ∈ Ψ, retrieves the matching eqk, stores c ∈ Ω, and outputs s ← OpenCom(c, eqk, m). It outputs ⊥ if no (c, eqk) was found in Ψ;

• ExtractCommit(c) first looks whether (c, •) ∈ Ψ in which case it outputs ⊥, otherwise it outputs m ← ExtCom(c).

The list Ψ is to keep track of the fake commitments, to exclude extraction on them, and the list Ω is to guarantee one opening only for any fake commitment. And then, with unlimited access to these oracles, we still expect the hiding and the binding properties to hold. They can be more formally modeled by the two following properties that, together with the setup indistinguishability, imply both the basic hiding and binding properties (see [START_REF] Abdalla | SPHF-Friendly Non-interactive Commitments[END_REF] for more details):

• (Strong) commitment equivocality indistinguishability: the real commitment algorithms Com/Open and the fake-commitment algorithms SimCom/OpenCom generate indistinguishable commitments and opening values. For any adversary A, we denote by Adv s-eq CS (A) its advantage in distinguishing the commitments and opening values generated by the two kinds of algorithms (even with unlimited access to the oracles GenEquivCommit, OpenEquivCommit, and ExtractCommit). When a commitment scheme satisfies setup indistinguishability, strong commitment equivocality indistinguishability, and strong binding extractability, which additionally imply the basic hiding and binding properties, we say it is strongly secure.

Instantiation. As shown in [START_REF] Abdalla | SPHF-Friendly Non-interactive Commitments[END_REF], UC-secure commitment schemes [CF01; Can01] are strongly secure, and so are enough for us. As a consequence, the UC-secure non-interactive constructions from [FLM11; ABB+13] fulfill all our requirements, in the standard model, with negligible advantages for any adversary, under the Decisional Diffie-Hellman assumption. However they will not be efficient enough for our purpose. On the other hand, the simple commitment scheme that commits m with large enough random coins r into c = H(m, r) is quite efficient and also fulfill all the above requirements, in the random oracle model [START_REF] Bellare | Random Oracles are Practical: A Paradigm for Designing Efficient Protocols[END_REF]:

Proof. Given a hash function H onto {0, 1} λ , the commitment scheme is defined as follows:

• Com(m): Generate r $ ← {0, 1} 2λ and output (c ← H(m, r), s ← (m, r)); • Open(c, s = (m, r)): if H(s) = c, return m, otherwise, return ⊥.
In the random oracle model, this simple scheme is trivially computationally binding (H is collision-resistant) and statistically hiding (for a large r ∈ {0, 1} 2λ , there is almost the same number of possible r -actually 2 λ -for any m, that would lead to the commitment c).

Additionally, we can use the programmability of the random oracle for equivocality and the list of query answer for extractability:

• SimCom() : Return c $ ← {0, 1} λ . • OpenCom(c, •, m) : Generate r $ ← {0, 1} 2λ
, set H(m, r) ← c, and return r.

• ExtCom(c): Search in list of queries to H which one was output to c and return the first corresponding m. If no such query exist, return ⊥.

By construction, we have the equivocality correctness, unless the value H(m, r) has already been asked, which is quite unlikely, since r is a fresh random. Extractability correctness is also ensured, as the recovered value m effectively commits to c. We also have perfect setup indistinguishability, so Adv setup-ind H (A) = 0 for any adversary A. The only way to distinguish a fake commitment from a real commitment would be to ask (m, r) to the oracle before OpenCom, hence to guess r. Therefore Adv s-eq H (A) ≤ q H × 2 -2λ , for any adversary A asking at most q H oracle queries and the scheme has strong commitment equivocability indistinguishability.

Moreover, this scheme has strong binding extractability. Suppose an adversary A is able to produce a tuple (c, s) that breaks the strong binding extractability. Hence if (m , r ) ← ExtCom(c), H(m, r) = H(m , r ). This means that there is a collision between true random values, which is bounded by the birthday paradox. Hence: Adv s-binding

H (A) < q 2
H × 2 -λ . Therefore, this commitment scheme is strongly secure in the random oracle model.

Authenticated encryption

Eventually, for explicit authentication of the players, we will sometimes make use of an authenticated encryption scheme [BN00] ES = (Enc, Dec), where decryption should fail when the cipher text has not been properly generated under the appropriate key. This will thus provide a kind of key confirmation, as usually done to achieve explicit authentication. However, some critical data will have to be sent, hence a simple MAC would not be enough, privacy of the content is important too.

For an authenticated encryption scheme, there are two main simulation-based security notions: The semantic security, aka indistinguishability under chosen plaintext attacks (IND-CPA), prevents any information being leaked about the plain texts, while the integrity of cipher texts, aka INT-CTXT, essentially says that no valid cipher text can be produced without the key. The definitions of the corresponding advantages Adv int-ctxt ES (A) and Adv ind-cpa ES (B), for any adversaries A, B can be found in [START_REF] Bellare | Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm[END_REF]. In addition, for adversaries A, B there exists an adversary C for which we define Adv authenc

ES (C) = max{Adv int-ctxt ES (A), Adv ind-cpa ES (B)}.
One simple way to achieve secure authenticated encryption is by using a generic Encryptthen-MAC approach [START_REF] Bellare | Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm[END_REF] or by using a dedicated scheme such as OCB [START_REF] Rogaway | OCB: A Block-Cipher Mode of Operation for Efficient Authenticated Encryption[END_REF].

Linear codes

A linear q-ary code of length n and rank k is a subspace C with dimension k of the vector space F n q . The vectors in C are called codewords. The size of a code is the number of codewords, and is thus equal to q k . The weight of a word w ∈ F n q is the number of non-zero components and the distance between two words is the Hamming distance between them (equivalently, the weight of their difference). The minimal distance d of a linear code C is the minimum weight of its non-zero codewords, or equivalently, the minimum distance between any two distinct codewords.

A code for an alphabet of size q, of length n, rank k, and minimal distance d is called a (n, k, d) q -code. Such a code can be used to detect up to d -1 errors (if a codeword is sent and fewer than d -1 errors occur, it cannot get transformed into another codeword), or correct up to (d -1)/2 errors (for any received word, there is a unique codeword within distance (d -1)/2 ). For linear codes, encoding of a (row vector) word W ∈ F k q is performed by an algorithm C.Encode : F k q → F n q , which is the multiplication of W by a matrix G ∈ F k×n q , called the "generating matrix" (which defines an injective linear map). This leads to a row-vector codeword c ∈ C ⊂ F n q . We also denote C.Decode : F n q → F k q the decoding algorithm for the correcting property mentioned before, that is ∀W ∈ F k q , ∀c ∈ F n q and c = C.Encode(W ), if c and c differ by at most (d -1)/2 coordinates, C.Decode(c ) = W . The Singleton bound states that for any linear code, k + d ≤ n + 1, and a maximum distance separable (MDS) code satisfies k + d = n + 1. Hence, MDS codes are fully described by the parameters (q, n, k). Such a (n, k) q -MDS code can correct up to (nk)/2 errors; it can detect if there are errors, whenever there are no more than nk of them.

For a thorough introduction to linear codes and proof of all statements in this short overview we refer the reader to [START_REF] Roth | Introduction to coding theory[END_REF].

Observe that a linear code, due to the linearity of its encoding algorithm, is not a primitive designed to hide anything about the encoded message. However, we show in Lemma 2.3.5 that a MDS code can be turned into a robust secret sharing (RSS) scheme, which is designed just for that and is presented next.

Robust secret sharing

Notion. We recall the definition of a RSS, slightly simplified for our purposes from [START_REF] Cramer | Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions[END_REF]. ∀c ∈ F n q , ∀A ⊂ 1, n , we denote by c A = (c i ) i∈A the projection of c into F |A| q . Definition 2.3.1. Let F q be a finite field. A (n, t, r) -RSS consists of two probabilistic algorithms Share : F q → F n q and Reconstruct : F n q → F q with the following properties:

• t-privacy: ∀s, s ∈ F q , ∀A ⊂ 1, n with |A| ≤ t, the restrictions c A and c A of c ← Share(s) and c ← Share(s ) to the coordinates in A are identically distributed.

• r-robustness ∀s ∈ F q , ∀A ⊂ 1,

n with |A| = r, c ← Share(s), if c is such that cA = c A it holds that Reconstruct(c) = s.
In other words, a RSS is able to reconstruct the shared secret even if the adversary tampered with up to nr shares, while each set of t shares is distributed independently of the shared secret, and thus reveals nothing about it. This definition allows for a gap, i.e. r ≥ t + 1 and RSS that have r > t + 1 are called in the literature ramp RSS.

Among other things, our definition of robustness above is slightly simplified from the one in [START_REF] Cramer | Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions[END_REF] which allowed for a slight probability δ of not reconstructing the secret. However, since we are interested in settings where r ≤ n/3, such a provision is not required. Indeed, we will construct a suitable RSS based on MDS linear codes, which has perfect robustness.

Remark 2.3.2. In Definition 2.3.1, c Ā -that is, the coordinates of c that are not in Ais determined by the adversary. A slightly weaker notion of robustness could be constructed by randomly sampling it instead. Such a weaker notion would be enough for all purposes in this thesis but, for the sake of simplicity we will retain the notion defined above in the following.

We now introduce a new RSS property called smoothness. Intuitively, it means that getting a set of shares with a small number of them correct and the others random leaks no information (computationally) on the shared secret. It can be considered either for any secret, or for a randomly chosen secret as well.

In the following, let Ā be the complement of A in 1, n , i.e. Ā = 1, n .

Definition 2.3.3 (Smoothness). We say that an (n, t, r) q -RSS is

• m-smooth if for any s ∈ F q , A ⊂ 1, n with |A| ≤ m, any c output by Share(s), and

any c such that cA = c A , c Ā $ ← F n-|A| q
, for all PPT A it holds that

| Pr[1 ← A(1 λ , Reconstruct(c))] -Pr[1 ← A(1 λ , u)]|
is negligible in λ, where the probability is taken over the random coins of A and Reconstruct and u $ ← F q .

• m-smooth on random secrets if it is m-smooth for randomly chosen s $ ← F q and the probabilities are additionally taken over the coins consumed by this choice.

We also introduce strong t-privacy, a slightly stronger notion of privacy than the one from the origin RSS definition above. Definition 2.3.4 (Strong t-privacy). We say that an (n, t, r) q -RSS has strong t-privacy, if for any s ∈ F q , A ⊂ [n] with |A| ≤ t, the projection c A of c $ ← Share(s) is distributed uniformly randomly in F |A| q . Note that while strong t-privacy implies t-privacy, the opposite does not necessarily hold (imagine a Share algorithm creating shares that start with "I'm a share!"). Note that, in case of random errors occuring, as long as there are fewer then t undisturbed shares, a strong t-private scheme actually hides the locations (and with this also the number) of errors.

The following Lemma shows that we can construct RSS directly from MDS linear codes. • Share(s) for s ∈ F q first chooses a random row vector W ∈ F k q such that W • L = s, and outputs c ← C .Encode(W ) (equivalently, we can say that Share(s) chooses a uniformly random codeword of C whose last coordinate is s, and outputs the first n coordinates as c).

• Reconstruct(w) for w ∈ F n q first runs C .Decode(w). If it gets a vector W , then output

s = W • L, otherwise output s $ ← F q .
Then Share and Reconstruct form a t-smooth, strongly t-private (n, t, r) q -RSS for t = k -1 and r = (n + k)/2 that is (r -1)-smooth on random secrets.

Proof. Let us consider the two properties from Definition 2.3.1.

• strong t-privacy: Assume |A| = t (privacy for smaller A will follow immediately by adding arbitrary coordinates to it to get to size t). Let J = A ∪ {n + 1}; note that

|J| = t + 1 = k.
Note that for the code C, any k coordinates of a codeword determine uniquely the input to Encode that produces this codeword (otherwise, there would be two codewords that agreed on k elements and thus had distance nk + 1, which is less than the minimum distance of C). Therefore, the mapping given by Encode J :

F k q → F |J| q
is bijective; thus coordinates in J are uniform when the input to Encode is uniform. The algorithm Share chooses the input to Encode uniformly subject to fixing the coordinate n + 1 of the output. Therefore, the remaining coordinates (i.e., the coordinates in A) are uniform. • t-smoothness: to prove this, we show that disturbing one share uniformly random already randomizes the output of Reconstruct. Let D denote the set chosen by Decode. Since every codeword is uniquely determined by k elements, the mappings f i :

F q → F q , x → Encode(G -1 D (c)) n+1 with c ← F k q , c i = x are bijective for all i ∈ [k]. Since t = k -1
, cD contains at least one entry that is chosen uniformly at random and thus the claim follows from the fact that the output of Reconstruct is computed as Encode(G -1 D (•)). • (r -1)-smoothness on random secrets: first, it holds that r -1 > k and thus c contains more than k undisturbed shares. We distinguish two cases. Either D chosen by Decode contains only undisturbed shares (i.e., D ⊆ A), then Reconstruct will output s which is distributed uniformly random in F q . Else, D ⊆ A. In this case, at least one element of cD is distributed uniformly random and the randomness of the output of Reconstruct follows as in the proof of t-smoothness.

Note that the Shamir's secret-sharing scheme is exactly the above construction with Reed-Solomon codes [START_REF] Mceliece | On Sharing Secrets and Reed-Solomon Codes[END_REF].

Models as UC functionalities

We recall in this section several classical models in cryptography, viewed as UC ideal functionality. While they are not usually instantiable, which means that proofs based on those have less implications, they still give a good intuition as of to why a protocol ought to be secure. We will therefore make use of them in several security proofs.

Common reference string. The common reference string (CRS) functionality was defined in [START_REF] Canetti | Obtaining Universally Compoable Security: Towards the Bare Bones of Trust (Invited Talk)[END_REF]. We recall it in Figure 2.3 for completeness. Note that we do not let F CRS check whether a party is allowed to obtain the CRS, but the latter can be assumed public.

The functionality F D

CRS is parametrized with a distribution D and proceeds as follows:

• Upon receiving (sid, crs), if there is no value r recorded, then choose and record a value r $ ← D and reply with (sid, r). Ideal cipher. An ideal cipher (IC) [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF] is a block cipher that takes a plain text or a cipher text as input. We describe the IC functionality F IC in Figure 2.5, in the same vein as the above RO functionality. Notice that the ideal cipher model UC-emulates this functionality. Note that this functionality characterizes a perfectly random permutation, by ensuring injectivity for each query simulation.

The functionality F RO proceeds as follows, running on security parameter λ, with a set of (dummy) parties P 1 , . . . , P n and an adversary S:

• F RO keeps a list L (which is initially empty) of pairs of bit strings.

• Upon receiving a value (sid, m) (with m ∈ {0, 1} * ) from some party P i or from S, do:

-If there is a pair (m, h) for some h ∈ {0, 1} λ in the list L, set h := h.

-If there is no such pair, choose uniformly h ∈ {0, 1} λ and store the pair (m, h) ∈ L. Once h is set, reply to the activating machine (either P i or S) with (sid, h). The functionality F IC takes as input the security parameter κ, and interacts with an adversary S and with a set of (dummy) parties P 1 , . . . , P n by means of these queries:

• F IC keeps an (initially empty) list L containing 3-tuples of bit strings and a number of (initially empty) sets C ek and M ek .

• Upon receiving a query (sid, E, ek, m) (with m ∈ {0, 1} κ ) from some party P i or S, do:

-If there is a 3-tuple (ek, m, c) for some c ∈ {0, 1} κ in the list L, set c := c.

-If there is no such record, choose uniformly c in {0, 1} κ \C ek which is the set consisting of cipher texts not already used with ek. Next, it stores the 3-tuple (ek, m, c) ∈ L and sets both M ek ← M ek ∪ {m} and C ek ← C ek ∪ {c}.

Once c is set, reply to the activating machine with (sid, c).

• Upon receiving a query (sid, D, ek, c) (with c ∈ {0, 1} κ ) from some party P i or S, do:

-If there is a 3-tuple (ek, m, c) for some m ∈ {0, 1} κ in L, set m := m.

-If there is no such record, choose uniformly m in {0, 1} κ \M ek which is the set consisting of plain texts not already used with ek. Next, it stores the 3-tuple (ek, m, c) ∈ L and sets both M ek ← M ek ∪ {m} and

C ek ← C ek ∪ {c}.
Once m is set, reply to the activating machine with (sid, m). Implicit-only PAKE

Motivation

Password authenticated key exchange (PAKE) is a cryptographic primitive that aims at allowing two parties sharing a low-entropy secret (the password) to interactively establish a high-entropy random session key. Two types of authentication have been considered: implicit authentication, where at the end of the protocol the two parties share the same key if they used the same password and random independent keys otherwise; or explicit authentication where, in addition, they actually know which of the two situations happened. A PAKE protocol that only achieves implicit authentication can be enhanced to have explicit authentication by adding key-confirmation flows [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF]. For more details about this primitive, one can refer to Section 2.2 of Chapter 2. Its standard universal composability (UC) ideal functionality F pake based on [CHK+05] (see Figure 2.2), while only achieving implicit authentication, was designed with explicit authentication in mind. Thus, it allows the adversary (but not the player) to know whether a password guess attempt was successful or not. In most settings this is reasonable, because success or failure can anyway be determined by trying to use the key established by the PAKE. However, some applications, such as the one we design in the next chapter, could make use of a PAKE that does not internally provide any feedback, even to the adversary.

Definition

Implicit-only. Hence, we introduce a new notion, called implicit-only password authenticated key exchange (iPAKE), as a stronger notion of PAKE. Its ideal functionality, presented in Figure 3.1, models the complete absence of feedback: the two players get back the session keys, but neither them nor the adversary can know if the protocol succeeded. Of course, in many cases, the players can later check whether the keys match or not, and so whether the passwords were the same or not, but this would actually depend on the protocol using the keys. Hence, we stress that this is not a leakage from the iPAKE protocol itself, but from the global system.

In terms of functionalities, there is only one relatively minor differences from F pake to F iPAKE , namely the fact that TestPwd-query now silently updates the internal state of the record, meaning that its outcome is not given to the adversary S as before. We stress that a NewKey-query can only be asked for a player P i that has previously issued a NewSession-

-21 -
The functionality F iPAKE is parameterized by a security parameter λ. It interacts with an adversary S and the (dummy) parties P 0 and P 1 via the following queries:

• Upon receiving a query (NewSession, sid, pw i ) from party P i : -Send (NewSession, sid, P i ) to S;

-If this is the first NewSession query, or if this is the second NewSession query and there is a record (sid, P 1-i , pw 1-i ), then record (sid, P i , pw i ) and mark this record fresh.

• Upon receiving a query (TestPwd, sid, P i , pw i ) from S : If there is a fresh record (sid, P i , pw i ), then do:

-If pw i = pw i , mark the record compromised;

-If pw i = pw i , mark the record interrupted.

• Upon receiving a query (NewKey, sid, P i , sk) from S, where |sk| = λ: If there is no record of the form (sid, P i , pw i ) or this is not the first NewKey query for P i , ignore this query. Otherwise:

-If the record is compromised, P i is corrupted or both P 1-i is corrupted and there is a record (sid, P 1-i , pw 1-i ) with pw i = pw 1-i , then output (sid, sk) to player P i .

-If the record is fresh, both parties are honest and a key sk was sent to P 1-i , at which time there was a fresh record (sid, P 1-i , pw 1-i ) with pw i = pw 1-i , then output (sid, sk ) to P i .

-In any other case, pick a new random key sk of length λ and send (sid, sk ) to P i .

Either way, mark the record (sid, P i , pw i ) as completed. query. If its partner P 1-i is corrupted, either a NewSession-query has been sent for it, which means that P 1-i got adaptively corrupted afterwards, and only matching passwords could provide it some control on the session key computed by P i , or no NewSession-query has been issued for P 1-i then only a TestPwd-query can impact the key received by P 1-i . Without a TestPwd-query, in the latter case, P 1-i receives a random session key.

Labeled implicit-only. We can also slightly alter this functionality to allow for public labels in Figure 3.2. We call this new functionality labeled implicit-only password authenticated key exchange (liPAKE), resembling the notion of labeled public-key encryption as formalized in [START_REF] Shoup | A Proposal for an ISO Standard for Public Key Encryption[END_REF]. In a nutshell, labels are public authenticated strings that are chosen by each user individually for each execution of the protocol. Here authenticated is relative to the authentication of the PAKE, meaning that tampering can be efficiently detected by the other user. i.e. if a user chooses label , it is required for the authentication to succeed (which, in the context of a iPAKE, only means that the final keys are equal) that the other user actually receives . In the next chapters, those labels will be used to distribute public information (such as public keys) reliably over an unauthenticated channel.

The functionality F liPAKE is parameterized by a security parameter λ and makes use of two initially empty lists Λ P and Λ L , storing passwords and labels, respectively. It interacts with an adversary S and the (dummy) parties P 0 and P 1 via the following queries:

• Upon receiving a query (NewSession, sid, pw i , ) from party P i : -Send (NewSession, sid, P i , ) to S;

-If this is the first NewSession query, or if this is the second NewSession query and there is a record (sid, P 1-i , pw 1-i ) in Λ P : * Record (sid, P i , pw i ) in Λ P and mark this record fresh. * Unless there exists a record (sid, P i , •), record (sid, P i , ) in Λ L .

• Upon receiving a query (TestPwd, sid, P i , pw i , ) from S : If there is a fresh record (sid, P i , pw i ) in Λ P , then do:

-If pw i = pw i , mark the record compromised; else mark it interrupted;

-Remove any previously existing record of the form (sid, P 1-i , •) and store (sid, P 1-i , ) in Λ L .

• Upon receiving a query (NewKey, sid, P i , sk) from S, where |sk| = λ: If there is a record (sid, P 1-i , ) in Λ L , extract from it; otherwise set ← ⊥ If there is no record of the form (sid, P i , pw i ) in Λ P or this is not the first NewKey query for P i , ignore this query. Otherwise:

-If the record is compromised, P i is corrupted or both P 1-i is corrupted and there is a record (sid, P 1-i , pw 1-i ) in Λ P with pw i = pw 1-i , then output (sid, , sk) to player P i .

-If the record is fresh, both parties are honest and a key sk was sent to P 1-i , at which time there was a fresh record (sid, P 1-i , pw 1-i ) with pw i = pw 1-i , then output (sid, , sk ) to P i ;

-In any other case, pick a new random key sk of length λ and send (sid, , sk ) to P i .

Either way, mark the record (sid, P i , pw i ) as completed.

Figure 3.2: Functionality F liPAKE

In the next section, we will present a protocol (Figure 3.3) and prove it is a UC-secure liPAKE.

Instantiation

In the seminal paper by Bellovin and Merritt [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF] that introduced PAKE, they propose the Encrypted Key Exchange protocol (EKE), which is essentially a Diffie-Hellman [DH76] key exchange, with the two flows encrypted under the password with an appropriate symmetric encryption scheme. This EKE protocol has been formalized by Bellare et al. [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF] under EKE2. We present its labeled variant in Figure 3.3. The idea of appending the label to the symmetric key is taken from [START_REF] Abdalla | Efficient Two-Party Password-Based Key Exchange Protocols in the UC Framework[END_REF].

A(pw ∈ P, ∈ L) B(pw ∈ P, ∈ L) x $ ← Z q , X ← g x X * ← E pw|| (X) , X * -------→ y $ ← Z q , Y ← g y , Y * ← -------Y * ← E pw || (Y ) Z ← D pw|| (Y * ) x Z ← D pw || (X * ) y sk ← H(X * , Y * , Z) sk ← H(X * , Y * , Z ) output ( , sk)
output ( , sk ) Figure 3.3: Protocol EKE2, in a group G = g of prime order q, with a hash function

H : {0, 1} κ × {0, 1} κ × G → {0, 1} λ and a symmetric cipher E : G → {0, 1} κ , D : {0, 1} * → G for keys in P × L.
The following theorem proves security in the F RO , F IC , F CRS -hybrid model, meaning that we use an ideal random oracle functionality F RO as the hash function, an ideal cipher functionality F IC to model the encryption scheme and assume a publicly available common reference string modeled by its functionality F CRS . We note that this result is not surprising given that other variants of EKE2 have already been proven to UC-emulate F pake . Intuitively, a protocol with only two flows not depending on each other does not leak the outcome to the adversary via the transcript, which explains why EKE2 is implicit-only. Hashing of the transcript keeps the adversary from biasing the key unless he knows the correct password or breaks the ideal cipher. For completeness, we include the full proof below.

Proof. We proceed in a serie of games, starting with the real execution of the protocol and ending up with the ideal execution, with a simulator. For convenience, we refer to a query (NewKey, sid, P i , , sk) from the adversary S as due when:

• P i is honest
• there is a fresh record of the form (sid, P i , pw i ) in Λ P

• this is the first NewKey query for

P i • there is a record (sid, P 1-i , pw 1-i ) in Λ P with pw i = pw 1-i
• a key sk was sent to the other party, and (sid, P 1-i , pw 1-i ) was fresh at the time.

Game G 0 : The real protocol execution. This is the real execution where the environment Z runs the EKE2 protocol (see Figure 3.4) with parties P 0 and P 1 , both having access to ideal common reference string (CRS), random oracle (RO), and ideal cipher (IC) functionalities, and an adversary A that, w.l.o.g., is assumed to be the dummy adversary as shown in [Can01, section 4.4.1].

The parties P 0 and P 1 are running with F CRS , F RO and F IC . Protocol Steps:

1. When a party P i receives an input (NewSession, sid, P i , pw i , ) from Z, it does the following:

• If P i = P 1 , it does nothing and waits for a message from P 1-i

• If P i = P 0 , P i first chooses x $ ← Z q . P i then sends (sid, crs) to F CRS and receives (sid, (g, q)) back sends (sid, E, pw i || , g x ) to F IC and receives (sid, X * ) back sends (sid, , X * ) to P 1-i and waits for an answer 2. When P 1 , who already obtained an input (NewSession, sid, P 1 , pw 1 , ), receives a message (sid, , X * ) from P 0 , it first chooses y $ ← Z q . P 1 then

• sends (sid, crs) to F CRS and receives (sid, (g, q)) back

• sends (sid, E, pw 1 || , g y ) to F IC and receives (sid, Y * ) back

• sends (sid, , Y * ) to P 0

• sends (sid, D, pw 1 || , X * ) to F IC and receives (sid, X ) back

• sends (sid, X * , Y * , X y ) to F RO and receives (sid, sk) back P 1 then outputs (sid, , sk) towards Z and terminates the session.

F RO F IC F CRS P i P 1-i A Z Z F S P i P 1-i F RO F IC F CRS A Figure 3.5: Transition from Game G 0 (left) to Game G 1 (right),
showing a setting where

P 1-i is corrupted.
Game G 1 : Modeling the ideal layout. We first make some purely conceptual changes that do not modify the input/output interfaces of Z. We add one relay (also referred to as the dummy party) on each of the wires between Z and a party. We also add one relay covering all the wires between the dummy parties and real parties and call it F (and let F relay messages according to the original wires). We group all the formerly existing instances except for Z into one machine and call it S. Note that this implies that S executes the code of the CRS, RO and IC functionalities as depicted in Figures 2.3, 2.4, and 2.5.

Game G 2 : Simulating the ideal functionalities. We modify simulation of F RO and F IC as follows. We let S implement Figure 2.5 by maintaining a list Λ IC with entries of the form (sid, k, m, α, E|D, c). S handles encryption and decryption queries as follows:

• Upon receiving (sid, E, ek, m) (for shortness of notation, we will also write E ek (m) for this query) if ek / ∈ P × L or m / ∈ G then abort. Else, if there is an entry (sid, ek, m, * , * , c) in Λ IC , S replies with (sid, c). Else, S chooses c $ ← {0, 1} κ . If there is already a record ( * , * , * , * , * , c) in Λ IC , S aborts. Else, S adds (sid, sk, m, ⊥, E, c) to Λ IC and replies with (sid, c).

• Upon receiving (sid, D, ek, c) (or D ek (c), for short), if ek / ∈ P × L or c / ∈ {0, 1} κ then abort. Else, if there is an entry (sid, ek, m, * , * , c) in Λ IC , S replies with (sid, m). Else, S chooses α ← Z q .
If there is already a record ( * , * , g α , * , * , * ) in Λ IC , S aborts. Else, S adds (sid, sk, g α , α, D, c) to Λ IC and replies with (sid, g α ).

Similarly, let Λ RO denote the list that S maintains upon implementing Figure 2.4, containing entries of the form (sid, m, h). We let S handle queries to F RO as follows: We note that these modifications later allow S to extract unique inputs from values obtained using the two functionalities. In particular, note that Λ IC will never contain (sid, ek, * , * , E, c), (sid , ek , * , * , E, c) with ek = ek . The entry α serves S as a trapdoor for solving discrete-log type problems.

• Upon receiving H(m), if m / ∈ {0, 1} κ × {0, 1} κ × G,
Since q is greater than 2 λ , if the oracles are only queried a polynomial number of times, the birthday problem states that Game G 1 and Game G 2 are indistinguishable with probability overwhelming in λ.

Game G 3 : Building F iPAKE . In this game, we start modeling F liPAKE . First, we let F maintain two initially empty lists: Λ P , a list of tuples of the form (sid, P i , pw i ) and Λ L , a list of tuples of the form (sid, P i , ). Upon receiving a query (NewSession, sid, pw i , ) from (dummy) party P i , if this is the first NewSession query, or if this is the second NewSession query and there is a record (sid, P 1-i , pw 1-i , ), then F records (sid, P i , pw i ) in Λ P and marks this record as fresh. If Λ L does not contain any record (sid, P i , •) so far, F also records (sid, P i , ) in Λ L . Then, F relays the query (NewSession, sid, pw i , ) to S. Now that F knows about passwords and labels, we can add an TestPwd interface to F as described in Figure 3.1. We let S parse outputs (sid, , sk) towards F to be of the form (NewKey, sid, P i , , sk) by adding the NewKey tag and the name of the party who produced the output. Additionally, we let F translate this back to (sid, , sk) and send it to Z via the dummy party P i .

Obviously none of these modifications change the output towards Z compared to the previous Game G 2 .

Game G 4 : F generates a random session key for an honest, interrupted session. Upon receiving a query (NewKey, sid, P i , sk) from S, if P i is not corrupted and there is a record of the form (sid, P i , pw) that is marked as interrupted, and this is the first NewKey query for P i , we let F choose a random session key sk * of length λ. Additionally, F derives the label as follows: if there is a record (sid, P 1-i , * ) in Λ L , extract * from it; otherwise, set * ← ⊥. Then, F outputs (sid, * , sk * ) to P .

If there is no such interrupted record, F continues to relay sk and .

Since the simulators described in Game G 3 and Game G 4 do not make use of the TestPwd interface, none of the records of F are marked as interrupted and thus the output towards Z is equally distributed in both games.

Game G 5 : S handles dictionary attacks against the client P 0 using the TestPwd interface. If both P 0 and P 1 are honest, P 0 obtained input and Z advises A to substitute (sid, , Y * ) with (sid, Z , Y * Z ), or if P 1 is corrupted and produces (sid, Z , Y * Z ) as first flow, then S will proceed with the simulation of P 0 using Z and Y * Z . In this situation, we modify S as follows: upon receiving (sid, Z , Y * Z ) if there is an entry 1 (sid, pw Z || ˆ , * , * , E, Y * Z ), for any ˆ ∈ L in Λ IC , S asks a TestPwd query Chapter 3 Implicit-only PAKE (TestPwd, sid, P 0 , pw Z , Z ) to F. S then proceeds the simulation2 using pw Z and Z instead of pw and . If there is no entry (sid, pw Z || ˆ , * , * , E, Y * Z ) in Λ IC , S sends (TestPwd, sid, P 0 , pw 0 , Z ) to F.

Regarding the label, observe that S's NewKey query will contain Z which was contained in the output of the honest P 0 (cf. Figure 3.4). Since TestPwd queries overwrite any existing labels, there will be an entry (sid, P 1 , Z ) in Λ L and thus, regarding the label, the output towards Z does not change compared to the previous game. Regarding the session key, we have to analyze different cases depending on whether Y * Z was generated using F IC or not. However, observe that the only changes of session keys between this and the previous game occur whenever a TestPwd query of S causes a record to be marked as interrupted.

• There is an entry (sid, pw Z || ˆ , * , * , E, Y * Z ) in Λ IC : if pw Z = pw 0 , the record is marked compromised and the session key is not changed by F. If pw Z = pw 0 , on the other hand, the record is marked interrupted and F hands out a random session key, as opposed to Game G 4 . However, since the session key is distributed as before, Z can only detect this by reproducing

P 0 's input (sid, X * , Y * Z , CDH(D pw 0 || (X * ), D pw 0 || Z (Y * Z )) to F RO . Lemma 3.3.2 (see below) shows indistinguishability of Game G 4 and Game G 5 .
• There is no entry (sid, * , * , * , E, Y * Z ) in Λ IC : since the TestPwd query will result in a compromised record, the modified simulation has no impact on the output towards Z in this case.

The following lemma bounds the probability that an unsuccessful dictionary attack leads to a non-random looking session key. Since in this case the labels do not play any role (the encryption keys of the form password||label will not match regardless of the labels), we ignore them for the sake of simplicity.

Lemma 3.3.2. If CDH holds in G, then ∀(pw 0 , ) ∈ P × L, Y * Z ← Z, where Y * Z is a cipher text generated through F IC with some key (pw Z , Z ) = (pw 0 , ), it holds that Pr G 5 [CDH(D pw 0 || (X * ), D pw 0 || (Y * Z )) ← Z(X * )] = negl(λ).
Proof. We create an attacker B CDH given a CDH instance (g, A = g a , B = g b ). B CDH runs Z simulating Game G 5 as follows: B CDH internally runs all of the participating machines, i.e. S, F and the dummy parties as in Game G 5 , but with some modifications. First, B CDH computes X * ← E pw 0 || (A) and updates Λ IC accordingly, aborting if there was already an entry (sid, pw 0 || , A, * , E, * ). Upon receiving a query D pw 0 || (Y * Z ), B CDH again aborts if there is already an entry (sid, pw 0 || , * , * , E, Y * Z ). Otherwise, it draws β $ ← Z q and sets the answer to this query to be Bg β . This can happen multiple times (for different Y * Z ), and B CDH keeps track of the pairs (β, Y * Z ) in a list Λ CDH . The last modification concerns the part of the simulator's code of Game G 5 where a value

Z ← D pw 0 || (Y * ) a needs to be computed, but note that B CDH does not know a. Instead, B CDH just sets Z ← ⊥.
Finally, B CDH picks a random entry from Λ RO asked by Z, parses it into the tuple (sid, pw 0 || , X * , Y * Z , Z), h), looks for an entry (β, Y * Z ) in Λ CDH and outputs Z/(g a ) β as a CDH solution.

First, note that if B CDH does not abort, it perfectly emulates Z's view in Game G 5 , since A, Bg β are random in G and the record for P 0 will be interrupted, which means that F will output a random session key for P 0 , overwriting ⊥. However, it is obvious that B CDH only has to abort if there is a collision upon choosing random values from G.

Assume that Z outputs CDH(D pw 0 || (X * ), D pw 0 || (Y * Z )
) with non-negligible probability. This is only possible if Z asked both corresponding decryption queries. Existence of (sid, pw Z || Z , * , * , E, Y * Z ) with (pw Z , Z ) = (pw 0 , ) in Λ IC ensures that the answer to D pw 0 || (Y * Z ) can be chosen by B CDH as described above. Thus, B CDH finds a correct CDH solution with probability 1/q Z , where q Z is the number of hash queries issued by Z.

Game G 6 : S handles dictionary attacks against the server P 1 using the TestPwd interface. Analogously to Game G 5 , we let S use the TestPwd interface upon receiving adversarially generated X * Z , Z upon simulating P 1 . Observe that the only difference is due to the order of flows: if S extracts an incorrect password, he produces Y * using this wrong password. However, Y * will be distributed as before and again, Z can only detect the change by reproducing

P 1 's input to F RO , namely (sid, X * Z , Y * , CDH(D pw 1 || Z (X * Z ), D pw 1 || (Y * ))
. Using an analogous argument to Lemma 3.3.2, indistinguishability from Game G 5 follows from the hardness of CDH in G.

Game G 7 : F aligns session keys. Upon receiving a query (NewKey, sid, P i , , sk) from S for a session where none of the players is corrupted, if this query is due then output (sid, * , sk * ) to P i where sk * is the session key that was formerly sent to the other party and the label * is derived as usual: if there is a record (sid, P 1-i , * ) in Λ L , extract * from it; otherwise, set * ← ⊥.

We now analyze distinguishability of this game from Game G 6 . If Z tampered with the transcript, any player that received a modified message will not have a fresh record anymore (cf. simulation described in games G 5 and G 6 ) and the output of this player towards Z is not changed in this game. On the other hand, if Z does not advise A to tamper with any message, F did not overwrite any labels and thus * = . Additionally, perfect correctness of the EKE2 protocol ensures that in case of a due record sk = sk * . Note that F still differs from the functionality F liPAKE described in Figure 3.1 in some aspects. First, it does not output randomly generated session keys towards Z for honest sessions. Furthermore, it reports all passwords to S. We will take care of these remaining differences in the next games.

Game G 8 : In some cases, F generates a random session key when the other party is corrupted. Upon receiving a NewKey query (NewKey, sid, P i , , sk) from S, if there is a fresh record of the form (sid, P i , pw i ) in Λ P , and this is the first NewKey query for P i , P i is honest and P 1-i corrupted and there is a record (sid, P 1-i , pw 1-i ) in Λ P with pw i = pw 1-i , we let F pick a new random key sk * of length λ and send (sid, * , sk * ) to P i , where * , as usual, is taken from the list Λ L or set to be ⊥.

The simulation ensures that the record (sid, P i , pw i ) is either compromised or interrupted (cf. description of the simulator in games G 5 and G 6 ). Thus, the modification has no effect since it only concerns fresh records.

Game G 9 : F generates a random session key for an honest session. Upon receiving a NewKey query (NewKey, sid, P i , , sk) from S, if there is a fresh record of the form (sid, P i , pw i ) in Λ P , and this is the first NewKey query for P i , both parties are honest and the NewKey query is not due, we let F pick a new random key sk * of length λ and send (sid, * , sk * ) to P i , where * , as usual, is taken from the list Λ L or set to be ⊥.

In other words, F now generates a random session key upon a first NewKey query for an honest party P i with fresh record (sid, P i , pw i ) where the other party is also honest if (at least) one of the following events happens:

1. There is a record (sid, P 1-i , pw 1-i ) in Λ P with pw i = pw 1-i ;

2. No output was sent to the other party yet;

3. If there was output to the other party, the record (sid, P 1-i , pw 1-i ) in Λ P was not fresh and thus interrupted or compromised at that time In all of these cases, S chose a fresh sk following a uniform distribution and was contained in the NewSession query of P i 's partner, thus = * . Regarding the session key, Z can only notice a difference if it reproduces sk by computing

P i 's input (sid, X * , Y * , CDH(D pw i || (X * ), D pw i || (Y * ))
to F RO and sending it to F RO via the adversary A.

The following lemma bounds the probability that a session key of an unattacked session does not look random.

Lemma 3.3.3. If CDH holds in G, then ∀pw, , ← Z with pw ∈ P, , ∈ L it holds that Pr G 9 [CDH(D pw|| (X * ), D pw|| (Y * )) ← Z(X * , Y * )] = negl(λ).
Proof. We only sketch the proof since it is similar to the proof of Lemma 3.3.2. Namely, the strategy of embedding (randomized versions of) a CDH challenge into the simulation of Game G 9 is done by just encrypting both CDH challenge elements to obtain X * and Y * . For the final argument, note that ⊥ is not seen by Z since it is either replaced using a random session key or a previously computed key.

It follows that Game G 8 and Game G 9 are indistinguishable.

Game G 10 : F always takes all labels from the list Λ L . We modify F as follows: if F outputs (sid, , sk) towards P i where , sk are taken from a query (NewKey, sid, P i , , sk) from S, F extracts * from a record (sid, P 1-i , * ) in Λ L or sets * ← ⊥ if such a record does not exist. F then outputs (sid, * , sk) towards P i . We additionally modify S to remove the labels from the NewKey queries altogether.

First observe that we can remove the labels from the NewKey queries because, in this and the past games, we ensured that F never accesses this label. However, we still have to argue indistinguishability of this and the previous game. The cases where sk of S is relayed by F towards P i are the following:

• P i has a compromised record

• P i is corrupted
• P i has a fresh record, its partner is corrupted and has a record with a matching password

In the first case, we have that = * since the label output by P i was also contained in a TestPwd query by S and overwrote any existing label send by P i 's partner. For the second case, observe that since we restrict to static corruption, corrupted players will not have records in Λ P and thus this case will never happen. In the third case, corruption of the partner ensures that S issued a TestPwd query which overwrote any existing label with , so = * as well.

Observe that now F acts like F liPAKE regarding the output of session keys. The only remaining difference is that the NewSession queries still contain the passwords of the parties. In the next games, we will make the simulation independent of these passwords.

Game G 11 : Simulate without pw 1 if the server P 1 is honest. In case of receiving a (NewSession, sid, pw 1 , ) from an honest P 1 playing the role of a server, we modify F by forwarding only (NewSession, sid, ) to S. We now have to modify S to proceed with the simulation without knowing pw 1 . Upon receiving (NewSession, sid, ) from F for an honest P 1 , we let S draw uniformly at random a "dummy" password pw S and proceed with the simulation of P 1 using pw S as a password.

We first note that in this case of both parties being honest, if at any time S sends a NewKey query to F containing a session key sk for P 1 , this session key is only seen by Z if the corresponding record is compromised. Otherwise, we thus only have to argue indistinguishability of the transcripts of Game G 10 and Game G 11 .

• Z sends Z , X * Z , there is a record (sid, pw Z || ˆ , X, * , E, X * ) in Λ IC for some ˆ ∈ L and pw Z = pw 1 : since S will issue a TestPwd query that will result in a compromised record (cf. simulation described in Game G 6 ), nothing is changed since pw S was never used, and Y * is generated using the correct password pw Z .

• Z sends Z , X * Z , there is a record (sid, pw Z || ˆ , X, * , E, X * ) in Λ IC for some ˆ ∈ L and pw Z = pw 1 : since P 1 will receive a random session key from F in this case (the record will be interrupted), we only have to argue indistinguishability of Y * generated with pw Z || instead of pw 1 || . Obviously, Y * is distributed uniformly random as before. Observe that here it is important that even for a corrupted session, an interrupted record lets the functionality hand out a random session key.

• Z sends Z , X * Z and no E record: the simulation described in Game G 6 tells S to issue a TestPwd query, but now using pw S instead of pw 1 . If, coincidentally, pw 1 = pw S , nothing changes. On the other hand, if pw 1 = pw S , P 1 obtains a random session key from F as opposed to the game before and Y * is created using pw S || instead of pw 1 || . This can only be detected if Z reproduces P 1 's input to F RO from Game G 10 , which happens only with negligible probability according to Lemma 3.3.4 (see below).

• both parties honest and no injections: P 1 will obtain a uniformly random session key from F in this case, and thus the only difference is that Y * was created using pw S || instead of pw 1 || . Again, this is indistinguishable since Y * is distributed exactly as before.

The following lemma bounds the probability that an injected X * that was not obtained using encryption leads to a non-random looking session key.

Lemma 3.3.4. If CDH holds in G, then ∀pw 1 , , Z , X * Z ← Z
, where X * Z was not generated using F IC , , Z ∈ L and pw 1 ∈ P, it holds that

Pr G 11 [CDH(D pw 1 || Z (X * Z ), D pw 1 || (Y * )) ← Z(Y * )] = negl(λ).
Proof. Note that the only difference to Lemma 3.3.2 is that this time, no record ( * , * , * , E, X * Z ) exists so the fact that B CDH is able to embed an element of its CDH challenge into D pw 1 (X * Z ) is even more obvious. The rest of the proof is analogous to Lemma 3.3.2.

Game G 12 : Simulate without pw 0 if the client P 0 is honest. In a similar fashion, we now let F cut the password from NewSession queries to an honest P 0 . We again have to modify S to proceed with the simulation without knowing pw 0 . Upon receiving (NewSession, sid, ) from F for an honest P 0 , we let S draw uniformly at random a "dummy" password pw S . S proceeds the simulation of P 0 using pw S as a password.

Additionally, we further change S in case of a dictionary attack against client P 0 , i.e., upon receiving Z , Y * Z from Z. After submitting a TestPwd query with an extracted pw Z , we let S now choose x $ ← Z q and add (sid, pw Z || , g x , x , ⊥, X * ) to Λ IC and proceed with the simulation of P 0 using x instead of x.

• Z sends Z , Y * Z , there is a record (sid, pw Z || ˆ , Y, * , E, Y *
) in Λ IC for some ˆ ∈ L and pw Z = pw 0 : S will issue a TestPwd query that will result in a compromised record (cf. simulation described in Game G 5 ), resulting in a session key that is computed using pw Z instead of pw S . Additionally, X * is generated using the incorrect password pw S . However, adjusting Λ IC as described above still allows S to know the exponent of D pw Z || (X * ) and continue the simulation, making it look like pw Z was used from the beginning. Z's view is distributed exactly as before since x , x are both uniformly random in Z q .

• Z sends Z , Y * Z , there is a record (sid, pw Z || ˆ , Y, * , E, Y * ) in Λ IC for some ˆ ∈ L and pw Z = pw 0 : since P 0 will receive a random session key from F in this case (the record will be interrupted), we only have to argue indistinguishability of X * generated with pw S | instead of pw 0 || . Obviously, Y * is distributed uniformly random as before. Observe that here it is crucial that even for a corrupted session, an interrupted record lets the functionality hand out a random session key.

• Z sends Z , Y * Z and no E record: the simulation described in Game G 5 tells S to issue a TestPwd query, but now using pw S || instead of pw 0 || . If, coincidentally, pw 0 = pw S , nothing changes. On the other hand, if pw 0 = pw S , P 0 obtains a random session key from F as opposed to the game before and X * was created using pw S || instead of pw 0 || . This can only be detected if Z reproduces P 0 's input to F RO from Game G 11 , which happens only with negligible probability using an argument very similar to Lemma 3.3.4.

• both parties honest and no injections: P 0 will obtain a uniformly random session key from F in this case, and thus the only difference is that X * was created using pw S || instead of pw 0 || . Again, this is indistinguishable since X * is distributed exactly as before.

Observe that in Game G 12 , F = F liPAKE3 , and thus the theorem follows. The complete description of the simulator of Game G 12 interacting with F iPAKE and Z is given in Figure 3.6.

The simulator S, initialized with a security parameter λ, first runs a group generation algorithm using λ to obtain a cyclic group G with generator g of order q with log 2 (q) ≥ λ. Then, S initializes the dummy adversary A. S then interacts with an ideal functionality F liPAKE and an environment Z via the following queries:

• Upon receiving a query (NewSession, sid, P i , ) from F liPAKE :

initialize a party P i , connect it to A and proceed the UC protocol execution described in Figure 3.4 using pw S $ ← P as password and S's random coins.

• Upon receiving a RO query (sid, m) from any entity: If m / ∈ {0, 1} κ × {0, 1} κ × G, then abort. Else: if there is an entry (sid, m, h) then reply with (sid, h).

else, choose h $ ← {0, 1} λ and abort if there is already an entry ( * , * , h) in Λ RO . Else, reply with (sid, h).

• If an internally simulated party P i produces an output (sid, , sk):

Send (NewKey, sid, P i , sk) to F liPAKE .

• If Z sends (sid, Z , Z * Z ) to an honest party P i : if (sid, pw Z || ˆ , * , * , E, Z * Z ) ∈ Λ IC for any ˆ ∈ L, then send the tuple (TestPwd, sid, P i , pw Z , Z ) to F liPAKE and proceed with the simulation of P with pw Z .

if (sid, * , * , * , E, Z * Z ) / ∈ Λ IC , then send (TestPwd, sid, P i , pw S , Z ) to F liPAKE . if P was started with input (NewSession, sid, P i , ), choose x $ ← Z q , add (sid, pw Z || , g x , x , ⊥, Z * ) to Λ IC and proceed as if x was the value drawn uniformly random from Z q at the beginning of the simulation.

• Upon receiving a query (sid, Encrypt, ek, m) from any entity:

If ek / ∈ P × L or m / ∈ G then abort. Else: if there is an entry (sid, ek, m, * , * , c) in Λ IC , reply with (sid, c) else, choose c $ ← {0, 1} * . If there is already a record (sid, * , * , * , * , c) then abort. Else, add (sid, ek, m, ⊥, E, c) to Λ IC and reply with (sid, c).

• Upon receiving a query (sid, Decrypt, ek, c) from any entity:

If ek / ∈ P × L or c / ∈ {0, 1} * then abort. Else: if there is an entry (sid, ek, m, * , * , c) in Λ IC , reply with (sid, m).

else, choose α $ ← G. If there is already a record (sid, * , g α , * , * , * ) then abort. Else, add (sid, ek, g α , α, D, c) to Λ IC and reply with (sid, g α ).

• Upon receiving a query (sid, crs) from any entity:

reply with (sid, (g, q)).

Additionally, S forwards all other instructions from Z to A and reports all output of More precisely, we define a threshold δ and require that the fPAKE session keys are identical if the distance between the two passwords, for a certain notion of distance, is smaller than δ. Otherwise, as in PAKE, the two session keys should each be indistinguishable from random.

A
Notation. In the following we assume the two passwords are strings of length n over some finite alphabet, and denote by pw[i] the i-th character of the string pw. We will use the Hamming distance as our choice of distance between two passwords, so

d(pw, pw ) := i ∈ 1, n : pw[i] = pw [i] .
Note that we do not restrict passwords to bit strings but view them as n-digit strings in any p-alphabet (e.g., coming from Z n p ) and the distance is defined as the number of non-matching password digits;

We also define a masking function, that reveals the positions of the identical bits, but nothing else:

m(pw, pw ) := i ∈ 1, n : pw[i] = pw [i] . By construction |m(pw, pw )| = n -d(pw, pw ).
Functionalities. We will now present ideal functionality for the fPAKE in the UC framework, with the δ threshold hard-coded in. We proceed from F pake and thus allow the adversary one password guess against each player per session, to model the possibility of dictionary attacks. We refer the reader to Section 2.2 for more details about the basic modeling of PAKE.

As in the definition of Canetti et al. [START_REF] Canetti | Universally Composable Password-Based Key Exchange[END_REF], we consider only static corruptions in the standard corruption model of Canetti [START_REF] Canetti | Universally Composable Security: A New Paradigm for Cryptographic Protocols[END_REF]. Also as in their definition, we choose not to provide the players with confirmation that key agreement was successful. The players might obtain such confirmation from subsequent use of the key.

The functionality F fpake is parameterized by a security parameter λ and tolerances δ ≤ γ. It interacts with an adversary S and the (dummy) parties P 0 and P 1 via the following queries:

• Upon receiving a query (NewSession, sid, pw i ) from party P i :

-Send (NewSession, sid, P i ) to S;

-If this is the first NewSession query, or if this is the second NewSession query and there is a record (sid, P 1-i , pw 1-i ), then record (sid, P i , pw i ) and mark this record fresh.

• Upon receiving a query (TestPwd, sid, P i , pw i ) from S : If there is a fresh record (sid, P i , pw i ), then set d ← d(pw i , pw i ) and do:

-If d < δ, mark the record compromised; -If d ≥ δ, mark the record interrupted.
• Upon receiving a query (NewKey, sid, P i , sk) from S, where |sk| = λ: If there is no record of the form (sid, P i , pw i ) or this is not the first NewKey query for P i , ignore this query. Otherwise:

-If the record is compromised, P i is corrupted or both P 1-i is corrupted and there is a record (sid, P 1-i , pw 1-i ) with d(pw i , pw 1-i ) < δ, then output (sid, sk) to player P i .

-If the record is fresh, both parties are honest and a key sk was sent to P 1-i , at which time there was a fresh record (sid,

P 1-i , pw 1-i ) with d(pw i , pw 1-i ) < δ, then output (sid, sk ) to P i .
-In any other case, pick a new random key sk of length λ and send (sid, sk ) to P i .

Either way, mark the record (sid, P i , pw i ) as completed. Ideally, since we target implicit authentication we would like to achieve full implicit authentication, as in iPAKE from Chapter 3 (i.e., the adversary is no more powerful than the players, and does not know either whether authentication succeeded). This is what is presented in Figure 4.1.

However, given the difficulty of achieving this, we also present a more general TestPwd interface which can be substituted to allow for setting some leakage functions.

It includes three leakage functions that we will instantiate in different ways below-L c if the guess is close enough to succeed, L f if it is too far. Moreover, a third leakage function-L m for medium distance-allows the adversary to get some information even if the adversary's guess is only somewhat close (closer than some parameter γ ≥ δ), but not close enough for successful key agreement. We thus decouple the distance needed for functionality from the (possibly larger) distance needed to guarantee security; the smaller the gap between these two distances, the better, of course.

Below, we list the specific leakage functions L c , L m and L f that we consider in this work, in order of decreasing strength (or increasing leakage):

• Upon receiving a query (TestPwd, sid, P i , pw i ) from the adversary S:

If there is a fresh record (sid, P i , pw i ), then set d ← d(pw i , pw i ) and do:

-If d ≤ δ, mark the record compromised and reply to S with L c (pw i , pw i );

-If δ < d ≤ γ, mark the record compromised and reply to S with L m (pw i , pw i );

-If γ < d, mark the record interrupted and reply to S with L f (pw i , pw i ).

L c (pw i , pw i ) = L m (pw i , pw i ) = L f (pw i , pw i ) = ⊥ .
2. A slightly weaker option would be, as with the regular PAKE functionality F pake to leak the correctness of the adversary's guess. We define F D fpake (for decision) to be the functionality described in Figure 4.1, except with TestPwd is from Figure 4.2 with

L c (pw i , pw i ) = L D c (pw i , pw i ) = "correct guess", and
L m (pw i , pw i ) = L D f (pw i , pw i ) = "wrong guess".
3. We define fPAKE M (for mask) to be the functionality described in Figure 4.1, except that TestPwd is from Figure 4.2, with L c and L m that leak the indices at which the guessed password differs from the actual one when the guess is close enough (we will call this leakage the mask of the passwords). That is,

L c (pw i , pw i ) = L M c (pw i , pw i ) = ({j s.t. pw i [j] = pw i [j]}, "correct guess"), L m (pw i , pw i ) = L M m (pw i , pw i ) = ({j s.t. pw i [j] = pw i [j]}, "wrong guess") and L f (pw i , pw i ) = L M f (pw i , pw i ) = "wrong guess".
Note that this functionality fPAKE M leaks enough information that a single guess within distance γ of the actual password will then enable the adversary to get within distance δ (and thus complete key agreement) through multiple on-line attempts, each guided by the leakage from the previous (by changing all the characters where the two passwords differ, in at most as many attempts as the size of the alphabet). Even so, this functionality can provide one-time security against guesses within distance γ. That is, a guess within distance γ, but not within distance δ, will not violate security if the honest party never reuses a password after an unsuccessful attempt. We do not define such security formally and do not pursue this direction further.

4. The weakest definition -or the strongest leakage -reveals the entire actual password to the adversary if the password guess is close enough. We define fPAKE P (for password) to be the functionality described in Figure 4.1, except that TestPwd is from Figure 4.2, with

L P c (pw i , pw i ) = L P m (pw i , pw i ) = pw i and L P f (pw i , pw i ) = "wrong guess".
Here, L P c and L P m do not need to include "correct guess" and "wrong guess", respectively, because this is information that can be easily derived from pw i itself.

The first two functionalities are the strongest, but there is no known construction that realize them, other than through generic two-party computation secure against malicious adversaries, which is an inefficient solution. The last two functionalities, though weaker, still provide meaningful security, especially when γ = δ (i.e., there is no L m situation). Intuitively, this is because strong leakage only occurs when an adversary guesses a "close" password, which enables him to authenticate as though he knows the real password anyway.

In the next section, we present a construction satisfying fPAKE M with γ = 2δ. A more generic construction satisfying fPAKE P , but with γ = δ and for any efficiently computable notion of distance (not just Hamming Distance) is presented in [DHP+18].

Construction

A naive idea

We now give an intuition of the strength of our fPAKE security notion. For this, we look at a fPAKE from the literature and show that it is inherently not UC-secure, regardless of the amount of leakage from F fpake that we allow, i.e., the result holds even w.r.t. our weakest notion F P fpake . A natural idea for building a fPAKE is the use of a fuzzy extractor [DRS04; Boy04], that allows to extract a common secret from two strings close enough, and to compose it with a regular PAKE. This approach was introduced in [BDK+05] (Section 4). Their protocol uses the code-offset construction of a fuzzy sketch [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF], aka fuzzy commitment [START_REF] Juels | A Fuzzy Commitment Scheme[END_REF], to implement a fuzzy extractor as a two-party primitive. In Figure 4.3, we present it while substituting the more generic robust secret sharing (RSS) notation that we presented in Section 2.3.4 for the error-correcting code. Proof. Consider the following attack by Z. Z sends a randomly chosen pw as input to an honest P 0 and obtains a sketch s from A. It then computes c ← spw and outputs 1 if c is in the image of Share. In the real world, this happens with probability 1. Now assume there is a simulator S outputting a simulated sketch s S in the ideal world. Since S does not get to learn pw unless it succeeds at a TestPwd query, observe that this output may not depend on pw except with some small (but non-negligible) probability p, namely the probability of guessing a password that makes F P fpake output pw. Thus, with probability 1p ≈ 1, c S := s Spw is randomly distributed in F n q and lies in the image of Share only with probability 1/q n-1 . More formally, the probability that Z outputs 1 in the ideal world is

P 0 (pw ∈ F n q ) P 1 (pw ∈ F n q ) w $ ← F k q , c ← Share(w) ∈ F n q s ← c + pw s -------→ c ← s + pw w ← Reconstruct(c ) K PAKE(w, w ) ← ------→ K sk ← K sk ← K
Pr[c S ∈ Im(Share)] = Pr[c S ∈ Im(Share)|S depends on pw] • p + Pr[c S ∈ Im(Share)|S does not depend on pw] • (1 -p) ≤ p + 1/q n-1 (1 -p) ≈ p.

Improved idea

In this section we show how to keep the full entropy of the password when some public data is seen (contrarily to the previous construction from Figure 4.3) and to avoid any leakage when the two passwords are away from each other. To this aim, we still use a RSS together with a signature scheme and our liPAKE from Chapter 3. Our protocol is depicted in Figure 4.4.

Intuitively, our protocol works as follows: in the first phase, the two parties aim at enhancing their passwords to a vector of session keys with good entropy. For this, passwords

Sender (pw ∈ F n p ) Receiver (pw ∈ F n p ) (vk, sk) $ ← SigGen(1 λ ) (vk,pw[t])t -------→ (ε,pw [t])t ← ------- for t ∈ 1, n liPAKE for t ∈ 1, n (ε,Kt)t ← ----- ( t,K t )t -----→ abort if r = s for any r, s or 1 / ∈ VK Let K := (K t ) t∈ 1,n Let K := (K t ) t∈ 1,n U $ ← F q , C ← Share(U ) E ← C + K σ E ← Sign(vk, E) E, σ E , vk -------→ abort if vk = 1 output k ← U or Vfy(vk, σ E , E) = 0 U ← Reconstruct(E -K ) output k ← U
q ≈ 2 λ is a prime number and + denotes the group operation in F n q . ε denotes the empty string. (Share, Reconstruct) is a Robust Secret Sharing scheme with Share : F q → F n q , and (SigGen → VK × SK, Sign, Vfy) is a signature scheme. The parties repeatedly execute a liPAKE protocol with label space VK and key space F q , which takes inputs from VK × F p . If at any point an expected message fails to arrive (or arrives malformed), the parties output a random key. are viewed as vectors of characters. Then, the parties repeatedly execute a PAKE on each one of these characters. The PAKE will ensure that the key vectors held by the two parties match in all positions where their passwords matched, and are uniformly random in all other positions.

Next, in the second phase of the protocol, one party -the sender -will pick the final session key uniformly at random and send it in such a way that it reaches the other party only if enough of the key vector matches. This is done by applying a RSS to the key, and send it to the other party using the key vector as a one-time pad. The robustness property of the RSS ensures that a few non-matching password digits do not prevent the receiver from recovering the sender's key.

When using the RSS derived from maximum distance separable (MDS) codes described in Lemma 2.3.5, the one-time pad encryption of the shares (which forms a codeword) can be viewed as the code-offset construction for information reconciliation (aka secure sketch) [JW99; DRS04] applied to the key vectors. While our presentation goes through RSS as a separate object, we could instead present this construction using information reconciliation. The syndrome construction of secure sketches can also be used here instead of the code-offset construction.

Security of FPAKE rss . We show that our protocol realizes functionality F M fpake in the F liPAKEhybrid model. In a nutshell, the idea is to simulate without the passwords by adjusting the keys outputted by F liPAKE to the mask of the passwords, which is leaked by F M fpake . Theorem 4.2.2. If RSS := (Share : F q → F n q , Reconstruct : F n q → F q ) is a t-smooth (n, t, r) q -RSS that in addition is (r -1)-smooth on random secrets, and (SigGen, Sign, Vfy) is a existencially unforgeable under adaptive chosen message attack (EUF-CMA) secure one-time signature scheme, protocol FPAKE rss securely realizes F M fpake with γ = nt -1 and δ = nr in the F liPAKE -hybrid model with respect to static corruptions.

In particular, if we wish key agreement to succeed as long as there are fewer than δ errors, we instantiate RSS using the construction of Lemma 2.3.5 based on a (n + 1, k) q MDS code, with k = n -2δ. This will give r = (n + k)/2 = nδ, so δ will be equal to nr, as required. It will also give γ = nt -1 = 2δ.

We thus obtain the following corollary:

Corollary 4.2.3. For any δ and γ = 2δ, given a (n + 1, k) q -MDS code for k = n -2δ

(with minimal distance d = nk + 2) and a EUF-CMA secure one-time signature scheme, protocol FPAKE rss securely realizes F M fpake in the F liPAKE -hybrid model with respect to static corruptions.

Proof sketch. We start with the real execution of the protocol and indistinguishably switch to an ideal execution with dummy parties relaying their inputs to and obtaining their outputs from F M fpake . To preserve the view of the distinguisher, the environment Z, a simulator S plays the role of the real world adversary by controlling the communication between F M fpake and Z. During the proof, we build F M fpake and S by subsequently randomizing passwords (since the final simulation has to work without them) and session keys (since F M fpake hands out random session keys in certain cases). We have to tackle the following difficulties, which we will describe in terms of attacks.

• Passive attack: in this attack, Z picks two passwords and then observes the transcript and outputs of the protocol, without having access to any internal state of the parties. We show that Z cannot distinguish between transcript and outputs that were either produced using Z's passwords or random passwords. Regarding the outputs, we argue that even in the real execution the session keys were chosen uniformly at random (with Z not knowing the coins consumed by this choice) as long as the distance check is reliable. Using properties of the RSS, we show that this is the case with overwhelming probability. Regarding the transcript, randomization is straightforward using properties of the one-time pad.

• Man-in-the-middle attack: in this attack, Z injects a malicious message into a session of two honest parties. There are several ways to secure protocols that have to run in unauthenticated channels and are prone to this attack. Basically, all of them introduce methods to bind messages together to prevent the adversary from injecting malicious messages. To do this, we need the labeled version of our iPAKE and a one-time signature scheme 1,2 . Unless Z is able to break a one-time-signature scheme, this attack always results in an abort.

• Honest-but-curious/Active attack: in this attack, Z corrupts one of the parties. The simulator will get help from F M fpake by issuing a TestPwd query, which will inform him whether the passwords used by both parties are close and, if so, in which positions they match (i.e., their mask).

-If the sender is honest, we show how to use this information to simulate the transcript. Note that knowledge of the mask is necessary since, due to corruption, Z can now actually decrypt the one-time pad and thus the transcript reveals the positions of the errors in the passwords, which are, of course, already known to Z. If the simulator does not learn a mask, then the passwords are too far away and it follows from the privacy of the RSS that real and simulated transcript are indistinguishable from Z's view.

-If the receiver is honest and Z injects a malicious message on behalf of the sender, the simulator uses the mask to compute the output of the honest receiver. If no mask is obtained then again, the passwords are too far away from each other, and the smoothness property of the RSS (for arbitrarily chosen secrets) says that the receiver's output can be simulated by choosing it uniformly at random.

One interesting subtlety that arises is the usage of the iPAKE. Observe that the UC security notion for a regular PAKE as defined in [START_REF] Canetti | Universally Composable Password-Based Key Exchange[END_REF] and in Section 2.2 provides an interface to the adversary to test a password once and learn whether it is right or wrong. Using this notion, our simulator would have to answer to such queries from Z. Since this is not possible without F M fpake leaking the mask all the time, it is crucial to use the iPAKE variant that we introduced in Chapter 3. Using this stronger notion, the adversary is still allowed one password guess which may affect the output, but the adversary learns nothing more about the outcome of his guess than he can infer from whatever access he has to the outputs alone.

Since our protocol uses the outputs of the PAKE as one-time pad keys, it is intuitively clear that by preventing Z from getting additional leakage about these keys, we protect the secrets of honest parties.

Proof. In this proof, we describe an honest execution of the protocol FPAKE rss in the UC framework in Figure 4.5. See [START_REF] Eduarda | Universally Composable Non-Interactive Key Exchange[END_REF] for a detailed description on how to execute protocols within the UC framework. This real protocol execution will be the starting point for our proof. We then proceed in a series of games, to end up with the ideal execution running with only dummy parties, a simulator and the ideal functionality F M fpake . For convenience, we refer to a received protocol message as adversarially generated if it was not produced by either P 0 or P 1 . We also refer to a query (NewKey, sid, P i , k i ) from the adversary S with an honest party P i as due if

• there is a fresh record of the form (P i , pw i )

• this is the first NewKey query for P i

• there is a record (P 1-i , pw 1-i ) with d(pw i , pw 1-i ) ≤ δ and P 1-i is honest

• a key k 1-i was sent to the other party while (P 1-i , pw 1-i ) was fresh at the time.

We also recall the masking function that reveals the positions of the identical bits:

m(pw, pw ) := i : pw[i] = pw [i], i ∈ 1, n .
Game G 0 : The real protocol execution. This is the real execution of FPAKE rss where the environment Z runs the protocol (cf. Game G 1 : Modeling the ideal layout. We first make some purely conceptual changes that do not modify the input/output interfaces of Z. We add one relay (also referred to as the dummy party) on each of the wires between Z and a party. We also add one relay covering all the wires between the dummy parties and real parties and call it F (and let F relay messages according to the original wires). We group all the formerly existing instances except for Z into one machine and call it S. Note that this implies that S executes the code of the liPAKE functionality F liPAKE . The differences are depicted in Figure 4.6 with F OT replaced by F liPAKE .

Game G 2 : Building F M fpake . In this game, we start modeling F M fpake . First, we let F maintain a list of tuples of the form (P i , pw i ). Upon receiving a query (NewSession, sid, pw i , role) from party P i , if this is the first NewSession-query, or if this is the second NewSession-query and there is a record (P 1-i , pw 1-i ), then F records (P i , pw i ) and marks this record as fresh.

In any case the query (NewSession, sid, P i , pw i , role) is relayed to S. Now that F knows about passwords, we can add a TestPwd interface to F as described in Figure 4.2, using leakage functions L M c , L M m and L M f . We let S parse outputs towards F to be of the form (NewKey, sid, P i , k i ) by adding the NewKey tag and the name of the party who The parties P 0 , P 1 are running with F liPAKE . Protocol Steps:

1. When a party P i , i ∈ {0, 1}, receives an input (NewSession, sid, pw i , sender) from Z, it does the following:

• compute (vk, sk) $ ← SigGen(1 λ )
• query n times F liPAKE with (NewSession, sid, (pw i ) t , vk), t = 1, ..., n, receiving back (sid, t , K t ) as answer

• choose U $ ← F q • compute C ← Share(U ) • compute E ← C + (K t ) n t=1 • compute σ E ← Sign(vk, E) • send (sid, E, σ E , vk) to P 1-i • set k ← U
• send (sid, k) towards Z and terminate the session.

2. When a party P i , i ∈ {0, 1}, receives an input (NewSession, sid, pw i , receiver) from Z, it does the following:

• query n times F liPAKE with (NewSession, sid, (pw i ) t , ε), t = 1, ..., n, receiving back (sid, t , K t ) as answer

• if not all t are equal or 1 = VK, then abort 3. When P i , who already obtained an input (NewSession, sid, pw i , receiver) and thus holds a vector (sid, t , K t ) obtained from F liPAKE , receives a message (sid, E, σ E , vk) from P 1-i , it does the following:

• set K := (K t ) t∈[n] • abort if vk = 1 • abort if Vfy(vk, σ E , E) = 0 • compute U ← Reconstruct(E -K ) • set k ← U
• send (sid, k) towards Z and terminate the session. produced the output. Additionally, we let F translate this back to (sid, k i ), send it to Z via P i and mark the corresponding record as completed.

None of these modifications changes the output towards Z compared to the previous Game G 1 .

Game G 3 : F generates a random session key for an interrupted session. Upon receiving a query (NewKey, sid, P i , k i ) from S, if there is a record of the form (P i , pw i ) that is marked as interrupted, and this is the first NewKey query for P i , we let F output a random session key of length λ to P i . Otherwise, it continues to relay k i .

Since the simulators described in Game G 2 and Game G 3 do not make use of the TestPwd interface, none of the records of F are marked as interrupted and thus the output towards Z is equally distributed in both games.

Game G 4 : S handles dictionary attacks using the TestPwd interface. In this game, we only change the simulation. Consider the following setting: P i obtained input (NewSession, sid, pw i , role) and P 1-i is corrupted and already provided its inputs to F liPAKE . In this situation, S will proceed with the simulation of P i as follows: First, S assembles pw Z ∈ F n p from the queries to F liPAKE that P 1-i issued. S sends (TestPwd, sid, P i , pw Z ) to F, obtaining either "wrong guess", "correct guess" and perhaps also a mask M ⊆ 1, n from F. If S does not receive a mask, S is not modified further. Else, let I := 1, n \ M the set of mismatching indices, and

d := |I| ≤ γ their number. S sets up keys K, K ∈ F n q with K t = K t $ ← F q for the matching indices t ∈ M and K t , K t $ ← F 2
p for the mismatching indices t ∈ I, where K denotes the F liPAKE output of P 1-i . S now continues the simulation of P i using K as output of F liPAKE .

We have to analyze different cases depending on the different outcomes of TestPwd. However, note that the modifications only have an impact on the output k i of P i if the record gets interrupted, and only affect the transcript if the answer to the TestPwd query contains a mask. Considering the case where TestPwd

• outputs m and sets the record compromised, i.e. d ≤ γ since the distribution of K, K only depends on the mask of the passwords, the view of Z is identically distributed in Game G 4 and Game G 3 ;

• outputs "wrong guess" and sets the record interrupted, i.e. d > γ: P i will now obtain a randomly chosen session key from F, substituting the key k i computed by S. If P i obtained role = sender, the output in Game G 4 and Game G 3 is equally distributed since the honest sender outputs a random F q value according to the protocol description. If P i obtained role = receiver, both outputs are indistinguishable with overwhelming probability due to the smoothness of the RSS, since in Game G 3 at least γ + 1 shares are random.

Game G 5 : Excluding man-in-the-middle attacks.

Again, in this game, we only change the simulation. We now consider the case where Z injects a message into a session where both parties are honest. We modify S as follows: upon receiving an adversarially generated (sid, M Z , σ Z , vk Z ) from Z intended for party P i , S aborts.

Observe that the simulation is only changed compared to the previous game if it is not aborted due to protocol instructions. This means that both games are equal unless all checks pass, especially Vfy(vk Z , σ Z , M Z ) = 1. Any distinguisher between Game G 5 and Game G 4 can thus be turned into a forger of a valid message w.r.t the verification key of an honest party. Indinstinguishability thus follows from the security of the one-time signature scheme.

Game G 6 : F aligns session keys. Upon receiving a query (NewKey, sid, P i , k i ) from S, if this query is due then output (sid, k 1-i ) to P i where k 1-i is the session key that was formerly sent to the other party.

We now analyze distinguishability of this game from Game G 5 . If Z tampered with the transcript, the simulation in Game G 5 ensures that the simulation aborts and there is thus no NewKey query for P i . On the other hand, if Z does not advise A to tamper with any message, perfect correctness of FPAKE rss protocol ensures that, in case of a due record where the parties hold close passwords pw i , pw 1-i with d(pw i , pw 1-i ) ≤ nr, the output of F towards Z is the same as in the previous Game G 5 . Observe that perfect correctness directly follows from the perfect correctness of F liPAKE and the r-robustness of the secret sharing, which is always able to correct up to nr errors.

Note that F still differs from the functionality F M fpake in some aspects. First, it does not output randomly generated session keys towards Z for honest sessions. Furthermore, it reports all passwords to S. We will take care of these remaining differences in the next games.

Game G 7 : In some cases, F generates a random session key when the other party is corrupted. Upon receiving a NewKey query (NewKey, sid, P i , k i ) from S, if there is a fresh record of the form (P i , pw i ), and this is the first NewKey query for P i , P i is honest and P 1-i corrupted and there is a record (P 1-i , pw 1-i ) with d(pw i , pw 1-i ) > δ, we let F pick a new random key k from F q and send (sid, k) to P i .

The simulation ensures that the record (P i , pw i ) is either compromised or interrupted (cf. description of the simulator in Game G 4 ). Thus, the modification has no effect since it only concerns fresh records.

Game G 8 : F generates a random session key for an honest session. Upon receiving a NewKey query (NewKey, sid, P i , k i ) from S, if there is a fresh record of the form (P i , pw i ), and this is the first NewKey query for P i , both parties are honest and the NewKey query is not due, we let F pick a new random key k from F q and send (sid, k) to P i .

In other words, F now generates a random session key upon a first NewKey query for an honest party P i with fresh record (P i , pw i ) where P 1-i is also honest if (at least) one of the following events happens:

1. There is a record (P 1-i , pw 1-i ) with d(pw i , pw 1-i ) > δ; then, the probability that k i was already random in Game G 7 is overwhelming due to the r -1-smoothness of the RSS on random secrets. Note that to apply this property it is crucial that both parties are honest and thus the value U is randomly chosen.

2. No session key was sent to P 1-i yet; we just have to consider the case where there is a record (P 1-i , pw 1-i ) with d(pw i , pw 1-i ) ≤ δ since we already dealt with the other case in the first event. Due to the r-robustness of the RSS, the session key in the previous game was U , which is distributed uniformly random in F q .

3. If there was a session key sent to P 1-i , the record (P 1-i , pw 1-i ) was not fresh and thus interrupted or compromised at that time; since our simulation never issues

TestPwd queries for honest sessions (in fact, Game G 5 states that S aborts upon man-in-the-middle attacks with overwhelming probability), this event can not happen in our simulation.

Game G 9 : Simulating without password if both parties are honest. In case of receiving a (NewSession, sid, pw i , role) from an honest P i , we modify F by forwarding only (NewSession, sid, P i , role) to S. We now have to modify S to proceed with the simulation without knowing pw. Upon receiving (NewSession, sid, P i , role) from F for an honest P i , we let S draw uniformly at random a "dummy" password pw S and proceed with the simulation of P i using pw S as a password.

We first observe that Z is oblivious of k i contained in the (NewKey, sid, P i , k i ) query that S will eventually send to F during the simulation (since F never lets the simulator determine k i for an honest session). This means that, informally, we have to show that Z, knowing pw i , pw 1-i and seeing two transcripts, cannot tell which one was generated using pw i , pw 1-i and which one was generated using pw S , pw 1-i with a random pw S unknown to Z. But this is trivial since the distribution of the values U, K does not depend on the passwords: U is randomly chosen from F q . F liPAKE ensures that K is randomly chosen from F n q . Game G 10 : Simulating without password if someone is corrupted. Upon receiving (NewSession, sid, pw i , role) from P i where P 1-i is corrupted, we modify F to only relay (NewSession, sid, P i , role) to S. Additionally, we let S draw uniformly at random a "dummy" password pw S and proceed with the simulation of P i using pw S as a password. Note that due to the simulation described in Game G 4 , S will ask a TestPwd query, and after this query the simulation described in that game is already independent of pw i except when F's reply does not contain a mask. In this case, we now let S set the output of F liPAKE for P i to be a random K $ ← F n q . Regarding indistinguishability, first note that in any case the input of P i to F liPAKE does not impact any values and thus we only have to argue further in case S is modified.

Then, it holds that d(pw i , pw 1-i ) > γ. Thus, P i 's record will get interrupted and P i will obtain a uniformly random session key from F, meaning that we only have to argue indistinguishability of E, σ E , vk generated with either K depending on pw i (as in the previous game) or K $ ← F n q (as in the current game). Opposed to the situation in Game G 9 , note that now Z knows K .

Since d(pw i , pw 1-i ) > γ = nt -1, at most t components of K are the same as K in G 9 with large probability 1 -n-t q , and thus w.h.p. Z learns at most t components of C. Therefore, the t-privacy of the Secret Sharing scheme states that nothing is leaked about U . Hence the transcript of the current and previous games are indistinguishable.

Observe that now F is equal to F M fpake and S is equal to the simulator described in Figure 4.7. The theorem thus follows.

The simulator S, initialized with a security parameter λ, initializes the dummy adversary A. S emulates an ideal labeled iPAKE functionality F liPAKE as depicted in Figure 3.2 for all calling entities in the system a . Additionally, S interacts with an ideal functionality F M fpake and a distinguisher, the environment Z, via the following queries: • Upon receiving a query (NewSession, sid, P i , role) from F M fpake : initialize a party P i and connect it to A.

-If P 1-i is honest, S proceeds the UC protocol execution as described in Figure 4.5 using pw S $ ← F p as password for P i and S's random coins. (Cf. Game G 9 .) -If P 1-i is corrupted, then S waits until P 1-i submitted n queries to F liPAKE and then assembles pw Z ∈ F n p from them. S sends (TestPwd, sid, P i , pw Z ) to F M fpake . If S receives back a mask M , let I := 1, n \ M , and S sets up n F q -keys K with K t = K t ∀t ∈ I and K t $ ← F p = K t ∀t ∈ M , where K denotes the output of F liPAKE towards P 1-i . S now continues the simulation of P i using K as outputs of F liPAKE . (see Game G 4 .) If S does not receive a mask, it sets the output of F liPAKE for P i to be K $ ← F n q . (Cf. Game G 10 .)

• If an internally simulated party P i produces an output (sid, k i ): Send (NewKey, sid, P i , k i ) to F M fpake .

• If Z sends (sid, M Z , σ Z , vk Z ) to an honest party P i : if P 1-i is honest, S aborts after the Vfy step in the protocol, regardless of its outcome. (Cf. Game G 5 .)

Additionally, S forwards all other instructions from Z to A and reports all output of A towards Z. Instructions of corrupting a player are only obeyed if they are received before the protocol started, i.e., before S received any NewSession query from F M fpake .

a An entity is any internally simulated ITM such as parties or the real-world adversary as well as ITMs outside S such as the distinguisher Z.

Removing modeling assumptions

All modeling assumptions of our protocol come from the realization of the ideal F liPAKE functionality. e.g., the liPAKE protocol from Chapter 3 requires a random oracle, an ideal cipher and a CRS. We note that we can remove everything up to the CRS by, e.g., taking the PAKE protocol introduced in [START_REF] Katz | Round-Optimal Password-Based Authenticated Key Exchange[END_REF]. This protocol also securely realizes our F liPAKE functionality3 . However, it is more costly than our liPAKE protocol since both messages each contain one non-interactive zero knowledge proof. Since fPAKE implies a regular PAKE (simply set δ = 0), [START_REF] Canetti | Universally Composable Password-Based Key Exchange[END_REF] gives strong evidence that we cannot hope to realize F fpake without a CRS.

Chapter 5 Human authenticated key exchange

We now present another notion derived from PAKE, called human authenticated key exchange (HAKE). Its goal is to design a key exchange specifically tuned for human authentication, i.e. when a human is operating one of the parties, called the terminal, and wants to establish a secure key with another party, called the server.

In a regular PAKE, this would be modeled as one of the parties being both the human (that knows the password) and the terminal (that can actually do the computations required in the PAKE). Such a model hence implicitly requires perfect trust between human and terminal, which is not really realistic. In real life, the terminal may be compromised, which cannot be accounted for with a PAKE.

Of course, if this is the case, any key computed on this terminal will be likewise compromised. However, one could hope that keys established using PAKE with the same password but an honest terminal will stay secure. This captures both notions of forward secrecy (past sessions are not compromised, as a passive transcript does not contain enough information to deduce the key) and future or backward secrecy (future sessions are not compromised).

The latter can seem hard to achieve since the password is likely leaked in the compromising of the terminal. However, there is hope, in the form of human computation, that is requiring some computation on the part of the human so that the full secret is not leaked to the terminal.

In this chapter, we will present how to model human computation and then a HAKE itself, as well as present solutions to achieve better security.

Human-compatible notions.

Here we present several notions that our definitions will use. Since it is hard to formalize human computational abilities, those are not mathematically precise. We say a message is human-readable if this is a short sequence of ASCII symbols, or images; human-writable if this is a short sequence of ASCII symbols1 ; human-memorizable if this is simple enough to be memorized by an average human, e.g., a simple arithmetical rule like "plus 3 modulo 10". A function is human-computable if an average human can evaluate it without help of additional resources other than his head, e.g., simple additions modulo 10. A set is human-sampleable if an average human can choose a message from the set at random according to the appropriate distribution without help of additional resources other than his head.

Human-compatible function family

In order to make our constructions more generic, we first define a new notion, called human-compatible function family (HCFF), which captures the relevant security and usability properties we would like to see regarding operations made by the human.

Since this field is quite new, and that it is quite challenging to construct a primitive which uses operations simple enough to be achievable by a human, ideally in his head, and yet is complex enough to offer some security, this notion allows us to abstract our HAKE constructions from the current state of research in this area.

We will restrict ourselves to single-round computations on the part of the human, using an input given by the terminal and a secret information that only the human has access to. This can be modeled as computing a function indexed by the secret information, hence the name of human-compatible function family.

Syntax

A human-compatible function family (HCFF) is specified by the challenge space C, the key generation algorithm KG, which takes as input the security parameter and outputs a highentropy key K , and the challenge-response function F that takes a key K and a challenge

x ∈ C and returns the response r = F K (x). We require that (see above for definitions):

1. for every K output by KG and every x ∈ C, both x and F K (x) are human-writable and human-readable;

2. C is human-sampleable.

We also define only-human human-compatible function family (where an additional device is excluded), which are the HCFF that also have:

1. for every K output by KG, F K (•) is human-computable;

2. every K output by KG is human-memorizable;

Security

In an authentication protocol with challenge-response pairs, intuitively, we would like that any successful authentication to a server should involve an evaluation of the function by the human user. So we expect no compromised/infected terminal to successfully authenticate to the server one more time than it interacted with the human. The security notion from the function is thus a kind of one-more unforgeability [START_REF] Bellare | The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme[END_REF]. But here, any query to an F K (•)-oracle should help to immediately answer F K (x) to the current challenge x, since a second challenge will come from a new session that has closed the previous one, and so the previous challenge is obsolete: the adversary cannot store the n + 1 challenges, ask n queries, and answer the n + 1 initial challenges. In our protocols, the adversary gets a random challenge (GetRandChal-query), can ask any F K (•)-query (GetResp-query), but should answer that challenge (TestResp-query), otherwise the failure is detected. After too many failures (recorded in the unvalidated-query counter ctr) one may restrict oracle queries.

The following security notion will formalize those restrictions to the adversary, and following potential relaxations.

GetRandChal()

GetResp()

TestResp() As said above, we define a kind of sequential one-more unforgeability experiment, with a limit η on the unvalidated-query counter ctr, where the queries follow the graph presented on Figure 5.1. Given an HCFF F , an adversary A, and a public parameter η, one first generates K with KG and initializes ctr ← 0. Then the adversary can ask the following queries, with possible short loops on the GetRandChal-query and direct TestResp-attempt right after getting a challengei x:

if ctr < η
1. GetRandChal() -It picks a new x $ ← C, marks it fresh and outputs it;

2. GetResp(x * ) -If ctr < η and x * ∈ C, it returns F K (x * ) and increments ctr. It also marks the fresh x as unfresh. Otherwise, it outputs ⊥;

TestResp(r) -

• If F K (x) = r and x is fresh, the adversary wins;

• If F K (x) = r and x is unfresh, it decrements ctr, marks x as used, and outputs 1;

• Otherwise, it outputs 0.

Because of the sequential iterations, any TestResp-query relates to the previous GetRandChalquery. One can thus consider one memory slot to store the challenges, but one only at a time: any new challenge replaces the previous one. The dashed line from GetRandChal to GetResp emphases the restriction on the number of unvalidated queries. When ctr ≥ η, the adversary has no more choice than immediately trying an answer to the random challenges. The bound η represents the maximum gap that is allowed at any time between the number of GetResp-queries and the number of correct TestResp-queries. Note that a random challenge x can only be either fresh, unfresh, or used, and that marking it as one of those erases the other flags. Intuitively, a fresh challenge has not been compromised in any way, and succeeding at a TestResp on it would indicate the unforgeability has been breached, hence the winning status for the adversary, and the experiment stops. A challenge can switch to the unfresh state if the adversary asks the GetResp-oracle for an answer. There are only two ways for the experiment to stop: if the adversary wins with a correct TestResp-query on a fresh challenge; or if the adversary aborts, it then loses the game. We stress that the adversary can query the GetResp-oracle on any x * of its choice, and so possibly different from the current challenge x obtained with the previous GetRandChal-query. But we give it a chance to still answer correctly to the challenge x with the correct TestResp-query that, on an unfresh challenge, cancels the instrumentation of the counter ctr. This counter represents the gap between the number of GetResp-queries and the number of correct TestResp-queries on random challenges. When one limits ctr to be at most 1, any GetResp-query should be immediately followed by a correct TestResp-query (one-more unforgeability). This definition is a weaker notion than the one-more unforgeability [START_REF] Bellare | The One-More-RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme[END_REF], but still allows the adversary to exploit malleability: For example, with the RSA function, for a random challenge y, the adversary can ask a GetResp-query on any y = y • r e mod n, for a r of its choice, so that it can then extract a e-th root of y. But this would not help it to answer a next fresh challenge.

2-Party η-Unforgeability. Unfortunately, the above clean security notion is not enough for a HAKE application, as client-server situations and man-in-the-middle attacks intrinsically allow a more complex ordering of the queries by the adversary. We therefore present a variant of this experiment below, that is suitable for a protocol involving two parties (hence in the following b ∈ {0, 1}).

Given an HCFF F , an adversary A, and a public parameter η, one first generates K with KG and initializes ctr ← 0. Then the adversary can ask the following queries: • Otherwise, it outputs 0.

The main difference with the previous experiment is the two memory slots for challenges x 0 and x 1 . But still, any GetResp-query must be followed by a correct TestResp-query to limit ctr from increasing too much. The advantage of any adversary A against the unforgeability Adv η-uf F (A) is the probability of winning in the above experiment (with a correct TestResp-query on a fresh challenge). Such a success indeed means that the adversary found the response for a new random challenge, without having asked for any GetResp-query.

The resources of the adversary are the polynomial running time and the numbers q c , q r , q t of queries to GetRandChal, GetResp and TestResp oracles, respectively. Of course it is crucial whether there are secure instantiations of HCFF. We propose some in the next section.

Indistinguishability.

For some constructions, we will simply expect the sequence of answers (F K (x i )) i=0,...,T to the challenges x i (either adversarially chosen or not) to look random, or at least any new element in the sequence is not easy to predict from the previous ones.

For the sake of simplicity, we assume that there exists a global distribution D with large enough entropy D such that any such sequence is computationally indistinguishable from and a challenge x ∈ C as inputs, and returns a response r = F K (x). Here F K : C → Z t q is defined as a t-tuple

(t ≥ 1) (f • σ l , • • • , f • σ l ), where • indicates the function composition.
For instance, if n = 100, l = 3, q = 10, t = 2, x = ((1, 4, 20), (3,36,41)), σ(i) = (i + 3) mod 10 and f = (x 1x 2 + x 3 ) mod 10, then σ( [START_REF] Functionality | [END_REF]4,20)) = (4, 7, 3), σ((3, 36, 41)) = (6, 9, 4) and F K (x) = (0, 1).

Given integers k 1 , k 2 > 0, the function f is instantiated as

f k 1 ,k 2 : Z 10+k 1 +k 2 10
→ Z 10 , which is defined as follows:

f k 1 ,k 2 (x 0 , . . . , x 9+k 1 +k 2 ) = x 9+k 1 i=10 x i mod 10 + 9+k 1 +k 2 i=10+k 1 x i mod 10.
Note that when f is instantiated as f k 1 ,k 2 , we have l = 10 + k 1 + k 2 and q = 10.

It is easy to see that such a function family is an only-human HCFF apart from the human memorization property. However, we can allow for images to represent the variables. As illustrated in [START_REF] Blocki | Towards Human Computable Passwords[END_REF], by using mnemonic helpers, humans are able to remember such mappings from images to digits. As evidence, the primary author of [START_REF] Blocki | Towards Human Computable Passwords[END_REF] was able to memorize a mapping from n = 100 images to digits in 2 hours.

Candidate's security

In [START_REF] Blocki | Towards Human Computable Passwords[END_REF], the authors proved the intractability to answer a new random challenge for the above HCFF instantiation based on the conjecture about the hardness of random planted constraint satisfiability problem (RP-CSP). In this section, we briefly recall one of their results, the RP-CSP conjecture, siglhtly simplified for our purpose (and thus we call it the RP-CSP * conjecture for disambiguation), and then proceed to show how to use it to achieve η-unforgeability.

The RP-CSP * conjecture. Before stating this conjecture, we introduce some notations as in [START_REF] Blocki | Towards Human Computable Passwords[END_REF]. Recall how

d(α 1 , α 2 ) = |{i ∈ 1, n | α 1 [i] = α 2 [i]}| is the Hamming distance between two strings α 1 , α 2 ∈ Z n q .
Then we say two mappings σ 1 , σ 2 ∈ Z n q are ε-correlated if d(σ 1 , σ 2 )/n ≤ (q -1)/qε.

Conjecture 1 (RP-CSP *). Consider the function f k 1 ,k 2 described above, for any ε, ε > 0 and any probabilistic polynomial time (in n) adversary A, there exists an integer N ∈ N, such that for all n > N , m ≤ n min{(k 2 +1)/2,k 1 +1-ε } , we have Adv rand

f k 1 ,k 2 (A, ε) = negl(n), where Adv rand f k 1 ,k 2 (A, ε) is the probability that A outputs a mapping σ that is ε-correlated with the secret mapping σ given m random "small" challenge-response pairs {(C i , f k 1 ,k 2 (σ l (C i )))} 1≤i≤m .

Remark 5.2.1. The RP-CSP conjecture in [BBDV17] is a general version of the RP-CSP *

Conjecture 1, where f can be instantiated as other functions. Here, for simplicity, we only state the conjecture where f = f k 1 ,k 2 . In [START_REF] Blocki | Towards Human Computable Passwords[END_REF], the authors also prove strong evidence in support of the RP-CSP conjecture: it holds for any statistical adversary and any Gaussian Elimination adversary. As observed in [START_REF] Feldman | On the Complexity of Random Satisfiability Problems with Planted Solutions[END_REF], most natural algorithmic techniques have statistical analogues except the Gaussian Elimination.

Basic η-unforgeability. To state the security theorem in [START_REF] Blocki | Towards Human Computable Passwords[END_REF], we need the following "basic" HCFF security notion that is a "non-malleable" version of the η-unforgeability. It indeed assumes that asking a GetResp-query with an input different from the current random challenge should not help to answer this challenge correctly to the TestResp-query. Given an HCFF F , an adversary A, and a public parameter η, one first generates K with KG and initializes ctr ← 0. Then the adversary can ask the following queries:

1. GetRandChal() -It picks a new x $
← C, marks it fresh and outputs it;

2. GetResp(x * ) -It increments ctr if x * = x;

• If ctr ≤ η and x * ∈ C, it outputs F K (x * ) and marks x as unfresh;

• Otherwise, it outputs ⊥;

3. TestResp(r) -

• If F K (x)
= r and x is fresh, the adversary wins;

• If F K (x) = r and x is unfresh, it outputs 1;

• Otherwise, it outputs 0.

Just like the η-unforgeability experiment, the above oracle calls are sequential (similar to Figure 5.1), starting with a GetRandChal-query. But since non-malleability is assumed, only

GetResp-queries with inputs different from the current random challenges make the counter increase, and it is never decreased. The advantage of any adversary A against the above unforgeability Adv η-uf-basic F (A) is the probability of winning in the above experiment. Such a success indeed means that the adversary found the response for a new random challenge, without having asked for a GetResp-query. The parameter η restricts the number of "adaptive" GetResp queries that A can make, where adaptive means "different from the current random challenge".

The resources of the adversary are the polynomial running time and the numbers q c , q r , q t of queries to the above GetRandChal, GetResp and TestResp oracles, respectively. For convenience, denote by q t the number of TestResp-queries such that the current random challenge x is fresh. By definition, we have q r ≤ q c , q t ≤ q c and q t ≤ q cq r . HCFF security results. Under Conjecture 1, one can prove the following unforgeability result about the HCFF.

Theorem 5.2.2 (From [BBDV17]

). Given ε, ε > 0, t ∈ N + and δ > ( 1 10 + ε) t , for any probabilistic polynomial time (in n, q c , 1/ε) adversary A against the basic 0-unforgeability security of the human-compatible function family F constructed above using

f = f k 1 ,k 2 with q t = 1, q c ≤ 1 t • n min{(k 2 +1)/2,k 1 +1-ε } -1,
under Conjecture 1, we have Adv 0-uf-basic

F (A) < δ.
Note that in the basic 0-unforgeability security game, the adversary learns nothing from GetResp(x * ) if x * is not the current random challenge x. So if η = 0, the adversary A is only given random challenge-response pairs. This result is actually not strictly good enough, even for our Confirmed HAKE. Indeed, this protocol's security stems from it's ability to detect bad behaviour (notably, adaptive querying) by one of the parties. However, if the HCFF function does not allow for at least one adaptive query, an attacker using one might be able to break the unforgeability of the function fast enough to be able to fool the detection mechanism. Thus, we extend the RP-CSP conjecture to allow log n adaptive "small" challenge-response pairs. Lemma 5.2.3. Consider the function f k 1 ,k 2 described above, for any ε, ε > 0, t ∈ N + and any probabilistic polynomial time (in n) adversary A, there exists an integer N ∈ N, such that for all n > N , m r ≤ n min{(k 2 +1)/2,k 1 +1-ε } and m a ≤ t log n, we have Adv adapt

f k 1 ,k 2 (A, ε) = negl(n),
where Adv adapt

f k 1 ,k 2
(A, ε) is the probability that A outputs a mapping σ that is ε-correlated with the secret mapping σ given m r random "small" challenge-response pairs and the correct responses to m a "small" challenges adaptively chosen by A.

Proof. For any adversary A we can construct an adversary B such that Adv adapt

f k 1 ,k 2 (A, ε) ≤ 10 t log n × Adv rand f k 1 ,k 2 (B, ε).
B simulates A's view by providing A with the given m r random "small" challenge-response pairs and randomly guessing the responses to the m a (≤ t log n) adaptive "small" challenges. The probability of correctly guessing all adaptive ones is 10 -t log n (refer to the construction of f k 1 ,k 2 ), hence the above advantage reduction. One should note that 10 t log n ×negl(n) = negl(n) and B's running time is polynomial in n.

Using this lemma, one can prove the following stronger unforgeability result about the HCFF, which "almost" suits our Basic HAKE (see Figure 5.3): Theorem 5.2.4. Given ε, ε > 0, t ∈ N + and δ > ( 1 10 + ε) t , for any probabilistic polynomial time (in n, q c , 1/ε) adversary A against the basic η-unforgeability security of the humancompatible function family F constructed above using

f = f k 1 ,k 2 with η ≤ log n, q c ≤ 1 t • n min{(k 2 +1)/2,k 1 +1-ε } -1,
under Conjecture 1, we have Adv η-uf-basic F (A) < q t • δ.

Proof. The proof is almost the same as that of Theorem 5.2.2. Informally, we need to show that any adversary A that breaks the basic η-unforgeability security of the HCFF can also "recover" the secret mapping σ in Conjecture 5.2.3. The reader can refer to the proof of Theorem 5 in [START_REF] Blocki | Towards Human Computable Passwords[END_REF], which we call the "HCP" proof below, for the details. Nevertheless, here the theorem differs from Theorem 5.2.2 in several aspects. First, A can adaptively select t log n "small" challenges to get the correct responses, while in Theorem 5.2.2 only random ones are allowed. But having adaptive queries does not affect the HCP proof because it only uses A as a black box to predict the responses to any t "small" challenges. Second, we apply a union bound of q t queries to the final advantage. Remark 5.2.5. In the above theorem ε, ε are almost 0. We can set n = 100,

k 1 = 1, k 2 = 3 and t = 5, then η ≤ 6, q c ≤ n 2 /t -1 ≈ 2000 and Adv η-uf-basic F (A) < q t • 10 -t ≤ 1/50.
We believe a similar theorem holds for Adv η-uf F (by replacing the oracles with those in the 2-party η-unforgeability experiment), which our HAKE security can rely on. The intuition is as follows. With the HCFF instantiation described in this section, a GetResp(x * ) query in the η-unforgeability experiment should not have x * too "far" from the random challenge x output by the latest GetRandChal query. Otherwise, it is very unlikely for the adversary to guess correctly in the TestResp query. But the adversary can modify x a little bit to guess the correct response with a smaller failure probability. This is the difference between the two unforgeability notions: the basic one does not tolerate any malleability, whereas the other can exploit malleability. Because of the size of the challenge space, that has to be quite large (it is essentially n t(10+k 1 +k 2 ) , and thus 2 465 , with the above parameters), the number of challenges that are "close" to any random challenge accounts for a tiny proportion. Thus, the adversary should not get much help from such "nearly random" challenges. Besides, such queries risk increasing the counter in the GetResp oracle without extracting much useful information. In addition, the two memory slots will not increase much the advantage of an adversary, and so Adv η-uf-basic F and Adv η-uf F should be quite close for this specific HCFF instantiation. We leave further studies of security of the HCFF from [START_REF] Blocki | Towards Human Computable Passwords[END_REF] to future works.

HAKE definition

We now define HAKE as an extension of PAKE.

Protocol participants. We fix the set of participants to be ID = {U } ∪ {T } ∪ {S}, which contains finite number of human users U , one terminal T and one server S. And we assume that each member is uniquely described by a bit string. In the real life, each user U can communicate with multiple servers via multiple terminals. But we justify below why considering a single terminal and a single server is sufficient HAKE syntax. We now formally describe a HAKE protocol. Definition 5.

(HAKE Protocol). A human authenticated key exchange protocol is an interactive protocol between a human user denoted U ∈ {U } and the server S, via the terminal T . It consists of two algorithms:

• A long-term key generation algorithm LKG which takes as input the security parameter and outputs a long-term key.

• An interactive key exchange algorithm KE which runs between U , T , and S. At the beginning, only U and S take as input the same long-term secret key and, at the end, T and S each outputs a session key sk T and sk S respectively. In case of additional explicit authentication, U and/or S may either accept or reject the connection.

The above algorithms must satisfy the following constraints:

• S can only communicate with T ;

• U can only communicate with T , and messages sent by T to U must be human-readable, and messages sent by U to T must be human-writable;

• The long-term secret and the state of U , if any, must be human-memorizable for the duration necessary. The correctness condition requires that for every security parameter and for every longterm key output by LKG, in any execution of KE, U and S both accept the connection (in case of explicit authentication), T and S complete the protocol with the same session key (sk T = sk S ).

HAKE security model

In this section, we formally define a simulation-based security model for a HAKE protocol that is derived from the BPR security model from [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF] (see Section 2.2.3 for a gist of the basic BPR model). As already mentioned, the goal of a HAKE protocol is to ensure that a human user sharing the long-term secret with a server can help a terminal to establish a secure channel with the server, in presence of a very powerful attacker, including strong corruptions of terminals.

As usual, to model multiple and possibly concurrent (except for the human users) sessions we consider oracles π j P , where j ∈ N and P ∈ ID. For human oracles, sessions can only be sequential, and not concurrent, meaning that humans are not allowed to run several sessions concurrently (a new session starts after the previous one ends). This is a reasonable assumption for human users. We note that since terminals do not store long-term secrets and do not preserve state between sessions, multiple terminal oracles model both multiple sessions ran from the same or different terminals.

Hence, in the following, we will consider several human users U with different long-term secret keys, one terminal T , and one server S, with all the users' long-term secret keys. For all of them, multiple instances will model the multiple sessions (either sequential for U , or possibly concurrent for T and S). However, while the server can concurrently run several sessions, we will also limit it to one session at a time with each user: the server will not start a new session with a user until it finishes the previous session with the same user.

Because of our specific context with a human user, there is a direct communication link between the user and the terminal, and so we can assume that the channels between instances π i U and π j T are authenticated and even private (unless the terminal oracle is compromised, as defined below), whereas the communication between the terminal and the server is over the Internet, and so the channels between instances π j T and π k S are neither authenticated nor private.

Security experiments. We consider the following security experiments associated with a given HAKE protocol and an adversary A, to define the two classical security notions for any authenticated key exchange: privacy (or semantic security of the session key) and authentication. In these experiments, the adversary A can make the following queries:

• Compromise(j, ), where j, ∈ N -As the result of this query, the terminal oracle π j T is considered to be compromised, and the adversary gets its internal state, i.e. the random tape, temporary variables, etc. If the terminal oracle π j T is not linked yet to a user, it is linked to user U with the user oracle π i U for a new index i, otherwise is ignored;

• Infect(j), where j ∈ N -As the result of this query, the terminal oracle π j T is considered to be infected. wlog, we limit this query to compromised terminals only;

• SendTerm(j, M ), where j ∈ N and M ∈ {0, 1} * ∪ {Start( )} -This sends message M to π j T . A specific Start( ) message asks the terminal to initiate a session, that will be conducted with a user oracle π i U for a new index i, unless the terminal oracle π j T was already linked to a user, in which cas is ignored. To compute its response to A, π j T may internally talk to its linked human oracle according to the protocol. In addition, if π j T is compromised, it will additionally give to A the messages exchanged with its linked human oracle2 .

• SendServ(k, M ), where k ∈ N and M ∈ {0, 1} * -This sends message M to oracle π k S . The oracle computes the response according to the corresponding algorithm and sends the reply to A.

• SendHum(j, M ) where j ∈ N and M ∈ {0, 1} * (and human-readable) -This sends a message to the π j T -linked human oracle π i U on behalf of π j T . This is allowed only if the terminal π j T is infected (and thus compromised, which implies the existence of a partnered human oracle). The oracle computes the response according to the corresponding algorithm and sends the reply to A.

• Test(j, P ), where j ∈ N and P ∈ {T } ∪ {S} -If sk P has been output by π j P , then one looks at the internal bit b (flipped once for all at the beginning of the privacy experiment, while b = 1 in the authentication experiment). If b = 1, then A gets the real session key sk P , otherwise it gets a uniformly random session key. This query is only allowed if π j P is fresh (defined below). In the privacy experiment, after having adaptively asked several of these oracle queries, the adversary A outputs a bit b (a guess on the bit b involved in the Test-queries). The intuition is that the adversary should not be able to distinguish the real session keys from independent random strings. While in the authentication experiment, the goal of the adversary is to make an honest party to successfully complete the protocol execution thinking it "built a secure session" with the right party, whereas that is not the case. In order to formally define the goals and the advantages of the adversary, we present the notions of partnering and freshness, as well as the flags accept and terminate.

Flags.

In order to model authentication, we follow BPR [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF], who defined two flags: accept essentially means that a party has all the material to compute the session key while terminate means that a party thinks that it completes the protocol execution thinking it communicates with the expected other party (a human user in our case). These two flags are initially set to False, and they are explicitly set to True in the description of the protocol. Note that in Definition 5.3.1 U and/or S accept if and only if in the end the terminate flag is set to True, otherwise, U and/or S reject.

Partnering. Whereas π i

U and π j T are declared as linked at the initialization of the communication because of the authenticated channels between users and the terminal, partnering between π i U and π k S is a posteriori: they are indeed declared partners in the end of the protocol execution if they use the same long-term key and both accept. Then we define partnering between π j T and π k S , by saying that they are declared partners if π k S and U i are partners and U i is linked to π j T .

Freshness. Informally, the freshness denotes oracles that hold sessions keys that are not trivially known to the adversary.

For P ∈ {T } ∪ {S}, the oracle π j P is fresh, if no Test-query has been asked to π j P nor its partner, and none of π j P or its partner have been compromised (π j T is fresh if it has not been compromised, and π k S is fresh if the terminal linked to the partner human user has not been compromised.).

Security notions.

In the privacy security game, the goal of the adversary is to guess the bit b involved in the Test-queries. Then we measure the success of an adversary A that outputs a bit b , by Adv priv

HAKE (A) = 2 • Pr[b = b] -1.
This notion implies implicit authentication, which essentially means that no one other than the expected partners knows the session key material.

For explicit authentication, we define the authentication security game: the goal of the adversary is essentially to make a player terminate (flag terminate set to true) without an accepting partner (flag accept set to true). But in our case with compromised or even infected terminals, this is a bit more complex than usual. We thus split the authentication security in two parts:

• Server-authentication: a user oracle should not successfully terminate a session if there is not exactly one partner server oracle that has accepted. Then, we denote by Adv s-auth HAKE (A) the probability the adversary A makes such a bad event happens; • User-authentication: a server oracle should not successfully terminate a session if there is not exactly one partner user oracle that has accepted. Then, we denote by Adv u-auth HAKE (A) the probability the adversary A makes such a bad event happens. Eventually, for any adversary A, B there exists an adversary C against the authentication security for which we define Adv auth HAKE (C) = max{Adv s-auth HAKE (A), Adv u-auth HAKE (B)}.

Passive sessions. We now define a new notion of passive session, which replaces the Executequeries in the standard BPR model [START_REF] Bellare | Authenticated Key Exchange Secure against Dictionary Attacks[END_REF] (see Section 2.2.3 for a discussion of why).

Recall that Execute-queries allow the adversary to get full transcripts of communication between honest parties. Even though the same can be achieved via Send-queries, in the security analysis it is useful to count the number of observed honest sessions and the number of maliciously altered sessions separately. In addition, we will not limit to full sessions: the adversary can stop forwarding honest flows, making the session abort. Then, there can be passive full/partial sessions: Definition 5.4.1 (Passive Session). A (full or partial) session between oracles π j T and π k S is called passive, if the messages of all queries SendTerm(j, •) or SendServ(k, •) are either Start(•) or themselves an output of one of these two queries type. If flows are numbered, this also implies that the actual order of flows between T and S has not been modified. If all the outputs have been forwarded as inputs, this is a passive full session, otherwise this is a passive partial session.

Sessions that are not passive are called active, since the adversary altered something in the honest execution.

This notion is stronger than the Execute-queries defined in the BPR security model, since the adversary does not need to decide from the beginning if all the exchanges will be passive or not. A can start with a passive sequence and decide at some point to stop (passive partial session) or behave differently in an adaptive way (active session).

Resources of the adversary. When doing security analyses, for every adversary and its privacy and authentication advantages, one also has to specify the adversarial resources such as the running time t, the number of oracle queries, the number of player instances, and the numbers n passive /n active of (fully) passive and active sessions the adversary needs.

Discussion. We discuss a bit more about our security definitions to explain why they capture the practical threats. First, a passive network adversary is able to observe legitimate communications via SendServ and SendTerm-queries (these will satisfy the passive session definition). An active network adversary can modify legitimate messages or impersonate a terminal or a server by injecting some messages of its choice, again, via SendServ and SendTerm-queries. This models, in the standard way, possible insecurity (in terms of privacy or authentication) of the network channel between terminals and servers.

Passive-insider attacks (such as key logger and screen capture malware compromising computers or their browsers) are modeled by Compromise-queries followed by SendTermqueries. The former gives the adversary full information about the terminal's internal state, including its random coins and registers' contents, and the latter reveals to the adversary the inputs from the human.

We consider even more powerful attackers who can take full control of the computers or some of their crucial applications such as browsers. In this case, in addition to learning the internal state and all the inputs, the adversary can impersonate the honest terminal while sending adaptively selected messages to the human. We model this by Infect and SendHum-queries.

Our model captures all the above scenarios and, moreover, it takes into account the possibility of multiple simultaneous attacks, such as colluding network and malware adversaries. One can notice that attacks involving Infect-queries are stronger than those with Compromisequeries: when an adversary infects a terminal, it takes full control on it, with knowledge of its internal state, and thus plays on its behalf, using SendServ and SendHum-queries.

Note that in any case, we are concerned with the security of a new session, in terms of privacy and authentication, over an honest terminal, that is neither compromised nor infected. Such security should be guaranteed even though the other sessions involving the same human with the same long-term secret were carried over compromised terminals, and if possible even over infected terminals. We model privacy via the Test-query and with the appropriate privacy advantage definition. We model authentication via the corresponding advantage definition.

We also stress that we do not consider corruption of the long-term secrets, since they are known by the users and the server only, and we do not allow to corrupt them. Would the long-term secret be leaked, we cannot guarantee any security for future sessions. The interesting open problem of dealing with such corruptions could be addressed using an asymmetric long-term secret: a verifier-based variant that would just provide an encoded version of the user's secret to the server.

Generic HAKE constructions

In this section, we propose two generic HAKE protocols. They build on a simple idea of composing a HCFF with a regular PAKE protocol used in black box. More precisely, a server chooses a random challenge x, the user U 's response is r = F K (x), where F is an HCFF and Human c,x S ,s K is the long-term secret shared between the user and the server. And finally the terminal and the server execute the PAKE on the one-time password r, as in [START_REF] Kenneth | One-Time-Password-Authenticated Key Exchange[END_REF]. As already mentioned, whereas the server supports concurrent sessions, since the human does not, there is no sense in maintaining multiple session states for one human user. However, a straightforward replay attack is possible. The adversary can first just eavesdrop a session by compromising a terminal, and then play on behalf of the server with the observed challenge-response pair (x, r), even when the user uses an honest terminal. The main issue is that there is no reason for the challenge to be distinct in the various sessions if we do not add a mechanism to enforce it. In [START_REF] Kenneth | One-Time-Password-Authenticated Key Exchange[END_REF]'s constructions, they assume the server is stateful to prevent it. However, we can do better. This is the goal of our first protocol: it adds a coin-flipping protocol between the terminal and the server to avoid either party to influence the challenge x, and thus to avoid the aforementioned replay attacks. We prove it secure (in terms of privacy, which implies implicit authentication) assuming security of commitments (underlying the coin-flipping), HCFF, and PAKE. However, the concrete security depends on the bound η, which is large enough for our device-based HCFF, but the only-human HCFF construction we will propose in Section 5.2 (and its underlying hardness problem) does not tolerate a high η.

U (K ) Terminal T Server S(K ) -------→ x T $ ← Z |C| (c, s) ← Com(x T ) , c -------→ x ← ------- x ← g(x S + x T ) x S ← ------- x S $ ← Z |C| r ← F K (x) r -------→ s -------→ x T ← Open(c, s) x ← g(x S + x T ) r ← F K (x) PAKE(r)
Hence, the goal of our second HAKE protocol is to add explicit authentication, which will help limiting the number of malicious challenge-response pairs the adversary can see, or at least to detect them: the user can then suspect the terminal to be infected. We still need the concrete HCFF to tolerate at least one malicious challenge, but this remains a reasonable assumption.

The Basic HAKE

Our first construction makes use of a commitment scheme, an HCFF, and a PAKE.

Description. Let (KG, F ) be a human-compatible function family with challenge space C, let CS = (Setup, Com, Open) be a commitment scheme, let pake be a password authenticated key exchange protocol and let g : Z |C| → C be a bijection. We construct the Basic HAKE (LKG = KG, KE). Its interactive KE protocol is described on Figure 5.2, here are the descriptions.

• KE execution:

1. When the user invokes a terminal to establish a connection with the server, the terminal chooses its part of the challenge x T , and commits it for the server. It also sends the user's identifier ;

2. Upon receiving the commitment, the server waits until any previous session for U finishes, then it chooses its part of the challenge x S , and sends it in clear to the terminal;

3. The terminal then combines both parts x T and x S to generate the challenge x = g(x S + x T ), and asks x to the user; 4. Upon reading the challenge x, the user computes and writes down the response r for the terminal;

5. When the terminal receives the response r from the human user, it opens its commitment to the server, and can already start with the PAKE protocol execution;

6. Upon receiving the opening value of the commitment, the server opens the latter to get x T . It can then combine both parts x T and x S to generate the challenge x = g(x S + x T ), and compute the response r. It can then proceed with the PAKE protocol too.

The terminal and the server both run the PAKE protocol with their (expected) common input r and a session id that is the concatenation of the transcript. At the end of the PAKE execution, they come up with two session keys, sk T and sk S , respectively, that will be equal if both parties used the same r in the PAKE. Since we do not consider explicit authentication, accept and terminate flags are not set.

Correctness of the Basic HAKE construction follows from correctness of the building blocks.

Security analysis.

For Basic HAKE, we only assess privacy of the session key, since this protocol does not provide explicit authentication3 .

Theorem 5.5.1. Consider the Basic HAKE protocol defined in Figure 5.2. Let A be an adversary against the privacy security game with static compromises, running within a time bound t and using less than n comp compromised terminal sessions, n uncomp uncompromised terminal sessions, n serv server sessions and n active ≤ n comp + n uncomp + n serv active sessions. Then there exist an adversary B 4 attacking the 2-party n comp -unforgeability of the HCFF with q r , q c , q t queries of the corresponding type, an adversary A and a distinguisher B 3 attacking UC-security of the PAKE with a simulator S pake as well as three adversaries D 1 , D 2 , and B 2 against the commitment scheme properties, all running in time t, such that

Adv priv HAKE (A) ≤ Adv ncomp-uf F (B 4 ) + 2 × Adv pake pake (S pake , A , B 3 ) + 2 × Adv setup-ind CS (D 1 ) + Adv s-eq CS (D 2 ) + Adv s-binding CS (B 2 ) ,
where q r ≤ n comp , q t ≤ n active , and q c ≤ n uncomp + n comp + n serv .

Discussion. Concrete security of the HCFF is definitely the most crucial compared to that of other building blocks, since it is hard to balance strong security and usability. This is why we emphasize this in the above theorem. We note that the sessions which lead to TestResp-queries have non-oracle-generated flows and therefore correspond to classical on-line dictionary attacks: the adversary simply tries to impersonate the user/terminal to the server (or vice-versa), with a guess for the answer r (unless the query has been asked to the GetResp-oracle). Indeed, sessions with GetRespqueries on the exact challenges have compromised terminals and correspond to spyware key loggers that record random challenge-response pairs. If using such a compromised terminal can be considered rare, this remains reasonable. Eventually, the sessions which lead to GetResp-queries on different challenges are the most critical, but they should likely fail. And we expect them to be quite exceptional. As remarked above, such sessions likely conclude to a failure: no concrete session is established with the server the user wanted to connect to (if the HCFF is still secure after such adaptive queries). If the user can detect such a failure, he can run away from this terminal. We now propose a way for the user to detect such a dangerous terminal, and thereafter take appropriate measures. At the same time, our next proposal will achieve explicit authentication.

Proof. We define a series of games that aims at bounding the privacy advantage of A. We denote B i the simulator for Game G i , that outputs 1 if b ← A (A wins in guessing b) and 0 otherwise. We also define D i the distinguisher between games G i and G i-1 , for i > 1. In general, the distinguisher D i between the two successive games exactly behaves as the simulator in G i-1 with all the secrets, but just interactions with two distributions to distinguish (either on sets or on oracles). The distributions on the outputs are thus as close as the input distributions which are close enough under a computational assumption. We start from G 0 , the privacy security game, between the adversary A and the challenger. We rewrite it below, with explicit definitions of the queries. Then, in the last game, we explain how a simulator does without knowing anymore the long-term secret keys but using instead the oracles GetResp, GetRandChal, and TestResp to replace calls to F K .

We stress that the corruptions are static, which means that Compromise-queries must happen before any other flow in a terminal session. However, infections can still be adaptively made (but on compromised sessions only).

We also require the internal PAKE primitive (denoted by the double arrow on the Figure 5.2) to be UC-secure (see Figure 2.2), as we will need the ideal functionality F pake and the simulator S pake in the proof. In particular, we need to be able to simulate transcripts between honest players, without knowing the password, and we will need to be able to extract the password tried by the adversary. On the other hand, we will have to be able to simulate the answers to the TestPwd queries.

In several games, some steps will depend on whether the input message is oracle-generated, meaning it is the output of another oracle and whether the terminal (be it the source of an oracle-generated message or the local oracle) is compromised or not.

In the case of SendTerm-queries, we will use the terminology compromised or uncompromised to denote the fact that the local terminal instance was compromised or not, as well as oraclegenerated or non-oracle-generated to denote the fact the input message was generated as output by a server oracle (from a SendServ-query).

In the case of SendServ-queries, the terminology will be remote-compromised or remoteuncompromised to denote the fact that the input message was generated as output by a terminal oracle (from a SendTerm-query) that is compromised or not. However, when the input message does not come as an output of a server oracle it is called non-oraclegenerated. Therefore there are three cases : remote-compromised, remote-uncompromised, and non-oracle-generated.

Game G 0 : In this game, the simulator generates the public parameters for the HC function, the commitment, and the PAKE. It also knows all the long-term secret keys of the users, which allows it to simulate every oracle π j P , as the latter would do in the real protocol, with a random bit b: T : run the PAKE protocol on r 7. SendHum(j, x) (from an infected terminal π j T ): Compute and return r ← F K (x) 8. Compromise(j, ): Unless a Start-SendTerm-query has already been sent to π j T , mark the instance π j T as compromised and reveal the random tape. 9. Infect(j): mark the session as infected, allowing SendHum 10. Test(j, P ): according to b, and whether π i P is fresh or not, the real key sk P , or a random key, or ⊥ is returned.

By definition Adv

| Pr G 1 [b ← A] -Pr G 0 [b ← A]| ≤ Adv setup-ind CS (D 1 )
, where D 1 behaves as B 0 , with either

Setup (which is G 0 ) or Setup (which is G 1 ).
Game G 2 : We can now enforce random challenges, by extracting the adversary commitments and generating a commitment on a value that complements appropriately.

In order to enforce random challenges:

• When processing SendServ(k, ( , c)), when c is non-oracle-generated or remotecompromised (the terminal is compromised or infected), we extract x T and generate x S ← g -1 (x) + x T so that g(x T + x S ) is the expected random challenge;

• When processing SendTerm(j, Start( )) and SendTerm(j, x S ), if the terminal is not compromised, it generates a fake commitment as output of the first query and will opens it to an x T that complements correctly with x S in the later one.

If the enforced random challenge does not get the expected value when processing SendServ(k, s), the simulator B 2 outputs (c, s) that breaks the strong binding extractability. Moreover, the strong simulation indistinguishability ensures that otherwise it is hard to distinguish this game from the previous one, by defining D 2 exactly as the simulator B 1 , using either Com/Open (which is G 1 ) or SimCom/OpenCom (which is G 2 ).

Hence, under the strong-security of the commitment scheme, the simulation remains the same to the adversary:

| Pr G 2 [b ← A] -Pr G 1 [b ← A]| ≤ Adv s-eq CS (D 2 ) + Adv s-binding CS (B 2 )
Game G 3 : We now use S pake to emulate all the messages our simulator should send for the

PAKE protocol: | Pr G 3 [b ← A] -Pr G 2 [b ← A]| ≤ Adv pake pake (S pake , A , B 3
). Since we are using a UC-secure PAKE, unless that adversary has guessed the password r, it has no information about the session key. As a consequence, unless the adversary has asked a successful TestPwd query (event GuessedPwd), he has no advantage in breaking the privacy of our HAKE: 2

× Pr G 3 [b ← A] -1 ≤ Pr G 3 [GuessedPwd].
As a consequence,

Adv priv HAKE (A) ≤ Pr G 3 [GuessedPwd] + 2 × Adv pake pake (S pake , A , B 3 ). + 2 × Adv s-eq CS (D 2 ) + Adv s-binding CS (B 2 ) + Adv setup-ind CS (D 1 )
Game G 4 : Eventually, we can make use of oracles GetResp, GetRandChal, and TestResp to replace calls to F K : we do not know anymore the long-term keys of the users, and we focus on a user U = U (all the other calls can be made as above), but we know the trapdoor for the commitment scheme.

Thanks to the extractable and equivocal commitment scheme, we can inject random challenges and use the adversary to break the HC function on one of them. The simulator will indeed be able to set x of its choice (from the HC function random selection) for either the server oracle or the terminal oracle, while the adversary has to commit its share and cannot equivocate.

Let us now give the details of the final game: the simulator uses the simulator S pake to generate the public parameters for the PAKE, generates the public parameters for the commitment with the trapdoors (for extraction and equivocality), and uses the challenge instance of the HCFF for the parameters of F . It also sets Λ to an empty set.

It will be used to keep track of the known challenge responses. Then it answers the oracle queries as follows:

1. SendServ(k, ( , c)):

• • If uncompromised and non-oracle-generated, use the simulator S pake to generate the terminal flow. In case of a TestPwd query on a candidate r A run TestResp(r A , b x ) 7. SendHum(j, x) (from an infected terminal):

• If (x, r) ∈ Λ for some r, output r ;

• Otherwise, compute r ← GetResp(x), store (x, r) in Λ and output r. 8. Compromise(j, ): (unchanged) Unless a Start-SendTerm-query has already been sent to π j T , mark the instance π j T as compromised and reveal the random tape. 9. Infect(j): (unchanged) mark the session as infected, allowing SendHum 10. Test(j, P ): (unchanged) according to b, and whether π i P is fresh or not, the real key sk P , or a random key, or ⊥ is returned.

Note that the event GuessedPwd now means that a TestResp-answer was positive, we no previous GetResp-query. This is exactly a success in the unforgeability of the HCFF, so

Adv priv HAKE (A) ≤ Adv ncomp-uf F (B 4 ) + 2 × Adv pake pake (S pake , A , B 3 ). + 2 × Adv s-eq CS (D 2 ) + Adv s-binding CS (B 2 ) + Adv setup-ind CS (D 1 )
We now have to count how many queries are asked by our simulator B 4 in Game G 4 .

One can note from this simulation that any interaction between the adversary and a safe player (uncompromised terminal/server) results in a x ∈ Λ 0 (generated by a GetRandChalquery from the simulator on behalf of the safe player). Moreover,

• in each passive session with an uncompromised terminal, there is just a GetRandChalquery;

• for each server interacting with a compromised terminal, the simulator makes use of a GetRandChal-query, a GetResp-query and a correct TestResp, hence ctr overall stays the same;

• in each session between a uncompromised terminal and an adversary trying to impersonate the server (some non-oracle-generated flows), there might be a GetRandChal-query and a TestResp-query;

• in each session between a compromised terminal and an adversary trying to impersonate the server (some non-oracle-generated flows) with an x of its choice, there might be a GetResp-query (and a GetRandChal in some cases), but no TestResp. Hence, ctr is incremented.

• in each session with an infected terminal that directly queries the user on its own challenge, there is a GetResp-query. Hence ctr is incremented.

• in each session between an honest server and an adversary playing on behalf of the user/terminal (after infecting or not the terminal), there are a GetRandChal-query and a TestResp-query. If one of the two previous terminal session situations occurred between those, the TestResp will decrement ctr6 if the PAKE succeeds Or none occurred, in which case π k S is fresh, but a success of the PAKE means winning the unforgeability game; As a consequence,

• a GetResp-query only appears in sessions with a compromised terminal Hence, q r is at most the number of compromised terminal sessions, that is c,x S ,s) Parses key:

q r ≤ n comp ; Human U (K ) Terminal T Server S(K ) accept ← False accept ← False terminate ← False terminate ← False -------→ x T $ ← Z |C| (c, s) ← Com(x T ) , c -------→ x ← ------- x ← g(x S + x T ) x S ← ------- x S $ ← Z |C| r ← F K (x) r -------→ s -------→ x T ← Open(c, s) accept ← True x ← g(x S + x T ) r ← F K (x) PAKE(r)
(k T ||sk T )
Parses key: (k S ||sk S ) • a TestResp-query only appears in sessions between a safe player (uncompromised terminal or honest server) and the other being impersonated by the adversary. In particular, such sessions are active, hence q t is at most the number of active sessions (n active ).

accept ← True x U $ ← C x U -------→ X U ← Enc[k T ](x U ) X U -------→ x U ← Dec[k S ](X U ) Verifies r U r U ← -------r U ← Dec[k T ](R U ) R U ← ------- R U ← Enc[k S ](F K (x U )) Outputs sk T Outputs sk S terminate ← True 0/1 -------→ terminate ← True
q t ≤ n active ;

• a GetRandChal-query only appears in sessions with a safe player (uncompromised terminal or honest server) or, in some cases, in sessions where a GetResp-query was issued. Hence, q c is at most the sum of the number of uncompromised terminal sessions (n uncomp ), GetResp-queries and the number of server sessions with a non-oracle-generated flow ( , c) (n nogc ),

q c ≤ n uncomp + q r + n nogc ≤ n uncomp + n comp + n serv .
• ctr is only incremented by compromised terminal session in which a GetResp-query was asked, while no concurrent server session successfully terminated. Unfortunately, such a situation is not reliably detectable by the human, though it will play an important role for the Confirmed HAKE.

ctr ≤ n comp

The Confirmed HAKE

We now enhance the Basic HAKE by adding two confirmations flows (see Figure 5.3) that allow the user to detect a bad behavior of the adversary, who compromised the device, and take appropriate measures. This can happen in two different scenarios: the adversary has compromised a terminal and additionally plays on behalf of the server, which allows it to ask any query to the user through the terminal, or the adversary has infected a terminal that allows it to directly ask any query to the user. As said above, such dangerous cases lead to no connection with the expected server. The user will thus check whether he built a secure session with the expected server, who should be able to answer a fresh random challenge. This is performed under the fresh key, established with the PAKE, using a secure authenticated encryption. As shown below, the two additional flows will not only provide explicit authentication, but also allow the user to detect such bad events and take measures. For this, it is important that the user does not start multiple sessions concurrently, which is anyway not realistic for a human (as already noticed above).

Description. The protocol is similar to Basic HAKE, but it uses an additional building block, an authenticated encryption scheme ES = (Enc, Dec), that is used in the new last stage of the protocol. The complete description is given in Figure 5.3.

Since we now consider the authentication of the players, we additionally include accept and terminate flags in the protocol: The user U accepts after sending the first response while the server S accepts after the PAKE. Then both terminate when they have the confirmation of the other partner. More precisely, the user terminates after sending the last bit (1 for acceptance and 0 for rejection) to the terminal (thus having verified the server's response in the last stage), and the server terminates after sending the encrypted response (thus having checked the terminal can generate a valid cipher text).

Note that if the protocol terminates, sk T and sk S must be equal, since our additional flows act as confirmation flows for the PAKE.

Security analysis. We now present Theorem 5.5.2 regarding the security of our Confirmed HAKE in the HAKE privacy and authenticity experiment.

While it relies on the same security properties of PAKE, authenticated encryption, commitment scheme and HCFF, a critical parameter is added, the number of human sessions that reject in the end.

Indeed, the explicit authentication property we achieve means that any attempt at issuing an adaptive query unrelated to the challenge will likely lead to a failure of the PAKE protocol, which can in turn be detected by the human, as he does not get the answer to x U he looked for. This allows to use a much more restricted η in the HCFF unforgeability game (up to η = 1 for a very strict human user), which is a much more reasonable goal for an only-human HCFF such as the one derived from [START_REF] Blocki | Towards Human Computable Passwords[END_REF], that we will present in Section 5.2.2 Theorem 5.5.2. Consider the Confirmed HAKE protocol defined in Figure 5.3. Let A, A be adversaries against the privacy and authenticity security game of HAKE within a time bound t and using less than n comp compromised terminal sessions, n uncomp uncompromised terminal sessions, n serv server sessions, n active ≤ n comp + n uncomp + n serv active sessions and n hr human session that reject in the end. Then there exist two adversaries B 1 , B 1 attacking the 2-party (n hr + 1)-unforgeability of HCFF with q r , q c , q t queries of the corresponding type, two adversaries B 2 , B 2 and two distinguishers B 3 , B 3 attacking UC-security of the PAKE with the simulator S pake , two adversaries B 4 , B 4 against the authenticated encryption, as well as six adversaries A 1 , A Privacy proof. The proof is very similar to the previous one, so we just introduce the new queries to add to the security games defined in Section 5.5.2, but only after the execution of the PAKE, and so the simulator (in the real game when it knows all the long-term keys) knows the output (k P sk P ):

Game G 0 : In this game, we simply simulate every oracle according to the protocol, knowing the output of the PAKE, and all the honest players accept at the end of the PAKE.

1. Last SendTerm-PAKE-query (that led to the session key (k T , sk T )): a) generate x U $ ← C (on behalf of the user, and so the internal random coins stay secret even if

π j T is compromised) b) send X U ← Enc[k T ](X U )
2. SendHum(j, x) (from an infected terminal): Not only output r, as before, but additionally generate and send

x U $ ← C. 3. SendServ(k, X U ): Compute and send R U ← Enc[k S ](F K (Dec[k S ](X U ))) (unless the decryption fails, terminate is set to True) 4. SendTerm(j, R U ): Compute r U ← Dec[k T ](R U ) and check whether r U = F K (x U )
or not (on behalf of the user). Unless the decryption fails, if the equality holds, the user accepts and the terminal sets terminate to True

5. SendHum(j, r U ) (from an infected terminal): Accept if r U = F K (x U ).
Game G 1 : In this game, we once again make use of the underlying HC security game oracles. But now, the simulator does not know anymore the long-term keys, and did not learn the output of the PAKE when the simulator S pake was involved.

1. Last SendTerm-PAKE-query:

• If compromised (the simulator honestly ran the PAKE on behalf of the terminal, and so the simulator knows (k T , sk T ), but the adversary too)

a) generate x U ← GetRandChal(1) b) send X U ← Enc[k T ](x U )
• If uncompromised, generate a random ciphertext X U 2. SendHum(j, x) (from an infected terminal), as before, and additionally generate and send x U ← GetRandChal(1)

3. SendServ(k, X U ):

• If remote-compromised, the simulator knows (k S , sk S ) and x U ; it then computes 4. SendTerm(j, R U ):

r U ← GetResp(x U ), stores (x U , r U ) in Λ and sends R U ← Enc[k 0 ](r U ) • If remote-uncompromised,
• If compromised and oracle-generated, r U is known and must be correct so the simulator simply runs TestResp(r U , 1) and terminates

• If compromised and non-oracle-generated, get r U ← Dec[k T ](R U ), and run TestResp(r U , 1), to either terminate or reject (a decryption failure leads to a reject)

• If uncompromised and oracle-generated, terminate

• If uncompromised and non-oracle-generated, reject 5. SendHum(j, r U ) (from an infected terminal): Accept if TestResp(r U , 1).

Note that in the added flows, all GetRandChal and TestResp occur with bit 1, which was only used previously if the terminal oracle was uncompromised, in which case either the adversary issued a correct TestPwd, and the simulator already won the HC unforgeability game, or (k P , sk P ) is unknown and the authenticated encryption hides all flows.

From the previous simulation, in case of passive sessions with a compromised terminal, in the first part of the simulation, the simulator honestly ran the PAKE, completing it with (k T , sk T ). It can thus continue honestly if the adversary continues to forward oracle generated flows. It then learns a new challenge-response pair. If the adversary starts to play on behalf of the server, it has to generate a forgery for the HC function (checked by the TestResp-query).

We will define an adversary B 1 against the combined security notion for authenticated encryption.

In case of passive sessions with an uncompromised terminal, k T is unknown to the adversary, then random ciphertexts can be sent, they are indistinguishable from real ciphertexts (from the semantic security of our secure authenticated encryption scheme, in which case B 1 is used as a distinguisher between the encryption of the real plaintext -as in Game G 0 -or of a random plaintext -as in Game G 1 -). Eventually, if the adversary tries to impersonate the server before the PAKE, and send non-oracle-generated messages to the terminal, they should not be encrypted under the correct key k T , unless the adversary has broken either the integrity of the authenticated encryption (in which case B 1 outputs the fake ciphertext message) or the PAKE (correct guess of r), which would have led to a positive answer to a TestResp during the simulation before: a forgery against the HC function.

As a consequence, unless the adversary has helped the simulator to break the unforgeability of the HCFF, this game G 1 is indistinguishable from the previous one, and leads to accepted sessions by the human user for passive sessions only (with compromised terminals or not) with the expected server, which was our target.

We have already shown that the server could only agree on a key (k P , sk P ) with a terminal linked to the expected human user, hence the global security of our protocol: privacy and authentication. In addition, the two additional flows allow the human user to detect whether the key sk T is shared with the expected server, just leaking one more random challenge-response pair in case of compromised terminal.

With the same reasoning as in the previous proof, we have

Adv priv HAKE (A) ≤ Adv η-uf F (B 1 ) + 2 × Adv pake pake (S pake , B 2 , B 3 ) + 2 × Adv authenc ES (B 4 ) + 2 × Adv setup-ind CS (A 1 ) + Adv s-eq CS (A 2 ) + Adv s-binding CS (A 3 ) .
However, there are a few changes regarding the number of queries involved in the simulation B 5 , but only on compromised sessions, as otherwise the simulator would not have played the PAKE honestly and therefore only random-looking messages are generated:

• There may be an additional GetRandChal in some compromised sessions.

• There may be an additional TestResp-query in some active sessions, but only if the PAKE was passive, without a previous TestResp-query. Otherwise k T is random, and the decryption fails.

• There may be an additional GetResp-query in some server session, if the PAKE succeeded, which means a compromised terminal session must have been used or a win was already reached.

• ctr may incremented, but only if the PAKE succeeded (meaning it was not durably increased by the previous flows). Moreover, if the human accepts, it is decreased (and overall stays the same).

Overall, it is notable that ctr is permanently increased only if the human rejects in the end or the HC unforgeability game is won. Hence: ctr ≤ n hr Moreover, ctr can never reach a value higher than its final value plus one. This means that η = n hr + 1 is sufficient for the HC unforgeability game.

Human

U (K ) Terminal T Server S(K ) -------→ x T $ ← Z |C| (c, s) ← Com(x T ) , c -------→ x ← -------x ← g(x S ⊕ x T ) x S ← ------- x S $ ← Z |C| r ← F K (x) r -------→ y T $ ← Z p Y T ← g y T y S $ ← Z p , Y S ← g y S (c T , s T ) ← Com T (Y T , r) s, Y T , c T -------→ x T ← Open(c, s) x ← g(x S ⊕ x T ) r ← F K (x) Y S , c S ← ------- (c S , s S ) ← Com S (Y S , r) s T -------→ If Open T (c T , s T ) = (Y T , r) then reject If Open S (c S , s S ) = (Y S , r) then reject s S ← ------- Outputs sk T ← (Y S ) y T Outputs sk S ← (Y T ) y S

Time-Based HAKE

Scenario. In this section, we focus on the particular (but quite usual) case where the physical device does not have a dedicated input but uses time instead to compute its output. More precisely, our protocol considers a device, such as the RSA-SecurId [RSA] token, that, based on an internal seed (the long-term key K ), generates a one-time password (the value F K (t), based on the time period t), and displays it on an LCD screen. The password is tied to an internal clock, and changes every τ (e.g. 30s). Note that such a password is already human readable and human writable, hence it satisfies our human-compatible communications.

Building on the security model presented in Section 5.4, we now consider time as a variable, that is to be segmented into timeframes (each spanning τ second). We then number those timeframes and associate to each message sent between T and S this number, representing the fact that each party can measure time and identify the timeframe in which the message was sent.

Since the one-time passwords are generated by a secure device implementing F K , we can make the assumption that, for each timeframe, the output is indistinguishable from an element sampled from the distribution D with entropy greater than D (which increases the advantage of an adversary A by at most Adv dist-T F (A) after T timeframes). We rely on the requirement that any user U can only make use of one terminal during a timeframe. That is, he may not attempt to authenticate using more than one terminal in a single time period.

Protocol. We now propose a protocol for called Time-Based HAKE that is suitable for this setting. It is presented on Figure 5.5. As in the previous Simplified Basic HAKE, it makes use The commitment scheme CS is initialized twice, with two independent setups, leading to

Time Human U Terminal T Server S ≤ t accept ← False accept ← False terminate ← False t ----→ x T $ ← Zp, X T ← g x T x S $ ← Zp, X S ← g x S t pw t ----→ (c T , s T ) ← Com T (X T , pw t ) , X T , c T -------→ t accept ← True X S , c S ← ------- (c S , s S ) ← Com S (X S , pw t ) . . . Wait for timeframe > t Wait for timeframe > t > t s T -------→ If Open T (c T , s T ) = (X T , pw t ) and ( , t) ∈ Λ, store ( , t) in Λ > t Otherwise reject > t accept ← True > t Reject if Open S (c S , s S ) = (X S , pw t ) s S ← ------- Outputs (X T ) x S > t Outputs (X S ) x T terminate ← True
Com T /Open T and Com S /Open S , each of them being used for the commitments generated by the terminal and the server, respectively. We also set up a group G of prime order p in which the discrete logarithm problem is believed to be hard. Let g be a generator of G.

The protocol itself is split into two parts: the commitment phase which must happen during a timeframe t (that we will call the session timeframe) and the verification phase, that must happen later than the session timeframe.

This delay is a clear limitation on the total speed of the protocol, which on average will take τ /2. It will, however, prove necessary, as it allows F K (t) to be revealed without compromising the security of the scheme, therefore building on the one-time specificity of the password. To enforce a unique session in a timeframe, the server will not accept to run several sessions within the same timeframe, with the same user, as the latter should not do it anyway (see above). This would thus come from an adversary, and then allowing multiple sessions in a timeframe t can compromise other sessions in the same timeframe when F K (t) is revealed.

It is interesting to note that this protocol uses the time period t as the HAKE challenge (the challenge is a counter) and the one-time password (F K (t)) read from the device as the human's response. Therefore, partnering between U and S is entirely determined at the end of the session timeframe t.

Security analysis.

In the security analysis, as in the previous analyses, we only consider static compromises. Hence Compromise(j) can only be the first oracle query of a session, and Infect(j) can only affect compromised sessions. Since compromises are known before the first flow and partnering between Human and Server is determined at the end of timeframe t, this means that freshness itself can be perfectly ascertained in any timeframe > t.

The security of our protocol heavily relies on the strong-security of the commitment scheme (see Section 2.3.1), as well as the indistinguishability of the password sequence distribution (see Section 5.1.2).

Theorem 5.6.1. Consider the Time-Based HAKE protocol defined in Figure 5.5. Let A, A be adversaries against the privacy and user authentication security games with static compromises, running within time t A and using less than n serv non-passive sessions against the server oracle, n term non-passive sessions against the terminal oracle, n total > n term + n serv total sessions and T < n total unique timeframes. Then there exist an adversary D 1 against the indistinguishability of the password distribution D running in time t, an adversary D 5 against the DDH experiment running in time t + 8n total τ exp , four adversaries B 3 , B 5 , D 2 , and D 3 against the commitment scheme properties running in time t:

Adv priv HAKE (A) ≤ (n serv + n term ) × 2 -D + Adv dist-T F (D 1 ) + Adv ind ddh (D 5 ) + Adv binding CS (B 3 ) + Adv setup-ind CS (D 2 ) + n total × Adv s-eq CS (D 3 ) + Adv s-binding CS (B 5 ) Adv u-auth HAKE (A ) ≤ (n serv + n term ) × 2 -D + Adv dist-T F (D 1 ) + Adv setup-ind CS (D 2 ) + n total × Adv s-eq CS (D 3 ) + Adv s-binding CS (B 5 ),
with τ exp the time necessary to exponentiate one group element, and n total the global number of sessions.

Remark 5.6.2. Note that the Time-Based HAKE only achieves user authentication in our setting, since server authentication requires the server identity to be approved by the human in our setting (the terminal could be infected so it cannot be relied on). A similar approach to the one of the Confirmed HAKE could be used to achieve a full mutual authentication.

Proof. Once again, we will denote B i the simulator for Game G i that outputs 1 if b ← A and 0 otherwise and define D i the distinguisher between games G i and G i-1 , for i > 1.

Game G 0 : This is the real game, where the adversary outputs its guess on the bit b:

Adv priv HAKE (A) = 2 × Pr G 0 [b ← A] -1.
Game G 1 : In this game the simulator will execute the real protocol, generating a password pw t $ ← D at the beginning of each timeframe t and subsequently using it whenever necessary. We will also consider a flag, NOG-Com-OK, which can be raised during the execution of the simulation. More precisely, in G 1 , the simulator answers each request as follows:

1. SendServ(k, ( , X T , c T )): Set the current timeframe t to be π k S 's session timeframe. Generate x S $ ← Z p and X S ← g x S . Then set (c S , s S ) ← Com(X S , pw t ) and send (X S , c S ).

2. SendServ(k, s T ): Check whether Open(c T , s T ) = (X T , pw t ).

• If so, send s S , accept and set sk S = (X T ) x S . Additionally, if π k S is fresh and c T was not oracle-generated, raise flag NOG-Com-OK.

• If the equality is not verified reject. 3. SendTerm(j, Start): Set the current timeframe t to be π j T 's session timeframe. Generate x T $ ← Z p and X T ← g x T . accept on behalf of the human and use the current password pw t to set (c T , s T ) ← Com(X T , pw t ) and send ( , X T , c T ). Additionally, if π j T is compromised, reveal the password pw t .

4. SendTerm(j, (X S , c S )): Wait until the timeframe is > t, then send s T .

5. SendTerm(j, s S ): Check whether Open(c S , s S ) = (X S , pw t ).

• If so, set sk T = (X S ) x T . Additionally, if π j T is fresh and c S was not oraclegenerated, raise flag NOG-Com-OK.

• If the equality is not verified, reject. 6. SendHum(): If π j T was marked as infected, reveal pw t , where t is the current timeframe and accept.

7. Compromise(j): Mark π j T as compromised and reveal the random tape. 8. Infect(j): If π j T is compromised through a previous Compromise(j) query, mark it as infected, allowing SendHum queries. 9. Test(j, P ): according to b and whether π j P is fresh or not, the real key sk P , a random key or ⊥ is returned.

It should be clear that this simulation performs exactly as the real game should, except for using the global distribution D to generate the passwords, since the additional flags are purement formal but do not affect the simulation. Hence:

|Pr G 1 [b ← A] -Pr G 0 [b ← A]| ≤ Adv dist-T F (D 1 ),
where D 1 behaves as B 0 but using either distribution D (which is then G 1 ) or the real distribution (as in G 0 ) to generate the passwords pw t .

Game G 2 : In this game, unless the oracle is compromised, we will reject all openings for non-oracle-generated commitments. More precisely, we change the query answers as follows:

2. SendServ(k, s T ): If c T was oracle-generated and Open(c T , s T ) = (X T , pw t ), send s S , accept and set sk S (X S ) x T . Otherwise reject. 5. SendTerm(j, s S ):

• If compromised, act exactly as in G 1

• Otherwise: If c S was oracle-generated and Open(c S , s S ) = (X S , pw t ), accept and set sk T = (X S ) x T . Otherwise reject.

Obviously, games G 2 and G 1 are not indistinguishable. However, this can only make a difference when NOG-Com-OK was raised. Hence:

|Pr G 2 [b ← A] -Pr G 1 [b ← A]| ≤ Pr G 1 [NOG-Com-OK]
Game G 3 : In this game, we further straighten our requirements for openings in noncompromised terminals. Indeed, we will also reject an opening if it opens to a different X S /X T than the one it was initially generated for. More precisely: 1. SendServ(k, ( , X T , c T )): Act as in G 1 . Then store (c S , X S , s S ) ∈ Υ S .

SendServ(k, s

T ): If Open(c T , s T ) = (X T , pw t ) and (c T , X T , •) ∈ Υ T , send s S ,
accept and set sk S = (X S ) x T . Otherwise reject. 3. SendTerm(j, Start): Act as in G 1 . Then store (c T , X T , s T ) ∈ Υ T .

Hence, using a distinguisher D 5 , that behaves as B 5 with C either real (as in G 4 ) or random (which is G 5 ):

|Pr G 5 [b ← A] -Pr G 4 [b ← A]| ≤ Adv ind ddh (D 5 ),
Note that our simulator makes 8 exponentiations to simulate any session in addition to the running time of A, so D 5 runs in time t A + 8n total τ exp with t A the running time of A and τ exp the time necessary to exponentiate one group element. When C is random, then every sk P is random and independent of all others. Hence one cannot distinguish the real key from a random key, since they are both random:

Pr G 5 [b ← A] = 1/2.
As a consequence, Adv priv HAKE (A) ≤ Pr We now need to bound the probabilities of events NOG-Com-OK in Game G 1 . For this, we construct another series of games from Game G 1 , in which we will consider the probability of raising a flag instead of the regular advantage over the Test-queries. For the sake of simplicity, we will denote the simulators in this branch C i for Game G i .

Game G 2 : In this game, we go back to Game G 1 and change the simulator's behavior to make use of the equivocality property of our commitment scheme. But before any equivocation, we just change the setup procedure of the commitment:

|Pr G 2 [b ← A] -Pr G 1 [b ← A]| ≤ Adv setup-ind CS (D 2 ),
where D 2 is a distinguisher that behaves as B 1 , with either Setup (which is G 1 ) or Setup (which is G 2 ).

Game G 3 : The simulator can now use its oracle access to equivocal commitments whenever it has to use commitments in order to delay the actual committed value. However, if the terminal is compromised, we will still use regular commitment algorithms. This is due to the fact that the adversary knows the random tape and can therefore deterministically reproduce the output of Com. The simulator runs as follows:

1. SendServ(k, ( , X T , c T )): Set the current timeframe t to be π k S 's session timeframe. Generate x S $ ← Z p and X S ← g x S . Get c S ← GenEquivCommit and send (X S , c S ). 2. SendServ(k, s T ): Check whether Open(c T , s T ) = (X T , pw t ).

• If so, send s S ← OpenEquivCommit(c S , (X S , pw t )), accept and output sk S = (X T ) x S . Additionally, if π k S is fresh and c T was not oracle-generated, raise flag NOG-Com-OK.

• Otherwise output ⊥. 3. SendTerm(j, Start): Set the current timeframe t to be π j T 's session timeframe and generate x T $ ← Z p and X T ← g x T . Then:

• If compromised: Act as in G 1 .

• If uncompromised: Get c T ← GenEquivCommit and send ( , X T , c T ). 4. SendTerm(j, (X S , c S )): Wait until the timeframe is > t. Then:

• If compromised: Act as in G 1 .

• If uncompromised: Send s T ← OpenEquivCommit(c T , (X T , pw t )). 5. SendTerm(j, s S ): Check whether Open(c S , s S ) = (X S , pw t ).

• If so, generate and output sk T = (X S ) x T Additionally, if π j T is fresh and c S was not oracle-generated, raise flag NOG-Com-OK.

• Otherwise output ⊥. The difference is just in the use of equivocal commitments instead of real ones:

|Pr G 3 [b ← A] -Pr G 2 [b ← A]| ≤ n total × Adv s-eq CS (D 3 ).
where D 3 is a distinguisher that behaves as C 2 but uses either real (like in G 2 ) or equivocal (as in G 3 ) commitments.

Game G 4 : One could remark that in the previous game, unless the session is compromised, the simulator doesn't use pw t in any timeframe ≤ t. Therefore, in this game, the simulator will delay producing pw t until the timeframe t has ended unless Compromise is called. This can be done using the same oracle handlers as in G 3 , simply adding the password definition: Game G 5 : We will now use the extractability property of our commitment scheme to check the adversary's commitment, by modifying the simulator as follows:

1. SendServ(k, ( , X T , c T )): If c T was not oracle-generated, extract (X * T , pw * t ) ← ExtractCommit(c T ). Then act as in G 4 . 2. SendServ(k, s T ): If c T was oracle-generated, act as in G 4 . Otherwise, generate pw t $ ← D t . Then check whether (X * T , pw * t ) = (X T , pw t ). • If so, send s S ← OpenEquivCommit(c S , (X S , pw t )), accept and output sk S = (X T ) x S . Additionally, if π k S is fresh, raise flag NOG-Com-OK. • Otherwise output ⊥. 4. SendTerm(j, (X S , c S )): Extract (X * S , pw * t ) ← ExtractCommit(c S ). Then act as in G 4 .

5. SendTerm(j, s S ): If c S was oracle-generated, act as in G 4 . Otherwise, check whether (X * S , pw * t ) = (X S , pw t ).

• If so, generate and output sk T = (X S ) x T Additionally, if π j T is fresh and c S was not oracle-generated, raise flag NOG-Com-OK.

• Otherwise output ⊥. Note that in this game, except for compromised sessions, pw * t is obtained before pw t is generated. Hence Pr[pw t = pw * t ] = 2 -D . The only way to distinguish Game G 5 from Game G 4 would be if (Open(c P , s P ) = ExtractCommit(c P ). But if so, then (c P , s P ) breaks the strong binding extractability, which can be output by a simulator B 5 similar to C 5 . Hence: Moreover, we can now bound the probability that those flags are raised in Game G 5 . Indeed, for it to happen, there must exist an oracle π j P such that (X * P , pw * t ) = (X P , pw t ). In particular, we must have pw * t = pw t . Moreover, this cannot happen if the session was passive. Hence, Authenticity proof. The simulated Game G 1 is indistinguishable from the real world (be it in the privacy security game or the authentication security game).

To break user authentication means that the adversary successfully opened a commitment c T to X T , pw t without interacting with U . This is exactly the situation in which flag NOG-Com-OK is raised. Hence:

Adv u-auth HAKE (A ) ≤ Pr Since SPAKE1 is also proven in the random oracle model, it is fair to use the efficient commitment scheme described in Section 2.3.1. We do not include the redundant X P in s P (it is transmitted at the commitment stage) for the communication complexity, and for a security parameter λ, we assume the group elements to be encoded into 2λ-long bit strings.

While our communication complexity is higher, the computational load is reduced by 30% from [START_REF] Kenneth | One-Time-Password-Authenticated Key Exchange[END_REF] with the most efficient PAKE. Relaxing the PAKE security properties allows a significant gain from the complexity point of view.

Chapter 6 Conclusion and open questions 6.1 Conclusion

In this thesis, we considered several variants of PAKE with an eye toward more usable and more realistic settings.

AKE is the basis for some of the most actually used cryptographic systems, and notably TLS. This is mostly for efficiency reasons as it allows to limit the costly asymmetric cryptographic operations to the bare minimum necessary to establish a shared key, and then rely on faster symmetric cryptographic primitives.

However, this is usually done using a PKI, with signed asymmetric keys as the basis of authentication. While this might be suitable for machine-to-machine interactions, it is not well-suited to human authentication. Indeed, actual human authentication is often performed as an afterthought, with human secrets transmitted over the symmetric channel, after the initial authentication with the PKI. Hence the whole security relies on this PKI-based authentication, which is far from flawless from a practical point of view. For instance, in TLS, it has been shown that in practice certification authorities can be corrupted. Barring that, since what is certified is seldom well understood, it is often enough to use a certificate that looks -to the actual human performing a casual validation -almost the same as the original one (e.g. with a typo in the domain's name).

PAKE is an attempt at using a symmetric authentication, where the secret known by the human is directly used in the authentication, therefore tying directly the human being into the authentication scheme. While there are conceptual difficulties with using a password as authentication -most notably the fact that it has to be provided to all parties in the first place, and their inherent small chance of being guessed -it is also easy to see that it offers less of a gap between the human's expectations and the way the protocol realizes it.

In Chapter 3, we showed how to restrict the regular PAKE UC functionality to really model for only an implicit authentication, instead of the usual explicit leakage toward the adversary. Moreover, we show that a usual PAKE construction -EKE2 -can provide it at no cost. This new primitive allows for new applications of PAKE, in protocols where the result of the PAKE itself needs to be hidden. We actually construct such a protocol in Chapter 4.

In Chapter 4, we presented a variant of PAKE, called fPAKE, that is set to tolerate some slight modifications of the password. This has multiple applications: in the usual "short sequence of alphanumerical symbols" typed by the human sense, it can account for typos and thus encourage to use longer passwords, increasing entropy overall. It can also be very -85 -useful for biometric authentication, where the authentication means' capture is intrinsically fuzzy. We believe this extends the domain of applicability of PAKE, and may lead to more actual applications.

Finally, in Chapter 5, we extended PAKE to show how to account for misbehavior on the part of the computer one is using. More precisely, we tried to tackle the issue that a human authenticating means is likely to be used even in some insecure settings, such as using an unknown computer "just for once", which usually implies all security is forever lost shall this computer be corrupted. Though the proposed solution is far from really usable without an external device, it shows ways in which we could protect sessions even if strong corruptions are considered. It also shows how a tighter interfacing with the human can lead to better security that could ever be provided with a PKI-based AKE, as misbehavior on the server's part is handled directly by the authenticating cryptographic protocol. With this method, even a malicious server cannot learn a password he does not know already, even through the human's mistake.

Open questions

In this thesis, we approached several interesting research questions that are still open to this date. Question 6.1. Can fPAKE be achieved without leaking anything on a successful authentication?

In Chapter 4, we presented several functionalities that model an ideal fPAKE, with an increasing leakage. We showed how to achieve F M fpake -which leaks only correct symbols -with a security bound γ twice as large as the functionality bound δ. In [DHP+18], we also achieve F D fpake , this time with no security gap (γ = δ), but this leaks the actual original password on a successful authentication.

Ideally, we would instead like to achieve F fpake , which can be seen as an extension of F iPAKE and does not leak anything. i.e., even on a successful guess of the password, the adversary would not be provided feedback to learn his attempt was successful. Of course, externally, this does not mean he cannot learn it, but that is only because of a leakage of the general system, and clever usages of fPAKE could make use of this added capability.

Even a simple leakage of whether authentication succeeded, as is done in the F pake functionality, would be better than leaking the password itself, given that passwords tend to be reused by human beings, potentially in systems with different security parameters. This is especially true as part of this functionality use case is biometrics, which cannot be changed at all. Hence guaranteeing the secrecy of the authentication means can be seen as of even more import than authentication itself, since it can be reused in systems with different security.

Question 6.2. Do practical only-human HCFF exist?

In Section 5.2, we presented two instantiations of HCFF, that may be used in our HAKE. The simplest one, if practical, does rely on a token to perform actual computation of the response. The second one, based on the work of [START_REF] Blocki | Towards Human Computable Passwords[END_REF], is only-human, meaning that it really represents operations that could be conducted out of one's head. While there are some hardness results that speak in its favor, resilience to adaptive leakage of challenge-response pairs is hard to achieve and hence has a high cost for the human (in terms of the number of image mappings to memorize and simple operations to perform) which severely impacts the practical applicability of our construction.

Hence we would like to see other, more practical, only-human HCFF functions.

Question 6.3. Can HAKE be achieved without requiring the HCFF function to be resilient to adaptive queries.

A related question is relative to reducing the requirements on the HCFF function. Indeed, with our latter Confirmed HAKE protocol, we are able to detect adaptive queries which can reduce this requirement to actually resisting only one adaptive query on the HCFF function, assuming a very restrictive security policy (i.e., if a potential adaptive query is detected, invalidate the password). While this is doable, it also means that some false positives, such as network timeouts in sensitive parts of the protocol, have to be treated as dangerous attacks, and a new password has to be generated and learned by the human.

Even with the Confirmed HAKE protocol, we still require the HCFF to resist one adaptive query, since without so, the adversary can spoof the detection. This already has a big impact on the HCFF parameters, and adds many constraints on the choice of this function.

Hence producing a HAKE with less stringent requirements on the HCFF would be a very valuable contribution.

Résumé

L'échange de clef authentifié est probablement la primitive asymétrique la plus utilisée, notamment du fait de son inclusion dans le protocole TLS. Pour autant, son cousin, l'échange de clef authentifié par mot de passe, où l'authentification s'effectue par comparaison de mot de passe, l'est bien moins, bien qu'ayant déjà fait l'objet d'études considérables. C'est pourtant une primitive finalement bien plus proche d'une authentification réelle, dès lors qu'une des parties est humaine.

Dans cette thèse, nous considérons des primitives avancées fondées sur l'échange de clef authentifié par mot de passe, en gardant à l'oeil ses applications pratiques. Spécifiquement, nous introduisons une nouvelle primitive, l'échange de clef authentifié par mot de passe approximatif, où la condition de succès de l'authentification est désormais d'avoir une distance suffisamment faible entre les deux mots de passe, et plus nécessairement l'égalité parfaite. Nous fournissons un modèle de sécurité dans le cadre du modèle de composabilité universelle (UC) ainsi qu'une construction reposant sur un partage de secret robuste et des échanges de clefs authentifiés par mot de passe exact.

Dans une seconde partie, nous considérons le problème pratique de la perte du mot de passe dès lors qu'une session est conduite sur un terminal compromis. Étant donné qu'il s'agit d'un problème intrinsèque à l'authentification par mot de passe, nous étendons le modèle BPR habituel pour prendre en compte, en lieu et place du mot de passe, des questionsréponses, toujours de faible entropie. Nous fournissons plusieurs protocoles dans ce modèle, dont certains reposent sur des familles de fonctions compatibles avec les humains, dans lesquelles les opérations requises pour dériver la réponse depuis la question sont suffisamment simples pour être faites de tête, permettant donc à l'humain de s'identifier directement.

Mots Clés

authentification, clef-publique, cryptographie, échange de clef, mot de passe, mot de passe approximatif

Abstract

Authenticated key exchange is probably the most widely deployed asymmetric cryptographic primitive, notably because of its inclusion in the TLS protocol. Its cousin, password-authenticated key exchangewhere the authentication is done using a low-entropy password -while having been studied extensively as well has been much less used in practice. It is, however, a primitive much closer to actual authentication when at least one party is human.

In this thesis, we consider advanced primitives based on password-authenticated key exchange, with an eye toward practical applications. Specifically, we introduce fuzzy password-authenticated key exchange, where the authentication succeeds as long as the two passwords are close enough, and not necessarily equal. We provide a security model in the UC framework, as well as a construction based on regular password-authenticated key exchanges and robust secret-sharing schemes.

Secondly, we consider the practical problem of password leakage when taking into account sessions conducted on a corrupted device. As there is intrinsically no hope with regular password authentication, we extend the BPR security model to consider low-entropy challenge responses instead. We then provide several instantiations, some based on human-compatible function families, where the operation required to answer the challenge are simple enough to be conducted in one's head, allowing the actual authentication to be directly performed by the human being.

Figure 2 . 1 :

 21 Figure 2.1: Ideal Functionality F H pake for PAKE (recalled from [CHK+05])

Figure 2 . 2 :

 22 Figure 2.2: Ideal Functionality F pake for PAKE (simplified from F H pake )

  Trapdoor correctness: (equivocality) for any message m, and any (c, eqk) $ ← SimCom() and s ← OpenCom(c, eqk, m), we have Open(c, s) = m; (extractability) for any message m and any (c, s) ← Com(m), we have ExtCom(c) = m; • Setup indistinguishability: the official setup Setup and the new one Setup generate indistinguishable global public parameters. We denote by Adv setup-ind CS (A) the advantage an adversary A can get in distinguishing the global public parameters generated by the two setup phases.

•

  (Strong) binding extractability: one cannot fool the extractor, i.e. produce a commitment c and a valid opening s to a message m = ExtCom(c). For any adversary A, we denote by Adv s-binding CS (A) its advantage in generating a commitment c that it can open in a different way than the extraction algorithm (even with unlimited access to the oracles GenEquivCommit, OpenEquivCommit, and ExtractCommit).

•

  r-robustness: Note that C has minimum distance nk + 2, and therefore C has minimum distance nk + 1 (because dropping one coordinate reduces the distance by at most 1). Therefore, C can correct (nk)/2 = nr errors. Since c A = cA and |A| ≥ r, there are at most nr errors in c, so the call to C .Decode(c) made by Reconstruct(c) will output W = W . Then Reconstruct(c) will output s = W • L = W • L.

Figure 2 . 3 :

 23 Figure 2.3: Functionality F CRS

Figure 2 . 4 :

 24 Figure 2.4: Functionality F RO

Figure 2 . 5 :

 25 Figure 2.5: Functionality F IC

Figure 3 . 1 :

 31 Figure 3.1: Functionality F iPAKE

Theorem 3 . 3 . 1 .

 331 If the computationnal Diffie-Hellman (CDH) assumption holds in G, the protocol EKE2 securely realizes F liPAKE in the F RO , F IC , F CRS -hybrid model with respect to static corruptions.

3 .

 3 When P 0 obtains an answer (sid, , Y * ) from P 1 , it • sends (sid, D, pw 0 || , Y * ) to F IC and receives (sid, Y ) back • sends (sid, X * , Y * , Y x ) to F RO and receives (sid, sk ) back P 0 then outputs (sid, , sk ) towards Z and terminates the session.

Figure 3 . 4 :

 34 Figure 3.4: An UC Execution of EKE2

Figure 4 . 1 :

 41 Figure 4.1: Ideal Functionality F fpake for fPAKE

Figure 4 . 2 :

 42 Figure 4.2: A Modified TestPwd Interface to Allow for Different Leakage

Theorem 4 . 2 . 1 .

 421 The construction from Figure4.3 cannot securely realize F P fpake .

Figure 4 . 3 :

 43 Figure 4.3: A First Natural Construction (with code-offset fuzzy sketch and PAKE)

Figure 4 . 4 :

 44 Figure 4.4: FPAKE rss Protocol

Figure 4 . 4 )

 44 with parties P 0 and P 1 , both having access to an ideal liPAKE functionality F liPAKE , and an adversary A that, w.l.o.g., can be assumed to be the dummy adversary as shown in [Can01, section 4.4.1].

Figure 4 . 5 :Figure 4 . 6 :

 4546 Figure 4.5: A UC Execution of FPAKE rss

Figure 4 . 7 :

 47 Figure 4.7: The Simulator S for FPAKE rss

Figure 5 . 1 :

 51 Figure 5.1: Graph of the sequential oracle calls in the η-unforgeability experiment

1 . 2 . 3 .

 123 GetRandChal(b) -It picks a new x b $ ← C, marks it fresh and outputs it; GetResp(x * ) -If ctr < η and x * ∈ C, it returns F K (x * ) and increments ctr. It also marks all fresh x b as unfresh. Otherwise, it outputs ⊥; TestResp(r, b) -If x b exists: • If F K (x b ) = r and x b is fresh, the adversary wins; • If F K (x b ) = r and x b is unfresh, it decrements ctr, marks x b as used and outputs 1;

)Figure 5 . 2 :

 52 Figure 5.2: Basic HAKE Construction

1 .

 1 SendServ(k, ( , c)): generate and send x S $ ← Z |C| 2. SendServ(k, s): open the value x T ← Open(c, s), set x ← g(x S +x T ), and compute r ← F K (x) 3. SendServ-PAKE queries to π k S : run the PAKE protocol on r 4. SendTerm(j, Start( )): a) generate x T $ ← Z |C| , commit (c, s) ← Com(x T ), and send c b) If compromised, reveal x T together with the random coins of the commitment 5. SendTerm(j, x S ): a) Set x ← g(x S + x T ), compute r ← F K (x), and send the opening value s b) If compromised, reveal r 6. SendTerm-PAKE queries to π j

1 :

 1 priv HAKE (A) = 2 × Pr G 0 [b ← A] -1.Game G We now replace the Setup algorithm of the commitment by Setup , allowing equivocal commitments and extractability, but without any additional change:

2 . 3 . 4 .••

 234 If remote-uncompromised: store b x ← 1, generate x S $ ← Z |C| and send it • If remote-compromised or non-oracle-generated: a) Store b x ← 0 b) Generate x ← GetRandChal(0). c) Using the extraction key of the commitment scheme, open c to learn x T d) Compute and send x S ← g -1 (x) + x T SendServ(k, s): Do nothing (since the committed value x T is already known) SendServ-PAKE queries to π k S : • If ∃r : (x, r) ∈ Λ 4 : run the PAKE protocol on r and issue a TestResp(r, b x ). • Otherwise: use the simulator S pake to generate the server flows (for an accepting PAKE transcript if the flows are oracle-generated). In case of a TestPwd query on a candidate r A run TestResp(r A , b x ) SendTerm(j, Start( )): Initialize b x ← 0 and • If uncompromised, generate and send an equivocal commitment c If compromised: a) generate x T $ ← Z |C| , commit (c, s) ← Com(x T ), and send c b) reveal x T together with the random coins of the commitment 5. SendTerm(j, x S ): • If compromised, set x * ← g(x S + x T ). Compute r ← GetResp(x * ) 5 . Then, store (x * , r) in Λ, send the opening value s and reveal r If uncompromised: a) Set x ← GetRandChal(1), x T $ ← x S + g -1 (x) and b x ← 1 b) Generate and send s such that Open(c, s) = x T , using the equivocation key of the commitment 6. SendTerm-PAKE queries to π j T : • If compromised, run the PAKE protocol on the known r • If uncompromised and oracle-generated, use the simulator S pake to generate the terminal flow (for an accepting PAKE transcript if the flows remain oracle-generated)

Figure 5 . 3 :

 53 Figure 5.3: Confirmed HAKE Construction

Figure 5 . 4 :

 54 Figure 5.4: Simplified Basic HAKE Construction

Figure 5 . 5 :

 55 Figure 5.5: Time-Based HAKE Construction

G 1 [F(D 1 )

 11 NOG-Com-OK] + Adv dist-T + Adv ind ddh (D 5 ) + Adv binding CS (B 3 ).

2 . 4 [

 24 SendServ(k, s T ): If not yet generated, generate pw t $ ← D. Then act as in G 3 . 4. SendTerm(j, (X S , c S )): After waiting for the current timeframe to be > t, if not yet generated, generate pw t $ ← D. Then act as in G 3 . 7. Compromise(j): Generate pw t $ ← D. Then act as in G 3 . This game is perfectly indistinguishable from the previous one: Pr G b ← A] = Pr

G 3 [

 3 b ← A].

|Pr G 5 [ 4 [

 54 NOG-Com-OK] -Pr G NOG-Com-OK]| ≤ Adv s-binding CS (B 5 ).

G 5 [ 1 [F(D 1 )(B 3 )+

 5113 NOG-Com-OK] ≤ (n serv + n term ) × 2 -D .And so:Pr G NOG-Com-OK] ≤ (n serv + n term ) × 2 -D + Adv setup-ind CS (D 2 ) + n total × Adv s-eq CS (D 3 ) + Adv s-binding CS (B 5 ).In conclusion, we have various adversaries such that:Adv priv HAKE (A) ≤ (n serv + n term ) × 2 -D + Adv dist-T +Adv ind ddh (D 5 ) + Adv binding CS Adv setup-ind CS (D 2 ) + n total × Adv s-eq CS (D 3 ) + Adv s-binding CS (B 5 ).

G 1 [F(D 1 )F 1 :

 111 Scheme Flows Terminal Server Communication expon. H eval. expon. H eval. complexity 1(SPAKE1)[PS10; AP05] 4 3 1 3 1 4λ Time-Based HAKE 4 2 2 2 2 10λ Table 5.1: Performance of the Time-Based HAKE

  1} λ . If there is already a record ( * , * , h) in Λ RO , S aborts. Else, S adds (sid, m, h) to Λ RO and replies with (sid, h).

then abort. Else, if there is an entry (sid, m, h) in Λ RO , S replies with (sid, h). Else, S chooses h $ ← {0,

  towards Z. Instructions of corrupting a player are only obeyed if they are received before the protocol started, i.e., before S received any NewSession query from F liPAKE .

	Chapter 4
	Fuzzy Password Authenticated Key
	Exchange
	4.1 Model

Figure 3.6: The Simulator S for the EKE2 Protocol indistinguishability from F liPAKE

We now present a new notion, called fuzzy password authenticated key exchange (fPAKE), which is a relaxation of a PAKE protocol (see Section 2.2) in the sense that the authentication should succeed even if the passwords are slightly different.

  1 , A 2 , A 2 , and A 3 , A 3 against the commitment scheme properties, all running in time t, such that Adv pake pake (S pake , B 2 , B 3 ) + 2 × Adv authenc Adv pake pake (S pake , B 2 , B 3 ) + 2 × Adv authenc where q r ≤ 2n comp , q t ≤ n active , q c ≤ n comp + n uncomp + n serv . We also note that given the confirmation phase, and assuming the strong policy of resetting all credentials if the confirmation phase fails, the coin-flipping part is no longer necessary for the security proof: we could let the server choose the challenge during the first phase and the human in the second one (to avoid one player being to make replay attacks). We chose to keep it as part of the protocol because, first, this would not reduce the number of flows since the terminal always initiates such a connection, and second, without coin-flipping a network attacker could test adaptive challenges. The confirmation phase would fail, but there is no real need for the user to take severe measures and change the long-term secret in such a weak attack. Hence we prevent adaptive tests (from network attacks) with coin-flipping, which may be useful if a policy a little weaker is in use, such as resetting only if there is a suspicion of terminal infection.

	Adv priv HAKE (A) ≤ Adv + 2 × Adv setup-ind (n hr +1)-uf F (B 1 ) + 2 × ES CS (A 1 ) + Adv s-eq CS (A 2 ) + Adv s-binding CS (A 3 ) , Adv auth HAKE (A ) ≤ Adv (n hr +1)-uf F (B 1 ) + 2 × ES + 2 × Adv setup-ind CS (A 1 ) + Adv s-eq CS (A 2 ) + Adv s-binding CS (A 3 ) ,	(B 4 ) (B 4 )
	Remark 5.5.3.

  generate and send a random ciphertext R U • If non-oracle-generated, either the simulator knows k S because of an honest execution of the PAKE with r. Then, it can get x U ← Dec[k S ](X U ). If this decrypts correctly, it checks if (x U , r U ) is in Λ for some r U . If it is not, get r U ← GetResp(x U ). It then sends Enc[k S ](r U ), and set terminate to True or the simulator does not know k S because it invoked the simulator S pake , which means that the adversary should not know the session key either, and so is unable to generate a valid cipher text: the simulator makes the server abort.

Actually, the modern definition of authentication would not be quite happy with just that, since even not knowing shared key, it is possible to manipulate a message (e.g. truncating it) which should be detected by the authentication property.

A notable issue in UC-proofs is that the simulation must be correct even in situations where the adversary breaks the scheme, such as by guessing passwords, whereas weaker models allow to stop the simulation.

If the adversary has no means of rewriting flows, it is obviously committed to passivity. However, a more reasonable assumption would be to assume it can write flows, but that it is more costly, notably because he then runs the risk of being detected.

This entry is unique due to the simulation of F IC as described in Game G2.

Note that, since F does not leak any information at this point, S cannot depend on the outcome of a TestPwd query.

We note that we can, w.l.o.g, assume that there is no NewSession queries from Z to corrupted parties. Thus, it is enough to remove the passwords from the NewSession queries given as input from Z to honest parties.

Instead, one could just sign all the messages, as would be done using the split functionality[START_REF] Barak | Secure Computation Without Authentication[END_REF], but this would be less efficient.

This trade-off is especially useful when we use a PAKE that admits adding labels basically for free, as it is the case with the special PAKE protocol we use.

In a nutshell, their protocol is implicit-only for the same reason as the liPAKE protocol we use here: there are only two flows that do not depend on each other, so the transcript cannot reveal the outcome of a guess unless it reveals the password to anyone. Looking at the proof in[START_REF] Katz | Round-Optimal Password-Based Authenticated Key Exchange[END_REF], it is easily verifiable that the simulator does not make use of the answer of TestPwd to simulate any messages. Furthermore, the protocol already implements labels.

It is also possible to incorporate mouse clicks into that, but we do not deal with it for simplicity.-49 -

The messages to the human oracle can already be deduced by the adversary as they are a function of the oracle's random tape, but we give the adversary the whole communication for convenience.

There is no hope of achieving any kind of server authentication implicitly, since the human is responsible for authentication in our security model, and he does not handle keys. User authentication could be achieved, but we defer the analysis to the next protocol.

In particular, this can be the case if the SendServ(k, ( , c))-query was remote-compromised or if r was queried through the SendHum query of an infected terminal session.

If such a query is not allowed because too many were asked since the last GetRandChal, it first issues a GetRandChal(0) query (and discards the result).

Thus, counting both the terminal session that increments ctr and the server sessions that decrements it, ctr is unchanged.

Acknowledgments

Acknowledgments

D T +1 : We denote by Adv dist-c F (D, A) the advantage the adversary A can get in distinguishing the sequence {y 0 = F K (x 0 ), . . . , y c-1 = F K (x c-1 )} for a random K , from (y 0 , . . . , y c-1 ) $ ← D × . . . × D. For the latter distribution, the probability to guess y c-1 from the view of (y 0 , . . . , y c-2 ) is 1/2 D .

(Weak) pseudo-random functions definitely satisfy this property. But from a more practical point of view, the function implemented in the RSA SecurID device [RSA] is believed to satisfy it too, with the x i being a time-based counter.

HCFF instantiations

We now propose some possible instantiations for the HCFF defined in the previous section.

Token-based HCFF

First, we introduce a simple token-based HCFF. This assumes that the human is in possession of a simple device on which it can input challenge x and get the response r ← F K (x). The device will store K and perform the computation, but the human is still responsible for the communication with the terminal. This allows us to use strong cryptographic primitives. For instance, we could set K $ ← {0, 1} λ and F K : 0, 9 t → 0, 9 t a pseudo-random function. In the random oracle model (for modeling H in F K (x) = H(K x)), we have Adv η-uf F (A) ≤ 10 -t for any adversary and any η, since the best strategy would be for the adversary to just guess by chance the answer to a fresh challenge. Note that this function is obviously human-readable, human-writable and human-sampleable as its input/output are numbers in basis 10 so it is an HCFF.

Hence this function family is a good candidate to use in our Basic HAKE protocol from Section 5.5.1 or its simplified version from Section 5.6.1.

Only-human HCFF

However, avoiding such devices would be much better in practice. We are thus interested in the only-human HCFF that would not require anything beyond simple human memory and brain computation power. Since such a function is necessarily weaker, we will use it in our Confirmed HAKE protocol from Section 5.5.2, which has a much tighter control over adaptive queries and therefore requires weaker security properties from the HCFF.

Construction

We present a candidate based on the construction of Blocki et al. [START_REF] Blocki | Towards Human Computable Passwords[END_REF], which security is based on [START_REF] Feldman | On the Complexity of Random Satisfiability Problems with Planted Solutions[END_REF]: Consider a challenge space C = X t l ⊆ 1, n lt , where 1, n = {1, . . . , n} is the set of n integers each representing one of the n variables and X l denotes the space of ordered clauses of l variables without repetition. The parameter t indicates that each challenge consists of t independent clauses, i.e., "small" challenges. The key generation algorithm KG of our HCFF takes as input a parameter n, then outputs a random mapping σ : 1, n → Z q as the key K, where the integer q is a constant. Usually we set q = 10 because most humans are familiar with computations on digits. Let σ l : 1, n l → Z l q = (σ, • • • , σ) denote the mapping that applies σ to each element of a l-tuple. Using a public human-computable function f : Z l q → Z q that is instantiated later, the challenge-response function F takes a key K = σ Authenticity proof. The simulated game G 1 is indistinguishable from the real one (either the privacy security game or the authentication security game). To break the server authentication, the adversary should be able to compute the answer to a random challenge x U with no GetResp allowed. Breaking the user-authentication means that the adversary succeeded in the PAKE, in order to know k S , and to send a valid cipher text X U and hence must also guess the answer r to a random x challenge. Since we exclude trivial attacks from the authentication security game, any winning strategy requires a successful TestResp-query.

Hence, the advantage Adv auth (A) of the adversary in the authentication security game is upper-bounded the same way as Adv priv (A).

Token-based HAKE constructions

In this section, we take a step back from only-human HCFF to allow the use of an additional device that will perform the computations in place of the human. In this setting, the HCFF can be quite powerful and thus resist to many adaptive queries. In our HCFF security notions, this means that it satisfies our strongest notion, indistinguishability. We consider it in two scenarios: first in a similar context as the generic HAKE constructions, where one can enter a challenge onto the device to get the response; and second, a time-based token, that outputs the response every timeframe, with the time as the challenge (without having the user to enter it).

Simplified Basic HAKE

In the security proof of the Basic HAKE, the PAKE has to be instantiated with a UC-Secure protocol, which turns out to be quite costly. Indeed, the only really efficient scheme that achieves this security level is the encrypted key exchange protocol (EKE) [START_REF] Bellovin | Encrypted Key Exchange: Password-Based Protocols Secure against Dictionary Attacks[END_REF]. However, the proof holds in the IC model, for a symmetric block cipher that should only output elements in the Diffie-Hellman group. In practice, the best way to do it is to iterate a large block cipher until one falls in the group. First, a large block cipher from a hash function (modeled as a random oracle) has fueled a whole line of works [CPS08; HKT11; DS16], and is nevertheless already quite costly: at the time of writing, at least 8-round Feistel network is required [START_REF] Dai | Indifferentiability of 8-Round Feistel Networks[END_REF], with an impossibility result below 6 [START_REF] Coron | The Random Oracle Model and the Ideal Cipher Model Are Equivalent[END_REF]. Thereafter, additional iterations are required to build a permutation onto the group. This eventually corresponds to dozens of hash function evaluations.

Looking back at the construction, using a full PAKE seems a bit overkill in this setting, since the ephemeral secrets are only used once, and need not to be kept secret afterwards if the HCFF is strong enough.

Taking advantage of this, we present, on Figure 5.4, the Simplified Basic HAKE, that is very similar to the Basic HAKE (Figure 5.2). As said above, it does not use a full PAKE, but just commitments to mutually check the knowledge of the ephemeral secret before it is revealed which is enough in this setting.

We do not provide a proof, but it is easy to see that the hiding/binding properties of the commitment scheme and the decisional Diffie-Hellman (DDH) hardness replace the security properties of the PAKE in the proof of the Basic HAKE from Section 5.5.1. The only change from Theorem 5.5.1 would be that q r is now only less or equal to n total = n comp +n uncomp +n serv (the total number of sessions), which should not be an issue for a device-assisted HCFF.

SendTerm(j, s S ):

• If compromised, act exactly as in G 2

• Otherwise: If Open(c S , s S ) = (X S , pw t ) and (c S , X S , •) ∈ Υ S , set sk T = (X S ) x T . Otherwise reject.

Game G 3 and G 2 are almost the same. The only difference would be if A somehow reuses an oracle-generated commitment c P but opens it to a different key X * P (and the same, valid, password pw t ) than the oracle-generated one X P . This would, however, break the binding property of CS, as we now know two opening values (s P , s * P ) for two messages ((X P , pw t ), (X * P , pw t )) with the same commitment c P ; we define a simulator B 3 that behaves as B 3 but outputs such a tuple. As it happens only on non-passive sessions, of which there is at most n term + n serv , we have:

Game G 4 : We now consider a CDH tuple (A, B, C) = (g a , g b , g ab ) and embed it into the simulation. Once again, simulations still behave as in the original Game G 1 for compromised sessions. More precisely, we change the query answers from Game G 3 as follows:

1. SendServ(k, ( , X T , c T )): Set the current timeframe t to be π k S 's session timeframe. Generate (β, δ) $ ← Z 2 p and set X S ← B δ • g β . Then set (c S , s S ) ← Com(X S , pw t ) and send (X S , c S ). Lastly, store (c S , X S , s S ) ∈ Υ S .

SendTerm(j, Start):

• If compromised, act exactly as in G 3 .

• Otherwise: Set the current timeframe t to be π j T 's session timeframe. Generate (α, γ) $ ← Z 2 p and set X T ← A γ • g α . Use the current password pw t to set (c T , s T ) ← Com(X T , pw t ) and send ( , X T , c T ). Then store (c T , X T , s T ) ∈ Υ T . 9. Test(j, P ): If sk P has been generated and π j P is fresh, we know (α, β, γ, δ) that were used to construct X T and X S (we only compute sk P if both are oraclegenerated). Then, the simulator uses sk P = C γδ • B αδ • A βγ • g αβ for the real key. Otherwise, it returns ⊥.

Regarding compromised sessions, either the adversary learned the password pw (from SendHum-query or by letting the compromised terminal ask the user) and no Test-query can be asked as neither π j T nor π k S is fresh; or the adversary did not learn the password, in which case Test-queries can still be asked to π k S , but the compromise did not reveal any secret.

Since we have C = g ab , then sk P = g (aγ+α)•(bδ+β) is exactly as the real key should be. This game is perfectly indistinguishable from the previous one:

Game G

List of Illustrations Figures