Jean Sébastien Coron

Nadia El Mrabet

Henri Gilbert

Matthieu Rivain D'

E Prou

G Renault

M Rivain

C O'flynn

Tout d'abord, je souhaiterais remercier Louis Goubin, mon directeur de thèse, de qui j'ai tant appris et qui m'a soutenu à travers les moments les plus diciles de cette thèse. Merci de m'avoir donné l'opportunité de démarrer cette aventure et donné goût à la cryptographie. Merci pour toutes les discussions que nous avons pu avoir, qu'elles concernent les mathématiques ou pas. C'est une des choses qui me manqueront le plus.

Ce manuscrit commence par un guide pour la cryptographie boîte blanche. Son but est de réviser, préciser ou corriger les modèles boîte blanche, les notions de sécurité et les constructions qui ont émergé dans l'état-de-l'art depuis l'introduction du concept. Notamment, nous clarifions les modèles 'Remote-Access' et 'Hardware-Module' et les contextualisons dans la littérature cryptographique au sens large.

Nous explorons ensuite les implémentations boîte blanche de l'AES en synthétisant tout d'abord les implémentations connues et leurs failles. Nous proposons ensuite une nouvelle implémentation de l'AES pour laquelle nous proposons une analyse de sécurité et un challenge. La dernière partie de cette thèse est consacrée à l'étude de l'implémentation des primitives à base de cryptographie multivariée. Après une introduction succincte à la cryptographie multivariée, nous motivons l'utilisation de la cryptographie multivariée dans le modèle boîte blanche. Nous proposons ensuite la première implémentation boîte blanche de la famille de signature HFE, pour laquelle nous proposons une analyse de sécurité et un challenge. Enfin, pour proposer d'autres idées basées sur la cryptographie multivariée, nous proposons un chiffrement à flot incompressible basé sur QUAD.

Title : Contributions to White-Box Cryptography: Models and Algebraic Constructions

Keywords : White Box Cryptography -Implementation -Software Security Abstract : Due to the democratization of technologies such as mobile payment or the soaring of blockchain technologies, there is a growing need for secure implementations of standardized algorithms in the white-box model. In spite of this, there are too few secure designs published in the literature. To avoid relying on hidden design implementations to provide any security in the white-box model, more implementations designs and techniques have to be explored.

This thesis begins with a guide to white-box cryptography. Its goal is to revise, precise or correct white-box models, security notions and constructions that have emerged in the state of the art since the introduction of the concept. We notably clarify the Remote-Access White-Box model and the Hardware Module White-Box and contextualize them in the general cryptographic literature.

We then explore white-box implementations of the AES by first synthesizing the known implementations techniques and their flaws, and then proposing a new solution based on polynomial representations, for which we propose a security analysis and a challenge implementation. The last part of this thesis focuses on the implementation of multivariate cryptographic primitives in the white-box model. After introducing succinctly multivariate cryptography, we motivate the study of this branch of public key cryptography in the white-box context. We propose the first implementation technique of the HFE family of signature algorithms, for which we propose an extensive security analysis and a challenge implementation. Finally, to propose other perspectives on multivariate white-box cryptography, we also propose an incompressible stream cipher adapted from QUAD.

Résumé Étendu :

Le but de la cryptographie est d'étudier la sécurité des communications et de l'information. L'analyse de sécurité d'un cryptosystème dépend d'une clé secrète. Dans les premières étapes de l'analyse de sécurité, le stockage et l'utilisation de la clé par un cryptosystème sont omises par abstraction dans ce que l'on appelle le modèle boîtenoire.

Si ce modèle est satisfaisant pour étudier la sécurité d'un algorithme à travers son comportement entrée-sortie, ce n'est pas le cas lorsque l'algorithme est déployé sur un hardware. En eet, un adversaire peut alors récupérer des données physiques provenant de l'exécution de l'algorithme, comme son temps de calcul ou sa consommation de puissance. Ce modèle d'attaque est appelé modèle boîte-grise. L'étude de la sécurité dans ce modèle est un sujet actif et bien étudié et les preuves de sécurité dans ce modèle sont conditionnelles à certaines propriétés du hardware sur lequel l'algorithme est déployé. La cryptographie boîte blanche a pour but de dépasser cette limite et d'étudier la sécurité des algorithmes lorsqu'aucun hardware sécurisé n'est disponible.

Dans ce contexte, l'implémentation software est la dernière barrière entre la clé et un adversaire boîte blanche, qui a un contrôle complet de l'implémentation.

Du fait de la démocratisation de technologies telles que le paiement par mobile ou l'essor des technologies basées sur la blockchain, les besoins d'implémentations sécurisées dans le modèle boîte blanche d'algorithmes standardisés sont de plus en plus conséquents dans l'industrie. Malgré ces besoins, très peu de nouveaux designs sont proposés dans la littérature. Par exemple, le problème initial d'implémentation de l'AES est toujours ouvert après deux décennies et les récents eorts de la communauté cryptographique pour implémenter ECDSA se sont conclus par un échec. Pour ne pas avoir à utiliser des implémentations aux designs non publics, de nouvelles techniques d'implémentations doivent être proposées et étudiées.

Ce manuscrit commence par un guide pour la cryptographie boîte blanche. Son but est de réviser, préciser ou corriger les modèles boîte blanche, les notions de sécurité et les constructions qui ont émergé dans l'état-de-l'art depuis l'introduction du concept.

Dans le modèle boîte blanche standard -`Plain White Box Model' -nous révisons les notions d'incompressibilité, notamment pour les signatures, les algorithmes à clé publique ayant été peu étudiés dans la littérature. Nous exposons ensuite des liens entre des notions classiques de cryptographie, telles que le chirement à clé publique et les signatures basées sur l'identité, et les implémentations dans le modèle boîte blanche.

Enn, nous clarions deux modèles issus de la littérature, les modèles 'Remote-Access' et 'Hardware-Module', et les contextualisons dans la littérature cryptographique au sens large. Notamment, nous montrons à travers des exemples de l'état de l'art que certaines de ces problématiques sont liées à celles rencontrées dans le domaine de l'obfuscation indistinguable.

General Introduction: Towards

White-Box Cryptography

9 CONTENTS
What is Cryptography ?

Our society relies more and more on digital communication for most of its activities.

Humans now share infomation in their everyday life through many devices and communications lines. In central places of our society, such as hospitals, banks and social networks, huge amount of sensitive data are stored and exchanged. The security of this information is central for the good functioning of our society and the well-being of individuals. It is therefore crucial to establish reliable methods to secure data: this is the goal of cryptography.

Cryptography is usually dened as the science of protecting communication and information in the presence of a malicious adversary. The two parties communicating are often abstracted as Alice and Bob and their adversary Charlie. For a better ow of this short introduction to cryptography, we will assume that Alice and Bob want to condentially exchange information over a canal. Using cryptography, Alice and Bob will apply cryptographic algorithms to the data they exchange. Such algorithms are based on mathematical structures that we assume the reader is familiar with.

In a cryptographer's toolbox, Alice and Bob would need an encryption scheme to ensure the condentiality of their communication. If Alice wants to send a message to Bob, we assume that they share a secret piece of information called the secret key.

With the secret key, Alice can encrypt her message with an encryption algorithm that will render it incomprehensible to Charlie. Bob can then decrypt the encrypted message send by Alice to recover the message. In cryptographic jargon, the original message of Alice is called plaintext and the encrypted message the ciphertext. Formally an encryption scheme is a set of three algorithms G,E and D such that :

G is the key generation algorithm. It generates a private-key k.

If a user knows k, the encryption algorithm E provides a ciphertext c = E k (m) of a message m.

The decryption algorithm D uses the key k to decrypt the ciphertext so that:

c = E k (m) ⇐⇒ D k (c) = m
The goal for us is now to very succinctly overview the methods available to build such algorithms and how to establish their security.

Public Key and Private Key Cryptography

Cryptography has historically been considered in the symmetrical setting, that is, a setting where Alice and Bob both have a secret key that allows them to use cryptographic algorithms. However, Die and Hellman showed in 1976 that it was in fact 10 CONTENTS possible to study cryptography in an asymmetric setting. In this setting Alice owns a private-key and can broadcast its public key. With it, Bob can communicate with

Alice, but Alice only can decrypt Bob's message.

The historical context also made these two settings dierent in the techniques they use to provide security. In the Private-Key setting, algorithms are composed of several rounds of a function that has, paraphrasing Shannon, local diusion and confusion properties. The DES is the rst standardized algorithm of this kind using the Feistel Network structure, but Substitution Permutations Networks (SPN) like the AES also share this school of design. We describe in more details the AES in the second part of this thesis. By design, these algorithms are fast and simple to evaluate on hardware.

The security of private-key algorithms is evaluated by submitting them to the best known attack. The state-of-the-art of attacks against cryptogtaphic is always improved by cryptographers and helps to constantly reevaluate the concrete security of the cryptography deployed.

In the public key setting, algorithms are often based on hard mathematical problems.

The well known examples, RSA or ECDSA , are respectively based on nding roots over a RSA group and the problem of nding discrete logarithms over elliptic curves.

Their security is proved by a reduction to said mathematical problem, which has often been studied by mathematicians before. The goal of cryptographers is then to break the underlying mathematical problem. Due to the mathematical structure needed to achieve public key functionnalities, asymmetric algorithms are often more costly than symmetric ones.

These two techniques usually work in tandem in our everyday life, in what we call hybrid encryption. The goal of this method is to use fast algorithms for communication while using the practical broadcasting of key provided by public key cryptography. To do so, Alice will ask Bob to send a private key using a public key algorithm. If

Alice decrypts the encrypted private-key sent by Bob, they can now use a symmetric algorithm to communicate.

Other Cryptographic Functionalities

From its historical goal to protect communications, cryptography has then evolved into a mature science that tackles many problems related to information security. Modern cryptographic algorithms satisfy properties such as :

Condentiality : Alice and Bob can be sure that no information about their communication is revealed by their ciphertexts.

Authenticity: Alice can be sure that the communication comes from Bob and Bob only. Many other functionalities can by assured by cryptographic algorithms. For some of them, such as Fully Homomorphic Encryption, Indistinguishability Obfuscation or Zero-Knowledge Proofs, their existence is already a marvel. We will encounter some of them in this thesis, and encourage the reader to refer to the sources we provide for more details about them.

As one of the part of this manuscript is dedicated to a signature algorithm, we briey dene it here. The goal of a signature scheme is to allow to Alice to prove to Bob the authenticity of a document she owns. A signature scheme is a set of three algorithms G,S and V such that :

G is the key generation algorithm. It generates a public key k v and a private-key k s .

If a user knows k s , the signature algorithm S provides a signature S ks (m) of a message m.

The verifying algorithm V uses the public key k v to verify the signature so that: s = S ks (m) ⇐⇒ V kv (s, m) = 1

Signature algorithms are by denition public key algorithms, but authenticity can also be ensured in the private-key setting by Message Authentication Codes (MAC), provided that Alice and Bob share the same key.

Evaluating the Security of Cryptographic Algorithms

The security of the communications of Alice and Bob is only relative to the capabilities of Charlie. In cryptography, the role of the attacker is taken by cryptanalysts and the security of algorithms is evaluated and discussed in the literature. The goals of an attacker can be multiple. They can attempt to recover the secret key, decrypt a message or recover partial information about it. Key recovery is obviously the most the potent of them all, and modeling the capabilities of an attacker toward this goal is crucial for a precise evaluation of the security of communication.

A First Security Analysis : the Black-Box Model

The security of an algorithm is usually evaluated by using its input-output behavior in what is called the black-box model. In this model, Charlie has access to the line of communication of Alice and Bob and tries to recover their secret key. This rst analysis is crucial as it will determine if an algorithm can be useful at all for cryptography.

Depending on the context, one can allow an adversary to make dierent types of queries to the encryption algorithm it studies. Among them, the most common ones are :

Ciphertext Only Attack (COA): This is the most basic model of attack. Charlie only has access to the encrypted data of Alice and Bob to conduct the attack Known Plaintext Attack (KPA): In this model, the attacker also knows the plaintext for each ciphertext it recieves. In this case, the goal is to decrypt future messages or recover the key.

Chosen Plaintext Attack (CPA): Relaxing the previous model, the attacker can now chose particular plaintexts to help their cryptanalysis. It is particularly relevant in the public key setting.

Chosen Ciphertext Attack (CCA): In this model, Charlie can request decryption of chosen ciphertexts.

If these models of attack grasp various use cases, they abstract the fact that the key used by the algorithm is itself vulnerable to attacks. In our everyday life, cryptographic algorithms are computed by hardware and attackers can have access to more information than the input-output behavior of the algorithm. As the algorithms is implemented on hardware, operations depend on the physical restraints of the device.

An attacker can now plant sensors or steal the device to attempt to recover the key.

Cryptography on Hardware: The Grey-Box model

The grey-box model of attack attempts to use the leakage from hardware to conduct a cryptanalysis. A grey-box attacker can use physical information of the device during executions, such as its power consumption, computation time or electromagnetic emanation to conduct its cryptanalysis. Hardware is indeed subject to the laws of physics and the behavior of operations varies depending on the computation it makes. The discovery of such methods by Kocher [START_REF] Kocher | Timing attacks on implementations of die-hellman, rsa, dss, and other systems[END_REF] in 1996 changed the way cryptographers envisioned security and forced the community to provide new solutions against this enhanced adversary.

CONTENTS

In the grey-box model, we can classify attacks in roughly two categories : the passive attacks and the active attacks. In passive attacks, the attacker measures physical properties of the hardware during the execution of a cryptographic algorithm.

In active attacks, the adversary tries to tamper the hardware to provoke a faulty behavior that will help the analysis.

The most common examples of side-channel attacks are Dierential Power Analysis (DPA) and Dierential Fault Analysis (DFA). DPA is a passive attack whose goal is to analyze the power consumption to build two distributions that are based on the inputoutput of the algorithm and key-guesses. If the distributions are distinguishable, the attacker made the correct key-guess. The DFA is an active attack in which the attacker aims to precisely fault the device. If the the fault is precise enough, information about the secret key can be recovered by comparing the correct input-output behavior with the faulty one.

If these attacks were a threat to original implementations, cryptographers have since proposed countermeasures to these attacks. Among them, we can notably nd masking countermeasures [START_REF] Chari | Towards sound approaches to counteract power-analysis attacks[END_REF][START_REF] Goubin | DES and dierential power analysis (the "duplication" method)[END_REF]. The goal of masking is to share a sensitive value into a collection of random ones, so that if all the shares are leaked but one, no information is leaked about the sensitive value. The computations are then made on the shares instead of the real value. For fault attacks, redundancy or noise can be introduced in computations to render the exploitation of faulted encryptions harder.

However, most of the countermeasures to these attacks are supplemented by the fact that hardware can be made a secure environment for computation. The epitome of this rationale is the usage of smart cards for sensible computations such as payment functionalities. Smart cards are a restrained environment where direct access is limited and the structure of the hardware can be hidden. In this context, security can be reasonably proved conditionally the limited leakage of the device.

Towards the White-Box Model However, the usage seems to move away from the smart card dogma. In the recent years, more and more sensible information are held by less secure devices such as smartphones. One glaring example is the soaring in mobile payments. In such context, the hardware is of limited use to protect information. Indeed, smartphones for instance are way more malleable than smart cards and one can plant malware on it to directly extract the key. Software is now the last barrier between and attacker and a user's key.

This context of attack is called the white-box model and is the focus of this thesis.

Part II: Implementation of AES

The second part is dedicated to the study of white-box implementations of the AES.

The rst chapter oers a synthesis of the known implementations techniques and the attacks that broke them. The second chapter details our new method of implementation designed to resist algebraic attacks based on polynomial representations and propose a challenge implementation to motivate its study. The chapter 3 is a detailed correctness and security analysis of our construction. Finally, chapter 4 shows that this technique can be applied to any SPN for similar security results.

The chapter 2 to 4 are extracted from our joint publication with Louis Goubin of our implementation technique that is currently in submission. This publication comes with a challenge implementation that can be found at: https://github.com/ p-galissant/RCKAES Part III: White-Box Techniques for Multivariate Cryptography

The last part of this thesis focuses on the implementation of multivariate cryptographic primitives in the white-box model. In chapter 1, after succinctly introducing multivariate cryptography, we motivate the study of this branch of public key cryptography in the white-box context. In chapter 3, we propose the rst implementation technique of the HFE family of signature algorithm, for which we propose an extensive security analysis and a challenge implementation. Finally, in chapter 4, to propose other perspectives on multivariate white-box cryptography, we also propose an incompressible stream cipher adapted from QUAD.

The chapter 3 is an adaptation of our joint publication with Louis Goubin of our implementation technique, currently in submission. This publication comes with a challenge implementation that can be found at: https://github.com/p-galissant/ WBHFE. A previous version of this work can be found https://eprint.iacr.org/ 2022/138.pdf. The adaptation of QUAD to the white-box model is original to this manuscript.

Part I A Guide To White-Box Cryptography

Chapter 1

The White Box Model: History and Context

In this chapter, we introduce the white-box model, rst through a short summary of its development in the state-of-the-art. We then explore some of the problems that motivate the study of the white-box model of attack, as well as designing algorithms secure against a white-box adversary. We then formalize the white-box framework we will use for the rest of the thesis and discuss some design rationales that are common in the state-of-the-art and what they oer to the study of the model.

A Short Story of White-Box Cryptography

The white-box model has been introduced by Chow et al. in 2002 in their paper [START_REF] Chow | White-box cryptography and an AES implementation[END_REF] as

a setting to answer the following question: 'What security can cryptographers provide to implementations of cryptographic algorithm that are executed on non-secure -or worse, non-trusted -hardware ?'. In this setting, an attacker can get a complete access to the device it targets, read computed values and modify the implementation to its liking.

The white-box model is a natural extension of the grey-box model that aims to use secure hardware to provide security against an attacker that could use 'side-channel' information that are leaked from said hardware, such as execution time, power consumption or electromagnetic emissions, to get an advantage that he could not get in the black-box model of attack. If providing security in the grey-box model of attack is a hard problem on its own, providing security in the white-box model seems like a whole new ball game. Indeed, if information leaked by a hardware in the grey-box model are noisy and partial, the data gathered by a white-box adversary is exact and each computation made by the execution of the implementation can be retrieved.

For the cryptographer implementing an algorithm in the white-box model, goals are usually weaker than in the black-box model. The minimum for a white-box implementation is to guarantee the integrity of its key, that is, it should not be possible for an attacker to extract the secret key from its implementation. Then, if the implementation is key-extraction resilient, one can also ask the question if the code of the implementation can be compressed, or if the functionality it computes can be inverted.

We discuss in more details the security goals of the white-box model in chapter 2.

Even if the transition from the grey to the white-box model of attack was ambitious, Chow et al. proposed in their seminal publication two white-box implementations of two widely used standards, DES and AES. However, their implementations were quickly broken by structural attacks like the BGE attack [START_REF] Billet | Cryptanalysis of a white box AES implementation[END_REF]. Some other candidates with interesting properties were also proposed, but all broken with adaptations of the same attacks, or known general methods.

If the state-of-the-art of implementation was dire at this point, it was only going to be worse. The introduction of Dierential Computation Attack (DCA) by Bos et al. at CHES 2016 [START_REF] Bos | Dierential computation analysis: Hiding your white-box designs is not enough[END_REF] and Sanfelix et al. at Black Hat Europe 2015 [START_REF] Sanfelix | Unboxing the white-box: Practical attacks against obfuscated ciphers[END_REF] showed that adaptations of attacks in the grey-box model are really ecient to break whitebox implementations alike. In this context, two contests, the Whibox 2017 and 2019 [START_REF]Ches 2017 ctf challenge whibox contest[END_REF][START_REF]Ches 2019 ctf challenge whibox contest[END_REF] contests were launched. As most of the papers before, the goal was to implement the AES so that the key could not be extracted from the implementation, up to the dierence that the designs were hidden to the attackers, i.e there was no publication explaining the technique used for each implementation. At the end of both contests, the conclusion is without appeal the same: among hundreds of participants not a single implementation could stand attackers in the white-box model. However, these contests were not without any lessons. The new submitted implementations stimulated attackers to improve or develop new automated attacks. We detail these attacks in chapter 4.

In the meantime, the academic research pushed itself away from the initial problem of implementing the AES. A rst line of work was to design algorithms adapted to the white-box model for which it is easier to prove security in the white-box model as well as the black-box model. We discuss shortly this line of work in the present chapter.

Another line of work was to tweak the white-box model to get access to stronger security results. The main two example are the use of some hardware functionality or to consider only attacks characterized by malware. We discuss and formalize this variation of model in chapter 3. Lastly, the natural extension of the original AES problem is to implement another standard. The most important attempt is the community attempt at implementing ECDSA in the Whibox 21 [START_REF]Ches 2021 ctf challenge whibox contest[END_REF] contest . As for the AES, all the implementations were broken even with unknown designs (see [START_REF] Barbu | Ecdsa white-box implementations: Attacks and designs from whibox 2021 contest[END_REF] for instance).

Security of Mobile Devices

The security of sensible data on mobile devices is a growing concern in the industry as well as for consumers. The ever growing usage of small devices in the Internet of Things gives rises to fears that personal data and especially cryptographic keys are exposed to private or institutional mistreatment. We motivate the use of white-box cryptography through two contemporary examples: the use of mobile payment and the development of mobile signature.

Mobile payment In the recent years, the payment industry has vested great interests in the extension of the EMV specications [START_REF] Emv | Integrated circuit card specications for payment systems[END_REF] to mobile transactions via Near Field Communication (NFC). In that scenario, the usual contactless smart card is emulated by an NFC-compliant mobile phone or wearable device such as a smart watch. This is referred to as Host Card Emulation (HCE).

Unfortunately, mobile platforms do not provide access to a secure element to third-party applications: the SIM card belongs to the telecommunication operator and handset manufacturers keep any form of trusted hardware for their own needs.

These emerging applications are therefore facing the challenge of being as secure as a tamper-resistant hardware although being totally based on software. White-box cryptography is currently the only approach to secure these applications and compensate the security risks inherent to common embedded operating systems such as Android. By relaxing constraints on the signing utility, the eIDAS regulation opens the way to software-only solutions for digital signatures. As a result, a rapid emergence of mobile contract signing is anticipated in the near future. The user experience is straightforward: a contract (or any form of document in that respect) is downloaded on the mobile device, reviewed by the human user, digitally signed locally and the legally binding signature is returned to a back-end server where it is validated and archived. Now, the need for the signing application to be eIDAS-qualied imposes (depending on the qualication level) to resist security threats pertaining to mobile platforms and most particularly logical attacks where some form of external control is exerted through malware, typically in an attempt to steal the signing key(s) stored on the device. Whitebox cryptography is the only approach that eectively puts the signing key(s) out of reach of logical attacks on the operating system. Combined with countermeasures against code lifting, white-box cryptography is expected to take a major role in the adoption and deployment of eIDAS-based services in the EU.

Cryptocurrencies and blockchain technologies.

Today, most solutions to store cryptocurrencies and perform transactions on the blockchain are based on a hardware token (USB stick, smart card) or on a mobile application.

While the former provide adequate security, it is inconvenient for the wider usage. For the latter case on the other hand, the security often relies on the operating system of the mobile device and the principle of application sandboxing. Given the wide variety of mobile OS on the eld, strictly relying on the operating system to protect critical assets is very hazardous and must be always be avoided.

This raises a strong need for the design of security solutions for pure-software cryptocurrency wallet against all kind of threats such as stealing malwares. In order to protect the cryptographic keys intrinsically involved in cryptocurrencies and blockchain technologies, white-box cryptography is essential. As concerns digital signatures, ECDSA is currently the most used algorithm (for instance Bitcoin and Ethereum do), but alternatives are considered either for other cryptocurrencies or to prepare the post-quantum era.

Mass Surveillance and Malicious Hardware

If white-box cryptography can attempt to solve particular industrial problems, it can also propose solutions to oer better security for all citizens against monopolies and institutionalized attacks.

Malicious Hardware The basis for secure computation is a trustful hardware that correctly computes and does not leak the secret key it contains. But if the hardware is faulty -that is, outputs incorrect results on certain inputs -or at worst malicious, the security of the algorithms deployed on it is compromised.

In this context, the dangers implied by malicious hardware cannot be ignored, especially with the monopoly of few factories and the heavy cost of building new hardware factories. According to the IC Insight 2014 report, 90% of integrated circuits are made by 13 factories and none of them are in Europe. If any of said factories are found to be malicious, the repercussions could be tremendous for a large portion of users all around the world. Imagine the consequences of malicious hardware in the defense or in electrical infrastructures.

To limit the danger of such prospect, cryptographer have proposed methods such as the detection of Trojans [START_REF] Aarestad | Detecting trojans through leakage current analysis using multiple supply pad i ddq s[END_REF][START_REF] Agrawal | Trojan detection using IC ngerprinting[END_REF], or designing algorithms for this special case [START_REF] Bronchain | MOE: multiplication operated encryption with trojan resilience[END_REF].

Even if these methods are ecient to a certain degree, they all have some disadvantage : the more complex the hardware is, the harder the detection of the Trojan, and using dedicated algorithms greatly diminishes the interoperability of the protected device in its ecosystem. One other solution is to use white-box cryptography. Indeed, if an implementation is secure in the white-box model, regardless of the hardware, a malicious or faulty hardware cannot break its security properties, as it could be seen as an adversary in the white-box model. They propose a solution with the 'Bounded Retrieval Model' which consist in making the keys so big that their extraction cannot go undetected. This goal is somewhat similar to the goal of an 'incompressible' white-box implementation. In this setting, the fact that the entire implementation has to be retrieved to get the functionality ensured by the secret key would hinder attempts of extractions.

Mass surveillance

The possibility for citizens to protect their secret keys in software implementation with white-box techniques and the open access to white-box implementations that are publicly studied is an interesting track to follow to ensure overall privacy against the ever growing malware and surveillance adversaries. This is especially important when most of the solutions in these models are designed by companies, and hence often copyrighted and unavailable to the majority.

Ecological Concerns

A certain advantage of security through software is a diminishing reliance on dedicated hardware for security in our everyday life. Without a strong reliance on hardware for dedicated tasks, discussions at the societal and consumerist level can be started to elect more reasonable consumption of hardware relatively to our needs and the stress they put on our ecosystem. That is not to say that abandoning all hardware is a good solution, but having the opportunity to use secure software can open new discussions.

One of the striking examples of how hardware production is detrimental to our ecosystem is the recycling and production of secure cards such as payment cards. We take this example as it is one of the most common, but it applies to other dedicated secure hardwares. Mainly composed of PVC and rare minerals such as copper, palladium, nickel, silver and gold, payment cards are often not recycled due to security concerns and the hardness of recycling components. According to the 2020 report of the french 'Observatoire de la sécurité des moyens de paiement' (Observatory for the security of means of payment), there are currently 94 millions payment cards in circulation, more than one per citizen, which represents about 400 tons of non-recycled wastes. Considering that the mining of rare mineral is one of the most polluting industry, with the most diminishing returns as reserves expire, exploring solution to this problem seems of prime interest.

If the recycling of hardware is certainly an excellent solution to extend the life cycle of metals and plastics alike, not using dedicated hardware seems like a more radical and ecient solution, that can be discussed in our current technological ecosystem. As the 'Observatoire de la sécurité des moyens de paiement' remarks, we have seen a surge in mobile payment post-COVID crisis, which supports the idea that consumers as well as industrial are ready for such a transition. While we note that it is of course due the mainstream use of smartphones, that contains more rare minerals than smartcards, the social cost of abandoning smartphones would be way heavier than changing a mean of payment.

The study of security in the white-box model can only put more trust in softwarebased solutions and incline the public opinion to change their usage or discuss such changes.

Formalization of the Context

The goal of this section is to set a formalism to study the white-box model. We rst set the boundaries for programs and then formalize white-box compilers.

Programs

As cryptographic algorithms are implemented, they leave their realm of abstraction to become grounded programs. Programs are very formally dened in a language theoretic sense and interpreted in the context of a programming and execution model. We will however not need this level of detail for our uses. Cryptographic algorithms are usually a composition of operations on mathematical structures and often agnostic to the programming language. This is the case for most of the white-box designs proposed in the literature.

For the following, we assume that a program is a sequence of operations over data that can be implemented by any programming language such as C, Java or Python. We describe programs as operations over mathematical structures and do not specify them for any programming language. Programs can be executed, copied or modied at will, which separate them from oracle calls to an algorithm. This denition is consistent with the white-box model in which an adversary can interrupt computations at will, read memory at any point, modify values in the execution and so on.

For any program P , we note Size(P ) the size of its code ignoring the constant overhead of its programming language. This denition is consistent with the attempt to propose incompressible structures regardless of the language they are implemented on. For any input x of P , we note T ime(x) its running time on x measured in number of elementary operations on data structures, similarly to the denition of complexity of an algorithm. We note T ime(P ) if the running time is identical for all inputs.

Remark: We could be tempted to dene Size(P ) to be the minimal size of code that implements P , but as we deal with white-box implementations, this minimal size is often close to the size of the key and hence not a good measure of the size of a program that wants to hide its key.

White-Box Compiler

The goal of a white-box designer is to implement a cryptographic algorithm, that is dened by a description of the algorithm and its secret key, into a secure implementation in the white-box model. Depending on use cases, these algorithms can be encryption schemes or signature algorithms. To do so, a designer can draw randomness to 'inject' into the implementation and try to hide the key or use the structure of the algorithm itself to bury the key. To synthesize this approach, we follow [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF] and use the framework of white-box compiler.

Denition 1 (White-Box Compiler). A white-box compiler C is probabilistic algorithm that on the input of a keyed-algorithm A and a key k, outputs an implementation of A k noted C A (k) that aims to achieve security properties in the white-box model.

The Grail for a cryptographer would be to propose a compiler for entire classes of algorithms that can be applied to an algorithm without concerns for its structure.

In practice, white-box compilers are dedicated to attempt to white-box a particular algorithm. The security notions that a compiler must achieve are discussed in detail in chapter 2 and 3.

The framework of white-box compiler allows to consider a setting where two or more implementations come from a same compiler and can be used to mount more complex attacks based on the similarities between the implementation. The author of [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF] dene these attacks as 'recompiling attacks'. While they certainly need to be addressed, there is no mention of these attacks in the literature : this is probably due to the fact that regular attacks on one implementation already break most white-box candidates. As recompiling attacks are not necessary to understand the state of the art of white-box cryptography, we do not study them further. For this reason it is common to nd security claims for an implementation instead of a compiler.

Hidden and Open Designs, Chosen or Fixed

Algorithms

As the seminal problem of implementing the AES in the white-box model quickly appeared to be a hard problem, cryptographers turned themselves into variations of the initial problem to better understand the white-box model of attacks. While we thoroughly discuss the variations of the initial model of security, we want here to discuss two variations in the practice of white-box cryptography. The rst one is the degree of freedom that hidden designs of implementation allow for the security of implementations. The second one is to build algorithms designed for white-box instead of working in implementations of standardized ones.

What do hidden designs oer ?

One of the key principles of modern cryptography is Kerckho 's Principle. In its 1883 article 'La Cryptographie Militaire', Kerckho states in the jargon of its time that if a cryptographic machine should fall to the hands of the ennemies, the security of the rest of the communications should not be impacted. In modern terms, cryptographers want that cryptographic algorithms to be secure, even if everything is known about it, except its secret key. While cryptography has drastically changed since the late 19th century, this rationale of design is still core to modern cryptography. In the white-box context, the natural way to extend Kerckho 's Principle is to publicly describe the compiler that produces our white-box implementation, even if there are secret random data drawn by the compiler to produce the nal implementation.

If this rationale of design was followed by the seminal paper of Chow et al., the idea of working with implementations with hidden design began to emerge to allow degrees of freedom to designers. For instance, the biggest contests for candidate whitebox implementations, Whibox17 and 19, were working with hidden designs. While this idea might seem daring, this change of rationale is supported by multiple factors. First, the hardness of the initial problem,that is implementing the AES, did not get many advances with usual cryptographic methods. Some of the best proposed solutions such as [START_REF] Biryukov | Attacks and countermeasures for white-box designs[END_REF], relied on obscurity of the code to get concrete security, and code obfuscation techniques were seen as an opportunity to patch what state-of-the-art implementation techniques were lacking. Secondly, a setting of hidden design is closer to industrial concerns and can help bridge the gap between communities. Understanding the security of white-box products on the market is essential for the overall security, especially when very few proven solutions exist, and the 'white-box' tag is used as a marketing advantage.

However, from this change of paradigm, it seems that very little security can be gained. If we take WhiBox17 and 19 as a case of study, the observation is clear:

among the hundreds of proposed designs, none did stand in the end. The reports of attacks such as [START_REF] Goubin | How to reveal the secrets of an obscure white-box implementation[END_REF] show that after a meticulous reverse engineering work, the power of automated attacks often trivialise a key-recovery from the implementation.

Choosing the algorithm to have better implementations

The holy grail of white-box cryptography would be to have secure white-box implementation of popular standards algorithms like the AES, RSA or ECDSA. However, proposing secure implementations of said algorithms has been found to be a hard problem, with very few candidate solutions. One of the fruitful alternatives for cryptographers has been to change the algorithms to implement. If the most commons algorithms are not well-suited for certain context or problem, it is common to design new algorithms adapted for a specic context. One can note algorithms designed with minimal multiplicative depth in mind for FHE or algorithms that are designed easy to mask to improve their security against side-channel attacks. In the same fashion, it is natural for cryptographer to design algorithms tailored for the white-box model.

The line of work dedicated to a better understanding of the notion of 'incompressibility' or 'big-key' ciphers in the white-box is the most notable one. In [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF] and [START_REF] Fouque | Ecient and provable white-box primitives[END_REF],

the authors describe symmetric encryption algorithms that are proven to be secure in the white-box model. In [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF], the authors transform the public-key algorithm RSA into a private-key algorithm and prove an implementation of this algorithm to be secure in the white-box model. The proven security of these implementation is a striking advantage of these methods, compared to all the broken candidates implementations of the AES.

While it does provide practical secure white-box implementation for these chosen algorithm, the designs exposed in this line of work did not help to get a better grasp of what was needed to achieve the implementation standardized algorithms. This gap between algorithms designed with the white-box model in mind, and the common standards has yet to be bridged. Furthermore, the success of chosen algorithm constructions in the white-box model strongly highlights that designing an implementation of a standard that is not inherently adapted to white-box model -such as the AES to name but one -is a way harder problem than choosing algorithms adapted to it.

Chapter 2

The Plain White-Box Model

In this chapter, we study the plain white-box model. We contrast it with models that dier from Chow et al. initial model and that are motivated by specic use cases.

We describe them in chapter 3. After dening its boundaries, we describe security notions that are relevant to this model, in the public-key and private-key setting. We then discuss of links between white-box cryptography and other notions from the state of the art of cryptography, including identity based cryptography and cryptographic obfuscation.

2.1

What is it ? For What use cases ?

The plain white-box is the model introduced by Chow et al. in their seminal paper [START_REF] Chow | White-box cryptography and an AES implementation[END_REF].

It studies the security notions that cryptography can oer when the program computing a cryptographic algorithm is the last barrier before the attacker. This model is the most demanding since an attacker has the complete control over an implementation and each of its executions. Hence, the security notions that can be studied in this model are way weaker than the ones studied in the black-box model.

However, the notions in the white-box model are more resilient to a bad usage by its user: to void the security of an algorithm with security only in the black-box model, one only needs a user to store its key negligently, as for an algorithm implemented with security in the white-box model in mind, the security property persists even through misuse. As this model is the most generic, properties studied in this model provide security in any of the context motivated in the previous chapter.

If the model is rather simple to describe, dening the white-box attacker and understanding its power is a rather dicult problem. We dedicate the entire chapter 4 to the automated attack such attacker can perform.

The rst intuition about implementations in the white-box model is that they should guarantee the condentiality of its key. This folklore notion has been formalized has 'unbreakability'. If achieving unbreakability is the main line of work for the implementation of the AES, it is clear that this notion is not satisfactory enough. Indeed, if the key cannot be extracted by an attack, he can then attempt to steal the entire implementation. To mitigate this, the implementation can be made as big as a desired threshold, and should be able to be compressed by the adversary. This notion is aptly known as 'incompressibility'.

Similarly to the black-box model, an adversary can attempt to inverse the implementation of our cryptographic algorithm, expect this time, he has access to the implementation instead of having an oracle access to the functionality. If a program, that is computing a bijection is hard to invert with the knowledge of its implementation, we say that it is 'one-way'.

In contexts similar to DRMs, one can also want to nd the original owner of a stolen program. If an implementation can be bound to the user it has been delivered to, we say that the implementation is 'traceable'. As this notion is not one of the most studied, we do not detail it here ( [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF] for more details).

Remark on the Denomination: We add the qualier 'plain' to the white-box model to distinguish it from variations that have been studied in the literature and to avoid any confusion that can come up when comparing models, security properties that can be achieved and techniques that are available . We study these variations of the plain white-box model in chapter 3.

Security Notions

The original work of Chow et al. did not formally introduce security notions. We adapt denitions from [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF] or in the same fashion as we believe they are the closest to practical concerns and the goals of the state-of-the-art of implementations. While there have been other attempts at formalizing security notions for white-box cryptography, such as [START_REF] Saxena | Towards security notions for white-box cryptography[END_REF] or [START_REF] Fouque | Ecient and provable white-box primitives[END_REF] -for often stronger notions than the ones we will discuss -we believe that the ones we propose here are the closest to the problems implementation designers have an that they are formal enough to be interesting for more theoretical designs.

Unbreakability

The rst intuitive requirement for a white-box implementation is that is provides the privacy of the secret key embedded in the program. This the rst developed notion by Chow et al. as for them, the choice of the implementation is the last standing line of defense against an attacker. This notion of resistance to key-extraction is formalized in the state-of-the-art by "key-extraction resistance" or "unbreakablity". Unbreakability is the bare minimum a white-box implementation should satisfy.

If designing implementations that resist key-extraction was a seminal goal of whitebox cryptography, especially of the AES as noted before, it is important to note that no publicly published AES implementation satises the unbreakability property. The two implementations contests [START_REF]Ches 2017 ctf challenge whibox contest[END_REF] and [START_REF]Ches 2019 ctf challenge whibox contest[END_REF] have been a community eort dedicated to implementing an unbreakable AES, which was not a success. It is hence a reasonable basic goal to achieve for new designs.

We separate denitions in the private-key setting and in the public-key setting to highlight the dierences between the two contexts and what they imply for the obtained implementations.

In the Private-Key Setting

The most common case of study of unbreakablilty is the symmetric key encryption algorithm, so we describe unbreakability in this context. Note that it can be adapted for any symmetric algorithm. For this paragraph, let E is an encryption scheme with encryption algorithm E

Let us describe the game for unbreakability of a compiler C E :

Draw at random a key k in keyspace K

The adversary A gets the program C E (k) from the compiler

The adversary A returns a key guess k in time τ knowing C E (k)

The adversary A succeeds if k = k Denition 2. Let E be an symmetric encryption algorithm, C E a white-box compiler and let A be any adversary. We dene the probability of the adversary A to succeed in the unbreakability game by:

Succ A,C E := P[k ← K; P = C E (k), A(P) = k; k = k]
We say that C E is (τ ,ϵ)-unbreakable if for any adversary A running in time τ , Succ A,C E ≤ ϵ.

When we want to precise that the compiler is unbreakable against a certain class of attacks noted ATK, we note that the compiler is (τ ,ϵ)-UBK-ATK.

Remark: Contrary to what can be done studying when asymptotic security, we do not set A to be a polynomial adversary depending on a security parameter λ and hope that ϵ is exponentially small in λ, as we are interested in concrete security for our chosen parameters.

Remark: It is often the case that, due to fact that an adversary only get one implementation from one compiler and that not everybody uses the compiler formalism, we often say that an implementation is unbreakable by abuse.

The 'one-way function trick' The rst remark a mischievous reader would make is that it is easy to transform an encryption algorithm -or any keyed cryptographic primitive -into another encryption algorithm for which an unbreakable implementation exists, provided one way function exists. As it is indeed the case, let us describe such a method. To do so, let us consider an encryption algorithm E = (M,C,K,Setup,Enc,Dec) and a one-way function f : K → K. We dene a new encryption algorithm E ′ :

The plaintext, ciphertext and key space are identical to

E ′ M = M ′ , C = C ′ , K ′ = K
The algorithm Setup' ,on the input of 1 k , outputs a call of Setup on 1 k :

Setup ′ (1 k ) = Setup(1 k )
The algorithms Enc' and Dec' are identical to respectively Enc and Dec except they operate on the key f (k) :

C = Enc ′ k (M ) = Enc f (k) (M ) ⇐⇒ M = Dec ′ k (C) = Dec f (k) (C)
If the function f is one-way, it is then trivial that E ′ = (M',C',K',Setup',Enc',Dec') admits an unbreakable implementation. Indeed, by semantic denition, the output of Setup' k is the key of the algorithm, and f (k) is sucient to encrypt and decrypt. As a consequence, an unbreakable implementation of Enc' can be made with the value f (k) and a regular implementation of Enc calling the value f (k).

While this remark makes the unbreakability security property pretty trivial to achieve from the design of encryption algorithms, it also underlines the fact white-box construction have to be evaluated and compared in regard to a reference implementation.

It also helps to get some perspectives on the state ofthe-art of implementations against stronger security notions that can be found in the literature : there isn't any unbreakable implementation of usual standardized cryptographic algorithm such as AES or RSA in the literature.

This remark however highlights that for practical as well as for theoretical concerns, the unbreakability notion is not enough. It is obvious that if the security notion was enough for practical concerns standards could be adapted to just use the 'one-way function trick' to have unbreakable implementations.

In the Public-Key Setting

As we motivated in chapter 1, public-key algorithms and especially signatures in the white-box model are a topic of their own interest due to the technologies they facilitate.

However, very few research on this topic has been made, theoretical and practical aspects as well. We adapt here the usual unbreakability notion to signature algorithms.

The main dierence here is that an attacker has the knowledge of the public key, i.e the verication algorithm, in addition to the implementation. For the rest of the paragraph, S is a signature algorithm.

Let us describe the game for unbreakability of a compiler C S :

Draw at random a key k in private key-space K S

The adversary A gets the program C S (k) from the compiler

The adversary A returns a key guess k in time τ knowing C S (k) -and the veriying algorithm V

The adversary A succeeds if k = k Denition 3. Let S be an asymmetric signature algorithm, C S a white-box compiler and let A be any adversary. We dene the probability of the adversary A to succeed in the unbreakability game by:

Succ A,C S := P[k ← K; P = C S (k), A(P) = k; k = k]
We say that C S is (τ ,ϵ)-unbreakable if for any adversary A running in time τ , Succ A,C S ≤ ϵ.

White-Box Signatures: a 'Double Trapdoor'

It is common to have signature built from a secure trapdoor one-way function (OWF) and extended into complete signature algorithm following the so-called 'hash-and-sign' paradigm. This is the case for RSA, with FDH or PSS and for instance. It is natural to study the white-box properties of these functions and how they extend to their corresponding signature schemes. In this case, what is interesting is the implementation of the inversion of f , for which a secret is needed.

For the rest of the paragraph, f is a secure trapdoor one-way function f : X ×K → Y and C f -1 is a white-box compiler for the inversion of this function. We dene unbreakability and incompressibility, similarly as we did for signatures before. Let us describe the game for unbreakability for the compiler C f -1 : Draw at random a key k in private keyspace K

The adversary A gets the program C f -1 (k) from the compiler The adversary A returns a key guess k in time τ knowing C f -1 (k)

The adversary A succeeds if k = k Denition 4. Let f be a secure trapdoor one-way function, C f -1 a white-box compiler of its inversion and let A be any adversary. We dene the probability of the adversary A to succeed in the unbreakability game by:

Succ A,C f -1 := P[k ← K; P = C f -1 (k), A(P) = k; k = k]
We say that C f -1 is (τ ,ϵ)-unbreakable if for any adversary A running in time τ , Succ A,C f -1 ≤ ϵ.

We will then study signature schemes that are built 'on top' of the inversion of a trapdoor OWF, which a general term to qualify a lot of already existing techniques such as FDH or PSS.

Denition 5. We say that a signature algorithm S is built on top of a trapdoor one-way function f if it can be decomposed into two algorithms:

Algorithm A : On the input of an element in Im(f ), outputs one of its premimages Algorithm B : On the input of a message, outputs a signature S(m) of a message m. The algorithm B can only perform computations using the message m, public data, data drawn at random and calls to A.

With such algorithms we can reduce the unbreakability of the signature algorithm to the unbreakability of the trapdoor OWF.

Proposition 1. Let f be a secure trapdoor one-way function. Let WBf -1 be any (τ, ϵ)-unbreakable implementation of f -1 . If S is a signature algorithm built "on top" of f (Denition 4) then there exist a (τ, ϵ)-unbreakable implementation of S.

Proof: If WBf -1 is such implementation (τ, ϵ)-unbreakable, build the implementation of S by replacing any call to f -1 by a call to WBf -1 and note this implementation WBS. Now, if any attacker A breaks the (τ, ϵ)-unbreakability , one can build an attacker A ′ breaking WBf -1 by simply building WBS and running A. This is absurd by unbreakability of WBf -1 .

For this category of algorithm, producing a white-box implementation a signature algorithm is very similar to introducing a second trapdoor to the function f . Indeed, if the rst trapdoor is compute f -1 wit the secret-key, the implementation can be seen as the second trapdoor intermediate trapdoor that allows to compute f -1 without revealing the secret-key. This draws similarities with identity-based encryption we describe later on.

Remark : Note that this property is not trivially generalized to incompressibility.

Indeed, composition of incompressible function do not always behave nicely.

Incompressibility

When a white-box implementation is unbreakable, one can try to retrieve the complete implementation to circumvent the fact that the key can't be extracted. While implementations can be hardware bound, it is not possible in the plain white-box model.

To mitigate this, the implementation can be made big enough and incompressible to dissuade attackers to attempt a code-lifting attack depending on the context. This goal is similar to big-key ciphers of Bellare et al. [START_REF] Bellare | Big-key symmetric encryption: Resisting key exltration[END_REF] but on the implementing side rather than the design side.

If the unbreakability notion is in practice the most studied one through challenge implementations, the incompressibility notion is the one that has been the most studied generically. For instance, Bodganov et al. [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF] study the 'space-hardness' of ciphers, which is essentially imcompressibility, itself based on the weak white-box security of [START_REF] Biryukov | Cryptographic schemes based on the ASASA structure: Black-box, white-box, and public-key (extended abstract)[END_REF]. Fouques et al. The paper of [START_REF] Fouque | Ecient and provable white-box primitives[END_REF] study weak and strong incompressibility and design a dedicated encryption algorithm satisfying these properties. While some of these denitions are interesting on their own, we believe that the notion of incompressibility we present here, adapted from [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF], is a good synthesis of them and is grounded in implementation attempts.

In the Private-Key Setting

Similarly to unbreakability, we describe the notion of incompressibility in the privatekey setting for encryption algorithms as it is the most common use case. Still, the denition can be adapted to any private-key algorithm.

We now describe, for any σ > 0 the game of incompressibility for a compiler C E :

Draw at random a key k in keyspace K

The adversary A gets the program C E (k) from the compiler

The adversary A returns a program P knowing C E (k)

The adversary A succeeds if P ≈ C E (k) and size(P) ≤ σ Denition 6. Let E be an symmetric encryption algorithm, C E a white-box compiler and let A be any adversary. We dene the probability of the adversary A to succeed in the σ-incompressibility game by:

Succ A,C E := P[k ← K; P = A(C E (k)) ; P ≈ C EN C (k); (size(P) ≤ σ)]
Moreover, we say that C S is (σ,τ ,ϵ)-incompressible if for any adversary A, Time(A)+Time(P ) < τ implies Succ A,C E ≤ ϵ.

When we want to precise that the compiler is (σ,τ ,ϵ)-incompressible against a certain class of attacks noted ATK, we note that the compiler is (σ,τ ,ϵ)-INC-ATK.

Remark: This denition can usually be found with a parameter δ that allows the program P to agree with the targeted function with probability δ. As no known attack exploits this fact yet, we did not include it for sake of clarity and simplicity.

The denition of incompressibility we propose here is a slightly corrected version from the usual one used in [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF]. Indeed, this one is awed as it does not constrain the running time of the program P. If the running time is not bounded we can propose a compression of any white-box algorithm by using brute force: an attacker can compute few pairs plaintext-ciphertext, and code the brute force attack on the primitives that is white-boxed, and then code the computation of the primitive with the key found. This program can be made with few lines of code, is identically functional to the whitebox code, but has an unreasonable running time. That is why we add a new time constraint: we want that the sum of the running time of the attacker and the program produced is less than a constant τ representing the whole computation time allowed.

Remark: Note that if a compiler is not unbreakable, then it cannot be incompressible for reasonable security levels: the key-recovery is indeed an extreme compression of a white-box implementation.

In the Public-Key Setting

Similarly to unbreakability, we describe the notion of incompressibility in the public setting for signature algorithms as we will need it for part III later on. This can easily be adapted to public-key encryption algorithms.

We now describe, for any σ > 0 the game of incompressibility for a compiler C S : Draw at random a key k in private keyspace K S The adversary A gets the program C S (k) from the compiler The adversary A returns a program P knowing C S (k)

The adversary A succeeds if P ≈ C S (k) and size(P) ≤ σ Denition 7. Let S be an asymmetric signature algorithm, C S a white-box compiler and let A be any adversary. We dene the probability of the adversary A to succeed in the σ-incompressibility game by:

Succ A,C S := P[k ← K; P = A(C S (k)) ; P ≈ C S (k); (size(P) ≤ σ)]
Moreover, we say that C S is (σ,τ ,ϵ)-incompressible if for any adversary A, Time(A)+Time(P ) < τ implies Succ A,C S ≤ ϵ.

Metrics for Incompressibility

While the notion of incompressibility is well discussed in the state of the art, the eld lacks good metrics to measure if the size σ of an implementation is satisfactory enough. Is it the ratio of the size to the key to the implementation ? Is it is the size of the implementation only ? The ratio size to key is probably a bad one as there exist algorithms with bigger keys than other for the same security level, and the absolute size of the implementation is completely depending on the usage of said implementation. If we can provide a functional white-box implementation with σ ≈ 2 40 , few GB for instance, retrieving it could probably be detected, but the running time of the implementation would be considerable. In that sense, smaller implementations might be more useful. However, if the reduction is too ecient with σ ≈ 2 20 , the incompressibility criteria might not be useful anymore: an attacker extracting the code from a device could remain unnoticed.

Overall, more grounded metrics for concrete use cases should be discussed to attempt to bridge the gap between the new incompressible algorithms the state-of-the-art proposes, and the implementations of standards that are motivated by concrete use in the industry.

The 'one-way function trick' meets composition

If the unbreakability notion suered from a denitional problem caused by the possibility of using the 'one-way function trick', the incompressibility property suers from a similar default. Indeed, this time, one can attempt to consider an encryption algorithm E that has been modied into E ′ following the one-way function trick, expect this time, any input x is replaced by f (x) where f is any bijection that admits an incompressible compiler.

If it is tempting to assess that the new E ′ admits a trivial incompressible compiler, some counterexamples show that one has to be careful. For instance, if E = f -1 , the incompressibility property completely vanishes. This shows that a composition of incompressible functions is not always incompressible and that incompressibility of complex algorithms can only be stated through precise analyses.

However, similarly to proofs of security in the random oracle model for hash and sign algorithms, if f is 'random' enough in regard to E, the composition has great chances to be incompressible.

One-Wayness

In the private-key setting, a natural improvement of the unbreakability notion is to require that the implementation cannot be inverted. Indeed, having both the functionality of encrypting and decrypting is equivalent to having the complete functionality of an encrpytion algorithm and its secret key, up to the size of these programs and the time computing these functionality takes. The idea is to extend the property of one-wayness of functions to the context a white-box program Let us describe the game for one-wayness of a compiler C E : Draw at random a key k in key-space K

The adversary A gets the program C E (k) from the compiler The adversary gets an encryption c of a random message m

The adversary A returns a message guess m in time τ knowing C E (k) and c

The adversary A succeeds if m = m Denition 8. Let E be an symmetric encryption algorithm, C E a white-box compiler and let A be any adversary. We dene the probability of the adversary A to succeed in the one-wayness game by:

Succ A,C E := P[k ← K; P = C E (k), A(P, c) = m; m = m]
We say that C E is (τ ,ϵ)-one-way if for any adversary A running in time τ , Succ A,C E ≤ ϵ.

When we want to precise that the compiler is one-way against a certain class of attacks noted ATK, we note that the compiler is (τ ,ϵ)-OW-ATK.

Remark : The notion of one-wayness is only interesting in the symmetric setting, as in the asymmetric setting, an inversion of the algorithm is possible via the public-key.

Remark : There is a trivial reduction from one-wayness to unbreakability as recovering the key allows to invert an encryption algorithm.

For a private-key encryption algorithm, having a one-way implementation is similar to transforming it into a public-key algorithm. The implementation can indeed be seen as a public-key as it is sucient to encrypt messages -but cannot be used to decrypt as it is one-way -and the secret-key still allows for decryption. This idea was already developed by Die and Hellman in their famous [START_REF] Die | New directions in cryptography[END_REF], where they advocate for the existence of public-key encryption, when no construction was known, through 'obfuscating' the program of a private-key algorithm.

What do we know about these notions

The goal of this section is to give insights on links between white-box cryptography and other state-of-the-art notions of cryptography or mathematics. We rst discuss incompressible structures at large and then draw similarities between public-key white box and identity-based cryptography. We nish this section by discussing the links between cryptographic obfuscation and white-box cryptography.

Incompressible Structures

For mathematicians, the rst intuition of incompressibility comes from Kolmogorov's complexity. In his axiomatic approach to the theory of probability in 1965, Kolmogorov

Links with Identity-Based Cryptography

Identity-Based Cryptography was conceptualized to answer the question: "is it possible to use human readable common data, such as e-mail addresses, to derive safe cryptographic key ?". This concept was rst introduced by Shamir in 1984 with an instantiation of a signature scheme [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. The problem of building an identity-based

encryption scheme was open until 2001 with the pairing-based of Boneh and Franklin [START_REF] Boneh | Identity-based encryption from the weil pairing[END_REF] for instance.

The goal of Identity-Based Cryptography is to replace the random public key -that is generated in the context of an asymmetric algorithm -by publicly available data linked to a user. As a consequence, the public key of such scheme is usually known is advance for it is an e-mail adress, a name, or any semantic data derived from the user, i.e. its identity for the scheme. The main problem is to derive the secret-key from this public semantic data. Contrary to usual public-key cryptography, the secret-key is derived by a trusted central authority.

In this paragraph, we focus on identity-based encryption (IBS) as we believe it has the most pertinence, but the following remark can be applied to identity-based encryption (IBE). Formally an IBS is a signature scheme described by 4 algorithms:

IBS -SETUP :The trusted identity generates a master secret key M SK and a master public-key M P K

IBS -SETUP(1 k ) = (M SK, M P K)
IBS -EXTRACT : For any semantic data ID of a user, the trusted authority computes from MSK and MPK, the secret-key of the user SK ID .

IBS -EXTRACT(ID, M SK, M P K) = SK ID IBS -SIGN : Given MPK and SK ID , one can compute the signature of M :

S = IBS -SIGN M P K,SK ID (M )
IBS -VERIF : Given a signature (S,M) , and the public-key MPK anyone knowing ID can compute:

IBS -VERIF M P K,ID (S, M ) = 1 iif S = IBS -SIGN M P K,SK ID (M )
Remark: It is important to remark that the trusted authority does not take part in the communication after key-generation. Conversely, the key SK ID is generated without the intervention of the signer.

For an IBS scheme to be of any use, the information of ID or MPK must not leak information about the secret key SK ID in addition to being secure in the classical black-box sense.

We now make the remark that an IBS scheme can be seen as an unbreakable signature scheme and its white-box implementation. Indeed, let us assume that (IBS -SETUP, IBS -EXTRACT, IBS -SIGN, IBS -VERIF) is a secure IBS scheme in the black-box model. We dene the public-key signature algorithm Sw/oIB by: Sw/oIB -SETUP : For a xed value ID, the algorithm rst computes IBS -SETUP(1 k ) = (M SK, M P K). The algorithm outputs the secret-key SK and the public-key P K Sw/oIB -SETUP(1 k ) = (SK, P K) = (M SK, (M P K, ID))

Sw/oIB -SIGN : Given a secret key SK from Sw/oIB -SET U P , the algorithm computes IBS -EXT RACT (ID, M SK, M P K) = (M P K, SK ID )

one can then compute the IBS signature of M :

S = Sw/oIB -SIGN SK (M ) = IBS -SIGN M P K,SK ID (M )
Sw/oIB -VERIF : Given a signature (S,M) , and the public-key P K = (M P K, ID) anyone knowing ID can compute :

Sw/oIB -VERIF P K (S, M ) = 1 iif S = IBS -SIGN M P K,SK ID (M )
The scheme Sw/oIB is just a rewriting of the IBS scheme where the generation of the ID related key is relegated to the signer. The algorithm we obtain is just a public-key signature scheme, without any identity based property. In this scheme, the master secret key MSK can be seen as the only secret element, with SK ID only being an information computed at the time of signature. To get an unbreakable white-box implementation of Sw/oIB, one would need to 'hide' the key MSK, but the IBS scheme is already tailored for that as the secret key SK ID (output of the extraction IBS -EXTRACT) can be used for signing and the security of IBS is based on the fact that recovering MSK from SK ID is hard. We hence get then the trivial property:

Proposition 1. Let IBS be a secure identity-based signature scheme and Sw/oIB its associated public-key signature scheme. Let WB-Sw/oIB be an implementation of Sw/oIB where the key SK ID from the extraction IBS -EXTRACT(ID, M SK, M P K)

is hardwired into the implementation instead of the master-key MSK and Sw/oIB -SIGN SK is replaced by IBS -SIGN M P K,SK ID . The imple- mentation WB-Sw/oIB is unbreakable for the same level of security as the black-box security of IBS.

If this remark highlights the similarities between Identity-Based Signatures and what

we require from white-box implementations of traditional pubic-key signatures, it fails to deliver solutions for concrete implementations techniques.

First, this remark only applies to the unbreakability property. Indeed, if we want to extend this result to incompressibility, we have to then consider the sizes of the keys MSK and SK ID , which are the only dierent elements from one implementation to the other. Usually, the sizes of these keys are quite similar and having big keys SK ID is not a goal of this area of research. In that sense, this remark is quite close to the "one-way function trick" (section 2.2) to get trivial unbreakable implementation of symmetric algorithms.

Secondly, while designing unbreakable or incompressible public-key signature algorithms from scratch, i.e. without implementing a standard or already deployed algorithm, can be an interesting area of research as it was done for block-ciphers [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF][START_REF] Fouque | Ecient and provable white-box primitives[END_REF],

this link with identity-based cryptography does not seem to help design implementations of standards such as RSA or ECDSA. Indeed, designing IBS schemes is already a hard problem, but transforming a traditional PKC signature algorithm into an IBS one seems out of reach for now.

To us, the important conclusion of this analogy is that the kind of 'double trapdoor' structure that white-box cryptography needs in the public-key setting exist in the eld of cryptography, which opens the room for more experimentation and designs and possibly for new PKC signature algorithms designed with their white-box implementation in mind.

Links with Cryptographic Obfuscation

The eld of cryptographic obfuscation has a lot of similarities with the goal of white-box cryptography. Especially, obfuscation techniques have been envisioned as possibilities to get white-box implementations. To precisely compare them and to see what can be learned from it, let us quickly introduce it.

The goal of cryptographic obfuscation is to construct a compiler O that transforms a program P into a functionally equivalent program O(P ) that is "unintelligible". First formally introduced by Hada in [START_REF] Hada | Zero-knowledge and code obfuscation[END_REF], dening properly what "unintelligible" means for such generic obfuscator -that is, that works for any class of programs -to exist has been the rst diculty. The work of Barak et al. [START_REF] Barak | On the (im)possibility of obfuscating programs[END_REF] formalizes the notion Virtual Black-Box Obfuscation which is pretty intuitive: the obfuscated program should not give more information than a black-box access to its functionality. Formally: Denition 9 (VBB Obfuscation). An algorithm O, which when given a circuit in C outputs a new circuit, is said to be a black-box obfuscator for the family C, if it has the following properties:

Preserving Functionality:

There exists a negligible function neg(n) such that for any input length n, for any ∀C ∈ C n :

P[∃x ∈ {0, 1} n : O(C)(x) ̸ = C(x)] ≤ neg(n)
The probability is over the random oracle and O's coins.

Polynomial Slowdown: There exists a polynomial p(n) such that for all but nitely many input lengths, for any C ∈ C n , the obfuscator O only enlarges C by a factor of p:

|O(C)| ≤ p(|C|).

Virtual Black-box:

For any polynomial-sized circuit adversary A, there exists a polynomial-sized simulator circuit S and a negligible function neg(n) such that, for every input length n and every C ∈ C n :

|P[A(O(C)) = 1] -P[|S C (1 n ) = 1]| ≤ neg(n)
Where the probability is over the coins of the adversary, the simulator and the obfuscator. In the presence of a random oracle, the probability is also taken over the random oracle.

However, in the same paper, Barak et al. [START_REF] Barak | On the (im)possibility of obfuscating programs[END_REF] prove that generic VBB obfuscators do not exist. To prove their result, they exhibit a special family of functions that have the property of leaking a secret on the input of a program that computes its own functionality. While this result proves a generic impossibility, it does not rule out the possibility of building VBB obfuscation for commonly used cryptographic primitives such as the AES. Having a VBB implementation of the AES would be ideal since it would trivially give a unbreakable and one-way implementation of the AES.

Since there are impossibility results for VBB in the standard model, the cryptographic community has shifted from the study of VBB obfuscation to a weaker notion of obfuscation, Indistinguishability Obfuscation (iO), that was rst introduced in the same article by Barak et al. [START_REF] Barak | On the (im)possibility of obfuscating programs[END_REF]. Roughly, the goal of iO is to transform a program into a pseudo-canonical form of it. This way, the obtained program should not leak more information than any program computing the same function. We recall the formal denition of iO: Denition 10 (iO). A probabilistic polynomial algorithm O, which takes as input a circuit in C and outputs a new circuit, is said to be an indistinguishability obfuscator for the family C, if it has the following properties:

Preserving Functionality:

There exists a negligible function neg(n) such that for any input length n, for any ∀C ∈ C n :

P[∃x ∈ {0, 1} n : O(C)(x) ̸ = C(x)] ≤ neg(n)
The probability is over the random oracle and O's coins.

Polynomial Slowdown: There exists a polynomial p(n) such that for all but nitely many input lengths, for any C ∈ C n , the obfuscator O only enlarges C by a factor of p:

|O(C)| ≤ p(|C|).

Indistinguishable Obfuscation: For all large enough input lengths, for any circuit C 1 ∈ C n and for any circuit C 2 ∈ C n which computes the same function as

C 1 with |C 1 | = |C 2 |, the two distributions O(C 1 , r) and O(C 2 ,
r) over the coins of the obfuscator are computationally indistinguishable.

After the rst plausible construction of iO by [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF], research bloomed on the subject and numerous applications of iO were found, including new cryptographic primitives.

Here is a short list of the notable primitives that iO could achieve:

Functional Encryption [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF] (open problem since 2005) Deniable Encryption [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF] (open problem since 2006) Multiparty Key Exchange [START_REF] Boneh | Multiparty key exchange, ecient traitor tracing, and more from indistinguishability obfuscation[END_REF] Universal Witness Signature [START_REF] Qian | Universal witness signatures[END_REF] (open problem since 2010)

As it was forecast, iO is indeed be a cryptographic master tool. The celebrated line of work leading to the result of Jain et al. [START_REF] Jain | Indistinguishability obfuscation from well-founded assumptions[END_REF] lately proved that a polynomials iO compiler exists under standard assumptions, while a realistic implementation is still out of reach for usual algorithms.

Link with white-box cryptography While white-box focuses on cryptographic algorithms such as encryption or signature algorithms, cryptographic obfuscation aims to be applicable to any program. Cryptographic obfuscation also radically diers from practical code obfuscation techniques, for it tries to proves its security based on standard assumptions while the other do not. The existence results for iO ensure that polynomial constructions exist, but the solutions tailored for a cryptographic algorithms will surely be more ecient.

We mention an interesting result of construction of white-box implementations provided that the targeted white-box properties exist. If a white-box compiler can do it, then an iO obfuscator can too. We state the result for unbreakability but it can also be extended to one-wayness and incompressibility. Let us rst assume that we extend the notion of white-box compiler to match an obfuscator, that is, our compiler is now dened for any class of circuit C n and satises 'Preserving Functionality' and 'Polynomial Slowdown'. In that case: Proposition 2. Let O a generic iO obfuscator and P a family of keyed-algorithms.

If there exist an (τ, ϵ)-unbreakable compiler W B with polynomial slowdown for the family of P, then O is a (τ, ϵ)-unbreakable compiler for P.

Proof. Let n ∈ N * and P ∈ P n . For a xed key k, the implementation W B(P k ) is (τ, ϵ)-unbreakable by hypothesis and its size λ is polynomial in n. Now, consider an implementation of Pk pf P k that is obtained by padding P k to the size λ. The programs W B(P k ) and Pk are of the same size and functionally equivalent. As W B is unbreakable for exponential security parameters, the implementation O(W B(P k )) is also unbreakable as O is polynomial. By the indistinguishably of O, the output programs distribution O(W B(P k )) and O(P k ) are computationally indistinguishable. If the program O(P k ) is not unbreakable, this means that the key-recovery is a distinguisher between the two distributions, which is absurd. The compiler O is thus unbreakable.

Remark: It is important to note that this result in asymptotic and hence might not be useful at all in the concrete context of white-box cryptography applied to the AES-128 primitive. It is however helpful to understand the similarities between the notions. Lastly, a line of work initiated by Alpirez-Bock et al. [START_REF] Bock | Security reductions for white-box key-storage in mobile payments[END_REF] where they use obfuscation techniques in addition to a specic hardware to prove strong security properties. We explain this line of work in more details in chapter 3.

Discussing an Impossibility Result

In 2020, Alpirez Block et al. published, in [START_REF] Bock | On the security goals of white-box cryptography[END_REF], a result concerning the impossibility of a secure generic compiler in the white-box model. Their result uses the same construction as the generic VBB impossibility result of Barak et al. of 2001 [5] and

gives the example of a secure encryption scheme that cannot be white-boxed that we briey recall.

Starting from a secure encryption scheme with encryption algorithm E, they design a new encryption algorithm E ′ that, on the input of a message that is the code of an encryption scheme, outputs the key of E, and on the input of a regular message, outputs the corresponding output ciphertext of E. The technical detail of checking the input is dealt with a simple pseudo-random functions, which makes the construction feasible for any encryption scheme. Such algorithm E ′ can still be proven secure, and no secure white-box implementation can be made: if one gets an implementation of E ′ , on the input of the same implementation, the key is output to an attacker.

While this result once again shows the similarities between obfuscation and whitebox, it does not motivate a complete change of paradigm nor does it give insight to the hardness of the problem for real cryptographic algorithms. Indeed, the VBB impossiblity result forced to change notions of obfuscations because the nature of cryptographic obfuscation is to be generic. The goal of white-box cryptography however, is to implement concrete functions that represent a tiny small amount of programs. For instance, a VBB implementation of the AES might still exist as the impossibility result of VBB does not rule it out and the same is true for an AES white-box secure implementation.

Chapter 3 Variations of the Plain White-Box Model: The Remote Access White-Box Model and Hardware-Module White-Box Model

The study of the plain white-box model is now about two decades old. In these decades, the cryptographers grown unsatised with some aspects of this model. First, the hardness of providing any secure implementations of standards in this model made deployment of peer reviewed implementations in the industry impossible. This established a gap between the concrete products that contain white-box implementations and the academic attempts towards secure implementations. Secondly, the security properties that can be achieved in the plain white-box model are sometimes too weak to ensure any security depending on the context. For instance, white-box implementations of encryption algorithms in the plain white-box model can be used to encrypt messages, which is a no go for certain applications.

In the recent years, two other main models, have emerged. The rst model is the Remote Access White-Box model, which attempts to capture the attack model of malware that are planted on a target hardware and remotely communicate with an attacker. The second one is the Hardware Module White-Box model, which studies secure implementations based on small secure hardware components.

If these two models were originally presented as security notions in the context pf the the white-box model, we here want to set them apart from the plain white-box model for sake of clarity and for a fair comparison with the security implementations can achieve in these model compared to the plain white-box model.

The Remote Access White-Box Model

To the best of our knowledge, the rst evocation of the Remote-Access White-Box model was made by Todo et al. [START_REF] Todo | Hybrid code lifting on space-hard block ciphers application to yoroi and spnbox[END_REF] to study the space-hardness [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF] of two blockcipher built for the white-box model, SPNbox [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF] and Yoroi [START_REF] Koike | Yoroi: Updatable whitebox cryptography[END_REF]. The authors describe the 'hybrid' setting of their attack in the following way. If a malware is planted on a device to target an implementation, it can compute specic information about the implementation on site before sending it to a black-box adversary that has more computation power than the device allows. This setting seems interesting to us as it highlights the asymmetry of capabilities between some devices where white-box implementations are deployed (smartwatches, TVs, ...), that have limited RAM, hard-memory or computational power, and the usual cryptographic adversary: data needs to be extracted from the device to perform more sophisticated attacks, which can be hard to do remotely. While this does not guarantee security against an adversary that can extract unlimited amount of data, this encapsulates the weaker and common adversaries such as malware.

We now formally describe the Remote Access model. In this model, we consider that an adversary only has remote access to the device where the implementation is deployed. We suppose that this device has memory µ 1 and can run for a time τ 1 .

To attack the implementation, the adversary has two possibilities: he can mount the attack on this device or extract a certain quantity of information δ to mount an attack with its own memory µ 2 and running time τ 2 ( Figure ?? ). Note that we add the memory constraint to the usual model that cannot be found in [START_REF] Hosoyamada | A modular approach to the incompressibility of block-cipher-based aeads[END_REF][START_REF] Todo | Hybrid code lifting on space-hard block ciphers application to yoroi and spnbox[END_REF] to grasp the real behavior of devices. To distinguish the two phases of the attacks, we divide the attacker into two subattackers, A M W that builds and plant the malware and A remote that carries on the black-box attack in the end.

Black box White box

This model is in essence very similar to the setting for strong incompressibility of [START_REF] Fouque | Ecient and provable white-box primitives[END_REF] except the leakage is here computationally bounded but is only restricted by minentropy in [START_REF] Fouque | Ecient and provable white-box primitives[END_REF]. Another main dierence is that strong incompressibility was introduced to get provable security while security in the remote-access model is similar to the notions we described in the plain white-box model and security is based on the analysis of the best known attacks against the construction.

One of the motivations of studying this model is that by relaxing the plain whitebox model, designers might achieve stronger securities properties that are useful in concrete cases. The asymmetric computational restriction (τ 1 , µ 1 ) from the target hardware greatly empowers designers, at least at rst glance.

Security Notions

As the remote-access model is a restriction of the plain white-box model, notions such as unbreakablility, incompressiblity and onewayness can still be studied. However, has the model restricts the plain white-box attacker, one can hope for stronger security notions, especially with the oine phase the model introduces. Similarly to chapter 2, we adapt security notions in the framework of [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF].

Notions from the Plain White-Box Model Let E be a symmetric encryption algorithm, C E a white-box compiler, let µ 1 , τ 1 , µ 2 , τ 2 ∈ N * , A be any adversary and D W B any data set of size δ that can be extracted from C E in time τ 1 and memory µ 1 in the white-box model. We dene the probability of the adversary A to succeed in the remote access unbreakability game by: A key k is chosen at random and a program C E (k) is computed by the compiler The adversary A creates a malware -or lifter. To create this malware M , the adversary only has remote-access to the devices, which is modeled as a black-box access to C E (k).

Succ A,C S ,D W B := P[k ← K; P = C S (k), A(O S(k) , D W B ) = P; P ≈ C E (k); size(P) < σ] We say that C E is (δ, (µ 1 , τ 1 ), (µ 2 , τ 2 )), σ, ϵ)-remote access incompressible if C E is (µ 1 , τ 1 , ϵ)-
Once the malware is built, it is planted and can perform any white-box attack in time τ 1 and memory µ 1 . It then leaks a data set D of size δ Finally, the adversary A can attack C E (k) in the black-box model aided by the leakage D.

In PRP security, the real game needs it ideal alternative. To do so, the authors use a simulator S that simulates the behavior of the malware M on the implementation. Formally, S is an algorithm that on the input of M and the functionalities E and E -1 , outputs a data set D IDEAL of size δ that is indistinguishable from the leakage D made by M . Hosoyamada et al. detail how such simulator should function, but we only assume here that it can be made in reasonable time.

We now describe these two games. The real experiment is as follow:

A key k is drawn at random and a program C E (k) is computed by the compiler

A M W builds a malware for C E (k). The malware leaks D = M W (C E (k)) to A
A tries to distinguish E k from an random permutation by using D and blackbox access to C E (k). It outputs

Exp P RP -real E,C E (k),A = 1 if it thinks it is random, 0 otherwise
The ideal game goes as follows.

A random permutation σ ∈ S n is drawn at random A M W builds a malware M W for σ.

The simulator S simulate the leakage that would produce M W on the input of a programm computing σ, leaking a data set D IDEAL A tries to distinguish σ from a random permutation by using D IDEAL and black-box access to σ. It ouputs Exp P RP -ideal

S,A = 1 if it thinks it is random, 0 otherwise Denition 12. Let E be a symmetric encryption algorithm, C E a white-box com- piler, let µ 1 , τ 1 , µ 2 , τ 2 ∈ N * , A = (A remote , A M W
) be any adversary. We dene the probability of the adversary A to succeed in the remote access unbreakability game by:

Succ A,C S ,D W B := |P r[Exp P RP -real E,C E (k),A = 1] -P r[Exp P RP -ideal S,A = 1]|
We say that the compiler C E is (δ, µ 1 , τ 1 , µ 2 , τ 2 , q, q sim , ϵ)-remote-access PRP secure if for any adversary A M W running in time and memory τ 1 , µ 1 leaking data sets δ in the white-box model and A remote running in time and memory τ 2 , µ 2 with at most q queries to C E (k) in the black-box model, there exists a simulator S that makes at most q sim queries such that Succ A,C S ,D W B ≤ ϵ.

As the authors of [START_REF] Hosoyamada | A modular approach to the incompressibility of block-cipher-based aeads[END_REF], the goal of this security notion is not to be proved, but to be tested against the best attack found in the literature, like it is common for the PRP property of usual algorithms. The authors also give SP ACE -n α [START_REF] Bogdanov | White-box cryptography revisited: Space-hard ciphers[END_REF], α ∈ {8, 16, 24, 32} as a candidate for remote-access PRP. They conjecture that it is the case for τ 2 = 2 128 ,q = 2 128 , δ = (128 -n α ) × 2 n α-2 and ϵ << 1 as long as τ 1 << q sim < 2 128 . This means that the property is essentially broken once few tables have been leaked.

A Lack of Benchmarks

The model is young, with very few publications on the topic. The rst conjectures of security about algorithms from the state of the art were made by Todo et al. [START_REF] Hosoyamada | A modular approach to the incompressibility of block-cipher-based aeads[END_REF].

These conjecture are essentially parameterized by δ and (τ 1 , µ 1 ). To know if these security conjectures are of any use, one needs to evaluate them in the context of concrete use cases.

A lack of benchmark for the hardware parameters It is natural in white-box works to ignore hardware specication, as it is the essence of the model. However, in the remote-access model, the parameters τ 1 and µ 1 are derived from concrete hardware.

Their specications vary : an hardware on a smartwatch, a TV or a smartphone might be really dierent. The power consumption on devices on batteries also intervene in the estimation of the time that the device can run the malware. As the model matures, these estimations have to come into play to ground the solutions proposed and evaluate the concrete utility of the construction.

A lack of study of the control of the extraction of data The argument of the hardness of huge data extraction on devices is a long time participant in white-box discussions to bind implementations to hardware. Since the introduction of the notion of incompressibility in the plain white-box model and works on 'big-key' ciphers [START_REF] Bellare | Big-key symmetric encryption: Resisting key exltration[END_REF], the argument that sensible data has to be made as big as possible to make the task of code lifting dicult is central to usefulness of the solutions. However, the actual means of assuring it or the amount of data extraction that can be detected is never detailed.

3.2

The Hardware Module White-Box Model Applications using secret data on devices such as smartphones are already deployed nowadays and widely used, notably for mobile payment. If the security of payment cards is usually a problem studied in the grey-box model of attacks as the smart card provides hardware security, the same cannot be said for mobile payment. In this setting, applications run on smartphones can be targeted by malware or a white-box adversary.

The industrial solutions to this problem often come with the usage of a trusted component in the device that will handle sensible computations. However, the solutions often vary due to the the available hardware. For instance, Apple smartphones all have their dedicated secure component, while only the top-end Android phones have them, and they dier from one supplier to the other.

In this context, the authors of [START_REF] Bock | On the security goals of white-box cryptography[END_REF] advocate the usage of hardware to provide hardware-binding properties, a property that cannot be achieved in the plain white-box model. The rationale is the following. If one can have a small secure hardware with a set functionality, one can attempt to bootstrap the security property from the hardware to multiple software implementation of cryptographic algorithms. The hardware will then be necessary to the implemented algorithm, and the functionality of said algorithm cannot be replicated by the an attacker that would retrieve the implementation, leaving the hardware on site. While this idea is not novel per se as we will see in section 3.2.2, their paper is the rst to label model and security notions as white-box cryptography. For the rest of the section we will assume that we can have access to hardware in the form of a hardware module. The hardware-module HM W is assumed to be tamper-proof, to be computationally bounded and to be equivalent to having a blackbox access to its functionality. For the rest of this section we consider the case of a symmetric encryption algorithm.

Security Notions

The notions can easily be adapted to the case public-key encryption or signature when the notion is meaningful.

Notions from the Plain White-Box model

As this model is a strong relaxation of the plain white-box model, an implementation in the hardware-module white-box model should at minimum satisfy notions such as unbreakability or one-wayness. However, the main motivation of this model is to exceed plain white-box security properties.

Hardware Binding

The adaptation of incompressibility as a code-lifting counter measure in the context of hardware-module is hardware-binding. The goal is to ensure that the functionality of the program cannot be used without the hardware on the device. This is the most basic property an implementation should achieve in this model.

We now describe, for any τ > 0 the game for hardware-binding security for a compiler C E : Draw at random a key k in private key-space K E The adversary A gets the program C E (k) from the compiler that can make calls to a hardware module HW M .

The adversary A returns a program P knowing C E (k) and making calls to HM W . The adversary A succeeds if P ≈ C E (k) and P does not make calls to HM W . Denition 13. Let E be an encryption algorithm, C E a white-box compiler and let A be any adversary. We dene the probability of the adversary A to succeed game by:

Succ A,C E := P[k ← K; P = A(C E (k), HW M ) ; P ≈ C E (k)]
Moreover, we say that C S is (τ ,ϵ)-hardware bound if for any adversary A, Time(A)+Time(P ) < τ implies Succ A,C E ≤ ϵ.

However, as the model oers more powerful methods to protect implementation by bootstrapping the security from a secure element to the implementation, one can aim for stronger security notions. Indeed, an implementation that is bound to a hardware, there is still the possibility to inverse it on site. The ideal security notion would be to match the properties such as IND-CPA in the white-box model.

Closing the Gap with the Black-Box model

Similarly to the remote-access model, the natural idea of a stronger security model than the plain white-box model is to achieve equivalent notions to black-box notions such as IND-CCA for encryption algorithms or Existential Forgery for signature.

The approach taken by the literature is to extend indistinguishability notions to the hardware-module context. The papers of [START_REF] Agrawal | White-box cryptography with device binding from token-based obfuscation and more[END_REF][START_REF] Bock | On the security goals of white-box cryptography[END_REF][START_REF] Bock | Security reductions for white-box key-storage in mobile payments[END_REF], respectively dene hardwarebinding security for encryption schemes, hardware-binding security for payment functionalities and security of 'global white-boxes'. Global white-boxes are out of the scope of this thesis.

These security properties aim to distinguish the behavior of the implementation on the device compared to a simulated one, similarly to the remote-access case or to cryptographic obfuscation security notions. We refer to the individual papers to the exact security properties.

Examples of Constructions

The goal of this section is to explore the solutions that are present in the state of the art. We review two constructions that are presented as white-box solutions and two solutions from the obfuscation state of the art, that have surprisingly not being considered in white-box publications.

Constructions under the White-Box label

The paper of Alpirez-Bock et al. [START_REF] Bock | Security reductions for white-box key-storage in mobile payments[END_REF] introduces the idea of using hardware modules to add security to software implementations. This started a line of work studying security properties of implementations using said methods. These works however do not detail hardware specications, nor software overhead -when it is concretely computable. This bias is interesting as it is the opposite goal of the model.

White-Box Key Derivation Function Following security benchmarks of Mastercard and EMVCo, Alpirez-Bock et al. [START_REF] Bock | Security reductions for white-box key-storage in mobile payments[END_REF] build a white-box key derivation function (WDKF) that uses a hardware functionnality and dene precise security properties to achieve. Their construction is based on pseudo-random function and iO, with an hardware that computes PRF functionalities. Roughly, iO helps to hide the key in the implementation and security is proven through the well-known puncturable function techniques of [START_REF] Sahai | How to use indistinguishability obfuscation: deniable encryption, and more[END_REF].

If their construction provides interesting proven security properties in the hardware model, the use of iO in their construction reduces the hopes of having a concrete implementation of their solution. Using watered down versions of iO would indeed void the security of the construction.

With Token Based Obfuscation The construction of Agrawal et al. [START_REF] Agrawal | White-box cryptography with device binding from token-based obfuscation and more[END_REF] uses Token Based obfuscation (TBO). Token Based Obfuscation is a form of obfuscation that allow to run the obfuscated program on an input only if a token related to said input is generated. In that sense, TBO produces reusable garbled circuits [START_REF] Goldwasser | Reusable garbled circuits and succinct functional encryption[END_REF]. A TBO obfuscator is then divided into two algorithms, the compiler O and the token generator T oken : Like obfuscators such as iO, on the input of a circuit C the obfuscator O output a circuit O(C) but also outputs a secret key k

The T oken generator outputs a token on the input of the secret key k and x an input of C such that:

(T x = T oken(k, x)) =⇒ (O(C)(T x ) = C(x))
Their construction essentially adapts this kind of obfuscator in the white-box model by storing the token generator in the hardware, while the obfuscated circuit is freely executed on software on the input of a token given by the hardware.

If the theoretical security of this construction is well-grounded in obfuscation works, the authors however do not elaborate on the concrete complexity of their construction, which is usual for applicable white-box designs. The construction of [START_REF] Goldwasser | Reusable garbled circuits and succinct functional encryption[END_REF]-that is a ground work for this construction -use universal circuits as a basis of their construction, which begs the question of eciency if it is used with multiple garbled circuits, especially if we consider similar constructions already exist since a decade in the obfuscation literature (see next section).

Construction from Hardware-Based Obfucation

The idea of using hardware as a crutch to achieve notions that we do not know how to achieve in the standard model is not new. Here, we study the example of obfuscators build with hardware functionalities. As we have seen in section 2.3.3, using obfuscation to achieve white-box properties is a natural idea. The example we give here can be concretely implemented and are very exible in their usage. As many construction of cryptographic obfuscators, the programs here are represented by circuits.

It is interesting to note that these kinds of constructions are not mentioned in the state of the art of hardware module white-box papers. We nd this rather surprising considering the similarities between the goal they achieve, and the techniques they use.

The TCC2010 Construction In the context of building an obfuscator, a line of work attempted to circumvent the impossibility result of Barak et al. by using hardware -tamper-proof hardware in the obfuscation literature. The work of [START_REF] Goyal | Founding cryptography on tamper-proof hardware tokens[END_REF] is the rst to achieve it with stateless hardware, that is, hardware that does not have to kept track of each computation made chronologically.

To build the obfuscator, the authors rst consider a universal circuit, that is, a circuit U such that for any circuit C of reasonable size, and x its input, we have :

U (C, x) = C(x)
Using such circuit allows to reduce the problem of obfuscating the circuit to hiding its input through computations made by the universal circuit. Then, each circuit bit is encrypted with a non-malleable encryption scheme E with secret key k.

The software part of the obfuscator is then composed of the encrypted circuit and the universal circuit and the hardware contains the secret key k and the encyption and decryption algorithms E and E -1 . To evaluate the circuit C on input x, one rst needs to encrypt each bit of x using the hardware. Then, for each gate of U , the user computes the ouput bit in the following way : the user sends the two encrypted bits to the hardware that decrypts them, computes the gate and encrypts the output, to send it back to the user.

This simplistic description however have some problems. For instance, a malicious user can change values on wires by using the encryption algorithm of the hardwareas the order and values of inputs are not xed. To circumvent these kinds of problems with stateless hardware the authors force the execution of the program to be made in the correct order, for correct inputs. To do so, the author achieve to assign to each computation what they call an 'execution identity' for the entirety of the execution of the program. This execution identity ensures that there is only a low probability that dierent executions of the circuit have the same execution identity. For an even simpler construction, the authors propose a stateful construction for which the hardware insert a nonce in all encrypted values. The hardware will then only compute a gate if the wire have the right nonce. For a complete description, refer to [START_REF] Goyal | Founding cryptography on tamper-proof hardware tokens[END_REF].

This construction is rather simple in essence as it only uses a hardware with encryption and decryption functionality -and a small check on execution identities. However, there are as many calls to the hardware than there are gates in the universal circuit, which is problematic if a user wants to use a large class of circuits C as input.

The FHE based Construction of Dötling et al. The construction of [START_REF] Döttling | Basing obfuscation on simple tamper-proof hardware assumptions[END_REF] is based on fully homomorphic encryption and the use of a hardware for decryption.

Similarly to the previous construction, the obfuscator uses a universal circuit to consider the circuit C as an input. The main dierence here is that each bit of the circuit is encrypted using the public key of a FHE scheme. The obfuscation software contains a description of U and the encryption of C, while the hardware part is composed of the decryption algorithm of the FHE scheme with the secret key.

The circuit can then be evaluated on input x by encrypting each bit of x and evaluating homomorphically U (C, x). The result then has to be decrypted by the hardware with the secret key. However, this leads to malleability problems similar to the previous construction. Here, to decrypt conditionality to a correct execution, user has to commit to a circuit C by signing its encryption and sending it to the hardware. This idea is similar to the rst GGH13 obfuscator. In their construction, the functionality of the hardware is obfuscated and allow a bootstrapping from low classes of circuits (N C 1 ) to any polynomial circuit. If the GGH13 construction had implementation issues due to the size the obfuscator on N C 1 circuits, this construction only relies on the security of the hardware and FHE. Using FHE might be more technical than a regular encryption scheme, this construction only makes one call the the hardware for the decryption of the output of the circuit. The circuit of decryption can also be small as there exists FHE schemes with decryption in N C 1 .

A Lack of Metrics, Again

The Hardware Module White-Box model has been motivated by concrete use cases found in the industry. However, there is still a huge gap between the literature and the concrete use of white-box cryptography in this context.

A rst problem is the lack of a good target problem. What are the most useful hardware to consider as a basis ? What are the main goals of implementations depending on the device ? If the problem of payment application has been studied in theory by Alpirez-Bock et al. [START_REF] Bock | Security reductions for white-box key-storage in mobile payments[END_REF], there are no concerns for the concrete use of such methods. The TBO based method of [START_REF] Agrawal | White-box cryptography with device binding from token-based obfuscation and more[END_REF]

Chapter 4 Generic Attacks in the White-Box Model

In the previous chapters, we investigated dierent white-box security models. In these models, there is one constant: the attacker is a allowed to have full access to a certain amount of the software computing the target cryptographic primitive. The goal of this chapter is to describe the automated attacks that are available to every white-box attacker and that are generic, i.e can be applied to any implementation without any real understanding of the implementation.

From Grey to White As the white-box model is a generalization of the grey-box model of attack, it is natural to consider grey-box attacks and their eciency against white-box implementations. The two main attack techniques that have been used in the literature are Dierential Power Analysis (DPA) [START_REF] Kocher | Dierential power analysis[END_REF] and Dierential Fault Analysis (DFA) [START_REF] Dusart | Dierential fault analysis on A[END_REF].

If the use of these attacks has not been immediate, their use in the white-box model was quickly shown to be powerful. Adaptations of DPA and DFA in the whitebox model have broken most of the state-of the-art solutions [START_REF] Bock | White-box cryptography: Don't forget about grey-box attacks[END_REF][START_REF] Bos | Dierential computation analysis: Hiding your white-box designs is not enough[END_REF][START_REF] Jacob | Attacking an obfuscated cipher by injecting faults[END_REF][START_REF] Sanfelix | Unboxing the white-box: Practical attacks against obfuscated ciphers[END_REF] and greatly questioned the eectiveness of the state-of-the-art implementation techniques.

The grey-box attacker is a real threat in the white-box model as it does not rely on a deep understanding of the implementation or an expert reverse engineering.

While being a weaker opponent than the white-box attacker, the grey-box adversary is a rst opponent to beat for a designer and resisting its attacks should be a prime goal for the designer.

Original White-Box Attacks The white-box attacker can observe exact computational traces which means that attack techniques that do not have an equivalent in the grey-box context can be envisioned. The eciency of these attacks often surpasses the eciency of grey-box attacks in the adapted situation.

The Linear Decoding Attack (LDA) is one of the prime examples of such attacks. This attack exploit the fact that, due to the techniques used in white-box implementation, there exists linear or low-degree relations between elements of computations traces and the target function. Finding the key can then be reduced to simply solving a linear system. This attack as rst been reported to break implementations of the WhiBox19 [START_REF]Ches 2019 ctf challenge whibox contest[END_REF] contest [START_REF] Goubin | How to reveal the secrets of an obscure white-box implementation[END_REF] and is particularly adapted to implementations using masking techniques.

One other notable category of attack is the collision-based attacks. Reported in papers like [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] and [START_REF] Zeyad | Another look on bucketing attack to defeat white-box implementations[END_REF], these attacks abuse the fact that collisions in computation traces are usually equivalent to collisions on target functions. The attack of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] exploit collisions that are inherent to the round funtion of the AES while [START_REF] Zeyad | Another look on bucketing attack to defeat white-box implementations[END_REF] exploits collisions that are present in traditional AES implementations.

4.1

Formalizing the framework of automated attacks The automated attacks we described previously all share the same framework that we describe now. Let us assume that an attacker targets a boolean function ϕ k with k ∈ K. The attack is divided into tree steps.

First, the attacker collects computation traces of the execution of the program.

For any number N of inputs (x (i) ) i∈{1,...,N } , the attacker collects any value read or computed by the implementation. This can take the form of values written in any memory location or the values of look-up tables. The values of the traces are acquired and ordered chronologically from the rst to the last T -th value. As the trace depend on the input, we note the trace (v i ) i∈{1,...,N } where :

(v i ) = (v i 1 , ..., v i T )
The traces can be obtained straight from the attacked implementation or some reverse engineering can be performed to reduce the size of traces. The traces can also be analyzed to remove constant or redundant elements.

After the acquisition of traces, the attacker tries to build a distinguisher D from the traces. The distinguisher gives a score for each possible key :

(γ k ) k∈K = D((x (1) , ..., x (N ) ), (v (1) , ..., v (N ) ))

Lastly, the attacker chooses a candidate among the ones with the best score γ k .

The attacker succeeds if the distinguisher correctly matches the best score with the correct key. The probability p is then dened by :

p = P r(k * = argmax k∈K γ k )
If the distinguisher matches not one but few keys to the best score, the attack can still succeed if the obtained key-space is small enough so that a brute-force search can eliminate the false positives.

DCA

The To launch a DCA, the attacker rst collects traces of executions of the program.

She then chooses a target keyed function and makes a key guess. Then the correlation between the evaluations of the target function and the corresponding traces is computed for each key guess. The key with highest correlation score is chosen as the key candidate, which is then conrmed or denied with a reference implementation.

Since its seminal use, this attack has proven to break most AES implementations, in works such as [START_REF] Bos | Dierential computation analysis: Hiding your white-box designs is not enough[END_REF][START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF]. The most important quality of DCA is that it only requires a partial knowledge of the implementation and can be launched generically and eciently.

The attacker does not need to reverse engineer the implementation, isolate components or modify the code, she only needs to read the values at execution. By its simplicity and eectiveness, the DCA is a very potent tool for the white-box attacker, and providing proven countermeasures against it is still a major open problem in the plain white-box model.

Although it was quickly proven to be eective against the state-of-the-art implementations of AES, the reasons of why it was so ecient were not well understood.

Further works with ner analysis lead to a better understanding such as [START_REF] Bock | On the ineectiveness of internal encodings -revisiting the DCA attack on white-box cryptography[END_REF][START_REF] Bock | White-box cryptography: Don't forget about grey-box attacks[END_REF]. For this thesis, we follow the precise analysis of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] that estimates the probability of success of the attack when the target is 'encoded' . While this might seems like a restriction, all the known techniques of open design implementations are using encoding techniques.

As a consequence, their work helps to understand the eectiveness of DCA against all known open design candidates.

Establishing Probability of Success

The DCA attack is very generic but can only be used with certain assumptions. Let us assume that the program P computes the function f . Two requirement to the success of DCA is that the input of P can be chosen and that the program P , on the input of x output f (x) were x is the chosen input. The requirement ensures that the program does not hide the input-output behavior of the program through external use like external encodings (extensive description of the encoding strategy of the AES on part II).

For the rest of this analysis, we follow [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF]. While their analysis is not generic, the work of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] gives us a good understanding of the eciency of DCA against internal encoding implementations. Initiated by Chow et

Cor(f, g) = 1 2 n x∈F n 2 (-1) f (x)+g(x)
Denition 15 (Correlation Distinguisher). Let v = (v 1 , ..., v T ) be a computation trace for an input x. For 1 ≤ j ≤ T , let V j be the random variable that returns v j on input x. For any key guess k * , we dene the DCA distinguisher by :

γ k * = max 1≤j≤T |Cor((ϕ k * ) i , V j )|
If for coordinates j where V j = fj we naturally have:

max 1≤j≤m |Cor((ϕ k * ) i , V j )| = max 1≤j≤m |Cor((ϕ k * ) i , (ϕ k ) j )|
Proposition 3 (Adaptation from RW19). Let k * be the correct key guess and k × a wrong one. The probability of success of DCA is :

p = P r[ max 1≤j≤m |Cor((ϕ k * ) i , (ϕ k ) j )| > max 1≤j≤m |Cor((ϕ k × ) i , (ϕ k ) i )|]
The probability p only depends on the encoding ϵ. If n ≥ 2m + 2 the probability p can be estimated by :

p ≈ 1 - 2 m-1 2 m-2 2m 2 m-1 2 m m
The result of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] is more complete shows how to evaluate the probability of success for other parameters regimes. The regime of parameter n ≥ 2m + 2 is however very commonly found in the state if the art of AES implementation. For instance, the seminal implementation of Chow et al. uses 4-bit encodings for 8-bit S-boxes, which brings the probability of success of the attack at more than 0.92. However, when m is equal to n, the probability quickly approaches 0.

The DCA attack can be extended to 'high-order' DCA by using correlation between linear combinations or products of elements of the traces instead of individual elements.

We refer to [START_REF] Wang | De la théorie à la pratique de la cryptographie en boite blanche)[END_REF] for more details.

Complexity Once the traces have been acquired, a DCA is made by computing the correlation scores of all the traces for each potential target. The authors of RW19 then evaluate the complexity of DCA at :

O(T × N × 2 k )
where T is the size of each trace, and N the number of traces. In the case of n ≥ 2n + 2, the number of traces is estimated by [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] to be N = O(2 2m ).

Countermeasures

As protecting implementations with open designs against DCA is still an open problem, providing countermeasures against DCA is not entirely solved. There are however many techniques, mostly inspired by the grey-box state of the art that can be proposed to diminish its eciency.

Linear Masking The rst idea is to adapt linear masking techniques in the whitebox context. Introduced to protect hardware implementations against DPA [START_REF] Chari | Towards sound approaches to counteract power-analysis attacks[END_REF][START_REF] Goubin | DES and dierential power analysis (the "duplication" method)[END_REF], the goal of this technique is to share secret variables into n parts:

x = x 1 + ... + x n
where the x i are random. The computations are made on the share instead of the variable x and recombined at the end for correctness. In essence, if only n -1 shares are known, no information is leaked about x. However, this technique assume that a generator of fresh randomness can be accessed by the implementation. Otherwise the bias in the distribution of shares is detrimental to the implementation -see [START_REF] Mangard | Power analysis attacks -revealing the secrets of smart cards[END_REF] for context in the grey-box model. As it is impossible to reveal the design of a PRNG in the plain white-box model and expect the pseudorandomness of its output, this forces designers using masking to obfuscate random number generators of unknown design into their implementations. In practice, implementations using these techniques have be defeated, as shown by the WhiBox contest.

Dierent Encoding Techniques In the context of encoding techniques, the eciency of DCA heavily depends on the size of the encoding. One can then hope to use bigger encodings to thwart the attack. This rationale has been used in implementations such as [START_REF] Lee | A masked white-box cryptographic implementation for protecting against dierential computation analysis[END_REF], with only partial success. The main problem comes from the existence of function with large input size that force large encodings to be used in the implementation. With such large encodings, the size of the implementation quickly explodes, making it a debatable countermeasure. This explosion is however somewhat inherent to the SPN structure of the AES and the implementation techniques used.

More on this topic in part 2 chapter 2.

Remark: Shuing Methods and Dummy Computations are methods used in hidden design implementations to limit the eectiveness of DCA. The goal of these methods is to disrupt the ow of execution of the program by shuing the computation in memory and time and introducing random computation to augment the overall noise of the implementation. We do not detail them as we want to focus on open design countermeasures. For the curious reader, we refer to [START_REF] Wang | De la théorie à la pratique de la cryptographie en boite blanche)[END_REF] for a detailed study.

Collision Attack

Introduced by [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF], the collision attacks is a variant of the DCA where the distinguisher is based on collisions happening on round function instead of a classic correlation score.

The main idea is the following : collisions on an encoded function ϵ • ϕ k are equivalent to collisions on ϕ k . This remarks stands for most of the implementations in the state of the art. For this section we assume that the target function ϕ k is from n bits to m bits and that n > m.

The attack is launched as follows:

For each key guess, group inputs if they collide after ϕ k * :

I v,k * = {x|ϕ k * (x) = v}
Dene the correlation function -that is equal to 1 if the target function collides on x and x ′ , 0 otherwise :

Φ k (x, x ′ ) = N OT (ϕ k * (x) × ϕ k * (x ′ ))
For any two inputs x, x ′ in I v,k * , compute correlation traces :

w x,x ′ i = N OT (v x i × v x ′ i ) If W (x,x ′ ) j
is the function that outputs the j-th element of the correlation trace w x,x ′ i the score for a key guess k * is dened by:

γ k * = max 1≤j≤T |Cor(Φ k * i , W j (x,x ′ ) )|
Remark : The Mutual Information Attack is a variant of collision attacks where the distinguisher is based on mutual information. As the authors of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] note, it can be seen as a regular MIA in the grey-box model where the encodings can be seen as complex leakages. The complexity of MIA attacks in the white-box model is similar to the collision one. As they share many similarities, we do not detail it here. We refer to [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] for any precision.

Probability of Success of the Attack

Similarly to the DCA, the analysis of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] estimates the probability of success of the attack for random boolean function encoded by n-to-m bits bijections.

Proposition 2. Let N be the number of acquired traces. If for all key guesses, the functions ϕ k are mutually independent and balanced the probability of the collision attack is lower-bounded by :

p ≥ 1 -#K × exp(- (N -1)(N -2) 2 m+1 )
Complexity To perform this attack, one only needs to compare collisions observed on ϕ k ⋆ and the observed encoded value ϵ • ϕ k . In their paper, the authors of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] note that when used on state-of-the-art implementations, the trace complexity of collision attacks is way smaller than the one of regular DCA. They theoretically estimate the complexity of the attack to be:

O(T × N 2 × 2 k )

Countermeasures

Countermeasures to collison attacks have not been discussed in the literature. A remark that is inherent to the attack is that it assumes the use of non-injections un the implementation. This is however very common against SPN due to their structure.

A simple idea to thwart collision attacks is to transforms the implementation so that it contains bijective transformation. In the case of encoding techniques for instance, this could lead to the absence of observations of collisions and any attempt at collision attacks would fail.

LDA

The Linear Decoding Attack (LDA) exploit the fact that, due to the techniques used in white-box implementation, there often exists linear or low-degree relations between elements of computations traces and the target function. Finding the key can then be reduced to simply solving a linear system. This attack has rst been reported to break implementations of the WhiBox19 contest [START_REF] Goubin | Defeating state-of-the-art white-box countermeasures with advanced gray-box attacks[END_REF] and is particularly adapted to implementations using linear masking techniques.

Rationale of the Attack

The rst goal of LDA is to tackle linear masking of sensible variable and to propose a more eective attack than DCA in this context. If a sensible variable ϕ k is masked in an implementation, there exists a linear relation between some of the values of the computation traces and the target ϕ k . For the rest of the section, we assume that there exists a linear relation between elements of computation traces such that:

ϕ k (x) = λ 0 + t i=1 λ i v i
An attacker with many execution traces on input x i can then build a matrix on computation traces and try to solve the following system for a key guess k * :

     1 v (1) 1 ... v (1) T 1 v (2) 1 ... v (2) T . . . . . . . . . . . . 1 v (N ) 1 ... v (N ) T      ×      λ 0 λ 1 . . . λ N      =      ϕ k * (x 0 ) ϕ k * (x 1 ) . . . ϕ k * (x N )     
Hopefully, the system only solves for the right key guess k * = k or a small subspace of the key-space and the correct key can be recovered.

While this attack works against linear masks or encodings, it can also be applied to higher degree masks or to certain forms of encodings. Indeed, if there exists a polynomial relation of degree d between values of a trace and the target function, one can relinearize the problem by considering a linear system depending on the monomials of the values of the traces. For a trace of execution (v (i) j ) j∈ 1,T on input (x (i) ), we compute the list of monomials for any order M on d ((v (i) )) of degree d, where d is the supposed degree of the masking/encoding. Then the linear system:

(M on d ((v (i) ))) i∈ 1,σ(T,d) × λ = (ϕ k (x (i) ) i∈ 1,σ(T,d) admits a solution Λ ∈ F σ(T,d) 2
if a relation exists for the guessed value k * . To formalize a distinguisher according to the attack framework of 4.1, the score γ k * is equal to 1 if the vector (ϕ k * (x (i) ) i∈ 1,σ(T,d) is in the image of the matrix we build for the attack, 0 otherwise. We note d-LDA a LDA of order d.

Complexity and Probability of success

We follow the analysis of [START_REF] Goubin | How to reveal the secrets of an obscure white-box implementation[END_REF] for the estimation of the probability of success of the attack.

This estimation is made under 3 assumptions :

There exist a linear relation between elements of the trace and the target function ϕ k .

The plaintext x input of the traces is uniformly distributed.

The traces are uniformly distributed among the t-uples that verify:

ϕ k (x) = λ 0 + t i=1 λ i v i
While the rst hypothesis is necessary for LDA to be of any use and the second is natural as it is usual in the white-box context, the third hypothesis is an ideal assumption to help the formal analysis. This assumption can be challenged to include dependency between variables, but it would harden any estimation of the success probability. The proof of this property can be found in [START_REF] Goubin | How to reveal the secrets of an obscure white-box implementation[END_REF] Proposition 4. Let T ≥ N and v (j) i 1 ≤ i ≤ T ,1 ≤ j ≤ N satisfying the 3 above assumptions. The probability that the system is solvable for an incorrect key guess k × ̸ = k * is lower than q N -T -1 where q is dened by :

q := max({P r(Φ k × (X) = L(Φ k * (X)))|L : F n 2 → F n 2 , L linear, (k * , k × ) ∈ K 2 })
with uniform X.

As a consequence, the probability to have false positives that are not linearly dependent to the target is exponential in q. It means that for enough traces, there will be one only positive with overwhelming probability. For instance, if we set the target ϕ to be a bit of the S-box of the AES, q = 9 16 which makes the probability of failure already small with very few traces.

Complexity If we assume ϕ, N and T are such that there is a unique key with overwhelming probability, the complexity of the attack is dominated by checking if the vector (ϕ k (x (i) ) i∈ 1,σ(T,d) is in the image of the matrix (M on d ((v (i) ))) i∈ 1,σ(T,d) . To do so, one can use the LU decomposition of the matrix which can be computed in O(n ω ). This means that the attack can be made in:

O(σ(T, d) ω × 2 k )
This makes LDA a very ecient attack against linear masks or encodings even if the design is not known. When the attacker has a better idea of the attack window, it is as ecient against higher order countermeasures.

Countermeasures

As the LDA is essentially DCA with an algebraic distinguisher, the countermeasures are similar to those of DCA, with a focus on the algebraic degree of the function involved.

Techniques to increase traces are still ecient to a certain degree.

While the state of the art has not been bubbling with papers on the topic, one can note the non-linear masking of [START_REF] Biryukov | Attacks and countermeasures for white-box designs[END_REF] and its extension by [START_REF] Seker | A white-box masking scheme resisting computational and algebraic attacks[END_REF]. Implementations uisng this countermeasure force attackers to perform higher degree LDA which pushes the complexity of attacks on unknown designs to their limits against obfuscated implementations. However, these techniques still need PRNGs to provide any security.

There is undoubtedly more exploration to be done against LDA. For instance, one could try to minimize the probability q for all degrees up to a certain threshold. While this would be the case for high degree masking techniques, we believe that this strategy could be used for encoding based implementations such as it is common for open-design implementations. More on this topic will be seen in part II.

BCA

The Bucket Computational Attack is a variation of the Statistical Bucket Attack that was introduced by Chow et al. to break their rst white-box DES implementation.

Revisited by Zeyad et al. [START_REF] Zeyad | Another look on bucketing attack to defeat white-box implementations[END_REF] to be adapted to the AES, this attack is based on the existence of collisions in existing AES implementations. In that sense, it is similar to the collision attacks of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF]. However, it targets non-injection that are caused by the implementation, not due to the structural collision of the underlying algorithm. This attack has only been described for DES and AES implementations, so we attempt here to abstract it in our usual framework.

The seminal setting for this attack is the special encodings of Chow et al. implementation. In that setting, the keyed S-box of the AES is encoded by a 4-to-4 bit bijection, building a 8-to-4 bit non-injection. As the encoding is a bijection on 4 bits, having collision on the four leftmost bit of the S-box will be equivalent to have collision on the encoding.

In the framework of this chapter, we assume that the target function is of the form ϕ k (x) = ϕ(x + k) for a bijection ϕ. Then, the m leftmost bits of target function

ϕ k : F n 2 → F n 2 are encoded by a bijection ϵ : F m 2 → F m 2 so that the encoding ϵ•ϕ k [1 : m]
can be observed in the implementation. To build a distinguisher, we now build a distinguisher in the following way:

Compute, from the computation traces, the values ϵ

• ϕ k [1 : m](x) for each x ∈ F n 2
Choose two m-bit values v 0 and v 1

Form two sets for each key guess k * I 0,k * and I 1,k * , such that:

I b,k * := {x|ϕ[1 : m](x + k * ) = v b }
Then, dene for each key guess the subsets of traces -computed from the implementation:

V b,k * := {ϵ • ϕ k [1 : m](x)|x ∈ I b,k * }
For each key guess k * compute the score:

γ k * = #{i|V 0,k * [i] ̸ = V 1,k * [i]}
The correct key guess is attributed to the biggest score as usual.

Estimating the Success of the Attack

This attack has been successfully used to break the usual white-box implementations of the AES such as the CHES 2016 challenge or Lee et al. CASE 1 algorithm. The author explain that their attack achieves lower traces size compared to DCA is most cases and similar time for complete key recovery. However, no extrapolation to other settings has been given by the author. An extension to the second order has been

given in [START_REF] Maghrebi | Revisiting higher-order computational attacks against white-box implementations[END_REF] with similar experimental arguments.

Complexity As the attack needs to compare the collisions of the target function and the elements of the trace on each input, for each key guess, the complexity is similar to a DCA:

O(T × N × #K)
However, the experimental analysis of [START_REF] Zeyad | Another look on bucketing attack to defeat white-box implementations[END_REF] on candidate white-box implementations with nibble encodings shows that the size T of traces is overall smaller than DCA for complete key-recovery.

Countermeasures

Similarly to Collision Attacks, BCA can be thwarted if non-injections are dicult to analyse in the program. One can for instance use bigger encodings to force the attacker to look for collisions in other potential target functions, with an hopefully bigger keyspace.

DFA

The Dierential Fault Analysis (DFA) is an active attack that was originally applied in the grey-box context. The goal of the attack is to disrupt sub-computations of a key-dependent cryptographic algorithm to collect faulted executions that can help to recover the secret key. This attack was pioneered by Boneh et al. in 1996 for publickey cryptosystems [START_REF] Boneh | On the importance of checking cryptographic protocols for faults (extended abstract)[END_REF] and then extended to DES by Biham and Shamir [START_REF] Biham | Dierential fault analysis of secret key cryptosystems[END_REF], and to AES by Dusart et al. [START_REF] Dusart | Dierential fault analysis on A[END_REF] The diculty of using fault attacks in the grey-box model of attack is to precisely fault the device to recover useful information. If the hardness of this practical aspect has been considerably diminished, exactly faulting an implementation is trivial in the white-box context. As it was shown by Sanfelix et al. [START_REF] Sanfelix | Unboxing the white-box: Practical attacks against obfuscated ciphers[END_REF], DFA is a potent method to break white-box implementations.

While the method is well-known to be an important toolbox of the white-box attacker, there are to very few analyses of the eciency of the attack against various targets and fault models. This fact can partly be attributed to the fact the automated attacks are the main focus of the literature for they are agnostic to the implementation.

Implementations are often obfuscated through obscurity and fault attacks often need reverse engineering to be applied.

In by Rijmen and Daemen [START_REF] Daemen | Rijndael for AES[END_REF], was chosen among the candidates to be the winner of the contest and is now called AES.

The AES algorithm is a block-cipher with a 128 bit block size, and with three possible key sizes -128, 192 or 256 -for dierent security levels. By design, it is a Substitution Permutation Network (SPN) that is composed of 10, 12 or 14 rounds for the respective key sizes 128, 192 or 256. We focus here on the 128 bit version, as it is the most commonly found in the state-of-the-art implementations.

In the AES specication, the operations are described at the byte level. Bytes are represented as elements of F 2 8 with the xed representation F 2 8 = F 2 [X]/(X 8 + X 4 + X 3 + X + 1). Elements in the eld are represented by two words in hexadecimal such that, for any element b 0 +b

1 X +b 2 X 2 +b 3 X 3 +b 4 X 4 +b 5 X 5 +b 6 X 6 +b 7 X 7 is mapped to 0x(b 0 b 1 b 2 b 3 ) 2 (b 4 b 5 b 6 b 7 ) 2 .
In the AES specication, the prex "0x" is removed when it is obvious due to the context.

The AES algorithm is composed of 10 rounds. These rounds are described on a 4 by 4 state of bytes s = (s i,j ) i,j∈ 1,4 . From the master key K of 128 bits, eleven round key K t of 128 bits each are derived by the key schedule of the algorithm, stored in a 4 by 4 array (K t i,j ) i,j∈ 1,4 ). One round of AES is the composition of four algorithms: AddRoundKey, SubBytes, ShiftRows and MixColumns. We now describe these algorithms.

On the input of t ∈ 0, 10 and a state s, AddRoundKey that XORs the i-th round key to the state:

AddRoundKey(s, t) i,j = s i,j ⊕ K t i,j
On the input of a state s, the algorithm SubBytes applies the sbox SB to each byte of the state:

SubBytes(s) i,j = SB(s i,j )
where SB is the composition of the multiplicative inverse on F 2 8 , extended to 0 by 0 and the ane map dened by:

            b 0 b 1 b 2 b 3 b 4 b 5 b 6 b 7             →             1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1             ×             b 0 b 1 b 2 b 3 b 4 b 5 b 6 b 7             +             1 1 0 0 0 1 1 0            
On the input of a state s, ShiftRows permutes bytes of the state:

ShiftRows(s) i,j = s i,(j+i) mod 4

On the input of a state s, MixColumn performs a linear transformation on each 'column' of the state:

MixColumn(s 1,j , s 2,j , s 3,j , s

R t j (x 1 , x 2 , x 3 , x 4 ) := M C 1 × SB(x 1 + K t-1 1,j ) + M C 2 × SB(x 2 + K t-1 2,j ) +M C 3 × SB(x 3 + K t-1 3,j ) + M C 4 × SB(x 4 + K t-1 4,j )
The output state of a round is the collections of R t i,j (x 1 , x 2 , x 3 , x 4 ), where R t i,j is the i-th byte of the function R t j .

For t = 10

R 10 i,j (x) = SB(x + K 9 i,j ) + K 10 i,j
Remark: We do not describe the key-schedule as it is not useful to the understanding of the rest of this chapter. For sake of completeness, it can be found in [START_REF] Daemen | Rijndael for AES[END_REF] The Standard Implementation The AES submission document [START_REF] Daemen | Rijndael for AES[END_REF] contains a reference implementation. As it is the starting point for many implementation techniques including the seminal Chow et al. technique, we include it for reference. The goal of this implementation is to be optimized on 32-bit processors. To do so, the authors reduce the implementation to 8-to-32-bit look up tables and XORs between the output of these tables.

To build the implementation, the authors use the commutation between some of the operations of the round function. First, ShiftRows and AddroundKey commute as they are linear on bytes, hence:

Shif tRows(AddRoundKey(S, K t )) = AddRoundKey(Shif tRows(s), Shif tRows(K t ))

Then, the MixColumn transformation can be reduced to the sum of 8-to-32-bit transformations by the following equation:

MixColumn(s 1,j , s 2,j , s 3,j , s 4,j ) =     02 01 01 03     ×s 1,j +     03 02 01 01     ×s 2,j +     01 03 02 01     ×s 3,j +     01 01 03 02     ×s 4,j
If we note:

SB ′ 1 (x) =     02 01 01 03     ×x , SB ′ 2 (x) =     03 02 01 01     ×x , SB ′ 3 (x) =     01 03 02 01     ×x , SB ′ 4 (x) =     01 01 03 02     ×x
The (i, j)-th block of 8 bits of the round function is then the XOR of the key and the functions SB' on permuted inputs :

SB ′ 1 (s 0,jmod4 ) + SB ′ 2 (s 2,j+1mod4 ) + SB ′ 3 (s 3,j+2mod4 ) + SB ′ 4 (s 4,j+3mod4 ) + K t i,j
The authors conclude that the AES round function can then be made made with 4 look-up tables SB' and 4 XORs per column and per round. This implementation weights approximately 4kB and can use a lot of parallelism, for fast performances.

While it does not provide any security in the grey or white-box models, it is often used as a comparison point for performances uses.

State-of-the-Art of the

The Seminal Chow et al. Construction

The 2002 paper of Chow et al. [START_REF] Chow | A white-box DES implementation for DRM applications[END_REF] introduces the concept of white-box cryptography and proposes an implementation of the AES that is designed to stand against key-extraction in the white-box model. While their implementation has been broken by structural and automated attacks, their work laid foundation for several other constructions using the same rationale of design.

The rst design techniques used in their implementation is to use the 'internal encoding' technique so that the key does not leak from sub computations of a round function. Roughly, one can represent the AES algorithm by the composition of N 'small' algorithms (E i ) i∈ 1,N and to be conjugated by bijections that are cancelled from one small algorithms to the other.

Denition 17. We say that an implementation of an algorithm A = ⃝ N i=1 E i is using the 'internal encoding' rationale if it has been decomposed in the form:

A = ⃝ N i=1 E ′ i where E ′ 1 = g 1 • E 1 , E ′ i = g i • E i • g -1 i-1 , E ′ N = E N • g -1 N -1
and g i are bijections. For E ′ i , g i is called the input encoding and g -1

i-1 the output encoding.

In their paper, Chow et al. also propose to use external encodings, that is, to

transform E ′ 1 into E ′ 1 • f in and E ′ N into f out • E ′
N to encode inputs and outputs as well. However, these transformations have to be hidden in the implementation as well. It is hence not a good design method in the plain white-box model. However, since it is the rst design ever proposed, we include it with external encodings in the state-of-the-art Denition 18. We say that an implementation of an algorithm A = ⃝ N i=1 E i is using the 'external encoding' rationale if it has been decomposed in the form:

A ′ = ⃝ N i=1 E ′ i where E ′ 1 = E 1 • g in , E ′ i = E i , E ′ N = g out • E 0 and
g in and g out are bijections. The description of g -1 in and g -1 out are necessary to correctly compute A.

E 1 τ 1 σ 2 = τ -1 1 E 2 τ 2 σ N = τ -1 N -1 E N Figure 1.1: Internal Encodings IN IN -1 E 1 E 2 E N OUT -1 OUT Figure 1.2: External Encodings
For this rationale to work, the transformations E ′ i need to hide the bijections g i . Indeed, if g i can be recovered, an attacker can then trivially recover E i to break the implementation. To circumvent this problem, the authors break the round function of the AES into small key-related transformation that can be encoded and represented by their look up tables. The main idea is that not leaking intermediate values can help to make the look up tables look random to an attacker, which is of course related to the unbreakability security notion we presented in part I. Denition 19. We say that an implementation is a look-up table network if it can be written by composition of 'small' look-up tables that are accessed to in a specic order. This rationale of design has given birth to variations that we will discuss later in this section.

Chow et al. AES implementation

In the formalism of part 1, Chow et al. propose a white-box compiler for AES, that is, their propose an algorithm that, on the input of a key, outputs a white-box implementation, with randomness drawn at random during the compilation when needed.

Decomposing the AES round function T-boxes and MixColumn

Similarly to the reference implementation, the method of Chow et al. starts by dening look up tables that allow to compute the round function, that is, the composition of AddRoundKey and SubBytes :

T t i,j (x) = SB(x + K t-1 i,j ) T 10 i,j (x) = SB(x + K 9 i,j ) + K 10 i,j
They then compose these function with MixColumn for rounds 1 to 9, like in the reference implementation to obtain:

T M C t 1,j (x) =     02 01 01 03     × T t 1,j , T M C t 2,j (x) =     03 02 01 01     × T t 2,j , T M C t 3,j (x) =     01 03 02 01     × T t 3,j , T M C t 4,j (x) =     01 01 03 02     × T t 4,j
The idea is to represent the key dependent computations succinctly by [START_REF] Biryukov | Attacks and countermeasures for white-box designs[END_REF] Encoding Phase The compiler can now randomize the XOR tables and the maps T M C t i,j following the internal and external encoding rationals. We now describe the look up tables that compose the implementation after encoding :

IN i,j encodes the 8-to-128 bits mapping composed of the inverse of the external g -1 in input encoding and a linear bijection. The input encoding of the lookup table is a 8-bit non-linear bijection and the output encoding is a concatenation of 32 4-bit encodings.

T M C t i,j encodes the tables T M C t i,j . The input encoding is a concatenation of two 4-to-4-bit random bijections composed by a linear 8-to-8-bit bijection. The output encoding is in the inverse sense, that is a linear 32-to-32-bit bijection followed by the concatenation of 8 4-to-4-bit bijections.

T 10 i,j encodes the last round map x → SB(x + K 9 i,j ) + K 10 i,j . The input encoding are of the same form as the other T-box input encodings with the addition of the output encoding g out that is composed of 32 4-bit bijections.

Txor encodes the XOR of two 4 bits words. As the input encodings have to be compatible with the the other tables, they are of the same form, that is, concatenation of 4-bit bijections.

T lin t i,j encodes the composition of the round function and a linear map. The encodings are consistent with tables T M C r i,j by removing the previous output encoding and applying the inverse input encoding.

Cryptanalysis

The early cryptanalysis of Chow et al. implementation was made dicult by the use of external encodings. Indeed, the astute reader would have noticed that all the attacks of part 1 chapter 4 break this implementation without external encodings. We detail the BGE attack, the rst attack to break Chow et al. implementation with external encodings. Historically, the collision attack of Lepoint and Rivain [START_REF] Lepoint | Another nail in the con of white-box AES implementations[END_REF] was also used to great success. As it is similar to collisions and bucket attacks, detailed in Part 1, due to the aw it uses, we do not describe it here.

The BGE Attack

The BGE attack [START_REF] Billet | Cryptanalysis of a white box AES implementation[END_REF], named after its authors, Billet, Gilbert and Ech Chatbi, is an elegant attack that was developed to break the external encoding implementation of Chow et al. in about 2 30 operations. Hence, it is also a potent attack without any external encodings, and is an important tool to cryptanalyse white-box implementations of AES and other SPNs. As we will see, the attack fully rely on the SPN structure of AES and the internal encoding paradigm to succeed, which means it is not a priori a generic attack against all white-box designs.

We present here the version of the attack that was used to break Chow et al.

implementation, but it is important to note that it was later generalized to more complex implementations later by Michiels et al. [START_REF] Michiels | Cryptanalysis of a generic class of white-box implementations[END_REF] to break implementations with the same rationale of design. More on this attack will be given below.

The attack is based on the fact that a composition of the right tables in the implementation leads to having access to an encoding of the round function. This remark is obvious since the composition of T M C and T xor is by denition an encoding of the round function, simply by correctness of the algorithm. What is not obvious however, is how to go around the external encoding strategy, which does not allow to control the input. We focus here on the recovery of the non-linear part of the encodings, as it is the most important part of the cryptanalysis and clearly shows the structural weakness of the encoding method.

Here is the trick the authors use to go around this problem. If ψ i,j (x 1 , x 2 , x 3 , x 4 ) denotes the 32-to-8-bit function that represents encoded byte of the round function R 1 i,j , Q 1 i,j the output encoding of the last XOR table and P 1 i,j the input encoding of the tables T M C, we have the following equality:

ψ i,j (x 1 , x 2 , x 3 , x 4 ) = Q 1 i,j (R 1 i,j (P 1 1,j (x 1
), P 2 2,j (x 2 ), P 1 3,j (x 3 ), P 4 4,j (x 4 ))

Then, if we note c 1 , c 2 , c 3 , c 4 constants of F 8 2 , we can x 3 out of the 4 bytes of the encoded round function to get:

ϕ i,j (x 1 , c 2 , c 3 , c 4 ) = Q 1 i,j (02 × SB(x 1 + K 1 1,j ) + α 1 (c 2 , c 3 , c 4 )).
These parametrized 8-to-8-bit functions are bijections since the constants α i take all possible values in F 8 2 . The authors then make the key remark that for any xed c 2 , c 3 , c 4 and free x 2 in F 8 2 :

ψ (c 2 ,c 3 ,c 4 ) • ψ -1 (x 2 ,c 3 ,c 4 ) (x 1 ) = Q 1 i,j (02 × SB(y 1 + K 1 1,j ) + α 1 (c 2 , c 3 , c 4 ))
with:

y 1 = (02 × SB) -1 ((Q 1 i,j ) -1 (x 1 ) + α 1 (x 2 , xc 3 , c 4 )) + K 1 1,j
Hence, after simplifying the expression:

ψ (c 2 ,c 3 ,c 4 ) • ψ -1 (x 2 ,c 3 ,c 4 ) (x 1 ) = Q 1 i,j ((Q 1 i,j ) -1 (x 1 ) + α 1 (x 2 , c 3 , c 4 ) + α 1 (c 2 , c 3 , c 4 ))
As α 1 (x 2 , c 3 , c 4 ) + α 1 (c 2 , c 3 , c 4 ) also describes F 8 2 as x 2 goes through F 8 2 with xed c 1 , c 2 and c 3 , we get 2 8 distinct bijections, and if we note ⊕ δ the function such that ⊕ δ (x) = x + δ we have that :

{ψ (c 2 ,c 3 ,c 4 ) • ψ -1 (x 2 ,c 3 ,c 4 ) | x 2 ∈ F 8 2 } = {Q 1 i,j • ⊕ δ • (Q 1 i,j ) -1 | δ ∈ F 8 2 }
At this point, we have a set that depends only on the internal encodings Q 1 i,j which has the excellent property to be a vector space for composition. The following property shows that we can recover Q 1 i,j up to an ane transformation. Proposition 5. Given the set

V δ = {ϵ • ⊕ δ • ϵ -1 |δ ∈ F 8 2 }, where ⊕ δ (x) = x + δ. A map ϵ ′ can be computed where ϵ • ϵ ′-1 is ane. Proof. The map Φ : V δ → F 8 2 dened by Φ(ϵ • ⊕ δ • ϵ -1 ) = δ is an injection as ϵ is a
bjection and a surjection by cardinality. It is then an isomorphism. The knowledge of Φ is enough to recover ϵ, as if Φ(g) = δ we have:

g(0) = ϵ • ⊕ δ • ϵ -1 (0) = ϵ(δ + ϵ -1 (0))
which helps us determine ϵ as g spans V δ .

However, it is not directly possible to get Φ as we cannot get access to δ with our encodings. It is still possible to get Φ up to an ane map.

By computing elements of V δ , it is possible to form a basis of V δ by completing the basis starting from a non-zero element g 1 . We go through V δ by 'brute-force' to check independent elements. We then get access to a basis (g 1 , ..., g 8 ) of V δ . We can then dene an isomorphism Ψ dened over the basis b i by Ψ(g i ) = b i , which is Φ written in the base b i instead of the canonical base. If l is the basis change map from the canonical basis to b i , we have Ψ(g) = l -1 (Φ(g)), hence

g i (0) = l(b i + (ϵ • l) -1 (0))) = l(b i ) + ϵ -1 (0).
If we note A the ane map A(x) = l(x) + ϵ -1 (0), we have for any g:

A • ⊕ Ψ(g) • A -1 = ⊕ Φ(g) Hence, g = ϵ • A • ⊕ Ψ(g) • A -1 • ϵ -1
author is that the implementation is made using a xed representation of the eld, that is, F 2 8 = F 2 [X]/(X 8 + X 4 + X 3 + X + 1). However, for any unitary irreducible polynomial P of degree 8, there is a representation of the eld F 2 [X]/(P ). As there are 30 distinct such polynomials, there is a degree of liberty to build a round function using multiplication and addition in these special representations. Denition 20. Let E and E ′ be two encryption algorithm with space K. E and E ′ are said to be dual ciphers if there exist bijections f , g and h such that :

∀m ∈ M, k ∈ K, f (E k (m)) = E ′ g(k) (h(m)).
Finding dual-ciphers of the AES as been a subject of research in cryptanalysis [START_REF] Barkan | In how many ways can you write rijndael[END_REF],

and Karoumi exploits the fact that there exist more than 9120 dierent dual ciphers of the AES. More precisely, there exist 240 linear maps ∆ such that:

∆(AES k (m)) = AES ∆(k) (∆(m)).
Once the rounds are transformed into their dual form, Karoumi uses the implementation technique of Chow et al. on his round function. We follow the precise description of De Mulder [START_REF] Mulder | White-Box Cryptography: Analysis of White-Box AES Implementations (White-Box Cryptograe: Analyse van White-Box AES implementaties)[END_REF]. We x a representation of F 2 8 by xing an irreducible polynomial P l of degree 8, there are 30 such polynomials. We note Ψ l an isomorphism from the AES representation to this new representation. We note respectively the addition ⊕ l and the multiplication ⊗ l . For any element α ∈ F × 2 8 , let m α (x) = α × x and F t the t-th iteration of the Frobenius, that is F t (x) = x 2 t . We now dene an AES dual round: Denition 21 (Dual AES Round). Let D be the set dened by

D := {Ψ l • m α • F t | l ∈ 1, 30 , α ∈ F 2 8 , t ∈ 0, 7 } Let for any 1 ≤ r ≤ 10, 1 ≤ j ≤ 4, let ∆ r,j ∈ D , ∃(l, α, t) , ∆ r,j = Ψ l • m α • F t
and dene δ r,j = Ψ l • F t . The AES Dual Round for a representation Ψ l , noted AES r,∆ r,j (x 1 , x 2 , x 3 , x 4 ) is the 4-uple (w 1 , w 2 , w 3 , w 4 ), where w i are dened by:

δ r,j (M C 1 ) ⊗ l SB r,j (x 1 ⊕ l ∆ r,j (K t-1 1,j )) ⊕ l δ r,j (M C 2 ) ⊗ l SB r,j (x 2 ⊕ l ∆ r,j K t-1 2,j )) ⊕ l δ r,j (M C 3 ) ⊗ l SB r,j (x 3 ⊕ l ∆ r,j K t-1 3,j )) ⊕ l δ r,j (M C 4 ) ⊗ l SB r,j (x 4 ⊕ l ∆ r,j K t-1 4,j ))
where SB r,j = ∆ r,j • SB • ∆ -1 r,j .

We then have: AES r,∆ r,j j

• (∆ r,j , ∆ r,j , ∆ r,j , ∆ r,j ) = (∆ -1 r,j , ∆ -1 r,j , ∆ -1 r,j , ∆ -1 r,j ) • AES r j

The AES can then be computed by using these new round functions. The obtained result is then conjugated to the real result which allows to compute the correct value with the maps ∆ r,j . The implementation of Karoumi uses these new round functions to build his implementation, to which he applies the implementation technique of Chow Historic Cryptanalysis While the technique of Xiao and Lai incorporates many of the improvements discussed before and the BGE attack cannot be applied as is, the work of Michiels et al. [START_REF] Michiels | Cryptanalysis of a generic class of white-box implementations[END_REF] shows that the BGE attack can be generalized to break a larger class of implementation, to which the implementation of Xiao and Lai belongs.

Michiels et al. adapt the BGE attack on any implementation of any SPN. Formally, the attack requires that:

The round function is bijective and composed of a round key addition, a layer of S-boxes and a linear layer.

The linear layer must be Maximum Distance Separable (MDS)

In the implementation the attacker can read encoded outputs of round functions.

These conditions are pretty easy to satisfy and are trivially satised by any previously discussed implementations. If these conditions are satised, one can state the following theorem:

Theorem 1.2.1 (Michiels et al.). Given traces of the function ϵ

• R 1 [0 : m -1], the vector space V δ = {ϵ • ⊕ δ • ϵ -1 |δ ∈ F m 2 } can be computed in O(m × 2 m
) where ⊕ δ (x) = x + δ. If the vector space V δ can be computed, a map ϵ ′ can be computed in O(2 3m ) where ϵ • ϵ ′ is ane.

This result shows that in essence, the implementations that we considered up to this point are too simple in design and are structurally awed. Hopefully, there is still a lot of design space to be explored.

Lee et al. Implementation

The implementation technique of Lee et al. [START_REF] Lee | A masked white-box cryptographic implementation for protecting against dierential computation analysis[END_REF] The work of Rivain and Wang [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] shows that due to a lack of mask in the round From a high level point of view, the technique used in these implementations is similar to a regular encoding strategy, that is, secret transformations are composed with functions that are necessary to the computation of the whole AES. The security of the implementation is then conditional to the fact that the encodings cannot be split to trivialize key-recovery.

Contrary to look-up tables, whose size is always exponential in their input, the size of a polynomial is, aptly, polynomial in its number of inputs. If its degree is not too high, one can hope to represent computation over a large number of variables by a composition of polynomials that will keep the overall size of the implementation reasonable. The natural goal using this technique is to allow more exibility for the design.

Bringer et al. Construction

The idea comes the Billet and Gilbert block cipher in which they introduce perturbations to enhance the security against algebraic attacks. Roughly speaking, the block cipher from Billet and Gilbert is composed of several rounds of IP-instances. However, Faugère and Perret showed how to break it and Ding explained how to repair it with perturbations.

The implementation of Bringer et al. [START_REF] Bringer | White box cryptography: Another attempt[END_REF]bounces back from this idea and represent the AES round functions as polynomials over F 8 2 and tries to hide the SPN round structure by adding perturbation polynomials. These polynomials are spread from one round to another, and the implementation still follows the 'internal encoding' paradigm by mixing perturbation with the round function with linear encodings. However, the correctness of the implementation cannot be guaranteed o of one representation of the ten perturbed AES rounds. To circumvent that problem, the implementation contains four instances with perturbations and the correct result is computed by a majority vote over the four instances. 8 . This means that the round function is represented as a polynomial of F 2 8 [X 1 , X 2 , X 3 , X 4 ]. For instance, the function SubByte(X i ) is a composition of X 254 i and a linear map which translates to a sum of powers of two in F 2 8 . The complete round function is a linear transformation of the S-boxes, so the round function has 4 variables and is of degree at most 254. The AES algorithm can then be described by the 10 family of these ANFs, 16 for each round. We note, for 1 ≤ t ≤ 10 and 1 ≤ i ≤ 16, S t i the ANFs of the round function.

If this implementation technique was envisioned for AES, the cryptanalysis of Coron

The main idea of the construction is to add the 'controlled faults' with 4 perturbations polynomials and 23 random polynomials for the rst 9 rounds, and 16 perturbation cancellation polynomials at the last round. The last round XORs the cancellation polynomials to the round functions S 10 to cancel the perturbations. By this method, the system S t i is transformed into its perturbed version S ′t j with 1 ≤ i ≤ 43. Finally, 43-to-43-bit linear internal encodings are applied to system S ′t j .

Remark: Note that the perturbation of the system implies an explosion of the number of variables as rounds functions from round 2 to 9 are now in 43 variables. This means that the implementation weights 142MB per AES instance, which is a far more than the usual table-based implementations.

Tools for the implementation

The key components of the implementation are the perturbation polynomials. The goal is to build a system of polynomials Φ that will take the values (ϕ 1 , ..., ϕ 4 ) most of the time. To do so, the author of [START_REF] Bringer | Perturbing and protecting a traceable block cipher[END_REF] propose to translate the ϕ i by a polynomial evaluating to 0 most of the time, for which they propose a construction (we rerefer to [START_REF] Bringer | Perturbing and protecting a traceable block cipher[END_REF]). Denition 22. (Perturbation Polynomials) Let ϕ 1 , ..., ϕ 4 ∈ F 2 8 and 0 ∈ F 2 8 [X 1 , ..., X 16 ] be a polynomial from the construction [START_REF] Bringer | Perturbing and protecting a traceable block cipher[END_REF] that ouptuts 0 for any input x in a message subset U 1 ⊂ (F 2 8 ) 16 . The system of perturbation polynomials Φ = (Φ 1 , ..., Φ 4 ) is dened by:

Φ i = 0 + ϕ i
For any system of perturbation polynomials Φ, we dene the perturbation cancelling polynomials 0 Φ to be a system of 16 polynomials in F 2 8 [X 1 , ..., X 4 ] such that:

0 Φ i (ϕ 1 , .., ϕ 4 ) = 0
The implementation uses particular linear encodings for diusion reasons. We refer to the original paper for their generation.

Description of the Implementation

We rst recall that the implementation is composed of four instances with dierent perturbations polynomials. We describe one instance for a set of perturbation polynomials and then explain how the authors generate these pertubations polynomials for correctness.

The compiler encodes the rst round function with perturbation polynomials and random polynomials. To do so, it draws 19 random polynomials RP 1 in F 2 8 [X 1 , ..., X 16 ], and a 43 by 43 linear encoding M 1 . It then builds the perturbation polynomials Φ = (Φ 1 , ..., Φ 4 ) and computes the encoding of the round system S 1 :

Z 1 = M 1 • (S 1 ||Φ||RP 1 ) S 1 Φ(x) R 1 M 1 Z 1
For any round 2 ≤ t ≤ 9, the perturbations polynomials are carried on by the identity function, new random polynomials RP t and linear encoding M t are drawn and the previous linear encodings are cancelled so that the round function Z t is dened by:

Z t = M t • (S t ||ID||RP t ) • M -1 t-1 M -1 i-1 Y i = Y i-1 S i (Y 1 i-1 ) R i (Z i-1 ) M i
Finally, the last round function Z 10 cancels the perturbations by adding O ϕ into the circuit:

Z 10 (x) = S 10 ( M -1 9 (x)) + O Φ ( M -1 9 (x)) with M -1 9
being the rst 20 coordinates of the inverse of M 9 .

M -1

9 o Φ S R Y 10

+

This last operation eectively eliminates the random polynomials, and if the perturbation polynomials evaluate to (ϕ 1 , ..., ϕ 4 ), they are cancelled by O Φ .

However, as Φ is not always (ϕ 1 , ..., ϕ 4 ), the authors introduce 3 other instances to ensure the correctness of the construction with probability 1. To do so, they generate 4 perturbation polynomials on complementary sets. Let us split the message space 90

Rasoamiaramanana et al. Construction

The implementation of Rasoamiaramanana et al. [START_REF] Rasoamiaramanana | Design of white-box encryption schemes for mobile applications security[END_REF] was rst published as a candidate to the WhiBox 19 contest [START_REF]Ches 2019 ctf challenge whibox contest[END_REF] and was broken among the last candidates. Rasoamiaramanana published the design of the implementation with as security analysis in her

PhD thesis which we describe now. The implementation uses hybrid methods with look-up tables and polynomial representation, which is the rst published using this design rationale. Roughly speaking, the implementation technique follows the internal encoding rationale but uses larger encoding. These encodings are structured to allow to represent the encoded round functions by look-up tables and degree 2 polynomials.

Tools for the Implementation

The implementation is based on two particular encodings. The rst encoding type called type 1 encoding, aims to protect the keyed Sbox of the round function, while including redundancy to lower the degree of its inverse encoding. The type 2 encoding is a degree 2 bijections that encodes the round function, while cancelling the redundancy of the previous encoding.

The type 1 encoding is based on a degree 2 bijection. In their description, they use Dobbertin's polynomials [START_REF] Dobbertin | Uniformly representable permutation polynomials[END_REF].

Proposition 6. Let m = 2n + 1 be an integer. The Dobbertin Polynomial X 2 m+1 +1 + X 3 + X is a bijection of F 2 n . Its coordinate are degree 2 polynomials over F n 2 Remark: The choice of Dobbertin polynomials for this construction seems to be entirely practical. The author do not give any advantage of using Dobbertin's polynomials over any bijection of degree 2 over F n 2 .

Denition 23. Let m > 8 be an integer and let f :

F 8 2 → F 8 2 .
For any m-to-m bits linear map A and n-to-n bit bjection σ, we say that ϵ(y) is a type 1 encoding of y = f (x) if it is of the form :

ϵ(y) = A(y + q(σ(x))||σ(x))
With the notation ȳ = ϵ(y), the inverse type 1 encoding ϵ -1 is:

ϵ -1 (ȳ) = A -1 (ȳ)[0 : 7] + q(A -1 (ȳ)[8 : m])
Denition 24. Let m ′ > 8 and j > 1 be an integer, f : F 8j 2 → F 8 2 and y a vector of F m ′ j 2 . For any m'-to-m' bits linear map A, a m ′ j-to-(m ′ -8)-bit linear map l, a (m ′ -8)-to-8-bit quadratic function q and a Dobbertin polynomial on F 2 m ′ -8 , we say that ξ(y) is a type 1 encoding of y = f (x) if it is of the form:

ξ(z) = A(z + q(l(ȳ))||σ(l(ȳ))
With the notation ȳ = ϵ(y), the inverse type 1 encoding ϵ -1 is:

ξ -1 (z) = A -1 (z)[0 : 7] + q(σ -1 (A -1 (z)[8 : m ′ ])).

Description of the Implementation

The implementation follows the decomposition of Chow et al., that is, the round key is composed with the Sbox and the linear part is set aside to carry the encodings onto the next round. We now describe the compiler.

The rst part of the construction encodes the T-boxes, that is, the functions:

T t i,j (x) = SB(x + K t-1 i,j ) T 10 i,j (x) = SB(x + K 9 i,j ) + K 10 i,j
The compiler then draws type 1 encodings ϵ r i for 0 ≤ i ≤ 15 and 0 ≤ r ≤ 9 and type 2 encodings ξ r i for 0 ≤ i ≤ 15 and 0 ≤ r ≤ 9.

T 1 i (x) = ϵ 1 i (T 1 i (x)) T t i (x) = ϵ t i (T 1 i ((ξ t-1 i ) -1 (x)) T 10 i (x) = T 1 i ((ξ 9 i ) -1 (x)
The sizes of the encodings depend of the round, according to the following

S i σ q + A
The tables are encoded so that encodings are cancelled after compositions of the encoded functions. For the correctness of the implementation, the encoding of the tables are carried onto the linear map. If we denote by L to be the 32-to-32-bit linear map that is the composition of ShiftRows and Mixcolumns, the compiler computes:

Lr = (ξ r 0 ||...||ξ r 15 ) • (L||L||L||L) • ((ϵ r-1 0 ) -1 ||...||(ϵ r-1 15 ) -1 )
Round 8 has been modied to include a redundancy countermeasure against DFA, hence, the linear map L 8 has been tweaked to add redundancy to thwart fault attacks.

It is important to note that the form of the type 2 encodings allows for the polynomials Lr to be only of degree 2. Indeed, the implementation is then composed of:

The truth tables T 1 i (x), T t i (x) and T 10 i (x). These truth tables are T-box encoded with type 1 input encodings and type 2 output encoding.

The collection of polynomials Lr . These are encodings of the round function with type 2 input encodings and type 1 output encodings.

For the sake of clarity, we detail a short correctness and size analysis of the implementation.

First, it is important to note that the polynomials Lr are of degree 2 over its inputs. Indeed, as the functions R t (L||L||L||L) • ((ϵ r-1 0 ) -1 ||...||(ϵ r-1 15 ) -1 )(ȳ) compute the round function by correctness of the inverse encodings ϵ t i , the encoded function Lr is such that:

ξ t i (ȳ) = A(R t [8i : 8i + 7](x) + q(l(ȳ)||σ(l(ȳ))) As R t is of degree 2 in ȳ, the encoding ξ t i (ȳ) is a degree 2 function.

Cryptanalysis

As a contestant of the WhiBox19 constest, this implementation has been broken, like of the other participants. In Rasoamiaramanana PhD Thesis, the security analysis is focused on DCA and Collision Attacks. If DCA against S-boxes are ruled out due to the encoding size and the analysis of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF], the authors attribute the break of their construction to collision attacks. Indeed, the collision attack strategy is adapted to internal encoding implementations (part I chapter 4). The authors also claim the security of their implementation against DFA, which we do not discuss here.

We want to underline another weakness of this implementation, which lies in the small degree of the inverse of the encodings. To start, let us recall that the map Lr is an encoding of the round function of the form:

ξ t i (ȳ) = A(R t [8i : 8i + 7](x) + q(l(ȳ)||σ(l(ȳ)
)) As a consequence, the inverse encoding (ξ t i ) -1 is also of degree 2 in the output ȳ of the encoded tables and the output z = ξ t i (ȳ) of the polynomials Lr . Indeed, if we note z = ξ t i (ȳ), one can remark that:

R t [8i : 8i + 7](x) = A -1 (z)[0 : 8] + q(l(ȳ))
This means that even if the inverse encoding ξ -1 is not of degree 2 in z, there exist a degree 2 relation in z and ȳ that allows to recover R t [8i : 8i + 7](x). An attacker can then launch a degree 2 LDA on R t [8i : 8i + 7](x) by xing 3 out of the 4 bytes. The complete key recovery can be made in complexity 16×(σ(17×4, 2)+σ(17×16, 2))×2 8 .

Synthesis of Security of White-Box implementation of the AES

We now make a complete summary of the the security of the state-of-the-art implementations we described earlier in the chapter. We evaluate the security of the Against DCA DCA has been showed to be really ecient to break all the state-ofthe-art implementations as we have seen in part I. When it is not possible to break the implementation targeting the S-box, it is possible to target the encoding of the round function.

Against CCA and MIA Reported to be ecient against many state-of-the-art implementations with internal encodings in [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF], the CCA breaks all the implementations using the Against BCA The Bucketing Computational Attack is not a historic threat but is proven to be really ecient against state of the art constructions. The paper of Zeyad et al. [START_REF] Zeyad | Another look on bucketing attack to defeat white-box implementations[END_REF] shows that most of the implementations with small encodings are broken by it in few minutes. This is the case of all the papers using Chow et al. We mark by * if an attack is ecient against an implementation and by ? if it is unknown. We refer to the previous paragraph for the justications. We do not put the exact complexity of the attack as for many of these implementations, some improvements can be done on the complexity of attacks with adaptation of state-of-the-art techniques.

Chapter 2 A SPN implementation Technique: Randomized Circuit Knitting

In this chapter we describe a rationale of implementation we call Randomized Circuit Knitting that is aimed to resist algebraic attacks such as high-order LDA or the BGE attack. We rst describe it through an implementation of AES, a challenge, and a security analysis. Then, we show that this rationale can be applied to other SPNs to provide similar security properties in the plain white-box model.

The AES-RCK Implementation

In this section, we detail our implementation of the AES. We rst explain the rationale of the construction from a high level point of view. We then detail the ten rounds of our implementation. We show its correctness and briey study its size.

Links with previous works

The implementation we propose is made according to the internal encoding rationale.

However, similarly to the implementation of Rasoamiaramanana et al., it uses the polynomial representation of computations to achieve security. Especially, it uses particular encodings that are adapted to this structure.

Rationale of the Construction

The starting point of our construction is the weakness of usual design against automated attacks, especially LDA. The main problem with the usual internal encoding strategy is that it does not make an optimal use of the available parameters the degree of the encoding and its support to increase the complexity of the attack. For seminal implementations, encodings where made on 4-bit nibbles, later augmented to 8-bit or more, but without a diusion of said encodings on the round function. It means that attacks can easily be made on 8-or 16-bit keyspace, with a small computation trace when the support is small.

To circumvent this problem, we divide our construction into two parts. First, we "expand" the usual AES by adding random transformations to round functions. These functions are incorporated to the round function with a 1-round Feistel transformation and for correctness, the 1-round Feistel is composed onto the next round. This transformation allows us to locally augment the degree and to increase the support of the substitution part. The counterpart for the augmentation of the degree is an exponential augmentation of the substitution part size. This expansion phase is however designed to keep the size of the substitution part reasonable.

After we have expanded our round functions, we perform an encoding step on the expanded rounds to "knit" rounds and secret transformations together. To avoid linear encodings while keeping the implementation size reasonable, we use encodings in that have inverses of degree 2. Using these bijections will allow us to augment the degree of the involved transformations once again. Their composition will lead to a degree 4 transformations over a relatively large support, but once again, this step is crafted to keep the size reasonable.

The complete implementation is then the composition of encoded substitution parts Σ and the degree 4 encoding compositions Λ. As Σ are transformations of full degree over their inputs, we represent them as truth tables for a tight representation. The polynomial coordinates of Λ are however only of degree 4, so we represent them by their algebraic normal forms.

Preliminaries

We here recall or dene few notations that we will need for the description of our implementation. To avoid using too many multi-indexes, for any function

f from F n 2 to F m 2 we note when it is well dened f [a : b] = (f a , ..., f b ).
For any set element (x 1 , .., x n ) ∈ F n 2 and integer d, we note M on d (x 1 , ..., x n ) the set of all the monomials in the x i of at most degree d. We note its cardinal σ(n, d) = d i=0 n i .

For any bijection f : F n 2 → F n 2 , we note f -1 its inverse. For any injection f :

F n 2 → F m
2 with m ≥ n we also note f -1 its left inverse, i.e. the function

F m 2 → F n 2 such that f -1 • f = id F n 2 .
We now describe families of functions we will need for our description:

Denition 25. Let d 1 , d 2 , n, m ∈ N * . We dene the set F d 1 n,m of all functions f : F n 2 → F n 2 such that ∀i ∈ 1, m deg(f i ) = d 1 We dene the set S d 1 ,d 2
n to be the set of all bijections f :

F n 2 → F n 2 such that ∀i ∈ 1, m deg(f i ) = d 1 and deg(f -1 i ) = d 2 . We note S d, * n = ∪ n i=1 S d,i n and S * ,d n = ∪ n i=1 S i,d n
To the best of our knowledge, to provide a generic ecient sampler over S 2,d n for any n, d ∈ N * is not an easy task. We do not provide a solution to this problem, but we provide a solution to sample on a subset of S 2, * n that will be large enough as n increases.

Sampling in S 2, * n For the need of our implementation technique, we will need a sampler in S 2, * n . However, to the best of our knowledge, sampling uniformly in this set is not an easy task, and there is no published sampling algorithm available. To circumvent that problem we will sample in a well-known subset of S 2, * n that stems from multivariate techniques it is almost exactly the C * trapdoor function.

For any integer n, one can study monomials in F 2 n that are of degree two when projected onto F n 2 , that is, monomials of the form X D with HW (D) = 2. Now, consider the special case where we take n such that:

∃D ∈ 2, n -1 gcd(D, 2 n -1) = 1 and HW (D) = 2. Then F = X D is a bijection of inverse F -1 = X D ′ where DD ′ = 1 mod 2 n -1. The degree of F -1 over F 2 is HW (D ′ ).
It is important to note that this construction will not work certain values of n. For instance, there are such no bijective monomials for n = 32 due to the smoothness of 2 32 -1. To be sure it exists, we will sample in S 2, * n when n is odd only. Now that we have a candidate bijection in S 2, * n we use the well-known multivariate to get a family of bijections: we compose x D with linear operations S and T . Formally, we project x D over F n 2 bijection over (F 2 ) n . To do so let us x a basis (e 1 , ..., e n ) ∈

(F 2 n ) n of F 2 n over F 2 . It induces an isomorphism π from (F 2 ) n to F 2 n such that π(x 1 , ..., x n ) = n i=1
x i e i . Then we dene the bijection σ S,F,T as the map from F n

2 to F n 2 is dened by: σ S,F,T = T • π -1 • F • π • S
Regarding our sampling problem, for each linear transformations S and T , we get a bijection σ S,x D ,T . However, as shown in [START_REF] Wolf | Equivalent keys in hfe, c * , and variations[END_REF], there are some equivalent choices of S and T that get to the same P essentially, maps that commute to a certain extend with the central map. The number of maps we get is the cardinal of GL n (F 2 ) × GL n (F 2 ) divided by the cardinal of the equivalence classes:

( n-1 i=1 (2 n -2 i )) 2 n(2 n -1) = O( 2 (n-1) 2 n )
Hence the following property:

Proposition 7. For any integer n and any D ∈ 2, n -1 gcd(D, 2 n -1) = 1 and HW (D) = 2. Let π be the canonical isomorphism from (F 2 ) n to F 2 n . We have :

#{T • π -1 • x D • π • S|(S, T ) ∈ GL n (F 2 ) 2 } = ( n-1 i=1 (2 n -2 i )) 2 n(2 n -1)
and the cardinal of the set of bijections S 2, * n is at least

( n-1 i=1 (2 n -2 i )) 2 n(2 n -1) .
This means that for n reasonably small, we can sample in a subset of S 2, * n that has more than 2 λ elements for a brute force search.

Our Implementation

We now describe the compiler. It is composed of 10 rounds transforming the 10 AES rounds (S i , L i ) into 10 new round functions (Σ i ; Λ i ). The functions Σ i are stored as truth tables and the functions Λ i are stored as their ANF.

For sake of simplicity, we introduce notations, grouping transformations by their functionality:

First, we relabel bytes of the state in the following way :

    s 0,0 s 0,1 s 0,2 s 0,3 s 1,0 s 1,1 s 1,2 s 1,3 s 2,0 s 2,1 s 2,2 s 2,3 s 3,0 s 3,1 s 3,2 s 3,3     →     x 0 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15    
We dene S i , and S i j its components byte by byte, to be the composition of AddRoundKey and SubBytes, that is we consider the keyed S-boxes:

S i (x) = (S i 0 (x 0 ), ..., S i 15 (x 15 )) = (SB(x 0 + K i 0 ), ..., SB(x 15 + K i 15 ))
We dene L i , and L i j its component 32 bits per 32 bits, to be the composition of ShiftRows and MixColumn for i ≤ 9 and the composition of ShiftRows and AddRoundKey for i = 10.

With these notations the rounds of the AES are just the composition of S i and L i . We note R i the round functions.

Round 1

We describe the algorithm for the rst quarter of the state, that is, for the round functions R 1 0 to R 1 31 . The algorithm applies the same way to other quarter of states, with the corresponding change of indexes.

The Substitution Σ The compiler rst draws random functions r 1 1,i ∈ F 16,5 for each 1 ≤ i ≤ 2, and transformations f 1 i,j ∈ F 5,8 of degree 5.

The compiler then computes two rst masks for pairs of keyed S-boxes by computing:

mask 1 1,1 = S 1 0 (z 0 ) + f 1 1,1 (r 1 1,1 (z 0 , z 5 )) mask 1 1,2 = S 1 5 (z 5 ) + f 1 1,2 (r 1 1,1 (z 0 , z 5 )) Σ1 1,1 = mask 1 1,1 ||mask 1 1,2 ||r 1 1,1 (z 0 , z 5 )
The same is done with other half of the state with s 10 and s 15 to compute:

Σ1 1,2 = mask 1 2,1 ||mask 1 2,2 ||r 1 1,2 (z 10 , z 15 )
The compiler nally computes the complete substitution part Σ by drawing two bijections σ 1 , σ 2 ∈ S * , 2 21 and composing them respectively with Σ1 and Σ2 :

Σ 1 1,i = σ 1,i • Σ1,i
The Diusion Λ The linear layer is then modied accordingly for correctness. If we note y i the output of Σ 1,i :

ỹi = σ 1 1,i -1 (y i ),
the inverse of the encodings are composed with the linear part of the round L 1 , for k ∈ 1, 4 :

L1 1,k := L 1 1,1 (ỹ 1 [0 : 7],
L1 1,k = ext 1 1,k • ext L1 1,k
The compiler then encodes bits corresponding to a S-box input of the next round by drawing, for k ∈ 1, 4 , τ 1,k ∈ S 2, * 21 at random computing:

Λ 1 1,k = τ 1,k • ext L1 1,k
The same is done for all bytes of the round function.

Output:

The output of the rst round is the collection of the applica-

tions Σ 1 = (Σ 1 1,1 , Σ 1 1,2 , ..., Σ 1 4,1 , Σ 1 4,2
) and the collection of the applications

Λ 1 = (Λ 1 1,1 , ..., Λ 1 1,4 , ..., Λ 1 4,1 , ..., Λ 1 4,4 ). The applications 1 ≤ i ≤ 4,1 ≤ j ≤ 4 τ 1 i,j and
ext 1 i,j and the functions 1 ≤ i ≤ 4,1 ≤ j ≤ 2, σ 1 i,j and f 1 i,j are carried as inputs for the next round.

Round 2

We describe the algorithm for the rst quarter of the state, that is, for the round functions R 2 0 to R 2 31 . The algorithm applies the same way to other quarter of states, with the corresponding change of indexes. We suppose that we have the output

functions 1 ≤ i ≤ 4,1 ≤ j ≤ 4 τ 1
i,j and ext 1 i,j and the functions 1

≤ i ≤ 4,1 ≤ j ≤ 2, σ 1
i,j and f 1 i,j of the previous round. We note z to be the output of Λ 1 , and we dene z i to be the coordinates of z by blocs of 21 bits, that is z = (z 0 , ...z 20 ).

The Substitution Σ The compiler rst composes the previous round transformation with the S-boxes of the current round and the 1-Round Feistel structure for correctness:

z ′ k = τ 1 i,j -1 (z k ) S ′2 k = S 2 k (z ′ k [0 : 7]+L 1 1 (f 1 1,1 (z ′ k [8 : 12]), f 1 1,2 (z ′ k [8 : 12]), f 1 2,1 (z ′ k [13 : 17]), f 1 2,2 (z ′ k [13 : 17]
)) The compiler draws random functions for each r 2 1,i ∈ F 21,3 (1 ≤ i ≤ 2) transformations of degree f 2 i,j ∈ F 3,3 .

The compiler then computes a mask for each keyed S-boxes by computing:

mask 2 1,i := S ′2 5k (z ′ 5i ) + f 2 1,i (r 2 1,i (z ′ 5i )) Σ2 1,i := mask 2 1,i || r 2 1,i (z 5i )
The compiler nally computes the complete substitution part Σ by drawing a bijection for each S-box σ 2 1,i , ∈ S * ,2 11 and composing them with Σ2

1,i :

Σ 2 1,i = σ 2 1,i • Σ2 1,i
The Diusion Λ The linear layer is then modied accordingly for correctness. If we note y i the output of Σ 1,i :

ỹi = σ 2 1,i -1 (y i ),
the inverse of the encodings are composed with the linear part of the round L

L2 1,k = ext 2 1,k • ext L2 1,k
The compiler then encodes bits corresponding to a S-box input of the next round by drawing, for k ∈ 1, 4 , τ 1,4 ∈ S 2, * 21 at random computing:

Λ 2 1,k = τ 1,k • ext L2 1,k
The same is done for all bytes of the round function.

Output: The output of the second round is the collection of the applications ). The applications 1 ≤ i ≤ 4,1 ≤ j ≤ 4 τ 2 i,j and ext 2 i,j , σ 2 i,j and f 2 i,j are carried as inputs for the next round.

Σ 2 = (Σ

Round 3 to 9

We describe the algorithm for the rst quarter of the state, that is, for 3 ≤ t ≤ 9 the round functions R t 0 to R t 31 . The algorithm applies the same way to other quarter of states, with the corresponding change of indexes. We suppose that we have the

functions 1 ≤ i ≤ 4,1 ≤ j ≤ 4 τ t-1
i,j and ext t-1 i,j and the functions 1

≤ i ≤ 4,1 ≤ j ≤ 2, σ t-1
i,j and f t-1 i,j of the previous round. We note z to be the output of Λ t-1 , and we dene z i to be the coordinates of z by blocs of 21 bits, that is z = (z 0 , ...z 20 ).

The Substitution Σ The compiler rst composes the previous round transformation with the S-boxes of the current round and the 1-Round Feistel structure for correctness:

z ′ k = τ t-1 i,j -1 (z k ) S ′t k = S t k (z ′ k [0 : 7]+L t 1 (f t-1 1,1 (z ′ k [8 : 10]), f t-1 1,2 (z ′ k [11 : 13]), f t-1 1,3 (z ′ k [14 : 16]), f t-1 1,4 (z ′ k [17 : 19]
)) The compiler draws random functions for each r 2 1,i ∈ F 21,3 (1 ≤ i ≤ 2) transformations of degree f t i,j ∈ F 3,3 .

The compiler then computes a mask for each keyed S-boxes by computing:

mask t 1,i := S ′t 5k (z ′ 5i ) + f t 1,i (r t 1,i (z ′ 5i )) Σ2 1,i := mask t 1,i || r t 1,i (z 5i )
The compiler nally computes the complete substitution part Σ by drawing a bijection for each S-box σ t 1,i , ∈ S * ,2 11 and composing them respectively with Σt 1 and Σt 2 :

Σ t 1,i = σ t 1,i • Σt 1,i
The Diusion Λ The linear layer is then modied accordingly for correctness. If we note y i the output of Σ 1,i :

ỹi = σ t 1,i -1 (y i ),
the inverse of the encodings are composed with the linear part of the round L

Lt 1,k = ext t 1,k • ext Lt 1,k
The compiler then encodes bits corresponding to a S-box input of the next round by drawing, for k ∈ 1, 4 , τ 1,4 ∈ S 2, * 21 at random computing:

Λ t 1,k = τ t 1,k • ext Lt 1,k
The same is done for all bytes of the round function.

Output: The output of the second round is the collection of the applications ). The applications 1 ≤ i ≤ 4,1 ≤ j ≤ 4 τ t i,j and ext t i,j , σ t i,j and f t i,j are carried as inputs for the next round.

Σ t = (Σ t

Round 10

We describe the algorithm for the rst quarter of state, that is, for the round functions R 10 0 to R 10 31 . The algorithm applies to the same way to other quarter of states, with the corresponding change of indexes. We suppose that we have the functions f 9

i,1 and

f 9 i,2 (1 ≤ i ≤ 4
) of the previous round. We note z the output of Λ 9 , and we dene z i to be the coordinates of z by blocs of 21 bits, that is z = (z 0 , ...z 21 ).

The Substitution Σ The compiler rst composes the previous round transformation with the S-boxes of the current round:

z ′ k = τ -1 k (l -1 k (z k ) S ′t k = S t k (z ′ k [0 : 7]+L t 1 (f t-1 1,1 (z ′ k [8 : 10]), f t-1 1,2 (z ′ k [11 : 13]), f t-1 1,3 (z ′ k [14 : 16]), f t-1 1,4 (z ′ k [17 : 19]))
As the linear layer is a permutation for last round, the compiler just composes the two layers:

Σ k = L(S ′ 0 , ...S ′ 15 )[8k : 8k + 7]
Output: The output of the last round is the collection of the applications Σ 10 = (Σ 0 , ..., Σ 15 ).

Correctness and Size of the Implementation

We now show the correctness of our algorithm and detail its size.

Correctness Round 1 For round 1, we just show that the composition of Σ and Λ is a special encoding of the round function. We only show this for the rst quarter of state and the proposition follows for the others.

Proposition 8. The function

Λ 1 1,1 (Σ 1 1,1 , Σ 1 1,2 , Σ 1 1,3 , Σ 1 1,4
) is an encoding of 8 bits of the round function R 1 1,1 . More precisely, with the notations of section 3.2 of round 1,if we note y the output of Λ

1 1,1 (Σ 1 1,1 , Σ 1 1,2 , Σ 1 1,3 , Σ 1 1,4
) for an input x and y ′ := ext 1 1,1 (τ 1 1,1

-1 (y), the following relation stands :

R 1 1,1 (x) = y[0 : 7]+L 1 1 (f 1 1,1 (y[8 : 12]), f 1 1,2 (y[8 : 12]), f 1 2,1 (y[13 : 17]), f 1 2,2 (y[13 : 17]))[0 : 7]
Proof. By construction, the mappings σ 1 1,j -1

and σ 1 1,j cancel out when composed.

Then, as L is a linear map, it commutes with the addition of the masks mask i,j , hence,

Λ 1 1,1 (Σ 1 1,1 , Σ 1 1,2 , Σ 1 1,3 , Σ 1 1,4
) is an encoding of :

R 1 1,1 + L 1 1 (mask 1 1,1 , mask 1 1,2 , mask 1 2,1 , mask 2,2 )[0 : 7] || r 1 1,1 || r 1 1,2
The rest follows from the inverse of the extension and of τ 1

1,1 to encode the following round.

Round 2 to 9 The construction is very similar for rounds 2 to 9 with the exception of round two having specic parameters. We show the result for round 2 and the proof for round 3 to 9 follows. We state that after t -1 rounds of our construction, the t-th round is an encoding of the t-th round of the AES. We only show this for the rst quarter of state and the proposition follows for the others. Proposition 9. Let z be the output of the (t -1)-th round of the implementation, that is, the output of Λ t-1 after the composition of the round functions on the input of x. The function Λ t 1 (Σ t 1,1 , ..., Σ t 1,4 , ...., Σ t 4,1 , ..., Σ t 4,4 )[0 : 20](z) is an encoding of the rst 8 bits of the composition of t rounds of the AES. More precisely, with the notations of section 3.2 of round 1,if we note y the output of this function for an input x, and y ′ := ext t 1,1 (τ t 1,1

-1 (y) the following relation stands

R t 1,1 (x) = y[0 : 7]+L 1 1 (f 1 1,1 (y[8 : 10]), f 1 1,2 (y[11 : 13]), f 1 1,3 (y[14 : 16]), f 1 1,4 (y[17 : 19]))[0 : 7]
Proof. To prove it by induction, consider the basic case t = 2. By the correctness property of round 1, the rst round of the implementation is an encoding of the rst round of the AES of the form, with the notations for x, y and y

′ := ext 1 1,1 (τ 1 1,1 -1 (y)
dened in the proposition, the following relation stands :

R 1 1,1 (x) = y[0 : 7]+L 1 1 (f 1 1,1 (y[8 : 12]), f 1 1,2 (y[8 : 12]), f 1 2,1 (y[13 : 17]), f 1 2,2 (y[13 : 17]))[0 : 7]
Then, by construction, the mapping Σ2 i starts by cancelling out τ 1 1,1 . Then, it computes masks f i,j (r k,l ) and adds L 1

1 (f 1 1,1 (r 1 1,1 ), f 1 1,2 (r 1 1,1 ), f 1 2,1 (r 1 1,2 ), f 1 2,2 (r 1 1,2
)) to the masked round. As L 1 is linear, it commutes with the additions of the masks and correctly unmasks the round. The rest of the round is similar to round 1, except the input is already large, so we choose smaller masks.

For heredity, the proof stems from the same arguments as the basic case, except the encodings σ and τ are applied to all the input/output of their respective mappings.

Round 10 Round 10 is just composed of the inverse encoding of the previous round and a substitution part. The correctness stems from the same arguments as for Σ t 's correctness.

Size of the Implementation

We now give a short synthesis of the sizes of the implementation. All the sizes of each component for each is given in bits. The size a n-to-m bits truth table is m × 2 n and the size of a polynomial of degree 4 in a boolean polynomial ring is given by its monomials, that is at most σ(n, 4).

Synthesis and Remarks Adding up all rounds the implementation weighs about

The fast growth of the size of the polynomials is a problem this technique cannot avoid which limits the array of 'reasonable' parameters. However, if we want bigger implementations, we can use bigger tables for Σ by adding variables in the rst round substitution part or using a larger encoding in round 2 to 10. The number of coordinates of Λ will then grow linearly, and the size of the truth table will rapidly catch up to dominate the implementation size. This regime of parameters is surely interesting for better security claims if bigger implementations are not a problem. For the challenge construction however, we tried to minimize the space requirements. More on this topic in the security conjecture section.

Concerning running time, similarly to the size analysis, the polynomials of Λ take the most time to be computed. As we use a simple polynomial evaluation technique in our implementation, that is, computing the monomials in a given input and then adding the corresponding monomials, the time used is then proportional to the size of our polynomials.

Security Analysis

We now perform the analysis of our construction. We recall that the study of fault attacks are out of the scope of this thesis. The goal of this analysis is to estimate the unbreakability of our compiler against state-of-the-art attacks, especially the algebraic ones.

When implementations are only composed of truth tables, no intermediate values appear during the computation of these tables, and the security analysis can be performed with only the input-ouput behavior of these atomic elements. However, when we add polynomials to an implementation however we add intermediate values such as monomials and their sums to computation traces. To perform a security analysis, one has to either consider each of these monomials and their combinations, or try to reduce the analysis to the input-output behavior of the polynomials -under right hypotheses. As the rst option makes a precise analysis impossible due to the combinatorial complexity of the problem, we will formalize hypotheses and rely on the second strategy.

It is important to note that this strategy is not new by any means. Indeed, it is common in multivariate cryptography to make these kind of assumptions when known structural attacks are not ecient. For instance, for cryptosystems based on the IP problem such as HFE or UOV (see also Part III), if the state-of-the-art attacks are not ecient enough, we consider that the polynomials are similar to a 'black-box', that is, the monomials they are composed of and their partial sums do not give more information than the complete input-ouput behavior of these polynomials.

For the rest of the analysis, we make the following reasonable hypothesis: having the polynomials of the application Λ on our algorithm is equivalent to having their truth table for the cryptanalysis. This hypothesis can obviously be challenged. A more detailed discussion about these hypotheses will be given in part III.

Furthermore, automated attacks are usually launched with a set of target functions to test. For this analysis, we will consider that targets are the most common ones, that is, outputs of the S-boxes and outputs of round functions.

Against LDA

To study the complexity of LDA or high order LDA against our construction, we detail the mappings that allow to recover the target function. We then discuss their degree.

Targeting a S-box We focus our analysis on round 1 as it is the case where the key-space is the smallest. We also detail the analysis only for Σ 1 1 as it is easy to generalize to the complete mapping Σ 1 . The analysis for S-boxes stems from the following property:

Proposition 10. Let y = Σ 1 1,1 (x 0 , x 15 ). We have:

S 0 (x 0 ) = σ 1 1,1 -1 (y)[0 : 7] + f 1 1,1 (σ 1 1,1 -1 (y)[16 : 19]
)

S 5 (x 5 ) = σ 1 1,1 -1 (y)[8 : 15] + f 1 1,2 (σ 1 1,1
-1 (y) [16 : 19])

As we note S 0 (x 0 ) = ψ 0 (y) and S 5 (x 5 ) = ψ 5 (y), for any other keyed S-box S ′ 0 and S ′ 5 we have:

S ′ 0 (x 0 ) = S ′ 0 (S -1 0 (ψ 0 (y)) S ′ 5 (x 5 ) = S ′ 5 (S -1 5 (ψ 5 (y))
Proof. The proof is trivial from the construction of Σ 1 .

According to this result, a d-LDA of order d = deg(ψ 0 ) will have a solution for S 0 . If d is smaller, the LDA will not succeed as ψ 0 is by denition the inverse of the encoding transformation. Furthermore, the second part of the property shows that a LDA of order deg(S ′ 0 (S -1 0 (ψ 0 ))) will also have a solution for any other keyed sbox S ′ 0 .

To continue our analysis, we have to estimate the degree of deg(ψ 0 ) and deg(S ′ 0 (S -1 0 (ψ 0 ))) when S 0 , S ′ 0 , f i,j and σ 1 vary through their respective spaces. We propose this conjecture, supported by numerical tests:

Conjecture: If S 0 ̸ = S ′ 0 are keyed s-boxes drawn at random and f i ∈ F 5,5 and σ 1 ∈ S * ,2 21 drawn at random, then the degree of coordinates of ψ 0 and and deg(S ′ 0 (S -1 0 (ψ 0 ))

are greater or equal to 10 independently of the key with overwhelming probablility.

If this conjecture stands, an attacker with LDA has to use σ(21, 10) > 2 16 monomials for the 2 16 possible inputs and the system admits solutions for more than a single key : it contains about 2.5 more variables than equations. The LDA then fails targeting the mappings Σ 1 .

Remark: We stated a strong version of the conjecture we really need, because it is a more succinct property. Indeed, it is enough for us that this result stands for enough S ′ 0 so that an adversary cannot reduce the key-space enough to brute force the leftover keys afterwards.

Targeting Round Functions We also focus on round 1 for key-space reasons and on the rst byte of the round function. By property 2, the composition of Σ 1 and Λ 1 is an special encoding of the AES rst round function. Let us note the degree of its decoding relation d.

Contrary to the attack on S-boxes, as the encoding is only of size 21, we have a solution for degree d for the right key-guess and no a priori solutions for other keyguesses. Indeed, a byte of an AES round function with a xed key k is not a basis for round functions with other keys k ′ ̸ = k. We can then evaluate the complexity of the attack according to section 2:

σ(21, d) 2 × 2 32
Again, we have to study the degree d depending of its composing elements:

Conjecture : For f i,j ∈ F 5,5 and τ 1 ∈ S * ,2

Targeting Sboxes In [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF], the authors prove that for random functions, the probability of success of a DCA against encoded S-box is small when the size of the encoding is bigger than the S-box support. In our case, S-boxes σ i are "encoded" into Σ i that is a mapping from F 16 2 to F 21 2 . In an ideal setting, this means that a DCA is not successful against with S-box as targets.

Targeting Round Functions In this setting, the size of the encoding of the round function is 21. This means that DCA can be used with a reasonable probability of success. However there are no results for this kind of encodings. If we apply the strategy of [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF] for 16-to-8-bit encodings, as our encodings are packed by pairs of bytes, we can x any bytes to simplify the attacks an the complexity is, with the notations of their paper:

T × N × #K = 21 × 2 21×2 × 2 32

Against MIA and Collision Attacks

To perform MIA and collision attacks, one has to target a non-injective function of the algorithm. In [START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF], the authors directly target the round function and exploit the equivalence between a collision on the round function and a collision on the encoded round function, as the encoding is a bijection. However, in our setting, the encodings of rounds are not local bijections. We still focus our study on the rst byte of round 1, which can be generalized to the rest of the round. Proposition 11. Let x = (x 0 , x 5 , x 10 , x 15 ) and x ′ = (x ′ 0 , x ′ 5 , x ′ 10 , x ′ 15 ) be two distinct vectors of 4 bytes. If there is a collision Λ 1 [0 : 16](x) = Λ 1 [0 : 16](x ′ ) then :

     R 1 [0; 7](x) = R 1 [0; 7](x ′ ) r 1 1,1 (x 0 , x 5 ) = r 1 1,1 (x ′ 0 , x ′ 5 ) r 1 1,2 (x ′ 10 , x ′ 15 ) = r 1 1,2 (x ′ 10 , x ′ 15 )
Proof. By property 2, a collision implies a collision for a function of the form:

τ 1 (R 1 [0 : 7] + L 1 1 (f 1 1,1 (r 1 1,1 ), f 1 1,2 (r 1 1,1 ), f 1 2,1 (r 1 1,2 ), f 1 2,2 (r 1 1,2 )||r 1 1,1 ||r 1 1,2 )
We can then remove the bijection τ 1 , but as we carry the random terms from the construction of Σ, a collision of the complete state implies a collision on all the coordinates and as the masks are computed from the rightmost part of the state, we have the desired property. This property means that collisions are observed on the encoded state when the random polynomials r 1 1,1 (x 0 , x 5 ) and r 1 1,2 (x 10 , x 15 ) and the round function simultaneously collide. In other words, the set of collisions is the intersection of the set of collision points of these 3 functions. If we consider the polynomials r 1 1,1 (x 0 , x 5 ) and r 1 1,2 (x 10 , x 15 ) as random functions from F 16 2 to F 5 2 , it means that they have 2 11 collisions on average. The cardinal of the intersection of the sets of collision points is now bounded by 2 11 and a subset of the collision of the round function, which reduces the set of collisions which was of about 2 24 collisions for a round function. To know whether this set is small enough to protect against collision attacks is a challenge for future works.

Against BCA

In the state of the art, BCA has been mostly used against non-injective encodings of S-boxes. In our case, the encodings of the S-boxes are wider than their input, hence the collision property that is needed by BCA to function is not present. We conjecture our construction to be secure against this form of BCA.

Against the BGE Attack

Let us rst recall the main theorem used for the BGE attack. In the BGE attack setting, an m bits encoding of a round function can be found in execution traces. Let assume that R 1 [0 :

m -1] is encoded by a m-to-m-bit bijection ϵ so that ϵ • R 1 [0 : m -1]
can be observed in execution traces. In the following we use the generalized attack of Michiels et al. [START_REF] Michiels | Cryptanalysis of a generic class of white-box implementations[END_REF].

In our setting, the encodings are not local bijections and the set V δ cannot be computed. Indeed, the proof of the theorem stands and the set V δ can be computed if there exist two sets of inputs x1 ,x 2 and functions ψ 1 and ψ 2 such that h(x

1 , x2 ) = ϵ(ψ 1 (x 1 ) + ψ 2 (x 2 )) = ϵ • R 1 [0 : m -1](x)
and for any constant c 1 and c 2 , h(x 1 , c 2 ) and h(c 1 , x2 ) are bijections (see [START_REF] Michiels | Cryptanalysis of a generic class of white-box implementations[END_REF] for more details).

As we add random 16-to-5 noise polynomials, that are not bjiections, there is no such decomposition of the encoding of our round function and the BGE attack cannot be applied against our design.

Variations of the Challenge Implementation

To improve the security of the construction we can adjust the parameters of the construction. The rst parameter to adjust is the size of the Σ tables. The input size of these tables is dependent on the number of random polynomials added. If n r is the number of random polynomials we introduced, their input size is at least 8 + 2 × n r + 1 for the rst round and 8 + 4 × n r + 1 for the other rounds, since we need an odd number of inputs for our encodings. For the challenge, n r = 5 on the rst round and n r = 3 for the rest of the implementation. Another possibility is to increase the size of the table outputs, hence the number of variables of the polynomials. It is one of the less costly adjustment since the size only increases polynomially by a degree 4 when we add variables. With these remarks in mind we propose 2 other implementations that are variations of the challenge.

The rst one is LIGHT-RCK-AES. For this implementation we choose n r = 5 for the rst round and n r = 2 for the rest, and the output size of the tables to be the same as the original challenge. In this setting, the encodings of functions and the input of truth tables are at most of size 17 and polynomials have at most 44 variables.

Extrapolating the analysis on the challenge, the security level of the implementation is conjectured to be 60. The implementation would weight 2 29 bits ≈ 70 MB.

The second one is HEAVY-RCK-AES. For this implementation we choose n r = 5 for the rst round and n r = 4 for the rest. In this setting, the encodings of round functions and the inputs of truth tables are of size 25 and polynomials have 100 variables. Extrapolating the analysis once again the security conjectured would be at a security level of 80. The implementation would weight 2 36 bits ≈ 8.5 GB .

2.3

The Randomized Circuit Knitting Rationale of Design

The goal of this section is to show that the technique we used for the implementation is rather generic and can be used for SPNs in general provided the S-boxes are not too big. Let us assume that we want to implement a SPN with a keyed S-box S i and linear layer L i so that L i (S i ) is the round function. We now describe the three parts of this method: a pre-processing step, a randomized expansion step and a knitting phase.

A Pre-processing Step

As the method of implementation we propose is somewhat agnostic to the mathematical structure the SPN is based on, we can represent S i and L i as their algebraic normal form over F 2 . Then the round function can be tweaked at will into any S ′i and L ′i , such that L i (S i ) = L ′i (S ′i ). This includes adding redundancy for DFA countermeasures or articially splitting the S-box layer to increase the support of S ′i . This phase can be seen as an 'unknitting' of the circuit corresponding to the round function. If the original round function of the SPN has really small S-boxes, depending on the linear layer, one can attempt to use the composition of two rounds instead of one -more on this strategy with PRESENT will be given in the following sections.

Randomized Expansion

The rst phase, the randomized expansion phase, allows to locally increase the degree of the transformations involved, while only paying for a small exponential overhead in the substitution part of the SPN and a linear increase in the permutation part. This phase follows ideas closer to [START_REF] Bringer | White box cryptography: Another attempt[END_REF] as it allows to introduce "random" polynomials that are chosen during the compilation. The goal of these random polynomials is to mask the round functions monomials by monomials and to increase the degree of algebraic relations leading to sensible variables. The masking can be done at the level of the layer S, or directly on L. The masking at the level of S is usually easier as the support of L is usually big enough so that polynomials of these degree are not adapted to 'reasonable' sizes of implementations. The random polynomials are then carried on to the next round to ensure the correctness of the computations. To control the size of our construction, we force these polynomials to be of a certain form. At the end of this procedure, we get new ANFs that allow to evaluate the SPN. At this point the representation of our SPN is still 'unknitted' but more complex from an algebraic standpoint.

Knitting Phase

The goal of the knitting phase is to factorize the ANFs we built in the previous step to hide the randomness we introduced. It allows to increase the support and the degree of the algebraic relation between sensible variables involved in the construction. The input of this transformation is the output of the Randomized Expansion algorithm.

First, we share the ANFs of the round function so that the shares are polynomials with specic support, leading to a representation of the round function L"(S") where the support of each coordinate of S" is 'small' enough. This step is needed to avoid an exponential blow-up of encoded shares. We then group these shares by support and encode them with bijections, whose inverse are of degree 2 . This leads to the functions Σ on the AES implementation. To protect the round function, we encode these degree 2 transformations whose inverse are of degree as high as possible to get a degree 4 part. This leads to the polynomials Λ in the AES implementation. The encodings are then carried on to the ANFs of the next round. If the randomized expansion phase as been correctly parameterized, the composition of randomized expansion and knitting onto the complete RCK algorithm does lead to a local exponential growth in size in the substitution part, and a polynomial one in the 'permutation part'.

Using RCK on PRESENT

PRESENT is an example of an SPN by Bogdanov et al. [START_REF] Bogdanov | PRESENT: an ultra-lightweight block cipher[END_REF]. It is composed of 31 rounds, the block length is 64 bits and two key lengths of 80 and 128 bits are supported.

It is a lightweight algorithm that has been designed to be fast in restrained environments. According to the designers, PRESENT has been meant with the following target goals, among others:

To be implemented in hardware To be deployed in situations where moderate security levels are needed.

To be used in challenge-response authentication protocols PRESENT has not been designed with the white-box model in mind. It is almost the opposite: it has been designed for restrained hardware environments. However, in the context of authentication, asymmetries might arise that would lead to consider implementing PRESENT in the white-box model. For instance, if PRESENT is used in the hardware of an IoT object for authentication, one can have an implementation of the encryption or decryption algorithm on a smartphone, that is software based. In this context, the hardware eciency of PRESENT is still relevant, but one needs to protect the other party with the white-box model in mind. That is why we propose to see how to use the RCK framework to implement PRESENT in the white-box model.

Description of PRESENT

The round function of PRESENT is composed of AddRoundKey, an S-box layer and a permutation layer. We do not cover the key schedule and refer to its specication. An implementation of PRESENT with RCK

PRESENT S-box

We now explain how we would use the RCK framework to implement PRESENT with similar security properties to the AES.

Pre-processing To use the RCK framework on PRESENT, we start by a reprocessing step that starting from round 1, consist of composing the round function of the t-th round with the S-box of the following round. For any t ≤ 30, t = 1mod3 we dene S t,t+1 by:

R t+1 • R t (x) = P (S(P (S(x + k t )) + k t+1 )) =: P • S t,t+1 (x)
Due to the structure of PRESENT, the coordinates of the map S t,t+1 each have 16 inputs. We let round t + 2 as is. We now can represent PRESENT with an alternation of 2 round functions dened by P • S t,t+1 and P • S, for 21 total round functions. The goal of this step is to adapt the representation of the round function to expansion, and then apply the knitting phase.

Randomized expansion

We are now ready to expand round functions. For the rounds of the form P • S t,t+1 we expand the "S-boxes" S t,t+1 in the same way we did for the AES, with n r random polynomials for the S-boxes sharing a 16-bit support. As the layer P involves 4 S-boxes, the number of inputs needed for evaluating the S-box of the following round is n r × 4 + 4. The inverse of the expansion is carried onto the following S-box round, which limits the input of the next round of S-boxes to n r ×4+4. A randomized expansion step can also be taken with round of the form P • S, but it will lead to S-boxes with more than 20 inputs, which is not ideal for minimizing the size of the implementation.

Knitting Phase For the knitting phase, as the layer P mixes 4 nibbles of 4 bits together, the randomized S-boxes functions can be grouped by 4 to encode at least 16 bits together. To further augment the size of the encodings, one can share the output of the S-boxes to articially introduce a linear layer that is not only a bit permutation.

Once the size of the encodings of the S-boxes are decided, the output encoding is xed by the size of the S-boxes of the next round.

Synthesis Following this method, the implementation is composed of tables Σ that have at least 16 bits inputs and depend on more key-bits than the original round function and the secret polynomials and encodings introduced. The composed degree-With these similarities in mind, the security of such an implementation depends on the same algebraic conjectures.

Conclusion of Part II

Implementing the AES is one of the rst goals established by the white-box community and is still far from being closed.

As we have seen from the short state-of-the-art study, attackers are stronger than designers by a huge margin. This is partly due to the impressive eciency of the automated attacks, but also due to the structural vulnerabilities of the methods used, namely the internal encoding rationale of design.

In the new design we propose, we try to push this rationale of design by using a polynomial representation to produce an implementation that is resilient to algebraic attacks such as LDA or the BGE attack. The conjectured security of our implementation is based on conjectures on the algebraic degree of the relation between the usual target values of attackers and the values computed by our implementation. We also motivate the study of our technique by publishing a challenge implementation.

We also abstract the design of our implementation as the RCK framework for SPNs and describe how to implement PRESENT to support the versatility of this framework.

As following works, it would be interesting to investigate whether the algebraic countermeasures we propose can be mixed with countermeasures specic to other attacks, such as DCA, in the same spirit as the masking techniques of [START_REF] Biryukov | Attacks and countermeasures for white-box designs[END_REF] can be mixed with linear masking for resilience against DCA and LDA.

Chapter 1 Introduction to Multivariate Cryptography and HFE

In this chapter, we propose a short introduction to multivariate cryptography, its usage, the problems it is based on and the usual attack techniques. We then shortly explain the "big eld" trapdoor rationale and extensively describe one of its well known element, the Hidden Field Equation (HFE) one-way trapdoor function. We then precise the state of the art of attacks against HFE specically

Introduction to Multivariate Cryptography

Multivariate cryptography is a part of public-key cryptography that relies on the hardness of solving polynomial equations. This rationale of design has been initiated by algorithms such as C * in the 80's and then followed by a lineage of algorithms such as HFE [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF] or UOV [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF] and their descendants.

Among the original appeal of this rationale, one can note its eciency for short signatures and its exibility of design as reected by the high number of techniques used to repair broken candidates or design new ones. However, multivariate cryptography is also one of the rare promising candidates for post-quantum cryptography, together with hash, code and lattice-based cryptography. Indeed, while polynomial time quantum algorithms such as Shor's algorithm threaten public-key cryptography based on factorisation or discrete logarithm, multivariate cryptography is conjectured to stand against quantum opponents. This is why multivariate schemes have been proposed to the post-quantum NIST competition, for instance GeMSS (an HFE variant).

Even if cryptanalysis showed that the parameters for these candidates were too optimist, the latest round of selection was gifted with new submitted multivariate algorithms such as VOX and PROV, showing the everlasting exibility of multivariate cryptography.

Multivariate Cryptography Rationale

In Public-Key Multivariate Cryptography, the public key is given as a set of m polynomials (P) = (P 1 , . . . , P m ) in n variables, of small degree d over a small nite eld F.

Most of the time, d equals 2 and 20 ≤ n ≤ 300:

(P)      P 1 (x 1 , . . . , x n ) • • • P m (x 1 , . . . , x n )
In practice, this system is structured: a central system P ′ : F n → F m called the central map is hidden by two ane secrets T : F m → F m and S : F n → F n to form a system P dened by:

P = T • P ′ • S
The private key is then dened by the set (S, P ′ , T ). The system P ′ is built to be easy to solve, and the system P hard to solve. We now explain how to use this public-key to build encryption and signature algorithms.

Encryption and Decryption For encryption, plaintexts are elements of F n and ciphertexts are elements of F m . Using the public key, a message (x 1 , ..., x n ) ∈ F n is encrypted by : c = (c 1 , ..., c m ) = P(x 1 , ..., x n )

In this context, the public key is the encryption algorithm. This encryption process is quite fast as evaluating such system of polynomials can be made in O(mn 2 ).

For decryption, one need to use the trapdoor, i.e to use the secret-key (S, P ′ , T ). For any c ∈ F m ∩ Im(P), one can inverse map by map the public key:

x = S -1 • P ′-1 • T -1 (c)
Note that c has to be in the image of P to have a solution and that we must have m ≥ n to hope for a unique solution.

s = S -1 • P ′-1 • T -1 (h(x))
This can only be done with the knowledge of the trapdoor. If h(x) is not in the image of P, one can pad x with a counter until its hash is in the image of P. To verify the signature, we simply evaluate P on s and compare it to h(x):

P(s) ? = h(x)

The PoSSo Problem

For this rationale to work, the public key P needs at least to be one-way. Indeed, if one can solve y = P (x), it means for instance that an attacker can forge signatures or decrypt. The hardness of solving polynomial equations is then a requirement for multivariate cryptography.

Denition 26. PoSSo and MQ Problems

Let n, m, d ∈ N * with d ≥ 2 and F a nite eld. The Polynomial System Solving problem is dened as follows.

Given a system of polynomials (P)(P 1 (x 1 , . . . , x n )P m (x 1 , . . . , x n ) in F, nd an n-tuple (x 1 , ..., x n ) ∈ F n such that:

(P)      P 1 (x 1 , . . . , x n ) = 0 • • • P m (x 1 , . . . , x n ) = 0
When d = 2 we call this problem Multivariate Quadratic (MQ).

In general, this problem is known to be NP-Hard [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF], which explains the initial interest for this rationale. However, with a complete random system, operations such that signature or decryption are impossible -that is, nding preimages of y through P -especially because of the hardness of PoSSo.

The Isomorphism of Polynomials Problem In the context of multivariate cryptography, nding the secrets S and T given (P) and (P ′ ) has been abstracted as the Isomorphism of Polynomial (IP) problem in [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF]. It started a line of work such as [START_REF] Bouillaguet | Practical cryptanalysis of the identication scheme based on the isomorphism of polynomial with one secret problem[END_REF][START_REF] Macario-Rat | New insight into the isomorphism of polynomial problem IP1S and its use in cryptography[END_REF][START_REF] Patarin | Improved algorithms for isomorphisms of polynomials[END_REF][START_REF] Perret | A fast cryptanalysis of the isomorphism of polynomials with one secret problem[END_REF] to better understand the security of general multivariate schemes.

There exist several families of multivariate schemes, corresponding to several choices for the system P ′ , such as C * [82], HFE [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF], Rainbow [START_REF] Ding | Rainbow, a new multivariable polynomial signature scheme[END_REF] or UOV [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF]. Their security depend on the internal polynomial and "perturbations" added to the system. If in general, solving a set of quadratic equations over a nite eld is an NP-hard problem for any nite eld it is however dicult to obtain a proof of security for multivariate schemes: since the system (P ′ ) has to be easy to solve, it is never random, and neither is (P) (since (P) is obtained by linear changes of variables from (P ′ )).

Trapdoor Techniques

The Big Field Trapdoor For this trapdoor technique, let us assume that we have F a map built on an extension F q n of a nite eld F q . Let us further assume that the map F can be easily inverted over F q n , think of a bijective monomial for instance. If π denotes an isomorphism from F q n to F n q , we then have the following commutative diagram :

F n q F n q F n q F n q F q n F q n S T F π π P
The public key is dened by :

P = T • π -1 • F • π • S
and the trapdoor is computed with the knowledge of (S, T ) and the big eld representation of F . This trapdoor is the basis of schemes such as C * [82] and HFE [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF].

The Unbalanced Oil and Vinegar Trapdoor The Unbalanced Oil and Vinegar (UOV) trapdoor is the basis of the UOV [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF] scheme and is used in other designs such as Rainbow [START_REF] Ding | Rainbow, a new multivariable polynomial signature scheme[END_REF]. This trapdoor needs two distinct sets of variables of size o and v such that n = o + v. We note the set of oil variables O and the set of vinegar variables V . Consider now a central map whose coordinates are of the form:

(x,y)∈O×V a x,y xy + (x,y)∈V ×V b x,y xy + x∈O∪V c x x + d
The idea is that, using map such as these, if we x vinegar variables, we get linear equations in oil variables. The system of equation can then be solved.

The security of such trapdoor is based on the fact that after a composition with the secrets S and T , distinguishing oil and vinegar variables is dicult. From these remarks, it seems that studying cryptosystems based on other rationals and mathematical structures can oer new design spaces. Even if some of them, such as lattice-based algorithms that need randomness to be secure, might be burdensome, others may oer new design avenues with new techniques due to the mathematical structures they are based on. This is why this part will be dealing with white-box techniques for multivariate cryptography.

A rst selling point is that polynomial representation helps to diuse key bits into the implementation and the decomposition of the public key is already taken into account by the black-box security study. In a sense, multivariate cryptography is one of the closest designs in the black-box model that takes white-box aspects in consideration, due to the nature of its public key. Also by using structured trapdoors, especially for big eld cryptosystems, a designer can take advantage of the vector space and the eld structure to use new algebraic techniques for implementations.

Usual Attack Techniques Against Multivariate Cryptography

In this section, we recall the main attack strategies that are specic to multivariate cryptography. This section is just a brief overview and we will detail them against the algorithms we study later.

Direct Inversion Attack

In a direct inversion attack, the goal of the attacker is to break the trapdoor one-way property of the public-key, hence breaking the PoSSo problem. The most common and ecient method is to use Gröbner bases. We do not detail the theory of how to compute them, and refer to [START_REF] Cox | Ideals, varieties, and algorithms -an introduction to computational algebraic geometry and commutative algebra[END_REF] for the curious reader. The algorithms to compute these bases have been improved over the years, the most powerful ones being Faugère algorithms F4 [START_REF] Faugére | A new ecient algorithm for computing gröbner bases (f4)[END_REF] and F5 [START_REF] Faugère | A new ecient algorithm for computing gröbner bases without reduction to zero (f5)[END_REF]. and the hybrid approach of [START_REF] Bettale | Hybrid approach for solving multivariate systems over nite elds[END_REF].

Rank Attacks

The goal of Rank Attacks is to abuse the structure of the central map to recover the secret-key. More precisely, it ties the key recovery to an instance of the MinRank problem [START_REF] Courtois | Ecient zero-knowledge authentication based on a linear algebra problem minrank[END_REF]. A MinRank instance is dened by a set of matrices. To solve a MinRank problem, one needs to nd a linear combination of the matrices that minimize the rank.

In the context of multivariate cryptography, it has been rst used in the Kipnis-Shamir [START_REF] Kipnis | Cryptanalysis of the HFE public key cryptosystem by relinearization[END_REF] attack: this attack is based on the fact that the initial system P ′ is often of low rank as a quadratic form. Solving a MinRank instance based on the equation of P allows to recover the map T , and the map S is recovered by solving an overdened system of linear equations.

The Hidden Field Equation Familly

We now describe HFE in more details and review the most powerful attacks known against it: the Gröbner bases message recovery attack and the key-recovery rank attacks are especially the attacks that are considered in the black-box model to test whether an HFE instance can be used to build secure primitives.

Description of HFE

First described by Patarin in [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF], the HFE scheme is a direct descendant of C * [START_REF] Matsumoto | Public quadratic polynominal-tuples for ecient signature-verication and message-encryption[END_REF][START_REF] Matsumoto | A class of asymmetric cryptosystems using obscure representations of enciphering functions[END_REF]. This is one of the 'big eld' algorithms, using polynomials that are of degree 2 over F q . For any positive integers n and D ∈ N let F ∈ F q n [X] be dened by:

F (X) = 0≤i<j<n q i +q j ≤D a i,j X q i +q j + 0≤i<n q i ≤D b i X q i + c
where the a i,j , the b i and c are elements of F q n . As the integer D bounds the actual degree of any such F , we call D the degree of the HFE instance. As the quantity ⌈log q (D)⌉ will be important in the description of attacks, we set d = ⌈log q (D)⌉

The secret key is the list of such polynomial F and a couple of ane transformations (S, T ) ∈ AF F n (F q ). We note it (S, F, T ). We remark that F is eciently invertible on its image due to the Berlekamp algorithm if D is not too big and that S and T are trivially invertible as long as q n is not too big.

To compute the public key, let us x a basis (e 1 , ..., e n ) ∈ (F q n ) n of F q n over F q . It induces an isomorphism π from (F q ) n to F q n such that π(x 1 , ..., x n ) = n i=1 x i e i . The public key P is the map from F n q to F n 2 dened by:

P = T • π -1 • F • π • S
The public key is represented by the n coordinates of P : for each 0 ≤ i < n we note its i-th coordinate P i ∈ F q [x 1 , ..., x n ].

Perturbations

Usually, a "nude" instance (that is, an instance without perturbations) is not enough to resist the state-of-the-art attacks. That is why perturbations were introduced to reinforce these nude instances, while keeping the trapdoor property. We describe only the ones that are useful to us in this thesis.

The Minus (-) Perturbation Let a be an integer and a < n. The minus perturbation, denoted by -, simply consists in keeping secret some of the n polynomials (P 1 , . . . , P n ). Only n -a are made public and will be used to check the validity of the equations. We formalize it by transforming the full ane transformation T into T -: F n q → F n-a q which is the (n -a) rst coordinates of the full transformation T . Then, messages of size n -a can be signed by selecting the a last elements in F q at random and signing with the n elements obtained. Note that these last a elements must be random; otherwise the last a polynomials can be interpolated.

A HFE scheme with the perturbationis called HFE -with public key

P = T -• π -1 • F • π • S
The Projection (p) Perturbation The projection variant p of HFE has been reinvestigated recently to enhance the resilience of the public key against support minor modeling attacks ( [START_REF] Øygarden | On the eect of projection on rank attacks in multivariate cryptography[END_REF]). In this variant, the map S is not a bijective ane map over F n q , but an ane map of full rank pS from F n-p q to F n q where the integer p is the projection parameter. With such map S, there is a probability 1 q p that an element y ∈ F n q has no preimage through the internal map. This means that there is a q p

Attacks on HFE variants

In this section, we recall the best attacks on HFE instances, that is, the best known message-recovery attacks and key-recovery attacks. The complexity of these attacks will help us benchmark our instances for the white-box implementations later.

Message Recovery Attacks

The idea of a direct message recovery attack is to invert the polynomial system dened by the public key for a xed value y. To that extent Gröbner bases are the best tools available to date. The computation of these bases have greatly been improved since Buchberger original discovery, with new algorithms to compute them such as J.-C.

Faugère F4 and F5 algorithms [START_REF] Faugère | A new ecient algorithm for computing gröbner bases without reduction to zero (f5)[END_REF].

To solve a polynomial system of n equations with n unknowns with F5, the complexity is proved to be [START_REF] Bardet | On the complexity of the F5 gröbner basis algorithm[END_REF]:

O n + d reg d reg ω
where 2 ≤ ω ≤ 3 is the linear algebra constant, and d reg is the degree of regularity of the polynomial system. Roughly speaking, the degree of regularity is the maximum degree that is reached during the Gröbner basis computation. As the complexity is exponential in d reg , it is really important to know how to compute it for practical HFE instances.

For HFE instances, the degree of regularity is not well understood theoretically, but it has been well studied experimentally. Due to the structure of the equations over F q n , it has been shown in [START_REF] Faugère | Algebraic cryptanalysis of hidden eld equation (HFE) cryptosystems using gröbner bases[END_REF] that d reg behaves as log q (D), whatever value is chosen for n. This is highly dierent from what has been theoretically investigated for random systems, where d reg is supposed to be close to n ( [START_REF] Bardet | On the complexity of the F5 gröbner basis algorithm[END_REF]).

Degree of Regularity for Perturbed HFE For the pHFE -variant, this degree of regularity is conjectured to behave as d + a -p + 7 3

Experimentally, this linear dependence on d + a has been observed in works such as [START_REF] Petzoldt | On the complexity of the hybrid approach on hfev[END_REF] or the GeMSS specication [START_REF] Casanova | GeMSS[END_REF]. The linear dependence in -p has been conjectured by Patarin et al. in [START_REF] Patarin | Ultra-short multivariate public key signatures[END_REF].

For the HFE +perturbation, the public-key can be reduced to a system of equations with degree of regularity conjectured in [START_REF] Faugère | A new perturbation for multivariate public key schemes such as HFE and UOV[END_REF] :

(q -1)(d + a + t -ϵ) 2

where ϵ = 1 if q is even, ϵ = 0 otherwise.

Key Recovery Rank-Attacks

To perform a key-recovery on HFE and its variants, the most ecient attacks to date are the Kipnis-Shamir attacks. In their paper [START_REF] Kipnis | Cryptanalysis of the HFE public key cryptosystem by relinearization[END_REF], A. Kipnis and A. Shamir show that nding equivalent keys to an HFE instance can be done by solving a particular instance of the MinRank problem [START_REF] Buss | The computational complexity of some problems of linear algebra[END_REF]. We note C R (n, d) the complexity of this attack.

Since then, variations of the attack have been thoroughly studied. Especially, variations with minor modeling and support minor have been the most successful.

Recently, Ding et al. [START_REF] Tao | Improved key recovery of the hfev-signature scheme[END_REF] proposed an ecient use of support minor modeling. This line of work was continued by [START_REF] Øygarden | On the eect of projection on rank attacks in multivariate cryptography[END_REF] and [START_REF] Baena | Improving support-minors rank attacks: Applications to gisplaystyle emss and rainbow[END_REF] to provide a key-recovery attack that breaks any small HFE instances such as RedGeMSS128 [START_REF] Casanova | GeMSS[END_REF]. Especially, the authors of [START_REF] Øygarden | On the eect of projection on rank attacks in multivariate cryptography[END_REF] show that a key-recovery for HFE can be made with minor modeling in:

O n 2 2d + 1 d + n 2d + 1 d 2 ω
An improvement can be made when there exists 2d + 1 ≤ n ′ ≤ n -a such that n ′ d ≥ n, showed by the author of [START_REF] Baena | Improving support-minors rank attacks: Applications to gisplaystyle emss and rainbow[END_REF] and the complexity is then:

O n ω n ′ d ω
This means that key recovery is exponential in d = ⌈log 2 (D)⌉, but polynomial in n. More details on the links between the parameters regime and the complexity of the attack can be found in [START_REF] Øygarden | On the eect of projection on rank attacks in multivariate cryptography[END_REF].

The Projection Perturbation and Support Minor Modeling Attacks In [START_REF] Øygarden | On the eect of projection on rank attacks in multivariate cryptography[END_REF], the authors analyse the complexity of rank attacks on pHFE variants. They prove that a pHFE instance with internal polynomial of degree D and p projected variables is equivalent to an HFE instance with internal polynomial of degree 2 p × D. Experimentally, the support minor modeling attacks on pHFE instances can be made with

d ′ = d + p.

Chapter 2 Ane Multiple Implementation of HFE

In this chapter, we detail our implementation technique of the HFE trapdoor. We adapt it to some perturbations of HFE and propose a challenge implementation. Finally, we conduct a security analysis of our construction in the plain white-box model.

2.1

The Technique

Ane Multiple Attacks

The starting point of our construction is the concept of ane multiple. It was introduced by Patarin in [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF] to generalize an inversion attack on C * to HFE. The central idea of this attack is that for any polynomial F ∈ F 2 n [X] there always exists a polynomial A(x, y) ∈ F 2 n [X, Y ] that is F 2 -linear in x and a multiple of the polynomial P (x) + y. This means that if y = F (x), then A(x, y) = 0.

Denition 27. Let F ∈ F 2 n [X]. The polynomial A(x, y) ∈ F 2 n [X, Y ] is said to be an ane multiple of F if A(x, y) = 0 mod F (x) + y and A is F 2 -linear in x.
The goal of the original ane multiple attack is to recover A via interpolation. When A is known to an attacker, they can plug any value of y to get a linear system in x of reasonable size they can solve to eciently sign without using the structure of the equation in F 2 n .

To further detail this attack, let us dene the ane degree d a of an ane multiple: Denition 28. Let A be an ane multiple of F (x) + y, that is, A(x, y) = a + i.e. the maximum Hamming weight of the monomials in y in the polynomial A(x, y).

We then remark that the composition by these ane transformations S and T leads to a new ane multiple that has the same d a degree. Now, to start the attack, just notice that A(x, y) is composed of about n × σ(n, d a ) unknown coecients over F n 2 , where σ(n, d a ) is the number of monomials in at most n variables in degree d.

We will go through this in more details in Section 3. This means that with enough queries (x, P (x)), the unknown coecients of A are the solution of a linear system of n equations with n × σ(n, d a ) unknowns that we can obtain with a Gaussian reduction. This gives us an attack, if F is known to have such ane multiple, in space n 2 × σ(n, d a ) and in time (n × σ(n, d a )) ω .

This attack is quite inecient in general as the degree d a is usually quite high. Also, it is well known that the perturbation minus (-) protects from ane multiple attacks [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF]. It is important to remark that the cost of computing an ane multiple of F (x) + y is easier when the private key (S, F, T ) is known than when only the public key P is known, especially when modiers like minus are used. This means that an ane multiple might be accessible with the knowledge of (S, F, T ) but not with the knowledge of P only.

Rationale of the construction

The starting point of our construction is to use the ane multiple relation over F 2 as an alternative way to inverse a public key P : the ane multiple will be our whitebox implementation. Indeed, if we take y = F (x) in the image of F , computing x knowing an ane multiple A(x, y) boils down to plugging y onto the expression and then solving linear system of the size of x. If the ane multiple is of a reasonable size, computing x is as easy as evaluating the ane multiple in y.

Construction for nude Public-Keys

Computing the ane multiple

We now detail the existence of ane multiples and expose an algorithm to eciently compute them if possible.

To prove the existence of ane multiple, let us assume that D = deg(F ) is such that D < n and let us consider the vector space F 2 (y)[x]/ (P (x)+y) of dimension D = deg(F ) over F 2 (y). Now, the (D+1) F 2 -linear polynomials (1, x 2 0 , x 2 1 , ..., x 2 D-1 ) are linearly dependent: ∃ a, a o , ..., a D-1 ∈ F 2 (y) , a + D-1 i=0 a i x 2 i = 0 mod (P (x) + y)

To compute the coecients a k , we can use the reductions of the monomials x 2 i modulo F (x) + y:

∃ b i,0 , ..., , b i,D-1 ∈ F 2 (y) , x 2 i = D-1 j=0 b i,j x j mod (P (x) + y)
We then reinject into the previous equation:

a + D-1 i=0 a i D-1 j=0 b i,j x j = 0
This clearly translates into the linear system:

     1 b 0,0 • • • b D-1,0 0 b 0,1 • • • b D-1,1 . . . . . . . . . . . . 0 b 0,D-1 • • • b D-1,D-1      ×      a a 0 . . . a D-1      =      0 0 . . . 0     
We can then solve this system with Gaussian reduction in F 2 (y). Multiplying this relation by the LCM of the a ′ k s denominators leads to an ane multiple polynomial A(x, y). We now note a k ∈ F 2 [y] the polynomials in y obtained that way. This proves the existence of an ane multiple, and gives us at the same time an algorithm to compute it. Remark: We do not claim the uniqueness of the ane multiple. It is indeed clear that considering D other F 2 -linear monomials leads to a similar relation, but it is not clear how it aects the coecients a k obtained.

The white-box construction

We now detail the construction of our white-box compiler and how to use it in practice.

As we mentioned earlier, we focus on implementing the P -1 functionality as it is enough to guaranty unbreakability and incompressibility (see Section 4.4).

) = A i (S(x 1 , ..., x n ), T -1 (y 1 , ..., y n ))
Produce a code that partially evaluates the Ãi over the y 1 , ..., y n Produce a code that compute a pre-image of the vector 0 through linear application given by the partial evaluations of the Ãi , and output "NONE" if no solution can be found.

Produce a code that check if the message to be signed is in the image of P .

Concatenate the produced codes to get the whole white-box implementation WBHFE (S , F , T ).

Dimensioning of the construction

The study of size of our solution boils down to two points: the computation of the multiple A over F 2 n and the size of its coordinates Ãi over (F 2 ) n . Indeed, the code size needed to perform evaluations of polynomials and Gaussian inversion is negligible. For the representation of polynomials, we use the so-called sparse representation to get the smaller size possible. The size analysis is of course to be linked with the white-box incompressibility which is detailed later on.

Cost of computing an Ane Multiple.

To compute the coecients b i,j , we have to go through the reduction of the monomials x 2 i modulo F (x) + y, with 0 ≤ i < D. Due to the reduction modulo F (x) + y, the degree of b i,j can be as big as 2 D and the b i,j can have up to 2 D monomials. The last part of the algorithm only solves a D × D system, leading to a worst case complexity if the polynomials b i,j are dense:

O(M (n, 2 D )D ω )
where M (n, 2 D ) is the cost of multiplying polynomials of degree 2 D with coecients of size n. This means that with D = O(n), computing this relation is usually impossible. However, we will use it with smaller polynomials than in usual HFE, i.e. D = O(1).

Size and Running Time of the WBHFE implementation.

For the rest of the construction, let us introduce the ane degree of F . The ane degree d a is the greatest Hamming weight that appears in the description of the ane multiple A over F 2 . Denition 29. Let A(x, y) = a+ D-1 i=0 a i x 2 i with a, a o , ..., a D-1 ∈ F 2 [y] , if Mon(a k ) is the set of the monomials of a k we dene d a the ane degree of A by:

d a := max k max m∈Mon(a k ) HW (deg y (m)) .
Over F 2 , d a + 1 is the highest degree of the monomials encountered in the expression of A(x, y). Indeed, A(x, y) is linear in the x i but of degree d a in the y i .

If we note σ(n, d a ) to be the number of monomials in at most n variables of degree at most d a , this means that we have about n × σ(n, d a ) coecients over F n 2 needed to compute a coordinate A i of A(x, y). When we compose by S and T to get Ã, the overall degree does not change since S and T are ane transformations. This means that each coordinate Ãi is composed of at most n × σ(n, d a ) monomials since S is a map from n bits to n bits.

As we are computing n coordinates, a lot of monomials will be shared in the expressions of the Ãi and it is more ecient to compute all the monomials that appear in these expressions, and then sum them. Since we want to only evaluate these polynomials in y i to get a linear system in x i , to then inverse it, we will represent the n polynomials Ãi as a matrix of polynomials over the y i . This transformed expression is of the same size but will be more suited to our goals. To do so, we dene the polynomials Ãi,j (y 1 , ..., y n ) by the expression:

Ãi (x 1 , ..., x n-p , y 1 , ..., y n ) = n j=0
Ãi,j (y 1 , ..., y n ) × x j Key elements of WBHFE: We can now precisely state the size of our construction. Since we will need to use great values of n, we will say in our size study that code size are 'negligible' if they are small -that is few kB. Our construction is composed of:

A code that evaluates, on an input m = (m 1 , ..., m n ) of size n, all the monomials of at most degree 2 in the m i . As we compute all the monomials, a generic code can be made. This means that this part is negligible in code size. However, this code will produce σ(n, d a ) bits during its execution. We will also suppose -without loss of generality -that these monomials are computed in an ordered way, with a label from 1 to σ(n, d a ).

The n × n les F ile i,j i,j < n for which the k-th bit of the le F ile i,j is 1 if the k-th monomial computed by the precedent code is in the expression of the polynomial Ãi,j . These les are the heaviest part of our implementation: their size is σ(n, d a ) bits. As we need each of the coordinates, the whole size is n 2 × σ(n, d a ). We divide the n 2 polynomials into n 2 les so we can load them one at a time during evaluation, with potential for parallelization.

A code that computes the evaluation of Ãi,j (m 1 , ..., m n ) given the evaluations of the monomials of degree 2 in m i and the le F ile i,j . To do so, one just has to go through the le F ile i,j and sum the corresponding monomials as they go. This code is negligible and can load one le F ile i,j at a time.

A code that computes the n by n binary matrix M at à such that (M at Ã) i,j = Ãi,j (m 1 , ..., m n ). This code is also negligible.

A code that computes a solution for the linear system M at ÃX = 0, X = (x 1 , ..., x n ) T . This can be done by Gaussian elimination. Hence, it is negligible.

A code that checks whether m was in the image of P , i.e. if P (x) = m. This can be done with the public key, whose size is n × σ(n, 2). The rest of the code is negligible.

Size and Time This means that the code is composed of the n 2 F ile i,j for n 2 × σ(n, d a ) bits, the matrix M at à of n 2 bits, the public key of n × σ(n, 2) bits, and some negligible code. The full size is then:

n 2 × σ(n, d a ) + n 2 + n × n 2 + negl ≈ n 2 × σ(n, d a )
For the rest of the paper we will dene:

σ W B := n 2 × σ(n, d a )
Regarding time, it is interesting to note that the computation of P -1 can be parallelized. Indeed, the n × n polynomials in the les F ile i,j can be computed independently. When the polynomials are evaluated, there is only a small n by n system to solve. If the evaluation of polynomials in the les F ile i,j is parallelized n p < n 2 times, the time for inverting P -1 is:

τ W B := n ω + n 2 n p × σ(n, d a )
Discussion on the ane degree.

As seen in the previous section, the size our construction is exponential in the ane degree d a , so it is important for us to understand its variations depending on F .

As a consequence of the algorithm we used to prove the existence of a multiple ane, we know that the degrees involved in the computation of the multiple are upper bounded by 2 D where D is the degree of F . The ane degree is then bounded by D but this bound is clearly an overestimate.

Through our experimentation we found that polynomials with degree of at most degree 12 can reach any ane degree ranging from 2 to 6. These experiments show that most of small d a can be reached and that there are many polynomials reaching these values. We give example of some families of these polynomials with d = 3 Besides our experiments on low degree polynomials, there are some examples that are really far from any expected bound. For instance, the Dobbertin polynomial x 2 m+1 +1 + x 3 + x (see [START_REF] Dobbertin | Almost perfect nonlinear power functions on gf(2n): The welch case[END_REF]) has a multiple ane of ane degree 3 over F 2 2m+1 for every value m ([88]), which is in general really dierent from the observed values.

Using Perturbations

Usually, nude HFE instances are not sucient by themselves to get reasonable blackbox security. The goal of this section is to explain how we can turn the implementation of a nude HFE instance into a perturbed one. We will focus on three of them: p, -, and +. For each perturbation on the public-key, we associate a perturbation or a list of perturbations between parentheses (p corresponding to (p) for instance) that are applied on the ane multiple of the nude HFE instance to match the perturbations made to the public-key.

The p Perturbation

To transform a nude public key to a one perturbed with p, one only needs to replace the bijective ane application S : F n 2 → F n 2 with an ane transformation of full rank S p : F n-p 2 → F n 2 for a small integer p.

This replacement can be made in the ane multiple representation by also replacing S by S p , so the perturbation is compatible with the ane multiple structure.

For a HFE instance perturbed with "p", we associate its ane multiple where S is replaced by S p . When we use this perturbation en the ane multiple, we note that à is perturbed by (p).

The -Perturbation

To transform a nude public-key to a one perturbed with -, one needs to remove some coordinates from the public-key. Let a be the number of equations removed. To sign with the private key, one needs to select at random these last a coordinates, and then proceed to the normal signing procedure.

The fact that the a last coordinates are random or at least secret is important to avoid any reduction to a nude public-key. Indeed, if the values of these coordinates are known for each signature produced, an attacker can then interpolate them and completely remove themodier from the key: the last a coordinates cannot be freely chosen in the white-box model.

For instance, one could try to replace the last a coordinates of y with any linear combination of the rst n -a coordinates. Then, the attacker knows that the missing polynomials in x are equal to a linear application in y and can then interpolate them from some couples message-signature (even in the black-box model). Note that, in practice, the choices we can make here are limited. If we take polynomials of degree 2 in the rst n -a coordinates for instance, the degree of the ane multiple increases. If these coordinates depend on x the ane multiple is not linear in x anymore.

If the HFE instance is itself resistant enough in the white-box model, one possibility is to let the last a coordinate free to be chosen at random for signing: For a HFE instance perturbed with "-", we can associate its ane multiple without any modication from the nude one, but the last a coordinate of the signature are taken at random. When we use this perturbation on the ane multiple, we note that à is perturbed by (-, 1).

Remark : Even if the ane multiple is not modied we can remark that in the black-box model, the last a coordinate are random so the reduction to an HFE instance without minus is not possible in the black-box model. This means that the (-, 1) perturbation on the ane multiple does not carry the security from minus in the white-box model but keeps it in the black-box model. More on the security of (-, 1) in section 4.

A direct consequence of the previous remark is that theperturbation is not directly compatible with the ane multiple structure. To partially go around this problem, we propose a countermeasure. To eciently interpolate the missing equations of the public key, the attacker needs to know that the a last coordinates depend from x and y in a simple way. We will then try to hide these coordinates in a single special ane multiple.

The + Perturbation

To transform a nude public key to a one perturbed with +, one needs to change the central polynomial F into F + Q where Q is quadratic over F 2 and of high degree over F n 2 such that ∀x ∈ F n 2 , Q(x) ∈ V , where V is a small vector space of dimension t. Similarly to the "-" modier, the value of Q(x) for any message y cannot be known to an attacker, otherwise Q can be interpolated. That is why the + perturbation is not directly compatible with the ane multiple construction. Also, it is not possible to propose a perturbation close to (-, 1) as the values of Q cannot be left to be freely chosen.

We propose the same kind of perturbation as (-, 2) to not reveal the values of Q(x). To do so, let us take any integer m s > 0 and split Im(Q) = ∪ ms i=1 V i where #V i = δ i ≥ 2. We set V i = {v i,1 , ..., v i,δ i }. Now consider the polynomials:

H i (x) = δ i j=1 (y -F (x) -v i,j )
A composite ane multiple C i (x, y) of H i in unknowns x and y and xed v k can produce signatures for which the value of Q can be any v i,j . An attacker can then at most guess that the missing coordinates lie in a set of δ k values to interpolate.

For a HFE instance perturbed with " +", we can associate the collection of the ane multiples of the H i . When we use this perturbation, we note that the implementation is perturbed by ( +) with parameters (δ 1 , ..., δ ms ).

Remark : In the same spirit as the remark on the (-, 2) perturbation, it is possible to not use the whole collection of the H i , but only few, or one of them. More details on this technique will be given in section 5.

Combining Perturbations

Usually, multiple perturbations are used on a nude-HFE to achieve satisfactory security parameters be it pHFE or the more recent HFE +-.

For our white-box implementation, we proceed similarly, although the compatibility depends on the perturbation used. For instance, the (p) and (-, 1) perturbation are easily compatible with ( +) but (-, 2) and ( +) needs more a subtle adaptation to work together: instead of splits of F a 2 and Im(Q), one needs to work with a split of F a 2 × Im(Q) and work with ane multiples of products of polynomials of the form (y + u -F (x) -v), with u ∈ F a 2 and v ∈ Im(Q).

In section 5, we detail more on the compatibility of perturbations for ane multiples in a case by case basis on the implementation.

Security analysis

In this section, we dene the white-box security notions of unbreakability and incompressibility for public-key signature algorithms. We then analyse the security of our implementation designs for these notions. For the rest of this section we suppose that

A is an ane multiple of F or a composite ane multiple with respect to perturbations of section 3.5.

We will study the unbreakability and incompressiblity of our construction. We recall that for unbreakablility, studying the unbreakability of the one-way function is sucient (part I, chapter 1).

Attack by Reduction to a Weaker HFE Instance

This paragraph only deals with HFE implementations with perturbations. If perturbations are used on an implementation (section 3.5), one idea to perform an attack is to try to remove the perturbation on the ane multiple construction, in the same way attackers try to remove perturbations on public-keys for attacks in the black-box model. We describe such reductions for some of the perturbations described in section 3.5.

Reduction for (-,1) If we have an implementation perturbed with (-,1), we can remove the perturbation -on the public-key by recovering the missing coordinates. We can x the last a coordinates to any constant and gather enough signatures to solve a linear system with the coecients of the monomials of our missing coordinates as unknowns. Experimentally, this allows us to recover vector space of dimension a that contains these equations, which is sucient to recover an equivalent HFE public key.

Since there are n 2

unknowns, the cost of this attack is O(n 2ω + n 2 × τ W B ).

Remark 1: The time τ W B can be increased by other used perturbations, and needs to be taken into account for concrete security analysis.

Reduction for (-,2) With the (-,2) perturbation, the a last coordinates are not known: they are grouped by sets of ϵ i unkown values. Indeed the ane multiples B i of the polynomials G i only provide a signature if the last coordinates are in U i . If the same attack as for (-,1) cannot be used, we can still know that the signatures from B i will satisfy:

ϵ i j=1 (Π a (P (x)) + u i,j ) = 0
where Π a is the projection onto F a 2 . This product can then be interpolated by gathering signatures, using the same method as in the reduction for (-, 1). Then, a recovery of Π a (P (x)) can be attempted. In our setting, the exact values u i,j are unknown.

To the best of our knowledge, recovering Π a (P (x)) can only be made by factoring ϵ i j=1 (Π a (P (x)) + u i,j ) = 0, which is hard for any instance we will use later.

Remark 2: Note that the same polynomial relation can be recovered for any HFE - instance in black-box for ϵ i = 2 a . This means that the security problem we have identied is similar to recovering the missing equations in a HFE instance for small values a.

Reduction ( +) For the ( +) perturbation, the same strategy as (-,2) can be used.

Indeed for the ane multiples C i of the polynomials H i the only possible values of Q(x) are in V i . The signatures from B i will satisfy:

δ i j=1 (Q(x) + v i,j ) = 0
This product can then be interpolated by gathering signatures using the same method as for the reduction for (-, 1). Then, a recovery of Q(x) can be attempted using the same method as for (-, 2), except this time, the entire set Im(Q) is unknown.

This reduction is hence similar than the (-.2) reduction.

Remark 3: Note that these equations can be gathered for any HFE + instance in black-box for V i = Im(Q). This means that any algorithm solving this problem if #V i = 2 t can break the corresponding HFE + instance. Even if this perturbation is young, no attack of this kind has been reported by the authors of [START_REF] Faugère | A new perturbation for multivariate public key schemes such as HFE and UOV[END_REF] which conrms our security analysis.

The Implementation as a (d a + 1)-IP1S Problem

To analyse unbreakability and incompressibility directly on the ane multiple, we rely on two properties of the polynomials describing our white-box implementation. The rst will be the key recovery of the underlying (d a + 1)-IP1S (Isomorphism of polynomials with one secret whose internal polynomial is of degree (d a + 1)) instance, a problem that has been studied in papers such as [START_REF] Bouillaguet | Practical cryptanalysis of the identication scheme based on the isomorphism of polynomial with one secret problem[END_REF][START_REF] Macario-Rat | New insight into the isomorphism of polynomial problem IP1S and its use in cryptography[END_REF][START_REF] Patarin | Improved algorithms for isomorphisms of polynomials[END_REF][START_REF] Perret | A fast cryptanalysis of the isomorphism of polynomials with one secret problem[END_REF] to explore the security of multivariate cryptography in general. The second one is a variant of the regular IP1S problem that we call incompressibility of IP instances. We detail these two properties, how they are linked to our problem and how well studied they are. For this section, let A be an ane multiple of any HFE instance with perturbations (p), (-,1), (-,2) or ( +).

Secret recovery on (d a + 1)-IP1S

Let us rst recall that our white-box implementation is composed of the n polynomials Ãi and a deterministic generic way to evaluate them (compute all the monomials then sum them up). The polynomials Ãi are dened by a composition with two ane transformations S and T such that:

Ãi (x 1 , ..., x n , y 1 , ..., y n ) = A i (S(x 1 , ..., x n ), T -1 (y 1 , ..., y n ))
It is then obvious that Ãi is an instance of a (d a + 1)-IP1S problem over 2n variables, with A i as the known polynomials and a block-ane transformation composed of S and T . This problem has a structured secret, so it is not generic, but we do not know any other attack against it (as an IP problem) than the generic ones. To the best of our knowledge, the best generic attack on 3-IP1S with ane secrets has complexity O(n 6 q n ) ( [START_REF] Bouillaguet | Practical cryptanalysis of the identication scheme based on the isomorphism of polynomial with one secret problem[END_REF]). This means that the best known attack against 3-IP1S instances is exponential in n . For our instances, (d a + 1) ≥ 3, these pieces of evidence allow us to conjecture that our instances are secure for the desired security level.

Remark 1: For the perturbation (p), the secret S : F n-p 2 → F n 2 is not a bijection, this instance is dierent from the one studied in general. However, as the projection variant is ecient against key recovery for HFE instances, one can hope that it will help our IP instance to stand against secret-recovery for the same reasons.

Remark 2: For perturbations (-, 2) and ( +) , the polynomial à are composite ane multiples, but the same analysis can be made.

Incompressibility of IP1S instances

The main goal of this part is to highlight a specicity of multivariate cryptography in general that will help us to prove the incompressibility of our white-box construction.

To do so, we formalize a new problem around IP instances, and analyse it on our instance ( Ãi ) i∈ 1,n .

We dene the (σ,τ )-incompressibility of an IP instance with known polynomials

(P i ) i∈ 1,m : Draw at random two secret ane transformations S, T in AF F n (F 2 )
The adversary A is given an IP instance ( Pi ) i∈ 1,m composed of (P i ) i∈ 1,m , S and T

The adversary A returns a program P that allows to evaluate ( Pi ) i∈ 1,m for every element (F 2 ) n

The adversary A wins if size(P) ≤ σ Denition 31. Let ( Pi ) i∈ 1,m be an IP instance with polynomials in n variables over F 2 , with known polynomials (P i ) i∈ 1,m and secrets S, T and let A an adversary. We say that ( Pi ) i∈ 1,m is (σ,τ )-incompressible if there is no adversary A that wins the σ-incompressibility game with probability 1 and Time(A)+Time(P ) < τ .

Remark 1: We could also consider, similarly to the incompressibility for whitebox, that A does not have to agree with (P i ) i∈ 1,m on all inputs or that it can be probabilistic. However, known attacks do not use this exibility.

It is well known that, for truly random polynomials, compressibility is not possible by denition in the sense of Kolmogorov, even with an unbounded computation power.

In contrast, in our context, a compressed version of the Ãi polynomials is obviously given if we can recover the secrets S and T . This problem of secret recovery on an IP instance corresponds to the extreme case σ = size(S) + size(T ) in Denition 4, and boils down to the unbreakability problem, for which the best known attacks require a computational eort way larger than 2 80 (see paragraph above, about Secret recovery on (d a + 1)-IP1S). In the intermediate cases size(S) + size(T ) < σ ≤ size(P i ), to the best of our knowledge, no attack has been found in the literature.

Generic White-Box Attacks on Multivariate Cryptography

In the literature, generic automated attacks are proven to be very ecient against the state-of-the-art white-box implementations of block-ciphers due to the techniques used (i.e masking or internal encodings for instance). These attacks include Dierential Computation Analysis (DCA) and Dierential Fault Analysis (DFA) as their most potent representatives. In this section we argue against their usefulness against our technique.

The main point of this section is to understand how IP instances are secure against these attacks, even if they are used in HFE schemes and hence have a trapdoor. A rst example of this is how HFE public keys are not vulnerable to DPA attacks or their white-box DCA counterpart. Indeed, even if the inversion of the public key can be attacked because it decomposes the inversion of P into the inversion of S, T and F separately, the public key itself is not vulnerable against DCA, even if it contains the complete key (S, T ). This is due to the structure of the IP problem. Indeed, all the bits of S and T are diused by polynomial composition into the coecients of the public key P . This means that unless a specic computation depending on few key bits is found on a specic instance, the probability is negligible that a nice target exists for generic white-box attacks, as the complexity of DCA is exponential in the number of key bits on which the target depends. The state of the art HFE security ignores these attacks for such reasons. For DFA, it is easy to make faults on the evaluation of P , but any evaluation of any function depending on the polynomials' coecients of the public is already allowed to solve IP and hence does not provide new information. This is a huge dierence compared to state-of-the-art targets of these attacks, which usually are S-Boxes in SPN schemes, and most often specically those of the AES algorithm.

For our implementation, the ane multiple structure allows to diuse S and T into A, in the same way they are diused into the public key. Unless a specic relation is found for this particular instance, the DCA has no more chances to succeed than the ones targeting the public key. The same argument also stands for DFA. In summary, such a DCA-like (resp. DFA-like) attack is not expected to be able to circumvent the similar hard-to-solve algebraic problem on which the algorithm's black-box security relies.

Remark: We can think of the following factorization-avoured analogy. Assume an attacker is given an RSA public key. Since n depends on the secrets primes p and q, one could wonder if DCA (resp. DFA) could be applied to n (or to a computation making use of n) to recover the secret elements p and q. However, it is also easy to see that in this case the algebraic complexity of the bits of n (as functions of the bits of p and q) quickly get so high that this kind of DCA (resp. DFA) strategy is not relevant here.

Conclusion of the Analysis of Security

In this section we synthesize the analysis of security above into two conjectures of similar nature, one for unbreakability, one for incompressibility.

Unbreakability Conjecture:

Let P be a HFE public key with modiers chosen among -, p and + . Let WBHFE be the white-box implementation of P -1 and A an associated composite ane multiple with corresponding perturbations. Let ϵ < 1 be a small probability and λ be our security level. If 1. The HFE instance associated to the public key P is secure against key recovery in the black-box model up to security level λ.

2. The knowledge of A does not help to remove modiers from P (Section 4.2) in less than 2 λ operations.

3. The ane multiple A is (2 λ ,ϵ)-unbreakable as a (d a +1)-IP1S instance. (Section

4.3.1)
then the implementation WBHFE of the primitive P -1 is (2 λ ,ϵ)-unbreakable in the white-box model.

Remark 1: The rst point of this conjecture is trivial if we want our HFE instance to be of any use. However, as we will see in section 5, this is an important dimensioning parameter to optimize the implementation size. This is why we make it part of the conjecture.

Incompressibility Conjecture:

Let P be a HFE public-key with modiers chosen among -, p and + . Let WBHFE be the white-box implementation of P -1 and A an associated composite ane multiple with corresponding perturbations. Let ϵ < 1 be a small probability and λ be our security level. If :

1. The HFE instance associated to the public-key P is secure against key recovery in the black-box model up to security level λ.

2. The knowledge of A does not help to remove modiers from P (Section 4.2) in less than 2 λ operations. Remark 2: This conjecture is very similar to the unbreakability one. This is due to the fact that the only compression we know from the public key is key recovery. Remark 1: It clearly appears that d being small is a problem to scale the construction. While we use perturbations to partly solve this problem, having a better understanding of the ane degrees could lead to smaller implementations (section 3.4.3). This remark carries onto the following instances.

Instances close to pC * -

As the Nude HFE instance is too weak for concrete use, we include state-of-the-art perturbations p and -. To do so, we include perturbations (p) and (-, 2) on the ane multiple. This means that the implementation is composed of the composite ane multiples of the polynomials G i :

G i (x) = ϵ i j=1 (y ′ + u i,j -F (x))
for which the last p coordinates of x are projected. For this section, we will choose internal polynomials of the form F = x 3 + Ax 2 , thus close to C * . Security analysis As for Nude HFE our instance needs to stand against direct inversion with Gröbner bases and key-recovery rank attacks (Section 2.10). However, the ane multiple attack is not applicable to public keys with -.

For white-box security, according to the conjecture, our instance needs to stand against attacks on d a -IP1S instances of section 4.4. This time, we need to ensure that perturbations cannot be removed in the white-box model. According to our conjecture, we only need to ensure that the attack of section 4.3 cannot be used. To do so, we take ϵ i = 3 so that the polynomial ϵ i j=1 (Π a (P (x)) + u i,j ) = 0 is not linear in Π a (P (x)).

Parameter Choices The main problem to minimize the implementation size for a given security level is that the ane degree of the ane multiple is high if we take F at random as soon as ϵ i ≥ 2. To reduce this degree, we choose polynomials F of the form x 3 + Ax 2 , A ∈ F n 2 and take ϵ i = 3. Indeed, with these parameters, we get ane multiples with d a = 3. We then optimize n, p and a for the desired level of security. Remark 1: To get an implementation of the complete signature algorithm, one needs to gather all the ane multiple B i . However, with only one of them, a signature can be computed if the last a coordinate of the signature lie in U i . This means that a message drawn at random will be signed with roughly probability 3 2 a . This probability is quite low but this remark can be used to have a smaller signature algorithm in the white-box model while not changing the public key and the verication algorithm.

Target

Instances close to C * +-

In this section we include the perturbations + and -. To do so, we include perturbations ( +) and (-, 1) in the ane multiple. This means that the implementation is composed of the composite ane multiples of the polynomials H i :

H i (x) = δ i j=1 (y + v i,j -F (x))
and the last a coordinates of y are chosen at random for signing. We will choose internal polynomials of the form F = x 3 + Ax 2 , thus close to C * . Security analysis The analysis is similar to the previous one, with p changed to + for better security against rank attacks: our instance needs to stand against direct inversion with Gröbner bases and key-recovery rank attacks (Section 2.10). However, once again, the ane multiple attack is not applicable to public keys with + and -.

For white-box security, according to the conjecture, our instance needs to stand against attacks on d a -IP1S instances of section 4.4, i.e. we only need to ensure that the attack of section 4.3 cannot be used. To do so, we take δ i = 3 so that the polynomial δ i j=1 (Q(x) + v i,j ) = 0

is not linear in Q(x).

Parameter Choices For the same reasons as for the previous instance, to reduce the ane degree, we choose polynomials F of the form x 3 + Ax Remark 3: Similarly to the previous instance with one of the ane multiples C i , a signature can be computed if its image through Q lies in V i . This means that a message drawn at random will be signed with roughly probability 3 2 t . This probability is quite low but this remark can be used to have a smaller signature algorithm in the white-box model while not changing the public-key and the verication algorithm.

Challenge: To motivate the cryptanalysis of our technique, we propose a challenge implementation corresponding to the line [START_REF] Mulder | White-Box Cryptography: Analysis of White-Box AES Implementations (White-Box Cryptograe: Analyse van White-Box AES implementaties)[END_REF][START_REF] Agrawal | Trojan detection using IC ngerprinting[END_REF][START_REF] Barkan | In how many ways can you write rijndael[END_REF][START_REF] Barak | On the (im)possibility of obfuscating programs[END_REF] on the previous table. The code in Sage 1 contains the public-key, one ane multiple and resources to manipulate them.

Instances close to D * +-

As a last example, we propose to use a variation of the long standing D * scheme. Even if the security of D * and its variations have not been studied in the recent literature, we use this instance to motivate the understanding of ane multiple structures over 1 available at the following URL: https://github.com/p-galissant/WBHFE dierent eld: the composite ane multiples of the D * +-have the smallest d a among the ones presented here.

One of the problems of the previous instances is that the ane multiples have to be built with δ i = 3 so that attacks from section 4.3 cannot be used. This is due to the fact that squaring is linear over F 2 . The signature algorithm D * is however designed over F q , q ̸ = 2, with internal polynomial F = x 2 : we want to use this fact to nd small ane multiple with d a = 2.

To do so, the public key is an instance with F = x 2 + Ax for any A ∈ F n 3 and use the + andperturbations. We include perturbations ( +) and (-, 1) on the ane multiple, as in section 5.3. This means that the implementation is composed of the composite ane multiples of the polynomials H i :

H i (x) = 2 j=1
(y -v i,j -x 2 -Ax) with v i,j in the image of Q.

Security analysis

The main problem with D * without perturbations is that polarisation attacks ( [START_REF] Patarin | Trapdoor one-way permutations and multivariate polynominals[END_REF]) easily break the public-key. However, the recent + makes the polarisation attack fail, for Q is not a square only.

Even if D * +-is not a state-of-the-art algorithm, we will assume the same relevant attacks as in the case of HFE, that is to say rank attacks and direct inversion attacks.

While it might need more research to conrm the soundness of this assumption, we will rely on these attacks to parameterize our proof of concept.

Parameter Choices The parameters n, t and a are the same as for the previous section. Indeed, we only we get a variation of d a from [START_REF] Agrawal | White-box cryptography with device binding from token-based obfuscation and more[END_REF] The goal of this chapter is to shortly discuss how multivariate cryptography problems such as the IP problem can be used for white-box cryptography in general and why multivariate cryptography is an adapted setting for white-box cryptography. As an example, we show a construction based on QUAD that inherently has incompressible properties.

Introducing IP-like problems for White-Box Cryptography

The implementation we made is essentially based on a variation of the IP problem. This 'decomposition' problem is very interesting in the white-box model as it let diuse all the key bits into the implementation at once, which is very unusual for white-box techniques. Usually, the key is 'glued' to a local transformation and hidden with an encoding. The key itself is not diused into the code and the encoding only locally randomizes the implementation. This leads to very ecient automated attacks on target functions with small key-spaces.

The HFE cryptosystem itself shows that there are inherent white-box properties to be found in multivariate cryptography. If the HFE instance is secure, the public key can be seen has an incompressible implementation of the composition of S, P and T .

Studying links between white-box cryptography and multivariate cryptography is surely a refreshing and fruitful approach.

For cryptosystem not related to multivariate cryptography, we believe this approach can also be interesting. First, polynomial transformations are a natural extension of the table-based methods to extend the support of the functions while keeping succinct representations. Attempting to composing them with techniques similar to the encoding rationale would lead to IP-like problems. Our AES construction of part II is made in this spirit.

One of the main problems to this approach is to actually decompose the algorithm into polynomials of small degrees. If ad hoc techniques might be successful for specic cryptosystem, we believe that structural techniques such as the ane multiple we used for HFE need to be investigated. The ARX implementation of Ranea et al. [START_REF] Ranea | Implicit white-box implementations: White-boxing ARX ciphers[END_REF] is an example of such attempt, but it also uses external encodings. To us, the structure of public-key cryptosystems can only oer more exibility to white-box designers.

An example : A Stream Cipher in the whitebox model

In this section, we adapt the stream cipher QUAD [START_REF] Berbain | QUAD: A practical stream cipher with provable security[END_REF] to get incompressible properties in the white-box model. Unlike HFE, QUAD is a private-key algorithm. To do so, we replace the random polynomial system that allows to compute the stream by a structured one. This approach is similar to the design of incompressible block-cipher presented in part I.

Description of QUAD

We describe QUAD over F 2 , knowing that it can be done in any characteristic. In the stream cipher QUAD published by Berbain et al. [START_REF] Berbain | QUAD: A practical stream cipher with provable security[END_REF], the key stream generation is made as follows. For any integers n and k, let S be a system of kn polynomials in n variables over F 2 : S = (Q 1 , ..., Q kn )

Then dene S out and S it as subsets of S: S it = (Q 1 , ..., Q n ) and S out = (Q n-1 , ..., Q kn ). The keystream generation is composed of the iteration of S it in the following way. Let x be the intermediate state:

Compute the system S(x) Output S out (x) as key-stream values Update the internal state x ← S it (x)

For initialization, assume that the secret key K and vector IV are dened by a n-bit vector and that we have access to other n-by-n random systems of polynomials of degree 2, namely S 0 and S 1 . We initialize the internal state x to the value K. Then, with p = kn, a = n and the + perturbation with quadratic form Q with parameter t ∈ N. We get a perturbed public key denoted by S (S,F,T ),Q , omitting indexes p and a since they are xed. Due to the chosen parameters, the public key S (S,F,T ),Q is a system of kn polynomials over n variables. We repeat this process with k = 1 to dene two systems S (S 0 ,F 0 ,T 0 ) 0 ,Q 0 and S (S 1 ,F 1 ,T 1 ),Q 1 , with the same trapdoor structure.

We dene the HFE-TRAP-QUAD stream cipher by using the exact same procedure for key-stream generation, except the private key is dened by the original private key K of QUAD, plus the secrets of the HFE instances, that is ((S, F, T ), Q), ((S 0 , F 0 , T 0 ), Q 0 ) and ((S 1 , F 1 , T 1 ), Q 1 ). We then dene the white-box implementation of WBHFE-TRAP-QUAD by the implementation of HFE-TRAP-QUAD where the systems polynomials S (S,F,T ),Q , S (S 0 ,F 0 ,T 0 ),Q 0 and S (S 1 ,F 1 ,T 1 ),Q 1 are computed with the knowledge of this secret key and stored that way. The rest of the implementation is identical to a naive implementation of QUAD. If the secret key cannot be recovered from the polynomials, the implementation is obviously unbreakable. For incompressibility however, we state the following conjecture.

Conjecture: Let S (S,F,T ),Q , S (S 0 ,F 0 ,T 0 ),Q 0 and S (S 1 ,F 1 ,T 1 ),Q 1 be the HFE instances dened above. If these instances dene secure trapdoor one-way functions, the streamcipher HFE-TRAP-QUAD is secure in the black-box model. If these instances are incompressible, the compiler WBHFE-TRAP-DOOR is incompressible. More precisely, if for any ϵ < 1, S (S,F,T ),Q is (σ, τ, ϵ)-incompressible, S (S 0 ,F 0 ,T 0 ),Q 0 is (σ 0 , τ 0 , ϵ)-incompressible and S (S 1 ,F 1 ,T 1 ),Q 1 is (σ 1 , τ 1 , ϵ)-incompressible, WBHFE-TRAP-QUAD is (σ + σ 0 + σ 1 , τ + τ 0 + τ 1 , ϵ)-incompressible in the plain white-box model.

Remark:

The incompressibility property of the implementation does not trivially stems for the incompressibility of the system. Indeed, similarly to the HFE implementation earlier, the stream-cipher generation functionality is not equivalent to the functionality of evaluating the polynomials but a subset of it.

We shortly discuss the size of the private key of HFE-TRAP-QUAD. For the system S (S,F,T ),Q , the size of the underlying HFE key is essentially the size of the matrices S and T and the size of the structure quadratic form Q which is composed of t random quadratic polynomials. As it is the same for S (S 0 ,F 0 ,T 0 ),Q 0 and S (S 1 ,F 1 ,T 1 ),Q 1 but with only n variables, the size of the private key is dominated by 2(kn) 2 + t × (kn) 2 . Once the HFE public keys have been composed, we obtain a system of kn equations in n variables for S (S,F,T ),Q , and systems of n equations in n variables for S (S 0 ,F 0 ,T 0 ) 0 ,Q 0 and S (S 1 ,F 1 ,T 1 ),Q 1 . Their total size is then dominated by kn × n 2 . This means there is essentially a gap of size n between the 'compact' private key and the incompressible representation. As values of k such as 2 or 3 are recommended in [START_REF] Berbain | QUAD: A practical stream cipher with provable security[END_REF] and small t can be taken for secure HFE instances, the incompressible implementation is n times bigger than its private key.

Conclusion of part III

The white-box state of the art of public-key cryptography is really young. It is however a subject that needs more attention considering the growing needs in the industry.

We propose the rst white-box implementation technique for the inversion of the HFE trapdoor one-way function based on the structure of its 'big eld' representation. This technique is based on the ane multiple principle, which relies on the vectorspace structure of the big eld representation. After proposing a rst implementation for nude HFE instances, we incorporate the perturbations p,and + into the design strategy. We then propose a security analysis that is based on a variation of the IP problem, and a challenge implementation to motivate cryptanalytic studies of this new kind of white-box implementation.

We then support the use of multivariate cryptography at large in the white-box context, and show some inherent white-box properties of multivariate schemes through an example based on QUAD.

As research on white-box cryptography has been mainly split between designing implementations of AES and attacking them, and theoretical constructions, there undoubtedly remain unturned stones for white-box implementations of public-key algorithms, and many areas are to be explored.

If one can look into new structures that support this 'double trapdoor' behavior of white-box signature implementation, one can also attempt to better understand the behavior of ane multiples. Indeed, we only explored ane multiples with a practical viewpoint, and a better understanding of their ane degree is a goal for future works, in order to generalize our implementation techniques to more HFE instances, or even to other multivariate schemes.

Assessing Security Contexts and Adversaries

In this thesis, we showed that in the state of the art, depending on the modeling of the attacker and the devices, an array of dierent security notions can be considered and the methods to achieve them can be vastly dierent. For instance, the use of hardware modules can enable very strong properties, but what are the adapted uses of an hardware in the context of a white-box study?

In that sense, we think that the concrete use cases for white-box cryptography need to be claried. A consultation between manufacturers and academics, to establish the concrete needs of the industry in terms of security goals and implementation environments, would be very useful. Some questions naturally emerge: is a secure hardware available at all? is there a control of the communications of the device? or is its computational power limited? To us, asking these question is essential, and precisely quantied answers could directly inuence the production of hardware (see Apple's phones for instance) and the accessibility of such technologies to individuals without the restraints of a specic hardware.

As we relax the white-box model to consider the hardware-module white-box model, we should also be careful of introducing again the problems of mistrusted hardware.

We can think of an 'hybrid' construction in the following sense. An implementation can be rst constructed in the plain white-box model and then transformed into a hardware-module implementation. That way, if the hardware on which the security in the hardware module is malicious or faulty, the underlying security of the implementation in the plain white-box model mitigates the aws.

With the ever increasing needs of white-box cryptography, we also believe that the standardization initiatives should lean toward imposing constraints of compatibility with white-box on their candidates. This is already the case for special use cases such as lightweight cryptography as shown by the recent NIST competition. If standardization does not include these constraints, the design of white-box implementation might be very arduous, as the post-quantum NIST candidates based on LWE may illustrate since they require precise noise distributions to be secure. In the plain white-box model, using randomness is surely a hard problem. The underlying problem of implementing standards such as AES or RSA is that the 'cutting' of the evaluation circuit is not very suited to the white-box context, with few bits of the key diused at the same time. One idea, that comes with the use of multivariate cryptography we made in part III, is that representing algorithms as a composition of multivariate polynomials systems of low degree would enable more possible techniques. This is however a very dicult problem in general and it is very likely that such 'cutting' would need to exploit the particular structure of the implemented algorithm.

More Structure for New Implementation Techniques

If the implementation of very common standards is out of reach for high security parameters for now, cryptographers can turn themselves to algorithms with more mathematical structure. Usually, if there is more mathematical structure, there are more attacks to be considered. However in our case as shown by our white-box implementation of HFE , it allows for techniques that are far from the usual 'internal encoding' rationale of implementation.

One could also try to implement functionalities that are extended from the original algorithm but still allow to compute the algorithm. For instance, one could remark that in our HFE implementation, A(x, y) is not strictly equivalent to F -1 . Having access to a structure that is not equivalent to the primitive that is to be white-boxed might give more freedom to designers.

If the algorithm or its underlying structure can be chosen, new designs constraints might arise. Finding 'double trap-door' structures, to help the design of cryptosystems adapted to the plain white-box model, is an interesting problem on its own that could greatly facilitate the deployment of white-box cryptography for asymmetric contexts.

One of the most interesting problems would be to implement the decryption algorithm of a fully homomorphic encryption (FHE) scheme, to allow to consider the boostrapping in relation to other functionalities, as it was done for iO in [START_REF] Garg | Candidate indistinguishability obfuscation and functional encryption for all circuits[END_REF].

Titre:

  Contribution à la Cryptographie Boîte Blanche : Modèles et Constructions Algébriques Mots clés : Cryptographie Boîte Blanche -Implémentation -Sécurité Logicielle Résumé : Du fait de la démocratisation de technologies telles que le paiement par mobile ou l'essor des technologies basées sur la blockchain, les besoins d'implémentations sécurisées dans le modèle boîte blanche d'algorithmes standardisés sont de plus en plus conséquents dans l'industrie. Malgré ces besoins, très peu de nouveaux designs sont proposés dans la littérature. Pour ne pas avoir à utiliser des implémentations aux designs non publics, de nouvelles techniques d'implémentations doivent être proposées et étudiées.

CONTENTSIntegrity:

  Alice can be sure that the message send by Bob has not been altered by an adversary on the line Non-Repudiation: Alice cannot deny being the sender of messages she has send before Non-Falsiability: Alice cannot tamper commitments she made in the past.

1 . 2

 12 Motivations to the White-Box Model : Industrial and Societal Needs Let us rst summarize some of the main interests in the study of white-box designs, whether it is for industrial concerns or the individual security of citizens. 1.2.1 Digital Rights Management One of the rst motivations introduced by Chow et al. to study this model of security is the security of DRM (Digital Rights Managements) technologies. The goal of Digital Rights Management is to restrict the access and distribution of copyrighted products such as music, lms or software. Avoid the distribution of illegal copies, locking certain functionalities to unlawful users or binding the content to a specic hardware are often the motivations to the use of such techniques. Usually, content protected by DRM technologies is encrypted by its owner (often a company) and sent to a customer. The customer is then provided a license to use the content. They then have to use a specic device or client to properly use the content if the license is correct and then decrypt the content using a secret key. If the key is stored in a secure device, solutions in the grey-box model of attacks are often sucient. However, if the key is stored in a software client, a malicious user can attempt to extract the key with the full knowledge of the implementation of the client. The security of such industrial solutions is often based on the obscurity of the construction, with hidden designs implementation. Designing solutions and understanding their security in the white-box model would greatly enhance the condence in DRM technologies.

  If notions such as incompressibility are well understood for the design of algorithm point of view, there are still too few implementation techniques for usual algorithms that achieve any security in the plain white-box model. Studying the security in the Remote-Access model might allow for new techniques to sprout, using the relaxation introduced by the model. We believe that studying notions such as unbreakability or one-wayness in this model for implementation of standards with relevant parameters is still a rst milestone to reach.We now describe the game of remote access incompressibility for any σ, δ > 0 for a compiler C E . This is a modied version of the game of unbreakability where we allow black-box access to E k and a certain quantity δ of data on C E (k) gathered in the white-box model on the device: Draw at random a key k in private keyspace K E The adversary A request any set of data D W B of size at most δ on the implementation C E (k) in the white-box model in time τ 1 and memory µ 1 . The adversary A returns a program P in time τ 2 and memory µ 2 having access to D W B and a black-box access to E k The adversary A succeeds if P ≈ E K and size(P) < σ Denition 11. Remote Access Incompressibility

  unbreakable and if for any adversary A and data set D W B running in time τ 2 and memory µ 2 , Succ A,C S ,D W B ≤ ϵ. Closing the Gap with the Black-Box Model The work of Hosoyamada et al. pushes the usual security notions of the plain white-box model for notions that are closer to the ones studied in the black-box model. They extend PRI, PRP, PRF and IND-CPA in the Remote-Access White-box model. If these notions were not achievable in the plain white-box model, the two-time phase of the remote-access model might allow implementation that satisfy these properties. We only adapt the PRP denition in our setting and refer to Hosoyamada et al. for the others. We describe the security property for encryption algorithms. The PRP security is dened by evaluating the distinguishability of two games: a real one based on the implementation and an ideal one based on oracle calls. To adapt their denition to the Remote-Access model, Hosoyamada et al. modify the usual PRP games.

Figure 3 . 1 :

 31 Figure 3.1: Framework for the Hardware-Module White-box model

  also lacks a concrete study of the cost in term of software overhead of this bootstrapping. Conversely, for designers, what is the metric to be optimizing if we aim at designing future hardware adapted to the white-box model? To what point is it important to minimize hardware functionalities? What are the hardware solution to minimize the implementation overhead? These questions are not discussed and no directions are taken to explore the model on concrete examples. We recall that minimizing hardware functionalities for bootstrapping security properties to software is the sine qua none condition for the usefulness of the model. Without this restraint, we are back at studying hardware security.

  view of the state of the art, it would be presumptuous to draw generic conclusions on the probabilty of success of fault attacks. They indeed dier greatly depending on the algorithm and the implementation technique used. For most of the state of the art, DFA on white-box implementation can be reduced to DFA against implementations in the grey-box model.In regards to these similarities, the countermeasures to grey-box DFA are similar to white-box DFA. They often come in the form of redundancy added to the implementation or error correcting codes embedded in the implementation to cancel certain types of faults. One can note parity-checks[START_REF] Bertoni | Error analysis and detection procedures for a hardware implementation of the advanced encryption standard[END_REF][START_REF] Karri | Parity-based concurrent error detection of substitution-permutation network block ciphers[END_REF] for block-ciphers, invariance-based codes[START_REF] Guo | Invariance-based concurrent error detection for advanced encryption standard[END_REF] for the AES. If these techniques might be useful in the white-box context, it is only conditional to the fact that this redundancy cannot be separated from the rest of the implementation which is harder to guarantee.Part II Implementation of AES in theWhite-Box Model Chapter 1 State-of-the-art : Implementing the AES in the White-Box Model In this chapter, we propose a state-of-the-art synthesis of open white-box implementations techniques of the AES-128 primitive in the plain white-box model. We choose to take a chronological approach to this synthesis. Indeed, we think that explaining constructions and attacks in reaction to these constructions leads to a better understanding of design development. Without the historical context, some of the constructions might feel too optimist in their security claims. This chapter starts with a short summary of the research timeline on white-box implementations. We focus only on published open designs. Then, we detail the most notable constructions in the seminal table-based rationale of Chow et al.. We also detail the new attacks that were used to break these constructions at the time. We then continue this state-of-the-art synthesis by detailing two polynomial based solutions and their cryptanalysis. At the end of the chapter, we propose an overall security analysis of all these constructions against state-of-the-art white-box attacks. 1.1 Description of the AES-128 Primitive The standard known as Advanced Encryption Standard (AES) is a symmetric encryption algorithm that won the 'AES competition' launched by the American National Institute of Standards and Technology (NIST) in 1997. The goal of this competition was to dene a new standard to replace the 3DES. The RIJNDAEL candidate, designed

  et al. As the transformation he uses are just dierent representations of the same computations, the implementation size is the same as Chow et al.. Cryptanalysis The implementation technique of Karoumi looked interesting because it transformed the AES round functions into new "randomized" ones before applying the encoding strategy. While Karroumi estimated the complexity of a BGE attack on his implementation to be 2 93 , De Mulder et al. showed that the dual round functions of Karroumi were in fact equivalent to regular AES rounds with the same key. The implementation would then be broken with a simple adaptation of the BGE attack. Luo et al. Large Non-Linear Encodings The implementation of Luo et al. tries to thwart the BGE attack by augmenting the size of the encodings, while not falling into the trap induced by the linear encodings of the Xiao and Lai implementation. Indeed, if the linear encodings can be peeled o by linear equivalence techniques, larger non-linear encodings might be enough to provide security to against the BGE attack. For their implementation technique, Luo et al. merge the technique of Chow et al. with the diusion technique of Xiao and Lai, to get larger encodings that do not blow up exponentially due to their size.

Figure 1 . 3 :

 13 Figure 1.3: Lee et al.'s basic tranformation

  in the the Bringer et al. paper shows the weakness of linear encodings in the white-box context without external encodings. To circumvent this problem, the authors propose an AES with random Sboxes. Contrary to the usual description at the byte level, the implementation of Bringer et al. uses a description of the round function over variables over F 2

Round 1

 1 The substitution part Σ 1 is composed of 16-bit truth tables. As we have 21 outputs for each of them per pair of S-boxes, the substitution part of round 1 is composed of 4 × 2 × 21 × 2 16 ≈ 2 23.4 bits. The encoding part Λ 1 is composed of 17 polynomials over 21×2 variables per S-box of the following round. Hence, the encoding part for round 1 has its representation composed of 17 × 16 × σ(21 × 2, 4) ≈ 2 25.5 bits. Round 2 to 9 The size of round 2 to 9 is the same as for round 1 except the substitution part Σ has a 21 bit input. Hence the size of the substitution part is 16 × ×11 × 2 21 ≈ 2 28.45 bits and the size of the polynomials of Λ is 16 × 21 × σ(11 × 4, 4) ≈ 2 25.5 bits. Round 10 The last round is only composed of the substitution part Σ. Its size is then 16 × 8 × 21 × 2 21 ≈ 2 25 bits.

1 . 2 A

 12 Short Plea for White-Box Multivariate Cryptography As we have seen from the theoretical study of part I and the state of the art of whitebox techniques for SPNs in part II, the array of techniques and mathematical objects used for white-box cryptography is quite limited. This is probably because the AES is the most studied algorithm in the white-box model. Indeed, its structure -i.e. the SPN structure with slow diusion of the key through ten rounds -does not help designers to decompose the algorithm into secure blocks in the white-box model. Essentially, with current state-of-the-art techniques the 8-to-8-bit layer of S-boxes followed by a 32-to-32 linear layer does not translate into a succinct representation of the round that can be composed with the next round to ensure a combinatorial hardness for adversaries. This is why rounds are usually broken down into tables with internal encodings, trying to decompose the round function -or the round function composed with a secret transformation.

D- 1 i=0 a i x 2 i

 12 with a, a o , ..., a D-1 ∈ F 2 [y] , if Mon(a k ) is the set of the monomials of a k we dene d a the ane degree of A by: d a := max k max m∈Mon(a k ) HW (deg y (m)) .

3 .

 3 The ane multiple A is (σ W B ,2 λ ,ϵ)-incompressible as a (d a + 1)-IP1S instance.(Section 4.3.2)then the implementation WBHFE of the primitive P -1 is (σ W B ,2 λ ,ϵ)-incompressible in the white-box model.

  White-Box Implementation of Standards, Mostly the AES In the last few years, few dierent implementation techniques appeared, especially for the AES. The implementation we propose is in a line of work that attempts to replace the countermeasures coming from the grey-box model, and based on randomness, by countermeasures based on the algebraic or combinatorial complexity of nding relations between sensible functions and values computed by the implementation. The questions to know if such design rationale can work in open design, and if a structural improvement can be gained by hidden design, are still open.Considering new techniques, one track would be to consider designs inspired by constructions of cryptographic obfuscators. For instance, considering universal circuits such as the constructions of part I would reduce the problem of white-boxing particular algorithms to the evaluation of encoded inputs. This change of viewpoint has been very fruitful for iO, and could probably help to produce new designs.

  By hard-coding the EMV keys into the application code itself, white-box cryptography tries to achieve a notion of tamper-resistant software. Improving white-box cryptography, in particular for signature algorithms, is therefore a powerful means to promote the rise of mobile payments. Note that the currently used signature algorithm is RSA, and EMVCo published a new specication in 2021, to enable Elliptic Curve Cryptography (ECC) on EMV contact chip payment cards.

Mobile contract signing The eIDAS regulation (EU Reg. N • 910/2014) came into force on July 1st 2016 in the (then) 28 member states of the EU, and introduced the end of the smart card dogma, in the sense that the signing capability can now be implemented by purely software means as long as they fulll specic requirements through a qualication procedure. Electronic signatures also became legal evidence that cannot be denied by sovereign authorities or in court.

  In their 2016 paper[START_REF] Bellare | Big-key symmetric encryption: Resisting key exltration[END_REF],Bellare et al. propose solutions to mass surveillance by Advanced Persistent Threats (APTs), i.e. malware implanted in a device that attempts to extract informations, especially secret keys. The start of their reexion is that APTs are almost impossible to entirely remove from one's system. They argue that leaks from Snowden show that the NSA and other organizations have enough means to plant APTs if they want to.

  al. this technique is the most common one to build AES implementation. Formally, the target function ϕ

	ϕ k	ϵ
	ϕ

k : F n 2 :→ F m 2 is encoded by a bijection ϵ : F m 2 → F m 2 .

The composition φk = ϵ • ϕ k can be observed in the evaluation traces. k Denition 14 ( Correlation Coecient). Let f and g be two balanced boolean functions from F n 2 to F 2 . We dene the correlation coecient between f and g by :

  For future use, we note M C the MixColumn matrix and M C i its columns.The AES algorithm starts by AddRoundKey(x,0). Then, it performs 9 rounds composed of SubBytes, ShiftRows, MixColumns and AddRoundKey. The last round is only composed of SubBytes, ShiftRows and AddRoundKey. Denition 16. For 1 ≤ t ≤ 9 and 1 ≤ i, j ≤ 4 and (K 0 , ...., K 10 ) the round keys after key-schedule. The four 32-to-32 bit round functions R t j (x 1 , x 2 , x 3 , x 4 ) of the AES-128 are dened by:

		 02 03 01 01 	 s 1,j	
	4,j ) =	   01 02 03 01 01 01 02 03    ×	   s 2,j s 3,j	  
		03 01 01 02	s 4,j

  Table Based Rationale The rst part of the state of the art contains table-based solution. Started by the seminal implementation of Chow et al., this technique of implementation represents sub-computations of the AES round functions by look-up tables. The goal of this strategy is to use look-up tables as incompressible elements in which the randomness introduced by the compiler hides secret information related to the key.

table :

 :

	Round	m	m'
	1	24	17
	2	24	13
	3 to 7	13	13
	8	4 × 13 13
	9	24	17
	10	-	-

Table 1 .

 1 1: Size of each round encodings

  implementation against key-extraction in the plain white-box model, that is, external encodings, if any, are included in the clear in the implementation, and can then be peeled o. This might seems like a disadvantage for earlier designs, but keep in mind that early designs were defeated by variants of the BGE attack, even with external encodings, and that more modern designs avoided the use of external encodings. Also, we include the implementation of Bringer et al. as an AES implementation without the keyed S-boxes for a fair comparison.To argument the results of the summary table 1.2, we rst detail the eciency of known attacks based on the state of the art of Part 1 and Chapter 2 Part 2. We assume that the implementations are taken without external encodings for a fair comparison in the plain white-box model. We also assume that the Bringer et al. implementation is made with the AES S-boxes. Against Linear Methods (LM) We group in linear methods the attacks that exploit the linear structure of the encodings that are not LDA. Historically, these are the Linear Equivalence methods and the cryptanalysis of Bringer et al. implementation. We set them aside from linear techniques such as LDA to emphasize their non-automatic behavior. All the implementations with non linear encodings are not vulnerable to these attacks. Against BGE In this category, we group the BGE attack and its extension by Michiels et al.. All the implementations using the technique of Chow et al. are structurally broken by it. The only constructions that stand against it are the ones that mask the round function to avoid to have a simple bijective encoding of the round function, namely, Rasoamiaramanana et al. and Bringer et al. constructions.

  techniques. For Lee et al., the aw resides in encodings at the round level that are not randomized like the s-boxes. Due to the heavy use of random polynomials in Bringer et al. implementation, it is not clear whether collisions can be exploited in this setting.The implementation of Rasoamiaramanana et al. should not be susceptible to BCA at the S-box levels as the encodings are larger than the S-box size.

		BCA
	Table 1.2: Comparative Security Analysis against Key-Extraction	Size LM BGE DCA CCA LDA
		Implementation	Chow et al.

  The functions Λ are extended to functions F 42,21 by linearly sharing the coordinates into 21 functions, that is, the compiler computes an application ext1 1,k ∈ F 18,21 such that there exist ext L11,k ∈ F 21,18 :

	ỹ1 [8 : 15], ỹ2 [0 : 7], ỹ2 [8 : 15])[8k : 8k+7] || ỹ1 [16 : 20] || ỹ2 [16 : 20]

  The functions Λ are extended to functions F 42,21 by linearly sharing the coordinates into 21 functions, that is, the compiler computes an application ext1 1,k ∈ F 20,21 such that there exist ext L11,k ∈ F 21,20 :

	1 , for
	k ∈ 1, 4 :
	L2 1,k := α || ỹ1 [8 : 12] || ỹ2 [8 : 12] || ỹ3 [8 : 12] || ỹ4 [[8 : 12]
	with
	α = L 1 1,1 (ỹ 1 [0 : 7], ỹ2 [0 : 7], ỹ3 [0 : 7], ỹ4 [0 : 7])[8k : 8k + 7]

  The functions Λ are extended to functions F 44,21 by linearly sharing the coordinates into 21 functions, that is, the compiler computes an application ext1 1,k ∈ F 20,21 such that there exist ext Lt 1,k ∈ F 21,20 :

1 , for k ∈ 1, 4 : Lt 1,k := α || ỹ1 [8 : 10] || ỹ2 [8 : 10] || ỹ3 [8 : 10] || ỹ4 [[8 : 10] with α = L t-1 1,1 (ỹ 1 [0 : 7], ỹ2 [0 : 7], ỹ3 [0 : 7], ỹ4 [0 : 7])[8k : 8k + 7]

Algorithm 1 :

 1 White-box compiler WBHFE input : A HFE secret key (S, F, T ) with ane projected S and ane complete T Compute the ane multiple A(x, y) of F with algorithm of section 3.2 Compute the composition with secrets S and T and projection maps to get the coordinates of Ãi

output: WBHFE (S , F , T ) the white-box implementation of P -1 with key (S, F, T ) :

Ãi (x 1 , ..., x n , y 1 , ..., y n

Table 2 .

 2 in the following table but these are just mere examples and any polynomial with the desired ane degree can be used in our construction. Internal Polynomial F , ∀A, B ∈ F n 2 d a x 12 + Ax 10 + Bx 6 2x 12 + Ax 4 + Bx 3 1: For the polynomials F proposed, the ane multiple is easily computable with the algorithm of section 3.2. The values d a are exact, provided that for our choice of A and B the terms of degree d a do not vanish (this only happens on few singular points).

	3

Table 2 .

 2 2: Set of parameters d a and n which satises particular security levels λ. The value log 2 (σ W B ) is the corresponding log 2 of implementation size in bits. The values C G , C R and C AF F are the log 2 of the complexity of respectively best Gröbner basis attack, best rank attack and best ane multiple attack.

Table 2 .

 2 3: Set of parameters d a , a, p and n which satises particular security level λ. The value log 2 (size(B i )) is the corresponding log 2 of size of an ane multiple in bits. The values C G and C R are the log 2 of the complexity of respectively best Gröbner basis attacks and best rank attacks.

	(n, d, p, a)	log 2 (size((B i ))	C G	C R
	Smallest for λ = 80 (101,2,12,21)	30.5	86.4	83
	Smallest for λ = 90 (116,2,14,26)	31.5	101.3	91.6
	Smallest for λ = 128 (169,2,23,41)	34.3	136.5	130

Table 2 .

 2 2 , A ∈ F n 2 and take ϵ i = 3. Indeed, with these parameters, we get ane multiples with d a = 3. We then optimize n, t and a for the desired level of security. 4: Set parameters d a , a, t and n which satises a particular security level λ. The value log 2 (size(C i )) is the corresponding log 2 of size of an ane multiple in bits. The values C G and C R are the log 2 of the complexity of respectively best Gröbner basis attacks and best rank attacks

	Target	(n, d, t, a)	log 2 (size((C i ))	C G	C R
	Smallest for λ = 80	(85,2,9,5)	29.5	82.4	80.3
	Smallest for λ = 90	(96,2,11,6)	30.3	106.5	91.3
	Smallest for λ = 128 (132,2,18,4)	32.6	138.3	128.9

Table 2 .

 2 to 2. 5: Set parameters a, t and n which satises a particular security level λ. The value log 2 (size(C i ) is the corresponding log 2 of size of an ane multiple in bits. The values C G and C R are the log 2 of the complexity of respectively best Gröbner basis

	Target	(n, d, t, a)	log 2 (size((C i ))	C G	C R
	Smallest for λ = 80	(85,2,9,5)	25.7	82.4	80.3
	Smallest for λ = 90	(96,2,11,6)	26.4	106.5	91.3
	Smallest for λ = 128 (132,2,18,4)	28.2	138.3	128.9
	attacks and best rank attacks

La seconde partie est consacrée à l'étude des implémentations d'AES en boîte blanche. Nous proposons d'abord une synthèse des techniques de l'état de l'art ainsi que de leur cryptanalyse historique. Nous proposons ensuite une implémentation de l'AES dont le but est de résister aux attaques de type Linear Decoding Attack (LDA) de degré supérieur. Cette technique est basée sur le rationnel d'encodage interne et utilise une représentation polynomiale des calculs. La sécurité de l'implémentation est ensuite estimée contre les attaques de l'état de l'art conditionnellement au degré de certaines relations de décodage. Pour motiver l'étude de cette technique, nous proposons une implémentation challenge. Enn, nous extrapolons une méthode d'implémentation pour les algorithmes de type Substitution Permutation Network (SPN) appelée Randomized Circuit Knitting (RCK). Pour illustrer sa versatilité, nous montrons comment implémenter l'algorithme PRESENT dans le modèle boîte blanche avec RCK. La dernière partie de cette thèse est consacrée à l'étude de l'implémentation des primitives à base de cryptographie multivariée. Après une introduction succincte à la cryptographie multivariée, nous motivons l'utilisation de la cryptographie multivariée dans le modèle boîte blanche, notamment pour primitives fondées sur les problèmes d'Isomorphismes de Polynômes (IP). Nous proposons ensuite la première implémentation boîte blanche de la famille de signature HFE. Cette technique repose sur le calcul de multiples ane permettant d'inverser la clé publique d'HFE sans utiliser la trappe traditionnelle. Après avoir étudié l'existence et la calculabilité des multiples anes en fonction de divers paramètres, nous proposons une analyse de sécurité de notre implémentation relative à une conjecture sur une variation du problème IP. Enn, pour illustrer la exibilité de la cryptographie multivariée, nous proposons un chirement à ot incompressible basé sur QUAD

Remark : The choice of allowing A to query C E (k) before building the malware can be seen as an empowerment of the usual malware adversary. Conversely, the fact that the malware cannot be modied adaptatively in regard to the white-box information extracted fails to grasp the most powerful adversaries. These variations can be discussed, but this framework allows for simplicity of description.

31.77 bits ≈ 450MB. While it is non-negligible, it is still deployable in most devices used nowadays.

drawn at random, with high probability, d ≥ 11.If this conjecture stands, the attack can be made in 2 74 operations.Remark: Note that to conduct this attack, one has to evaluate Λ over many inputs and the polynomials of Λ are composed of σ(42, 4) ≈ 2 24.1 monomials, The evaluation of the polynomials Λ can be a lower bound for the attack.2.2.2 Against DCAFor this section, we base our analysis on the analysis of DCA made on random encodings by Rivain and Wang in[START_REF] Rivain | Analysis and improvement of dierential computation attacks against internally-encoded white-box implementations[END_REF].

encodings with the sharing of the S-box output leads to a map represented by degree-4 polynomials that can be made similar in size to the maps Λ of the AES implementation.

Signature and Verication For signature, as usual, we use the direct sense of the trapdoor to verify and the inverse to sign. Contrary to encryption, m can be smaller than n without any impact on the ability to sign. We give the example of a hashand-sign algorithm. Let h : {0, 1} * → F m be a hash function. To sign a message x ∈ {0, 1} * , one needs to compute the preimage of its hash through P:

and we can recover ϵ • A over a basis since :

The ane part is then recovered by solving an overdened system of equations and the input encodings are easily peeled out, to complete the key-recovery. We refer to [START_REF] Billet | Cryptanalysis of a white box AES implementation[END_REF] for the complete attack.

Upgrade and Attacks

In this section, we briey detail the improvement and variations to the state-of-theart candidate constructions. As constructions are often reactions to new attacks or optimizations of attacks, we also include the chronological cryptanalysis of the constructions.

The Xiao Lai Implementation

The rst idea to resist the BGE attack is to consider larger encodings and to encode more than one byte at a time. The implementation of Xiao and Lai [START_REF] Xiao | A secure implementation of white-box aes[END_REF] uses this idea to modify the original implementation of Chow et al.. In this construction, the authors use linear encodings to widen the size of the encoding, while not having an exponential explosion in degree due to the composition of random non-linear encodings. The authors claimed that their construction was standing against the BGE attack. This implementation still has external encodings.

Historic Cryptanalysis The cryptanalysis of this implementation was made by De

Mulder et al. [START_REF] Mulder | Cryptanalysis of the xiao -lai white-box AES implementation[END_REF] by using an adaptation of Biryukov et al. [START_REF] Biryukov | A toolbox for cryptanalysis: Linear and ane equivalence algorithms[END_REF] For the sake of completeness, we also discuss the security against the BGE attack.

The claim of the author was proven to be wrong, as a generalization of the attack on all traditional encoding strategies was made by Michiels et al. [START_REF] Michiels | Cryptanalysis of a generic class of white-box implementations[END_REF]. More on this attack will be given below.

Karoumi Dual Cipher Implementation

The implementation idea of Karoumi [START_REF] Karroumi | Protecting white-box AES with dual ciphers[END_REF] is to use the underlying algebraic structure of the AES to propose a family of distinct implementations. The remark made by the in two sets (F 2 8 ) 16

We then dene a set of perturbation polynomials Φ 1 ,Φ c 1 ,Φ 2 and Φ c 2 such that :

.., ϕ 4 ) and Φ 1 (x) and Φ 2 (x) are random.

It means that there are always at least two perturbation polynomials that agree for any input, and that the correct value (ϕ 1 , ..., ϕ 4 ) can always be found by taking the majority vote out of all the 4 possible values.

The nal implementation is composed of four instances of the construction described before, one for each of the perturbation polynomials we just described.

Cryptanalysis

A rst cryptanalysis of the construction is the report by Bringer et al. themselves of an attack by Coron. The main aw is due to the fact that the encodings are linear.

Targeting a S-box, one can attempt to solve a linear system by xing input 3 input bytes out of the 4 on the rst systems of polynomials Z 1 . This is essentially a LDA.

To circumvent this problem, the authors propose to use random S-boxes instead of the s-box of the AES, turning them into a new block-cipher AEw/oS. This variation seems to lead to a secure implementation even if this changes the original problem while proposing new designs to explore. overhead to nd an element in the image of P , hence a q p overhead in signature time.

However, the cryptanalysis of this variation is broken by

More details on this variant are given in [START_REF] Ding | Algebraic attack on hfe revisited[END_REF][START_REF] Øygarden | On the eect of projection on rank attacks in multivariate cryptography[END_REF].

A HFE scheme with the modiers p is called pHFE with public key:

The Plus Hat ( +) Perturbation Introduced in [START_REF] Faugère | A new perturbation for multivariate public key schemes such as HFE and UOV[END_REF], the Plus Hat + perturbation modies the central polynomial F . To do so, let t be an integer, (β 1 , ..., β t ) ∈ (F q ) t and (p 1 , ..., p t ) ∈ F q [x 1 , ..., x n ] t dene a transformation Q such that:

where we identify X to its representation (x 1 , ..., x n ) in (F q ) n . The central polynomial is then modied to be H = F + Q. A HFE scheme with the modiers + is called HFE + with public key:

To sign with such instance, we can remark that the image of Q is a small subvector space of F n q of dimension at most t. Then the q t values of Q can be guessed, and the regular inversion of the instance can be made for each of these guess. The signature is the only x corresponding to the correct value of Q. More details on the Plus Hat variant can be found in [START_REF] Faugère | A new perturbation for multivariate public key schemes such as HFE and UOV[END_REF].

The C * and D * schemes

We give a brief description of C * and D * , ancestors of HFE, as we will use them for particular instantiations in section 5.

Historically, HFE is a descendant of the scheme C * [START_REF] Matsumoto | Public quadratic polynominal-tuples for ecient signature-verication and message-encryption[END_REF][START_REF] Matsumoto | A class of asymmetric cryptosystems using obscure representations of enciphering functions[END_REF]. This scheme is identical to HFE except this time, the internal polynomial is only a monomial F = x 1+q θ for any integer θ. The cryptanalysis of C * by Patarin [START_REF] Patarin | Hidden elds equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms[END_REF] caused the disuse of this simple central polynomials for nude instances and the complete key recovery of [START_REF] Dubois | Practical cryptanalysis of SFLASH[END_REF] broke the C * -perturbation. However, the state of the art for pertubations still enables the design of unbroken multivariate schemes such as C * +-. The D * scheme is more contemporary of C * and was proposed in [START_REF] Patarin | Trapdoor one-way permutations and multivariate polynominals[END_REF]. The idea is to use F = x 2 as a central polynomial over F n q where q ̸ = 2. Its security is discussed in the seminal paper [START_REF] Patarin | Trapdoor one-way permutations and multivariate polynominals[END_REF] but without the considering perturbations like p or +. More on this topic will be given in section 5.

The Plus Hat Perturbations and Support Minor Modeling Attacks The authors of [START_REF] Faugère | A new perturbation for multivariate public key schemes such as HFE and UOV[END_REF] analyse rank attacks against HF E +. They conjecture the best attack to be in:

where C R (n, d) is the complexity of the support minor modeling attack on the underlying HFE instance.

Dierential Attacks

The dierential attacks were introduced in [START_REF] Dubois | Practical cryptanalysis of SFLASH[END_REF] to attack the scheme of Matsumoto and Imai. They exploit the simple structure of the dierential of the monomial used in the scheme, as well as a commutation with some multiplication operation.

Even if they were really ecient against C * , no adaptation to HFE was ever found and the authors of [START_REF] Cartor | On the dierential security of the hfev-signature primitive[END_REF][START_REF] Daniels | Dierential properties of the HFE cryptosystem[END_REF] showed that the usually chosen HFE polynomials do not have any exploitable dierential structure. Now, to start the white-box transformation from an HFE secret key (S, F, T ) over n bits -with bijective ane transformation S : F n 2 → F n 2 and bijective ane transformation T: F n 2 → F n 2 and the public transformation π -the compiler computes rst the ane multiple A(x, y) of F over F 2 n following the algorithm described in the previous section.

From the polynomial A(x, y), the compiler can now compute the coordinates A i (x 1 , ..., x n , y 1 , ..., y n ) (for i ∈ 1, n ) of A through the isomorphism π, and its composition with the secrets map S and full map T :

Now, to compute P -1 (y), one can plug the coordinates y 1 , ..., y n of y into the polynomials Ãi to get a linear system of n equations in x 1 , ..., x n that can be solved through Gaussian inversion for instance. However, one should worry that (F (x) = y) only implies (A(x, y) = 0), and not the reciprocate. Indeed, when we plug y in, we might get a solution x such that (A(x, y) = 0 and F (x) ̸ = y). To avoid such cases, we have to verify that for the chosen y, the signature is valid (i.e. F (x) = y). As the verication is made with the public key, the time needed to perform this check is negligible.

We dene the collection of the n polynomials Ãi , the code for evaluation and the code for linear inversion to be the white-box implementation of the computation of P -1 . We note this compiler WBHFE . This leads to the compiling Algorithm 1 :

First, we decompose y = y ′ + y -from a direct sum

The idea is to have an ane multiple that represents at least 2 xed choices for the last a coordinates y -. To do so, let us take any integer n s > 0 and split F a 2 = ∪ ns i=1 U i where #U i = ϵ i ≥ 2. We set U i = {u i,1 , ..., u i,ϵ i }. Now consider the polynomials :

We now want an object that is similar to an ane multiple for the polynomial F , but for the polynomials G i . To do so, we introduce the composite ane multiple: Denition 30. Let δ ∈ N and ∀i,

Remark: It is obvious that the algorithm of section 3.3 can be adapted to compute a composite ane multiple. The modulus simply needs to be changed to the product G. Its functionality is then similar to a regular ane multiple, except the solution satises one of the equations F i (x) = y.

A composite ane multiple B i (x, y ′ ) of G i in unknowns x and y ′ can produce signatures for which the last a coordinates of the message can be any element of U i (relatively to the nude public key). When signing in the white-box model, the value of the u i,j are then not revealed and the signature can be chosen randomly among the ones satisfying the n -a rst coordinates. An attacker can then, at best, guess that the missing coordinates lie in a set of ϵ i values to interpolate.

To incorporate the "-" perturbation in the white-box model, we will use the polynomials G i and apply the ane multiple construction:

For a HFE instance perturbed with "-", we can associate the collection of the ane multiples of the G i . When we use this perturbation, we note that the implementation is perturbed by (-, 2) with parameters (ϵ 1 , ..., ϵ ns ).

Remark : In the (-, 2) perturbation, we provide a collection of n s ane multiple to cover the whole vector space F a 2 . Note that it is possible to do it for only few values, only one of the U i for instance, and then get an implementation that produces a signature only when the last a coordinates are in U i . This will lead to a smaller signature space and a smaller implementation size. More details on this technique will be given in section 5.

Of course, proving this conjecture still requires new insights, in particular to clarify the deep algebraic links between the polynomial systems arising from A(x, y) on the one hand, and from P -1 on the other hand. However, we believe this paves the way for a better understanding of the incompressibility property, which up to now could be formally veried only for white-box implementations of symmetric cryptosystems in very restricted models (see the proof of incompressibility of an RSA-like symmetric encryption scheme in [START_REF] Delerablée | White-box security notions for symmetric encryption schemes[END_REF], using an Ideal Group Model).

Instantiations

In this section, we propose instances of HFE based on the construction of section 3 according to the security analysis of section 4 in the white-box model. We propose challenges for a subset of them.

Nude HFE

As a starting example, we propose a Nude HFE instantiation. This rst example is a proof of concept and shows the need of perturbations to reach any reasonable size of implementation.

Security analysis Let us rst recall the main attacks in the black-box model. Our instance needs to stand against direct inversion with Gröbner bases and key-recovery rank attacks (Section 2.10). As our instance will not have any perturbation, it also needs to be protected against the ane multiple attack.

For the white-box security, according to our conjecture, the instance needs to stand against attacks on d a -IP1S instances of section 4.4. As the HFE instance will be nude, the problem of removing modiers is not relevant here.

Parameter Choices The goal of this section is to minimize the size of the implementation for a given security level. For the Nude HFE instance, the only parameters to be chosen are n and d a . For a better compromise between size and security, we can take polynomials for which there exist ane multiples with d a = 2 and d and d reg is maximal. The maximum we experimentally found is d reg = 3 for internal polynomials of the form F = x 6 + Ax 5 + Bx S it (x) S out (x)

x for each bit of IV, the state is updated as follows: starting from i = 1, IV i = b, x is updated by S b (x). Note that in QUAD, the system S, S 0 and S 1 are made public.

The authors of QUAD prove that, provided S, S 0 and S 1 are random systems, their algorithm is secure. More precisely, they show that if the MQ problem stands for these systems of polynomials, then the stream cipher is secure.

A variation of QUAD with small representation

The original QUAD algorithm uses random systems S, S 0 and S 1 with n variables over F 2 . Such systems are inherently incompressible as random systems of equations. We now propose to introduce a 'trapdoor' in these systems to get a compact version of it.

We can then have a short description of this algorithm, and use the whole system of polynomials as the incompressible representation.

To do so, we will generate the system S as a pHFE +-public key. While this variation is not used for signature due to the large overheads induced by + and p, we only use the system in the direct sense, so that these concerns are not relevant here.

We then conjecture that if the MQ problem stands on the HFE instance we propose, the tweaked QUAD stream cipher admits incompressible implementations in the white-box model, with a non negligible gap between the short and long implementations. HFE-TRAP-QUAD We now dene a new stream cipher based on QUAD. Instead of taking a random polynomial S, we use a system S (S,F,T ),Q . This system will be secret unlike regular QUAD. It is dened in the following way. Let (S, F, T ) be a naked HFE instance over F 2 ( (k+1)×n . We now perturb the naked public key P = T -•π -1 •F •π •S

General Conclusion