Standard model leakage-resilient authenticated key exchange using inner-product extractors

Abstract

With the development of side-channel attacks, a necessity arises to invent authenticated key exchange protocols in a leakage-resilient manner. Constructing authenticated key exchange protocols using existing cryptographic schemes is an effective method, as such construction can be instantiated with any appropriate scheme in a way that the formal security argument remains valid. In parallel, constructing authenticated key exchange protocols that are proven to be secure in the standard model is more preferred as they rely on real-world assumptions. In this paper, we present a Diffie–Hellman-style construction of a leakage-resilient authenticated key exchange protocol, that can be instantiated with any $\text {CCLA2}$-secure public-key encryption scheme and a function from the pseudo-random function family. Our protocol is proven to be secure in the standard model assuming the hardness of the decisional Diffie–Hellman problem. Furthermore, it is resilient to continuous partial leakage of long-term secret keys, that happens even after the session key is established, while satisfying the security features defined by the $\text {eCK}$ security model.

Appendices

Appendix A: Preliminaries

1.1 A.1 Leakage model

We frequently borrow notions for the leakage model from Dziembowski and Faust [18].

Leakage game Assume that secret key is stored in the memory as two encoded parts, say L and $R \in \{ 0, 1\}^s$, and an adversary ${\mathcal {A}}$ wants to learn information from L and R. For a positive integer $\lambda$, we define $\lambda$-leakage game between an adaptive adversary ${\mathcal {A}}$, called $\lambda$-limited adversary, and a leakage oracle $\varLambda (L, R)$ as follows: the adversary queries two adaptively-chosen leakage functions $(f_1, f_2)$ to the oracle $\varLambda (L, R)$. Then the oracle replies with $f_1(L)$ and $f_2(R)$ with restriction that the adversary cannot learn more than $\lambda$-bits from each L and R at the end of the game. We denote $Out( {\mathcal {A}}, \varLambda (L, R) )$ by the output of this game. Moreover, the information from L and R are leaked independently from each other.

Leakage from computations We follow the axiom “only computations leak information" and assume that only computations involving L or R leak their information to the adversary. This can be described in the following setting.

Consider a two-party protocol between the parties $P_L$ and $P_R$. Initially, the party $P_L$ (respectively, $P_R$) is given the input L (resp. R) and at the end of the protocol each party have the results $L'$ and $R'$, respectively. The execution of the protocol proceeds in rounds. In each round, one party (owner) computes a message and send it to the other. The message may be computed from owner’s input (eg. L or R), randomness chosen by the owner, and the received message from the earlier rounds. In the setting that only computation leaks information, the computations carried out by $P_L$ (resp. $P_R$) with the initial state L (resp. R) in each round may leak information on L (resp. R) independently from R (resp. L). Precisely, the adversary ${\mathcal {A}}$ adaptively chooses two leakage functions $(f_1^j,f_2^j)$ and obtains $f_1^j(L)$ and $f_2^j(R)$ from each j-th round in the execution of the protocol. At this time, the adversary is allowed to play the $\lambda$-leakage game with access to the leakage oracle $\varLambda ( (L, \rho _L, M_L ) ; ( R, \rho _R, M_R ) )$, where $\rho _x$ is the randomness used by $x \in \{L, R \}$ and $M_x$ is the previously received message by user $x \in \{ L, R \}$ in the execution of the protocol. We sometimes omit $\rho _x$ or $M_x$ when they are obviously null from the context.

1.2 A.2 Leakage-resilient storage scheme and it’s refreshing protocol

In Dziembowski and Faust [18], they used a leakage-resilient storage scheme to encode the secret key into two parts and a refreshing protocol to construct public-key cryptosystems secure against continuous partial leakage attacks.

1.2.1 A.2.1 Leakage-resilient storage

A leakage-resilient storage (LRS) $\varPhi = (\text {Encode}, \text {Decode})$ is a scheme to encode a message in ${\mathcal {M}}$, where $\text {Encode}: {\mathcal {M}} \rightarrow {\mathcal {L}} \times {\mathcal {R}}$ is a probabilistic polynomial-time function and $\text {Decode}: {\mathcal {L}} \times {\mathcal {R}} \rightarrow {\mathcal {M}}$ is a deterministic, polynomial-time function satisfying $\text {Decode}( \text {Encode}(S) ) = S$ for any $S \in {\mathcal {M}}$.

An LRS $\varPhi$ is called $(\lambda , \epsilon )$-secure if for any $S, S' \in {\mathcal {M}}$ and any $\lambda$-limited adversary ${\mathcal {A}}$, we have

$$\begin{aligned} \varDelta ( Out( {\mathcal {A}}, \varLambda (L, R) ), Out( {\mathcal {A}}, \varLambda (L', R') ) ) \le \epsilon , \end{aligned}$$

where $(L, R) {:= } \text {Encode}(S)$ and $(L', R') {:= } \text {Encode}(S')$. Here, $\varDelta$ denotes the statistical distance.

In Dziembowski and Faust [18], they use the fact that the LRS from inner product is $(\lambda , \epsilon )$-secure for some $\lambda$ and $\epsilon >0$. Precisely, for a field ${\mathbb {F}}$, an LRS $\varPhi _{{\mathbb {F}}}^{n, m} = (\text {Encode}_{{\mathbb {F}} }^{n, m} , \text {Decode}_{{\mathbb {F}} }^{n, m} )$ is defined as follows:

• $\text {Encode}_{{\mathbb {F}} }^{n, m}(S)$ chooses $L \leftarrow {\mathbb {F}}^n \backslash \{0^n\}$ and samples $R \leftarrow {\mathbb {F}}^{n \times m}$ such that $L \cdot R = S$.

• $\text {Decode}_{{\mathbb {F}} }^{n, m}(L, R)$ computes $L \cdot R = S$.

Corollary 1

[18] Suppose $| {\mathbb {F}} | = \varOmega (n)$ and $m < n/20$, then the LRS $\varPhi _{{\mathbb {F}}}^{n, m}$ is a $( 0.3 | {\mathbb {F}}^n | , \epsilon )$-secure LRS, where $\epsilon$ is negligible in the statistical security parameter $n \in {\mathbb {N}}$.

1.2.2 A.2.2 Refreshing protocol

It is obvious that the above LRS scheme is not secure, if we allow an adversary to obtain leakage information continuously from L and R. To prevent this obstacle, Dziembowski and Faust [18] introduced a refreshing protocol $\text {Refresh}$ of an LRS $\varPhi$. The main idea is to refresh the encoded secret (L, R) securely to a newly encoded value $(L', R')$ so that it does not reveal enough information to recover the secret key even when an $\lambda$-limited adversary can observe the leakage continuously from the refreshing protocol.

Precisely, a refreshing protocol $(L', R') \leftarrow \text {Refresh}(L , R)$ is a two-party protocol between $P_L$ and $P_R$ holding L and R respectively. At the end of the protocol, each party outputs $L'$ and $R'$ respectively satisfying $\text {Decode}(L, R) = \text {Decode}(L', R')$.

Let $\text {Refresh}$ a refreshing protocol, $\varPhi = (\text {Encode}, \text {Decode})$ an LRS, ${\mathcal {A}}$ an $\lambda$-limited adversary, $\ell \in {\mathbb {N}}$ and $S \in {\mathcal {M}}$. We consider the following experiments $\text {Exp}_{(\text {Refresh}, \varPhi )} ({\mathcal {A}}, S, \ell )$:

• For a secret S, encode it by $(L^0, R^0) \leftarrow \text {Encode}(S)$.

• For $i=1$ to $\ell$, run ${\mathcal {A}}$ against the refreshing protocol: ${\mathcal {A}} \leftrightarrows ( \text {Refresh}(L_{i-1}, R_{i-1}) \rightarrow (L_i, R_i) )$.

• Return $b \in \{0, 1\}$ output by ${\mathcal {A}}$.

As described in the previous paragraph, the leakage from each execution of the protocol is obtained via the leakage oracle $\varLambda ( (L_i , \rho _{L_i}, M_{L_i}) ; (R_i , \rho _{R_i} , M_{R_i} ) )$. Finally, the security of the refreshing protocol is defined by indistinguishability notion.

Definition 1

($A (\ell , \lambda , \epsilon _1)$-secure refreshing protocol [18]) For a LRS $\varPhi$ with message space ${\mathcal {M}}$ and $\ell \in {\mathbb {N}}$ number of leakage rounds, a refreshing protocol $\text {Refresh}$ is $(\ell , \lambda , \epsilon _1)$-secure, if for any $\lambda$-limited adversary ${\mathcal {A}}$ and any two secrets $S, S' \in {\mathcal {M}}$, we have

$$\begin{aligned} \varDelta ( \text {Exp}_{(\text {Refresh}, \varPhi ) } ({\mathcal {A}}, S, \ell ) , \text {Exp}_{(\text {Refresh}, \varPhi ) } ({\mathcal {A}}, S' , \ell ) ) \le \epsilon _1. \end{aligned}$$

Theorem 2

[18] Let $m/3 \le n$, $n \ge 16$ and $\ell \in {\mathbb {N}}$. Let n, m and ${\mathbb {F}}$ be such that $\varPhi _{{\mathbb {F}}}^{n, m}$ is $(\lambda , \epsilon )$-secure for some $\lambda , \epsilon >0$. Then the protocol $\text {Refresh}_{{\mathbb {F}}}^{n, m}$ is a $(\ell , \lambda /2-1, \epsilon ')$-secure refreshing protocol for $\varPhi _{{\mathbb {F}}}^{n, m}$ with $\epsilon ' = 2\ell | {\mathbb {F}} |^m ( 3 |{\mathbb {F}}|^m \epsilon + m |{\mathbb {F}}|^{-n-1} )$.

Definition 2

($A (\ell , \lambda , \epsilon _1)$-secure refreshing protocol with auxiliary information [18]) Let $Z \subset {\mathcal {M}}^m$ be an $m' < m$ dimensional affine subspace defined by W and Q. For a LRS $\varPhi$ with message space ${\mathcal {M}}$ and $\ell \in {\mathbb {N}}$, a refreshing protocol $\text {Refresh}$ is $(\ell , \lambda , \epsilon _1)$-secure with auxiliary information (W, Q), if for any $\lambda$-limited adversary ${\mathcal {A}}$ and any two secrets $S, S' \in {\mathcal {M}}$, we have,

$$\begin{aligned} \begin{aligned} \varDelta ( \text {Exp}^{\text {aux}}_{(\text {Refresh}, \varPhi ) } ({\mathcal {A}}, S, \ell ,W,Q ) , \text {Exp}^{\text {aux}}_{(\text {Refresh}, \varPhi ) } ({\mathcal {A}}, S' , \ell ,W,Q ) ) \le \epsilon _1. \end{aligned} \end{aligned}$$

Theorem 3

(Generalization of Theorem 1 [18]) Let $m/4 \le n$, $n \ge 16$ and $\ell \in {\mathbb {N}}$. Let (W, Q) be as above defining an $m' < m$ dimensional affine subspace Z. Let $n, m'$ and ${\mathbb {F}}$ be such that $\varPhi _{{\mathbb {F}}}^{n, m'}$ is $(\lambda , \epsilon )$-secure for some $\lambda , \epsilon >0$. Then the protocol $\text {Refresh}_{{\mathbb {F}}}^{n, m}$ is a $(\ell , \lambda /2-1,\epsilon ')$-secure refreshing protocol with auxiliary information defined by (W, Q) for $\varPhi _{{\mathbb {F}}}^{n, m}$ with $\epsilon ' = 2\ell | {\mathbb {F}} |^m ( 3 |{\mathbb {F}}|^{2m} \epsilon + m |{\mathbb {F}}|^{-n-1} )$.

Corollary 2

[18] Suppose $| {\mathbb {F}} | = \varOmega (n)$ and $m =o(n)$, then the $\text {Refresh}_{{\mathbb {F}}}^{n, m}$ is a $(\ell , 0.15n\log |{\mathbb {F}}|)-1,\epsilon _1)$-secure refreshing protocol for $\varPhi _{{\mathbb {F}}}^{n, m}$, where $\ell$ is a polynomial and $\epsilon _1$ is negligible in the statistical security parameter $n \in {\mathbb {N}}$.

1.3 A.3 Leakage-resilient CCA2-secure public-key encryption scheme

For security parameter k, a public-key encryption scheme $\text {PKE} = ( \text {KG}, \text {Enc}, \text {Dec})$ consists of the following algorithms.

• $(pk , sk) \leftarrow \text {KG}(1^k)$: It outputs a public/secret key pair.

• $c \leftarrow \text {Enc}(pk, m)$: A probabilistic polynomial-time algorithm that outputs $c = \text {Enc}(pk, m)$ with inputs a message m and the public key pk.

• $m = \text {Dec}(sk, c)$: A deterministic algorithm that decrypts the ciphertext c together with the secret key sk. We always have $m = \text {Dec}(sk, \text {Enc}(pk , m) )$.

The strongest security notion for public-key encryption scheme is security against adaptively-chosen-ciphertext attacks (CCA2-secure). In CCA2 attack against a public-key encryption scheme, the adversary who is given pk picks two messages $m_0, m_1$ and guesses $b \in \{ 0, 1 \}$ on input $c^* = \text {Enc}(pk, m_b)$ while the adversary is allowed to ask for the decryption of chosen-ciphertexts prior and after to seeing $c^*$.

In the setting that computation leaks information, it is natural to consider leakage information from the queries to the decryption oracle. This yields the following extension of CCA2-security against leakage attacks.

Definition 3

([18], Security against Chosen Ciphertext Leakage Attacks (CCLA2)) Let k be the security parameter. A public-key encryption scheme $\text {PKE} = (\text {KG}, \text {Enc}, \text {Dec})$ is $\text {CCLA2}$-secure if for any $\lambda '$-limited adversary ${\mathcal {A}}$ the probability that the experiment below outputs 1 is at most $1/2 + \texttt {negl}(k)$.

• 1. The challenger runs $(pk, sk) \leftarrow \text {KG}(1^k)$ and sends pk to ${\mathcal {A}}$.

• 2. The adversary ${\mathcal {A}}$ asks for the decryption of a ciphertext c learning at most $\lambda '$-bits of the current secret sk for each query: ${\mathcal {A}} \leftrightarrows ( \text {Dec}(sk, c) \rightarrow sk' )$. Set $sk {:= } sk'$ for the next round.

• 3. ${\mathcal {A}}$ outputs two messages, $m_0, m_1$, and sends them to the challenger.

• 4. The challenger computes $c^* \leftarrow \text {Enc}(pk, m_b)$ for $b \in \{0, 1\}$ and gives it to ${\mathcal {A}}$.

• 5. Repeat ${\mathcal {A}} \leftrightarrows ( \text {Dec}(sk, c) \rightarrow sk' )$ for $c \ne c^*$ learning at most $\lambda '$-bits of the current secret sk. Set $sk {:= } sk'$ for the next round.

• 6. ${\mathcal {A}}$ outputs $b' \in \{ 0, 1\}$. If $b = b'$, then output 1, otherwise output 0.

1.4 A.4 Pseudo-random functions

We now describe the security definition of pseudo-random functions according to Katz and Lindell [22].

Definition 4

(Pseudo-Random Functions) Let $F: \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^*$ be an efficient, length preserving, keyed function. We say F is a pseudo-random function if for all probabilistic polynomial-time adversaries ${\mathcal {A}}$, there exists a negligible function $\epsilon _{\text {PRF}}$ in the security parameter k such that:

$$\begin{aligned}\Big | \Pr [{\mathcal {A}}^{F(key,\cdot )}(1^k)=1] - \Pr [{\mathcal {A}}^{f_{\text {rnd}}(\cdot )}(1^k)=1] \Big | \le \epsilon _{\text {PRF}},\end{aligned}$$

where $key \in \{0,1\}^k$ is chosen uniformly at random an $f_{\text {rnd}}$ is chosen uniformly at random from the set of functions map** k-bit strings to k-bit strings.

Appendix B: Proof sketches of Lemmas 1 and 2

1.1 B.1 Proof sketch of Lemma 1

Proof

(Sketch) The proof is similar to that in Dziembowski and Faust [18]. The simulation is described as follows:

• 1. The simulator ${\mathcal {S}}$ is given the auxiliary information $\text {aux} = (R_1 + R_2)$, and given access to the leakage oracle $\varLambda (L^*, R^*)$. She sets $L = L^*$ and $R_1 = R^*$.

• 2. ${\mathcal {S}}$ simulates the leakage of L and $R_1$ using the leakage oracle $\varLambda (L^*, R^*)$.

• 3. The leakage of $R_2$ can be described from the relation $R_2=\text {aux} - R^*$. Therefore, ${\mathcal {S}}$ can perfectly simulate the leakage of $R_2$ using the leakage oracle $\varLambda (L^*, R^*)$ and the auxiliary value $\text {aux}$.

$\square$

1.2 B.2 Proof sketch of Lemma 2

Proof

(Sketch) Note that (W, A) defines a 1-dimensional subspace $Z \subset ({\mathbb {Z}}_q)^2$ that contains all the pairs $(a_1, a_2)$ that correspond to the public key A. For any $S,S' \in Z$ and any $(\lambda /2 -1 )$-limited adversary ${\mathcal {A}}$ we have by the Theorem 2 (Generalization of Theorem 1) of Dziembowski and Faust [18], for refreshing of $\varPhi _{{\mathbb {Z}}_q}^{n, 2}$ that,

$$\begin{aligned} \begin{aligned}&\varDelta ( \text {Exp}^{\text {aux}}_{\texttt{expRef}(B,(L, R))} ({\mathcal {A}}, S, \ell , W, A ) , \text {Exp}^{\text {aux}}_{\texttt{expRef}(B,(L, R)) } ({\mathcal {A}}, S' , \ell , W, A) ) \le \\&\quad 2 \ell p^6 (3 \epsilon + 2 p^{-n-5} ). \end{aligned} \end{aligned}$$

(18)

The above experiment addresses only the leakage from the refreshing operation of (L, R). In order to combine this with leakage from $\texttt{exp}$, we use the leakage simulation from Lemma 1. We can apply this lemma since (1)–Eq. (18) is shown by reduction to the $(\lambda ,\epsilon )$-security of $\varPhi _{{\mathbb {Z}}_q}^{n, 2}$ and (2)–$\text {aux}$ is known to the leakage simulator. This completes the proof of Lemma 2, by proving that $\epsilon _1$ is negligible in the statistical security parameter n. $\square$