Michel Abdalla

Sonia Belaïd

Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Sonia Abdalla

Belaid

Leakage-Resilient Symmetric Encryption via Re-keying ⋆

Keywords: leakage-resilience, symmetric encryption, re-keying, synchronization

In the paper, we study whether it is possible to construct an efficient leakage-resilient symmetric scheme using the AES block cipher. We aim at bridging the gap between the theoretical leakage-resilient symmetric primitives used to build encryption schemes and the practical schemes that do not have any security proof against side-channel adversaries. Our goal is to construct an as efficient as possible leakageresilient encryption scheme, but we do not want to change the cryptographic schemes already implemented. The basic idea consists in adding a leakage-resilient re-keying scheme on top of the encryption scheme and has been already suggested by Kocher to thwart differential power analysis techniques. Indeed, in such analysis, the adversary queries the encryption box and from the knowledge of the plaintext/ciphertext, she can perform a divide-and-conquer key recovery attack. The method consisting in changing the key for each or after a small number of encryption with the same key is known as re-keying. It prevents DPA adversaries but not SPA attacks which uses one single leakage trace. Here, we prove that using a leakage-resilient re-keying scheme on top of a secure encryption scheme in the standard model, leads to a leakage-resilient encryption scheme. The main advantage of the AES block cipher is that its implementations are generally heuristically-secure against SPA adversaries. This assumption is used in many concrete instantiations of leakage-resilient symmetric primitives. Consequently, if we use it and change the key for each new message block, the adversary will not be able to recover any key if the re-keying scheme is leakage-resilient. There is mainly two different techniques for re-keying scheme, either parallel or sequential, but if we want to avoid the adversary having access to many inputs/outputs, only the sequential method is possible. However, the main drawback of the latter technique is that in case of de-synchronization, many useless computations are required. In our re-keying scheme, we use ideas from the skip-list data structure to efficiently recover a specific key.

Introduction

Most of widely used cryptosystems are secure in the black-box model when the adversary is limited to the observation of the inputs and outputs. However, this model does not faithfully reflect the reality of embedded devices. Introduced in the nineties, a more realistic model in which the attacker can observe the physical leakage of the device has revealed a new class of attacks gathered around the term Side-Channel Analysis (SCA for short). These attacks exploit the dependence between sensitive values of an algorithm and the physical leakage of the device (time, power consumption, electromagnetic radiation, . . . ).

In order to avoid the large variety of side-channel attacks, many countermeasures have been proposed. Most of them are designed to thwart one specific attack. A widely used example is masking [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Goubin | DES and Differential Power Analysis (The "Duplication" Method)[END_REF][START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF]] that aims at protecting implementations against Differential Power Analysis (DPA) [START_REF] Paul | Differential Power Analysis[END_REF] but can be defeated by higher-order attacks [START_REF] Messerges | Using Second-Order Power Analysis to Attack DPA Resistant Software[END_REF]. However, over the last few years, significant efforts have been made to define generic models capturing physical attacks in order to provide guarantees of a generic security. Two main examples are the physically observable cryptography [START_REF] Micali | Physically Observable Cryptography (Extended Abstract)[END_REF] and leakage-resilient cryptography [START_REF] Dziembowski | Leakage-Resilient Cryptography[END_REF]. Several pseudorandom functions, generators and permutations have already been proposed in the latter [START_REF] Dodis | Leakage-Resilient Pseudorandom Functions and Side-Channel Attacks on Feistel Networks[END_REF][START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF][START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF][START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF][START_REF] Standaert | Leakage Resilient Cryptography in Practice. Towards Hardware-Intrinsic Security, Information Security and Cryptography[END_REF]. Unfortunately, these primitives are not always relevant to practice. They are often associated to large complexities and are sometimes constructed in a non realistic model in view of current embedded devices. Nevertheless and as stressed in [START_REF] Medwed | Towards Super-Exponential Side-Channel Security with Efficient Leakage-Resilient PRFs[END_REF], theoretical ideas proposed in the design of these primitives can be used to significantly improve the physical security of cryptographic primitives against side-channel attacks.

In this paper, we propose a more efficient and provably secure symmetric encryption based on fresh re-keying. This technique has first been investigated in [1] in the context of increasing the lifetime of a key and in [START_REF] Paul | Leak-resistant cryptographic indexed key update[END_REF] to thwart side channel attacks by updating regularly the secret key. The principle of rekeying is based on an inherent primitive that, given a master key and a public nonce, generates a new session key. Such schemes have already been designed [START_REF] Medwed | Fresh Re-keying: Security against Side-Channel and Fault Attacks for Low-Cost Devices[END_REF] but no security proof has been given. Here, we rather focus on a mode of operation provably secure in the leakage model. A first requirement for the security is to encrypt each block of message with a different session key. As formally described in [1], the session keys can be generated either from the same master key (in parallel by applying a pseudorandom function on the index with a part of the master key) or sequentially, using the previous session key to derive the current one. Although the choice of the model depends on the underlying primitive, the second one is more suited to avoid DPA as it changes the key at each execution in the re-keying part also. However, the sequential method faces a problem of efficiency when a client and a server need to resynchronize. For example, servers that operate with many clients (as in electronic cash applications) cannot precompute all the possible session keys. They have to derive them, that is operate as many operations as the difference of indices between the key they currently have and the key they need. As a result, the process of re-keying suffers from the time complexity of the number of similar operations required to obtain the correct session key.

Related Work. The first construction of leakage-resilient symmetric encryption has only been recently proposed in [START_REF] Hazay | Leakage-Resilient Cryptography from Minimal Assumptions[END_REF] by Hazay et al.. However, the main objective of the authors was to propose a generic scheme based on minimal assumptions and the efficiency was not their priority. There are several works on the construction of leakage-resilient symmetric primitives such as block ciphers or stream ciphers [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF][START_REF] Dodis | Leakage-Resilient Pseudorandom Functions and Side-Channel Attacks on Feistel Networks[END_REF][START_REF] Dziembowski | Leakage-Resilient Cryptography[END_REF]. One of the main assumptions to design such schemes is that AES implementations are heuristically secure against SPA [START_REF] Biryukov | Two New Techniques of Side-Channel Cryptanalysis[END_REF][START_REF] Schramm | A Collision-Attack on AES: Combining Side Channel-and Differential-Attack[END_REF][START_REF] Moradi | Statistical Tools Flavor Side-Channel Collision Attacks[END_REF][START_REF] Moradi | Correlation-Enhanced Power Analysis Collision Attack[END_REF][START_REF] Gérard | Unified and Optimized Linear Collision Attacks and Their Application in a Non-profiled Setting[END_REF] or AES can be implemented to be a leakage-resilient block cipher if the number of queries with the same key is small. Consequently, this block cipher is the main practical building block used by theoreticians to instantiate their constructions and namely in [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF], Pietrzak proposes to use AES(0 p) AES(1 p) for constructing a weak PRF with 2n bits of outputs. A weak PRF is a PRF when the adversary cannot choose the inputs but only has access to random evaluations of the function. Such weak PRF is a critical ingredient of the design of GGM (Goldreich, Goldwasser and Mical) leakage-resilient PRF [START_REF] Goldreich | How to construct random functions[END_REF] which is resistant for many queries and not only two. To construct a leakage-resilient block cipher, Faust et al. propose to use this PRF in a three Feistel rounds in [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF] but the overall construction has been shown to be inefficient by Bernstein at the CHES'12 rump session [START_REF] Daniel | Implementing "Practical leakage-resilient symmetric cryptography[END_REF]. The GGM construction is however very inefficient and in an effort improve it, Medwed, Standaert and Joux in [START_REF] Medwed | Towards Super-Exponential Side-Channel Security with Efficient Leakage-Resilient PRFs[END_REF] propose a version of the tree by considering byte rather than bit. They analyze the security of this variant with the AES block cipher and lead to the conclusion that AES is not well-suited for this purpose. Indeed, even though the adversary does not control the inputs, she can still efficiently recover the secret key of the first round byte after byte. A similar conclusion has been made by Jaffe in [START_REF] Jaffe | A first-order dpa attack against aes in counter mode with unknown initial counter[END_REF] on the AES-CTR mode of operation. Constructing a leakage-resilient PRF is a crucial issue since the construction of a leakage-resilient block-cipher as in [START_REF] Dodis | Leakage-Resilient Pseudorandom Functions and Side-Channel Attacks on Feistel Networks[END_REF][START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF] or a leakage-resilient stream-cipher require this primitive [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF]. It is an important problem to design leakage-resilient block ciphers but here, we avoid to consider it when building a practical leakage-resilient symmetric encryption.

Contributions. Our goal is to construct an efficient leakage-resilient symmetric encryption scheme using the AES block cipher without constructing a leakageresilient block cipher. Since AES is only secure if we encrypt a limited number of plaintexts with the same key, we need to regularly change the key. Therefore, re-keying appears to be an interesting solution as it was earlier proposed by Kocher in [START_REF] Paul | Leak-resistant cryptographic indexed key update[END_REF] to avoid DPA attacks, but here we want to prove that this idea leads to an efficient leakage-resilient symmetric encryption scheme. To this end, we need to construct an efficient re-keying scheme. However, to design such a scheme, one solution is to use a leakage-resilient PRF and we will be back to our initial problem since we want to use AES in an efficient leakage-resilient encryption scheme. Our first solution consists in showing that a leakage-resilient PRF combined with a block cipher is a leakage-resilient encryption scheme. To this end, we can use the GGM construction as proven by Faust et al. in [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF]. However, in order to build a more efficient scheme and to solve the synchronization problem, avoiding the computation of all the intermediate keys, we propose a new one. We show that we do not need a PRF to build a secure encryption scheme, but we only need a leakage-resilient re-keying scheme. To this end, we use similar ideas from the skip-list data structure [START_REF] Pugh | Skip Lists: A Probabilistic Alternative to Balanced Trees[END_REF] proposed by Pugh in the late eighties. In this list, one half of the main list elements are chosen randomly to constitute a new list and from this list, another smaller one are derived and so on using O(log n) stages with high probability if we have n elements. The idea to look for an element in this sorted list consists in beginning with the last floor and identifying the interval where the element is and recurse in the next floor up to identifying the element or finding that it is not in the list. On average, the running time is also O(log n) which is asymptotically as efficient as a random binary tree. Our problem is similar to finding an element in a sorted list since we have the index of the key we are looking for. It turns out that this construction serves the same purpose than the one proposed by Kocher in [START_REF] Paul | Leak-resistant cryptographic indexed key update[END_REF]. However, the latter does not share the same design mainly because of the multiple use of the same re-keying keys and suffers from the absence of security proof.

Organization. In Sect. 2, we give a theoretical background on leakage-resilient notions. Then, we describe in Sect. 3 our new leakage-resilient symmetric encryption. In Sect. 4, we provide the proof of our construction while in Sect. 5, we evaluate its efficiency in practice.

Theoretical Background

In this section, we introduce our security model inspired from most previous works [START_REF] Dziembowski | Leakage-Resilient Cryptography[END_REF][START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF][START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF]. We also formally define the functions we use in the following.

Notations

For the rest of the paper, we introduce some useful notations. In the following, the uppercase letters will be used to denote random variables and lowercase letters to denote their realization. Exceptions are made to define security parameters or sizes. We denote with R m,n the set of uniformly random functions from {0, 1} m to {0, 1} n . For a set X , we eventually write X Continuous Leakage. In the continuous leakage model, the attacker has access to an unlimited amount of leakage. There is only a few works on provable security against continuous side-channel attacks and most of them only target one specific attack like probing [START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF].

Leakage-Resilient Primitives. As in [START_REF] Dziembowski | Leakage-Resilient Cryptography[END_REF], we consider an adversary able to collect a bounded amount of leakage at each invocation of the primitive without being limited in the number of invocations. From the axiom "Only computation leaks" [START_REF] Micali | Physically Observable Cryptography (Extended Abstract)[END_REF], we assume that only the data involved in an invocation can leak in this invocation. We leave to the adversary the choice of the function f which will be used to compute the leakage. However there is no other choice than restricting the range of this function. Otherwise, the adversary could choose to learn the exact secret state S using the identity function: f (S) = S. Hence, we limit to the leakage functions with range {0, 1} λ , λ ≪ |S|. All the primitives which are secure under these conditions will be referred to as leakage-resilient primitives. Granular Leakage Resilience. In this model introduced in [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF], we consider the global cryptographic primitive as a combination of smaller blocks that leak independently. These blocks can be either different primitives or several invocations of the same primitive, following the works [START_REF] Dodis | Leakage-Resilient Pseudorandom Functions and Side-Channel Attacks on Feistel Networks[END_REF][START_REF] Standaert | Leakage Resilient Cryptography in Practice. Towards Hardware-Intrinsic Security, Information Security and Cryptography[END_REF][START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF]. Let us denote by τ i the state before step i. The adversary can choose a leakage function f i before step i and gets f i (τ i ) at the end of the step execution. In the following, we will omit the term granular but all the schemes will be proven secure under this model.

Non-adaptive Leakage-Resilience (naLR). In this paper and as in [START_REF] Dodis | Leakage-Resilient Pseudorandom Functions and Side-Channel Attacks on Feistel Networks[END_REF][START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF], we allow the attacker to choose a new leakage function per independent block and to learn its output. However, we require these leakage functions to be chosen nonadaptively, that is before obtaining any leakage or outputs. This model actually fits the reality since these functions entirely depend on the embedded devices.

Non-adaptive Function (na). Another relaxation is the notion of non-adaptive function, introduced in [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF] for PRFs. In this context, the adversary is expected to choose her input queries in advance, that is before seeing any leakage or output.

Definitions and Security Notions

Secure and efficient cryptosystems require functions which are indistinguishable from equivalent random objects and which require only a few amount of randomness. A widely used function which fills these criteria is the pseudorandom random function (PRF for short). To define the security notion of such a PRF F we consider a challenge oracle which is either the PRF F (K, .) instantiated with a uniformly random key K (with probability 1/2) or a uniformly random function R(.). As formalized in Definition 1, the PRF is secure if no adversary is able to distinguish both games with a significant advantage. Definition 1. A function F : {0, 1} k × {0, 1} m → {0, 1} n is a (ǫ, s, q)-secure PRF if for any adversary (or statistical test) A of size s that can make up to q disjoint queries to its challenge oracle, we have:

Adv prf F (A) = | IP K * ←{0,1} k [A(F (K, .)) = 1] -IP R←Rm,n [A(R(.)) = 1]| ǫ.
A weak PRF (wPRF) shares the same definition except that its inputs are chosen uniformly at random. Contrary to the PRFs and as proven in [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF], the wPRFs remain secure whenever they are used with the so-called low keys defined below.

Definition 2. A α-low key K ∈ {0, 1} k is a key with min-entropy equal to k-α:

∀x ∈ {0, 1} k , IP[K = x] 2 -(k-α) .
Both wPRFs and PRFs can be leakage-resilient secure, that are secure even if an adversary observes a bounded amount of leakage at each execution. This second security notion requires the introduction of a second oracle referred to as leakage oracle and denoted by F f (K, .). It returns both the output of the function F (K, X) and the corresponding leakage f (K, X) on an input query X.

Definition 3. A function F : {0, 1} k × {0, 1} m → {0, 1}
n is a (ǫ, s, q)-secure leakage-resilient PRF if for any adversary A of size at most s who can make up to q distinct queries to its two oracles, we have:

Adv lr prf F (A) = | IP K * ←{0,1} k [A(F (K, .), F f (K, .)) = 1] - IP R←Rm,n,K * ←{0,1} k [A(R(.), F f (K, .)) = 1]| ǫ.
Although they also provide pseudorandomness, encryption schemes are stronger notions than PRFs. Given the ciphertexts of two different messages, no adversary can decide with a significant confidence which ciphertext is related to which plaintext. In this paper, we focus on an equivalent security notion for encryption schemes introduced in [START_REF] Bellare | A Concrete Security Treatment of Symmetric Encryption[END_REF] and called the real-or-random indistinguishability. The security of an encryption scheme is then verified if no adversary can distinguish the encryption of a real query from the encryption of a random string.

Definition 4. An encryption scheme S : {0, 1} k × {0, 1} n → {0, 1} n is (ǫ, s, q)secure in the real-or-random sense, if any adversary A of size at most s who asks at most q distinct queries, has an advantage bounded as follows:

Adv enc S (A) = | IP K * ←{0,1} k [A(S K (.)) = 1] - IP K * ←{0,1} k [A(S K ($)) = 1]| ǫ
where $ represents a random string in {0, 1} n .

Let us now define the leakage-resilient security of an encryption scheme.This notion ensures that even with additional leakage, no adversary should be able to distinguish both games with a significant advantage. As for the PRFs, we consider a leakage oracle referred to as S f K (.) for a uniformly random key K. Definition 5. An encryption scheme S : {0, 1} k ×{0, 1} n → {0, 1} n is a (ǫ, s, q)secure leakage-resilient encryption scheme if any adversary A of size at most s who asks at most q distinct queries has an advantage bounded as follows:

Adv lr enc S (A) = | IP K * ←{0,1} k [A(S K (.), S f K (.)) = 1] - IP K * ←{0,1} k [A(S K ($), S f K (.)) = 1]| ǫ.
In the following, we will consider a function secure if the advantage of the attacker is negligible in the key size k and if s and q are superpolynomial in k.

Leakage-Resilient Symmetric Encryption Scheme

In this section, we propose to build a non-adaptive leakage-resilient symmetric encryption scheme. As suggested by Kocher in [START_REF] Paul | Leak-resistant cryptographic indexed key update[END_REF], this security can be achieved by key updates, also referred to as re-keying, combined with secure primitives. Following this design principle, we propose in a first part a construction based on a naLR naPRF and a block cipher which yields a naLR encryption scheme secure in the sense of Definition 5. In a second part, we focus on the instantiation of the inherent naLR naPRF. We start with the recent construction of [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF] since to the best of our knowledge, it is the most efficient proven one. Based on this construction, we try to improve the efficiency of the whole scheme in the context of re-synchronization. However through the improvements, we observe that the naLR naPRF is not a requirement to build a naLR encryption scheme. In fact, we introduce a new re-keying scheme which does not fulfil the properties of a PRF but surprisingly still yields a naLR encryption scheme. Furthermore, it improves significantly the efficiency of a sequential re-keying scheme when instantiated with the AES in the context of the synchronisation issue exhibited in Sect. 1. Eventually, we conclude the section by discussing the generation and the repartition of the public random values used in the whole encryption scheme.

Leakage-Resilient Encryption from a naLR naPRF

As outlined in [START_REF] Medwed | Towards Super-Exponential Side-Channel Security with Efficient Leakage-Resilient PRFs[END_REF], PRFs appear to be good candidates for integration in leakageresilient re-keying schemes. In this work, we show that a naLR naPRF F associated with a secure block cipher β (in the sense of PRF in Definition 1) yields a naLR encryption scheme. For this purpose, Theorem 1 is proven is Sect. 4.

Theorem 1. Let F denote a naLR naPRF and β a block cipher in the sense of PRF. Then the symmetric encryption scheme S F,β is a non-adaptive leakageresilient encryption scheme. The amount of leakage λ tolerated per time step depends on the inherent naLR naPRF:

λ ∈ O(log(1/ǫ F )).
The principle is as follows. From an initial secret key k and a public random value p, the PRF outputs a session key k ⋆ = F (k, p) that is further used by the block cipher for a single block encryption. Figure 1 illustrates this process.

Since each block is encrypted with a different secret key, the block cipher is not expected to be resistant against differential attacks.

Fig. 1: Non-adaptive leakage-resilient encryption scheme from a naLR naPRF.

Leakage-Resilient Encryption Scheme from a weak PRF

We have proposed the construction of a naLR encryption scheme from a naLR naPRF. Now we aim to instantiate this naLR naPRF in the most efficient way.

Since it is proven secure, we start with the naLR naPRF introduced in [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF]. We observe that it has likeable security features but it is not optimal in terms of efficiency since among all the nodes of the binary tree, only the leaves are finally exploited. As a consequence, we propose to improve the efficiency of the whole scheme by also using the intermediate nodes in a suitable order. A solution to benefit from the intermediate nodes is to slightly change the inherent wPRF. In [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF], this wPRF outputs 2n-bit values from n-bit inputs. In this paper, we refer to as φ the wPRF we use to compute n-bit values from n-bit values and as φ 2 (resp. φ 3 ) the concatenation of two (resp. three) invocations of φ. Instead of deriving two keys generally from two random public values of same size, we could directly use the wPRF φ 3 to derive three keys using one more random value. Among these three keys, two would still be used to derive the subsequent tree keys while the third one would be processed in the block cipher. Although this solution exploits the intermediate nodes, it requires a more expensive derivation since the intermediate wPRF is expected to generate one more key with an additional amount of randomness.

A more efficient option is to maintain the binary tree construction with the wPRF φ 2 and to use directly the intermediate keys in the block cipher. In this case, a third random value can be used with the intermediate key and the output of the block cipher can be bitwise added to the chosen message 3 . However, the re-keying scheme involved in this new construction is not a PRF anymore, since an adversary could easily take advantage of its outputs to derive the following keys. One may consequently expect the encryption scheme (we refer to as S R φ ,φ ) not to be secure anymore. Surprisingly, this intuition is wrong. By Theorem 2 that will be proven in Sect. 4, we show that we are still able to build a naLR symmetric encryption scheme with relaxed properties on the re-keying scheme. However unlike the previous scheme, the proof we established requires the block cipher to be the same primitive than the wPRF used to derive the keys.

Theorem 2. Let φ be a secure wPRF. Let R φ denote the re-keying scheme described above. Then S R φ ,φ is a naLR encryption scheme. The amount of leakage λ tolerated per time step depends on φ: λ = O(log(1/ǫ φ )). Now that we have presented the security aspects when exploiting all the nodes of the binary tree, we still have to fix a suitable order in the nodes to be as efficient as possible in the re-synchronization scenario. For this purpose, we need to define short-cuts between distant keys to avoid the expensive computation of all the intermediate keys. Inspired by the skip-list data structure introduced in [START_REF] Pugh | Skip Lists: A Probabilistic Alternative to Balanced Trees[END_REF], we suggest to organize our re-keying scheme in s stages, s 2 containing increasingly sequences of keys4 . This organization in lists, illustrated in Fig. 2 Fig. 2: Stage representation of our new re-keying scheme R φ in the case s = 3. with p i and q i public random values, involves a more efficient lookup with a reduction of the complexity from linear to logarithmic. Nevertheless, it is worth noticing that unlike skip-lists, this structure does not expect additional relations the public random values are known after the first encryption, the message blocks would have been chosen non-adaptively to avoid non random inputs.

between keys. There is still one single computation path to derive each key. Figure 3 illustrates the whole encryption scheme using φ 3 for the concatenation of the block cipher and the wPRFs used for the derivation. The values r i are the public random values used for the encryption, the values m i represent the blocks of message to encrypt and the values c i the corresponding ciphertexts. The very first key K 0 is the entry point of the first stage. Keys from the first stage allow to generate the following first stage keys or to go down to the second stage. When going down, the index of the key increases by one whereas when computing the next key in the same stage s c , the index is increased by 1 + s + • • • + s s-sc . Each derivation requires one public value that we refer to as p i when going down and q i otherwise with i referring to the index of the key used for the derivation. In practice, the sender updates his own secret key after each operation, following the indices order. When he wants to perform a transaction with the receiver, he just has to relay his current transaction counter. The receiver then performs a series of operations to derive the expected session key. For this purpose, he can either decides to always start with the very first key K 0 or to start with another key that he already computed and that is compliant with the new index. Algorithm 15 depicts the process for the first situation.

Efficient Generation of Random Values

For efficiency purpose, one tries to minimize the generation of fresh randomness in our construction. We propose several methods to distribute the public random values. In a first attempt, we generate two fresh public random values p and q for the key derivation as illustrated in Fig. 2 and 3 and one additional random value for the input message block. Although the encryption scheme is naLR, the solution is impractical. Another solution is to follow the method from [START_REF] Faust | Practical Leakage-Resilient Symmetric Cryptography[END_REF] and attribute two fresh random values by tree layer plus one for each block of message. This new proposal reduces the amount of randomness without loss of security since each path uses different random values for each time step.

The work of Yu and Standaert in [START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF] allows to reduce even more the cost of the generation of randomness. It suggests to replace the randomness by pseudorandom values generated by a PRF in counter mode from a single public seed. This solution can directly be applied to ours and results in a significant improvement of the performances. The global scheme can still be proven naLR in the peculiar world of minicrypt [START_REF] Impagliazzo | A Personal View of Average-Case Complexity[END_REF], that is either the scheme is secure or we can build public-key primitives from our symmetric functions, which is very unlikely. Theorem 3. Let φ be a weak PRF and G a PRF. Then the system S R φ ,φ,G described above is a naLR encryption scheme or we can build public-key primitives from the PRFs φ and G and the related leakage functions.

Leakage-Resilient Security Analysis

In this section, we give the security proofs of the three theorems presented in Sect. 3.

Security Analysis of Theorem 1

In Sect. 3, Theorem 1 states the non-adaptive leakage-resilient security of an encryption scheme composed of a naLR naPRF and a block cipher, as illustrated in Fig 1 . The following depicts the proof.

Proof. From the granular leakage-resilient model, our scheme is split into time steps which leak independently. The attacker is allowed to choose non-adaptively a leakage function f = (f 1 , f 2 ) with components for each of these time steps: f 1 for the PRF and f 2 for the block cipher. Then, she can submit q distinct queries to her oracles which can be divided between challenge queries and leakage queries. For each challenge query, she gets back either the real output of her query or the encryption of a random string. For each leakage query, she gets both the real output of her query and the leakage which is exactly the output of the leakage function f she chose. Let us now show the proof that the construction is a naLR encryption scheme. As explained in [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF], we organize the security proof of Theorem 1 as a sequence of games. The first one, referred to as Game 0, represents the real case, that is when the attacker gets both the leakage and the real outputs of her queries. It directly corresponds to the left-hand side probability in Definition 5 for an adversary A having access to challenge and leakage oracles:

IP K * ←{0,1} k [A(S K (.), S f K (.)) = 1].
We denote by G 0 the event A(S K (.), S f K (.)) = 1 and corresponding to Game 0. The last game Game N represents the random case, that is when all the challenge outputs are generated from random queries. It corresponds to the right-hand side probability in Definition 5 with $ a random string in {0, 1} n :

IP K * ←{0,1} n [A(S K ($), S f K (.)) = 1].
Similarly, we denote by G N the event: A(S K ($), S f K (.)) = 1. We aim to show that the difference between these probabilities (which is exactly the advantage of the attacker according to Definition 5) is negligible. To proceed, we go through intermediate games and we iteratively prove that the probability P(G i ) corresponding to Game i is negligibly close to the probability P(G i+1 ) corresponding to Game i + 1 for i ∈ [N -1]. The difference between two successive games is expected to be very small for the needs of the proof. In the following, we will use three kinds of games transition: the transitions based on indistinguishability, the transitions based on failure events and the so-called bridging steps.

Game 0 [SYM-REAL]. This game is referred to as the real game. In this game, the attacker A who submits adaptive leakage and challenge queries to her challenger, gets back both the leakage and the real outputs of her queries. We depict below the process in details.

Leakage functions. The adversary A first chooses a leakage function f = (f 1 , f 2 ) to observe the leakage during both the naLR naPRF and the block cipher executions. In our security model, we impose the leakage function to be chosen non-adaptively that is before seeing any leakage or outputs.

Challenge Before everything, the challenger of A chooses uniformly at random a key K ∈ {0, 1} n for the naLR naPRF F . Subsequently, A is allowed to submit adaptively to her challenger q distinct queries whose q 0 are leakage queries M 1 , . . . , M q0 and q 1 = q -q 0 are challenge queries M ′ 1 , . . . , M ′ q1 . Then, for each leakage query M i , i ∈ [q 0 ] the challenger receives from A, the challenger chooses uniformly at random an index ind i as input for the PRF and returns both the real output c i and the corresponding leakage:

c i ← β Ki (M i ) with K i = F (K, ind i ) and f 1 (K, ind i ), f 2 (K i , M i ).
For each challenge query M ′ i , i ∈ [q 1 ], the challenger also chooses uniformly at random an index ind ′ i and returns to A only the real output:

c ′ i ← β K ′ i (M ′ i ) with K ′ i = F (K, ind ′ i ).
We aim now to transform this real game into a new game that is equivalent to the computation of the adversary given an oracle access to the encryption of a random value in {0, 1} n and such that the probability that b = 1 in this latter game is negligibly close to P[G 0 ].

Game 1 [bridging step]

In Game 0, the challenger chooses uniformly at random a index as input for the naLR naPRF at each leakage or challenge query. We make here a conceptual change. Instead of choosing the indices at each query, the challenger chooses now all the q indices at the very beginning, that is before receiving the first query from the attacker. Since the indices are chosen uniformly at random, it does not change anything for the attacker. However, it is mandatory to use the naLR naPRF since it expect its inputs to be chosen non-adaptively that is before seeing any leakage or output. Eventually,

P[G 0 ] = P[G 1 ].
Game 2 [transition based on a failure event]. In Game 1, the challenger chooses uniformly at random the q indices of the future queries. We now modify this first game so that we ensure that all the uniformly random indices chosen by the challenger are pairwise distinct. It is easy to note that Games 1 and 2 proceed identically, unless there is a collision in the set of uniformly random indices. Let us denote by E this specific event. If E does not occur, then the output of both games is exactly the same. Equivalently, the following relation is satisfied:

G 1 ∧ E ⇔ G 2 ∧ E.
Then, from the common Lemma denoted by Difference Lemma in [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF], we have the following result:

|P[G 1 ] -P[G 2 ]| P[E].
Let us now determine the probability of event E. The q index values of Game 0 are sampled uniformly at random. Therefore, from the birthday bound, the probability of having at least a collision is less than q(q -1)/2 n+1 if q n. This result gives us a bound on the difference between the probabilities of the events of b = 1 in both games:

|P[G 1 ] -P[G 2 ]| q(q -1) 2 n+1 .
Game 3 [transition based on indistinguishability]. We now make a small change to the above game. Namely, instead of computing the intermediate keys from the naLR naPRF F (for the challenge queries), we generate them using a random function:

R ← R n,n K ′ i ← R(M ′ i ) c ′ i ← β K ′ i (M ′ i ) ∀i ∈ [q 1 ]
or indistinguishably

K ′ i ← $ c ′ i ← β K ′ i (M ′ i ) ∀i ∈ [q 1 ]
where $ is a random string in {0, 1} n .

Let us consider an adversary A who distinguish these two games. A interacts with a challenger C A as in Game 0 and gets back either outputs using random keys if b = 1 or outputs using keys computed from the naLR naPRF F if b = 0.

A then outputs a bit b ′

A in view of the information she got that aims to be identical to b.

Let us now show that if A actually exists, we are able to build a new adversary B against the naLR naPRF F who uses A. The process is as follows. As above, the adversary A first chooses a leakage function f = (f 1 , f 2 ) but this time sends it to the adversary B who transmits f 1 to her own challenger C B . Then, as the challenger of adversary A in previous games, C B chooses q uniformly random distinct indices and a uniformly random key K that he submits to the naLR naPRF leakage and challenge oracles with the leakage function f 1 . The challenger then gets back from the leakage oracle and transmits to B both the leakage during the execution of this naLR naPRF:

f 1 (K, ind i ) ∀i ∈ [q 0 ]
and the keys corresponding to the leakage queries:

K 1 , . . . , K q0 .
Then, C B gets back from the challenge oracle the keys K ′ i , i ∈ [q 1 ] representing either the real keys (if b = 0) or uniformly random strings in {0, 1} n (if b = 1). Once these data collected, B is ready to answer the adaptive leakage and challenge queries of A. For each leakage query M i , B computes β Ki (M i ) and f 2 (K i , M i ) and with the oracle previous replies sends back to A:

f 1 (K, ind i ) f 2 (K i , M i ) c i = β Ki (M i ).
For each challenge query M ′ i , i ∈ [q 1 ], B directly uses the key K ′ i given by its challenge oracle and sends back to A according to the bit b: b=0:

c ′ i = β K ′ i (M ′ i ) with K ′ i ← F (K, ind ′ i ) b=1: c ′ i = β K ′ i (M ′ i ) with K ′ i ← $.
Eventually, A got the leakage outputs corresponding to its leakage queries and the outputs of the encryption scheme with its challenge queries either with the real keys if b = 0 or with uniformly random keys if b = 1. This situation perfectly simulates Game 0 with the real keys (when b = 0) and Game 1 with the uniformly random keys (when b = 1). As a result, the bit b ′ B given by adversary B after its challenge on the naLR naPRF F is exactly the same than the bit b ′ A given by adversary A to distinguish both Games.

Consequently, an adversary who aims to distinguish both games has the same advantage an adversary who aims to break the security of the naLR naPRF F . This is bounded by the naLR naPRF advantage ǫ F . Eventually, we have:

|P(G 2 ) -P(G 3 )| = ǫ F .
Game 4 [transition based on a failure event]. We now modify Game 3 so that in addition to be uniformly random, the keys we use are also pairwise distinct.

K ′ i ← $ s.t. K ′ i = K ′ j if i = j c ′ i ← β K ′ i (M ′ i ) ∀i, j ∈ [q 1 ].
It is worth noticing that Games 3 and 4 proceed identically, unless there is a collision in the set of uniformly random keys. Let us denote by E this specific event. If E does not occur, then the output of both games is exactly the same. As detailed in [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF] with the Difference Lemma and since the following relation is satisfied:

G 3 ∧ E ⇔ G 4 ∧ E, we have |P[G 3 ] -P[G 4 ]| P(E).
We now determine the probability of event E. The q 1 key values of Game 1 are sampled independently and at random. Therefore, from the birthday bound, the probability of a collision is less than (q 1 (q 1 -1))(2 n+1 ) if q 1 √ n. Straightforwardly, this result gives us a bound on the difference between the probabilities of the events of b = 1 in both games:

|P[G 3 ] -P[G 4 ]| q1(q1-1) 2 n+1 .
Game 5.0 [bridging step]. We now make a purely conceptual change to Game 4. In this game, the challenge outputs are computed from uniformly random keys without any intervention of the naLR naPRF:

K ′ i ← $ s.t. K ′ i = K ′ j ∀i, j ∈ [q 1 ], i = j c ′ i ← β K ′ i (M ′ i ) ∀i ∈ [q 1 ]
Since the keys are now uniformly random and pairwise distinct, the invocations to the block cipher are completely independent from each other. So we can now consider them separately. Let us say that in this game, zero challenge query is computed from a random function and the q 1 others using the block cipher β.

Clearly,

P[G 4 ] = P[G 5.0 ].

Game 5.t [transition based on indistinguishability]

. We now modify Game 5.0 by replacing the t first invocations of the block cipher β for the challenge queries by invocations of a truly random function R ← R n,n :

K ′ i ← $ s.t. K ′ i = K ′ j ∀i, j ∈ [q 1 ], i = j c ′ i ← R(M ′ i ) ∀i ∈ [t] and c ′ i ← β K ′ i (M ′ i ) ∀i ∈ t + 1, . . . , q 1 .
We consider an adversary A who aims to distinguish Games 5.0 and 5.t. A first chooses a leakage function f = (f 1 , f 2 ) (respectively related to F and β) and sends it to her challenger. For each leakage query M i , i ∈ [q 0 ] she makes, A gets back:

f 1 (K, ind i ) f 2 (K i , M i ) c i = S F,β (M i ) = β Ki (M i )
with K uniformly generated at random by the challenger. For the t first challenge queries M ′ 1 , . . . , M ′ t sent to her challenge oracle, A gets back according to the game: Game 5.0:

c ′ i = β K ′ i (M ′ i ) ∀i ∈ [t] Game 5.t: c ′ i = R(M ′ i ) , R ← R n,n ∀i ∈ [t].
The other challenge queries are equivalent to Game 5.0. Eventually from these data, A output a bit b ′ A indicating which game is played. Now, let us show that if such an adversary A exists, we can build an adversary B against the block cipher β that uses A. B proceeds as follows. B gets from A the leakage function f = (f 1 , f 2 ) and transmits it to her challenger C B . C B generates the master K and the indices uniformly at random and uses them to compute the leakage of F and the intermediate keys. For each leakage query M i , i ∈ [q 0 ] from A, C B directly computes the leakage of the whole encryption. B gets back the corresponding leakage and outputs and sends to A:

f 1 (K, ind i ) f 2 (K i , M i ) c i = β Ki (M i ).
For each of the t first challenge queries from A, B sends both the query and the corresponding intermediate key to her challenge oracle. According to the bit b, B gets back and returns to A: b=0:

c ′ i = β K ′ i (M ′ i ) b=1: c ′ i = $.
The other challenge queries are directly computed by B and sent back to A.

Eventually, this experience perfectly simulates Games 5.0 when b = 0 and 5.t when b = 1. The adversary B faces the same challenge to distinguish the real output of the block cipher and a random string than A to distinguish both games. Their output bits b ′ B and b ′ A are perfectly equal which allows us to conclude that the difference between probabilities of events of both games when b = 1 is directly based on the security parameter of the block cipher as a PRF for each invocation:

|P[G 5.0 ] -P[G 5.t ]| = |P[G 5.0 ] -P[G 5.1 ] + P[G 5.1 ] -• • • -P[G 5.t ]| |P[G 5.0 ] -P[G 5.1 ]| + • • • + |P[G 5.t-1 ] -P[G 5.t ]| t • ǫ β .
from the triangular inequality.

Game 6 [SYM-RANDOM]. In this game, the invocations of the block cipher corresponding to all the q th 1 query are replaced by the invocations of uniformly random functions.

K ′ i ← $ s.t. K ′ i = K ′ j ∀i, j ∈ [q 1 ], i = j c ′ i ← R(M ′ i ) ∀i ∈ [q 1 ]
or equivalently

K ′ i ← $ s.t. K ′ i = K ′ j ∀i, j ∈ [q 1 ], i = j c ′ i ← $ ∀i ∈ [q 1 ].
As explained in this introduction, this last game represents the right-hand side of the advantage of the attacker in Definition 5. Let us now compute the difference of the probability of G 0 corresponding to Game 0 and the probability of G 6 corresponding to this last game:

|P[G 0 ] -P[G 5 ]| = |P[G 0 ] -P[G 1 ] + P[G 1 ] -P[G 2 ] + P[G 2 ] -P[G 3 ] + P[G 3 ] -P[G 4.0 ] + P[G 4.0 ] -P[G 4.t ] + P[G 4.t ] -P[G 5 ]|.
From the triangular inequality, we obtain:

|P[G 0 ] -P[G 5 ]| |P[G 0 ] -P[G 1 ]| + |P[G 1 ] -P[G 2 ]| + |P[G 2 ] -P[G 3 ]| + |P[G 3 ] -P[G 4.0 ]| + |P[G 4.0 ] -P[G 4.t ]| + |P[G 4.t ] -P[G 5 ]| q(q -1) 2 n+1 + ǫ F + q 1 (q 1 -1) 2 n+1 + 0 + t • ǫ β + (q 1 -t) • ǫ β .
Eventually the advantage of an attacker against the encryption scheme described in Theorem 1 is bounded by: q(q -1) + q 1 (q 1 -1)

2 n+1 + ǫ F + q 1 • ǫ β
which is negligible.

Security Analysis of Theorem 2

Unfortunately, our new re-keying scheme is not a PRF since the adversary could easily take advantage of the outputs of the intermediate nodes to recover the following keys. However we prove hereafter that instantiated with a specific wPRF, it still yields a naLR encryption scheme.

Proof. To prove Theorem 2, we first prove the security of the independent time steps in the new re-keying scheme. Let us consider an intermediate node of the re-keying scheme. If a challenge or a leakage query is defined on this node, the related operation will be the concatenation φ 3 of three wPRFs: two for the derivation of the next keys and one for the encryption. In the case no query is defined on this node, the concatenation φ 2 of only two wPRFs is required. As a result, we prove that the concatenation of two or three invocations of the wPRF φ using the same key (two for the derivation and in some cases one for the block cipher) still forms a secure wPRF.

Proposition 1. Let φ : {0, 1} n × {0, 1} n → {0, 1} n be a (ǫ, s, 3q)-secure wPRF.

φ 3 : {0, 1} n × {0, 1} 3n → {0, 1} 3n (k, p, q) → (φ(k, p) φ(k, q))
is then a (ǫ ′ , s, q)-secure weak PRF with ǫ ′ 3q(3q-1)

2 n+1 + ǫ 6 .
Proof (Proof of Proposition 1). As done in the previous section, we organize this proof as a sequence of games. But this time, we aim to show the security of a function as a weak PRF in the sense of Definition 1. We start with Game 0 which represents the real game in which the attacker gets exclusively the real outputs of her queries.

Game 0 [SYM-REAL]. As briefly mentioned, in this game the attacker gets the real outputs of her queries. Contrary to the previous proof, there is no leakage here so we only consider challenge queries.

Challenge As usual, we consider an attacker A and her challenger C A . The attacker A asks her challenger for q queries. The challenger C A then chooses uniformly at random an initial key K ∈ {0, 1} n and q queries M 1 , . . . , M q ∈ {0, 1} 3n and returns to A both the queries and their real outputs:

(M i , φ 3 (K, M i )) = ((p i , q i , r i ), (φ(K, p i )||φ(K, q i )||φ(K, r i ))), ∀i ∈ [q].
We will now slightly transform this game until we reach the random game in which the adversary only gets random values in answer to her challenge queries. At each step, we show that the probability of b = 1 is negligibly close between consecutive games.

Game 1 [transition based on a failure event]. In Game 0, the challenger chooses q random and distinct challenge queries (p i ||q i ||r i ) 1 i q . We now slightly modify this game to ensure that the intermediate queries (p i ), (q i ) and (r i ) for i ∈ [q] are all pairwise distinct. From the birthday bound and the Difference Lemma in [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF], we obtain a bound on the difference between the probabilities of the events of b = 1 in both games:

|P[G 0 ] -P[G 1 ]| 3q(3q -1) 2 n+1 .
Game 2 [transition based on indistinguishability]. Game 1 is different from the original game since all the intermediate parts of the q queries are pairwise distinct. Let us now consider instead of the weak PRF φ 3 , three invocations of a random function in {0, 1} n .

We consider an adversary A 3 who is able to distinguish both games. We show now that we are able to build a new adversary A against the weak PRF φ who uses A 3 . The process is as follows. The challenger C A of the adversary A replaces the challenger of A 3 to generate the initial key K and the random queries. He then submits to his challenge oracle O φ this initial key and the 3q distinct and uniformly random intermediate queries. According to the random bit b, he gets back and gives to A either the real outputs of the weak PRF φ or random values. Thus, A returns to

A 3 : b = 0 : (M i , φ 3 (K, M i )) = ((p i , q i , r i ), (φ(K, p i )||φ(K, q i )||φ(K, r i ))) b = 1 : ((p i , q i , r i ), (R(p i )||R(q i )||R(r i ))).
with R a random function in {0, 1} n . Eventually, this situation perfectly simulates Game 1 with the real outputs (b = 0) and Game 2 with the random ones (b = 1). The adversary A faces the same challenge in distinguishing the real and random outputs than A 3 to distinguish Games 1 and 2. Consequently, we have

|P[G 1 ] -P[G 2 ]| = ǫ φ .
Game 3 [transition based on a failure event]. In Game 1, we modified the inputs to ensure the absence of collision between the intermediate values. Now we switched to random functions, we can come back to the initial random values in order to reach the final game according to Definition 1. The difference of probabilities between these two games is straightforwardly the same than between Game 0 and 1:

|P[G 2 ] -P[G 3 ]| 3q(3q -1) 2 n+1 . Game 4 [SYM-REAL].
For the security definition to be perfectly verified, we conceptually modify Game 3 to only consider one invocation of a random function in {0, 1} 3n instead of three in a smaller range. Both games are equivalent and we can observe that this new one represents exactly the right-hand side of Definition 1. As a result, we obtain:

|P[G 0 ] -P[G 3 ]| = |P[G 0 ] -P[G 1 ] + P[G 1 ] -P[G 2 ] + P[G 2 ] -P[G 3 ] + P[G 3 ] -P[G 4 ]| 3q(3q -1) 2 n + ǫ φ
which concludes the security proof. Now we have independent time steps, we can build the proof on the security model previously established. The attacker is still allowed to choose a global leakage function f = (f 1 , f 2 ) but this time f 1 related to the invocations of weak PRF φ 2 during the re-keying R φ and f 2 to the final encryption. Then, she submits q 0 distinct leakage queries and q 1 = q -q 0 different and pairwise distinct challenge queries. For each leakage query, the adversary gets the leakage of the intermediate nodes computed with function phi 2 and both the leakage and the output of the last node computed with function φ 3 . For each challenge query, she receives either the real output or the encryption of a random string of the input's size. Let us now give the proof organised as a sequence of games as proposed by Shoup in [START_REF] Shoup | Sequences of games: a tool for taming complexity in security proofs[END_REF]. As detailed in Subsection 4.1, the first game refers to the left-hand side probability of Definition 5 whereas the last game refers to the right-hand side probability in the same definition. By showing that the games are negligibly close, we prove that the advantage of the attacker in distinguishing them is negligible and as a result that the scheme is leakage-resilient secure.

Game 0 [SYM-REAL]. In this game, the attacker gets from her challenger both the leakage and the real outputs of her leakage and challenge queries. Below we formally describe the process.

Leakage functions. The adversary A is allowed to choose a leakage function f = (f 1 , f 2 ) giving the leakage of the key derivation and the leakage of the encryption. Recall that the naLR security notion requires that the adversary choose this leakage function non-adaptively, that is before seeing any leakage or output.

Challenge. In this game, the challenger of A chooses uniformly at random an initial key K ∈ {0, 1} n . Then, for each leakage query M i , i ∈ [q 0 ] chosen by A, the challenger chooses uniformly at random an index ind i for the naLR naPRF and returns the real output and the corresponding leakage:

c i ← φ(K i , r i ) ⊕ M i and f 1 (K, ind i ) and f 2 (K i , M i ) with r i ⋆ ← {0, 1} n and K i ← R φ (K, ind i ).
For each challenge query M ′ i , i ∈ [q 1 ], he also chooses uniformly at random an index ind ′ i and only returns the real output:

c ′ i ← φ(K ′ i , r ′ i ) ⊕ M ′ i with r ′ i ⋆ ← {0, 1} n and K ′ i ← R φ (K, ind ′ i ).
We denote this first game by Game 0 and the related event by G 0 . We will now transform this real game into a new one whose probability will be negligibly close.

Game 1 [bridging step]. In Game 0, the indices for the PRF are chosen by the challenger at each query. In this game, we make a conceptual change consisting in choosing all the indices before the first query. Since they are chosen uniformly at random, it does not change the advantage of the attacker. However, it is mandatory for the use the naLR naPRF which requires non-adaptive inputs.

We have:

P[G 0 ] = P[G 1 ].
Game 2 [transition based on indistinguishability]. In this game, we modify all the nodes involved in leakage queries included the intermediate ones. Since the related keys leak, we replace all the invocations of the related weak PRFs φ 2 and φ 3 by truly random functions: R ← R n,n :

K ′ j ← $
for all keys generated from low keys

c ′ i ← φ(K ′ i , r ′ i ) ⊕ M ′ i with r ′ i ⋆ ← {0, 1} n and K ′ i ← (φ • R) ⋆ (K, ind ′ i )
with (φ • R) ⋆ representing the combination of invocations of function φ and random function according to the nodes involved in leakage queries. To perform the reduction we use a lemma from [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF] that we recall here.

Lemma 1 (Lemma 2 from [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF]). For any α > 0 and t ∈ N : If F : {0, 1} n × {0, 1} n → {0, 1} n is a (ǫ, s, q)-secure wPRF (for uniform keys), then it is a (ǫ ′ , s ′ , q ′ )-secure wPRF with α-low keys if the following holds:

q q ′ .t ǫ ǫ ′ /2 α+1 -q 2 /2 n+1 -2exp(-t 2 ǫ ′2 /8) s s ′ .t.
Now we consider an adversary A who aims to distinguish Games 1 and 2. A first chooses a leakage function f = (f 1 , f 2 ) and sends it to her challenger C. For each leakage query M i , i ∈ [q 0 ] A submits, she gets back:

f 1 (K, ind i ) f 2 (K i , M i ) c i = φ(K i , r i ) ⊕ M i with r i ⋆ ← {0, 1} n and K i ← R φ (K, ind i ).
For each challenge query M ′ i , i ∈ [q 1 ], A gets back according to the game:

Game 1 : c ′ i = φ(K ′ i , r ′ i ) ⊕ M ′ i with r ′ i ⋆ ← {0, 1} n and K ′ i ← R φ (K, ind ′ i ) Game 2 : c ′ i = φ(K ′ i , r ′ i ) ⊕ M ′ i with r ′ i ⋆ ← {0, 1} n and K ′ i ← (φ • R) ⋆ (K, ind ′ i ).
Now let us demonstrate that if such an adversary A exists, we are able to build an adversary B against the weak PRF that uses A as follows. B gets from A the leakage function f = (f 1 , f 2 ) and transmits it to her challenger D. D generates the master key K and q 0 indices (for each leakage query) uniformly at random and uses them to compute the leakage and the intermediate keys. Then for each leakage query M ′ i submitted by A, he sends the results to B who returns to A:

f 1 (K, ind i ) and f 2 (K i , M i ) c i = φ(K i , r i ) ⊕ M i with r i ⋆ ← {0, 1} n and K i ← R φ (K, ind i ).
For each challenge query M i submitted by A and transmitted by B, D computes the derivations for all the nodes not involved in the transformation and sends the data to her challenge oracle for the others. According to the bit b representing the choice of her oracle, B gets back the results, computes the encryptions and returns to A:

b = 0 : c ′ i = φ(K ′ i , r ′ i ) ⊕ M ′ i with r ′ i ⋆ ← {0, 1} n and K ′ i ← R φ (K, ind ′ i ) b = 1 : c ′ i = φ(K ′ i , r ′ i ) ⊕ M ′ i with r ′ i ⋆ ← {0, 1} n and K ′ i ← (φ • R) ⋆ (K, ind ′ i ).
Eventually, this experience perfectly simulates Game 1 when b = 0 and Game 2 when b = 1. Indeed, the adversary B faces the same challenge to distinguish the real output of the weak PRF and a random string than A to distinguish both games. We can conclude from this reduction that the probabilities related to both games are negligibly close. The difference directly comes from the Lemma 2 in [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF] and the number of nodes involved in leakage queries.

|P[G 1 ] -P[G 2 ]| 2 3λ+1 (ǫ φ2 + q 2 0 /2 n+1 + 2 exp(-ǫ 2 φ2 /8)) • (v 0 -q 0 ) + 2 3λ+1 (ǫ φ3 + q 2 0 /2 n+1 + 2 exp(-ǫ 2 φ3 /8)) • q 0
with v 0 the number of nodes involved in leakage queries. Note that the presence of two terms is related to the use of function φ 2 for keys derivation only and φ 3 at the last node of the query for also an encryption.

Let us now compute the bound on the number of nodes involved in leakage queries according to the parameters s (number of stages) and l (number of children of a node at the upper stage) 7 . We consider the worst case, that is when we always start from the initial key without storing any node, when no node is used in several leakage queries and we take the average index 2 n-1 .

v 0 < q 0 ( 2 n-1 s-1 j=0 l j + s.l)
invocations of weak PRFs. Choosing s = n and l = 2 gives us the following bound:

v 0 < q 0 ( 2 n-1 2 n -1 + 2n) < q 0 (1 + 2n).
Game 3 [transition based on indistinguishability]. In this game, we modify all the nodes involved in challenge queries except those involved in leakage queries and already transformed. We replace the weak PRFs instantiated with the corresponding keys by random functions R ← R n,n :

K ′ j ← $ for all keys involved in queries c ′ i ← $ ⊕ M ′ i .
Let us consider an attacker A who is able to distinguish Game 3 from Game 2. A first chooses a leakage function f and sends it to her challenger. For each leakage query M i , i ∈ [q 0 ] A submits, she gets back:

f 1 (K, ind i ) f 2 (K i , M i ) c i = φ(K i , r i ) ⊕ M i with r i ⋆ ← {0, 1} n and K i ← R φ (K, ind i ).
For each challenge query M ′ i , i ∈ [q 1 ], A gets back according to the game:

Game 2 : c ′ i = φ(K ′ i , r ′ i ) ⊕ M ′ i with r ′ i ⋆ ← {0, 1} n and K ′ i ← (φ • R) ⋆ (K, ind ′ i ) Game 3 : $ ⊕ M ′ i .
with (φ • R) ⋆ the combination of invocations φ and random functions (for the node involved in leakage queries) corresponding to Game 2.

We now show that if such an attacker exists, we can build an attacker B who is able to break the weak PRFs φ 2 , φ 3 using A. The process is as follows. A first chooses a leakage function f and submits it to B. B sends it to her challenger. The latter generates the master key K and the q 0 indices for the leakage queries uniformly at random. He then computes both the leakage and the intermediate keys. Then for each leakage query M i that A submits to B, she transmits it to her challenger who computes and returns the following results:

f 1 (K, ind i ) and f 2 (K i , M i ) c i = φ(K i , r i ) ⊕ M i with r i ⋆ ← {0, 1} n and K i ← R φ (K, ind i ).
As Eve only has access to the communication, she only gets knowledge of the intermediate public value (but not the seed), the current view and the correct or false result of the encryption. Hence she cannot guess the bit b A without breaking the scheme with secret seed. From the non negligible advantage of the adversary A, the bit agreement we established achieves correlation (IP[b A = b B ] is greater than 1/2). As a consequence, this protocol is equivalent to a bit-PKE in which the secret key corresponds to the seed generated by Alice and the public key to the intermediate public values.

Practical Aspects

In previous sections, we have shown that our construction instantiated with a weak PRF φ and combined with a PRF G yields a non-adaptive leakage-resilient encryption scheme. We now focus on the practical aspects.

Instantiation

Our encryption scheme requires two primitives: a weak PRF φ for the derivation and the block cipher and a PRF G for the generation of random values.

Weak PRF φ The concatenation of invocations of the weak PRF φ with random inputs is a suitable solution for the key derivation and the block cipher. Such a weak PRF can be built from any secure block cipher, like AES. Hence, inspired by [START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF], we propose the constructions φ 2 (k, p) = AES(k, p 0) AES(k, p 1), for the key derivation and φ 3 (k, p, r) = φ 2 (k, p) AES(k, r), for also the encryption which benefit from the reuse of one public random input. PRF G Following [START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF], we instantiate G with a secure block cipher, e.g. the AES. Since the AES is already implemented for the weak PRF φ, this choice benefits from the feature of limiting the code size. As proved in [START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF], only log(1/ǫ) bits of fresh pseudo-randomness are required for each public value, with ǫ the security parameter of the weak PRF φ (e.g. AES). As a consequence, we only need one additional call of the AES every ⌊n/ log(1/ǫ)⌋ invocations of φ.

Complexity Evaluation

Let us now focus on the complexity of encrypting a n-block message using our construction. We denote by τ AES the complexity in time of one AES calls either as a PRF for the re-keying or as a block cipher for the encryption. First, note that without updating the secret key and without any mode of operation, the complexity of the encryption is exactly C = n • τ AES . Then, let us compute the same complexity in our leakage-resilient construction by first omitting the generation of randomness. For the sake of simplicity and because it is negligible, we will omit the complexity of the bitwise addition which is performed once per block encryption. Furthermore, we will start with the initial key K 0 without loss of generality since what counts is the distance between the current index and the targeted one. We recall that the distance between two keys indices from the same stage s c is equal to 1 + s + • • • + s s-sc . We denote by N s this distance which is also the number of children of a key from the same stage plus one. As a result, the number of AES executions N required to reach the key K i is bounded as follows: i N1 N ≤ i N1 + s(s -1) with s(s -1) the maximum number of executions needed to reach a child from a first stage key. These bounds can be squeezed with the parameters related to the other stages. Table 1 presents the number of AES executions required to re-synchronize from K 0 to keys with increasing indices. For comparison purpose, when the keys are updated sequentially, 10,000 invocations of the re-keying primitives are required to compute K 10 4 from K 0 . When using our construction with five stages, only N = 20 invocations are necessary that is five hundred times less. In the general case, one also needs to consider the generation of random values. Since the generation is also performed with the AES, the complexity of encrypting a nblock message is: C = (2N + 4n -2)τ AES if we consider one invocation of G for each key derivation and each block encryption. From [START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF] we could reduce the number of invocations of the generator until one every ⌊n/ log(1/ǫ)⌋ invocations of φ without loss of security:

C = N + 2n -1 + N + 2n -1 ⌊n/ log(1/ǫ)⌋ τ AES .

Conclusion

In this paper, we have studied the problem of constructing an efficient and provably-secure symmetric encryption scheme based on re-keying ideas. In particular, we have first proven that a naLR naPRF combined with a block cipher yields a non-adaptive leakage-resilient symmetric encryption scheme. Then we have shown that such an encryption scheme does not actually require this level of security for its re-keying scheme. In fact, we have introduced a new re-keying process with relaxed security properties but which still yields a secure encryption scheme. Furthermore, it benefits the feature of being much more efficient than a sequential scheme when both parts of the symmetric communication need to re-synchronize. We have both proven the security based on this new re-keying scheme and evaluated the global complexity.

This work shows that it is possible to use the security of the mode of operations in order to construct leakage-resilient encryption scheme. The previous approach in this area tries to construct leakage-resilient block ciphers but it turns out that they are very inefficient. One of the main drawback of this scheme is that we need to compute the keyschedule algorithm for each message block. One interesting idea would be to avoid it by using a more secure mode of operations such as OCB. Indeed, this mode is interesting since the adversary cannot know what is the real input of the block cipher and consequently classical DPA attack are thwarted. However, the security proof of this mode is a real challenge.

Fig. 3 :

 3 Fig. 3: Tree representation of our new encryption scheme S R φ ,φ in the case s = 3.

3 • 4 #

 34 10 2 3.3 • 10 3 3.3 • 10

  Algorithm 1 Re-keying SchemeRequire: current key Kc, index c, stage sc, new index i Ensure: key Ki, index i, stage si

	1: (K, ind, st) ← (Kc, c, sc)
	2: while (ind = i) do
	3:	while (i > ind +	s-s t	s j ) do	⊲ Horizontal steps
				j=1
	4:	K ← φ(K, q ind )
	5:	ind ← ind +	s-s t	s j
			j=0
	6: 7:	end while while (i > ind) & (i ind +	s-s t	s j ) do	⊲ Vertical steps
						j=1
	8:	K ← φ(K, p ind )
	9:	ind ← ind + 1
	10:	st ← st + 1
	11:	end while
	12: end while
	13: return (K, st)

Table 1 :

 1 Number of AES executions to derive a key from K 0 given its index

	K 10	K 10 2	K 10 3	K 10 4	K 10 5
	#stages = 2

We could also have chosen to add the message to the random value before the encryption, referring to Lemma 3 from[START_REF] Pietrzak | A Leakage-Resilient Mode of Operation[END_REF] in the case of leakage. However, in case

In this description, each node generates s nodes at the first upper stage. Although convenient for the analysis, another choice can be made.

The input sc can also be directly computed from c.

Similarly, the security parameter of φ2 is bounded by 2q(2q-1) 2 n+1 + ǫ.

Then, for each challenge query M ′ i that A submits, B sends it to her challenger. The challenger sends the indices to B's challenge oracle and B gets back according to the bit b the real outputs of the weak PRFs or random values. She sends back to A:

This experience perfectly simulates Game 2 when b = 0 and Game 3 when b = 1. So if the adversary A exists, we can build an adversary B who is able to break the previous weak PRF. As a result, we obtain the following equality:

with v 1 the number of nodes involved in challenge queries. We apply the same computation than in Game 2 to bound this value:

Still instantiating s by n and l by 2, we obtain:

Game 4 [SYM-RANDOM]. In this last Game, all the nodes involved in challenge queries have been replaced by random functions. Hence, this game represents exactly the right-hand side probability in Definition 5. From the above sequence of games, we are able to compute a bound on the advantage of an attacker against this non-adaptive leakage-resilient encryption scheme.

Note that the advantage of the attacker depends on the number of nodes involved in leakage and challenge queries. This number depends in it turn on the parameters of the skip-lists: the number of stages s and the number of children for each node l. In Figure 1, we chose to order the keys linearly but we could also have chosen to jump in the first stage by powers of two if it was relevant for our implementation. In any case, one can find appropriate parameters which maintain the advantage of the attacker negligible enough so that the whole encryption scheme is still secure. As shown in example in the proof, s = n and l = 2 gives interesting bounds.

Security Analysis of Theorem 3

In 1995, Impagliazzo defined five complexity worlds [START_REF] Impagliazzo | A Personal View of Average-Case Complexity[END_REF]: algorithmica in which P = N P with all the amazing consequences, heuristica world in which on the contrary N P -complete problems are hard in the worst-case (P = N P ) but are efficiently solvable on average and the three worlds on the existence of the cryptographic functions. In the pessiland world, there exist average-case N Pcomplete problems but one-way functions do not exist, which implies that we cannot generate hard instances of N P -complete problem with known solution. In the minicrypt world, one-way functions exist but public-key cryptographic schemes are impossible and finally in the cryptomania world, public-key cryptographic schemes exist and secure communication is possible. These worlds have been used positively to establish security proofs in many papers [START_REF] Pietrzak | Composition implies adaptive security in minicrypt[END_REF][START_REF] Pietrzak | Weak pseudorandom functions in minicrypt[END_REF][START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF].

In this section, we follow the work of Yu and Standaert who show in [START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF] how to improve the efficiency of our re-keying scheme, maintaining its leakage-resilient security in the minicrypt world. In fact, our new construction currently requires a large amount of fresh randomness since we need to generate a new fresh random value for each new session key. Yu and Standaert show that tweaking a similar design to use only a small amount of randomness can still be leakage-resilient in the world of minicrypt. That is, either the new design is leakage-resilient or it becomes possible to build public-key primitives from the involved symmetric-key blocks and the related leakage functions, which is very unlikely. Their technique directly applies to our symmetric encryption scheme and only requires a public seed s that is randomly chosen. Instead of being randomly generated, our public values p i 's and q i 's are now computed from a PRF G in counter mode.

Proof of Theorem 3 from [START_REF] Yu | Practical Leakage-Resilient Pseudorandom Objects with Minimum Public Randomness[END_REF]. The scheme is trivially secure if the seed is secret since it is like replacing the outputs of the PRF G by a true random values. Let us now prove the leakage-resilience security when the seed is public. For this purpose, we assume by contradiction that there exists an adversary A against our scheme. If the scheme is not a naLR encryption scheme, there exists an adversary able to distinguish with a significant advantage the encryption of a real query from the encryption of a random string with the same size given the previous leakage and outputs. Let us now consider a protocol between two parties which we refer to as Alice and Bob who want to communicate over an authenticated channel. The protocol is a secure bit-agreement if an adversary, refer to as Eve, cannot recover the output bit of Alice. We construct it as follows: