Alex Biryukov
email: alex.biryukov@uni.lu

Léo Perrin
email: perrin.leo@gmail.com

Symmetrically and Asymmetrically Hard Cryptography (Full Version) *

Keywords: white-box cryptography, memory hardness, big-key encryption, Skipper, Whale, Diodon

The main efficiency metrics for a cryptographic primitive are its speed, its code size and its memory complexity. For a variety of reasons, many algorithms have been proposed that, instead of optimizing, try to increase one of these hardness forms.

We present for the first time a unified framework for describing the hardness of a primitive along any of these three axes: code-hardness, timehardness and memory-hardness. This unified view allows us to present modular block cipher and sponge constructions which can have any of the three forms of hardness and can be used to build any higher level symmetric primitive: hash function, PRNG, etc.

We also formalize a new concept: asymmetric hardness. It creates two classes of users: common users have to compute a function with a certain hardness while users knowing a secret can compute the same function in a far cheaper way. Functions with such an asymmetric hardness can be directly used in both our modular structures, thus constructing any symmetric primitive with an asymmetric hardness. We also propose the first asymmetrically memory-hard function, Diodon.

As illustrations of our framework, we introduce Whale and Skipper. Whale is a code-hard hash function which could be used as a key derivation function and Skipper is the first asymmetrically time-hard block cipher.

Introduction

The design of cryptographic algorithms is usually a trade-off between security and efficiency. Broadly speaking, the efficiency of an algorithm is defined along three axes: time, memory and code size. Yet in some scenarios it is desirable to design primitives that are purposefully inefficient for one or several of these metrics. This can be done to slow down the attackers, provide different levels of service to privileged and non-privileged users, adjust cost of operation in proof-of-work schemes, etc.. Primitives with different forms of computational hardness have been scattered in time and in several seemingly unrelated research/application areas. In this paper we propose a simple unifying framework which allows us to build new provably hard modes of operation and primitives.

The simplest illustration of functions designed to be time consuming to compute is that of key derivation functions (KDF). A KDF is typically built by iterating a one-way function (for example a cryptographic hash function), multiple times. Such functions are intended to prevent an adversary from brute-forcing a small set of keys (corresponding to, say 12 letter strings) by making each attempt very costly.

Time, however, is not the only form of hardness for which an artificial increase can be beneficial. Memory-hardness was one of the design goals of the winner of the Password Hashing Competition, Argon2 [START_REF] Biryukov | Argon2: new generation of memory-hard functions for password hashing and other applications[END_REF], the aim being to prevent hardware optimization of the primitive. As another example, one research direction in white-box cryptography is nowadays focusing on designing block ciphers such that the code implementing them is very large in order to prevent duplication and distribution of their functionality [BBK14, [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF][START_REF] Fouque | Efficient and provable white-box primitives[END_REF][START_REF] Bogdanov | Towards practical whitebox cryptography: Optimizing efficiency and space hardness[END_REF][START_REF] Bellare | Big-key symmetric encryption: Resisting key exfiltration[END_REF]. In this case, the aim could be to implement some form of Digital Right Management or to prevent the exfiltration of a block cipher key by malware.

Since hardness is an inherently expensive property, there are cases where a trap-door could be welcome. This is the case for the most recent weak white-box block ciphers [BBK14, [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF][START_REF] Fouque | Efficient and provable white-box primitives[END_REF]: while the white-box implementation requires a significant code size, there exists a functionally equivalent implementation which is much smaller but cannot be obtained unless a secret is known. That way, two classes of users are created: those who know the secret and can evaluate the block cipher efficiently and those who do not and thus are forced to use the code-hard implementation.

The different forms of hardness, their applications and typical instances from the literature are summarized in Table 1. Table 1: Six types of hardness and their applications.

Our Contribution Regardless of the form of hardness, the aim of the designer of a hard primitive is to prevent an attacker from by-passing this complexity, even if the attacker is allowed significant precomputation time. Informally, a user cannot decrease the hardness of the computation below a certain threshold.

Inspired by the formal definitions of hardness used in white-box cryptography, we provide for the first time a unified framework to study and design cryptographic algorithms with all forms of hardness. Our framework is easily extended to encompass asymmetric hardness, a form of complexity which can be bypassed provided that a secret is known. Our approach consists in combining simple functions called plugs having the desired form of hardness with secure cryptographic primitives. Algorithms are then built in such a way as to retain the cryptographic security of the latter while forcing users to pay for the full hardness of the former. In fact, we provide a theoretical framework based on random oracles which reduces the hardness of the algorithms we design to that of their plugs.

Furthermore, we introduce the first asymmetrically memory-hard function, Diodon. It is a function based on scrypt [START_REF] Percival | Stronger key derivation via sequential memory-hard functions[END_REF] modified in such a way as to allow users knowing an RSA private key to evaluate it using a constant amount of memory. It can of course be used as a plug within our framework.

Finally, we used this approach to build a code-hard hash function called Whale and an asymmetrically time-hard block cipher called Skipper. It is impossible to design a functionally equivalent implementation of the Whale hash function which is much smaller than the basic one. On the other hand, encrypting a block with Skipper is time consuming but this time can be significantly decreased if an RSA private key is known.

Outline. First, Section 2 provides more details about the different forms of hardness and their current usage for both symmetric and asymmetric hardness. We also introduce the first asymmetrically memory-hard function, Diodon, in Section 2.4.3. Then, Section 3 presents our generic approach for dealing with all forms of hardness at once. To this end, plugs achieving all forms of hardness are introduced in the same section. We deduce practical modes of operation for building hard block ciphers and hard sponges which are described in Section 4. Our concrete proposals, called Skipper and Whale, are introduced in Section 5.

Enforcing Hardness

In this section, we argue that many recent ideas in symmetric cryptography can be interpreted as particular cases of a single general concept. The aim of several a priori different research areas can be seen as imposing the use of important resources for performing basic operations or in other words, bind an operation to a specific form of hardness. We restrict ourselves to the basic case of a well-defined function mapping each input to a unique output. It means in particular that protocols needing several rounds of communication or randomized algorithms which may return any of the many valid solution to a given problem such as HashCash (see below) are out of our scope. We also tie each function to an algorithm evaluating it: further below, functionally equivalent functions evaluated using different algorithms are considered like different functions. Thus, the "hardness" discussed is the hardness of the algorithm tied to the function.

The three main metrics for assessing the efficiency of an algorithm are its time complexity, its RAM usage and its code size. As we explain below, different lines of research in symmetric cryptography can be interpreted as investigating the design of algorithms such that one of these metrics is abnormally high and cannot be reduced while limiting the impact on the other two as much as possible.

Time-hardness is discussed in Section 2.1, memory-hardness in Section 2.2 and code-hardness in Section 2.3. Finally, in Section 2.4, we present the general notion of asymmetric hardness.

It is also worth mentioning that the three forms of hardness are not completely independent from one another. For example, due to the number of memory access needed in order for a function to be memory-hard, a function with this property cannot be arbitrarily fast.

Time Hardness

While the time efficiency of cryptographic primitives is usually one of the main design criteria, there are cases where the opposite is needed. That is, algorithms which can be made arbitrarily slow in a controlled fashion.

One of the most simple approaches is the one used for instance by the key derivation function PBKDF2 [START_REF] Kaliski | PKCS #5: Password-Based Cryptography Specification Version 2[END_REF]. This function derives a cryptographic key from a salt and a password by iterating a hash function multiple times, the aim being to frustrate brute-force attacks. Indeed, while the password may be from a space small enough to be brute-forced, evaluating the key derivation function for each possible password is made infeasible by its time-hardness.

Somewhat similarly, proofs-of-work such as HashCash (used by the cryptocurrency Bitcoin [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]) consist in finding at least one of many solutions to a given problem. The hardness in this case comes from luck. Miners must find a value such that the hash of this value and the previous block satisfies the difficulty constraint. However, the subset of such valid values is sparse and thus miners have to try many random ones. Two different miners may find two different but equally valid values. Because of this randomness, such puzzles are out of our scope. In this paper, we only consider functions which are equally hard to evaluate on all possible inputs, not puzzles for which finding a solution is hard on average. Furthermore, in order to mitigate the impact of adversaries with vast amount of processors at their disposal, we consider sequential time-hardness. Using a parallel computer should not help an attacker in evaluating the function much quicker. Formalizing parallel time hardness the way we do it for sequential time-hardness is left as a future work.

Overall, the goal of time-hardness is to prevent an adversary from computing a function in a time significantly smaller than the one intended. In other words, it must be impossible to compress the amount of time needed to evaluate the function on a random input.

Memory Hardness

Informally, a function is memory-hard if even an optimized implementation requires a significant amount of memory. For each evaluation, a large amount of information is written and queried throughout the computation. As a consequence, a memory-hard function cannot be extremely fast.

A function requiring large amounts of RAM for its computation prevents attacker from building ASICs filled with huge number of cores for parallel computations. This implies that memory-hard functions make good password hashing functions and proofs-of-work. One of the first to leverage this insight was the hash function scrypt [START_REF] Percival | Stronger key derivation via sequential memory-hard functions[END_REF] which was recently formally proved to be memory-hard in [ACP + 17]. More recently several other memory-hard algorithms have been designed, such as the password hashing competition winner Argon2 [START_REF] Biryukov | Argon2: new generation of memory-hard functions for password hashing and other applications[END_REF] as well as the more recent Balloon Hashing [START_REF] Boneh | Balloon hashing: A memory-hard function providing provable protection against sequential attacks[END_REF] and Equihash [START_REF] Biryukov | Equihash: Asymmetric proof-of-work based on the generalized birthday problem[END_REF]. Those can be used as building blocks to create memoryhard proofs-of-work which can offset the advantage of cryptocurrency miners using dedicated ASICs.

The idea of using memory-hard functions for general purpose computations was further explored in the context of egalitarian computing [START_REF] Biryukov | Egalitarian computing[END_REF]. Similarly, proofs of space [START_REF] Dziembowski | Proofs of space[END_REF][START_REF] Ateniese | Proofs of space: When space is of the essence[END_REF] are protocols which cannot be run by users if they are not able to both read and write a large amount of data. However, those are interactive protocols and not functions.

The recent research investigating memory-hardness has lead to several advances in our understanding of this property. For example, the difference between amortized and peak memory hardness was highlighted in [START_REF] Alwen | High parallel complexity graphs and memory-hard functions[END_REF].

Code Hardness

First of all, let us clarify the distinction we make between memory and codehardness. With code-hardness, we want to increase the space needed to store information that is needed to evaluate a function on all possible inputs. However, the information itself does not depend on said input. During evaluation of the function, it is only necessary to read the memory in which the code is stored. In contrast, memory-hardness deals with the case where we need to store a large amount of information which depends on the function input and which is thus different during each evaluation of the function. In this case, one must be able to both read and write to the memory. Furthermore, in a typical code-hard function, only a small fraction of the whole information stored in the implementation is read during each call to the function. On the other hand, if a memory-hard function uses 𝑀 bytes of memory, then all of those bytes will be written and read at least once.

Code-hardness is very close to what was first defined as memory-hard whitebox implementation (or weak white-box) in the paper introducing the ASASA crypto-system [START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[END_REF], and later formalized under different names as (𝑀, 𝑧)space hardness [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF][START_REF] Bogdanov | Towards practical whitebox cryptography: Optimizing efficiency and space hardness[END_REF] or as incompressibility in [START_REF] Fouque | Efficient and provable white-box primitives[END_REF] following the more general definition from [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF]. In all cases, the aim is the same: the block cipher implementation must be such that it is impossible to write a functionally equivalent implementation with a smaller code. This stands in contrast to strong white-box cryptography (as defined in [START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[END_REF]) where inverting a function given its white-box implementation should be impossible. We do not consider this case in this paper.

As was pointed out in [START_REF] Fouque | Efficient and provable white-box primitives[END_REF], what we call code-hardness is also the goal of so-called big-key encryption. For instance, the XKEY2 scheme introduced in [START_REF] Bellare | Big-key symmetric encryption: Resisting key exfiltration[END_REF] achieves this goal: it uses a huge table and a nonce to derive a key of regular size (say, 128 bits) to be used in a standard encryption algorithm, e.g. a stream cipher. Bellare et al. show that even if an attacker manages to obtain half of the huge table, i.e. half of the code needed to implement the scheme, then they are still unable to compute the actual encryption key with non-negligible probability. Using our terminology, XKEY2 can be seen as a code-hard key derivation function. A more detailed analysis of the literature on code-hardness is provided in Appendix A.2.

The concept of proof of storage can also be interpreted as a particular type of code-hard protocol. Indeed, in such algorithms, challengers must prove that they have stored a given file.

Asymmetric Hardness

In this section, we discuss the concept of asymmetric hardness which introduces two classes of users. Common users evaluate a hard function but privileged users, who know a secret key, can evaluate a functionally equivalent function which is not hard. We also introduce Diodon, the first asymmetrically memoryhard function.

Asymmetric Code-Hardness

The most recent white-box block ciphers such as SPACE [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF], the Puppy-Cipher [START_REF] Fouque | Efficient and provable white-box primitives[END_REF] and SPNbox [START_REF] Bogdanov | Towards practical whitebox cryptography: Optimizing efficiency and space hardness[END_REF] can be seen as providing asymmetric code-hardness. Indeed, while the first aim of these algorithms is to provide regular code-hardness, referred to as "space-hardness" for the former and "incompressibility" for the latter, they both allow the construction of far more code-efficient implementation. For both SPACE and the PuppyCipher, the idea is to compute a large table containing the encryptions of the first 2 𝑡 integers with AES-128 for 𝑡 in {8, 16, 24, 32}. These tables are then used as the codehard part of the encryption which cannot be compressed because doing so would require a break of the AES. However, a user knowing the 128-bit AES key can get rid of these tables and merely recompute the entries needed on the fly, thus drastically decreasing the code-hardness of the implementation.

In fact, both constructions can be seen as structures intended to turn an asymmetrically code-hard function into an asymmetrically code-hard block cipher. In both cases, the asymmetrically code-hard function consists in the evaluation of the AES on a small input using either the secret key, in which case the implementation is not code-hard, or using only the public partial codebook which, because of its size, is code-hard.

Time-Hardness

While the asymmetry of its hardness was not insisted upon, there is a known asymmetrically time-hard function, which we call RSA-lock. It was proposed as a time-lock in [START_REF] Rivest | Time-lock puzzles and timed-release crypto[END_REF], that is, a function whose output cannot be known before a certain date.

It is based on the RSA cryptosystem [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF]. It consists in iterating squarings in an RSA modular ring: a user who does not know the prime factor decomposition of the modulus 𝑁 must perform 𝑡 squarings while a user who knows that 𝑁 = 𝑝𝑞 can first compute 𝑒 = 2 𝑡 mod (𝑝 -1)(𝑞 -1) and then raise the input to the power 𝑒. If 𝑡 is large enough, the second approach is much faster.

Memory-Hardness

We are not aware of any asymmetrically memory-hard function in the existing literature. Thus, we propose the first such function which we call Diodon. It is based on the ROMix function used to build scrypt [START_REF] Percival | Stronger key derivation via sequential memory-hard functions[END_REF] and relies on the RSA crypto-system to provide the asymmetry, much like in RSA-lock.

Diodon maps an element 𝑥 of {0, 1} 𝑡 to a an element 𝑦 of {0, 1} 𝑢 using RSA computations and a hash function 𝐻. It is parametrized by an RSA modulus 𝑁 of size 𝑛 𝑝 , a hash function 𝐻 and its input and output sizes 𝑡 and 𝑢. Only privileged users know the prime factor decomposition of the RSA modulus. Finally, a parameter 𝑀 is used to tune its memory-hardness while parameters 𝐿 and 𝜂 decide its time complexity. The computation is described in Algorithm 1 and in Figure 1. In both, 𝑇 𝑢 denotes the function truncating a bitstring to its 𝑢 bits of lowest weight. A user without knowledge of the factorization of 𝑁 must use Algorithm 1 to evaluate Diodon(𝑥). However, if a user knows the factorization of 𝑁 = 𝑞𝑞 ′ , she does not need to store the vector 𝑉 . Indeed, she can simply evaluate 𝑉 𝑖 = 𝑥 2 𝑖×𝜂 mod 𝑁 in constant time by first reducing 2 𝑖×𝜂 modulo (𝑞 -1)(𝑞 ′ -1) and then raising 𝑥 to the corresponding exponent. One may call her ability to access an arbitrary element of 𝑉 in constant time an RSA RAM. Her evaluation strategy is summarized in Algorithm 2. Basic users need to perform 𝜂×𝑀 RSA squarings while privileged ones need to perform roughly (𝐿 + 1) × 𝑛 𝑝 of those as 𝑒 and each exponent 𝑒 𝑗 is a priori of length 𝑛 𝑝 .

Algorithm 2 Diodon for privileged users Inputs: 𝑡-bit block 𝑥; RSA factors 𝑞, 𝑞 ′ ; 𝜂; 𝑀, 𝑇 ;

Output: 𝑢-bit output 𝑦 𝑒 = 2 (𝑀 -1)×𝜂 mod (𝑞 -1)(𝑞 ′ -1) 𝑆 = 𝑥 𝑒 mod (𝑞𝑞 ′ ) for all 𝑖 ∈ {0, ..., 𝐿 -1} do 𝑗 = 𝑆 mod 𝑀 𝑒 𝑗 = 2 𝑗×𝜂 mod (𝑞 -1)(𝑞 ′ -1) 𝑆 = 𝐻 ( 𝑆, (𝑥 𝑒𝑗 mod (𝑞𝑞 ′ )) ) end for return 𝑇 𝑢 (𝑆)
Let us first consider the simplest parameters, that is 𝜂 = 𝑛 𝑝 and 𝐿 = 𝑀 . In this case, the time complexity for both users is comparable as each class of user needs to perform 𝑀 RSA encryptions.1 Furthermore, without the knowledge of the secret key, the computation is essentially scrypt ROMix function which was shown to be optimally linearly memory hard [ACP + 17], keeping time-memory product constant. It means that it is either necessary to store all the values 𝑉 𝑖 for the computation or any algorithm that saves a factor 𝑓 in memory will have to pay the same factor in time.

The choice of the parameters 𝜂, 𝑀, 𝐿 and 𝑛 𝑝 has a significant impact on the time efficiency of Diodon. It is investigated in Appendix A.1 where we also propose some concrete instances.

A Generic Framework

As we have seen, all the techniques presented in the sections above are intended to enforce some form of computational hardness. In this section, we present a unified framework for building any symmetric algorithm with some form of guaranteed hardness. We describe our aim in Section 3.1 and our design strategy with the generic hardness definition it is based on in Section 3.2. Our constructions need small functions with the intended hardness type to be bootstrapped.

We provide examples of those in Section 3.3.

Design Strategy

Our aim is to design a general approach to build any cryptographic primitive with any form of hardness. To achieve this, we will build modes of operations allowing us to combine secure cryptographic primitives, such as the AES block cipher [START_REF] Daemen | The design of Rijndael: AESthe advanced encryption standard[END_REF] or the Keccak sponge [START_REF] Bertoni | Keccak specifications[END_REF], with small functions called plugs. These plugs are simple functions with the desired form of hardness.

Our modes of operations, which are presented in Section 4, are all based on the same principle: ensuring that enough plug calls with an unpredictable input are performed so as to guarantee that, with overwhelming probability, an adversary cannot bypass the hardness of all plug evaluations. This ensures that the full complexity of a plug evaluation is paid at least once.

Indeed, regardless of the hardness form considered, the strategy of a generic adversary will always be the same. Provided that the plugs are indeed hard to evaluate, the only strategy allowing an adversary to bypass their hardness consists in storing a (feasibly) large number of plug outputs in a database and then querying those. If 2 𝑝 outputs of a plug 𝑃 : {0, 1} 𝑡 → {0, 1} 𝑣 have been stored, the plug can be evaluated successfully without paying for its hardness with probability 2 𝑝-𝑡 .

An alternative strategy using the same space consists in storing 2 𝑝 (𝑣/𝑑) partial outputs of length 𝑑. In this case, the success probability becomes 2 𝑝-𝑡 (𝑣/𝑑)× 2 𝑑-𝑣 : the input is partially known with a higher probability 2 𝑝-𝑡 (𝑣/𝑑) but (𝑣-𝑑) bits of the output remain to be guessed. This method is (𝑣/𝑑) × 2 𝑑-𝑣 more efficient than the basic one but, for 1 ≤ 𝑑 < 𝑣, this quantity is always smaller than one. The strategy consisting in storing full outputs is therefore the best.

However, if the output size of the plug is small enough, it might be more efficient for the adversary to directly guess the whole output. The probability that an adversary merely guessing the output of the plug gets it right2 is 2 -𝑣 .

Our aim is therefore to guard our constructions from the adversary defined below. Protecting our structure against those is sufficient to reduce their hardness to that of the plug they use. Recall that we tie each function to a specific algorithm evaluating it. Thus, the hardness is actually that of the corresponding algorithm.

Definition 1 (2 𝑝 -adversary). Let 𝑓 be a time-, memory-or code-hard function. A 2 𝑝 -adversary is an adversary trying to generate a function 𝑓 ′ which does not have the hardness of 𝑓 but which does not have access to more memory than needed to store 2 𝑝 outputs of 𝑓 .

A 2 𝑝 -adversary can perform more than 2 𝑝 calls to the function it is trying to approximate when generating 𝑓 ′ , although 𝑓 ′ itself cannot have access to more than 2 𝑝 of those. Still, 𝑓 ′ can perform additional computations using the information stored during its generation.

However, the computational power of this adversary is not unbounded. More precisely we consider only 2 𝑝 -adversaries which cannot perform more than 2 100 operations. This means for example that recovering a 128-bit AES key is out of their reach. We are not interested in guarding against unrealistic, computationally unbounded adversaries.

Similarly, the complexity of the plug approximation along the other axes cannot be arbitrarily high. Consider a code-hard function 𝑓 which uses a table 𝑠 of 𝑀 bits and an approximation 𝑓 ′ which works as follow:

1. Evaluate and store several values of 𝑓 (𝑖) for random inputs 𝑖 using far fewer than 𝑀 bits of storage.

2. When given a random input 𝑥:

(a) brute-force all possible values of 𝑠, i.e. 2 𝑀 values using 𝑀 bits of RAM to store each candidate table 𝑠 ′ ;

(b) try each candidate 𝑠 ′ to see if they yield 𝑓 ′ (𝑖) = 𝑓 (𝑖) using the values of 𝑓 (𝑖) previously stored;

(c) once the right 𝑠 has been found, use it to evaluate 𝑓 ′ (𝑥), return it and then erase 𝑠 ′ .

Such an approximation 𝑓 ′ is not code-hard, it merely needs enough space to store 𝑓 (𝑖) for several 𝑖. However, it is memory-hard since it needs to store the same amount of information as is stored in the implementation of 𝑓 , although the storage is in RAM rather than code. Much more importantly, its timehardness is astronomical: 𝑀 will typically be in the millions, if not the billions, meaning that enumerating all 2 𝑀 candidates 𝑠 ′ is utterly impossible. We explicitly do not consider such extreme trade-offs: in our cases, the hardness of 𝑓 remains practical-though expensive-, meaning that a 2 𝑝 -adversary trying to bypass its hardness is trying to optimize an already usable implementation. It does not make sense for her to trade code-hardness for a wildly impractical time-hardness.

Theoretical Framework

Generic Symmetric Hardness

We are now ready to formally define hardness. We use a generalization to all forms of hardness of the incompressibility notion from [START_REF] Fouque | Efficient and provable white-box primitives[END_REF].

Definition 2 (R-hardness). We say that a function 𝑓 : 𝒳 → 𝒴 is R-hard against 2 𝑝 -adversaries for some tuple R = (𝜌, 𝑢, 𝜖(𝑝)) with 𝜌 ∈ {Time, Code, RAM} if evaluating the function 𝑓 using less than 𝑢 units of the resource 𝜌 and at most 2 𝑝 units of storage is possible only with probability 𝜖(𝑝). More formally, the probability for a 2 𝑝 -adversary to win the efficient approximation game, which is described below, must be upper-bounded by 𝜖(𝑝).

1. The challenger chooses a function 𝑓 from a predefined set of functions requiring more than 𝑢 units of 𝜌 to be evaluated.

2. The challenger sends 𝑓 to the adversary.

3. The adversary computes an approximation 𝑓 ′ of 𝑓 which, unlike 𝑓 , can be computed using less than u units of the resource 𝜌.

4. The challenger picks an input 𝑥 of 𝒳 uniformly at random and sends it to the adversary.

The adversary wins if 𝑓

′ (𝑥) = 𝑓 (𝑥).
This game is also represented in Figure 2. The approximation 𝑓 ′ computed by the adversary must be evaluated using significantly less than 𝑢 units of the resource 𝜌, although the precomputation may have been more expensive.

challenger 2 𝑝 -adversary Choose 𝑓 𝑓 𝑓 ′ ← Precompute(𝑓 ) 𝑥 $ ← -𝒳 𝑥 𝑓 ′ (𝑥) 𝑓 (𝑥) = 𝑓 ′ (𝑥)?
Figure 2: The game corresponding to the definition of (𝜌, 𝑢, 𝜖(𝑝))-hardness against 2 𝑝 -adversaries.

In order for this definition to be relevant, the power of the adversary must be estimated. For example, preventing attacks from 2 512 -adversaries would most definitely be over engineering and, conversely, preventing attacks from 2 20 -adversaries would be useless since such precomputation is always feasible.

Our definition is not the strongest in the sense that it does not encompass e.g. "strong space-hardness" [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF]. This definition of code-hardness aims at preventing the attacker from encrypting a plaintext of their choosing, a far stronger requirement than preventing the encryption of a random plaintext.

In the efficient approximation game described above, 𝑓 ′ must be less hard than 𝑓 along the appropriate axis. For example, if 𝑓 is code-hard then the code implementing 𝑓 ′ must be significantly smaller than that implementing 𝑓 , meaning that the game corresponding to code-hardness when 𝑓 is an encryption algorithm is essentially the same as the one used in the definition of encryption incompressibility [START_REF] Fouque | Efficient and provable white-box primitives[END_REF]. Indeed, the computation of 𝑓 ′ and its use by the adversary corresponds in this case to the computation of the leakage function on the secret large table and its use by the adversary to approximate the original table.

In the case of code-hardness the maximum code size of the implementation of 𝑓 ′ must coincide with the power of the 2 𝑝 -adversary. Indeed, the implementation of the approximation 𝑓 ′ needs at least enough space to store 2 𝑝 outputs of the plug.

For time-hardness, the time is measured in number of simple operations. For example, if a function requires evaluating a hash function 𝑡 times, the unit of time is a hash computation. Memory-and code-hardness are measured in bytes. In our examples, code-hardness is achieved not by using programs with a complex logic but by forcing them to include large and incompressible tables. Much like in most recent white-box block ciphers, the size of the logic of the program is considered to be negligible and the size of the implementation is reduced to that of its incompressible tables.

A function which is easy to compute on a subset of its domain or whose output is not uniformly distributed in its range can still be (𝜌, 𝑢, 𝜖)-hard as such limitations can be taken into account by modifying the 𝜖 factor. For example, if a function is easy to evaluate on a fraction 𝑓 of its domain then this limitation is simply captured by the fact that 𝜖 ≥ 1/𝑓 .

Generic Asymmetric Hardness

This generic definition is easily generalized to encompass asymmetric hardness.

Definition 3 (Asymmetric R-hardness). We say that a function 𝑓 : 𝒳 → 𝒴 is asymmetrically R-hard against 2 𝑝 -adversaries for some tuple R = (𝜌, 𝑢, 𝜖(𝑝)) with 𝜌 ∈ {Time, Code, RAM} if it is impossible for a 2 𝑝 -adversary to win the approximation game of Definition 2 with probability higher than 𝜖(𝑝), unless a secret 𝐾 is known. If this secret is known then it is possible to evaluate another function 𝑓 𝐾 which is is functionally equivalent to 𝑓 but does not have its hardness.

An immediate consequence of this definition is that extracting the secret key 𝐾 from the description of 𝑓 must be computationally infeasible. Otherwise, the adversary could simply recover 𝐾 during the precomputation step, use 𝑓 𝐾 as their approximation and then win the approximation game with probability 1. This observation is reminiscent of the unbreakability notion presented in [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF].

White-box block ciphers are simple example of asymmetrically code-hard functions. This concept can also be linked to the proof of work or knowledge presented in [START_REF] Baldimtsi | Indistinguishable proofs of work or knowledge[END_REF]. It is a proof of work where a solution can be found in a more efficient way if a secret is known.

Asymmetric hardness is a different notion from public key encryption. Indeed, in the latter case, the whole decryption functionality is secret. In our case, the functionality is public. What is secret is a method to evaluate it efficiently.

A Counter-Example

The inversion of a one-way function may seem like a natural example of a timehard function. However, as described below, it may not satisfy the requirements of our definition of (Time, 𝑢, 𝜖(𝑝))-hardness.

Let ℎ : {0, 1} 50 → {0, 1} 50 be the function mapping a 50-bit string to the first 50 bits of their SHA-256 digest and let 𝑓 be the inverse of ℎ. In other words, 𝑓 returns a preimage of a given digest. This function may seem time-hard at first glance as SHA-256 is preimage resistant. More specifically, it might be expected to be about (Time, 2 50 , 2 -20 )-hard against a 2 30 -adversary. However, as is well known, such constructions can be attacked using Hellman's tradeoff [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF] in the form of rainbow-tables allowing an attacker to recover a preimage in far less time at the cost of significant but practical pre-computation and storage. If 𝑀 is the size of this table and 𝑇 is the time complexity of an inversion using this table then it must hold that 𝑀 𝑇 2 = 𝑁 2 where 𝑁 = 2 50 in our case. The failure of 𝑓 to be time-hard in the sense of Definition 2 can be seen in the following strategy to win the approximation game.

2. The 2 30 -adversary precomputes Hellman-type rainbow tables with in total 2 30 entries using about 2 50 calls to ℎ. This adversary chooses 𝑀 = 2 30 and 𝑇 = 𝑁/ √ 𝑀 = 2 35 .

3. The challenger chooses a random value 𝑥 ∈ {0, 1} 50 and sends it to the adversary.

4. With high probability, the adversary computes 𝑓 (𝑥) using their precomputed table in time 𝑇 = 2 35 which is 2 15 times smaller than the time needed for brute-force.

Thus, such a function is not time-hard in the sense of Definition 2.

Examples of Plugs

As our modes rely on smaller R-hard function to achieve their goal, we describe an array of such components, one for each hardness goal. A summary of all the plugs we describe, along with what we consider to be their hardness against 2 𝑝 -adversaries, is given in Table 2.

Hardness Symmetric Asymmetric Time IterHash 𝑡 𝜂 RSAlock 𝑡 𝜂 (Time, 𝜂, 2 𝑝-𝑡 ) (Time, 𝜂, 2 𝑝-𝑡 ) Memory Argon2 Diodon (RAM, 𝑀/5, 2 𝑝-𝑡 ) (RAM, 𝑀/10, 2 𝑝-𝑡 ) Code BigLUT 𝑡 𝑣 BcCounter 𝑡 𝑣 (Code, 2 𝑝 , 2 𝑝-𝑡 ) (Code, 2 𝑝 , 2 𝑝-𝑡 )
Table 2: Possible plugs, i.e. sub-components for our constructions which we assume to be R-hard against 2 𝑝 -adversaries.

While we provide an intuition on why we assume these plugs to have the hardnesses we claim, we do not prove that it is the case.

If the output it is too large to be used in a higher level construction then it is possible to truncate it to 𝑣 bits. If we denote 𝑇 𝑣 the function discarding all but the first 𝑣 bits of its input and if 𝑃 is a plug with a 𝑡-bit input which is (𝜌, 𝑢, 𝜖(𝑝))hard against 2 𝑝 -adversaries, then 𝑥 ↦ → 𝑇 𝑚 (𝑃 (𝑥)) is (𝜌, 𝑢, max(𝜖(𝑝), 2 𝑝-𝑡 ))-hard against 2 𝑝 -adversaries. Overall, the probability of success of an approximation made by a 2 𝑝 -adversary of a plug mapping 𝑡 to 𝑣 bits is lower-bounded by max(2 -𝑣 , 2 𝑝-𝑡 ) if its output is uniformly distributed in its range.

Time-Hard plug

This hardness has been considered in previous works for instance in the context of key stretching and key derivation or for time-lock encryption. In fact, the constructions proposed for each use case can be used to provide time-hardness and asymmetric time-hardness respectively. Symmetric Hardness. IterHash 𝑡 𝜂 iterates a 𝑡-bit hash function on a 𝑡-bit input block 𝜂 times where 𝜂 must be much smaller than 2 𝑡/2 to avoid issues related to the presence of cycles in the functional graph of the hash function. If we denote by 𝐻 the hash function used, then IterHash 𝑡 𝜂 (𝑥) = 𝐻 𝜂 (𝑥). Evaluating this function requires at least 𝜂 hash function calls and, provided that the hash function iterated is cryptographically secure, it is impossible for an adversary to guess what the output is after 𝜂 iterations with probability higher than 2 -𝑡/2 . We consider that this function is (Time, 𝜂, 2 𝑝-𝑡 )-hard against 2 𝑝 -adversaries, as long as 𝑝 ≪ 𝑡/2. Asymmetric Hardness. RSAlock 𝑡 𝜂 is a function performing 𝜂 squaring in a RSA modular ring of size 𝑁 = 𝑞𝑞 ′ ≈ 2 𝑡 , where 𝑞 and 𝑞 ′ are secret primes. Using these notations, RSAlock 𝑡 𝜂 (𝑥) = 𝑥 2 𝜂 mod 𝑁 . The common user therefore needs to perform 𝜂 squarings in the modular ring.

However, a user who knows the prime decomposition of the RSA modulo can first compute 𝑒 = 2 𝜂 mod (𝑞 -1)(𝑞 ′ -1) and thus compute RSAlock 𝑡 𝜂 (𝑥) = 𝑥 𝑒 mod 𝑁 . Furthermore, such a user can also use the Chinese remainder theorem to further speed up the computation which increases their advantage over common users. Thus, as long as 𝑡 > 𝑛, the privileged user has an advantage over the common. We consider that RSAlock 𝑡 𝜂 is asymmetrically (Time, 𝜂, 2 𝑝-𝑡 )-hard against 2 𝑝 -adversaries.

Code-Hard plug

As explained in Section 2.3, the main goals of code-hardness are white-box and big-key encryption. The structures used for both purposes rely on the same building block, namely a large look-up table where the entries are chosen uniformly at random or as the encryption of small integers. The former, BigLUT 𝑡 𝑣 , is code-hard. The latter, BcCounter 𝑡 𝑣 , is asymmetrically code-hard. Furthermore, an identical heuristic can be applied to both of them to increase the input size of the plug while retaining a practical code size. It is described at the end of this section. This function is (Code, 2 𝑝 , 2 𝑝-𝑡 )-hard against 2 𝑝 -adversaries. Indeed, an adversary who has access to 2 𝑝 outputs of the function cannot evaluate it efficiently on a random input with probability more than 2 𝑝-𝑡 . Simply guessing the output succeeds with probability 2 -𝑣 which is usually much smaller than 2 𝑝-𝑡 . Thus, we consider that BigLUT 𝑡 𝑣 is (Code, 2 𝑝 , 2 𝑝-𝑡 )-hard against 2 𝑝 -adversaries.

Symmetric

Asymmetric Hardness. BcCounter 𝑡 𝑣 is the function mapping a 𝑡-bit integer 𝑥 to the 𝑣-bit block 𝐸 𝑘 (0 𝑣-𝑡 ||𝑥), where 𝐸 𝑘 is a 𝑣-bit block cipher with a secret key 𝑘 of length at least 𝑣. A common user would be given the codebook of this function as a table of 2 𝑡 integers while a privileged user would use the secret key 𝑘 to evaluate this function.

The hardness of BcCounter 𝑡 𝑣 is the same as that of BigLUT 𝑡 𝑣 for a common user. The contrary would imply the existence of a distinguisher for the block cipher, which we assume does not exist. However, a privileged user with knowledge of the secret key used to build the table can bypass this complexity.

Furthermore, as the key size is at least as big as the block size in modern block ciphers, an adversary guessing the key is not more efficient than one who merely guesses the output of the cipher. Thus, we consider that BigLUT 𝑡 𝑣 is asymmetrically (Code, 2 𝑝 , 2 𝑝-𝑡 )-hard.

Increasing the input size. Both BigLUT 𝑡 𝑣 and BcCounter 𝑡 𝑣 have a low input size and leave a fairly high success probability for an attacker trying to win the efficient approximation game without using a lot of resource. An easy way to work around this limitation is to use ℓ > 1 distinct instances of a given function in parallel and XOR their outputs. For example, 𝑥 ↦ → 𝑓 (𝑥) where

𝑓 (𝑥 0 ||...||𝑥 ℓ-1 ) = ⊕ ℓ-1 𝑖=0 𝐸 𝑘 (byte(𝑖)||0 𝑛-𝑡-8 ||𝑥 𝑖 )
and where byte(𝑖) denotes the 8-bit representation of the integer 𝑖 combines ℓ different instances of BcCounter 𝑡 𝑣 . We consider that, against 2 𝑝 -adversaries, it is asymmetrically

( Code, 2 𝑝 , max(2 𝑝-𝑣 , (2 𝑝-𝑡 /ℓ) ℓ )
) -hard. Indeed, an attacker could store 2 𝑝 /ℓ entries of each of the ℓ distinct tables, in which case they can evaluate the whole function if and only if all the table entries they need are among those they know. This happens with probability (2 𝑝-𝑡 /ℓ) ℓ . Alternatively, they could store the output of the whole function for about 2 𝑝 values of the complete input. In that case, they can evaluate the function if and only if the whole input is one that was precomputed, which happens with probability 2 𝑝-𝑣 . We assume that there is not better attack for a 2 𝑝 -adversary than the ones we just described, hence the hardness we claimed.

It is also possible to use a white-box block cipher as an asymmetrically code-hard function as this complexity is precisely the one they are designed to achieve.

Memory-Hard plug

Definition 2, when applied to the case of memory hardness, corresponds to functions for which a reduction in the memory usage is either impossible or extremely costly in terms of code or time complexity. We are not aware of any function satisfying the first requirement but, on the other hand, there are many functions for which a decrease in memory is bound to cause a quantifiable increase in time complexity. These are the functions we consider here. Symmetric Hardness. Several recent functions are intended to provide memoryhardness. The main motivation was the Password Hashing Competition (PHC) which favored candidates enforcing memory-hardness to thwart the attacks of adversaries using ASICs to speed up password cracking.

The winner of the PHC competition, Argon2 [START_REF] Biryukov | Argon2: new generation of memory-hard functions for password hashing and other applications[END_REF], uses 𝑀 bytes of memory to hash a password, where 𝑀 can be chosen by the user. It was designed so that an adversary trying to use less than 𝑀/5 bytes of memory would have to pay a significant increase in time-hardness. Using our definition, if 𝑡 is the size of a digest (this quantity can also be chosen by the user) and 𝑣 is the size of the input, then Argon2 is about (RAM, 𝑀/5, 2 𝑝-𝑡 )-hard against 2 𝑝adversaries as long as enough passes are used to prevent ranking and sandwich attacks [START_REF] Alwen | Efficiently computing dataindependent memory-hard functions[END_REF][START_REF] Alwen | Towards practical attacks on Argon2i and balloon hashing[END_REF] and as long as 2 𝑝-𝑡 > 2 -𝑣 .

The construction of memory-hard functions is a very recent topic. Only a few such functions are known, which is why Argon2 and Diodon are far more complex than the other plugs proposed in this section. It is an interesting research problem to build a simpler memory hard function with the relaxed constraint that it might be cheap to compute on a part of its domain, a flaw which would easily be factored into the 𝜖(𝑝) probability.

Asymmetric Hardness. The only asymmetrically memory-hard function we are aware of is the one we introduced in Section 2.4.3, Diodon. Because of its proximity with scrypt, we claim that it is (RAM, 𝑀/10, 2 -𝑢 )-hard for basic users [ACP + 17]. In other words, we consider that Diodon is asymmetrically (RAM, 𝑀/10, 2 𝑝-𝑡 )-hard -under the assumption, as for Argon2, that 2 𝑝-𝑡 > 2 -𝑢 . Note however that [ACP + 17] guarantees only linear penalties if attacker trades memory for time, while modern memory-hard functions like Ar-gon2 provide superpolynomial penalties. This leads us to the following open problem.

Open Problem 1. Is it possible to build an asymmetrically memory-hard function for which the time-memory tradeoff is superpolynomial, i.e. such that dividing its memory usage by a factor 𝛼 must mutiply its execution time by 𝛼 𝑑 for some 𝑑 > 1?

Modes of Operations for Building Hard Primitives

As said above, our strategy is to combine hard plugs with secure cryptographic primitives in such a way that the input of the plugs are randomized and that enough such calls are performed to ensure that at least one plug evaluation was hard with a high enough probability. The method we use is nicknamed plugthen-randomize. It is formalized in Section 4.1. Then, the block cipher and the sponge mode of operation based on it are introduced respectively in Sections 4.2 and 4.3. Unfortunately, our security arguments are not as formal as those used in the area of provable security. Our main issue is that we are not trying to prevent the adversary from recovering a secret: in fact, there is none in the case of symmetric hardness! Furthermore, since an (inefficient) implementation is public, we cannot try to prevent the attacker from distinguishing the function from an ideal one. It is our hope that researchers from the provable security community will suggest directions for new and more formal arguments. |𝑥 ′ | = 𝑚 -𝑡 -𝑣 to 𝑦 defined by:

Plug-Then-Randomize

(𝐹 • 𝑃 )(𝑥 𝑡 || 𝑥 𝑣 || 𝑥 ′ ) = 𝑦 = 𝐹 (𝑥 𝑡 || 𝑥 𝑣 ⊕ 𝑃 (𝑥 𝑡 ) || 𝑥 ′ ) .
This computation is summarized in Figure 3.

Lemma 1 (Plugged Function Hardness). If 𝑃 : {0, 1} 𝑡 → {0, 1} 𝑣 is a plug (𝜌, 𝑢, 𝜖(𝑝))-hard against 2 𝑝 -adversaries and if 𝐹 : {0, 1} 𝑛 → {0, 1} 𝑛 is a public random (permutation) oracle then the plugged function (𝐹 • 𝑃 ) is (𝜌, 𝑢, 𝜖(𝑝))hard.

Proof. First, the adversary could try and store 2 𝑝 outputs of (𝐹 • 𝑃 ). However, such an approximation would work only with probability 2 𝑝-𝑛 < 2 𝑝-𝑣 ≤ 𝜖, so that it is less successful than an approximation based on an approximation of the plug. Without knowledge of the full input of 𝐹 , it is impossible to predict its output because 𝐹 is a random (permutation) oracle. Therefore, we simply need to show that the function ℱ 𝑃 mapping (𝑥, 𝑦, 𝑧) of {0, 1} 𝑡 × {0, 1} 𝑣 × {0, 1} 𝑛-𝑡-𝑣 to (𝑥, 𝑦 ⊕ 𝑃 (𝑥), 𝑧) is as hard as 𝑃 itself.

By contradiction, suppose that there is an adversary 𝒜 capable of winning the approximation game for ℱ 𝑃 . That is, 𝒜 can compute an approximation ℱ ′ 𝑃 of ℱ 𝑃 using less than 𝑢 units of the resource 𝜌 which works with probability strictly higher than 𝜖(𝑝). Then 𝒜 can win the approximation game for 𝑃 itself as follows. When given 𝑃 , 𝒜 computes the approximation ℱ ′ 𝑃 of the corresponding function ℱ 𝑃 . Then, when given a random input 𝑥 of 𝑃 of length 𝑡, 𝒜 concatenates it with random bitstrings 𝑦 and 𝑧 of length 𝑣 and 𝑛 -𝑡 -𝑣 respectively. The output of 𝑃 is then approximated as the 𝑣 center bits of ℱ ′ 𝑃 (𝑥||𝑦||𝑧) ⊕ (𝑥||𝑦||𝑧) = 0 𝑡 ||𝑃 (𝑥)||0 𝑛-𝑡-𝑣 . Thus, 𝒜 can violate the (𝜌, 𝑢, 𝜖(𝑝))hardness of 𝑃 .

We deduce that if 𝑃 is (𝜌, 𝑢, 𝜖(𝑝))-hard, then so is ℱ 𝑃 and thus (𝐹 • 𝑃 ).

Using this lemma, we can prove the following theorem which will play a key role in justifying the R-hardness of our later constructions.

Theorem 1 (Iterated Plugged Function Hardness). Let 𝐹 𝑖 , 𝑖 < 𝑟 be a family of 𝑟 independent random oracles (or random permutation oracles) mapping 𝑛 bits to 𝑛. Let 𝑃 : {0, 1} 𝑡 → {0, 1} 𝑣 with 𝑡 + 𝑣 ≤ 𝑛 be a plug (𝜌, 𝑢, 𝜖(𝑝))-hard against 2 𝑝 -adversaries. Then the function 𝑓 : {0, 1} 𝑛 → {0, 1} 𝑛 defined by

𝑓 : 𝑥 ↦ → ( (𝐹 𝑟-1 • 𝑃 ) ∘ ... ∘ (𝐹 0 • 𝑃 ) ) (𝑥)
is (𝜌, 𝑢, max(𝜖(𝑝) 𝑟 , 2 𝑝-𝑛 ))-hard against 2 𝑝 -adversaries.

Proof. We denote 𝑓 𝑖 the function defined by 𝑓 : 𝑥 ↦ → ( (𝐹 𝑖-1 •𝑃 )∘...∘(𝐹 0 •𝑃 ) ) (𝑥), so that 𝑓 = 𝑓 𝑟 . We proceed by induction on the number of rounds 𝑖, our induction hypothesis being that the theorem holds for 𝑟 ≤ 𝑖.

Initialization. If 𝑖 = 1 i.e. for 𝑓 1 = (𝐹 • 𝑃 ), Lemma 1 tells us that this function is (𝜌, 𝑢, 𝜖)-hard. As 𝜖 ≥ 2 𝑝-𝑣 > 2 𝑝-𝑛 , the induction holds for 𝑖 = 1.

Inductive

Step. Suppose that the theorem holds for 𝑖 rounds. The attack based on pre-querying 2 𝑝 outputs of 𝑓 𝑖+1 and then approximating 𝑓 𝑖+1 using the content of this table would still work. Thus, if 𝜖 𝑖+1 ≤ 2 𝑛-𝑝 then this strategy is the optimal one. Suppose now that 𝜖 𝑖+1 > 2 𝑛-𝑝 , which also implies that

𝜖 𝑖 > 2 𝑛-𝑝 .
As 𝐹 𝑖+1 is a random (permutation) oracle, the only way to evaluate the output of 𝑓 𝑖+1 is to first evaluate 𝑓 𝑖 and then to evaluate (𝐹 𝑖+1 • 𝑃 ). The existence of another efficient computation method would violate the assumption that 𝐹 𝑖+1 is a random oracle.

Thus, the adversary needs first to evaluate 𝑓 𝑖 and then (𝐹 𝑖+1 • 𝑃 ). Let 𝑓 ′ 𝑗 be an approximation of the function 𝑓 𝑗 computed by a 2 𝑝 -adversary and let 𝑔 𝑗 be an approximation of (𝐹 𝑗 • 𝐹 ) computed by the same adversary. The probability of the successful evaluation of 𝑓 ′ 𝑖+1 is:

𝑃 [ 𝑓 ′ 𝑖+1 (𝑥) = 𝑓 𝑖+1 (𝑥), 𝑥 $ ← {0, 1} 𝑛 ] = 𝑃 [𝑔 𝑖+1 (𝑦) = (𝐹 𝑖+1 • 𝑃 )(𝑦) | 𝑦 = 𝑓 𝑖 (𝑥)] × 𝑃 [ 𝑓 ′ 𝑖 (𝑥) = 𝑓 𝑖 (𝑥), 𝑥 $ ← {0, 1} 𝑛 ] .
On the other hand, the first term is equal to

𝑃 [𝑔 𝑖+1 (𝑦) = (𝐹 𝑖+1 • 𝑃 )(𝑦) | 𝑦 = 𝑓 𝑖 (𝑥)] = 𝑃 [ 𝑔 𝑖+1 (𝑦) = (𝐹 𝑖+1 • 𝑃 )(𝑦), 𝑦 $ ← {0, 1} 𝑛 ] (1)
which, because of Lemma 1, is at most equal to 𝜖. Equation (1) is true. Were it not the case, then 𝐹 𝑖+1 would not be behaving like a random oracle. Indeed, 𝑦 = 𝑓 𝑖 (𝑥) is the output of a sequence of random oracle calls sandwiched with simple bijections consisting in the plug calls that are independent from said oracle. Therefore, since 𝑥 is picked uniformly at random, 𝑦 must take any value with equal probability. Furthermore, the events 𝑓 𝑖 (𝑥) = 𝑦 and 𝑔 𝑖+1 (𝑦) = (𝐹 𝑖+1 • 𝑃 )(𝑦) are independent: the latter depends only on the last random (permutation) oracle 𝐹 𝑖+1 while the former depends on all other random (permutation) oracles. As a consequence, the probability that 𝑓 ′ 𝑖+1 (𝑥) = 𝑓 𝑖 (𝑥) for 𝑥 picked uniformly at random and for any approximation 𝑓 ′ 𝑖+1 obtained by a 2 𝑝 -adversary is upper-bounded by 𝜖 𝑖+1 .

Hard Block Cipher Mode (HBC)

Let 𝐸 𝑘 be a block cipher operating on 𝑛-bit blocks using a key of length 𝜅 ≥ 𝑛.

Let 𝑃 be a plug (𝜌, 𝑢, 𝜖(𝑝))-hard against 2 𝑝 -adversaries. The HBC mode of operation iterates these two elements to create an 𝑛-bit block cipher with a 𝜅bit secret key which is (𝜌, 𝑢, max(𝜖(𝑝) 𝑟 , 2 𝑝-𝑛 ))-hard against 2 𝑝 -adversaries. This construction, when keyed by the 𝜅-bit key 𝑘, is the permutation HBC[𝐸 𝑘 , 𝑃, 𝑟] which transforms an 𝑛-bit input 𝑥 as described in Algorithm 3. This process is also summarized in Figure 4. Below, we describe the hardness (Theorem 2) such an HBC instance achieves. We also reiterate that if an asymmetrically hard plug is used then the block cipher thus built is also asymmetrically hard.

Our proof is in the ideal cipher model, a rather heavy handed assumption. We leave as future work to prove the hardness of this mode of operation in simpler settings. The role of the round counter XOR in the key is merely to make the block cipher calls independent from one another. If the block cipher had a tweak, these counter additions could be replaced by the use of the counter as a tweak with a fixed key. It is possible to use block ciphers which are not secure in the related-key setting and still retain the properties of HBC by replacing the keys 𝑘 ⊕ 𝑖 by the outputs of a key derivation function.

Theorem 2 (Hardness of HBC). If the block cipher 𝐸 𝑘 used as a component of HBC[𝐸 𝑘 , 𝑃, 𝑟] is an ideal block cipher and if the plug 𝑃 is (𝜌, 𝑢, 𝜖(𝑝))-hard against 2 𝑝 -adversaries, then the block cipher HBC[𝐸 𝑘 , 𝑃, 𝑟] is

( 𝜌, 𝑢, max(𝜖(𝑝) 𝑟 , 2 𝑝-𝑛 ) ) -hard against 2 𝑝 -adversaries.
Proof. As 𝐸 𝑘 is an ideal cipher, 𝐸 𝑘 and 𝐸 𝑘⊕𝑖 act like two independent random permutation oracles. As a consequence, Theorem 1 immediately gives us the theorem.

We used the HBC structure to build an asymmetrically time-hard block cipher, Skipper, which we describe in Section 5.1.

Hard Sponge Mode (HSp)

The sponge construction was introduced by Bertoni et al. as a possible method to build a hash function [START_REF] Bertoni | Sponge functions[END_REF]. They used it to design Keccak [START_REF] Bertoni | Keccak specifications[END_REF] which later won the SHA-3 competition. It is a versatile structure which can be used to implement hash functions, stream ciphers, message authentication codes (MAC), authenticated ciphers as described in [START_REF] Bertoni | Duplexing the sponge: single-pass authenticated encryption and other applications[END_REF], pseudo-random number generators (PRNG) and key derivation functions (KDF) as explained for example in [START_REF] Gaži | Provably robust sponge-based prngs and kdfs[END_REF]. In this section, we first provide a brief reminder on the sponge construction Then, we show how plugs can be combined with secure sponge transformation to build R-hard sponges, thus providing R-hard hash function, MAC, etc.

𝑔 𝑔 𝑔 ⊕ ⊕ 0 IV 𝑚 0 𝑚 1 ℎ 0 ℎ 1 𝑟 𝑐

Initialization Absorption Squeezing

Figure 5: A sponge-based hash function.

The Sponge Construction

A sponge construction uses an 𝑛-bit public permutation 𝑔 and is parametrized by its capacity 𝑐 and its rate 𝑟 which are such that 𝑟 + 𝑐 = 𝑛. This information is sufficient to build a hash function, as illustrated in Figure 5. The two higher level operations provided by a sponge object parametrized by the function 𝑔, the rate 𝑟 and the capacity 𝑐 are listed below.

• Absorption. The 𝑟-bit block 𝑚 𝑖 of the padded message 𝑚 is xored into the first 𝑟 bits of the internal state of the sponge and the function 𝑔 is applied.

• Squeezing. The first 𝑟 bits of the internal state are output and the function 𝑔 is applied on the internal state.

The internal state of the sponge obviously needs to be initialized. It can be set to a fixed string to create a hash function. However, if the initial value is a secret key, we obtain a MAC. Similarly, if the initial value is a secret key/initialization pair, we can generate a pseudo-random keystream by iterating the squeezing operation.

As explained in [START_REF] Bertoni | Duplexing the sponge: single-pass authenticated encryption and other applications[END_REF], this structure can be modified to allow singlepass authenticated encryption. This is achieved by using the sponge object to generate a stream with the added modification that, between the generation of the 𝑟-bit keystream block and the application of 𝑔 to the internal state, the 𝑟-bit block of padded message is xor-ed into the internal state, just like during the absorption phase. In this case, there is no distinction between the absorption and squeezing phase. Once the whole padded message has been absorbed and encrypted using the keystream, the sponge object is squeezed to obtain the tag.

Finally, a sponge object can also be used to build a KDF or a PRNG using a similar strategy in both cases, as proposed in [START_REF] Gaži | Provably robust sponge-based prngs and kdfs[END_REF]. The general principle is to absorb the output of the low-entropy source and follow the absorption of each block by many iterations of 𝑥 ↦ → 0 𝑟 ||𝑇 𝑐 (𝑔(𝑥)) on the internal state, where 𝑇 𝑐 (𝑥) is equal to the last 𝑐 bits of 𝑥. Setting the first 𝑟 bits of the internal state to zero prevents the inversion of the update function.

Sponge construction are known to be secure as long as the public update function 𝑔 has no structural distinguishers such as high probability differentials or linear approximation with a high bias.

The main advantages of the sponge structure are its simplicity and its versatility. It is simple because it only needs a public permutation and it is versatile because all symmetric primitives except block ciphers can be built from it with very little overhead. As we will show below, the fact that its internal state is larger than that of a usual block cipher also means that attacks based on precomputations are far weaker.

The HSp Mode and its Hardness

Given that a sponge object is fully defined by its rate 𝑟, capacity 𝑐 and public update function 𝑔, we intuitively expect that building a R-hard sponge object can be reduced to building a R-hard update function. As stated in the theorem below, this intuition is correct provided that the family of functions 𝑔 𝑘 : {0, 1} 𝑐 → {0, 1} 𝑐 indexed by 𝑘 ∈ {0, 1} 𝑟 and defined as the capacity bits of 𝑔(𝑥||𝑘) is assumed to be a family of independent random oracles.

We call HSp the mode of operation described in this section. It is superficially similar to a round of the HBC block cipher mode.

An update function 𝑔 can be made R-hard using the R-hardness of a plug 𝑃 : {0, 1} 𝑡 → {0, 1} 𝑣 to obtain a new update function (𝑔 • 𝑃 ) as described in Algorithm 4.

Algorithm 4 (𝑔 • 𝑃 ) sponge transformation Inputs: 𝑛-bit block 𝑥;

Output: 𝑛-bit block 𝑦 𝑥 𝑡 || 𝑥 𝑣 || 𝑥 ′ ← 𝑥, where |𝑥 𝑡 | = 𝑡, |𝑥 𝑣 | = 𝑣, |𝑥 ′ | = 𝑛 -𝑡 -𝑣 𝑥 𝑣 ← 𝑥 𝑣 ⊕ 𝑃 (𝑥 𝑡 ) 𝑦 ← 𝑔(𝑥 𝑡 || 𝑥 𝑣 || 𝑥 ′ ) return 𝑦
This process is summarized in Figure 6. In order to prevent the adversary from reaching either the input or the output of 𝑃 , which could make some attacks possible, we impose that 𝑡 + 𝑣 ≤ 𝑐 so that the whole plug input and output are located in the capacity.

Theorem 3 (HSp absorption hardness). Consider a sponge defined by the 𝑛-bit transformation (𝑔 • 𝑃 ), a rate 𝑟 and a capacity 𝑐 so that 𝑟 + 𝑐 = 𝑛 and 𝑟 > 𝑐. Let (𝑔 • 𝑃 ) be defined as in Algorithm 4, where 𝑃 : {0, 1} 𝑡 → {0, 1} 𝑣 is a plug (𝜌, 𝑢, 𝜖(𝑝))-hard against 2 𝑝 -adversaries.

Let Absorb : {0, 1} ℓ×𝑟 → {0, 1} 𝑐 be the function mapping an un-padded message 𝑚 of ℓ 𝑟-bit blocks to the capacity bits of the internal state of the sponge after it absorbed 𝑚. Furthermore, suppose that the 𝑛-bit transformation 𝑔 is such that the family of functions 𝑔 𝑘 : {0, 1} 𝑐 → {0, 1} 𝑐 indexed by 𝑘 ∈ {0, 1} 𝑟 and defined as 𝑔 𝑘 (𝑥) = 𝑇 𝑐 ((𝑔(𝑥||𝑘)) can be modeled as a family of random oracles.

Then Absorb is ( 𝜌, 𝑢, max(𝜖(𝑝) ℓ-1 , 2 𝑝-𝑐 ) ) -hard against 2 𝑝 -adversaries.

This theorem deals with un-padded messages. The padding of such a message imposes the creation of a new block with a particular shape which cannot be considered to be random.

Proof. Let 𝑔 𝑘 : {0, 1} 𝑐 → {0, 1} 𝑐 be as defined in the theorem. Let the message 𝑚 be picked uniformly at random.

The first call to (𝑔 • 𝑃 ) is not (𝜌, 𝑢, 𝜖(𝑝))-hard. Indeed, the content of the message has not affected the content of the capacity yet. However, the capacity bits of the internal state after this first call to (𝑔 • 𝑃 ) are uniformly distributed as they are the image of a constant by the function indexed by 𝑚 0 from a family of 2 𝑟 different random oracles.

Let 𝑚 ′ 𝑖 = 𝑚 𝑖 ⊕ 𝑧 𝑖 , where 𝑚 𝑖 is the message block with index 𝑖 > 1 and where 𝑧 𝑖 is the first 𝑟 bits of the content of the sponge after the absorption of 𝑚 0 , ..., 𝑚 𝑖-1 . That is, 𝑧 𝑖 is the content of the rate juste before the call to (𝑔 • 𝑃 ) following the addition of the message block 𝑚 𝑖 . We can therefore represent the absorption function as described in Figure 7.

Since the message blocks 𝑚 𝑖 have been picked uniformly at random, so are the values 𝑧 𝑖 . We can therefore apply Theorem 1, where the independent random oracles are 𝑔 𝑧𝑖 , the plug is 𝑃 , the random message is (𝑔 𝑚0 • 𝑃 )(0||𝐼𝑉 ), the block size is 𝑐 and the number of rounds is ℓ -1.

As 𝑐 is typically much larger than a usual block cipher size of 128 bits, the probability of success of a 2 𝑝 adversary can be made much smaller when a sponge is built rather than a block cipher.

Note that if a sponge is used to provide e.g. authenticated encryption, the same bound should be used as the message is absorbed into the state in the same fashion in this case.

The following claim describes the hardness of the squeezing operation.

Claim 1 (HSp squeezing hardness). Consider a sponge defined by the 𝑛-bit transformation (𝑔 • 𝑃 ), a rate 𝑟 and a capacity 𝑐 so that 𝑟 + 𝑐 = 𝑛 and 𝑟 > 𝑐.

Let (𝑔 • 𝑃 ) be defined as in Algorithm 4, where 𝑃 : {0, 1} 𝑡 → {0, 1} 𝑣 is a plug (𝜌, 𝑢, 𝜖(𝑝))-hard against 2 𝑝 -adversaries. Let Squeeze ℓ : {0, 1} 𝑛 → {0, 1} ℓ×𝑟 be the function mapping an internal state of 𝑛 bits to a stream of ℓ 𝑟-bit blocks obtained by iterating ℓ times the Squeeze operation.

Then Squeeze ℓ is ( 𝜌, 𝑢, max(𝜖(𝑝) ℓ , 2 𝑝-(𝑐+𝑟) ) ) -hard against 2 𝑝 -adversaries.

We cannot prove this hardness using Theorem 1 because the transformations called in each round are all identical. In particular, they cannot be independent. This situation can however be interpreted as a variant of the one in the proof of Theorem 3 where 𝑧 𝑖 is not formally picked uniformly at random as there is no message absorption but can be interpreted as such because it is the output of the sponge function.

The claimed probability of success bound comes from the hardness of approximating all ℓ calls to the plug composed with the sponge transformation (𝜖(𝑝) ℓ ) and the hardness of using a precomputation of the image of 2 𝑝 possible internal states (2 𝑝-(𝑐+𝑟) )).

If the sponge is used to provide a simple stream cipher, the bound of Claim 1 should be used. Indeed, since there is no message absorption in this case, Theorem 3 cannot be used.

Practical Instances: Skipper and Whale

We illustrate the versatility and simplicity of the modes of operation described in the previous section by presenting an instance of each. The first is an asymmetrically time-hard block cipher called Skipper and the second is a code-hard sponge called Whale.

The Skipper Block Cipher

One possible application for egalitarian computing which is mentioned but not explored in [START_REF] Biryukov | Egalitarian computing[END_REF] is obfuscation. The idea is to modify a program in such a way that a memory-hard function must be computed in parallel to the execution of the program. Using this very general approach, any program or function could be made memory-hard, not just cryptographic ones. However, a shortcoming in this case is the fact that the compiler returning the obfuscated code must also pay the full price of running this parallel memory-hard function.

Solving this issue requires a primitive with asymmetric memory hardness such as Diodon. However, this primitive is rather slow even for privileged users. Therefore, we build instead an asymmetrically time-hard block cipher using the HBC mode to combine the AES and the RSA-lock plug. The result is the asymmetrically time-hard block cipher Skipper. It could be used to create an efficient obfuscator. The obfuscator would use the fast implementation of the plug to create an obfuscated program which forces common users to evaluate its slow version to run the program. That way, the computational hardness is only paid by the users of the program and not by the compiler. While this cost might be offset through the use of dedicated hardware for the computation of RSA-lock, we note that this function cannot be parallelized.

Our ) hard. As said before in Section 3.3, we assume that no adversary can evaluate 𝑥 2 𝜂 mod 𝑁 without performing 𝜂 squarings in the modular ring. However, a 2 𝑝 -adversary can either guess all 40 bits of the output, which succeeds with probability 2 -40 , or store 2 𝑝 out of the 2 88 possible outputs, in which case a successful evaluation is possible with probability 2 𝑝-88 .

Merely guessing is the best strategy unless the adversary has access to at least 40 × 2 88-40 ≈ 2 53.3 bits of storage, i.e. more than a thousand terabytes. Furthermore, the cost of such a pre-computation could only be amortized if more than 2 48 /2 = 2 47 blocks are encrypted using the same plug, i.e. 2 54 bits (more than a thousand Tb). Otherwise, the time taken by the precomputation would be superior to the time needed to evaluate the slow function. We therefore consider 2 48 -adversaries, that is, adversaries capable of pre-computing 2 48 values of RSAlock 𝑛𝑝 𝜂 (𝑥). Such an adversary is already quite powerful as it has significant computing power and storage in addition to knowing the secret key 𝑘. Providing maximum security against more powerful adversaries would probably be over-engineering. Thus, in our setting, the plug is asymmetrically (Time, 𝜂, 2 -40 )-hard.

Claim 2 (Properties of Skipper). The block cipher Skipper is asymmetrically (Time, 𝜂, 2 -80 )-hard and cannot be distinguished from a pseudo-random permutation using less than 2 128 operations.

Skipper is HBC[AES -128, RSAlock 𝑛𝑝 𝜂 , 2] and its plug is asymmetrically (Time, 𝜂, 2 -40 )-hard. Thus, by applying Theorem 2 we obtain that Skipper is asymmetrically ( Time, 𝜂, max (

2 48-128 , (2 -40 ) 2 )) -hard.
As there is to the best of our knowledge no related-key attack against fullround AES-128 in the case where the related keys are linked by a simple XOR, we claim that Skipper cannot be distinguished from a random permutation using much less than 2 128 operations. Should such distinguishers be found, an alternative key schedule such as the one from [START_REF] Nikolić | Tweaking AES[END_REF] could be used.

We implemented Skipper on a regular desktop PC. The corresponding benchmarks are provided in Appendix A.3.

The Whale Hash Function

Preventing the leakage of encryption keys is a necessity in order for a system to be secure. A possible method for preventing this was informally proposed by Shamir in a talk at RSA'2013 and then formalized by Bellare et al. in their CRYPTO'16 paper. As the throughput of the exfiltration method used by the attacker is limited, using a huge key would make their task all the harder. To use our terminology, an encryption algorithm with significant code-hardness would effectively be bound to the physical device storing it: since the code cannot be compressed, an attacker would have to duplicate the whole implementation to be able to decrypt the communications. Even a partial leakage would be of little use.

The proposal of Bellare et al., XKEY2, is effectively a code-hard key derivation algorithm which takes as input a random initialization vector and outputs a secret key. Since it is code-hard, an attacker cannot evaluate this function without full knowledge of the source code of the function and cannot extract a smaller (and thus easier to leak) implementation.

We propose the code-hard hash function Whale as an alternative to XKEY2. It can indeed be used to derive a key by hashing a nonce, a process which cannot be approximated by an attacker unless they duplicate the entirety of the implementation of Whale. Whale is a simple sponge-based hash function which uses the XOR of ⌈128/𝑡⌉ instances of BigLUT 128 𝑡 as a plug. Different choices of 𝑡 lead to different levels of code-hardness. It is only parametrized by the input length of the tables 𝑡.

It is based on SHA-3-256: it uses the Keccak -𝑓 [1600] permutation, the same padding scheme, the same rate 𝑟 = 1088, the same capacity 𝑐 = 512 and the same digest size of 256 bits. There are only two differences:

• the permutation Keccak -𝑓 [1600] is augmented with the code-hard plug consisting in the XOR of ℓ = ⌈128/𝑡⌉ distinct instances of BigLUT 128 𝑡 , and

• 𝑡 blank calls to the transformation are performed between absorption and squeezing.

These parameters were chosen so as to prevent an adversary with access to at most half of the implementation of Whale to compute the digest of a message with probability higher than 2 -128 .

Claim 3 (Code-hardness of Whale). The Whale hash function using tables with 𝑡-bit inputs is (Code, 2 𝑡+13 /𝑡, 2 -128 )-hard against an adversary trying to use only half of the code-space used to implement Whale.

Whale uses ⌈128/𝑡⌉ tables of 2 𝑡 128-bit entries. Thus, about 2 𝑡 × 128 × ⌈128/𝑡⌉ ≈ 2 𝑡+14 /𝑡 bits are needed to store the implementation of its plug. An adversary trying to compress it and divide its size by 2 therefore has access to 2 𝑡+13 /𝑡 bits. Note however that, since the entries in each instance of BigLUT 128 𝑡 have been picked uniformly at random, it is impossible to actually compress them. The best an attacker can do is therefore to store as many entries as they can.

When hashing a message, at least 𝑡 calls to the plug are performed during the blank calls to the transformation between the absorption and the squeezing. Therefore, the adversary needs to successfully compute 𝑡×⌈128/𝑡⌉ ≥ 128 entries of the big tables. If they only have half of them stored, then they succeed in computing the digest of a message with probability at most 2 -128 .

Conclusion

We have presented for the first time a unified framework to study all three forms of hardness (time, memory and code) as well as their asymmetric variants. We have proposed Diodon, the first asymmetrically memory-hard function. We have also presented the first general approach for building a cryptographic primitive with any type of hardness and illustrated it with two fully specified proposals. The first is the asymmetrically time-hard block cipher Skipper which can be made arbitrarily slow for some users while retaining its efficiency for those knowing a secret key. The second is the code-hard hash function Whale whose implementation cannot be compressed.

A Appendix

A.1 Choosing Parameters for Diodon

An RSA modulus of at least 2048 bits is necessary to prevent attacks from 2 𝑝adversaries who can perform up to 2 100 operations (see Table 2 of Unfortunately, such a choice of parameters leads to a slow function for both users. We have experimentally found that it requires about 14 seconds to compute its output for both classes of users. Worse still, since the time taken to evaluate the function is proportionnal to the amount of memory used, filling 100 Mb of RAM will take dozens of minutes. As a consequence, we suggest two different methods to speed up this function.

First, depending on the context, protecting ourselves from adversaries capable of doing 2 100 simple operations may be over-engineering, e.g. if the RSA modulus can be changed frequently. In this case, using a modulus of 1024 bits (about 80-bits of security) or even less may be sufficient. As shown in the benchmark (Appendix A.3) of our RSA-based asymmetrically time-hard block cipher Skipper (introduced in Section 5.1), decreasing the RSA modulus size leads to observable performance gain.

Second, we can give different values to 𝑀 and 𝐿 so that 𝐿 ≪ 𝑀 . To retain a similar time complexity for both classes of users, we need to ensure that 𝑛 𝑝 × 𝐿 ≈ 𝜂𝑀 as these are roughly the number of squarings performed by the privileged and the basic user respectively. For scrypt, Alwen et al. formally showed in [ACP + 17] that the product time×memory for an algorithm evaluating scrypt could not be much smaller than 𝐿 × 𝑀 in the case 𝐿 = 𝑀 . If 𝐿 < 𝑀 then it is easy to decrease this product: an adversary who does not store any value 𝑉 𝑖 but instead recomputes 𝑉 𝑖 = 𝑥 2 𝑖×𝜂 mod 𝑁 every time needs roughly a time corresponding to 𝐿 × 𝑀 RSA squarings. If this adversary stores instead of a fraction 𝑓 of 𝑉 , then she needs a time roughly equal to 𝐿/𝑓 to evaluate the output as she needs about 1/𝑓 squarings to obtain the value 𝑉 𝑖 from the closest one she stored. As a consequence, the product 𝐿 × 𝑀 is preserved. Claim 4. The product time × memory for an algorithm evaluating Diodon cannot be much smaller than 𝐿 × 𝑀 .

We leave a formal proof which would be a straightforward generalization of the result from [ACP + 17] for the future work. In the light of this claim, we propose another set of parameters: 𝑡 = 𝑢 = 128, 𝜂 = 1, 𝑛 𝑝 = 1024, 𝑀 = 8, 000, 000, and 𝐿 = 20, 000. It is such that 𝜂 × 𝑀 ≈ 2 23 and 𝐿 × 𝑛 𝑝 ≈ 2 24 are close and such that the basic user needs to fill 𝑀 × 𝑛 𝑝 /8 ≈ 8 • 10 9 bytes of RAM, i.e. about 1 Gb.

We have benchmarked the time taken by basic and privileged users to evaluate Diodon on random strings of 𝑢 bits for the two sets of parameters specified above. The result is summarized in implementations. The results presented in Table 3 are the averages of these values. Note that we did not implement the Chinese Remainder Theorem-based exponentiation in this case, but it would provide a constant factor advantage to the privileged user. The tests were done on a regular desktop with an i7-3770 CPU clocked at 3.4 Ghz and 8 Gb of RAM. The code was written in C++ and will be made available on github. Large integer arithmetic relies on the GMP library.

A.2 Code-Hardness: a Literature Overview Symmetric white-box cryptography has received renewed interest in the past few years following the publication of [START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[END_REF], a paper describing white-box block ciphers relying on the so-called ASASA structure. A string of paper has followed, some attacking the corresponding scheme [DDKL15, MDFK15], others proposing new primitives with similar security goals [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF][START_REF] Fouque | Efficient and provable white-box primitives[END_REF]. We first describe the different notions of white-box security presented in these papers and its relation with "big-key cryptography". The corresponding security notions can be interpreted as enforcing that the code implementing the studied functionalities is expensive to store. The authors of [START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key[END_REF] introduced two different notions of white-box encryption. The notions introduced were similar to those in [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF] but, rather than describing the properties of a white-box compiler, they deal with the properties of a fixed white-box implementation. The first notion, strong white-box security, corresponds to public key encryption in the sense that an adversary with a white-box implementation of the encryption function should not be able to recover a decryption function, effectively turning a secret key algorithm into a public key one. The second is called weak white-box security.

Definition 5. Let 𝐸 𝐾 be an encryption algorithm and let 𝒪 𝐸 𝐾 be its white-box implementation. The function 𝒪 𝐸 𝐾 is a 𝑇 -secure weak white-box implementation for 𝐸 𝐾 if it is computationally hard to obtain 𝑘 such that 𝐸 ′ 𝑘 and 𝐸 𝐾 are functionally equivalent and such that |𝑘| < 𝑇 given full access to 𝒪 𝐸 𝐾 .

This intuitive notion was further formalized by the designers of the SPACE cipher [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF]. This block cipher, a target-heavy Feistel Network which uses a full AES-128 encryption as its Feistel function, aims at providing so-called (𝑀, 𝑍)-space hardness. This property was finally presented as (𝑠, 𝜆, 𝜖)-weak incompressibility in [START_REF] Fouque | Efficient and provable white-box primitives[END_REF], that is as a bound on the probability for an adversary to win a particular game.

Definition 6 ((𝑀, 𝜆, 𝛿)-weak incompressibility [START_REF] Fouque | Efficient and provable white-box primitives[END_REF]). Let Enc : 𝒦 × ℛ × 𝒫 → 𝒞 denote an encryption algorithm. Let 𝑀, 𝜆 denote security parameters. Let us further assume that the big-key 𝐾 ∈ 𝒦 is a function 𝐾 : ℐ → 𝒪 for some input and output sets ℐ and 𝒪. The encryption scheme is said to be secure for (𝑀, 𝜆, 𝛿)-weak incompressibility if and only if, with probability at least 1 -2 -𝜆 over the random choice of 𝐾 ∈ 𝒦 (performed in the initial step of the game), the probability of success of the adversary in the following game is upper bounded by 𝛿.

1. The challenger picks 𝐾 ∈ 𝒦 uniformly at random. The adversary wins if and only if 𝐶 decrypts to 𝑃 for the key 𝐾 (see also Figure 8).

We omit the definition of (𝑀, 𝑍)-space hardness from [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF] because this notion is effectively equivalent to (𝑀, 𝜆, 2 -𝑍 )-weak incompressibility. The only 𝑛 𝑝 for 𝜇 ∈ {2, 10, 100, 1000}, each time being the average of 10 experiments performed with a different RSA modulus. These are just examples, in fact arbitrary slowdowns for the non-privileged user are possible. We express the results as throughputs in blocks per seconds. The results are given in Table 4; e.g. a common user using Skipper with 𝑛 𝑝 = 768 and 𝜇 = 2 encrypts on average 750.1 blocks of 128 bits per second on our benchmark machine.

In order to prevent attacks from 2 𝑝 -adversaries who cannot perform more than 2 100 operations, a modulus size of 2048 bits is necessary according to The tests were done on a regular desktop with an i7-3770 CPU clocked at 3.4 Ghz and 8 Gb of RAM. The code was written in C++ and will be made available on github.

The ratio of the efficiency of the encryption depending on whether the secret is known or not is not equal to 𝜇. This is because the common user performs exactly 𝜇×𝑛 𝑝 squarings while the privileged one uses a smaller exponent. Further, the privileged user uses the Chinese Remainder Theorem to implement an even faster exponentiation. Still, multiplying 𝜇 by 10 does divide the throughput by 10 for the common user.

Figure 1 :

 1 Figure 1: The evaluation of 𝑦 = Diodon(𝑥).

Definition 4 (Figure 3 :

 43 Figure 3: Evaluating the plugged function (𝐹 • 𝑃 ).

Figure 4 :

 4 Figure 4: The HBC block cipher mode.

Algorithm 3

 3 HBC[𝐸 𝑘 , 𝑃, 𝑟] encryption Inputs: 𝑛-bit plaintext 𝑥; 𝜅-bit key 𝑘 Output: 𝑛-bit ciphertext 𝑦 𝑦 ← 𝐸 𝑘 (𝑥) for all 𝑖 ∈ {1, ..., 𝑟} do 𝑦 𝑡 || 𝑦 𝑛-𝑡 ← 𝑦, where |𝑦 𝑡 | = 𝑡 and |𝑦 𝑛-𝑡 | = 𝑛 -𝑡 𝑦 𝑛-𝑡 ← 𝑦 𝑛-𝑡 ⊕ 𝑃 (𝑦 𝑡 ) 𝑦 ← 𝐸 𝑘⊕𝑖 (𝑦 𝑡 ||𝑦 𝑛-𝑡 ) end for return 𝑦

Figure 6 :Figure 7 :

 67 Figure 6: The hard sponge transformation (𝑔 • 𝑃 ).

  [BBB + 07]). We thus suggest a first set of concrete parameters for Diodon: 𝑛 𝑝 = 𝜂 = 2048, 𝑀 = 4000, 𝑡 = 𝑢 = 128 and 𝐻 = Sha-256. Such a function would use 𝑀 × 𝑛 𝑝 /8 ≈ 10 6 bytes of ram, unless the RSA secret key is known. It also has the advantage of being very close to the original ROMix function used by scrypt, meaning that the work of Alwen et al. [ACP + 17] can be leveraged to justify its memory-hardness.

  Figure 8: The game corresponding to the definition of (𝑠, 𝜆, 𝛿)-weak incompressibility.

  2. For 0 ≤ 𝑖 < 𝑀 : (a) the adversary chooses 𝑞 𝑖 , (b) queries 𝐾[𝑞 𝑖 ] from the challenger (adaptative queries). 3. The challenger picks 𝑃 ∈ 𝒫 uniformly at random. 4. The challenger sends 𝑃 to the adversary. 5. The adversary chooses 𝐶 ∈ 𝒞.

  Algorithm 1 Diodon Asymmetrically memory-hard function Inputs: 𝑡-bit block 𝑥; RSA modulus 𝑁 of 𝑛 𝑝 bits; 𝑀, 𝐿;

	Output: 𝑢-bit output 𝑦
	𝑉 0 = 𝑥
	for all 𝑖 ∈ {1, ..., 𝑀 -1} do 𝑉 𝑖 = 𝑉 2 𝜂 𝑖-1 mod 𝑁
	end for
	𝑆 = 𝑉 𝑀 -1
	for all 𝑖 ∈ {0, ..., 𝐿 -1} do
	𝑗 = 𝑆 mod 𝑀
	𝑆 = 𝐻(𝑆, 𝑉 𝑗 )
	end for
	return 𝑇 𝑢 (𝑆)
	𝑥 2 𝜂	2 𝜂	2 𝜂	2 𝜂
	𝑉		...
	𝑆	𝐻	𝐻	𝐻	𝑇 𝑢	y

  Hardness. BigLUT 𝑡 𝑣 uses a table 𝐾 consisting in 2 𝑡 entries, each being a 𝑣-bit integer picked uniformly at random. Evaluating BigLUT 𝑡 𝑣 then consists simply in querying this table: BigLUT 𝑡 𝑣 is the function mapping a 𝑡-bit integer 𝑥 to the 𝑣-bit integer 𝐾[𝑥].

  proposal Skipper is HBC[𝐴𝐸𝑆 -128, RSAlock 𝑛𝑝 𝜂 , 2], that is, a 128-bit block cipher using a 128-bit secret key 𝑘, an RSAlock 𝑛𝑝 𝜂 instance truncated to 40 bits as a plug and 3 calls to AES-128 sandwiching 2 calls to the plug. The plug operates modulo 𝑁 ≥ 2 𝑛𝑝 . The Skipper encryption procedure is described in Algorithm 5. Skipper encryption Inputs: 𝑛-bit plaintext 𝑥; 𝑘-bit key 𝑘; RSA modulus 𝑁 Output: 𝑛-bit ciphertext 𝑦 𝑦 ← AES 𝑘 (𝑥) for all 𝑖 ∈ {1, 2} do 𝑦 1 || 𝑦 2 ← 𝑦, where |𝑦 1 | = 88 and |𝑦 2 | = 40 𝑦 2 ← 𝑦 2 ⊕ 𝑇 40 (𝑦 2 𝜂

	Algorithm 5 1	mod 𝑁 )
	𝑦 ← AES 𝑘⊕𝑖 (𝑦 1 ||𝑦 2 )
	end for
	return 𝑦
	The RSA-based plug we use is asymmetrically	(	Time, 𝜂, max(2 𝑝-88 , 2 -40 )

Table 3 .

 3 For each set of parameter, we generated 50 random input values and hashed each using the basic and the privileged

	Parameters	Conservative	Fast
	𝑡	128	128
	𝑢	128	128
	𝑛 𝑝	2048	1024
	𝜂	2048	1
	𝑀	4, 000	8, 000, 000
	𝐿	4, 000	20, 000
	RAM (basic user)	1 Mb	1 Gb
	Time (basic user)	10.00 s	9.87 s
	Time (privileged)	13.49 s	10.65 s

Table 3 :

 3 Two sets of parameters for Diodon and the results of our benchmark.

Table 4 :

 4 Table 2 of [BBB + 07]. Otherwise, such adversaries could simply factorize the RSA modulus. However, as we can see in Table4, the performance penalty when increasing 𝑛 𝑝 is significant. Benchmark of the Skipper block cipher, where 𝑛 𝑝 is the RSA modulus, 𝜇 × 𝑛 𝑝 is the number of squarings performed by the common user, and the throughputs are given in block/second.

	𝑛 𝑝	𝜇	Tput. common Tput. privileged	ratio
		2	750.1	4234.4	5.6
	768	20	76.5	4182.7	54.7
		500	3.0	4210.3	1401.8
		2	357.6	2012.0	5.6
	1024	20	35.8	2062.1	57.6
		500	1.4	2106.8	1463.3
		2	119.4	739.7	6.2
	1536	20	12.3	752.0	60.9
		500	0.5	754.9	1525.5
		2	52.4	346.1	6.6
	2048	20	5.5	358.1	64.8
		500	0.22	359.4	1605.2
		2	7.6	54.5	7.1
	4096	20	0.77	55.4	71.8
		500	0.03	55.4	1778.1

The privileged user still has a small advantage in this case since knowing the prime factor decomposition of the modulus allows the use of the Chinese Remainder Theorem (DRT) to speed the exponentiation.

This is only true under the assumption that the output of the plug is uniformly distributed. As we will see later, the plug can still be used if it is not the case.

The challenger chooses a secure hash function (SHA-256) and sends its description to the adversary.

Acknowledgements

We thank anonymous reviewers from S&P, USENIX and ASIACRYPT'17 for their helpful comments. The work of Léo Perrin was supported by the CORE project ACRYPT (ID C12-15-4009992) funded by the Fonds National de la Recherche, Luxembourg.

difference lies in the fact that tables are allowed to be somehow weak with probability 2 -𝜆 in the latter. Both the SPACE cipher from [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF] and the WhiteBlock structure, which is instantiated as the PuppyCipher and Hound ciphers in [START_REF] Fouque | Efficient and provable white-box primitives[END_REF], achieve this definition of security.

The SPACE designers proposed a more demanding model called strong (𝑀, 𝑍)-space hardness. It is essentially the same as weak incompressibility except that the attacker choses the plaintext to encrypt. While an attacker must be able to encrypt a plaintext with high enough probability to violate weak incrompressibility, it is sufficient to produce one plaintext and its encryption to violate strong space hardness.

Another notion of security in a similar setting is described in a recent work of Bellare et al. on so-called "Big-Key Symmetric Encryption" [START_REF] Bellare | Big-key symmetric encryption: Resisting key exfiltration[END_REF]. The idea in that paper is to use a regular encryption algorithm along with a special method to use a very long (possibly 1Tb long) key called the Big Key. One of the main contribution of the paper is the XKEY2 key encapsulation and the proof that it is secure even if the attacker has some information about the big key. The XKEY2 algorithm works as follows:

1. the encryptor chooses a "selector" (a sort of IV) made of two parts: 𝑅 = (𝐼, p), where p is an array of size 𝑝 of elements in [1, len (𝐾)],

2. the key 𝐾 is set to

where 𝐻 is a hash function and 𝐾[𝑖] is the bit with index 𝑖 of 𝐾, the big key.

More precisely, the probability that an adversary manages to guess all the bits

given 𝑝, the length |𝐾| of the big-key and the output of an 𝑚-bit leakage function of their choosing is denoted Adv skp |𝐾|,𝑝 (𝑀 ) and is such that

where 𝐻 2 is the binary entropy function with 𝐻 2 (𝑥) = -𝑥 log 2 (𝑥) -(1 -𝑥) log 2 (1 -𝑥) and 𝐻 -1 2 (𝑥) is the smallest value 𝑦 such 𝐻 2 (𝑦) = 𝑥. Most importantly and unsurprisingly, the probability of success for the adversary decreases exponentially with the number of calls to the big-key during key setup.

The idea of allowing the attacker to obtain the output of any leakage function (with a bounded min-entropy) was also used in [START_REF] Fouque | Efficient and provable white-box primitives[END_REF] to formalize encryption incompressibility. It is based on the same game as weak incompressibility but the attacker does not have to query the 𝐾. Instead, much like in the work of Rogaway et al., the attacker may choose any 𝑚-bit leakage function 𝜑, ask the challenger for 𝜑(𝐾) and then try to encrypt a random plaintext. Note that if this leakage simply consists in querying some entries of the big-key, then we obtain weak incompressibility.

A.3 Benchmarking Skipper

We have implemented this block cipher using openssl (for AES) and the GMP library (for RSA). Specifically, modular exponentiation is performed with the function mpz powm sec to minimize the threat of side-channed attacks, although this function is about 20% slower than the basic mpz powm.

To benchmark its speed, we have computed the average time taken to encrypt 20 blocks of data for all 𝑛 𝑝 ∈ {768, 1024, 1536, 2048, 4096} and all 𝜂 = 𝜇 ×