Continuous After-the-Fact Leakage-Resilient eCK-Secure Key Exchange

Abstract

Security models for two-party authenticated key exchange (AKE) protocols have developed over time to capture the security of AKE protocols even when the adversary learns certain secret values. Increased granularity of security can be modelled by considering partial leakage of secrets in the manner of models for leakage-resilient cryptography, designed to capture side-channel attacks. In this work, we use the strongest known partial-leakage-based security model for key exchange protocols, namely continuous after-the-fact leakage $\mathrm {eCK}$ ($\mathrm {CAFL\text {-}eCK}$) model. We resolve an open problem by constructing the first concrete two-pass leakage-resilient key exchange protocol that is secure in the $\mathrm {CAFL\text {-}eCK}$ model.

1 Introduction

During the past two decades side-channel attacks have become a familiar method of attacking cryptographic systems. Examples of information which may leak during executions of cryptographic systems, and so allow side-channel attacks, include timing information [6, 8, 18], electromagnetic radiation [15], and power consumption [21]. Leakage may reveal partial information about the secret parameters which have been used for computations in cryptographic systems. In order to abstractly model leakage attacks, cryptographers have proposed the notion of leakage-resilient cryptography [1, 4, 7, 13, 14, 16, 17, 20]. In this notion the information that leaks is not fixed, but instead chosen adversarially, so as to model any possible physical leakage function. A variety of different cryptographic primitives have been developed in recent years. As one of the most widely used cryptographic primitives, it is important to analyze the leakage resilience of key exchange protocols.

Earlier key exchange security models, such as the Bellare–Rogaway [5], Canetti–Krawczyk [9], and extended Canetti–Krawczyk (eCK) [19] models, aim to capture security against an adversary who can fully compromise some, but not all, secret values. This is not a very granular form of leakage, and thus is not suitable for modelling side-channel attacks in key exchange protocols enabled by partial leakage of secret keys. This motivates the development of leakage-resilient key exchange security models [3, 4, 11, 22, 23]. Among them the generic security model proposed by Alawatugoda et al. [3] in 2014 facilitates more granular leakage.

Alawatugoda et al. [3] proposed a generic leakage-security model for key exchange protocols, which can be instantiated as either a bounded leakage variant or as a continuous leakage variant. In the bounded leakage variant, the total amount of leakage is bounded, whereas in the continuous leakage variant, each protocol execution may reveal a fixed amount of leakage. Further, the adversary is allowed to obtain the leakage even after the session key is established for the session under attack (after-the-fact leakage). In Sect. 3 we review the continuous leakage instantiation of the security model proposed by Alawatugoda et al.

Alawatugoda et al. [3] also provided a generic construction for a protocol which is proven secure in their generic leakage-security model. However, when it comes to a concrete construction, the proposed generic protocol can only be instantiated in a way that is secure in the bounded version of the security model. Until now there are no suitable cryptographic primitives which can be used to instantiate the generic protocol in the continuous leakage variant of the security model.

Our aim is to propose a concrete protocol construction which can be proven secure in the continuous leakage instantiation of the security model of Alawatugoda et al. Thus, we introduce the first concrete construction of continuous and after-the-fact leakage-resilient key exchange protocol.

Bounded Leakage and Continuous Leakage. Generally, in models assuming bounded leakage there is an upper bound on the amount of leakage information for the entire period of execution. The security guarantee only holds if the leakage amount is below the prescribed bound. Differently, in models allowing continuous leakage the adversary is allowed to obtain leakage over and over for a polynomial number of iterations during the period of execution. Naturally, there is a bound on the amount of leakage that the adversary can obtain in each single iteration, but the total amount of leakage that the adversary can obtain for the entire period of execution is unbounded.

After-the-Fact Leakage. The concept of after-the-fact leakage has been applied previously to encryption primitives. Generally, leakage which happens after the challenge is given to the adversary is considered as after-the-fact leakage. In key exchange security models, the challenge to the adversary is to distinguish the session key of a chosen session, usually called the test session, from a random session key [5, 9, 19], After-the-fact leakage is the leakage which happens after the test session is established.

Our Contribution. Alawatugoda et al. [3] left the construction of a continuous after-the-fact leakage-resilient $\mathrm {eCK}$ secure key exchange protocol as an open problem. In this paper, we construct such a protocol (protocol $\mathrm {P2}$) using existing leakage-resilient cryptographic primitives. We use leakage-resilient storage schemes and their refreshing protocols [12] for this construction.

Table 1 compares the proposed protocol $\mathrm {P2}$, with the NAXOS protocol [19], the Moriyama-Okamoto (MO) protocol [22] and the generic Alawatugoda et al. [3] protocol instantiation, by means of computation cost, security model and the proof model.

Table 1. Security and efficiency comparison of leakage-resilient key exchange protocols

In protocol $\mathrm {P2}$, the secret key is encoded into two equal-sized parts of some chosen size, and the leakage bound from each of the two parts is $15\,\%$ of the size of a part, per occurrence. Since this is a continuous leakage model the total leakage amount is unbounded. More details of the leakage tolerance of protocol $\mathrm {P2}$ may be found in Sect. 5.3.

2 Preliminaries

We discuss the preliminaries which we use for the protocol constructions.

2.1 Diffie–Hellman Problems

Let $\mathcal {G}$ be a group generation algorithm and $(\mathbb {G},q,g) \leftarrow \mathcal {G}(1^k)$, where $\mathbb {G}$ is a cyclic group of prime order q and g is an arbitrary generator.

Definition 1

(Computational Diffie–Hellman $(\mathrm {CDH})$ Problem). Given an instance $(g,g^a,g^b)$ for $a,b \xleftarrow {\$} \mathbb {Z}_q$, the $\mathrm {CDH}$ problem is to compute $g^{ab}$.

Definition 2

(Decision Diffie–Hellman $(\mathrm {DDH})$ Problem). Given an instance $(g,g^a,g^b,g^c)$ for $a,b \xleftarrow {\$} \mathbb {Z}_q$ and either $c \xleftarrow {\$} \mathbb {Z}_q$ or $c=ab$, the $\mathrm {DDH}$ problem is to distinguish whether ${c}={ab}$ or not.

Definition 3

(Gap Diffie–Hellman $(\mathrm {GDH})$ Problem). Given an instance $(g,g^a,g^b)$ for $a,b \xleftarrow {\$} \mathbb {Z}_q$, the $\mathrm {GDH}$ problem is to find $g^{ab}$ given access to an oracle $\mathcal {O}$ that solves the $\mathrm {DDH}$ problem.

2.2 Leakage-Resilient Storage

We review the definitions of leakage-resilient storage according to Dziembowski et al. [12]. The idea behind their construction is to split the storage of elements into two parts using a randomized encoding function. As long as leakage is then limited from each of its two parts then no adversary can learn useful information about an encoded element. The key observation of Dziembowski et al. is then to show how such encodings can be refreshed in a leakage-resilient way so that the new parts can be re-used. To construct a continuous leakage-resilient primitive the relevant secrets are split, used separately, and then refreshed between any two usages.

Definition 4

(Dziembowski-Faust Leakage-Resilient Storage Scheme). For any $m,n \in \mathbb {N}$, the storage scheme $\varLambda _{\mathbb {Z}_q^*}^{n,m}=(\mathrm {Encode}_{\mathbb {Z}_q^*}^{n,m},\mathrm {Decode}_{\mathbb {Z}_q^*}^{n,m})$ efficiently stores elements $s\in ({\mathbb {Z}_q^*})^m$ where:

• $\mathrm {Encode}_{\mathbb {Z}_q^*}^{n,m}(s):$ $s_L\xleftarrow {\$}(\mathbb {Z}_q^*)^n \backslash \{(0^n)\}$, then $s_R\leftarrow (\mathbb {Z}_q^*)^{n \times m}$ such that $s_L \cdot s_R=s$ and outputs $(s_L,s_R)$.

• $\mathrm {Decode}_{\mathbb {Z}_q^*}^{n,m}(s_L,s_R):$ outputs $s_L\cdot s_R$.

In the model we expect an adversary to see the results of a leakage function applied to $s_L$ and $s_R$. This may happen each time computation occurs.

Definition 5

( $\varvec{\lambda }$ -limited Adversary). If the amount of leakage obtained by the adversary from each of $s_L$ and $s_R$ is limited to $\varvec{\lambda }=(\lambda _1,\lambda _2)$ bits in total respectively, the adversary is known as a $\varvec{\lambda }$ -limited adversary.

Definition 6

( $(\varvec{\lambda }_{\varLambda },\epsilon _1)$ -secure leakage-resilient storage scheme). We say $\varLambda =(\mathrm {Encode},\mathrm {Decode})$ is $(\varvec{\lambda }_{\varLambda },\epsilon _1)$-secure leakage-resilient, if for any $s_0,s_1\xleftarrow {\$}({\mathbb {Z}_q^*})^m$ and any $\varvec{\lambda }_{\varLambda }$-limited adversary $\mathcal {C}$, the leakage from $\mathrm {Encode}(s_0)=({s_0}_L,{s_0}_R)$ and $\mathrm {Encode}(s_1)=({s_1}_L,{s_1}_R)$ are statistically $\epsilon _1$-close. For an adversary-chosen leakage function $\mathbf {f}=(f_1,f_2)$, and a secret s such that $\mathrm {Encode}(s)=(s_L,s_R)$, the leakage is denoted as $\big (f_1({s}_L),f_2({s}_R)\big )$.

Lemma 1

([12]). Suppose that $m<n/20$. Then $\varLambda _{\mathbb {Z}_q^*}^{n,m}=(\mathrm {Encode}_{\mathbb {Z}_q^*}^{n,m},\mathrm {Decode}_{\mathbb {Z}_q^*}^{n,m})$ is $(\varvec{\lambda }, \epsilon )$-secure for some $\epsilon$ and $\varvec{\lambda }=(0.3 \cdot n \log q,0.3 \cdot n \log q)$.

The encoding function can be used to design different leakage resilient schemes with bounded leakage. The next step is to define how to refresh the encoding so that a continuous leakage is also possible to defend against.

Definition 7

(Refreshing of Leakage-Resilient Storage). Let $(L',R')\leftarrow \mathrm {Refresh}^{n,m}_{\mathbb {Z}_q^*}(L,R)$ be a refreshing protocol that works as follows:

• Input  : (L, R) such that $L\in ({\mathbb {Z}_q^*})^{n}$ and $R\in ({\mathbb {Z}_q^*})^{n\times m}$.

• Refreshing R : 

  • 1. $A\xleftarrow {\$} ({\mathbb {Z}_q^*})^{n} \backslash \{(0^n)\}$ and $B\leftarrow \text {non singular } ({\mathbb {Z}_q^*})^{n\times m}$ such that $A\cdot B=(0^m)$.

  • 2. $M \leftarrow \text {non-singular }({\mathbb {Z}_q^*})^{n \times n}$ such that $L\cdot M=A$.

  • 3. $X \leftarrow M\cdot B$ and $R' \leftarrow R+X$.

• Refreshing L : 

  • 1. $\tilde{A}\xleftarrow {\$} ({\mathbb {Z}_q^*})^{n} \backslash \{(0^n)\}$ and $\tilde{B}\leftarrow \text {non singular } ({\mathbb {Z}_q^*})^{n\times m}$ such that $\tilde{A}\cdot \tilde{B}=(0^m)$.

  • 2. $\tilde{M}\leftarrow \text {non-singular } ({\mathbb {Z}_q^*})^{n\times n}$ such that $\tilde{M}\cdot R'=\tilde{B}$.

  • 3. $Y \leftarrow \tilde{A}\cdot \tilde{M}$ and $L' \leftarrow L+Y$.

• Output $:(L',R')$

Let $\varLambda =(\mathrm {Encode},\mathrm {Decode})$ be a $(\varvec{\lambda }_{\varLambda },\epsilon _1)$-secure leakage-resilient storage scheme and $\mathrm {Refresh}$ be a refreshing protocol. We consider the following experiment $\mathrm {Exp}$, which runs $\mathrm {Refresh}$ for $\ell$ rounds and lets the adversary obtain leakage in each round. For refreshing protocol $\mathrm {Refresh}$, a $\varvec{\lambda }_{\mathrm {Refresh}}$-limited adversary $\mathcal {B}$, $\ell \in \mathbb {N}$ and $s\xleftarrow {\$}({\mathbb {Z}_q^*})^m$, we denote the following experiment by $\mathrm {Exp}_{(\mathrm {Refresh},\varLambda )}(\mathcal {B},s,\ell )$:

• 1. For a secret s, the initial encoding is generated as $({s}_L^0,{s}_R^0)\leftarrow \mathrm {Encode}(s)$.

• 2. For $j=1$ to $\ell$ run $\mathcal {B}$ against the $j^{th}$ round of the refreshing protocol.

• 3. Return whatever $\mathcal {B}$ outputs.

We require that the adversary $\mathcal {B}$ outputs a single bit $b\in \{0,1\}$ upon performing the experiment $\mathrm {Exp}$ using $s\xleftarrow {\$}\{s_0,s_1\} \in ({\mathbb {Z}_q^*})^m$. Now we define leakage-resilient security of a refreshing protocol.

Definition 8

( $(\ell ,\varvec{\lambda }_{\mathrm {Refresh}},\epsilon _2)$ -secure Leakage-Resilient Refreshing Protocol). For a $(\varvec{\lambda }_{\varLambda },\epsilon _1)$-secure Leakage-Resilient Storage Scheme $\varLambda =(\mathrm {Encode},\mathrm {Decode})$ with message space $({\mathbb {Z}_q^*})^m$, $\mathrm {Refresh}$ is $(\ell ,\varvec{\lambda }_{\mathrm {Refresh}},\epsilon _2)$-secure leakage-resilient, if for every $\varvec{\lambda }_{\mathrm {Refresh}}$-limited adversary $\mathcal {B}$ and any two secrets $s_0,s_1\in ({\mathbb {Z}_q^*})^m$, the statistical distance between $\mathrm {Exp}_{(\mathrm {Refresh},\varLambda )}(\mathcal {B},s_0,\ell )$ and $\mathrm {Exp}_{(\mathrm {Refresh},\varLambda )}(\mathcal {B},s_1,\ell )$ is bounded by $\epsilon _2$.

Theorem 1

([12]). Let $m/3 \le n, n\ge 16$ and $\ell \in \mathbb {N}$. Let n, m and $\mathbb {Z}_q^*$ be such that $\varLambda ^{n,m}_{\mathbb {Z}_q^*}$ is $(\varvec{\lambda },\epsilon )$-secure leakage-resilient storage scheme (Definitions 4 and 6). Then the refreshing protocol $\mathrm {Refresh}^{n,m}_{\mathbb {Z}_q^*}$ (Definition 7) is a $(\ell ,\varvec{\lambda }/2, \epsilon ')$-secure leakage-resilient refreshing protocol for $\varLambda ^{n,m}_{\mathbb {Z}_q^*}$ (Definition 8) with $\epsilon '= 2\ell q (3q^m \epsilon + m q^{-n-1})$.

3 Continuous After-the-Fact Leakage $\mathrm {eCK}$ Model and the $\mathrm {eCK}$ Model

In 2014 Alawatugoda et al. [3] proposed a new security model for key exchange protocols, namely the generic after-the-fact leakage eCK ($(\cdot )\mathrm {AFL\text {-}eCK}$) model which, in addition to the adversarial capabilities of the $\mathrm {eCK}$ model [19], is equipped with an adversary-chosen, efficiently computable, adaptive leakage function $\mathbf {f}$, enabling the adversary to obtain the leakage of long-term secret keys of protocol principals. Therefore the $(\cdot )\mathrm {AFL\text {-}eCK}$ model captures all the attacks captured by the $\mathrm {eCK}$ model, and captures the partial leakage of long-term secret keys due to side-channel attacks.

The eCK Model. In the $\mathrm {eCK}$ model, in sessions where the adversary does not modify the communication between parties (passive sessions), the adversary is allowed to reveal both ephemeral secrets, long-term secrets, or one of each from two different parties, whereas in sessions where the adversary may forge the communication of one of the parties (active sessions), the adversary is allowed to reveal the long-term or ephemeral secret of the other party. The security challenge is to distinguish the real session key from a random session key, in an adversary-chosen protocol session.

Generic After-the-Fact Leakage eCK Model. The generic $(\cdot )\mathrm {AFL\text {-}eCK}$ model can be instantiated in two different ways which leads to two security models. Namely, bounded after-the-fact leakage eCK ($\mathrm {BAFL\text {-}eCK}$) model and continuous after-the-fact leakage eCK ($\mathrm {CAFL\text {-}eCK}$) model. The $\mathrm {BAFL\text {-}eCK}$ model allows the adversary to obtain a bounded amount of leakage of the long-term secret keys of the protocol principals, as well as reveal session keys, long-term secret keys and ephemeral keys. Differently, the $\mathrm {CAFL\text {-}eCK}$ model allows the adversary to continuously obtain arbitrarily large amount of leakage of the long-term secret keys of the protocol principals, enforcing the restriction that the amount of leakage per observation is bounded.

Below we revisit the definitions of the $\mathrm {CAFL\text {-}eCK}$ model, and we also recall the definitions of the $\mathrm {eCK}$ model as a comparison to the $\mathrm {CAFL\text {-}eCK}$ definitions.

3.1 Partner Sessions in the $\mathrm {CAFL\text {-}eCK}$ Model

Definition 9

(Partner Sessions in the $\mathrm {CAFL\text {-}eCK}$ Model). Two oracles $\varPi _{U,V}^{s}$ and $\varPi _{U',V'}^{s'}$ are said to be partners if all of the following hold:

• 1. both $\varPi _{U,V}^{s}$ and $\varPi _{U',V'}^{s'}$ have computed session keys;

• 2. messages sent from $\varPi _{U,V}^{s}$ and messages received by $\varPi _{U',V'}^{s'}$ are identical;

• 3. messages sent from $\varPi _{U',V'}^{s'}$ and messages received by $\varPi _{U,V}^{s}$ are identical;

• 4. $U'=V$ and $V'=U$;

• 5. Exactly one of U and V is the initiator and the other is the responder.

The protocol is said to be correct if two partner oracles compute identical session keys.

The definition of partner sessions is the same in the $\mathrm {eCK}$ model.

3.2 Leakage in the $\mathrm {CAFL\text {-}eCK}$ Model

A realistic way in which side-channel attacks can be mounted against key exchange protocols seems to be to obtain the leakage information from the protocol computations which use the secret keys. Following the previously used premise in other leakage models that “only computation leaks information”, leakage is modelled where any computation takes place using secret keys. In normal protocol models, by issuing a $\mathtt {Send}$ query, the adversary will get a protocol message which is computed according to the normal protocol computations. Sending an adversary-chosen, efficiently computable adaptive leakage function with the $\mathtt {Send}$ query thus reflects the concept “only computation leaks information”.

A tuple of t adaptively chosen efficiently computable leakage functions $\mathbf {f}=(f_{1j},f_{2j},\dots ,f_{tj})$ are introduced; j indicates the jth leakage occurrence and the size t of the tuple is protocol-specific. A key exchange protocol may use more than one cryptographic primitive where each primitive uses a distinct secret key. Hence, it is necessary to address the leakage of secret keys from each of those primitives. Otherwise, some cryptographic primitives which have been used to construct a key exchange protocol may be stateful and the secret key is encoded into number of parts. The execution of a stateful cryptographic primitive is split into a number of sequential stages and each of these stages uses one part of the secret key. Hence, it is necessary to address the leakage of each of these encoded parts of the secret key.

Note that the adversary is restricted to obtain leakage from each key part independently: the adversary cannot use the output of $f_{1j}$ as an input parameter to the $f_{2j}$ and so on. This prevents the adversary from observing a connection between each part.

3.3 Adversarial Powers of the $\mathrm {CAFL\text {-}eCK}$ Model

The adversary $\mathcal {A}$ controls the whole network. $\mathcal {A}$ interacts with a set of oracles which represent protocol instances. The following query allows the adversary to run the protocol.

• $\mathtt {Send}(U,V,s,m,\mathbf {f})$ query: The oracle $\varPi _{U,V}^{s}$, computes the next protocol message according to the protocol specification and sends it to the adversary $\mathcal {A}$, along with the leakage $\mathbf {f}(sk_U)$. $\mathcal {A}$ can also use this query to activate a new protocol instance as an initiator with blank m.

In the $\mathrm {eCK}$ model $\mathtt {Send}$ query is same as the above except the leakage function $\mathbf {f}$.

The following set of queries allow the adversary $\mathcal {A}$ to compromise certain session specific ephemeral secrets and long-term secrets from the protocol principals.

• $\mathtt {SessionKeyReveal}(U,V,s)$ query: $\mathcal {A}$ is given the session key of the oracle $\varPi _{U,V}^{s}$.

• $\mathtt {EphemeralKeyReveal}(U,V,s)$ query: $\mathcal {A}$ is given the ephemeral keys (per-session randomness) of the oracle $\varPi _{U,V}^{s}$.

• $\mathtt {Corrupt}(U)$ query: $\mathcal {A}$ is given the long-term secrets of the principal U. This query does not reveal any session keys or ephemeral keys to $\mathcal {A}$.

$\mathtt {SessionKeyReveal}$, $\mathtt {EphemeralKeyReveal}$ and $\mathtt {Corrupt}$ (Long-term key reveal) queries are the same in the $\mathrm {eCK}$ model.

Once the oracle $\varPi _{U,V}^{s}$ has accepted a session key, asking the following query the adversary $\mathcal {A}$ attempt to distinguish it from a random session key. The $\mathtt {Test}$ query is used to formalize the notion of the semantic security of a key exchange protocol.

• $\mathtt {Test}(U,s)$ query: When $\mathcal {A}$ asks the Test query, the challenger first chooses a random bit $b \xleftarrow {\$} \{0,1\}$ and if $b=1$ then the actual session key is returned to $\mathcal {A}$, otherwise a random string chosen from the same session key space is returned to $\mathcal {A}$. This query is only allowed to be asked once across all sessions.

The $\mathtt {Test}$ query is the same in the $\mathrm {eCK}$ model.

3.4 Freshness Definition of the $\mathrm {CAFL\text {-}eCK}$ Model

Definition 10

( $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$ -freshness). Let $\varvec{\lambda }=(\lambda _1,\dots ,\lambda _t)$ be a vector of t elements (same size as $\mathbf {f}$ in $\mathtt {Send}$ query). An oracle $\varPi _{U,V}^{s}$ is said to be $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$-fresh if and only if:

• 1. The oracle $\varPi _{U,V}^{s}$ or its partner, $\varPi _{V,U}^{s'}$ (if it exists) has not been asked a $\mathtt {SessionKeyReveal}$.

• 2. If the partner $\varPi _{V,U}^{s'}$ exists, none of the following combinations have been asked:

  • (a) $\mathtt {Corrupt}(U)$ and $\mathtt {EphemeralKeyReveal}(U,V,s)$.

  • (b) $\mathtt {Corrupt}(V)$ and $\mathtt {EphemeralKeyReveal}(V,U,s')$.

• 3. If the partner $\varPi _{V,U}^{s'}$ does not exist, none of the following combinations have been asked:

  • (a) $\mathtt {Corrupt}(V)$.

  • (b) $\mathtt {Corrupt}(U)$ and $\mathtt {EphemeralKeyReveal}(U,V,s)$.

• 4. For each $\mathtt {Send}(U,\cdot ,\cdot ,\cdot , \mathbf {f})$ query, size of the output of $|f_{ij}({sk_{U}}_i)|\le \lambda _i$.

• 5. For each $\mathtt {Send}(V,\cdot ,\cdot ,\cdot , \mathbf {f})$ queries, size of the output of $|f_{ij}({sk_{V}}_i)|\le \lambda _i$.

The $\mathrm {eCK}$-freshness is slightly different from the $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$-freshness by stripping off points 4 and 5.

3.5 Security Game and Security Definition of the $\mathrm {CAFL\text {-}eCK}$ Model

Definition 11

( $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$ Security Game). Security of a key exchange protocol in the $\mathrm {CAFL\text {-}eCK}$ model is defined using the following security game, which is played by the adversary $\mathcal {A}$ against the protocol challenger.

• Stage 1: $\mathcal {A}$ may ask any of $\mathtt {Send}$, $\mathtt {SessionKeyReveal}$, $\mathtt {EphemeralKeyReveal}$ and $\mathtt {Corrupt}$ queries to any oracle at will.

• Stage 2: $\mathcal {A}$ chooses a $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$-fresh oracle and asks a $\mathtt {Test}$ query. The challenger chooses a random bit $b \xleftarrow {\$} \{0,1\}$, and if $b=1$ then the actual session key is returned to $\mathcal {A}$, otherwise a random string chosen from the same session key space is returned to $\mathcal {A}$.

• Stage 3: $\mathcal {A}$ continues asking $\mathtt {Send}$, $\mathtt {SessionKeyReveal}$, $\mathtt {EphemeralKeyReveal}$ and $\mathtt {Corrupt}$ queries. $\mathcal {A}$ may not ask a query that violates the $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$-freshness of the test session.

• Stage 4: At some point $\mathcal {A}$ outputs the bit $b' \leftarrow \{0,1\}$ which is its guess of the value b on the test session. $\mathcal {A}$ wins if $b'=b$.

The $\mathrm {eCK}$ security game is same as the above, except that in Stage 2 and Stage 3 $\mathrm {eCK}$-fresh oracles are chosen instead of $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$-fresh oracles. $Succ_{\mathcal {A}}$ is the event that the adversary $\mathcal {A}$ wins the security game in Definition 11.

Definition 12

( $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$ -security). A protocol $\pi$ is said to be $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$ secure if there is no adversary $\mathcal {A}$ that can win the $\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}$ security game with significant advantage. The advantage of an adversary $\mathcal {A}$ is defined as ${\mathrm {Adv}}_{\pi }^{\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}}(\mathcal {A})=|2 \Pr ({Succ}_\mathcal {A}) -1|.$

3.6 Practical Interpretation of Security of $\mathrm {CAFL\text {-}eCK}$ Model

We review the relationship between the $\mathrm {CAFL\text {-}eCK}$ model and real world attack scenarios.

• Active adversarial capabilities: $\mathtt {Send}$ queries address the powers of an active adversary who can control the message flow over the network. In the previous security models, this property is addressed by introducing the send query.

• Side-channel attacks: Leakage functions are embedded with the $\mathtt {Send}$ query. Thus, assuming that the leakage happens when computations take place in principals, a wide variety of side-channel attacks such as timing attacks, EM emission based attacks, power analysis attacks, which are based on continuous leakage of long-term secrets are addressed. This property is not addressed in the earlier security models such as the BR models, the CK model, the eCK model and the Moriyama-Okamoto model.

• Malware attacks: $\mathtt {EphemeralKeyReveal}$ queries cover the malware attacks which steal stored ephemeral keys, given that the long-term keys may be securely stored separately from the ephemeral keys in places such as smart cards or hardware security modules. Separately, $\mathtt {Corrupt}$ queries address malware attacks which steal the long-term secret keys of protocol principals. In the previous security models, this property is addressed by introducing the ephemeral-key reveal, session-state reveal and corrupt queries.

• Weak random number generators: Due to weak random number generators, the adversary may correctly determine the produced random number. $\mathtt {EphemeralKeyReveal}$ query addresses situations where the adversary can get the ephemeral secrets. In the previous security models, this property is addressed by introducing the ephemeral-key reveal query or the session-state reveal query.

4 Protocol $\mathrm {P1}$: Simple $\mathrm {eCK}$-Secure Key Exchange

The motivation of LaMacchia et al. [19] in designing the eCK model was that an adversary should have to compromise both the long-term and ephemeral secret keys of a party in order to recover the session key. In this section we look at construction paradigms of $\mathrm {eCK}$-secure key exchange protocols, because our aim is to construct a $\mathrm {CAFL\text {-}eCK}$-secure key exchange protocol using a $\mathrm {eCK}$-secure key exchange protocol as the underlying primitive.

In the NAXOS protocol, [19], this is accomplished using what is now called the “NAXOS trick”: a “pseudo” ephemeral key $\widetilde{esk}$ is computed as the hash of the long-term key lsk and the actual ephemeral key esk: $\widetilde{esk} \leftarrow H(esk, lsk)$. The value $\widetilde{esk}$ is never stored, and thus in the eCK model the adversary must learn both esk and lsk in order to be able to compute $\widetilde{esk}$. The initiator must compute $\widetilde{esk} = H(esk, lsk)$ twice: once when sending its Diffie–Hellman ephemeral public key $g^{\widetilde{esk}}$, and once when computing the Diffie–Hellman shared secrets from the received values. This is to avoid storing a single value that, when compromised, can be used to compute the session key.

Moving to the leakage-resilient setting requires rethinking the NAXOS trick. Alawatugoda et al. [3] have proposed a generic construction of an after-the-fact leakage eCK ($(\cdot )\mathrm {AFL\text {-}eCK}$)-secure key exchange protocol, which uses a leakage-resilient NAXOS trick. The leakage-resilient NAXOS trick is obtained using a decryption function of an after-the-fact leakage-resilient public key encryption scheme. A concrete construction of a $\mathrm {BAFL\text {-}eCK}$-secure protocol is possible since there exists a bounded after-the-fact leakage-resilient public key encryption scheme which can be used to obtain the required leakage-resilient NAXOS trick, but it is not possible to construct a $\mathrm {CAFL\text {-}eCK}$-secure protocol since there is no continuous after-the-fact leakage-resilient scheme available. Therefore, an attempt to construct a $\mathrm {CAFL\text {-}eCK}$-secure key exchange protocol using the leakage-resilient NAXOS approach is not likely at this stage.

4.1 Description of Protocol $\mathrm {P1}$

Our aim is to construct an $\mathrm {eCK}$-secure key exchange protocol which does not use the NAXOS trick, but combines long-term secret keys and ephemeral secret keys to compute the session key, in a way that guarantees $\mathrm {eCK}$ security of the protocol. The protocol $\mathrm {P1}$ shown in Table 2 is a Diffie–Hellman-type [10] key agreement protocol. Let $\mathbb {G}$ be a group of prime order q and generator g. After exchanging the public values both principals compute a Diffie–Hellman-type shared secret, and then compute the session key using a random oracle $\mathrm {H}$. We use the random oracle because otherwise it is not possible to perfectly simulate the interaction between the adversary and the protocol, in a situation where the simulator does not know a long-term secret key of a protocol principal.

Table 2. Protocol $\mathrm {P1}$

In order to compute the session key, protocol $\mathrm {P1}$ combines four components ($Z_1 \leftarrow B^a$, $Z_3 \leftarrow Y^a$, $Z_4 \leftarrow Y^x$, $Z_2 \leftarrow B^x$) using the random oracle function $\mathrm {H}$. These four components cannot be recovered by the attacker without both the ephemeral and long-term secret keys of at least one protocol principal, which allows a proof of $\mathrm {eCK}$ security.

Though the design of protocol $\mathrm {P1}$ is quite straightforward, we could not find it given explicitly in the literature: most work on the design of eCK-secure protocols seeks to create more efficient protocols than this naive protocol, but the naive protocol is more appropriate for building into a leakage-resilient protocol.

Leakage-Resilient Rethinking of Protocol P1. Moving to the leakage-resilient setting requires rethinking the exponentiation computation in a leakage-resilient manner. Since there exist leakage-resilient encoding schemes and leakage-resilient refreshing protocols for them (Definitions 4 and 7) our aim is computing the required exponentiations in a leakage-resilient manner using the available leakage-resilient storage and refreshing schemes. For now we look at the $\mathrm {eCK}$ security of protocol $\mathrm {P1}$, and later in Sect. 5 we will look at the leakage-resilient modification to protocol $\mathrm {P1}$ in detail.

4.2 Security Analysis of Protocol P1

Theorem 2

If $\mathrm {H}$ is modeled as a random oracle and $\mathbb {G}$ is a group of prime order q and generator g, where the gap Diffie–Hellman $(\mathrm {GDH})$ problem is hard, then protocol $\mathrm {P1}$ is secure in the $\mathrm {eCK}$ model.

Let $\mathcal {U}=\{U_1,\dots ,U_{N_P}\}$ be a set of $N_P$ parties. Each party $U_i$ owns at most $N_S$ number of protocol sessions. Let $\mathcal {A}$ be an adversary against protocol $\mathrm {P1}$. Then, $\mathcal {B}$ is an algorithm which is constructed using the adversary $\mathcal {A}$, against the $\mathrm {GDH}$ problem such that the advantage of $\mathcal {A}$ against the $\mathrm {eCK}$-security of protocol $\mathrm {P1}$, $\mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}$ is:

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}} (\mathcal {A})\le \max \Big ({N_P^2 N_S^2}\big ({\Pr }^{\mathrm {GDH}}_{g,q} (\mathcal {B})\big ), {N_P^2}\big ({\Pr }^{\mathrm {GDH}}_{g,q} (\mathcal {B})\big ),\quad {N_P^2 N_S}\big ({\Pr }^{\mathrm {GDH}}_{g,q} (\mathcal {B})\big ),\\ {N_P^2 N_S}\big ({\Pr }^{\mathrm {GDH}}_{g,q} (\mathcal {B})\big ),{N_P^2 N_S}\big ({\Pr }^{\mathrm {GDH}}_{g,q} (\mathcal {B})\big ), {N_P^2}\big ({\Pr }^{\mathrm {GDH}}_{g,q} (\mathcal {B})\big )\Big ). \end{aligned}$$

Proof Sketch: Let $\mathbf {A}$ denote the event that $\mathcal {A}$ wins the $\mathrm {eCK}$ challenge. Let $\mathbf {H}$ denote the event that $\mathcal {A}$ queries the random oracle $\mathrm {H}$ with $(\mathrm {CDH}(A^*,B^*),\mathrm {CDH}(B^*,X^*), \mathrm {CDH}(A^*,Y^*), \mathrm {CDH}(X^*,Y^*), \textit{initiator}, X, \textit{responder}, Y)$, where $A^*$, $B^*$ are the long-term public-keys of the two partners to the test session, and $X^*$, $Y^*$ are their ephemeral public keys for this session. Note that when $A=g^a,B=g^b, \mathrm {CDH}(A,B)=g^{ab}$; also initiator is the initiator of the session and responder is the responder of the session.

$$\begin{aligned} \Pr (\mathbf {A}) \le \Pr (\mathbf {A} \wedge \mathbf {H}) + \Pr (\mathbf {A} \wedge \mathbf {\bar{H}}). \end{aligned}$$

Without the event $\mathbf {H}$ occurring, the session key given as the answer to the $\mathtt {Test}$ query is random-looking to the adversary, and therefore $\Pr (\mathbf {A} | \mathbf {\bar{H}}) = \frac{1}{2}$. $\Pr (\mathbf {A} \wedge \mathbf {\bar{H}}) = \Pr (\mathbf {A} | \mathbf {\bar{H}}) \Pr (\mathbf {\bar{H}})$, and therefore $\Pr (\mathbf {A} \wedge \mathbf {\bar{H}}) \le \frac{1}{2}$. Hence,

$$\begin{aligned} \Pr (\mathbf {A}) \le \frac{1}{2} + \Pr (\mathbf {A} \wedge \mathbf {H}), \end{aligned}$$

that is $\Pr (\mathbf {A} \wedge \mathbf {H}) = \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}(\mathcal {A})$. Henceforth, the event $(\mathbf {A} \wedge \mathbf {H})$ is denoted as $\mathbf {A^*}$.

Note 1

Let $\mathcal {B}$ be an algorithm against a $\mathrm {GDH}$ challenger. $\mathcal {B}$ receives $L=g^\ell , W=g^w$ as the $\mathrm {GDH}$ challenge and $\mathcal {B}$ has access to a $\mathrm {DDH}$ oracle, which outputs 1 if the input is a tuple of $(g^{\alpha },g^{\beta },g^{\alpha \beta })$. $\varOmega : \mathbb {G} \times \mathbb {G} \rightarrow \mathbb {G}$ is a random function known only to $\mathcal {B}$, such that $\varOmega (\varPhi ,\varTheta )=\varOmega (\varTheta ,\varPhi )$ for all $\varPhi ,\varTheta \in \mathbb {G}$. $\mathcal {B}$ will use $\varOmega (\varPhi ,\varTheta )$ as $\mathrm {CDH}(\varPhi ,\varTheta )$ in situations where $\mathcal {B}$ does not know $\log _{g} \varPhi$ and $\log _g \varTheta$. Except with negligible probability, $\mathcal {A}$ will not recognize that $\varOmega (\varPhi ,\varTheta )$ is being used as $\mathrm {CDH}(\varPhi ,\varTheta )$.

We construct the algorithm $\mathcal {B}$ using $\mathcal {A}$ as a sub-routine. $\mathcal {B}$ receives $L=g^\ell , W=g^w$ as the $\mathrm {GDH}$ challenge. We consider the following mutually exclusive events, under two main cases:

• 1. A partner to the test session exists: the adversary is allowed to corrupt both principals or reveal ephemeral keys from both sessions of the test session.

  • (a) Adversary corrupts both the owner and partner principals to the test session - Event $\mathbf {E_{1a}}$

  • (b) Adversary corrupts neither owner nor partner principal to the test session - Event $\mathbf {E_{1b}}$

  • (c) Adversary corrupts the owner to the test session, but does not corrupt the partner to the test session - Event $\mathbf {E_{1c}}$

  • (d) Adversary corrupts the partner to the test session, but does not corrupt the owner to the test session - Event $\mathbf {E_{1d}}$

• 2. A partner to the test session does not exist: the adversary is not allowed to corrupt the intended partner principal to the test session.

  • (a) Adversary corrupts the owner to the test session - Event $\mathbf {E_{2a}}$

  • (b) Adversary does not corrupt the owner to the test session - Event $\mathbf {E_{2b}}$

In any other situation the test session is no longer fresh. If event $\mathbf {A^*}$ happens at least one of the following event should happen.

$$\begin{aligned}{}[(\mathbf {E_{1a} \wedge A^*}),(\mathbf {E_{1b} \wedge A^*}),(\mathbf {E_{1c} \wedge A^*}),(\mathbf {E_{1d} \wedge A^*}),(\mathbf {E_{2a} \wedge A^*}),(\mathbf {E_{2b} \wedge A^*})] \end{aligned}$$

Hence,

$$\begin{aligned} \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}} \le \max&\Big (\Pr (\mathbf {E_{1a} \wedge A^*}),\Pr (\mathbf {E_{1b} \wedge A^*}),\Pr (\mathbf {E_{1c} \wedge A^*}),\\&\quad \Pr (\mathbf {E_{1d} \wedge A^*}),\Pr (\mathbf {E_{2a} \wedge A^*}),\Pr (\mathbf {E_{2b} \wedge A^*})\Big ). \end{aligned}$$

Complete security analysis of each event is available in the full version of this paper [2].    $\square$

5 Protocol $\mathrm {P2}$: A Leakage-Resilient Version of $\mathrm {P1}$

Protocol $\mathrm {P1}$ is an $\mathrm {eCK}$-secure key exchange protocol (Theorem 2). The $\mathrm {eCK}$ model considers an environment where partial information leakage does not take place. Following the concept that only computation leaks information, we now assume that the leakage of long-term secret keys happens when computations are performed using them. Then, instead of the non-leakage $\mathrm {eCK}$ model which we used for the security proof of protocol $\mathrm {P1}$, we consider the $\mathrm {CAFL\text {-}eCK}$ model which additionally allows the adversary to obtain continuous leakage of long-term secret keys.

Our idea is to perform the computations which use long-term secret keys (exponentiation operations) in such a way that the resulting leakage from the long-term secrets should not leak sufficient information to reveal them to the adversary. To overcome that challenge we use a leakage-resilient storage scheme and a leakage-resilient refreshing protocol, and modify the architecture of protocol $\mathrm {P1}$, in such a way that the secret keys s are encoded into two portions $s_L,s_R$, Exponentiations are computed using two portions $s_L,s_R$ instead of directly using s, and the two portions $s_L,s_R$ are being refreshed continuously. Thus, we add leakage resiliency to the $\mathrm {eCK}$-secure protocol $\mathrm {P1}$ and construct protocol $\mathrm {P2}$ such that it is leakage-resilient and $\mathrm {eCK}$-secure.

Obtaining Leakage Resiliency by Encoding Secrets. In this setting we encode a secret s using an $\mathrm {Encode}$ function of a leakage-resilient storage scheme $\varLambda =(\mathrm {Encode},\mathrm {Decode})$. So the secret s is encoded as $(s_L,s_R) \leftarrow \mathrm {Encode}(s)$. As mentioned in the Definition 2.4.1 the leakage-resilient storage scheme randomly chooses $s_L$ and then computes $s_R$ such that $s_L \cdot s_R=s$. We define the tuple leakage parameter $\varvec{\lambda }=(\lambda _1,\lambda _2)$ as follows: $\varvec{\lambda }$-limited adversary $\mathcal {A}$ sends a leakage function $\mathbf {f}=(f_{1j},f_{2j})$ and obtains at most $\lambda _1,\lambda _2$ amount of leakage from each of the two encodings of the secret s respectively: $f_{1j}(s_L)$ and $f_{2j}(s_R)$.

As mentioned in Definition 7, the leakage-resilient storage scheme can continuously refresh the encodings of the secret. Therefore, after executing the refreshing protocol it outputs new random-looking encodings of the same secret. So for the ${\varvec{\lambda }}$-limited adversary again the situation is as before. Thus, refreshing the encodings will help to obtain leakage resilience over a number of protocol executions.

The computation of exponentiations is also split into two parts. Let $\mathbb {G}$ be a group of prime order q with generator g. Let $s\xleftarrow {\$}\mathbb {Z}_q^*$ be a long-term secret key and $E=g^e$ be a received ephemeral value. Then, the value Z needs to be computed as $Z\leftarrow E^s$. In the leakage-resilient setting, in the initial setup the secret key is encoded as $s_L,s_R\leftarrow \mathrm {Encode}_{\mathbb {Z}^*_{q}}^{n,1}(s)$. So the vector $s_L = ({s_L}_1, \cdots , {s_L}_n)$ and the vector $s_R = ({s_R}_1, \cdots , {s_R}_n)$ are such that $s={s_L}_1 {s_R}_1+ \cdots + {s_L}_n {s_R}_n$. Then the computation of $E^s$ can be performed as two component-wise computations as follows: compute the intermediate vector $T \leftarrow E^{s_L}=(E^{{s_L}_1},\cdots , E^{{s_L}_n})$ and then compute the element $Z \leftarrow T^{s_R}=E^{{s_L}_1{s_R}_1}E^{{s_L}_2{s_R}_2}\cdots E^{{s_L}_1{s_R}_1}= E^{{s_L}_1{s_R}_1 +\cdots +{s_L}_n {s_R}_n} = E^s$.

5.1 Description of Protocol $\mathrm {P2}$

Using the above ideas, by encoding the secret using a leakage-resilient storage scheme, and refreshing the encoded secret using a refreshing protocol, it is possible to hide the secret from a $\varvec{\lambda }$-limited adversary. Further, it is possible to successfully compute the exponentiation using the encoded secrets. We now use these primitives to construct a $\mathrm {CAFL\text {-}eCK}$-secure key exchange protocol, using an $\mathrm {eCK}$-secure key exchange protocol as an underlying primitive.

Let $\varLambda _{\mathbb {Z}_q^*}^{n,1}=(\mathrm {Encode}_{\mathbb {Z}^*_{q}}^{n,1},\mathrm {Decode}_{\mathbb {Z}^*_{q}}^{n,1})$ be the leakage-resilient storage scheme which is used to encode secret keys and $\mathrm {Refresh}^{n,1}_{\mathbb {Z}^*_{q}}$ be the $(\ell ,\varvec{\lambda },\epsilon )$-secure leakage-resilient refreshing protocol of $\varLambda _{\mathbb {Z}^*_q}^{n,1}$.

As we can see, the obvious way of key generation (initial setup) in a protocol principal of this protocol is as follows: first pick $a \xleftarrow {\$} \mathbb {Z}_{q}^*$ as the long-term secret key, then encode the secret key as $(a_L^0,a_R^0) \leftarrow \mathrm {Encode}_{\mathbb {Z}^*_{q}}^{n,1}(a)$, then compute the long-term public key $A=g^a$ using the two encodings $(a_L^0,a_R^0)$, and finally erase a from the memory. The potential threat to that key generation mechanism is that even though the long-term secret key a is erased from the memory, it might not be properly erased and can be leaked to the adversary during the key generation. In order to avoid such a vulnerability, we randomly picks two values $a_L^0\xleftarrow {\$}(\mathbb {Z}_q^*)^n \backslash \{(0^n)\}$, $a_R^0\xleftarrow {\$}(\mathbb {Z}_q^*)^{n \times 1} \backslash \{(0^{n \times 1})\}$ and use them as the encodings of the long-term secret key a of a protocol principal. As explained earlier, we use $a_L^0, a_R^0$ to compute the corresponding long-term public key A in two steps as $a' \leftarrow g^{a_L^0}$ and $A \leftarrow a'^{a_R^0}$. Thus, it is possible to avoid exposing the un-encoded secret key a at any point of time in the key generation and hence avoid leaking directly from a at the key generation step. Further, the random vector $a_L^0$ is multiplied with the random vector $a_R^0$, such that $a=a_L^0 \cdot a_R^0$, which will give a random integer a in the group $\mathbb {Z}_{q}^*$. Therefore, this approach is same as picking $a \xleftarrow {\$} \mathbb {Z}_{q}^*$ at first and then encode, but in the reverse order. During protocol execution both $a_L^0,a_R^0$ are continuously refreshed and refreshed encodings $a_L^j, a_R^j$ are used to exponentiation computations.

Table 3 shows protocol $\mathrm {P2}$. In this setting leakage of a long-term secret key does not happen directly from the long-term secret key itself, but from the two encodings of the long-term secret key (the leakage function $\mathbf {f}=(f_{1j},f_{2j})$ directs to the each individual encoding). During the exponentiation computations and the refreshing operation collectively at most $\varvec{\lambda }=(\lambda _1,\lambda _2)$ leakage is allowed to the adversary from each of the two portions independently. Then, the two portions of the encoded long-term secret key are refreshed and in the next protocol session another $\varvec{\lambda }$-bounded leakage is allowed. Thus, continuous leakage is allowed.

Table 3. Concrete construction of Protocol $\mathrm {P2}$

5.2 Security Analysis of Protocol $\mathrm {P2}$

Theorem 3

If the underlying refreshing protocol $\mathrm {Refresh}_{\mathbb {Z}^*_{q}}^{n,1}$ is $(\ell ,\varvec{\lambda },\epsilon )$-secure leakage-resilient refreshing protocol of the leakage-resilient storage scheme $\varLambda _{\mathbb {Z}_q^*}^{n,1}$ and the underlying key exchange protocol $\mathrm {P1}$ is $\mathrm {eCK}$-secure key exchange protocol, then protocol $\mathrm {P2}$ is $\varvec{\lambda }$-$\mathrm {CAFL\text {-}eCK}$-secure.

Let $\mathcal {A}$ be an adversary against the key exchange protocol $\mathrm {P2}$. Then the advantage of $\mathcal {A}$ against the $\mathrm {CAFL\text {-}eCK}$-security of protocol $\mathrm {P2}$ is:

$$\begin{aligned} \mathrm {Adv}^{\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}}_{\mathrm {P2}}(\mathcal {A})\le N_P\Big ( \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}(\mathcal {A}) + \epsilon \Big ). \end{aligned}$$

Proof

The proof proceeds by a sequence of games.

• Game 1. This is the original game.

• Game 2. Same as Game 1 with the following exception: before $\mathcal {A}$ begins, an identity of a random principal $U^*\xleftarrow {\$} \{U_1,\dots ,U_{N_P}\}$ is chosen. Challenger expects that the adversary will issue the $\mathtt {Test}$ for a session which involves the principal $U^*$ ($\varPi ^{\cdot }_{U^*,\cdot }$ or $\varPi ^{\cdot }_{\cdot ,U^*}$). If not the challenger aborts the game.

• Game 3. Same as Game 2 with the following exception: challenger picks a random $s\xleftarrow {\$}\mathbb {Z}_{q}^*$ and uses encodings of s to simulate the adversarial leakage queries $\mathbf {f}=(f_{1j},f_{2j})$ of the principal $U^*$.

We now analyze the adversary’s advantage of distinguishing each game from the previous game. Let $\mathrm {Adv}_{\text {Game }x}(\mathcal {A})$ denote the advantage of the adversary $\mathcal {A}$ winning Game x.

Game 1 is the original game. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 1}}(\mathcal {A}) = \mathrm {Adv}^{\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}}_{\mathrm {P2}}(\mathcal {A}). \end{aligned}$$

(1)

Game 1 and Game 2. The probability of Game 2 to be halted due to incorrect choice of the test session is $1-\frac{1}{N_P}$. Unless the incorrect choice happens, Game 2 is identical to Game 1. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 2}}(\mathcal {A}) = \frac{1}{N_P} \mathrm {Adv}_{\text {Game 1}}(\mathcal {A}). \end{aligned}$$

(2)

Game 2 and Game 3. We construct an algorithm $\mathcal {B}$ against a leakage-resilient refreshing protocol challenger of $\mathrm {Refresh}_{\mathbb {Z}^*_{q}}^{n,1}$, using the adversary $\mathcal {A}$ as a subroutine.

The $(\ell ,\varvec{\lambda },\epsilon )$-$\mathrm {Refresh}_{\mathbb {Z}^*_{q}}^{n,1}$ refreshing protocol challenger chooses $s_0,s_1\xleftarrow {\$}\mathbb {Z}_{q}^*$ and sends them to the algorithm $\mathcal {B}$. Further, the refreshing protocol challenger randomly chooses $s\xleftarrow {\$} \{s_0,s_1\}$ and uses s as the secret to compute the leakage from encodings of s. Let $\varvec{\lambda }=(\lambda _1,\lambda _2)$ be the leakage bound and the refreshing protocol challenger continuously refresh the two encodings of the secret s.

When the algorithm $\mathcal {B}$ gets the challenge of $s_0,s_1$ from the refreshing protocol challenger, $\mathcal {B}$ uses $s_0$ as the secret key of the protocol principal $U^*$ and computes the corresponding public key. For all other protocol principals $\mathcal {B}$ sets secret/public key pairs by itself. Using the setup keys, $\mathcal {B}$ computes answers to all the queries from $\mathcal {A}$ and simulates the view of $\mathrm {CAFL\text {-}eCK}$ challenger of protocol $\mathrm {P2}$. $\mathcal {B}$ computes the leakage of secret keys by computing the adversarial leakage function $\mathbf {f}$ on the corresponding secret key (encodings of secret key), except the secret key of the protocol principal $U^*$. In order to obtain the leakage of the secret key of $U^*$, algorithm $\mathcal {B}$ queries the refreshing protocol challenger with the adversarial leakage function $\mathbf {f}$, and passes that leakage to $\mathcal {A}$.

If the secret s chosen by the refreshing protocol challenger is $s_0$, the leakage of the secret key of $U^*$ simulated by $\mathcal {B}$ (with the aid of the refreshing protocol challenger) is the real leakage. Then the simulation is identical to Game 2. Otherwise, the leakage of the secret key of $U^*$ simulated by $\mathcal {B}$ is a leakage of a random value. Then the simulation is identical to Game 3. Hence,

$$\begin{aligned} |\mathrm {Adv}_{\text {Game 2}}(\mathcal {A}) - \mathrm {Adv}_{\text {Game 3}}(\mathcal {A})| \le \epsilon . \end{aligned}$$

(3)

Game 3. Since the leakage is computed using a random s value, the adversary $\mathcal {A}$ will not get any advantage due to the leakage. Therefore, the advantage $\mathcal {A}$ will get is same as the advantage that $\mathcal {A}$ has against $\mathrm {eCK}$ challenger of protocol $\mathrm {P1}$. Because both $\mathrm {P1}$ and $\mathrm {P2}$ are effectively doing the same computation, regardless of the protocol $\mathrm {P2}$, and with no useful leakage the $\mathrm {CAFL\text {-}eCK}$ model is same as the $\mathrm {eCK}$ model. Hence,

$$\begin{aligned} \mathrm {Adv}_{\text {Game 3}}(\mathcal {A})= \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}(\mathcal {A}). \end{aligned}$$

(4)

We find,

$$\begin{aligned} \mathrm {Adv}^{\varvec{\lambda }-\mathrm {CAFL\text {-}eCK}}_{\mathrm {P2}}(\mathcal {A})\le N_P\Big ( \mathrm {Adv}^{\mathrm {eCK}}_{\mathrm {P1}}(\mathcal {A}) + \epsilon \Big ). \end{aligned}$$

   $\square$

5.3 Leakage Tolerance of Protocol $\mathrm {P2}$

The order of the group $\mathbb {G}$ is q. Let $m=1$ in the leakage-resilient storage scheme $\varLambda _{\mathbb {Z}^*_q}^{n,1}$. According to the Lemma 1, if $m<n/20$, then the leakage parameter for the leakage-resilient storage scheme is $\varvec{\lambda }_{\varLambda }=(0.3 n \log q,0.3 n \log q)$. Let $n=21$, then $\varvec{\lambda }_{\varLambda }= (6.3 \log q, 6.3 \log q)$ bits. According to the Theorem 1, if $m/3\le n$ and $n\ge 16$, the refreshing protocol $\mathrm {Refresh}_{\mathbb {Z}^*_{q}}^{n,1}$ of the leakage-resilient storage scheme $\varLambda _{\mathbb {Z}_q^*}^{n,1}$ is tolerant to (continuous) leakage up to $\varvec{\lambda }_{\mathrm {Refresh}}=\varvec{\lambda }_{\varLambda }/2=(3.15 \log q,3.15 \log q)$ bits, per occurrence.

When a secret key s (of size $\log q$ bits) of protocol $\mathrm {P2}$ is encoded into two parts, the left part $s_L$ will be $n \cdot \log q = 21 \log q$ bits and the right part $s_R$ will be $n \cdot 1 \cdot \log q=21 \log q$ bits. For a tuple leakage function $\mathbf {f}=(f_{1j},f_{2j})$ (each leakage function $f_{(\cdot )}$ for each of the two parts $s_L$ and $s_R$), there exists a tuple leakage bound $\varvec{\lambda }=(\lambda ,\lambda )$ for each leakage function $f_{(\cdot )}$, such that $\lambda =3.15 \log q$ bits, per occurrence, which is $\frac{3.15 \log q}{21 \log q}\times 100\,\%=15\,\%$ of the size of a part. The overall leakage amount is unbounded since continuous leakage is allowed.

6 Conclusion

In this paper we answered that open problem of constructing a concrete $\mathrm {CAFL\text {-}eCK}$ secure key exchange protocol by using a leakage-resilient storage scheme and its refreshing protocol. The main technique used to achieve after-the-fact leakage resilience is encoding the secret key into two parts and only allowing the independent leakage from each part. As future work it is worthwhile to investigate whether there are other techniques to achieve after-the-fact leakage resilience, rather than encoding the secret into parts. Moving to the standard model is another possible research direction. Strengthening the security model, by not just restricting to the independent leakage from each part, would be a more challenging research direction.