# A Generic Multifactor Authenticated Key Exchange with Physical Unclonable Function

Authors: Jin Wook Byun
Journal: Security and Communication Networks
 (2019)

---

## Abstract

We study how to generally construct aPUF-based multifactor authenticated key exchange (MAKE) protocol from any secure password-based authenticated key exchange protocol. We newly consider a new setting in which a user holding aPUF-embedded device desires to perform an authenticate key exchange through multifactor authentication factors (password, biometrics, secret). Our construction is the firstPUF-based generalMAKE construction. By applying aPUF in a device, ourMAKE construction is still secure even if all authentication factors are totally compromised. Our construction is the firstPUF-based genericMAKE protocol requiring additional three communication flows without any public key based primitives such as signature.


---

## Body

## 1. Introduction

To establish a secure communication over public network, a secure exchange of secret key with authentication is an absolute prerequisite. Thus, authenticated key exchange (for short,AKE) has been one of the most important cryptographic primitives. Basically, for practical and secureAKE, a memory requirable long-term secret key, a human memorable password, and human-dependent biometric information have been utilized as authentication factors in theAKE. If theAKE protocol is designed with only one factor (e.g., secret key or password) for authentication, it is considered as a one-factorAKE. Bellare and Rogaway first formalized security notions and definitions for the one-factorAKE based on symmetric secret key [1]. Subsequently, Bellare et al. have established a new security model in case of memorable password [2] (for short,PAKE). In a span of twenty years, these two models not only have been the foundation for subsequentPAKE results achieving augmented provable security with efficiency [3, 4], but also have been bases for the extended model such as group, three-party, and multifactor (secret, password, biometrics) authentication settings [5–9]. In this paper, we aim to design a generic framework to transform any securePAKE into a secureMAKE with physical unclonable function. Before discussing our motivations, let us briefly summarize relevant results on provably secureAKE andMAKE constructions.If two authentication factors (secret key and password) are simultaneously used into anAKE protocol, we consider it as a two-factorAKE (for short,TAKE) protocol. With the rapid popularization of smartcard, there have been huge amounts of research onTAKE in a practical scenario where a user memorizes own password and possesses a secret key in each own smartcard [10–16]. In a smartcard setting, it is impossible to list all (or even some specific related works and topics) works here. One main research stream is that many protocols have been found to be flawed and then finally redesigned repeatedly. Furthermore, our paper does focus on not theTAKE, but theMAKE that handles multifactorAKE. However, in theTAKE, there have been good relevant works on generic construction. First, Yang et al. [17] have designed a framework to transform a secure password-basedPAKE [18] suggested by Halevi and Krawczyk into theTAKE protocol. The main idea is to combine theHK password-basedPAKE with signature-based authenticator, which finally enables achieving a generalTAKE scheme. However, it is not general construction since the scheme is only able to transform theHK scheme into two-factor scheme, and is not be able to handle all kinds of securePAKE for buildingTAKE. In 2010, Stebila et al. suggested multifactor password-basedAKE [19]. It has been designed to allow multiple kinds of passwords. More precisely, this protocol deals with multiple passwords for authentication (note that biometrics is not included at all). Hence it is fair to say that it falls into theTAKE protocol. Besides, the protocol relies on thePKI environment and random oracle model for security proof. In 2014, Huang et al. have presented new types of adversaries with precomputed and different data on the smart card in aTAKE setting [20]. TwoTAKE schemes [21, 22] have been analyzed and securely revised under the new adversaries [20]. In 2018, Wang and Wang have syntagmatically and universally defined an explicit and new security model with practical adversaries’ capabilities for aTAKE setting. Also, a new and secureTAKE scheme, satisfying all security criteria, has been suggested. Very recently, Wang et al. have also proposed a new framework for evaluating security, efficiency, and scalability for aTAKE wireless sensor network [23]. Under the framework, two existing schemes [24, 25] have been found to be flawed [23]. Furthermore, 44TAKE schemes have been universally compared and analyzed. It is one of the systematic comparisons over such vast amounts of research.A multifactorAKE (for short,MAKE) deals with three types of authentication factors (secret, password, and biometrics). The main advantage ofMAKE overTAKE is its ability to preserve the security even if one or two authentication factors are compromised. Despite its merits, relatively, theMAKE has been received less attention in the literature than theTAKE. In 2008, Pointcheval and Zimmer have designed a provably secureMAKE protocol (for short,PZ) under computational Diffie-Hellman assumption [26]. It uses an ElGamal public key encryption [27] for securing biometric information. However, in 2012, it has been found to be insecure by Hao and Clarke [28]. The insecurity ofPZ is that an attacker, who steals a password, is able to deduce biometric information. After thePZ, there have been attempts to design aMAKE in smartcard, cloud computing, three-party, and multiserver environments [29–32]. In 2009, Fan et al. have proposed a public key basedMAKE in a smartcard setting [29]. It protects users’ biometric data from anyone else including a server while allowing secure authentication. Later, thePZ has been extended into three-party setting by Liu et al. [30]. It has been the first work on addressing the three-party setting that assumes an intervention of trusty party between a client and a server. A newMAKE based on elliptic curve has been suggested in a multiserver setting by He et al. in 2015 [31]. Very recently, Wei et al. have presented a privacy-preserving multifactor authenticated key exchange for cloud computing [32]. It has achieved better efficiency than thePZ in terms of computation and bandwidth costs.


### 1.1. Related Works

Our goal is to construct a secure genericPUF-basedMAKE protocol from any securePAKE protocol. To the best of our knowledge, aPUF-basedMAKE protocol has not been proposed yet in the literature. However, regarding genericMAKE constructions, which are not based onPUF, there have been few results in recent years. First, in 2011, Huang et al. have designed a generic transformation that combines any securePAKE in the smartcard setting with biometrics for building aMAKE [33]. Their main idea is to execute aTAKE twice. They use a fuzzy extractor to handle user’s biometrics. Later, it has been enhanced by Yu et al. in 2014 [34]. Its enhanced version applied a fuzzy vault based on euclidian distance for handling biometric features. And also, it used aTAKE just once. Despite its efficiency and novelty, these two constructions have been built under aPKI setting where participants must be allowed to sign (verify) and encrypt (decrypt) based on public key cryptography. Moreover, one critical problem is that these two constructions [33, 34] have not been built in a generic way. For example, in [34], they first make pw=H(pw1∥bio) and apply pw into aTAKE where pw1 is a password, bio is a biometric information, and H is a cryptographic secure hash function. Depending on what kind ofTAKE is being used, an input of pw(=H(pw1∥bio)) is not always an input forTAKE. For instance, ifTAKE uses a structure gpw (or Epw(·)) inside, then, before application, pw(=H(pw1∥bio)) should be customized as f(pw) where f is a function that converts an input to a cyclic group element output (or fixed length output, e.g., 128 bits, 256 bits). In [34], they select a good but specificTAKE [17] and demonstrate how it can be initiated to build a finalMAKE. It does not mean that their genericMAKE is able to cover all cases ofTAKE. One important observation from this issue is that a genericMAKE should execute aTAKE first and then use its session key for integrating multifactor authenticators rather than executingTAKE with an integration of multifactor authenticators.Fleischhacker et al. have presented a genericMAKE construction (for short,FMA) by combining subprotocols such as unauthenticated key exchange, password-based authentication (password), public key authentication (secret key), and biometric authentication protocols (biometric) [35]. The main idea is that it uses subprotocols independently for building a generalMAKE. This approach guarantees not only better security but also simplicity for implementation. However it does not allow two authentication factors to be used together for one subprotocol; hence it has a limitation to enhance the total communication cost.


### 1.2. Motivation

In the paper, we firstly attempt to use a physical unclonable function (PUF) for generally building a secureMAKE. ThePUF is basically embedded in a device at manufacturing stage. It always produces an unpredictable output depending on device’s physical status, and it cannot be duplicated or cloned over a new device. This unpredictability has been one of the good properties for enhancing security in cryptology. However, if thePUF always outputs different unpredictable result, then its output itself cannot become a secret key. A secret key in cryptology should be not only unpredictable, but also the same value when it is used for a secret key of encryption, decryption, and authentication. For this reason, generally, a fuzzy extractor (FE) has been used with thePUF for making a secure fixed secret from the unpredictablePUF’s outputs. In fact, much research on how thePUF can be securely combined with the existing cryptographic primitives, such asPUF-based authentication, bit commitment, andPUF-based encryption, has been conducted in recent decades. From the short histories of thePAKE,MAKE, andPUF, one question naturally arises; can we design aMAKE protocol by using the existing and well-provedPAKE protocol? More precisely, is it possible to generally constructMAKE if we are given any securePAKE and hardware dependentPUF? Generally, theMAKE needs a storage device for maintaining a long-term secret. That is why a huge amount ofMAKE has been presented in a smartcard setting so far. Besides, thePUF is hardware dependent function and it is well suited for a storage device. Therefore, it is quite natural for aMAKE to assume aPUF-embedded device such as smartcard,DRAM,SRAM. This setting has one important benefit that the previousMAKE inherently has not satisfied. That is, even if three authentication factors (password, secret, biometrics) are all compromised, ourMAKE withPUF-based device can be still secure.


### 1.3. Our Result

In the paper, we first study a topic on how to systematically construct aMAKE protocol with any securePAKE protocol in aPUF-embedded device setting. In our setting, a user holds aPUF-embedded device and desires to mutually authenticate it with a server by multifactor authenticators. The design difficulties come from how common symmetric secrets are securely established from multiple authenticators. As illustrated in Figure 1, our main idea is to apply user’s strong secrets (a long-term secret, biometrics) into an input ofPUF in a device and obtain an output secret r. OurPUF in aMAKE actually does not need a password as an input;, instead, ourMAKE just needs to execute a securePAKE first and obtainPAKE’s session key. Finally,PUF’s r andPAKE’s session key are hashed (random oracle) in order to produce two symmetric authentication keys. These keys perform a critical role for securely making message authentication codes for Diffie-Hellman values and a final session key ofMAKE. Executing a securePAKE first can avoid the security problem on the password such as off-line or on-line dictionary attacks. For instance, in case of using a long-term secret or biometric basedAKE, we should first go through a problem on how a weak secret, password, can be securely combined with a secret or biometrics basedAKE, which would be much more harder than the cases of combining thePAKE with a long-term secret and biometrics.Figure 1
A generation of authentication keys from multifactor authenticators.Most of all, our construction is the firstPUF-based generalMAKE constructions. By applying aPUF in a device, ourMAKE construction can be still secure even if all authentication factors (password, secret, biometrics) are totally revealed. Moreover, our construction is relatively efficient in terms of communication cost. That is, our construction needs at most 6 communication flows (one execution ofPAKE and three additional communication flows) that no public key based primitives such as signature are using. Unless the underlyingPAKE is asymmetric-based setting, ourMAKE construction is comprised of only symmetric primitives such as symmetric encryption,MAC function, which are relatively efficient than the works [35], as analyzed in Table 2. While the total communication round is greatly enhanced, our communication cost is not better than theFMA [35]. This slight inefficiency is due to the use ofPUF and Diffie-Hellman keying materials. However, enhanced security and the reduced total communication flow balance up these little computation loss.


## 1.1. Related Works

Our goal is to construct a secure genericPUF-basedMAKE protocol from any securePAKE protocol. To the best of our knowledge, aPUF-basedMAKE protocol has not been proposed yet in the literature. However, regarding genericMAKE constructions, which are not based onPUF, there have been few results in recent years. First, in 2011, Huang et al. have designed a generic transformation that combines any securePAKE in the smartcard setting with biometrics for building aMAKE [33]. Their main idea is to execute aTAKE twice. They use a fuzzy extractor to handle user’s biometrics. Later, it has been enhanced by Yu et al. in 2014 [34]. Its enhanced version applied a fuzzy vault based on euclidian distance for handling biometric features. And also, it used aTAKE just once. Despite its efficiency and novelty, these two constructions have been built under aPKI setting where participants must be allowed to sign (verify) and encrypt (decrypt) based on public key cryptography. Moreover, one critical problem is that these two constructions [33, 34] have not been built in a generic way. For example, in [34], they first make pw=H(pw1∥bio) and apply pw into aTAKE where pw1 is a password, bio is a biometric information, and H is a cryptographic secure hash function. Depending on what kind ofTAKE is being used, an input of pw(=H(pw1∥bio)) is not always an input forTAKE. For instance, ifTAKE uses a structure gpw (or Epw(·)) inside, then, before application, pw(=H(pw1∥bio)) should be customized as f(pw) where f is a function that converts an input to a cyclic group element output (or fixed length output, e.g., 128 bits, 256 bits). In [34], they select a good but specificTAKE [17] and demonstrate how it can be initiated to build a finalMAKE. It does not mean that their genericMAKE is able to cover all cases ofTAKE. One important observation from this issue is that a genericMAKE should execute aTAKE first and then use its session key for integrating multifactor authenticators rather than executingTAKE with an integration of multifactor authenticators.Fleischhacker et al. have presented a genericMAKE construction (for short,FMA) by combining subprotocols such as unauthenticated key exchange, password-based authentication (password), public key authentication (secret key), and biometric authentication protocols (biometric) [35]. The main idea is that it uses subprotocols independently for building a generalMAKE. This approach guarantees not only better security but also simplicity for implementation. However it does not allow two authentication factors to be used together for one subprotocol; hence it has a limitation to enhance the total communication cost.


## 1.2. Motivation

In the paper, we firstly attempt to use a physical unclonable function (PUF) for generally building a secureMAKE. ThePUF is basically embedded in a device at manufacturing stage. It always produces an unpredictable output depending on device’s physical status, and it cannot be duplicated or cloned over a new device. This unpredictability has been one of the good properties for enhancing security in cryptology. However, if thePUF always outputs different unpredictable result, then its output itself cannot become a secret key. A secret key in cryptology should be not only unpredictable, but also the same value when it is used for a secret key of encryption, decryption, and authentication. For this reason, generally, a fuzzy extractor (FE) has been used with thePUF for making a secure fixed secret from the unpredictablePUF’s outputs. In fact, much research on how thePUF can be securely combined with the existing cryptographic primitives, such asPUF-based authentication, bit commitment, andPUF-based encryption, has been conducted in recent decades. From the short histories of thePAKE,MAKE, andPUF, one question naturally arises; can we design aMAKE protocol by using the existing and well-provedPAKE protocol? More precisely, is it possible to generally constructMAKE if we are given any securePAKE and hardware dependentPUF? Generally, theMAKE needs a storage device for maintaining a long-term secret. That is why a huge amount ofMAKE has been presented in a smartcard setting so far. Besides, thePUF is hardware dependent function and it is well suited for a storage device. Therefore, it is quite natural for aMAKE to assume aPUF-embedded device such as smartcard,DRAM,SRAM. This setting has one important benefit that the previousMAKE inherently has not satisfied. That is, even if three authentication factors (password, secret, biometrics) are all compromised, ourMAKE withPUF-based device can be still secure.


## 1.3. Our Result

In the paper, we first study a topic on how to systematically construct aMAKE protocol with any securePAKE protocol in aPUF-embedded device setting. In our setting, a user holds aPUF-embedded device and desires to mutually authenticate it with a server by multifactor authenticators. The design difficulties come from how common symmetric secrets are securely established from multiple authenticators. As illustrated in Figure 1, our main idea is to apply user’s strong secrets (a long-term secret, biometrics) into an input ofPUF in a device and obtain an output secret r. OurPUF in aMAKE actually does not need a password as an input;, instead, ourMAKE just needs to execute a securePAKE first and obtainPAKE’s session key. Finally,PUF’s r andPAKE’s session key are hashed (random oracle) in order to produce two symmetric authentication keys. These keys perform a critical role for securely making message authentication codes for Diffie-Hellman values and a final session key ofMAKE. Executing a securePAKE first can avoid the security problem on the password such as off-line or on-line dictionary attacks. For instance, in case of using a long-term secret or biometric basedAKE, we should first go through a problem on how a weak secret, password, can be securely combined with a secret or biometrics basedAKE, which would be much more harder than the cases of combining thePAKE with a long-term secret and biometrics.Figure 1
A generation of authentication keys from multifactor authenticators.Most of all, our construction is the firstPUF-based generalMAKE constructions. By applying aPUF in a device, ourMAKE construction can be still secure even if all authentication factors (password, secret, biometrics) are totally revealed. Moreover, our construction is relatively efficient in terms of communication cost. That is, our construction needs at most 6 communication flows (one execution ofPAKE and three additional communication flows) that no public key based primitives such as signature are using. Unless the underlyingPAKE is asymmetric-based setting, ourMAKE construction is comprised of only symmetric primitives such as symmetric encryption,MAC function, which are relatively efficient than the works [35], as analyzed in Table 2. While the total communication round is greatly enhanced, our communication cost is not better than theFMA [35]. This slight inefficiency is due to the use ofPUF and Diffie-Hellman keying materials. However, enhanced security and the reduced total communication flow balance up these little computation loss.


## 2. Preliminaries

### 2.1. Fuzzy Extractor and PUF

Definition 1 (fuzzy extractor[36]).
A fuzzy extractor consists of two procedures,Gen(·),Rep(·): (1)
Gen(·) outputs a string R∈{0,1}lr and a helper string P∈{0,1}∗, on input W∈M, guaranteeing that for any distribution W with min-entropy m, if (R,P)←Gen(W), then SD((R,P),(Ul,P))≤ϵ, where the SD means statistical distance.(2)
Rep(·) takes (W′,P) on inputs and it outputs Rep(W′,P)=R if dist(W,W′)≤t and (R,P)←Gen(W).Definition 2 (PUF[37, 38]).
A physically unclonable function(t,ϵ1,ϵ2,ϵpuf)-PUF is a function {0,1}lp→{0,1}lo satisfying the following. (1)
APUF is bound to a device and its evaluation is efficient.(2)
For anyPPT adversary Apuf, PUF’s output is impossible to characterize. Let PUF:{0,1}lp→{0,1}lo be an idealPUF. An experiment ExpApufpufb(k) is defined for b⟵R{0,1} where k∈N is a security parameter. ExpApufpuf0(k) means an experiment in which Apuf can access an idealPUF in polynomial number of times. That is, in this experiment, an oracle OPUF(·) returns y←P(x) on input x∈{0,1}lp. Otherwise if b=0, in ExpApufpuf1(k), OPUF(·) returns a random y←R{0,1}lo as an answer. Apuf’s goal is to finally output a guessing bit b′ for b. To be precise, the followingpuf-advantage, ϵpuf, should be negligible.(1)ϵpuf=PrExpApufpuf1k=1-PrExpApufpuf0k=1(3)
The distance between twoPUF’s outputs on the same challenge x is at most t; e.g., the following probability is negligible ϵ1.(2)Pr⁡disty,z>t∣x←0,1lp,y←PUFx,z←PUFx≤ϵ1(4)
The distance between two outputsPUFA(x),PUFB(x) from different devices A,B, on the same challenge x, is at least t; e.g., the following probability is negligible ϵ2.(3)Pr⁡disty,z<t∣x←0,1lp,y←PUFAx,z←PUFBx≤ϵ2OurPUF is based on an idealPUF model where aPUF is considered as a random permutation oracle. In the same way as a random oracle, an adversary Apuf is adaptively able to query thePUF within polynomial time [37–41], but Apuf is never able to tell apart which one is realPUF or simulatedPUF. This second property basically follows the definition in [37]. The third property says that thePUF’s output (r=PUF(x)) is always different within a certain distance d on the same input x. It is one of the good properties as any adversary cannot predictPUF’s outputs, but its uncertainty makes it hard to directly apply r(=PUF(x)) itself for making a cryptographic key. Thus, aPUF is usually combined with a fuzzy extractor which consists ofGen andRep for making and recovering a fixed cryptographic secret k. That is, even if any adversary corrupts the input x, it cannot predict output r(=PUF) or k withoutPUF while only valid user who holdsPUF can recover k. The last property means that eachPUF in different device should have own unique output on the same input. These third and fourth properties follow definitions in [38].


### 2.2. PRF and DDH

Definition 3 (pseudorandom function family (PRF)).
A pseudorandom function family is a collection of functionsFK:K(F)×D(F)→R(F) indexed by a key K∈K(F), where K(F) is the set of keys of FK and D(F) is the set of domains of FK, such that for anyPPT algorithm B, it holds the following: (i)
Givenx∈D(F) and K∈K(F), there is aPPT algorithm to compute FK(x).(ii)
For anyPPT algorithm B, the followingprf-advantage, ϵprf, is negligible:(4)PrBFK=1:K←RKF-PrBF=1:F←RUFK≤ϵprfwhereUFK is the set of all functions mapping from D(F) to R(F) and ←R denotes an element chosen randomly.Definition 4 (decisional Diffie-Hellman assumption (DDH)).
The DDH problem is defined as follows: LetG be a cyclic group that has a prime order q and a generator g. The advantage of A is(5)AdvAddhTD,G=PrAgu,gv,guv=1;u,v←Zq∗-PrAgu,gv,R=1;u,v←Zq∗,R←Gwhere A isPPT adversary with time complexity TD. The DDH assumption is that the advantage of A is negligible.


### 2.3. Secure MAC and Secure Symmetric Encryption under CCA

Definition 5 (secure message authentication code under chosen message attack).
A message authentication code is a pair of algorithms MAC = (T, V). We define a MAC key setMk = {0,1}lm where lm is the size of MAC key. An algorithm T is a MAC generation algorithm which takes as inputs a MAC key K∈Mk and message x and outputs a string T(K,x) called a tag. An algorithm V is a MAC verification algorithm which takes key K, message x, and tag T(K,x) and outputs a bit 1 (authentic) or 0 (unauthentic). Let us consider the following experiment. A notation of AmacO(·) indicates that the adversary Amac can access an oracle O(·).
Experiment E x p A m a c c m a
k ← R MKey
( x ∗ , v ∗ ) ← A m a c T ( K , · ) , V ( K , · , · ): v∗ is a tag value for a new message x∗
IfV(K,x∗,v∗)=1 and v∗ was never outputted by T(K,·) in response to query x∗, then return 1; else return 0.
We definecma (chosen message attack) advantage of Amac as follows.(6)AdvAmaccmaTm,k=PrExpAmaccmaTm,k=1.If cma-advantage ofMAC is negligible, theMAC scheme is secure under chosen message attack.Definition 6 (secure symmetric encryption under chosen cipher attack).
LetSE = (E,D) be a symmetric encryption scheme and Ase be an adversary ofSE. We define a symmetric key setKey = {0,1}le where le is the size of encryption key. An algorithmE is a probabilistic symmetric encryption algorithm which takes a symmetric key K∈Key and plaintext m and outputs ciphertext EK(m). An algorithm D is a deterministic decryption algorithm which takes key K, plaintext m, and EK(m) as inputs and outputs message m. Let us consider the following experiment. A notation of AseO(·) indicates that the adversary Ase can access an oracle O(·).(1)
K←RKey(2)
(Find Stage)(x0,x1,s)←AseEK(·)DK(·)(3)
b←R{0,1}, c←EK(xb)(4)
(Guess Stage)b′←AseEK(·)DK(·)(c,s)(5)
Ifb′=b then return 1 else return 0
For anyTse, qe, qd, we definecca-advantage ofSE as(7)AdvAseccak=2Prb=b′-1.Ifcca-advantage ofSE is negligible, theSE schemeissecure under chosen ciphertext attack.


## 2.1. Fuzzy Extractor and PUF

Definition 1 (fuzzy extractor[36]).
A fuzzy extractor consists of two procedures,Gen(·),Rep(·): (1)
Gen(·) outputs a string R∈{0,1}lr and a helper string P∈{0,1}∗, on input W∈M, guaranteeing that for any distribution W with min-entropy m, if (R,P)←Gen(W), then SD((R,P),(Ul,P))≤ϵ, where the SD means statistical distance.(2)
Rep(·) takes (W′,P) on inputs and it outputs Rep(W′,P)=R if dist(W,W′)≤t and (R,P)←Gen(W).Definition 2 (PUF[37, 38]).
A physically unclonable function(t,ϵ1,ϵ2,ϵpuf)-PUF is a function {0,1}lp→{0,1}lo satisfying the following. (1)
APUF is bound to a device and its evaluation is efficient.(2)
For anyPPT adversary Apuf, PUF’s output is impossible to characterize. Let PUF:{0,1}lp→{0,1}lo be an idealPUF. An experiment ExpApufpufb(k) is defined for b⟵R{0,1} where k∈N is a security parameter. ExpApufpuf0(k) means an experiment in which Apuf can access an idealPUF in polynomial number of times. That is, in this experiment, an oracle OPUF(·) returns y←P(x) on input x∈{0,1}lp. Otherwise if b=0, in ExpApufpuf1(k), OPUF(·) returns a random y←R{0,1}lo as an answer. Apuf’s goal is to finally output a guessing bit b′ for b. To be precise, the followingpuf-advantage, ϵpuf, should be negligible.(1)ϵpuf=PrExpApufpuf1k=1-PrExpApufpuf0k=1(3)
The distance between twoPUF’s outputs on the same challenge x is at most t; e.g., the following probability is negligible ϵ1.(2)Pr⁡disty,z>t∣x←0,1lp,y←PUFx,z←PUFx≤ϵ1(4)
The distance between two outputsPUFA(x),PUFB(x) from different devices A,B, on the same challenge x, is at least t; e.g., the following probability is negligible ϵ2.(3)Pr⁡disty,z<t∣x←0,1lp,y←PUFAx,z←PUFBx≤ϵ2OurPUF is based on an idealPUF model where aPUF is considered as a random permutation oracle. In the same way as a random oracle, an adversary Apuf is adaptively able to query thePUF within polynomial time [37–41], but Apuf is never able to tell apart which one is realPUF or simulatedPUF. This second property basically follows the definition in [37]. The third property says that thePUF’s output (r=PUF(x)) is always different within a certain distance d on the same input x. It is one of the good properties as any adversary cannot predictPUF’s outputs, but its uncertainty makes it hard to directly apply r(=PUF(x)) itself for making a cryptographic key. Thus, aPUF is usually combined with a fuzzy extractor which consists ofGen andRep for making and recovering a fixed cryptographic secret k. That is, even if any adversary corrupts the input x, it cannot predict output r(=PUF) or k withoutPUF while only valid user who holdsPUF can recover k. The last property means that eachPUF in different device should have own unique output on the same input. These third and fourth properties follow definitions in [38].


## 2.2. PRF and DDH

Definition 3 (pseudorandom function family (PRF)).
A pseudorandom function family is a collection of functionsFK:K(F)×D(F)→R(F) indexed by a key K∈K(F), where K(F) is the set of keys of FK and D(F) is the set of domains of FK, such that for anyPPT algorithm B, it holds the following: (i)
Givenx∈D(F) and K∈K(F), there is aPPT algorithm to compute FK(x).(ii)
For anyPPT algorithm B, the followingprf-advantage, ϵprf, is negligible:(4)PrBFK=1:K←RKF-PrBF=1:F←RUFK≤ϵprfwhereUFK is the set of all functions mapping from D(F) to R(F) and ←R denotes an element chosen randomly.Definition 4 (decisional Diffie-Hellman assumption (DDH)).
The DDH problem is defined as follows: LetG be a cyclic group that has a prime order q and a generator g. The advantage of A is(5)AdvAddhTD,G=PrAgu,gv,guv=1;u,v←Zq∗-PrAgu,gv,R=1;u,v←Zq∗,R←Gwhere A isPPT adversary with time complexity TD. The DDH assumption is that the advantage of A is negligible.


## 2.3. Secure MAC and Secure Symmetric Encryption under CCA

Definition 5 (secure message authentication code under chosen message attack).
A message authentication code is a pair of algorithms MAC = (T, V). We define a MAC key setMk = {0,1}lm where lm is the size of MAC key. An algorithm T is a MAC generation algorithm which takes as inputs a MAC key K∈Mk and message x and outputs a string T(K,x) called a tag. An algorithm V is a MAC verification algorithm which takes key K, message x, and tag T(K,x) and outputs a bit 1 (authentic) or 0 (unauthentic). Let us consider the following experiment. A notation of AmacO(·) indicates that the adversary Amac can access an oracle O(·).
Experiment E x p A m a c c m a
k ← R MKey
( x ∗ , v ∗ ) ← A m a c T ( K , · ) , V ( K , · , · ): v∗ is a tag value for a new message x∗
IfV(K,x∗,v∗)=1 and v∗ was never outputted by T(K,·) in response to query x∗, then return 1; else return 0.
We definecma (chosen message attack) advantage of Amac as follows.(6)AdvAmaccmaTm,k=PrExpAmaccmaTm,k=1.If cma-advantage ofMAC is negligible, theMAC scheme is secure under chosen message attack.Definition 6 (secure symmetric encryption under chosen cipher attack).
LetSE = (E,D) be a symmetric encryption scheme and Ase be an adversary ofSE. We define a symmetric key setKey = {0,1}le where le is the size of encryption key. An algorithmE is a probabilistic symmetric encryption algorithm which takes a symmetric key K∈Key and plaintext m and outputs ciphertext EK(m). An algorithm D is a deterministic decryption algorithm which takes key K, plaintext m, and EK(m) as inputs and outputs message m. Let us consider the following experiment. A notation of AseO(·) indicates that the adversary Ase can access an oracle O(·).(1)
K←RKey(2)
(Find Stage)(x0,x1,s)←AseEK(·)DK(·)(3)
b←R{0,1}, c←EK(xb)(4)
(Guess Stage)b′←AseEK(·)DK(·)(c,s)(5)
Ifb′=b then return 1 else return 0
For anyTse, qe, qd, we definecca-advantage ofSE as(7)AdvAseccak=2Prb=b′-1.Ifcca-advantage ofSE is negligible, theSE schemeissecure under chosen ciphertext attack.


## 3. Security Model for Multifactor Authenticated Key Exchange

Based on theBPR model [2], in this section, a new security model is presented forPUF-basedMAKE. We follow the basic framework and its notations ofBPR model [2]. As our compiler converts any securePAKE into securePUF-basedMAKE, two security models (PAKE andMAKE) are required for security proof. Two security models are the same except the number of authentication factors, session freshness.


### 3.1. Communication Model

Participants, long-lived secrets in the MAKE . Two types of protocol participants, a set of users U and a set of servers S, are assumed in aMAKE protocol with multiple long-lived secrets. That is, we suppose that each user U∈U owns a tuple Mc=δ~,pw,s,PUF.U memorizes a secret password pw and possesses a physical unclonable function,PUF, which is usually embedded into a smartcard or memory card.U holds a long-term secrets.U itself owns biometric template δ~ such as iris or fingerprint. S securely keeps Ms={ID,T[Mc]} in its database, where ID is an identifier and T[Mc] is a transformation of Mc. A userU (or a serverS) may executeMAKE protocol multiple times and we also denote the i-th instance executed by entity U (resp., S) as Umi (resp. Smi).Participants, long-lived secret in the PAKE . We assume two types of protocol participants, a user U∈U and a server S∈S. The set of all participants is the union U∪S. We suppose that each user U∈U memorizes a secret password pw and the serverS keeps a vector pws=〈pwu〉u∈U that contains entry for each client. The passwords pw,pws are called the long-lived key of userU and serverS. A userU (or a serverS) may execute the 2-partyPAKE protocol multiple times. The i-th instance is executed by entity U (resp., S) as Uti (resp., Sti).Queries of Adversary in the MAKE . Queries are defined to model malicious behaviors of an adversary. We assume that there is an adversary A that is able to control communications over the networks and interact with the oracles by asking queries defined below.(i)
Sendm(U,i,M). It sends the message M to an oracle Umi. This query models that A sends a message M to an instance of Umi in the real protocol. The oracle Umi will return the next message that an honest Umi should be sent according to the protocol.(ii)
Revealm(U,t). If the oracle Umt has a session key, then this query outputs a session key to A. This query models the possibility that A gets session keys.(iii)
Corruptm(U,a). This query models the possibility that A corrupts a client U. We assume that A can just obtain long-lived keys, but cannot obtain ephemeral states of instances. This query is classified into three types according to a.
(a)
Ifa = 1, then the passwordpw ofU is returned as an answer.(b)
Ifa = 2, then the secretPUF ofU is returned as an answer.(c)
Ifa = 3, then the secret δ~ ofU is returned as an answer.(d)
Ifa = 4, then the secrets ofU is returned as an answer.In case ofPAKE, the cases of a=1 are only considered.(iv)
Executem(U,i,S,j). This query returns transcripts of an honest execution between user instance Umi and server instance Smj. This query models a passive adversary who simply eavesdrops transcripts on an honest execution.(v)
Testm(Umi). This query is only used to measureA’s knowledge on a session key. WhenA asks aTest query to thefreshUmi, a coin is flipped to generate a random bit b. If b = 1, the real session key is returned to A. Otherwise a random value is returned. A is allowed to make aTest query only once at any time during the experiment.Queries of Adversary in the PAKE . All queries and their responses are the same as those ofMAKE except a corrupt query with notions. A corrupt query in thePAKE is defined only in case ofa=1. A notion on the instance, Umi, is replaced with Uti (Stj). And also, to distinguish notations in the security proof, we define notations of queries for thePAKE without subscript m (e.g.,Send,Corrupt,Execute,Reveal,Test).


### 3.2. Security Definition

Definition 7 (session identifier, session key, partner identifier, and partnering 2-partyMAKE).
We define a session identifier (SID) for Umi assidUmi which is the concatenation of all messages sent and received by Umi. A session key is denoted asskU,S. A partner ID is a corresponding participant with whom Umi is interacting, which is denoted aspidUmi. Instances Umi and Smj are partnering if the following conditions are satisfied: (1) Both instances have been accepted with the same session key, session ID, and partner ID. That is, if both oracles have been accepted withskU,S,sidUmi,pidUmj,(skS,U,sidSmj,pidSmj), thenskU,S=skS,U,sidUmi=sidSmj≠NULL. (2) No oracle other than Umi and Smj is accepted with the pid of Umi and Smj. (pidUmi=Smj, pidSmj=Umi).Regarding thePAKE, we use essentially the same definitions, notations forSID, a session key, andPID with the ones ofMAKE model. Thus we do not define them again here. Next, we consider freshness, forward secure freshness forMAKE andPAKE, respectively.Definition 8 (freshness for 2-partyMAKE).
An instanceUmi isfresh in terms of multifactorAKE if (1) neither Umi nor its partner has been asked for aReveal query; (2) neither Umi nor its partner has been asked for aCorrupt(Umi, 1),Corrupt(Umi, 2),Corrupt(Umi, 3),Corrupt(Umi, 4) queries. The second condition means that Umi and its partner have been asked for less than four corrupt queries. That is, A can askCorrupt queries satisfying the following equation.(8)Corrupt1∧Corrupt2∧Corrupt3∧Corrupt4=FALSEIf A has asked query ofCorrupt(U,a) where 1≤a≤4, then it isCorrupt(a) =TRUE. Otherwise, it isCorrupt(a) =FALSE.Definition 9 (forward secure freshness for 2-partyMAKE).
Regarding forward secrecy, a new freshness,fs-fresh, is defined. An instance Umi isfs-fresh in terms of multiple authentication factors if (1) neither Umi nor its partner has been asked for aReveal query; (2) beforeTest(Umi), neither Umi nor its partner has been asked for all threeCorrupt(Umi, 1),Corrupt(Umi, 2),Corrupt(Umi, 3),Corrupt(Umi, 4) queries andSendm(U,i,M) queries.Remark 10.
The above first property (1) is forReveal case for bothPAKE andMAKE. However, the second property (2) has been modified by multiple authentication factors. For example, let us consider some cases offs-fresh. If A asksCorrupt(Umi, 1),Corrupt(Umi, 2) queries (less than all four Corrupt queries) beforeTest(Umi) and does askSendm(U,i,M) query, then it isfs-fresh. Also, if A asksCorrupt(Umi, 1),Corrupt(Umi, 2), andCorrupt(Umi, 3) queries beforeTest(Umi) and does not askSendm(U,i,M) query, then it isfs-fresh. If all Corrupt queries have been asked after Test query, then it is alsofs-fresh.Definition 11 (freshness for 2-partyPAKE).
It is defined in the same way asMAKE except the second condition. That is, the first condition is the same as theMAKE, but the second condition is that (2) neither Umi nor its partner has been asked for aCorrupt(Umi, 1) query.Definition 12 (forward secure freshness for 2-partyPAKE).
It is defined in the same way as the aboveMAKE except the second condition. That is, (2) beforeTest(Umi), neither Umi nor its partner has been asked for aCorrupt(Umi, 1) query andSendm(U,i,M) query.Definition 13 (session key security for 2-partyMAKE).
Let us consider the following experiment. We assume that an adversaryA is run within a polynomial time bound T. A interacts with a finite number of oracles by asking queries defined above during the experiment. A can ask aTest query to a fresh oracle at any time. When A asks aTest query to thefreshUmi, then the experiment flips a coin for bit b. If it lands b = 1, then the real session key is returned to the adversary. Otherwise, a random key is returned to the adversary. Eventually A guesses b, outputs the guessed bit b′, and terminates the experiment. Theskadvantage of A in attacking theMAKE protocol P is defined as AdvP,skmake(A)=2Prb=b′-1. It should be negligible as follows.(9)AdvP,skmakeA,T,k≤C′·qss′+εk,where ε(k) is a negligible function, D(e.g.,12,898,437) is a password space for a Zipf’s parameters C′(e.g.,0062239), s′(e.g.,0.155478), which follows Zipf’s law for password [42, 43], qs is the number of on-lineSend queries asked, and k is a security parameter.Remark 14.
Since a memorable password is chosen by a user, it is not uniformly distributed. That is, due to the memorable property, it is natural for the user not to be able to make full use of the whole distribution ofD at password selection stage. Thus, regarding the formalization term on an on-line-password guessing attack in all of our definitions here, we follow the Zipf assumption for password distributions [42, 43], which formalizes user own memorable password (not uniform from D), C′·qss′, rather than a uniformly modeled term qs/D, where C′,s′ are Zipf’s parameters [42, 43] depending on dataset, policy, language.Definition 15 (session key security for 2-partyPAKE).
The definition forPAKE is the same as theMAKE security except that a notion AdvP,skmake(A,T,R) is replaced with a notion AdvP,skpake(A,T,k). It is defined as AdvP,skpake(A,T,k)=2Prb=b′-1 and it should be as follows. AdvP,skpake(A,T,k)≤C′·qss′+ε(k) where ε(k) is a negligible function, |D|(e.g.,12,898,437) is a password space for a Zipf’s parameters C′(e.g.,0062239), s′(e.g.,0.155478), which follows Zipf’s law for password [42, 43], qs is the number of on-lineSend queries asked, and k is a security parameter.Definition 16 (forward secure session key security for 2-partyPAKE).
A forward secure 2-partyPAKE protocol is defined with a condition that thefs-fresh instance should be asked for aTest query. Basically its definition is the same as the definition of session key securePAKE except that a notion AdvP,skpake(A,T,k) is replaced with a notion AdvP,skfs-pake(A,T,k)=2Pr[b=b′]-1. It should be as follows: AdvP,skfs-pake(A,T,k)≤C′·qss′+ε(k) where ε(k) is a negligible function, D(e.g.,12,898,437) is a password space for a Zipf’s parameters C′(e.g.,0062239), s′(e.g.,0.155478), which follows Zipf’s law for password [42, 43], qs is the number of on-lineSend queries asked, and k is a security parameter.The mutual authentication forMAKE andPAKE is defined by an event,Succ, as follows.Definition 17 (mutual Authentication [2]).
We follow a definition of mutual authentication defined in [2]. For client authentication, we consider sessions where the server accepts with no partner instance of the client. With regard to server authentication, we consider sessions where the client accepts with no partner instance of the server. We say that an adversary breaks mutual authentication if either server or client instance is accepted, but has no partner oracle. We denote this event bySucc and its probability is defined as SuccPma(A,T,k)=Pr[Succ]. We say that a givenMAKE protocol P provides mutual authentication if SuccPma(A,T,k) is negligible as follows:(10)SuccPmaA,T,k≤εk,where ε(k) is a negligible function and k is a security parameter.


## 3.1. Communication Model

Participants, long-lived secrets in the MAKE . Two types of protocol participants, a set of users U and a set of servers S, are assumed in aMAKE protocol with multiple long-lived secrets. That is, we suppose that each user U∈U owns a tuple Mc=δ~,pw,s,PUF.U memorizes a secret password pw and possesses a physical unclonable function,PUF, which is usually embedded into a smartcard or memory card.U holds a long-term secrets.U itself owns biometric template δ~ such as iris or fingerprint. S securely keeps Ms={ID,T[Mc]} in its database, where ID is an identifier and T[Mc] is a transformation of Mc. A userU (or a serverS) may executeMAKE protocol multiple times and we also denote the i-th instance executed by entity U (resp., S) as Umi (resp. Smi).Participants, long-lived secret in the PAKE . We assume two types of protocol participants, a user U∈U and a server S∈S. The set of all participants is the union U∪S. We suppose that each user U∈U memorizes a secret password pw and the serverS keeps a vector pws=〈pwu〉u∈U that contains entry for each client. The passwords pw,pws are called the long-lived key of userU and serverS. A userU (or a serverS) may execute the 2-partyPAKE protocol multiple times. The i-th instance is executed by entity U (resp., S) as Uti (resp., Sti).Queries of Adversary in the MAKE . Queries are defined to model malicious behaviors of an adversary. We assume that there is an adversary A that is able to control communications over the networks and interact with the oracles by asking queries defined below.(i)
Sendm(U,i,M). It sends the message M to an oracle Umi. This query models that A sends a message M to an instance of Umi in the real protocol. The oracle Umi will return the next message that an honest Umi should be sent according to the protocol.(ii)
Revealm(U,t). If the oracle Umt has a session key, then this query outputs a session key to A. This query models the possibility that A gets session keys.(iii)
Corruptm(U,a). This query models the possibility that A corrupts a client U. We assume that A can just obtain long-lived keys, but cannot obtain ephemeral states of instances. This query is classified into three types according to a.
(a)
Ifa = 1, then the passwordpw ofU is returned as an answer.(b)
Ifa = 2, then the secretPUF ofU is returned as an answer.(c)
Ifa = 3, then the secret δ~ ofU is returned as an answer.(d)
Ifa = 4, then the secrets ofU is returned as an answer.In case ofPAKE, the cases of a=1 are only considered.(iv)
Executem(U,i,S,j). This query returns transcripts of an honest execution between user instance Umi and server instance Smj. This query models a passive adversary who simply eavesdrops transcripts on an honest execution.(v)
Testm(Umi). This query is only used to measureA’s knowledge on a session key. WhenA asks aTest query to thefreshUmi, a coin is flipped to generate a random bit b. If b = 1, the real session key is returned to A. Otherwise a random value is returned. A is allowed to make aTest query only once at any time during the experiment.Queries of Adversary in the PAKE . All queries and their responses are the same as those ofMAKE except a corrupt query with notions. A corrupt query in thePAKE is defined only in case ofa=1. A notion on the instance, Umi, is replaced with Uti (Stj). And also, to distinguish notations in the security proof, we define notations of queries for thePAKE without subscript m (e.g.,Send,Corrupt,Execute,Reveal,Test).


## 3.2. Security Definition

Definition 7 (session identifier, session key, partner identifier, and partnering 2-partyMAKE).
We define a session identifier (SID) for Umi assidUmi which is the concatenation of all messages sent and received by Umi. A session key is denoted asskU,S. A partner ID is a corresponding participant with whom Umi is interacting, which is denoted aspidUmi. Instances Umi and Smj are partnering if the following conditions are satisfied: (1) Both instances have been accepted with the same session key, session ID, and partner ID. That is, if both oracles have been accepted withskU,S,sidUmi,pidUmj,(skS,U,sidSmj,pidSmj), thenskU,S=skS,U,sidUmi=sidSmj≠NULL. (2) No oracle other than Umi and Smj is accepted with the pid of Umi and Smj. (pidUmi=Smj, pidSmj=Umi).Regarding thePAKE, we use essentially the same definitions, notations forSID, a session key, andPID with the ones ofMAKE model. Thus we do not define them again here. Next, we consider freshness, forward secure freshness forMAKE andPAKE, respectively.Definition 8 (freshness for 2-partyMAKE).
An instanceUmi isfresh in terms of multifactorAKE if (1) neither Umi nor its partner has been asked for aReveal query; (2) neither Umi nor its partner has been asked for aCorrupt(Umi, 1),Corrupt(Umi, 2),Corrupt(Umi, 3),Corrupt(Umi, 4) queries. The second condition means that Umi and its partner have been asked for less than four corrupt queries. That is, A can askCorrupt queries satisfying the following equation.(8)Corrupt1∧Corrupt2∧Corrupt3∧Corrupt4=FALSEIf A has asked query ofCorrupt(U,a) where 1≤a≤4, then it isCorrupt(a) =TRUE. Otherwise, it isCorrupt(a) =FALSE.Definition 9 (forward secure freshness for 2-partyMAKE).
Regarding forward secrecy, a new freshness,fs-fresh, is defined. An instance Umi isfs-fresh in terms of multiple authentication factors if (1) neither Umi nor its partner has been asked for aReveal query; (2) beforeTest(Umi), neither Umi nor its partner has been asked for all threeCorrupt(Umi, 1),Corrupt(Umi, 2),Corrupt(Umi, 3),Corrupt(Umi, 4) queries andSendm(U,i,M) queries.Remark 10.
The above first property (1) is forReveal case for bothPAKE andMAKE. However, the second property (2) has been modified by multiple authentication factors. For example, let us consider some cases offs-fresh. If A asksCorrupt(Umi, 1),Corrupt(Umi, 2) queries (less than all four Corrupt queries) beforeTest(Umi) and does askSendm(U,i,M) query, then it isfs-fresh. Also, if A asksCorrupt(Umi, 1),Corrupt(Umi, 2), andCorrupt(Umi, 3) queries beforeTest(Umi) and does not askSendm(U,i,M) query, then it isfs-fresh. If all Corrupt queries have been asked after Test query, then it is alsofs-fresh.Definition 11 (freshness for 2-partyPAKE).
It is defined in the same way asMAKE except the second condition. That is, the first condition is the same as theMAKE, but the second condition is that (2) neither Umi nor its partner has been asked for aCorrupt(Umi, 1) query.Definition 12 (forward secure freshness for 2-partyPAKE).
It is defined in the same way as the aboveMAKE except the second condition. That is, (2) beforeTest(Umi), neither Umi nor its partner has been asked for aCorrupt(Umi, 1) query andSendm(U,i,M) query.Definition 13 (session key security for 2-partyMAKE).
Let us consider the following experiment. We assume that an adversaryA is run within a polynomial time bound T. A interacts with a finite number of oracles by asking queries defined above during the experiment. A can ask aTest query to a fresh oracle at any time. When A asks aTest query to thefreshUmi, then the experiment flips a coin for bit b. If it lands b = 1, then the real session key is returned to the adversary. Otherwise, a random key is returned to the adversary. Eventually A guesses b, outputs the guessed bit b′, and terminates the experiment. Theskadvantage of A in attacking theMAKE protocol P is defined as AdvP,skmake(A)=2Prb=b′-1. It should be negligible as follows.(9)AdvP,skmakeA,T,k≤C′·qss′+εk,where ε(k) is a negligible function, D(e.g.,12,898,437) is a password space for a Zipf’s parameters C′(e.g.,0062239), s′(e.g.,0.155478), which follows Zipf’s law for password [42, 43], qs is the number of on-lineSend queries asked, and k is a security parameter.Remark 14.
Since a memorable password is chosen by a user, it is not uniformly distributed. That is, due to the memorable property, it is natural for the user not to be able to make full use of the whole distribution ofD at password selection stage. Thus, regarding the formalization term on an on-line-password guessing attack in all of our definitions here, we follow the Zipf assumption for password distributions [42, 43], which formalizes user own memorable password (not uniform from D), C′·qss′, rather than a uniformly modeled term qs/D, where C′,s′ are Zipf’s parameters [42, 43] depending on dataset, policy, language.Definition 15 (session key security for 2-partyPAKE).
The definition forPAKE is the same as theMAKE security except that a notion AdvP,skmake(A,T,R) is replaced with a notion AdvP,skpake(A,T,k). It is defined as AdvP,skpake(A,T,k)=2Prb=b′-1 and it should be as follows. AdvP,skpake(A,T,k)≤C′·qss′+ε(k) where ε(k) is a negligible function, |D|(e.g.,12,898,437) is a password space for a Zipf’s parameters C′(e.g.,0062239), s′(e.g.,0.155478), which follows Zipf’s law for password [42, 43], qs is the number of on-lineSend queries asked, and k is a security parameter.Definition 16 (forward secure session key security for 2-partyPAKE).
A forward secure 2-partyPAKE protocol is defined with a condition that thefs-fresh instance should be asked for aTest query. Basically its definition is the same as the definition of session key securePAKE except that a notion AdvP,skpake(A,T,k) is replaced with a notion AdvP,skfs-pake(A,T,k)=2Pr[b=b′]-1. It should be as follows: AdvP,skfs-pake(A,T,k)≤C′·qss′+ε(k) where ε(k) is a negligible function, D(e.g.,12,898,437) is a password space for a Zipf’s parameters C′(e.g.,0062239), s′(e.g.,0.155478), which follows Zipf’s law for password [42, 43], qs is the number of on-lineSend queries asked, and k is a security parameter.The mutual authentication forMAKE andPAKE is defined by an event,Succ, as follows.Definition 17 (mutual Authentication [2]).
We follow a definition of mutual authentication defined in [2]. For client authentication, we consider sessions where the server accepts with no partner instance of the client. With regard to server authentication, we consider sessions where the client accepts with no partner instance of the server. We say that an adversary breaks mutual authentication if either server or client instance is accepted, but has no partner oracle. We denote this event bySucc and its probability is defined as SuccPma(A,T,k)=Pr[Succ]. We say that a givenMAKE protocol P provides mutual authentication if SuccPma(A,T,k) is negligible as follows:(10)SuccPmaA,T,k≤εk,where ε(k) is a negligible function and k is a security parameter.


## 4. A Compiler fromPAKE toMAKE withPUF

The construction ofMAKE consists of two phases; one is for thePAKE phase to derive a common key, and the other is for generic authentication phase with the derived common key, as illustrated in Figure 2 and Figure 3, respectively. We use the following notations in the protocol.Figure 2
A setup phase.Figure 3
A general construction ofMAKE.


### 4.1. Notation

(i)
c: It is a set of messages transferred between the userU and the serverS in thePAKE. We assume that it has lc bits. We can assume a function (pseudorandom or hash function) that maps a set of messages generated by anyPAKE into the fixed size lc bits. (ii)
I D, δ~,pw, skp: ID is an identifier ofU and it has lid bits. δ~ isU’s biometric template,pw isU’s memorable password, ands is a long-term secret key. skp is an agreed-upon common key betweenU andS in thePAKE, which are assumed to have lp bits. (iii)
H 0 , H 1 , H 2 , H 3: They are all cryptographic secure hash functions, which are simulated as random oracles in the security proof. They are, respectively, defined as H0:{0,1}n0→{0,1}l0, H1:{0,1}n1→{0,1}l1, H2:{0,1}n2→{0,1}l2, H3:{0,1}n3→{0,1}l3.


### 4.2. A Setup Description

(i)
A setup is executed over a secure channel.U first computes a strong secret δ(=Gen(δ~)) from its own biometric template δ~. And,U evaluatesPUF and generates (r,h) fromGen(PUF(δ∥s)). The values ID,r,pw are sent toS. (ii)
U andS securely maintain (pw,PUF,δ,s)(ID,r,pw), respectively.We note that the setup phase is a necessary step to sharepw in thePAKE setting. OurMAKE setup phase is also unavoidable for securely delivering multiple authentication factors betweenU andS.


### 4.3. A Description of the Compiler

(1)
A userU and a serverS execute any efficient and provably securePAKE protocol with c (a set of all transferred messages) and a common key skp. If the agreement of skp or authentication is failed in thePAKE, then our compiler outputs a failure and stops the protocol. Otherwise, it continues to run the next step (2). (2)
The userU inputs own biometric template δ~ and then computes a strong secret δ fromRep(δ~,hδ).U evaluatesPUF and executesGen with h, then computes r(=PUF(H0(δ∥s),hr)), and derives common keys k1(=H1(c∥r∥skp)),k2(=H2(c∥r∥skp)) for message authentication.U finally computes α1(=gxmodq) and β1(=MACk1(α1)) and sends them toS. (3)
On receivingα1,β1,S first searchesU’s list, (ID,r,pw) from database. ThenS derives k1(=H1(c∥r∥skp)),k2(=H2(c∥r∥skp)) from c,r,skp.S with k1 verifies that β1(=MACk1(α1)) is valid or not. If it is valid thenS makes α2=gymodq for a random y∈Zq∗, its authentication tag β2=MACk2(α2), and γ=(α1)y.S also computes keying material sk′(=H3(γ∥α1∥α2∥β1∥β2∥c)) and its authenticator h1(=H3(sk′∥1)). The messages α2,β2,h1 are sent toU. (4)
Regardingα2,β2,h1,U verify α2’s authenticator β2. If it is valid thenU computes keying material sk′(=H3(γ∥α1∥α2∥β1∥β2∥c)).U also verifies h1(=H3(sk′∥1)) by using sk′. If it is also valid thenU makes h2(=H3(sk′∥2)) and sends it toS. ThenU finally computes a common session key sk(=H3(sk′∥0)). On receiving h2,S verifies h2 with sk′. If it is valid,S finally computes a common session key sk=H3(sk′∥0).In Figures2 and 3, we illustrate a setup phase and a final generalPUF-basedMAKE construction, respectively. Our construction combines two authentication factors, biometric template, and long-term secret and makes one secret r using aPUF. However, our compiler does not directly handle a password at all, but just takes aPAKE as an input. That is, ourMAKE obtainsPAKE’s session key skt through executing a securePAKE. This approach can guarantee the password security such as off-line or on-line dictionary attacks, as explained earlier. Anyway, these two secret values r,skt are mainly used to establish intermediate keys k1,k2.


### 4.4. Security Proof

The following well-known lemma [44] is used for calculating difference of probability between adjacent games in the security proof.Lemma 18.
LetE, E′, and F be events defined on a probability space such that Pr[E∧¬F]=Pr[E′∧¬F]. Then, we have |Pr[E]-Pr[E′]|≤Pr[F].Theorem 19.
LetA be a PPT adversary against the session key security ofMAKE protocol P within a time bound T. A can ask qsm to send queries, qem executes queries, and then(11)AdvP,skmakeA,T,k≤2AdvP,skpakeAp,Ta,k+2ϵpuf++qH322l3+qsm+qse222p+1+2AdvAddhddhTD,G+4AdvAmaccmaTmac,kSuccPmaA,T,k≤qsm22l1+1+2l2+12l1+l2+2+AdvP,skpakeAp,Ta,k+ϵpuf+qH322l3+1+qsm+qse222p+1+AdvAddhddhTD,G+2AdvAmaccmaTmac,kwhere Ta,TD≥T+qsm(Tf+Te+Th),Tmac≥T+Tf(qt+qv). qsm,qt,qv are the total numbers ofSendm, tag, verification (for MAC) queries. Tf,Te,Th are the computation time for MAC, exponentiation, and hash function, respectively.Proof. We assume an adversary A that runs in games from G0 to G5. In each game, A asks aTestm query, then a coin for bit b is flipped to specify a real key or a random key, and then A outputs a guessing bit b′. Let Si be an event that b′ = b in Gi and Pr[Si] is its probability. Also, Succi is defined as an event that a server or a user instance accepts with no partner instance of the client in Gi as in Definition 17.Game G 0 . The game G0 provides a real environment for theMAKE protocol. By the security definition, the session key advantage of A is defined as follows.(12)AdvP,skmakeA,T,k=2PrS0-1,SuccPmaA,T,k=PrSucc0GameG1. In this game, a random key skr is selected randomly and it is replaced with the established key skp of thePAKE. Through the replacement, we show that if there exists a PPT adversary AD that distinguishes two games, then one can build an adversary Ap that breaks the security ofPAKE, which is shown in Lemma 20.Lemma 20.
The difference of success probability betweenG0 and G1 is at most the advantage of breaking 2-partyPAKE protocol.(13)PrS0-PrS1=AdvP,skpakeAp,Ta,kwhere Ta≥T+qsm(Tf+Te+Th). qsm is the total number ofSendm queries. Tf,Te,Th are the computation time for MAC, exponentiation, and hash function.Proof.
A p exploits AD to guess a hidden bit b defined in the experiment of 2-partyPAKE. Ap provides simulations on queries asked by AD. All queries are simulated as follows.(i)
Hash queries of H1,H2,H3: If AD asks a hash query of m to H1 (resp. H2,H3) where a list (m,λ) appears in the hash table δH1 (resp. δH2, δH3), then λ is returned as an answer for H1(m) (resp. H1(m),H2(m)). Otherwise, a new λ∈{0,1}1l (resp. l2,l3) is chosen at random and returned. Then the list (m,λ) is added to the table δH1 (resp. δH2,δH2).(ii)
Sendm(U,i,M): It is classified into two types as follows.
(a)
IfSend query is asked to the parts ofPAKE, Ap first asksSend(U,i,m) query to thePAKE and then returns its output as an answer. At the end ofPAKE protocol, there exists aSend query to let the instance be accepted in thePAKE. For thisSend query, Ap uses the random key skr to simulate an answer α1,β1. That is, first, Ap evaluatesPUF, computes r, and then decides k1=H1(c∥r∥skr), k2=H2(c∥r∥skr) from skr and H1,H2 oracles. Ap finally produces an answer, α1=gxmodq, β1=MACk1(α1) for a random x from Zq∗. Ap keeps r,α1,β1 for later simulations.(b)
Otherwise ifM=α2,β2,h1, then Ap verifies h1. If it is valid, then it is accepted with sk′=H3(γ∥α1∥α2∥β1∥β2∥c) and h2=H3(sk′∥2). Ap finally outputs h2 as an answer.(iii)
Sendm(S,j,M): There are also three types of queries as follows.
(a)
IfSend query belongs to the query inPAKE, Ap asksSend(S,i,M) query to thePAKE and then uses its output as an answer.(b)
IfM=α1∥β1, then Ap verifies β1. If it is valid, then Ap makes k1=H1(c∥r∥skr), k2=H2(c∥r∥skr) with previously made value c,r. Ap finally produces an answer, α2=gymodq, β2=MACk1(α2) for a random y from Zq∗. Ap keeps α2,β2 for later simulations.(c)
Otherwise ifM=h2, then Ap first verifies h2. If it is valid, then Ap accepts it with sk=H3(sk′∥0).(iv)
Executem(U,i,S,j): To return transcripts of an honest execution between Umi and Smj, Ap collects all outputs ofSendm queries and outputs them as an answer(v)
Revealm(U,t): For the instance that has been accepted, Ap returns sk=H3(sk′∥0) as an output where sk′=H3(γ∥α1∥α2∥β1∥β2∥c).(vi)
Corruptm(U,a): According to a, it outputs registered passwordpw(a=1),PUF(a=2), biometric template δ~(a=3), ands(a=4) for U.(vii)
Testm(U,t): When AD asksTestm(U,i) query, Ap chooses a random bit b∈{0,1} and selects afs-fresh instance in aspect ofMAKE and asks aTest(U,i) query. For the hidden bit b (real or session key), AD outputs b′. If b=b′, then Ap outputs 1; otherwise, Apake outputs 0.
Let us consider the advantage ofAp over the above simulation. We define an eventreal as a real session key, skp (b=1) is given by experiment ofMAKE security while an eventrand is a random key, and skr (b=0) is given to Ap.(14)AdvP,skpakeT′,Ap,k=2Prb=b′-1=Pr⁡Ap=1∣real-PrAp=1∣rand=Pr⁡b=b′∣G0-Prb=b′∣G1=PrS0-PrS1If we suppose AD runs with polynomial time T, then Ap’s running time Ta is dependent on T. Additionally, it requires the time of making the messages α1,β1,α2,β2,h1,h2. Hence the total time is bounded as Ta≥T+qsm(Tf+Te+Th). qsm is the total number ofSendm queries. Tf,Te,Th are the computation time for MAC, exponentiation, hash function.
This completes the proof of Lemma20.
Game G 2. In this game, we consider a value r in the protocol, which is an output of idealPUF. We replace r with a random value as a random oracle. That is, a table LP is maintained for a valid simulation. Regarding each input x, if a list (x,y) appears in LP, then y is outputted as an answer. Otherwise, a random y is selected from {0,1}lo and returned as an answer forPUF(x). The list (x,y) is added to the list LP. Then, if there exists A that is able to distinguish two adjacent games, then it is clear to build an adversary Apuf. In G1, an idealPUF has been used, but in G2, a randomly chosen value is used. Apuf returns an output bit d=1 if b′=b. Otherwise, Apuf returns d=0. Then we have the following.(15)ϵpuf=PrExpApufpuf1k=1-PrExpApufpuf0k=1=Pr⁡d=1∣PUFx-Pr⁡d=1∣y←0,1lo≥Pr⁡b=b′∣G1-Prb=b′∣G2=Pr⁡S1-Pr⁡S2GameG3. In this game, we analyze a collision eventCol that an identical session key is accidentally generated for any two sessions. This event is due to a random oracle H3 that produces final secrets sk′,sk. It can be analyzed in two cases. The first case is that if its simulated output (randomly chosen value) is identical for two sessions, then two sessions naturally have the same sk′,sk. For example, on two different input queries x=(γ∥α1∥α2∣β1∥β2∥c),x′=(γ′∥α1′∥α2′∣β1′∥β2′∥c′), each output can be simulated as an one random value (e.g.(x,y),(x′,y)∈Lp). However, its probability is qH32/2l3+1, which is negligible. The second case is that the input queries (γ∥α1∥α2∣β1∥β2∥c) themselves can be the same and then they naturally output the same output of sk′,sk. The security (duplication) of c comes from the security ofPAKE, which is negligible. In addition, the values α2,β2 are decided by α1,α2. Hence, for two sessions, the probability of equally selecting α1=gxmodq,β1=gymodq is bound to (qsm+qse)2/22(q+1) where qsm,qse are the total numbers ofSend,Execute queries. We have the following.(16)PrS2-PrS3≤PrCol≤qH322l3+1+qsm+qse222q+1GameG4. In this game, we consider an eventMS that A makes validSend(S,j,M~) queries where M~=β~1∥MACk1(α~1). Regarding valid messages α1,β1, theirSend(S,j,M) query has been simulated in G2. Here, our goal is to exclude forgery events amongSend(S,j,M) queries that have valid MAC pair β~1∥MACk1(α~1). Let us assume a MAC forgery Amac. If this event happens, then Amac halts and outputs the pair α~1,β~1 as its forgery of MAC, which contradicts a secure MAC assumption. If there are no forgeries, then Amac returns a failure notification. Other processes of simulation for A are the same as those of previous games. Amac requires computational time Tmac such that Tmac≥T+Tf(qt+qv), where τT is computational time for MAC and qt, qv are tag and verification queries that A makes. The same analysis applies to the case of α2,β2. We have the following.(17)PrG3∣¬MS=PrG4∣¬MSPrG3-PrG4≤PrMS≤2·AdvAmaccmaTmac,kGameG5. In this game, we consider a randomDDH triple Drand=(X,Y,Z) where X=gumodq,Y=gvmodq, and Z=grmodq. Using DR, theSend queries are simulated as follows.(i)
Sendm(U,i,M): It is classified into two types as follows.
(a)
IfSend query is asked for letting the instance be accepted in thePAKE, then G5 uses the random key skr to make k1,k2. However, the value α1 is replaced with X. Accordingly, the value β1(=MACk1(X)) is made by k1,X. Other simulations are the same as the previous games.(b)
Otherwise ifM=α2,β2,h1, then Ap verifies h1. If it is valid, then accepts with sk′=H3(Z∥α1∥α2∥β1∥β2∥c) and h2=H3(sk′∥2). Ap finally outputs h2 as an answer.(ii)
Sendm(S,j,M): There are also three types of queries as follows.
(a)
IfSend query belongs to the query inPAKE, the way of simulations is the same as the previous game.(b)
IfM=α1∥β1, then Ap verifies β1. If it is valid, then Ap makes k1=H1(c∥r∥skr), k2=H2(c∥r∥skr). However, the answer value α2 is replaced with Y and its MAC value is also computed by β2=MACk1Y. Others are the same as the previous games.
By usingA, which tries to distinguish two games G4 and G5, one can build a polynomial time algorithm Addh that breaks the assumption ofDDH. For aTest query, A guesses a coin and outputs b′. If b=b′, then Addh outputs 1, which means that the input triple is a realDDH triple. Otherwise it outputs 0 which means that the input triple is a randomDDH triple. The success probability of Addh is calculated as follows. Addh requires computation time for simulatingSend queries such that TD≥T+qsm(Tf+Te+Th).(18)AdvAddhddhTD,G=PrAddhgx,gy,gxy=1;x,y←Zq∗-PrAddhX,Y,Z=1;u,v←Zq∗,Z←G≤PrAddh=1∣Dreal-PrAddh=1∣Drand.=Prb=b′∣G4-Prb=b′∣G5.=PrS4-PrS5.
Let us considerPr[G5] in G5. As simulated inSend queries, the session key sk is decided by the given random element Z. Hence sk is random and independent of elements U, V. That is, no information of b is leaked through theTest query. We have the following.(19)PrS5=12
Thus, we obtain the final result as follows.(20)PrS0≤AdvP,skpakeAp,Ta,k+ϵpuf+qH322l3+1+qsm+qse222p+1+AdvAddhddhTD,G+2·AdvAmaccmaTmac,k+12
Let us consider the eventSucci. We have already excluded collision events on α1,β2 and MAC forgeries on β1,β2 in the previous games. The left analysis is on h1,h2. In this game, the secret sk′ is made by a random oracle H3 and h1(=H3(sk′∥1)) is also simulated by a random oracle H3. Thus, for successful impersonation, A should correctly guess h1, h2. This probability is bounded as qsm2/2l1+1,qsm2/2l2+1, respectively.(21)PrSucc5≤qsm22l1+1+qsm22l2+1By the following difference, we can bound SuccPma(A,T,k). (Δi is the probability difference between Gi and Gi+1.)(22)SuccPmaAM=PrSucc0≤PrSucc5+∑i=04Δi≤qsm22l1+1+2l2+12l1+l2+2+AdvP,skpakeAp,Ta,k+ϵpuf+qH322l3+1+qsm+qse222p+1+AdvAddhddhTD,G+2·AdvAmaccmaTmac,k
This completes the proof of Theorem19.


## 4.1. Notation

(i)
c: It is a set of messages transferred between the userU and the serverS in thePAKE. We assume that it has lc bits. We can assume a function (pseudorandom or hash function) that maps a set of messages generated by anyPAKE into the fixed size lc bits. (ii)
I D, δ~,pw, skp: ID is an identifier ofU and it has lid bits. δ~ isU’s biometric template,pw isU’s memorable password, ands is a long-term secret key. skp is an agreed-upon common key betweenU andS in thePAKE, which are assumed to have lp bits. (iii)
H 0 , H 1 , H 2 , H 3: They are all cryptographic secure hash functions, which are simulated as random oracles in the security proof. They are, respectively, defined as H0:{0,1}n0→{0,1}l0, H1:{0,1}n1→{0,1}l1, H2:{0,1}n2→{0,1}l2, H3:{0,1}n3→{0,1}l3.


## 4.2. A Setup Description

(i)
A setup is executed over a secure channel.U first computes a strong secret δ(=Gen(δ~)) from its own biometric template δ~. And,U evaluatesPUF and generates (r,h) fromGen(PUF(δ∥s)). The values ID,r,pw are sent toS. (ii)
U andS securely maintain (pw,PUF,δ,s)(ID,r,pw), respectively.We note that the setup phase is a necessary step to sharepw in thePAKE setting. OurMAKE setup phase is also unavoidable for securely delivering multiple authentication factors betweenU andS.


## 4.3. A Description of the Compiler

(1)
A userU and a serverS execute any efficient and provably securePAKE protocol with c (a set of all transferred messages) and a common key skp. If the agreement of skp or authentication is failed in thePAKE, then our compiler outputs a failure and stops the protocol. Otherwise, it continues to run the next step (2). (2)
The userU inputs own biometric template δ~ and then computes a strong secret δ fromRep(δ~,hδ).U evaluatesPUF and executesGen with h, then computes r(=PUF(H0(δ∥s),hr)), and derives common keys k1(=H1(c∥r∥skp)),k2(=H2(c∥r∥skp)) for message authentication.U finally computes α1(=gxmodq) and β1(=MACk1(α1)) and sends them toS. (3)
On receivingα1,β1,S first searchesU’s list, (ID,r,pw) from database. ThenS derives k1(=H1(c∥r∥skp)),k2(=H2(c∥r∥skp)) from c,r,skp.S with k1 verifies that β1(=MACk1(α1)) is valid or not. If it is valid thenS makes α2=gymodq for a random y∈Zq∗, its authentication tag β2=MACk2(α2), and γ=(α1)y.S also computes keying material sk′(=H3(γ∥α1∥α2∥β1∥β2∥c)) and its authenticator h1(=H3(sk′∥1)). The messages α2,β2,h1 are sent toU. (4)
Regardingα2,β2,h1,U verify α2’s authenticator β2. If it is valid thenU computes keying material sk′(=H3(γ∥α1∥α2∥β1∥β2∥c)).U also verifies h1(=H3(sk′∥1)) by using sk′. If it is also valid thenU makes h2(=H3(sk′∥2)) and sends it toS. ThenU finally computes a common session key sk(=H3(sk′∥0)). On receiving h2,S verifies h2 with sk′. If it is valid,S finally computes a common session key sk=H3(sk′∥0).In Figures2 and 3, we illustrate a setup phase and a final generalPUF-basedMAKE construction, respectively. Our construction combines two authentication factors, biometric template, and long-term secret and makes one secret r using aPUF. However, our compiler does not directly handle a password at all, but just takes aPAKE as an input. That is, ourMAKE obtainsPAKE’s session key skt through executing a securePAKE. This approach can guarantee the password security such as off-line or on-line dictionary attacks, as explained earlier. Anyway, these two secret values r,skt are mainly used to establish intermediate keys k1,k2.


## 4.4. Security Proof

The following well-known lemma [44] is used for calculating difference of probability between adjacent games in the security proof.Lemma 18.
LetE, E′, and F be events defined on a probability space such that Pr[E∧¬F]=Pr[E′∧¬F]. Then, we have |Pr[E]-Pr[E′]|≤Pr[F].Theorem 19.
LetA be a PPT adversary against the session key security ofMAKE protocol P within a time bound T. A can ask qsm to send queries, qem executes queries, and then(11)AdvP,skmakeA,T,k≤2AdvP,skpakeAp,Ta,k+2ϵpuf++qH322l3+qsm+qse222p+1+2AdvAddhddhTD,G+4AdvAmaccmaTmac,kSuccPmaA,T,k≤qsm22l1+1+2l2+12l1+l2+2+AdvP,skpakeAp,Ta,k+ϵpuf+qH322l3+1+qsm+qse222p+1+AdvAddhddhTD,G+2AdvAmaccmaTmac,kwhere Ta,TD≥T+qsm(Tf+Te+Th),Tmac≥T+Tf(qt+qv). qsm,qt,qv are the total numbers ofSendm, tag, verification (for MAC) queries. Tf,Te,Th are the computation time for MAC, exponentiation, and hash function, respectively.Proof. We assume an adversary A that runs in games from G0 to G5. In each game, A asks aTestm query, then a coin for bit b is flipped to specify a real key or a random key, and then A outputs a guessing bit b′. Let Si be an event that b′ = b in Gi and Pr[Si] is its probability. Also, Succi is defined as an event that a server or a user instance accepts with no partner instance of the client in Gi as in Definition 17.Game G 0 . The game G0 provides a real environment for theMAKE protocol. By the security definition, the session key advantage of A is defined as follows.(12)AdvP,skmakeA,T,k=2PrS0-1,SuccPmaA,T,k=PrSucc0GameG1. In this game, a random key skr is selected randomly and it is replaced with the established key skp of thePAKE. Through the replacement, we show that if there exists a PPT adversary AD that distinguishes two games, then one can build an adversary Ap that breaks the security ofPAKE, which is shown in Lemma 20.Lemma 20.
The difference of success probability betweenG0 and G1 is at most the advantage of breaking 2-partyPAKE protocol.(13)PrS0-PrS1=AdvP,skpakeAp,Ta,kwhere Ta≥T+qsm(Tf+Te+Th). qsm is the total number ofSendm queries. Tf,Te,Th are the computation time for MAC, exponentiation, and hash function.Proof.
A p exploits AD to guess a hidden bit b defined in the experiment of 2-partyPAKE. Ap provides simulations on queries asked by AD. All queries are simulated as follows.(i)
Hash queries of H1,H2,H3: If AD asks a hash query of m to H1 (resp. H2,H3) where a list (m,λ) appears in the hash table δH1 (resp. δH2, δH3), then λ is returned as an answer for H1(m) (resp. H1(m),H2(m)). Otherwise, a new λ∈{0,1}1l (resp. l2,l3) is chosen at random and returned. Then the list (m,λ) is added to the table δH1 (resp. δH2,δH2).(ii)
Sendm(U,i,M): It is classified into two types as follows.
(a)
IfSend query is asked to the parts ofPAKE, Ap first asksSend(U,i,m) query to thePAKE and then returns its output as an answer. At the end ofPAKE protocol, there exists aSend query to let the instance be accepted in thePAKE. For thisSend query, Ap uses the random key skr to simulate an answer α1,β1. That is, first, Ap evaluatesPUF, computes r, and then decides k1=H1(c∥r∥skr), k2=H2(c∥r∥skr) from skr and H1,H2 oracles. Ap finally produces an answer, α1=gxmodq, β1=MACk1(α1) for a random x from Zq∗. Ap keeps r,α1,β1 for later simulations.(b)
Otherwise ifM=α2,β2,h1, then Ap verifies h1. If it is valid, then it is accepted with sk′=H3(γ∥α1∥α2∥β1∥β2∥c) and h2=H3(sk′∥2). Ap finally outputs h2 as an answer.(iii)
Sendm(S,j,M): There are also three types of queries as follows.
(a)
IfSend query belongs to the query inPAKE, Ap asksSend(S,i,M) query to thePAKE and then uses its output as an answer.(b)
IfM=α1∥β1, then Ap verifies β1. If it is valid, then Ap makes k1=H1(c∥r∥skr), k2=H2(c∥r∥skr) with previously made value c,r. Ap finally produces an answer, α2=gymodq, β2=MACk1(α2) for a random y from Zq∗. Ap keeps α2,β2 for later simulations.(c)
Otherwise ifM=h2, then Ap first verifies h2. If it is valid, then Ap accepts it with sk=H3(sk′∥0).(iv)
Executem(U,i,S,j): To return transcripts of an honest execution between Umi and Smj, Ap collects all outputs ofSendm queries and outputs them as an answer(v)
Revealm(U,t): For the instance that has been accepted, Ap returns sk=H3(sk′∥0) as an output where sk′=H3(γ∥α1∥α2∥β1∥β2∥c).(vi)
Corruptm(U,a): According to a, it outputs registered passwordpw(a=1),PUF(a=2), biometric template δ~(a=3), ands(a=4) for U.(vii)
Testm(U,t): When AD asksTestm(U,i) query, Ap chooses a random bit b∈{0,1} and selects afs-fresh instance in aspect ofMAKE and asks aTest(U,i) query. For the hidden bit b (real or session key), AD outputs b′. If b=b′, then Ap outputs 1; otherwise, Apake outputs 0.
Let us consider the advantage ofAp over the above simulation. We define an eventreal as a real session key, skp (b=1) is given by experiment ofMAKE security while an eventrand is a random key, and skr (b=0) is given to Ap.(14)AdvP,skpakeT′,Ap,k=2Prb=b′-1=Pr⁡Ap=1∣real-PrAp=1∣rand=Pr⁡b=b′∣G0-Prb=b′∣G1=PrS0-PrS1If we suppose AD runs with polynomial time T, then Ap’s running time Ta is dependent on T. Additionally, it requires the time of making the messages α1,β1,α2,β2,h1,h2. Hence the total time is bounded as Ta≥T+qsm(Tf+Te+Th). qsm is the total number ofSendm queries. Tf,Te,Th are the computation time for MAC, exponentiation, hash function.
This completes the proof of Lemma20.
Game G 2. In this game, we consider a value r in the protocol, which is an output of idealPUF. We replace r with a random value as a random oracle. That is, a table LP is maintained for a valid simulation. Regarding each input x, if a list (x,y) appears in LP, then y is outputted as an answer. Otherwise, a random y is selected from {0,1}lo and returned as an answer forPUF(x). The list (x,y) is added to the list LP. Then, if there exists A that is able to distinguish two adjacent games, then it is clear to build an adversary Apuf. In G1, an idealPUF has been used, but in G2, a randomly chosen value is used. Apuf returns an output bit d=1 if b′=b. Otherwise, Apuf returns d=0. Then we have the following.(15)ϵpuf=PrExpApufpuf1k=1-PrExpApufpuf0k=1=Pr⁡d=1∣PUFx-Pr⁡d=1∣y←0,1lo≥Pr⁡b=b′∣G1-Prb=b′∣G2=Pr⁡S1-Pr⁡S2GameG3. In this game, we analyze a collision eventCol that an identical session key is accidentally generated for any two sessions. This event is due to a random oracle H3 that produces final secrets sk′,sk. It can be analyzed in two cases. The first case is that if its simulated output (randomly chosen value) is identical for two sessions, then two sessions naturally have the same sk′,sk. For example, on two different input queries x=(γ∥α1∥α2∣β1∥β2∥c),x′=(γ′∥α1′∥α2′∣β1′∥β2′∥c′), each output can be simulated as an one random value (e.g.(x,y),(x′,y)∈Lp). However, its probability is qH32/2l3+1, which is negligible. The second case is that the input queries (γ∥α1∥α2∣β1∥β2∥c) themselves can be the same and then they naturally output the same output of sk′,sk. The security (duplication) of c comes from the security ofPAKE, which is negligible. In addition, the values α2,β2 are decided by α1,α2. Hence, for two sessions, the probability of equally selecting α1=gxmodq,β1=gymodq is bound to (qsm+qse)2/22(q+1) where qsm,qse are the total numbers ofSend,Execute queries. We have the following.(16)PrS2-PrS3≤PrCol≤qH322l3+1+qsm+qse222q+1GameG4. In this game, we consider an eventMS that A makes validSend(S,j,M~) queries where M~=β~1∥MACk1(α~1). Regarding valid messages α1,β1, theirSend(S,j,M) query has been simulated in G2. Here, our goal is to exclude forgery events amongSend(S,j,M) queries that have valid MAC pair β~1∥MACk1(α~1). Let us assume a MAC forgery Amac. If this event happens, then Amac halts and outputs the pair α~1,β~1 as its forgery of MAC, which contradicts a secure MAC assumption. If there are no forgeries, then Amac returns a failure notification. Other processes of simulation for A are the same as those of previous games. Amac requires computational time Tmac such that Tmac≥T+Tf(qt+qv), where τT is computational time for MAC and qt, qv are tag and verification queries that A makes. The same analysis applies to the case of α2,β2. We have the following.(17)PrG3∣¬MS=PrG4∣¬MSPrG3-PrG4≤PrMS≤2·AdvAmaccmaTmac,kGameG5. In this game, we consider a randomDDH triple Drand=(X,Y,Z) where X=gumodq,Y=gvmodq, and Z=grmodq. Using DR, theSend queries are simulated as follows.(i)
Sendm(U,i,M): It is classified into two types as follows.
(a)
IfSend query is asked for letting the instance be accepted in thePAKE, then G5 uses the random key skr to make k1,k2. However, the value α1 is replaced with X. Accordingly, the value β1(=MACk1(X)) is made by k1,X. Other simulations are the same as the previous games.(b)
Otherwise ifM=α2,β2,h1, then Ap verifies h1. If it is valid, then accepts with sk′=H3(Z∥α1∥α2∥β1∥β2∥c) and h2=H3(sk′∥2). Ap finally outputs h2 as an answer.(ii)
Sendm(S,j,M): There are also three types of queries as follows.
(a)
IfSend query belongs to the query inPAKE, the way of simulations is the same as the previous game.(b)
IfM=α1∥β1, then Ap verifies β1. If it is valid, then Ap makes k1=H1(c∥r∥skr), k2=H2(c∥r∥skr). However, the answer value α2 is replaced with Y and its MAC value is also computed by β2=MACk1Y. Others are the same as the previous games.
By usingA, which tries to distinguish two games G4 and G5, one can build a polynomial time algorithm Addh that breaks the assumption ofDDH. For aTest query, A guesses a coin and outputs b′. If b=b′, then Addh outputs 1, which means that the input triple is a realDDH triple. Otherwise it outputs 0 which means that the input triple is a randomDDH triple. The success probability of Addh is calculated as follows. Addh requires computation time for simulatingSend queries such that TD≥T+qsm(Tf+Te+Th).(18)AdvAddhddhTD,G=PrAddhgx,gy,gxy=1;x,y←Zq∗-PrAddhX,Y,Z=1;u,v←Zq∗,Z←G≤PrAddh=1∣Dreal-PrAddh=1∣Drand.=Prb=b′∣G4-Prb=b′∣G5.=PrS4-PrS5.
Let us considerPr[G5] in G5. As simulated inSend queries, the session key sk is decided by the given random element Z. Hence sk is random and independent of elements U, V. That is, no information of b is leaked through theTest query. We have the following.(19)PrS5=12
Thus, we obtain the final result as follows.(20)PrS0≤AdvP,skpakeAp,Ta,k+ϵpuf+qH322l3+1+qsm+qse222p+1+AdvAddhddhTD,G+2·AdvAmaccmaTmac,k+12
Let us consider the eventSucci. We have already excluded collision events on α1,β2 and MAC forgeries on β1,β2 in the previous games. The left analysis is on h1,h2. In this game, the secret sk′ is made by a random oracle H3 and h1(=H3(sk′∥1)) is also simulated by a random oracle H3. Thus, for successful impersonation, A should correctly guess h1, h2. This probability is bounded as qsm2/2l1+1,qsm2/2l2+1, respectively.(21)PrSucc5≤qsm22l1+1+qsm22l2+1By the following difference, we can bound SuccPma(A,T,k). (Δi is the probability difference between Gi and Gi+1.)(22)SuccPmaAM=PrSucc0≤PrSucc5+∑i=04Δi≤qsm22l1+1+2l2+12l1+l2+2+AdvP,skpakeAp,Ta,k+ϵpuf+qH322l3+1+qsm+qse222p+1+AdvAddhddhTD,G+2·AdvAmaccmaTmac,k
This completes the proof of Theorem19.


## 5. Performance Analysis and Discussion

For coherent comparison and analysis, we follow a recent evaluation metrics that has been suggested by Wang and Wang [45] and been utilized in many other recent studies [20, 23, 45–47]. One important difference is that our scheme is not two-factor (smartcard and password)AKE scheme, but a generic construction that securely converts any securePAKE intoMAKE. Hence, regarding criteria on a password, our construction depends on the properties that the basisPAKE itself guarantees. And also, our scheme aims for a universal construction and thus it cannot guarantee or handle criteria on a smart card. Moreover, our scheme is the first genericMAKE using aPUF; for short, there is no scheme for comparison. However, in view of generic construction, we compare our generic construction with other recent schemes in Table 1 (security) and Table 2 (efficiency). As explained earlier, we remind again that recent schemes [33, 34] cannot be a generic construction, unlike their claims, even though their subjects are on general construction. However, please note that their constructions have been built up with the assumption of secure existingPAKE orTAKE. Thus, those two schemes [33, 34] have been analyzed with theFMA [35] scheme in each table. First, we briefly summarize 12 evaluation criteria introduced in [45].(i)
C1: The server never needs a database for user password or verifier.(ii)
C2: The user can freely choose and change a memorable password(iii)
C3: The server administrator should not be able to derive user’s password.(iv)
C4: The scheme is strong against a smart card loss attack.(v)
C5: The scheme is strong against off-line, replay, parallel session, desynchronization, stolen verifier, impersonation, key control, unknown key share, and known key attacks.(vi)
C6: The user can revoke own card without changing its own identity.(vii)
C7: The scheme provides a key agreement between participants.(viii)
C8: The scheme is free from a clock synchronization.(ix)
C9: If a wrong password is typed by mistake, any type of notification is alarmed to the user.(x)
C10: The scheme provides a mutual authentication.(xi)
C11: The scheme protects users’ identities.(xii)
C12: The scheme provides forward secrecy.Table 1
Security criteria comparison.
Scheme G C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 HXCZD [33] × × √ - - √ - √ √ - √ - √ YWMG [34] × × √ - - √ - √ √ - √ - √ FMA [35] √ × - - - √ - √ √ - √ - √ Our scheme √ × - - √ √ × √ √ - √ - √ G: whether it is a generic compiler or not, √: satisfied, ×: unsatisfied, -: depending on the basis instantiations or not considered.Table 2
Efficiency comparison.
Scheme G T F R 1 TCC2 TSS3 HXCZD [33] × 4 ≤ 2 ⋅ t a ≤ 6 h + f h+f YWMG [34] × 2 ≤ t a ≤ 3 2 e + v + p e + f + h 2e+s+pd FMA [35] √ 10 ≤ u + p w + b + p k + 2 ≤ 14 3 h 3h Our scheme √ 5 ≤ p w + 3 ≤ 6 5 h + 2 e + m + p 5 h + 2 e + m T F R   1: the total flow number of communications. The notions u,pw,b,pk,ta, respectively, mean unauthenticated key exchange, PAKE, biometric-based authentication, public key authentication, and two-factor authentication protocols. T2he total computation time for a user: h,e,m: computation time for hash, exponentiation, and MAC operations, resp.; p,f: computation time for PUF, fuzzy vault, resp.; s,v: computation time for a signature generation and verification, resp. T3he total computation time for a server.


### 5.1. Discussion on Security Criteria

OurMAKE has been built up with a securePAKE scheme. From thePAKE, our compiler securely adds other multiple factors to achieve an authenticated key exchange. Since the securePAKE itself handles security of password, our construction is free from its related attacks. Thus, in some criteria, our scheme depends on how the basisPAKE has been instantiated. The same applies to other schemes [33–35]. It is because not only they have been constructed from secure initiations (general construction), but also security criteria defined in [45] (Table 1) are actually motivated from two-factor authenticators (password and smart card). For instance, a generalMAKE construction just assumes multiple long-term secrets and does not take account of how these secrets are maintained. Thus, a smart card stolen attack (C4) cannot be considered in a general construction model. In our model, however, we firstly usePUF as an authenticator that is dependent on a hardware device such as a smart card, and C4 can be analyzed for comparison. Even if an adversary obtainsPUF, our scheme is still secure authentication unless other secrets remain secure, which is better criterion than others. The criteria C2, C3, C4, C6, C9 are closely related to the underlyingPAKE orTAKE. In particular, C1 evaluates whether a database is required or not for a password verifier. In mostTAKE schemes over a smart card, actually C1 may be easily attained. It is because they assume a smart card that is capable enough to take a valid password as an input through a card reader and calculate a valid shared secret with a server if its input password is valid on a smart card. Afterwards, the server just takes a step for checking whether the shared secret is valid or not, which never requires a password or password verifier on a server side. However, in generic compiler setting, first of all, holding a smart card is not necessary condition. It just focuses on how to securely transform a secure primitive one into an integrated primitive one. One may argue that a generalMAKE can be systematically constructed from aTAKE with a smart card. But, in this approach, the underlyingTAKE already includes a smart card, and it is hard (or not practical) to include a new hardware dependentPUF more. In conclusion, inPUF setting, it is more reasonable to initiatePAKE (orAKE) first and then constructMAKE by usingPUF. Table 1 shows that our scheme is an accurate generalMAKE construction with relatively better security performances.


### 5.2. Discussion on Efficiency

Table2 shows, in general construction setting, that our scheme achieves better communication cost than theFMA [35] scheme. TheFMA scheme executes many types of subprotocols for making a generalMAKE. It may guarantee better security from the secure underlying subprotocols with simple implementation. However, two authentication factors are never used together for one subprotocol, and many types of subprotocols should be initiated independently. Hence, it has a fundamental limits in order to reduce the total communication cost. In Table 2, we assume that a normalPAKE orTAKE can be designed in two communication flows without an authentication. This influences upper or lower bounding ofTFR. In conclusion, our scheme requires at most 6 communication flows with no public key based setting such as a signature used. While the total communication flow is more greatly enhanced than theFMA [35], our communication cost is not better than theFMA. This slight inefficiency is due to the use ofPUF and Diffie-Hellman keying materials for guaranteeing forward secrecy. That is, enhanced security and the reduced total communication cost balance up this little computation loss. One interesting topic would be on how we can designMAKE withPUF at the lower communication bounding cost (e.g.,4≤pw+2). Except the part ofPAKE, our compiler additionally needs three more communication flows. But, by initiatingPAKE, we already share a common key. This common secret can be used for making a final session key with slight modification. For instance, in our protocol, a user can compute a final session key after receiving messages in step (3), ignoring step (4). In the same way, upon messages of (2), a server can generate a final session key before step (3). The messages in steps (2) and (3) can be designed for just sharing ephemeral values and verifying (authentication) keying materials by using a shared key fromPAKE. This construction remains one of future work including security analysis under rigorous security model.


## 5.1. Discussion on Security Criteria

OurMAKE has been built up with a securePAKE scheme. From thePAKE, our compiler securely adds other multiple factors to achieve an authenticated key exchange. Since the securePAKE itself handles security of password, our construction is free from its related attacks. Thus, in some criteria, our scheme depends on how the basisPAKE has been instantiated. The same applies to other schemes [33–35]. It is because not only they have been constructed from secure initiations (general construction), but also security criteria defined in [45] (Table 1) are actually motivated from two-factor authenticators (password and smart card). For instance, a generalMAKE construction just assumes multiple long-term secrets and does not take account of how these secrets are maintained. Thus, a smart card stolen attack (C4) cannot be considered in a general construction model. In our model, however, we firstly usePUF as an authenticator that is dependent on a hardware device such as a smart card, and C4 can be analyzed for comparison. Even if an adversary obtainsPUF, our scheme is still secure authentication unless other secrets remain secure, which is better criterion than others. The criteria C2, C3, C4, C6, C9 are closely related to the underlyingPAKE orTAKE. In particular, C1 evaluates whether a database is required or not for a password verifier. In mostTAKE schemes over a smart card, actually C1 may be easily attained. It is because they assume a smart card that is capable enough to take a valid password as an input through a card reader and calculate a valid shared secret with a server if its input password is valid on a smart card. Afterwards, the server just takes a step for checking whether the shared secret is valid or not, which never requires a password or password verifier on a server side. However, in generic compiler setting, first of all, holding a smart card is not necessary condition. It just focuses on how to securely transform a secure primitive one into an integrated primitive one. One may argue that a generalMAKE can be systematically constructed from aTAKE with a smart card. But, in this approach, the underlyingTAKE already includes a smart card, and it is hard (or not practical) to include a new hardware dependentPUF more. In conclusion, inPUF setting, it is more reasonable to initiatePAKE (orAKE) first and then constructMAKE by usingPUF. Table 1 shows that our scheme is an accurate generalMAKE construction with relatively better security performances.


## 5.2. Discussion on Efficiency

Table2 shows, in general construction setting, that our scheme achieves better communication cost than theFMA [35] scheme. TheFMA scheme executes many types of subprotocols for making a generalMAKE. It may guarantee better security from the secure underlying subprotocols with simple implementation. However, two authentication factors are never used together for one subprotocol, and many types of subprotocols should be initiated independently. Hence, it has a fundamental limits in order to reduce the total communication cost. In Table 2, we assume that a normalPAKE orTAKE can be designed in two communication flows without an authentication. This influences upper or lower bounding ofTFR. In conclusion, our scheme requires at most 6 communication flows with no public key based setting such as a signature used. While the total communication flow is more greatly enhanced than theFMA [35], our communication cost is not better than theFMA. This slight inefficiency is due to the use ofPUF and Diffie-Hellman keying materials for guaranteeing forward secrecy. That is, enhanced security and the reduced total communication cost balance up this little computation loss. One interesting topic would be on how we can designMAKE withPUF at the lower communication bounding cost (e.g.,4≤pw+2). Except the part ofPAKE, our compiler additionally needs three more communication flows. But, by initiatingPAKE, we already share a common key. This common secret can be used for making a final session key with slight modification. For instance, in our protocol, a user can compute a final session key after receiving messages in step (3), ignoring step (4). In the same way, upon messages of (2), a server can generate a final session key before step (3). The messages in steps (2) and (3) can be designed for just sharing ephemeral values and verifying (authentication) keying materials by using a shared key fromPAKE. This construction remains one of future work including security analysis under rigorous security model.


## 6. Concluding Remarks

In the paper, we presented a generalPUF-MAKE construction that securely transforms aPAKE into aMAKE with a physically unclonable function. Our construction especially takes a securePAKE rather than taking thePKI-based (or nonPKI-based)AKE as an input. The reason is that it naturally resolves a password issue such as off-line or on-line dictionary attacks. For instance, in case of transforming aPKI-basedAKE into aMAKE, we should first go through a problem on how an easy-to-guess password can be securely combined with thePKI-basedAKE and biometrics, which would be much more harder than the case of combining thePAKE with a long-term key and biometrics. Nevertheless, in view of foundation works, it is quite meaningful to show the existence ofPUF-MAKE fromPKI, non-PKI-basedAKE, or otherAKE primitives. In addition, we elaborated on two-party setting here, but a generalPUF-MAKE construction for a group setting would also be a good future work.



---

*Source: 5935292-2019-03-04.xml*