Je Remercie

Anne Canteaut

Pierre-Alain Fouque

Helena Handschuh

David Pointcheval

Guénael Renault

Merci Donc

Srinivas Vivek

Anthony Journault

François-Xavier Standaert

Antoine Joux

Sonia Belaid

Victor Lomné

Jérémy Jean

Thomas Prest

Alain Passelegue

Ange Martinelli Je Tiens Également À Remercier

André Chailloux

Thomas Debris

Michel Abdalla

Balthazar Bauer

Fabrice Benhamouda

Raphael Bost

Florian Bourse

Celine Chevalier

Jeremy Chotard

Simon Cogliani

Mario Cornejo

Geoffroy Couteau

Edouard Dufour Sans

Rafael Del Pino

Aurelien Dupin

Pierre-Alain Dupont

Pooya Farshim

Houda Ferradi

Georg Fuchsbauer

Romain Gay

Chloe Hebant

Julia Hesse

Louiza Khati

Pierrick Meaux

Thierry Mefenza

Michele Minelli

Anca Nitulescu

Michele Orru

Razvan Rosie

Melissa Rossi

Adrian Thillard

Bogdan Ursu

Damien Vergnaud

Jacques Beigbeder

Lise-Marie Bivard

Isabelle Delais

Nathalie Gaudechoux

Joelle Isnard

Valerie Mongiat

Ludovic Ricardou

Sophie Jaudon

Aurélien Laetitia Ange

Crypto de l'ENS auprès de collègues mais surtout amis

Keywords: cryptography, side-channel attacks, efficient implementation, countermeasures, provable security, assembly

Depuis leur introduction à la fin des années 1990, les attaques par canaux auxiliaires sont considérées comme une menace majeure contre les implémentations cryptographiques. Parmi les stratégies de protection existantes, une des plus utilisées est le masquage d'ordre supérieur. Elle consiste à séparer chaque variable interne du calcul cryptographique en plusieurs variables aléatoires. Néanmoins, l'utilisation de cette protection entraîne des pertes d'efficacité considérables, la rendant souvent impraticable pour des produits industriels. Cette thèse a pour objectif de réduire l'écart entre les solutions théoriques, prouvées sûres, et les implémentations efficaces déployables sur des systèmes embarqués. Plus particulièrement, nous nous intéressons à la protection des algorithmes de chiffrement par bloc tel que l'AES, dont l'enjeu principal revient à protéger les boîtes-s avec un surcoût minimal. Nous essayons tout d'abord de trouver des représentations mathématiques optimales pour l'évaluation des boîtes-s en minimisant le nombre de multiplications (un paramètre déterminant pour l'efficacité du masquage, mais aussi pour le chiffrement homomorphe). Pour cela, nous définissons une méthode générique pour décomposer n'importe quelle boîte-s sur un corps fini avec une complexité multiplicative faible. Ces représentations peuvent alors être évaluées efficacement avec du masquage d'ordre supérieur. La flexibilité de la méthode de décomposition permet également de l'ajuster facilement selon les nécessités du développeur. Nous proposons ensuite une méthode formelle pour déterminer la sécurité d'un circuit évaluant des schémas de masquages. Cette technique permet notamment de déterminer de manière exacte si une attaque est possible sur un circuit protégé ou non. Par rapport aux autres outils existants, son temps de réponse n'explose pas en la taille du circuit et permet d'obtenir une preuve de sécurité quelque soit l'ordre de masquage employé. De plus, elle permet de diminuer de manière stricte l'emploi d'outils coûteux en aléas, requis pour renforcer la sécurité des opérations de masquages. Enfin, nous présentons des résultats d'implémentation en proposant des optimisations tant sur le plan algorithmique que sur celui de la programmation. Nous utilisons notamment une stratégie d'implémentation bitslice pour évaluer les boîtes-s en parallèle. Cette stratégie nous permet d'atteindre des records de rapidité pour des implémentations d'ordres élevés. Les différents codes sont développés et optimisés en assembleur ARM, un des langages les plus répandus dans les systèmes embarqués tels que les cartes à puces et les téléphones mobiles. Ces implémentations sont, en outre, disponibles en ligne pour une utilisation publique.

Introduction

Cryptography is the science of secret, being both an ancient art from the antiquity and a new science for which scientific research has grown popular since the seventies. From ancient history, its use was essential to allow different military entities to communicate about vital information (army positions or numbers, resource disposal, etc.) without risking any leakage in case enemies intercept a message. Its ground goal is hence to guarantee the confidentiality of the information, namely the fact that only the authorized parties (namely that possess a certain cryptographic key) can understand encrypted information. With the rise of new technologies and the Internet, protecting communications and sensible data has become a crucial issue. Modern cryptography has then transitioned to answer the needs of the society as much as in democratising itself to no longer only serve military purposes but also to protect anyone's privacy, as well as in diversifying its utility. Nowadays, cryptography can provide confidentiality (only the sender and the receiver can understand the communication), authenticity (the receiver can verify from who he received the communication) and data integrity (the communication has not been altered during its transfer).

Since the 1970's, we distinguish two types of cryptography: secret-key cryptography and public-key cryptography. The former allows to establish secure communication when the two representatives share a secret private key that is used for both encryption and decryption (hence its other designation of symmetric cryptography), whereas the latter uses a pair of different keys, a public key and a private key, where the public key is used for encryption and the private key for decryption (hence its other designation of asymmetric cryptography). In this thesis, we will mainly focus on symmetric cryptography, and more particularly on cryptographic schemes called block ciphers. One of the most prevailing and deployed block ciphers is the Advanced Encryption Standard (AES) proposed by Daemen and Rijmen in 1998 and standardized by the National Institute of Standards and Technology (NIST) in 2001. Based on a substitution-permutation network, this encryption scheme is very efficient both in hardware and software. The security of this scheme, as for most symmetric cryptographic solutions, does not rely on formal security proofs but on the fact that since its release in the public domain 20 years ago no attack that performs better than an exhaustive search of the secret key has been found.

In order to render cryptographic applications easy and transparent for day to day usage, industry opted in the middle of the 1980's for a hardware solution that could fit inside a pocket: the smart card. Those cards are tiny computers that store secret keys and can perform cryptographic operations such as encryption, personal identification or authentication. The most famous ones are credit cards, the French Carte Vitale or SIM cards in our mobile phones. This solution represents a difficult cryptographic challenge as once deployed in the wild, it should guarantee the protection of the stored secrets from malicious adversaries that can have a total control of the hardware.

In the late 1980's, Kocher introduced the first physical attack against cryptographic hardware such as embedded systems. This kind of attack differs from the one in the classical model, namely the black-box model, where the adversary can only access the input and the output of the cryptosystem to recover its secret key. Through physical access to the device evaluating cryptographic operations, the adversary can obtain information on intermediate computations that directly depends on the secret key, and can hence break the underlying cryptosystem. In particular, the adversary can exploit side channels of the hardware such as the computation time, the power consumption of the device or its electro-magnetic emanation during the computation. Those attacks are particularly efficient and disastrous since one can easily get access to the target device such as smart cards, and utilize those side-channels.

Among the existing countermeasures against physical attacks to protect block cipher implementations, the most widely used is (higher-order) masking. It consists in splitting every sensitive variable in the cryptographic computation into several random values, denoted shares, so that at the end of the computation the sum of all the shares is equal to the expected result. This is a sound countermeasure as it has been formally proven that the higher the number of shares, the more difficult for the attacker to recover the secret key. However, applying higher-order masking to protect a cryptographic implementation implies a strong overhead in performance which can make its deployment in an industrial context unrealistic. In fact, the performance losses come from the fact that elementary arithmetic operations are replaced with tools that perform secure operations on encodings of sensitive variables. The linear operations, such as addition, have a computation time that is linear in the number of masks, whereas the computation time of non-linear operations such as multiplication is quadratic in the number of masks. Hence, the bottleneck of protecting encryption schemes with higher-order masking is to efficiently compute those non-linear operations, which in a standard block cipher are the substitution boxes (s-boxes). Many theoretical schemes have been proposed to tackle the issue of efficient masking schemes. However most of them are still considered impracticable as soon as the masking order grows.

In the last couple of years, a first step towards efficient implementation of higher-order masking has been made. The solution is to look at the s-box as a polynomial over a finite field and to find an efficient way to represent it so that the number of multiplications required for its evaluation is minimized. Two main approaches have been studied in the literature. The first one targets specific s-boxes (such as the one of the AES) to exploit the particularity of their algebraic structure and get very efficient representation in terms of number of multiplications involved. The second one tackles this issue on any kind of functions and this problem, I have first started doing an implementation case study of all existing masking schemes in ARM assembly. This study resulted in the first concrete comparisons between all the polynomial solutions proposed in the state-of-the-art. I have also investigated an alternative to polynomial methods for specific block ciphers such as the AES which is based on bitslicing at the s-box level. This led to significantly faster implementations compared to polynomial solutions. Following this line of work, I studied the use of bitslicing for random s-boxes and proposed a method to get a representation of Boolean circuit with a minimalized multiplicative complexity. This new method led to implementation that are asymptotically faster than the classical polynomial approach but less efficient for small masking orders. Hence, I proposed a more generic framework that allows to decompose any polynomial over any finite field of characteristic two and encapsulating the previous methods (the polynomial approach and the Boolean approach). In all produced implementations, and more specifically for the AES s-box with a bitslice strategy, I have chosen a very conservative approach of inserting a refresh gadget after each multiplication to guarantee the security of the implementation. This conservative choice was backed up by the state-of-the-art tools that analyze the security of a circuit. However, these tools happen to produce false negatives and can hence lead to overkill in security gadgets. Therefore, I proposed a formal verification tool that can exactly check the security of an s-box implementation for any masking order. This allows to reduce by a factor of two the randomness requirement for the implementation of the AES s-box.

Personal Contributions

The detailed list of my personal publications with full names, authors, and conferences is given at the end of the introduction. Here I briefly describe the goal of each of these papers, as well as the results they achieve. [GR16] In this paper, we present a generic method to find a Boolean representation of an s-box with efficient bitsliced higher-order masking. Specifically, we propose a method to construct a circuit with low multiplicative complexity. Compared to previous works on this subject, our method can be applied to any s-box of common size and not necessarily to small s-boxes. We use it to derive higher-order masked s-box implementations that achieve important performance gain compared to optimized state-of-the-art implementations.

Contributions in this Thesis

[GR17] In this paper, we investigate efficient higher-order masking techniques by conducting a case study on ARM architectures (the most widespread architecture in embedded systems). We follow a bottom-up approach by first investigating the implementation of the base field multiplication at the assembly level. Then we describe optimized low-level implementations of the ISW scheme and its variant (CPRR) due to Coron et al. (FSE 2013). Finally we present improved state-of-the-art polynomial decomposition methods for s-boxes with custom parameters and various implementation-level optimizations.

We also investigate an alternative to these methods which is based on bitslicing at the s-box level. We describe new masked bitslice implementations of the AES and PRESENT ciphers. These implementations happen to be significantly faster than (optimized) state-of-the-art polynomial methods.

[GRVV17] In this paper, we propose a generalized decomposition method for s-boxes that encompasses several previously proposed methods while providing new trade-offs. It allows to evaluate nλ-bit to mλ-bit s-boxes for any integers n, m, λ ≥ 1 by seeing it a sequence of m n-variate polynomials over F 2 λ and by trying to minimize the number of multiplications over F 2 λ .

[GJRS18] In this paper, we optimize the performance and compare several recent masking schemes in bitslice representation on 32-bit ARM devices, with a focus on multiplication.

Our main conclusion is that efficiency (or randomness) gains always come at a cost, either in terms of composability or in terms of resistance against horizontal attacks. Our evaluations should therefore allow a designer to select a masking scheme based on implementation constraints and security requirements. They also highlight the increasing feasibility of (very) high-order masking that are offered by increasingly powerful embedded devices, with new opportunities of high-security devices in various contexts.

[BGR18] In this paper, we exhibit the first method able to clearly state whether a shared circuit composed of standard gadgets (addition, multiplication and refresh) is t-probing secure or not. Given such a composition, our method either produces a probing-security proof (valid at any order) or exhibits a security flaw that directly imply a probing attack at a given order. Compared to the state-of-the-art tool maskComp, our method can drastically reduce the number of required refresh gadgets to get a probing security proof, and thus the randomness requirement for some secure shared circuits. We apply our method to a recent AES implementation secured with higher-order masking in bitslice and we show that we can save all the refresh gadgets involved in the s-box layer, which results in a significant performance gain.

Other contributions [GRV16]

In this paper, we extend existing attacks that exploit a few bits of the nonce to fully recover the secret key of elliptic-curve signature implementations protected with common countermeasures. Specifically, we extend the famous Howgrave-Graham and Smart lattice attack when the nonces are blinded by the addition of a random multiple of the elliptic-curve group order or by a random Euclidean splitting. We then assume that noisy information on the blinded nonce can be obtained through a template attack targeting the underlying scalar multiplication and we show how to characterize the obtained likelihood scores under a realistic leakage assumption. To deal with this scenario, we introduce a filtering method which given a set of signatures and associated likelihood scores maximizes the success probability of the lattice attack.

Our approach is backed up with attack simulation results for several signal-to-noise ratio of the exploited leakage.

[GJR18] In this paper, we show how to compute in the presence of noisy leakage with a leakage rate up to Õ(1) in complexity Õ(n). We use a polynomial encoding allowing quasilinear multiplication based on the fast Number Theoretic Transform (NTT). We first show that our scheme is secure in the random-probing model with leakage rate O(1/ log n). Using the reduction by Duc et al. this result can be translated in the noisy leakage model with a O(1/|F| 2 log n) leakage rate. However, as in the work of

Organization of this Thesis

Andrychowicz et al. [START_REF] Andrychowicz | Circuit Compilers with O(1/ log(n)) Leakage Rate[END_REF], our construction also requires |F| = O(n). In order to bypass this issue, we refine the granularity of our computation by considering the noisy leakage model on logical instructions that work on constant-size machine words. We provide a generic security reduction from the noisy leakage model at the logicalinstruction level to the random-probing model at the arithmetic level. This reduction allows us to prove the security of our construction in the noisy leakage model with leakage rate Õ(1).

Organization of this Thesis

In Chapter 2, I first detail all of the state-of-the-art solutions for masking schemes and some overview of the software choices we made throughout this thesis. In Chapter 3, I propose a generic decomposition method for any s-boxes to obtain efficient implementations. In Chapter 4, I formally define how the security of a circuit protected with higher-order masking can be reduced to problem of linear algebra. Then, I propose a formal verification tool that given a circuit outputs if an attack exists or not for any masking order. In Chapter 5, I detail optimisations at the algorithmic and assembly levels and give implementation results for the state-of-the-art methods as for the different schemes proposed in this thesis. Finally

Higher-Order Masking

Among the existing protection strategies against physical attacks, one of the most widely used relies on applying secret sharing at the implementation level, which is known as (higher-order) masking. This strategy achieves provable security in the so-called probing security model [START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF] and noisy leakage model [START_REF] Prouff | Masking against Side-Channel Attacks: A Formal Security Proof[END_REF][START_REF] Duc | Unifying Leakage Models: From Probing Attacks to Noisy Leakage[END_REF], which makes it a prevailing way to obtain secure implementations against side-channel attacks.

Description

Higher-order masking consists in sharing each internal variable x of a cryptographic computation into d random variables x 1 , x 2 , . . . , x d , called the shares and satisfying

x 1 + x 2 + • • • + x d = x, ( 2.1)
for some group operation +, such that any set of d -1 shares is randomly distributed and independent of x. In this manuscript, we will consider the prevailing Boolean masking which is based on the bitwise addition of the shares. It has been formally demonstrated that in the noisy leakage model, where the attacker gets noisy information on each share, the complexity of recovering information on x grows exponentially with the number of shares [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Prouff | Masking against Side-Channel Attacks: A Formal Security Proof[END_REF]. This number d, called the masking order, is hence a sound security parameter for the resistance of a masked implementation.

When dth-order masking is involved to protect a block cipher, a so-called dth-order masking scheme must be designed to enable the computation on masked data. To be sound, a dth order masking scheme must satisfy the two following properties:

• completeness: at the end of the encryption/decryption, the sum of the d shares must give the expected result;

• probing security: every tuple of d -1 or less intermediate variables must be independent of any sensitive variable.

Masking Block Ciphers

Most block cipher structures are composed of one or several linear transformation(s), and a non-linear function, the s-box (where the linearity is considered w.r.t. the bitwise addition). Computing a linear transformation x → (x) in the masking world can be done in O(d) complexity by applying to each share independently. This clearly maintains the probing security and the completeness holds by linearity since we have (x 1 )+ (x 2 )+• • •+ (x d ) = (x).

On the other hand, the non-linear operations (such as s-boxes) are more tricky to compute on the shares while ensuring completeness and probing security.

The state-of-the-art solutions to perform a multiplication between two masked variable x and y are all based on the following rationale:

1. Compute the d 2 cross products x i y j , for 1 ≤ i, j ≤ d; 2. Combine the cross products to get d output shares (in order to keep completeness); 3. Interleave fresh randomness in the previous step to avoid security flaws (in order to keep the probing security).

The main differences between all the solution in the literature are on how to implement this three different stages (see for instance [ISW03; BBP+16; BCPZ16; BDF+17]).

Implementation Transformation

We now describe how to transform the implementation of a block cipher into a secure implementation with higher-order masking.

Encoding

Let us first detail how to encode every input of the block cipher into masked variables. Let d be the masking order. A random d-sharing of an element x ∈ F 2 n is defined as follows:

Definition 2.1.1. Let x ∈ F 2 n and d ∈ N. A d-sharing of x is a tuple (x i ) d i=1 ∈ F d 2 n satisfying d i=1 x i = x.
A d-sharing is said to be uniform if, for a given x, it is uniformly distributed over the subspace of tuples satisfying x = d i=1 x i . A uniform sharing of x is such that any m-tuple of its shares x i is uniformly distributed over F m 2 for any m ≤ d. We further denote by Enc the probabilistic algorithm that maps an element x ∈ F 2 n to a random uniform d-sharing of x: Enc(x) → (x 1 , x 2 , . . . , x d ) .

(2.

2)

The corresponding decoding function Dec is defined as:

Dec x 1 , x 2 , . . . , x d := d i=1 x i (2.
3)

It is easy to check that we have Pr(Dec(Enc(x)) = x) = 1 for every x ∈ F 2 n .

Gadgets

To perform operations on masked variables, we define new building blocks called gadgets that perform a given operation on d-sharings. For instance, for some two-input operation * , a * -gadget takes two input sharings Enc(x 1 ) and Enc(x 2 ) and it outputs a sharing Enc(y) such that y = x 1 * x 2 . In this thesis, we will only consider gadgets that take one input (refresh, squaring, or evaluation of a quadratic function) or two inputs (addition, subtraction, multiplication). Specifically, a gadget performs several elementary operation on the shares of the inputs in order to get the desired outputs. We give in the following some examples of the most used gadgets in this thesis.

• Addition gadget. Let (x i ) d i=1 be a d-sharing of x and (y i ) d i=1 be a d-sharing of y. To compute a d-sharing (z i ) d i=1 of z = x + y, we simply compute: (z 1 , z 2 , . . . , z d ) ← (x 1 + y 1 , x 2 + y 2 , . . . , x d + y d )

• Field squaring gadget. Let (x i ) d i=1 be a d-sharing of x. To compute a d-sharing (z i ) d i=1 of z = x 2 , we simply compute: (z 1 , z 2 , . . . , z d ) ← (x 2 1 , x 2 2 , . . . , x 2 d )

• Field multiplication gadget. Let (x i ) d i=1 be a d-sharing of x and (y i ) d i=1 be a d-encoding of y. To compute a d-sharing (z i ) d i=1 of z = x • y, we simply compute: (z 1 , z 2 , . . . , z d ) ← IswMult((x 1 , x 2 , . . . , x d ), (y 1 , y 2 , . . . , y d ))

where IswMult denotes the secure multiplication proposed by Ishai, Sahai and Wager and described in the following section (Section 2.2). Other algorithms for this operation are described in Chapter 5.

Finally, another type of gadget exists that does not perform an operation on d-sharing but from an input d-sharing of a secret variable x, produces a fresh random uniform d-sharing of this variable. This type of gadgets is called refresh gadget and works as follows:

• Refresh gadget. Let (x i ) d i=1 be a d-sharing of x. To compute a d-sharing (z i ) d i=1 of z = x, we simply compute:

(z 1 , z 2 , . . . , z d ) ← Refresh(x 1 , x 2 , . . . , x d )

The details on how to compute soundly the Refresh function are detailed hereafter. Basically, the idea is to perform a secure multiplication between an encoding of x and an encoding of 1, namely the d-sharing (1, 0, . . . , 0).

It is easy to see that to remain efficient, the goal is to find a secure implementation of the block cipher that minimizes the number of field multiplication, quadratic evaluation and refresh gadgets, as they are the ones with a quadratic complexity in the masking order. In this manuscript, we will equally use the denomination of gadgets and secure operations (namely secure multiplication, secure evaluation, etc...).

Transformation

Now that we have defined encodings of sensitive variables and gadgets that perform simple operations on encodings, we can describe how to transform an implementation of a block cipher into a secure implementation protected with higher-order masking. To do so, every elementary operation in the implementation of the block cipher is transformed into the corresponding gadget working on d-sharings. Hence, the secure implementation takes as inputs d-sharings corresponding to each input of the block cipher thanks to the encoding function Enc. At the end of the computation, the output d-sharings of the computation are transfomed into the outputs of the block-ciphers with the help of the decoding function Dec. At carefully chosen positions in the secure implementation, refresh gadgets are inserted in order to ensure the security of the implementation (see Chapter 4 for more details).

Probing security

The probing security was first introduced in the seminal work of Ishai, Sahai, and Wager at Crypto 2003 [START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF]. It has been used to prove the security of several of the masking schemes in the literature. The definition of the probing security is defined as follows: Definition 2.1.2 (from [START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF]). Let d be the masking order and 1 ≤ t ≤ d an integer. A algorithm is t-probing secure if and only if any set of at most t intermediate variables is independent from the secret.

Informally speaking, in this model, we suppose that the adversary can probe up to t intermediate computations in the secure implementation. Namely, she can place up to t probes in any of the elementary operations performed by the gadgets. As each of the elementary operations in a gadget are performed on shares, the attacker recovers the knowledge of the one or two shares processed by the operation. This can be seen as probing one software instruction where one probe allows to recover information on either the source of the instruction (namely one or two operands) or the destination (namely the output of the instruction). Then with the information provided by her probes, the adversary tries to find some dependence with the secret. If such dependence does not exist, then the secure implementation is said to be t-probing secure. One of the strongest advantages of this model is that it allows to do elegant and easy proofs to ensure the security of the secure implementation.

This model is also practically relevant and realistic as it catches what an adversary performs with an higher-order side-channel attack. In fact, in a practical scenario the attacker tries to find points of interest in the leakage trace corresponding to the evaluation of the implementation. Then he tries to recombine these point of interests to find a statistical correlation with the secret. Hence, the point of interests can be seen as placing probes in the secure implementation.

Secure Non-Linear Operations

We now review some (widely used) constructions from the literature to compute masking gadgets for non-linear operations. The two operands x, y ∈ F 2 n of the non-linear operation gadget are represented as random d-sharings (x 1 , x 2 , . . . , x d ) and (y 1 , y 2 , . . . , y d ). Specifically, we focus on the scheme proposed by Ishai, Sahai, and Wagner (ISW scheme) for the secure multiplication [START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF], and its extension by Coron, Prouff, Rivain and Roche (CPRR scheme) to secure any quadratic function [CPRR14; CPRR15].

Ishai-Sahai-Wagner Multiplication

From two d-sharings (x 1 , x 2 , . . . , x d ) and (y 1 , y 2 , . . . , y d ), the ISW scheme computes an output d-sharing (z 1 , z 2 , . . . , z d ) as follows:

1. for every 1 ≤ i < j ≤ d, sample a random value r i,j over F 2 n ; 2. for every

1 ≤ i < j ≤ d, compute r j,i = (r i,j + x i • y j ) + x j • y i ; 3. for every ≤ i ≤ d, compute z i = x i • y i + j =i r i,j .
One can check that the output (z 1 , z 2 , . . . , z d ) is well a d-sharing of the product z = x • y. We indeed have i z i = i,j x i • y j = ( i x i )( j y j ) since every random value r i,j appears exactly twice in the sum and hence vanishes.

Mask refreshing

The ISW multiplication was originally proved probing secure at the order t = (d -1)/2 (and not d -1 as one would expect with masking order d). The security proof was later made tight under the condition that the input d-sharings are based on independent randomness [START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF]. In some situations, this independence property is not satisfied. For instance, one might have to multiply two values x and y where x = (y) for some linear operation . In that case, the shares of x are usually derived as x i = (y i ), which clearly breaches the required independence of input shares. To deal with this issue, one must refresh the sharing of x. However, one must be careful doing so since a bad refreshing procedure might introduce a flaw [START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF]. A sound method for mask-refreshing consists in applying an ISW multiplication between the sharing of x and the tuple (1, 0, 0, . . . , 0) [START_REF] Duc | Unifying Leakage Models: From Probing Attacks to Noisy Leakage[END_REF][START_REF] Barthe | Verified Proofs of Higher-Order Masking[END_REF]. This gives the following procedure:

1. for every 1 ≤ i < j ≤ d, randomly sample r i,j over F 2 n and set r j,i = r i,j ; 2. for every 1 ≤ i ≤ d, compute

x i = x i + j =i r i,j .
It is not hard to see that the output sharing (x 1 , x 2 , . . . , x d ) well encodes x. One might think that such a refreshing implies a strong overhead in performance (almost as performing two multiplications) but this is still better than doubling the number of shares (which roughly quadruples the multiplication time). Moreover, we show in Chapter 5 that the implementation of such a refreshing procedure can be very efficient in practice compared to the ISW multiplication.

Coron-Prouff-Rivain-Roche evaluation

The CPRR scheme was initially proposed in [START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF] as a variant of ISW to securely compute multiplications of the form x → x • (x) where is linear, without requiring refreshing. It was then shown in [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF] that this scheme (in a slightly modified version) could actually be used to securely evaluate any quadratic function f over F 2 n . The method is based on the following equation From a d-sharing (x 1 , x 2 , . . . , x d ), the CPRR scheme computes an output d-sharing (y 1 , y 2 , . . . , y d ) as follows:

f (x 1 + x 2 + • • • + x d ) = 1≤i<j≤d f (x i + x j + s i,j ) + f (x j + s i,j ) + f (x i + s i,j ) + f (s i,j ) + d i=1 f (x i ) + (d + 1 mod 2) • f (0) (2.4) which holds for every (x i ) i ∈ (F 2 n ) d , every (s i,j ) 1≤i<j≤d ∈ (F 2 n ) d(d-
1. for every 1 ≤ i < j ≤ d, sample two random values r i,j and s i,j over F 2 n , 2. for every

1 ≤ i < j ≤ d, compute r j,i = r i,j + f (x i + s i,j ) + f (x j + s i,j ) + f ((x i + s i,j ) + x j ) + f (s i,j ) , 3. for every 1 ≤ i ≤ d, compute y i = f (x i ) + j =i r i,j , 4. if d is even, set y 0 = y 0 + f (0).
According to Equation (2.4), we then have

d i=1 y i = f d i=1 x i )
, which shows that the output sharing (y 1 , y 2 , . . . , y d ) well encodes y = f (x).

In [START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF][START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF] it is argued that in the gap where the field multiplication cannot be fully tabulated (2 2n elements is too much) while a function f : F 2 n → F 2 n can be tabulated (2 n elements fit), the CPRR scheme is (likely to be) more efficient than the ISW scheme. This is because it essentially replaces (costly) field multiplications by simple look-ups.

Polynomial Methods for S-boxes

An approach to reduce the number of multiplication involved in the evaluation of the s-box in masking schemes is to consider the s-box as a polynomial over a finite field. This way, the problem of efficiently evaluating the non-linear part becomes equivalent to studying fast evaluation of polynomials over F 2 n . In [START_REF] Carlet | Higher-Order Masking Schemes for S-Boxes[END_REF], Carlet, Goubin, Prouff, Quisquater and Rivain, were the first to give a countermeasure based on polynomial representation of the s-box and proposed two methods to evaluate it. Then in [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF], Coron, Roy and Vivek extend their approach to propose a new generic method for fast evaluation of polynomials over binary fields.

In [START_REF] Carlet | Higher-Order Masking Schemes for S-Boxes[END_REF] the notion of cyclotomic class is introduced, which will be used for the CRV method.

C α = {α.2 i mod 2 n -1 ; i ∈ [0; n -1]}
A cyclotomic class allows to get efficient masked operations: a power x α can be computed from x β without any non-linear multiplications if α and β are in the same cyclotomic class since it only requires squarings.

Coron-Roy-Vivek method

The CRV method was proposed by Coron, Roy and Vivek in [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF]. It consists in representing an s-box S(x) over

F 2 n [x]/(x 2 n -x) as S(x) = t-1 i=1 p i (x) • q i (x) + p t (x) , ( 2.5)
where p i (x) and q i (x) are polynomials with monomials in x L for some set of cyclotomic classes

L = C α 1 =0 ∪ C α 2 =1 ∪ C α 3 ∪ . . . ∪ C α such that for every i ≥ 3, α i = α j + α k mod 2 n -1 for some j, k < i (or more generally α i = 2 w • α j + α k mod 2 n -1 with k ∈ [[0, n -1]]
). Such polynomials can be written as:

p i (x) = j=2 l i,j (x α j ) + c i,0 and q i (x) = j=2 l i,j (x α j ) + c i,0 , (2.6)
where the l i,j , l i,j are linearized polynomials over F 2 n [x]/(x 2 nx) and where the c i,0 , c i,0 are constants in F 2 n . In [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF], the authors explain how to find such a representation. In a nutshell, one randomly picks the q i 's and searches for p i 's satisfying Equation (2.5). This amounts to solving a linear system with 2 n equations and t • |L| unknowns (the coefficients of the p i 's). Note that when the choice of the classes and the q i 's leads to a solvable system, then it can be used with any s-box (since the s-box is the target vector of the linear system). We then have two necessary (non sufficient) conditions for such a system to be solvable, and one additional for the sake of efficiency:

1. the set L of cyclotomic classes is such that t • |L| ≥ 2 n
2. all the monomials can be reached by multiplying two monomials from x L , that is

{x i • x j mod (x 2 n -x) ; i, j ∈ L} = x [[0,2 n -1]]
3. every class (but C 0 = {0}) have the maximal cardinality of n. Under this additional constraint, Condition 1 leads to the following inequality:

t • 1 + n • ( -1)) ≥ 2 n .
Minimizing the number of nonlinear multiplications while satisfying this constraint leads to parameters t ≈ 2 n /n and ≈ 2 n /n. Based on the above representation, the s-box can be evaluated using ( -2) + (t -1) nonlinear multiplications (plus some linear operations). In a first phase, one generates the monomials corresponding to the cyclotomic classes in L. Each x α i can be obtained by multiplying two previous x α j and x α k (where x α j might be squared w times if necessary). In the masking world, each of these multiplications is performed with a call to ISW. The polynomials p i (x) and q i (x) can then be computed according to Equation (2.6). In practice the linearized polynomials are tabulated so that at masked computation, applying a l i,j simply consists in performing a look-up on each share of the corresponding x α j . In the second phase, one simply evaluates Equation (2.5), which takes t -1 nonlinear multiplications plus some additions. We recall that in the masking world, linear operation such as additions or linearized polynomial evaluations can be applied on each share independently yielding an O(d) complexity, whereas nonlinear multiplications are computed by calling ISW with an O(d 2 ) complexity. The performance of the CRV method is hence dominated by the + t -3 calls to ISW.

Algebraic decomposition method

The algebraic decomposition method was proposed by Carlet, Prouff, Rivain and Roche in [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF]. It consists in using a basis of polynomials (g 1 , g 2 , . . . , g r ) that are constructed by composing polynomials f i as follows

g 1 (x) = f 1 (x) g i (x) = f i g i-1 (x) (2.7)
The f i 's are of given algebraic degree s. In our context, we consider the algebraic decomposition method for s = 2, where the f i 's are (algebraically) quadratic polynomials. The method then consists in representing an s-box S(x) over

F 2 n [x]/(x 2 n -x) as S(x) = t i=1 p i q i (x) + r i=1 i g i (x) + 0 (x) , ( 2.8)
with

q i (x) = r j=1 i,j g j (x) + i,0 (x) , (2.9)
where the p i 's are quadratic polynomials over F 2 n [x]/(x 2 nx), and where the i 's and the i,j 's are linearized polynomials over

F 2 n [x]/(x 2 n -x).
As explain in [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF], such a representation can be obtained by randomly picking some f i 's and some i,j 's (which fixes the q i 's) and then searching for p i 's and i 's satisfying Equation (2.8). As for the CRV method, this amounts to solving a linear system with 2 n equations where the unknowns are the coefficients of the p i 's and the i 's. Without loss of generality, we can assume that only 0 has a constant term. In that case, each p i is composed of 12 n(n -1) monomials, and each i is composed of n monomials (plus a constant term for 0 ). This makes a total of 1 2 n (n -1) • t + n • (r + 1) unknown coefficients. In order to get a solvable system we hence have the following condition: (1) 1 2 n (n -1) • t + n • (r + 1) ≥ 2 n . A second condition is (2) 2 r+1 ≥ n, otherwise there exists some s-box with algebraic degree greater than 2 r+1 that cannot be achieved with the above decomposition i.e. the obtained system is not solvable for every target S.

Based on the above representation, the s-box can be evaluated using r + t evaluations of quadratic polynomials (the f i 's and the q i 's). In the masking world, this is done with the help of CPRR evaluations. The rest of the computation are additions and (tabulated) linearized polynomials which are applied to each share independently with a complexity linear in d. The cost of the algebraic decomposition method is then dominated by the r + t calls to CPRR.

Specific Methods for AES and PRESENT

Specific methods that target the algebraic structure of a particular s-box have also been proposed in the literature. In this thesis, we mainly focus on the s-box of the AES and of PRESENT as they are popular block-ciphers, the former beeing the standard for encryption and the latter one of the most efficient lightweight block-ciphers.

Rivain-Prouf Decomposition

Many works have studied masking schemes for the AES s-box and most of them are based on its peculiar algebraic structure. This s-box is defined as the composition of the inverse function x → x 254 over F 2 8 and an affine function: S(x) = Aff(x 254 ). The affine function being straightforward to mask with linear complexity, the main issue is to design an efficient masking scheme for the inverse function. In [START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF], Rivain and Prouff introduced the approach of using an efficient addition chain for the inverse function that can be implemented with a minimal number of ISW multiplications. They show that the exponentiation to the power of 254 can be performed with 4 nonlinear multiplications plus some (linear) squarings, resulting in a scheme with 4 ISW multiplications. In [START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF], Coron et al. propose a variant where two of these multiplications are replaced CPRR evaluations (of the functions x → x 3 and x → x 5 ). 1 This was further improved by Grosso et al. in [START_REF] Grosso | Efficient Masked S-Boxes Processing -A Step Forward[END_REF] who proposed the following addition chain leading to 3 CPRR evaluations and one ISW multiplications:

x 254 = (x 2 • ((x 5 ) 5 ) 5 ) 2 . This addition chain has the advantage of requiring a single function x → x 5 for the CPRR evaluation (hence a single LUT for masked implementation). Moreover it can be easily checked by exhaustive search that no addition chain exists that trades the last ISW multiplication for a CPRR evaluation.

Kim-Hong-Lim (KHL) method

This method was proposed in [START_REF] Kim | A Fast and Provably Secure Higher-Order Masking of AES S-Box[END_REF] as an improvement of the RP scheme. The main idea is to use the tower field representation of the AES s-box [START_REF] Satoh | A Compact Rijndael Hardware Architecture with S-Box Optimization[END_REF] in order to descend from F 2 8 to F 2 4 where the multiplications can be fully tabulated. Let δ denote the isomorphism mapping F 2 8 to (F 2 4 )2 with F 2 8 ≡ F 2 4 [x]/p(x), and let γ ∈ F 2 8 and λ ∈ F 2 4 such that p(x) = x 2 + x + λ and p(γ) = 0. The tower field method for the AES s-box works as follows:

1. a h γ + a l = δ(x), a h , a l ∈ F 2 4 4. a h = d a j ∈ F 2 4 2. d = λ a 2 h + a l • (a h + a l ) ∈ F 2 4 5. a l = d (a h + a l ) ∈ F 2 4 3. d = d 14 ∈ F 2 4 6. S(x) = Aff(δ -1 (a h γ + a l )) ∈ F 2 8
At the third step, the exponentiation to the 14 can be performed as d 14 = (d3 ) 4 • d 2 leading to one CPRR evaluation (for d → d 3 ) and one ISW multiplication (plus some linear squarings). 2 This gives a total of 4 ISW multiplications and one CPRR evaluation for the masked AES implementation.

Method for PRESENT

As a 4-bit s-box, the PRESENT s-box can be efficiently secured with the CRV method using only 2 ISW multiplications, where the field multiplications are fully tabulated. The algebraic decomposition method would give a less efficient implementation with 3 CPRR evaluations. Another possible approach is to use the fact that the PRESENT s-box can be expressed as the composition of two quadratic functions S(x) = F • G(x). This representation (which is recalled in Table 2.1) was put forward by Poschmann et al. in [PMK+11] to design an efficient threshold implementation of PRESENT. In our context, this representation can be used to get a masked s-box evaluation based on 2 CPRR evaluations. Note that this method is asymptotically slower than CRV with 2 full-table ISW multiplications. However, due to additional linear operations in CRV, F • G might actually be better for small values of d.

Table 2.1: PRESENT s-box S(x) = F • G(x).

Bitslice Strategy

Bitslicing is an implementation strategy initially proposed by Biham in [START_REF] Biham | A Fast New DES Implementation in Software[END_REF]. It consists in performing several parallel evaluations of a Boolean circuit in software where the logic gates can be replaced by instructions working on registers of several bits. As nicely explained in [START_REF] Matsui | On the Power of Bitslice Implementation on Intel Core2 Processor[END_REF], "in the bitslice implementation one software logical instruction corresponds to simultaneous execution of hardware logical gates, where is a register size [...] Hence bitslice can be efficient when the entire hardware complexity of a target cipher is small and an underlying processor has many long registers."

In the context of higher-order masking, bitslicing can be used at the s-box level to perform several secure s-box computations in parallel. One then needs a compact Boolean representation of the s-box, and more importantly a representation with the least possible nonlinear gates. Specifically, based on a Boolean circuit for an s-box S, one can perform parallel evaluations of S in software by replacing each gate of the circuit with the corresponding bitwise instruction, where is the bit-size of the underlying CPU architecture. It results that the only nonlinear operations in the parallel s-box processing are bitwise AND instructions between -bit registers which can be efficiently secured using the ISW scheme. Such an approach achieves important speedup compared to polynomial methods since (i) ISW-based ANDs are substantially faster than ISW-based field multiplications in practice, (ii) all the s-boxes within a cipher round are computed in parallel. Such an approach was applied in [START_REF] Grosso | LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations[END_REF] to design block ciphers with efficient masked computations. To the best of our knowledge, it has never been applied to obtain fast implementations of classical block ciphers such as AES or PRESENT.

ISW Logical AND

The ISW scheme can be easily adapted to secure a bitwise logical AND between two mbit registers. 1. for every 1 ≤ i < j ≤ d, sample an m-bit random value r i,j , 2. for every

1 ≤ i < j ≤ d, compute r j,i = (r i,j ⊕ a i ∧ b j ) ⊕ a j ∧ b i , 3. for every 1 ≤ i ≤ d, compute c i = a i ∧ b i ⊕ j =i r i,j .
If the architecture size is , we can hence perform secure logical AND in parallel. Moreover a logical AND is a single instruction so we expect the above ISW logical AND to be faster than the ISW field multiplications.

ARM Assembly

In this thesis most of the implementation produced to benchmark and compare the different masking schemes are developed in ARM assembly, a low level implementation language widely used in mobile devices and smart cards. Most ARM cores are RISC processors composed of sixteen 32-bit registers, labeled R0, R1, . . . , R15. Registers R0 to R12 are known as variable registers and are available for computation. 3 The three last registers are usually reserved for special purposes: R13 is used as the stack pointer (SP), R14 is the link register (LR) storing the return address during a function call, and R15 is the program counter (PC). The link register R14 can also be used as additional variable register by saving the return address on the stack (at the cost of push/pop instructions). The gain of having a bigger register pool must be balanced with the saving overhead, but this trick enables some improvements in many cases.

In ARM v7, most of the instructions can be split into the following three classes: data instructions, memory instructions, and branching instructions. The data instructions are the arithmetic and bitwise operations, each taking one clock cycle (except for the multiplication which takes two clock cycles). The memory instructions are the load and store (from and to the RAM) which require 3 clock cycles, or their variants for multiple loads or stores (n + 2 clock cycles). The last class of instructions is the class of branching instructions used for loops, conditional statements and function calls. These instructions take 3 or 4 clock cycles. This classification is summarized in Table 2.2. One important specificity of the ARM assembly is the barrel shifter allowing any data instruction to shift one of its operands at no extra cost in terms of clock cycles. Four kinds of shifting are supported: the logical shift left (LSL), the logical shift right (LSR), the arithmetic shift right (ASR), and the rotate-right (ROR). All these shifting operations are parameterized by a shift length in [ [1,32]] (except for the logical shift left LSL which lies in [[0, 31]]). The latter can also be relative by using a register but in that case the instruction takes an additional clock cycle.

Another feature of ARM assembly that can be very useful is the branch predication. This feature allows any instruction to be conditionally executed with respect to a (data dependent) flag value (e.g. the carry flag, the zero flag, etc.). In the context of secure embedded implementations, we have to ensure a data-independent operation flow in order to prevent timing and/or simple side-channel attacks. We must therefore avoid data-dependent conditional branches. For this reason we do not make use of the branch predication, except when it involves non-sensitive data such as loop counters.

Open Problems

As explained in this chapter, gadgets performing operation on d-sharing are the ground building block of masking schemes. As the multiplication gadgets require a quadratic number of field operations with respect to the masking order, an interesting line of work could be to find efficient ways to perform those operations. In fact, field multiplications are the core operations in the evaluation of multiplication gadgets. As soon as the field size grows, field multiplication can not be fully tabulated due to the size of the look-up tables. Hence, studying and optimizing at the implementation level different approaches to perform those field multiplications, such as the Karatsuba multiplication or the exp-log multiplication, can lead to efficient multiplication gadgets with different time and memory trade-offs.

In the past few years, several new secure multiplication schemes have been proposed based on the ISW multiplication method to get more efficient (at the cost of security) or more secure (at the cost of effiency) multiplication gadgets. However, no work made a concrete comparison between these different secure multiplications to better understand the performance gains and overheads that correspond to their different security guarantees. Moreover, several lines of work are based on the fact that the CPRR evaluation scheme should outperform the ISW multiplication scheme to justify their efficiency. However, no concrete comparisons at an implementation level have been made to corroborate the state-of-the-art intuition.

One of the missing part of all the proposed masking schemes to get an efficient polynomial decomposition of an s-box is a concrete comparison of them in practice. In fact, no work has produced a fair implementation of all the solutions and analysed the performance results to have clear insight on which method to use. It also seems like going down in a smaller field to perform the decomposition allows to get more efficient implementation results. Pushing forward this approach could be of interest by going over the Boolean field. Under this field, the costly field multiplication becomes a simple bitwise AND and with a bitslice strategy this could allow some significant improvement in the performance gain.

The idea of working on smaller field could also be ported to generic methods. In fact, the CRV method could be extend to any finite field to produce more efficient decomposition. One could produce generic methods for any s-box that is defined with respect to the s-box input and output and the field size. Then, the developer could instantiate the decomposition with these parameters on any finite field of characteristic 2 to get the most suitable decomposition depending on his requirements. For instance, as the bitslice strategy seems to be promising to obtain efficient masking schemes, it can be interesting to have a decomposition method for generic s-boxes over the Boolean field.

Finally, most of the masking schemes are very consuming in terms of randomness requirement due to the multiplication gadgets but also the refresh gadgets. Minimizing the randomness consumption is hence an important line of work in order to produce efficient implementations of masking schemes. Several formal verification tools have been developed in the recent years to ensure the probing security of masking schemes by placing refresh gadgets at carefully chosen positions. However, it sometimes happen that those tools lead to add refresh gadgets at uncessary positions (in terms of probing security). It can be interesting to find a formal method that allows to guarantee the probing security of an implementation with a tight number of inserted refresh gadgets, compared to existing solutions, in order to lower the randomness usage.

Introduction

As explained in Chapter 2, the most widely-used solution is to consider the representation as a polynomial function over a finite field (using Lagrange's interpolation theorem) and to find an efficient way to evaluate this polynomial. In order to obtain an efficient implementation of an s-box protected with higher-order masking, the first challenge is to find an efficient representation of it, where the number of multiplications involved in the evaluation is minimized.

The first generic method to mask any s-box at any masking order d was proposed in 2012 by Carlet, Goubin, Prouff, Quisquater and Rivain [START_REF] Carlet | Higher-Order Masking Schemes for S-Boxes[END_REF] (following prior work by Rivain and Prouff for the AES block cipher [START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF]). The core idea is to split the evaluation of the polynomial representation of the s-box into simple operations over F 2 n (namely, addition, multiplication by a constant, squaring and regular multiplication of two distinct elements), where n denotes the number of input bits of the s-box. Among these operations, only the regular multiplication of two distinct elements is non-linear (since squaring over a characteristic 2 finite field is linear), and one can use the secure multiplication algorithms to evaluate them [RP10; BBP+16; BCPZ16]. Carlet et al. [START_REF] Carlet | Higher-Order Masking Schemes for S-Boxes[END_REF] defined the masking complexity (also known as multiplicative complexity and non-linear complexity) of an s-box as the minimal number of such multiplications necessary to evaluate the corresponding polynomial and they adapted known methods for polynomial evaluation based on cyclotomic classes (see [START_REF] Carlet | Higher-Order Masking Schemes for S-Boxes[END_REF] for details).

This technique was later improved by Roy and Vivek in [START_REF] Roy | Analysis and Improvement of the Generic Higher-Order Masking Scheme of FSE 2012[END_REF] using cyclotomic cosets addition chains. They notably presented a polynomial evaluation method for the DES s-boxes that requires 7 non-linear multiplications (instead of 10 in [START_REF] Carlet | Higher-Order Masking Schemes for S-Boxes[END_REF]). They also presented a lower-bound on the length of such a chain and showed that the multiplicative complexity of the DES s-boxes is lower bounded by 3. In 2014, Coron, Roy and Vivek [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF] proposed a heuristic method which may be viewed as an extension of the ideas developed in [START_REF] Carlet | Higher-Order Masking Schemes for S-Boxes[END_REF] and [START_REF] Roy | Analysis and Improvement of the Generic Higher-Order Masking Scheme of FSE 2012[END_REF]. The so-called CRV method considers the s-box as a polynomial over F 2 n and has heuristic multiplicative complexity O(2 n/2 / √ n) instead of O(2 n/2 ) proven multiplicative complexity for the previous methods. They also proved a lower bound of Ω(2 n/2 / √ n) on the multiplicative complexity of any generic method to evaluate n-bit s-boxes. For all the tested s-boxes their method is at least as efficient as the previous proposals and it often requires fewer non-linear multiplications (e.g. only 4 for the DES s-boxes).

Approach

In this chapter, we propose a generalized decomposition method for s-boxes. More precisely, in our approach any nλ-bit s-box for some integers n ≥ 1 and λ ≥ 1 can be seen as a polynomial (or a vector of m ≥ 1 polynomials) over F n 2 λ . We first start by defining the multiplicative complexity for s-boxes and some lower bounds. We prove a lower bound of Ω(2 λn/2 m/λ) for the complexity of any method to evaluate nλ-bit to mλ-bit s-boxes. We then describe our generalized decomposition method for which we provide concrete parameters to achieve a decomposition for several triplets (n, m, λ) and for exemplary s-boxes of popular block ciphers (namely PRESENT [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF], SC2000 [START_REF] Shimoyama | The Block Cipher SC2000[END_REF], CLEFIA [START_REF] Shirai | The 128-Bit Blockcipher CLEFIA (Extended Abstract)[END_REF] and KHAZAD [START_REF] Barreto | The Khazad Legacy-Level Block Cipher[END_REF]).

Depending on the s-box, our generalized method allows one to choose the parameters n, m and λ to obtain the best possible s-box decomposition in terms of multiplications over F 2 λ . In particular, for 8 × 8 s-boxes, the CRV decomposition method [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF] (n = 1, m = 1, λ = 8) is a special case of this generalized decomposition method. We also investigate a particular case of our decomposition, the Boolean case, where n = 8, m = 8, λ = 1. For this specific instantiation, we can apply a bitslicing strategy for the implementation part and some improvement tailored for the Boolean field.

Multiplicative Complexity of Generic S-boxes

Notations and notions

Let λ be a positive integer. Then F 2 λ denotes the finite field with 2 λ elements. Let F λ,n be the set of functions from F n 2 λ to F 2 λ . Using Lagrange's interpolation theorem, any function f ∈ F λ,n can be seen as a multivariate polynomial over

F 2 λ [x 1 , x 2 , . . . , x n ]/(x 2 λ 1 -x 1 , x 2 λ 2 - x 2 , . . . , x 2 λ n -x n ): f (x) = u∈[0,2 λ -1] n a u x u , ( 3.1)
where

x = (x 1 , x 2 , . . . , x n ), x u = x u 1 1 • x u 2 2 • . . . • x un n , and a u ∈ F 2 λ for every u = (u 1 , . . . , u n ) ∈ [0, 2 λ -1] n .
The multiplicative complexity of a function in F λ,n (also called the non-linear complexity) is defined as follows: Definition 3.3.1. Let f be a function in F λ,n . The multiplicative complexity of f is the minimal number of F 2 λ -multiplications required to evaluate it.

In the following, an s-box S is characterized with respect to 3 parameters: the number of input elements n; the number of output elements m; and the bit-size of the elements λ. In other words, an s-box with λn input bits and λm outputs bits is represented as follows:

∀x ∈ F n 2 λ , S(x) = (f 1 (x), f 2 (x), . . . , f m (x)), (3.2)
where the functions f 1 , f 2 , . . . , f m ∈ F λ,n are called the coordinate functions of S.

The multiplicative complexity of an s-box S : x → (f 1 (x), f 2 (x) . . . , f m (x)), denoted C(S), is naturally defined as the multiplicative complexity of the family of its coordinate functions. We shall also call the multiplicative complexity of a given circuit the actual number of multiplication gates involved in the circuit, so that the multiplicative complexity of a circuit gives an upper bound of the multiplicative complexity of the underlying s-box.

Multiplicative Complexity Lower Bound for S-boxes

Roy and Vivek presented in [START_REF] Roy | Analysis and Improvement of the Generic Higher-Order Masking Scheme of FSE 2012[END_REF] a lower-bound on the length of cyclotomic coset addition chains and used it to derive a logarithmic lower bound on the multiplicative complexity of an s-box (i.e. on the minimal number of such multiplications necessary to evaluate the corresponding polynomial). As mentioned in Chapter 2.3, Coron et al. [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF] improved this lower bound and showed that the non-linear complexity of any generic method to evaluate n-bit s-boxes when seen as a polynomial defined over F 2 n is in Ω(2 n/2 / √ n). In the following section, we generalize their approach and provide a new lower bound on the multiplicative complexity of a sequence of n-variate polynomials over F 2 λ . Following [START_REF] Roy | Analysis and Improvement of the Generic Higher-Order Masking Scheme of FSE 2012[END_REF], we define the multiplicative complexity notion for such a sequence as follows:

Definition 3.3.2 (Polynomial chain). Let λ ≥ 1, n ≥ 1, l ≥ 1 and m ≥ 1 be four integers and let f 1 , . . . , f m ∈ F 2 λ [x 1 , . . . , x n ] be a sequence of n-variate polynomials over F 2 λ . A polynomial chain #" π for (f 1 , . . . , f m ) is a sequence #" π = (π i ) i∈{-n,..., } and a list (i 1 , . . . , i m ) ∈ {-n, . . . , } m with π -n = x n , π 1-n = x n-1 , . . . , π -1 = x 1 , π 0 = 1, π i j = f j (x 1 , . . . , x n ) mod (x 2 λ 1 + x 1 , . . . , x 2 λ n + x n ), ∀j ∈ {1, .
. . , m}, and such that for every i ∈ {1, . . . , }, one of the following condition holds:

1. there exist j and k in {-n, . . . , i -1} such that π i = π j • π k ; 2. there exist j and k in {-n, . . . , i -1} such that π i = π j + π k ; 3. there exists j in {-n, . . . , i -1} such that π i = π 2 j ;

4. there exists j in {-n, . . . , i -1} and α ∈ F 2 λ such that

π i = α • π j .
Given such a polynomial chain #" π for (f 1 , . . . , f m ), the multiplicative complexity of #" π is the number of times the first condition holds in the whole chain #" π . The multiplicative complexity of (f with multiplicative complexity M(f 1 , . . . , f m ) = r for some integer r ≥ 1. If we consider only the non-linear operations in a polynomial chain of minimal multiplicative complexity #" π = (π i ) i∈{-n,..., } , we can see that there exist indices m 0 , m 1 , . . . , m n+r+(m-1) with

m i ∈ {-n, . . . , } for i ∈ {0, . . . , n + r + (m -1)} such that • π m k = π -k-1 = x k+1 for k ∈ {0, . . . , n -1}); (i.e. construction of the mononials in F 2 λ [x 1 , . . . , x n ].)
• for k ∈ {n, . . . , n + r -1}, there exist field elements

β k , β k ∈ F 2 λ and β k,i,j , β k,i,j ∈ F 2 λ for (i, j) ∈ {0, . . . , k -1} × {0, . . . , λ -1} such that π m k =   β k + k-1 i=0 λ-1 j=0 β k,i,j π 2 j m i   •   β k + k-1 i=0 λ-1 j=0 β k,i,j π 2 j m i   mod (x 2 λ 1 + x 1 , . . . , x 2 λ n + x n ) (i.
e. construction of elements in the span of previously constructed π m k );

• for k ∈ {n + r, . . . , n + r + (m -1)} there exist field elements β k ∈ F 2 λ and β k,i,j ∈ F 2 λ for (i, j) ∈ {0, . . . , n + r -1} × {0, . . . , λ -1} such that

f k+1-(n+r) = π m k = β k + n+r-1 i=0 λ-1 j=0 β k,i,j π 2 j m i mod (x 2 λ 1 + x 1 , . . . , x 2 λ n + x n ) (i.
e. construction of the coordinate functions with the span of previously constructed

π m k ).
The total number of parameters β in this evaluation scheme of #" π is simply equal to:

n+r-1 k=n 2 • (1 + k • λ) + m(1 + (n + r) • λ) = r 2 λ +
, . . . , f m ∈ F 2 λ [x 1 , . . . , x n ] defined mod(x 2 λ 1 + x 1 , . . . , x 2 λ n + x n ) is ((2 λ ) 2 nλ
) m , in order to be able to evaluate all such polynomials with at most r non-linear multiplications, a necessary condition is to have

r 2 λ + r(λm + 2λn -λ + 2) + λmn + m ≥ m2 nλ
and therefore

r 2 λ + r(λm + 2λn -λ + 2) -(m2 nλ -λmn -m) ≥ 0. Eventually, we obtain r ≥ λ4m2 nλ + (λm + 2λn -λ + 2) 2 -(λm + 2λn -λ + 2) 2λ , ( 3.3)
and

r ≥ √ 4λm2 nλ -2(λm + 2λn -λ + 2) 2λ ≥ m2 nλ λ -(2n + m -1).

Some results for the Boolean case.

In the Boolean case (when λ = 1), an s-box can be seen as Boolean circuit. We give hereafter some results from the state-of-the-art on the multiplicative complexity of s-boxes in the Boolean case. We shall also call multiplicative complexity of a given circuit the actual number of multiplication gates involved in the circuit, so that the multiplicative complexity of a circuit gives an upper bound of the multiplicative complexity of the underlying s-box. The best known circuit for the AES s-box in terms of multiplicative complexity is due to Boyar et al. [START_REF] Boyar | Logic Minimization Techniques with Applications to Cryptology[END_REF]. This circuit achieves a multiplicative complexity of 32 which was obtained by applying logic minimization techniques to the compact representation of the AES s-box by Canright [START_REF] Canright | A Very Compact S-Box for AES[END_REF] (and saving 2 multiplications compared to the original circuit).

In [START_REF] Courtois | Exact Logic Minimization and Multiplicative Complexity of Concrete Algebraic and Cryptographic Circuits[END_REF], Courtois et al. use SAT-solving to find the multiplicative complexity of small s-boxes. Their approach consists in writing the Boolean system obtained for a given s-box and a given (target) multiplicative complexity t as a SAT-CNF problem. For each value of t, the solver either returns a solution or a proof that no solution exists, so that the multiplicative complexity is the first value of t for which a solution is returned. They apply this approach to find Boolean circuits with the smallest multiplicative complexity for a random 3 × 3 s-box (meant to be used in CTC2 [START_REF] Courtois | CTC2 and Fast Algebraic Attacks on Block Ciphers Revisited[END_REF]), the 4 × 4 s-box of PRESENT, and for several sets of 4 × 4 s-boxes proposed for GOST [START_REF] Poschmann | 256 Bit Standardized Crypto for 650 GE -GOST Revisited[END_REF]. These results have recently been extended by Stoffelen who applied the Courtois et al. approach to find optimal circuits for various 4 × 4 and 5 × 5 s-boxes [START_REF] Ko Stoffelen | Optimizing S-Box Implementations for Several Criteria Using SAT Solvers[END_REF]. These results are summarized in Table 3.1, where for comparison we also include known results for AES [START_REF] Boyar | Logic Minimization Techniques with Applications to Cryptology[END_REF] and some bitslice-oriented block ciphers [DPAR00; GLSV15]. The main limitation of the SAT-solving approach is that it is only applicable to small s-boxes due to the combinatorial explosion of the underlying SAT problem, and getting the decomposition of an s-box of size e.g. n = 8 seems out of reach. Moreover, the method is not generic in the sense that the obtained decomposition stands for a single s-box and does not provide an upper bound for the multiplicative complexity of s-boxes of a given size.

Parallel Multiplicative Complexity

We introduce hereafter the notion of parallel multiplicative complexity for s-boxes. The kparallel multiplicative complexity of an s-box is the least number of k-parallel multiplications required to compute it. We formalize this notion hereafter:

Definition 3.3.4. The k-parallel multiplicative complexity M (k) (f 1 , f 2 , . . . , f m ) of a family of functions f 1 , f 2 , . . . , f m ∈ F λ,n
, is the minimal integer t for which there exist functions g i , h i ∈ F λ,n for i ∈ [ [1, tk]] such that:

     g 1 , h 1 , g 2 , h 2 , . . . , g k , h k ∈ 1, x 1 , x 2 , . . . , x n , ∀i ∈ [[1, t -1]] : g ik+1 , h ik+1 , . . . , g (i+1)k , h (i+1)k ∈ 1, x 1 , x 2 , . . . , x n , g 1 • h 1 , . . . , g ik • h ik (3.4) and f 1 , f 2 , . . . , f m ∈ 1, x 1 , x 2 , . . . , x n , g 1 • h 1 , . . . , g tk • h tk . (3.5)
The main motivation for introducing this notion comes from the following scenario. Assume we want to perform t s-box computations on an -bit architecture, where > t. Since each register contains only λ bits elements out of , one can perform up to τ = /λ multiplication with a single call to a parallelized version of the multiplication algorithm (modulo some packing of the operands and unpacking of the results, see Section 5.3.2.6 of Chapter 5). This would in turn enable to perform k = t/τ s-box computations in parallel. If the used decomposition of the s-box has a k-parallel multiplicative complexity of s, then the resulting implementation involve s multiplication instructions. This number of instructions is the main efficiency criterion when such an implementation is protected with higher-order masking which makes the k-parallel multiplicative complexity an important parameter for an s-box in this context. Remark 3.3.5. Note that in the Boolean case, if grows significantly the k-parallel multiplicative complexity is equivalent to the notion of multiplicative depth of a Boolean circuit.

As an illustration, we give in Figure 3.1 gives a sorted version of the AES circuit by Boyar et al. [START_REF] Boyar | Logic Minimization Techniques with Applications to Cryptology[END_REF] optimized with respect to the parallel multiplicative complexity. One can observed 6 groups of AND gates: a first group of 8 AND gates (in blue), 4 groups of 2 AND gates (in orange), and a last group of 16 AND gates (in blue). Each group can be fully parallelized but two different groups cannot be computed in parallel due to dependence between variables. We deduce that we can evaluate the circuit based on sixteen 2-parallel AND gates, ten 4-parallel AND gates, seven 8-parallel AND gates, and six 16-parallel AND gates.

Chapter 3 Decomposition

-top linear transformationy 14 = x 3 ⊕ x 5 y 1 = t 0 ⊕ x 7 y 15 = t 1 ⊕ x 5 y 17 = y 10 ⊕ y 11 y 13 = x 0 ⊕ x 6 y 4 = y 1 ⊕ x 3 y 20 = t 1 ⊕ x 1 y 19 = y 10 ⊕ y 8 y 12 = y 13 ⊕ y 14 y 2 = y 1 ⊕ x 0 y 6 = y 15 ⊕ x 7 y 16 = t 0 ⊕ y 11 y 9 = x 0 ⊕ x 3 y 5 = y 1 ⊕ x 6 y 10 = y 15 ⊕ t 0 y 21 = y 13 ⊕ y 16 y 8 = x 0 ⊕ x 5 t 1 = x 4 ⊕ y 12 y 11 = y 20 ⊕ y 9 y 18 = x 0 ⊕ y 16 t 0 = x 1 ⊕ x 2 y 3 = y 5 ⊕ y 8 y 7 = x 7 ⊕ y 11 -middle non-linear transformation -

t 2 =

Generic Framework

In this section, we study a generic decomposition framework to evaluate any n λ-bit to m λ-bit function over a finite field F 2 λ , for any n, m, λ ≥ 1. Depending on the function, we can choose the parameters n, m and λ in order to obtain the best possible decomposition in terms of multiplicative complexity.

Decomposition of a Single Coordinate Function

Let us define the linear power class of a function φ ∈ F λ,n , denoted by C φ , as the set

C φ = {φ 2 i : i = 0, . . . , λ -1}. (3.6)
C φ corresponds to the set of functions in F λ,n that can be computed from φ using only the squaring operation. It is not hard to see that the set of {C φ } φ are equivalence classes partitioning F λ,n . For any set B ⊆ F λ,n , let us define the linear power closure of B as the set

B = φ∈B C φ ,
and the linear span of B as the set

B = φ∈B a φ φ a φ ∈ F 2 λ .
Let f be a function in F λ,n . The proposed decomposition makes use of a basis of functions B ⊆ F λ,n and consists in writing f as:

f (x) = t-1 i=0 g i (x) • h i (x) + h t (x), (3.7)
where g i , h i ∈ B and t ∈ N. By definition, the functions g i and h i can be written as

g i (x) = |B| j=1 j (ϕ j (x)) and h i (x) = |B| j=1 j (ϕ j (x)),
where the j , j are linearized polynomials over F λ,1 (i.e. polynomials for which the exponents of all the monomials are powers of 2) and where {ϕ j } 1≤j≤|B| = B. We now explain how to find such a decomposition by solving a linear system. Solving a linear system. In the following, we shall consider a basis B such that 1 ∈ B and we will denote B * = B \ {1} = {φ 1 , φ 2 , . . . , φ |B|-1 }. We will further heuristically assume

|C φ i | = λ for every i ∈ {1, 2, . . . , |B| -1}. We then get |B| = 1 + λ|B * | = 1 + λ(|B| -1).
We first sample t random functions g i from B . This is simply done by picking t • |B| random coefficients a i,0 , a i,j,k of F 2 λ and setting

g i = a i,0 + j,k a i,j,k φ 2 k j for every i ∈ [0, t -1] where 1 ≤ k ≤ λ and 1 ≤ j ≤ |B| -1.
Then we search for a family of t + 1 functions {h i } i satisfying Equation (3.7). This is done by solving the following system of linear equations over F 2 λ :

A • c = b (3.8)
where b = (f (e 1 ), f (e 2 ), . . . , f (e 2 nλ )) T with {e i } = F n 2 λ and where A is a block matrix defined as

A = (1|A 0 |A 1 | • • • |A t ), (3.9)
where 1 is the all-one column vector and where

A i = (A i,0 |A i,1 | • • • |A i,|B|-1 ), (3.10)
with

A i,0 = (g i (e 1 ), g i (e 2 ), . . . , g i (e 2 nλ )) T , (3.11) for every i ∈ [0, t], with A i,j =            φ j (e 1 ) • g i (e 1 ) φ 2 j (e 1 ) • g i (e 1 ) ... φ 2 λ-1 j (e 1 ) • g i (e 1 ) φ j (e 2 ) • g i (e 2 ) φ 2 j (e 2 ) • g i (e 2 ) ... φ 2 λ-1 j (e 2 ) • g i (e 2 ) . . . . . . . . . . . . φ j (e 2 nλ ) • g i (e 2 nλ ) φ 2 j (e 2 nλ ) • g i (e 2 nλ ) ... φ 2 λ-1 j (e 2 nλ ) • g i (e 2 nλ )            , ( 3.12)
for every i ∈ [0, t -1] and j ∈ [1, |B| -1], and with

A t,j =            φ j (e 1 ) φ 2 j (e 1 ) ... φ 2 λ-1 j (e 1 ) φ j (e 2 ) φ 2 j (e 2 ) ... φ 2 λ-1 j (e 2 ) . . . . . . . . . . . . φ j (e 2 nλ ) φ 2 j (e 2 nλ ) ... φ 2 λ-1 j (e 2 nλ )            , (3.13) for every j ∈ [1, |B| -1].
It can be checked that the vector c, solution of the system, gives the coefficients of the h i 's over the basis B (plus the constant term in first position). A necessary condition for this system to have a solution whatever the target vector b (i.e. whatever the coordinate function f ) is to get a matrix A of full rank. In particular, the following inequality must hold:

(t + 1)|B| + 1 ≥ 2 nλ . (3.14)
Another necessary condition to get a full-rank matrix is that the squared linear power closure B × B spans the entire space F λ,n . More details about the choice of such basis are discussed in the following.

S-box Decomposition

Let S : x → (f 1 (x), f 2 (x), . . . , f m (x)) be an s-box as defined in Section 3.3.1. We could apply the above decomposition method to each of the m coordinate functions f i , which could roughly result in multiplying by m the multiplicative complexity of a single function in F λ,n . As suggested in [START_REF] Boyar | Logic Minimization Techniques with Applications to Cryptology[END_REF] to construct an efficient circuit for the inversion in F 16 , we can actually do better: the product involved in the decomposition of a coordinate function can be added to the basis for the subsequent decompositions. Indeed, the term g i,j (x) • h i,j (x) involved in the computation of f i (x) can be reused in the computation of the following f i+1 (x), . . . , f m (x). In our decomposition process, this means that the g j • h i,j functions can be added to the basis for the decomposition of the next coordinate functions f i+1 , . . . , f m . Specifically, we start with some basis B 1 and, for every i ≥ 1, we look for a decomposition

f i (x) = t i -1 j=0 g i,j (x) • h i,j (x) + h i,t i (x), (3.15)
where t i ∈ N and g i,j , h i,j ∈ B i . Once such a decomposition has been found, we carry on with the new basis B i+1 defined as:

B i+1 = B i ∪ {g i,j • h i,j } t i -1 j=0 . (3.16)
This update process implies that, for each decomposition, the basis grows and hence the number t i of multiplicative terms in the decomposition of f i might decrease. In this context, the necessary condition on the matrix rank (see Equation (3.14)) is different for every i. In particular, the number t i of multiplications at step i satisfies:

t i ≥ 2 nλ -1 λ|B * i | + 1 -1 , (3.17)
where as above B * i stands for B i \ {1}.

Optimal parameters

Assuming that satisfying the lower bound on t i (see Equation (3.17)) is sufficient to get a full-rank system, we can deduce optimal parameters for our generalized decomposition method. Specifically, if we denote

s i = |B * i |, we get a sequence (s i ) i that satisfies    s 1 = r + n s i+1 = s i + t i with t i = 2 nλ -1 λs i +1 -1 , ( 3.18)
for i from 1 to m -1, where r denotes the number of multiplications involved in the construction of the first basis B 1 (the n free elements of B 1 being the monomials x 1 , x 2 , . . . ,

x n ). From this sequence, we can determine the optimal multiplicative complexity of the method C(S) which then satisfies

C(S) = min r≥r 0 (r + t 1 + t 2 + • • • + t m ) , (3.19)
where r 0 denotes the minimal value of r for which we can get an initial basis B 1 satisfying the spanning property (that is

B 1 × B 1 = F λ,n
) and where the t i 's are viewed as functions of r according to the sequence Equation (3.18). Table 3.2 provides a set of optimal parameters r, t 1 , t 2 , . . . , t m and corresponding C(S) for several s-box sizes and several parameters λ and n = m (as for bijective s-boxes). For the sake of completeness, we included the extreme cases n = 1, i.e. standard CRV method [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF], and λ = 1, i.e. Boolean case [GR16]. We obtain the same results as in [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF] for the standard CRV method. For the Boolean case, our results slightly differ from [GR16]. This is due to our improved generation of B 1 and to our bound on the t i 's (see Equation (3.17)) which is slightly more accurate than in [GR16].

Basis Selection

Let us recall that the basis B 1 needs to be such that the squared basis B 1 × B 1 spans the entire space F λ,n , i.e. B 1 × B 1 = F λ,n in order to have a solvable linear system. This is called the spanning property in the following. This property can be rewritten in terms of linear algebra. For every S ⊆ F λ,n , let us define Mat(S) as the (λn × |S|)-matrix for which each column corresponds to the evaluation of one function of S in every point of

F n 2 λ , that is Mat(S) =           ϕ 1 (e 1 ) ϕ 2 (e 1 ) ... ϕ |S| (e 1 ) ϕ 1 (e 2 ) ϕ 2 (e 2 ) ... ϕ |S| (e 2 ) . . . . . . . . . . . . ϕ 1 (e 2 nλ ) ϕ 2 (e 2 nλ ) ... ϕ |S| (e 2 nλ )           , ( 3.20)
where {ϕ 1 , ϕ 2 , . . . , ϕ |S| } = S. Then, we have

B 1 × B 1 = F λ,n ⇐⇒ rank(Mat(B 1 × B 1 )) = 2 λn . (3.21)
To construct the basis B 1 , we proceed as follows. We start with the basis composed of all monomials of degree 1 plus unity, i.e. the following basis:

B 1 = {1, x 1 , x 2 , . . . , x n }. (3.22)
Then, we iterate B 1 ← B 1 ∪ {φ • ψ}, where φ and ψ are randomly sampled from B 1 until reaching a basis with the desired cardinality and satisfying rank(Mat(B 1 × B 1 )) ≥ 2 λn . We add the constraint that, at each iteration, a certain amount of possible products are tried and only the best product is added to the basis, namely the one inducing the greatest increase in the rank of Mat(B 1 × B 1 ). To summarize, the construction of the basis B 1 is given in Algorithm 1.

Algorithm 1 B 1 construction algorithm

Input: Parameters λ, n, and N Output:

A basis B 1 such that B 1 × B 1 = F λ,n 1: B 1 = {1, x 1 , x 2 . . . , x n } 2: rank = 0 3: while rank< 2 nλ do 4: for i = 1 to N do 5: φ, ψ $ ← -B 1 6: S i ← B 1 ∪ {φ • ψ} 7: r i ← rank(Mat(S i × S i )) 8: j ← argmax r i 9:
if r j = rank then return error 10:

rank ← r j 11:

B 1 ← S j return B 1
Table 3.3 gives the size of the smallest randomized basis we could achieve using Algorithm 1 for various parameters. The number of tries was N = 1000 before adding a product of random linear combination to the current basis.

Application

Boolean case

We first study our decomposition method for the case where we want to decompose s-boxes over the Boolean field, namely the case where n = m and λ = 1. We first exhibit an improvement, called the rank drop improvement, in order to obtain decomposition leading to more efficient implementations and then provide some experimental results on several s-boxes. Finally, we exploit the fact that our method is highly parallelizable to get more efficient decompositions on the Boolean field.

Exploiting rank drops

The rank drop improvement is based on the observation that even if the matrix A is not full-rank, the obtained system can still have a solution for a given s-box. Specifically, if A is of rank 2 nδ then we should get a solution for one s-box out of 2 δ in average. Hence, instead of having t i satisfying the condition (t i + 1)|B| ≥ 2 n , we allow a rank drop in the system of equations, by taking t i ≥ 2 n -δ |B i | -1 for some integer δ for which solving 2 δ systems is affordable. We hence hope to get smaller values of t i by trying 2 δ systems. Note that heuristically, we can only hope to achieve the above bound if δ is slightly lower than the maximal rank 2 n (e.g. δ ≤ 2 n 4 ). As an illustration, Table 3.4 provides the obtained parameters for a δ up to 32. In the last column, we can see that the rank-drop improvement (theoretically) saves a few multiplications.

Remark 3.5.1. When λ = 1, the probability of getting a solvable system should be around ( 12 ) δ , which means that by trying about 2 δ random systems we should find a solution with a rank drop. For other values of λ, the possible gain from this improvement becomes marginal as the number of random systems to try grows exponentially in λ. Therefore we choose to only consider the rank-drop improvement for λ = 1.

In practice, we observe that the condition (t i + 1)|B i | ≥ 2 nδ is not always sufficient to get a matrix A of rank 2 nδ. We shall then start with t i = 2 n -δ |B i | -1 and try to solve α • 2 δ systems, for some constant α. In case of failure, we increment t i and start again until a solvable system is found. The overall process is summarized in Algorithm 2. The execution time of Algorithm 2 is dominated by the calls to a linear-solving procedure (Step 6). The number of trials is in o(n α 2 δ ), where the constant in the o(•) is the average incrementation of t i (i.e. the average number of times Step 13 is executed per i). In our experiments, we observed that the optimal value of t 1 = 2 n -δ s 1 -1 is rarely enough to get a solvable system for f 1 . This is because we start with the minimal basis as in the single-Boolean-function case. We hence have a few incrementations for i = 1. On the other hand, the next optimal t i 's are often enough or incremented a single time.

Experimental results

Selected s-boxes. We used Algorithm 2 to obtain the decomposition of various n × n s-boxes for n ∈ [ [4,8]], namely the eight 4 × 4 s-boxes of Serpent [ABK98], the s-boxes S 5 (5 × 5) and S 6 (6 × 6) of SC2000 [START_REF] Shimoyama | The Block Cipher SC2000[END_REF], the 8 × 8 s-boxes S 0 and S 1 of CLEFIA [START_REF] Shirai | The 128-Bit Blockcipher CLEFIA (Extended Abstract)[END_REF], and the 8 × 8 s-box of Khazad [START_REF] Barreto | The Khazad Legacy-Level Block Cipher[END_REF]. The obtained results are summarized in Table 3.5. Note that we chose these s-boxes to serve as examples for our decomposition method. Some of them may have a mathematical structure allowing more efficient decomposition (e.g. the CLEFIA S 0 s-box is based on the inversion over F 256 and can therefore be computed with a 32-multiplication circuit as the AES). We further give in appendix the obtained 2-parallel decomposition for the s-boxes of SC2000, CLEFIA and Khazad.

We observe that Algorithm 2 (almost) achieves the optimal parameters given in Table 3.4 for n ∈ {4, 5, 6}. For n = 8, we only get the optimal multiplicative complexity of the generalized method but without the rank-drop improvement. This might be due to the fact that when n increases the value of δ becomes small compared to 2 n and the impact of exhaustive search is lowered.

Random s-boxes. We also applied Algorithm 2 on random s-boxes to observe the average Algorithm 2 Boolean decomposition with exhaustive search Input: An s-box S ≡ (f 1 , f 2 , . . . , f m ), parameters s 1 = |B 1 |, α, and δ Output: A basis B 1 and the functions {h i,j } i,j and {g i,j } i,j

1: i = 1; t 1 = 2 n -δ |s 1 | -1 2: do α • 2 δ times: 3: if i = 1 then randomly generate B 1 ⊇ B 0 with |B 1 | = s 1 4: randomly sample t i functions g i,j ∈ B i 5: compute the corresponding matrix A 6: if A • c = b f i has a solution then 7:
store the corresponding functions {h i,j } j and {g i,j } j 8:

if i = n then return B 1 , {h i,j } i,j , {g i,j } i,j 9: B i+1 = B i ∪ {h i,j • g i,j } j ; t i+1 = 2 n -δ |B i+1 | -1; i++ 10: goto Step 2 11:
endif 12: enddo 13: t i ++; goto Step 2 effectiveness of our method. Specifically, we generated 1000 s-boxes (using the Knuth shuffle algorithm) and we decomposed each of these s-boxes using Algorithm 2 with the following parameters: n = 8, α = 8 and δ = 16. The obtained multiplicative complexities were 59 (for 9 s-boxes), 60 (for 536 s-boxes), and 61 (455 s-boxes), which is equivalent to what we got for Khazad and CLEFIA in half of the trials and better (by 1 or 2 multiplications) for the rest. These results are summarized in Table 3.6.

We also looked at the influence of the two parameters α and δ on our decomposition method. For this purpose, we applied Algorithm 2 to 1000 random s-boxes with smaller parameters α and δ. The results are summarized in Figure 3.2. We observe a mean difference of 1.68 multiplications between the two extreme pairs of parameters i.e. (α, δ) = (4, 4) and (α, δ) = (16, 8). As expected, we also see that the δ parameter has more impact than the α parameter.

Parallelization

The decomposition method over F 2 is highly parallelizable. In practice, most SPN block ciphers have a nonlinear layer applying 16 or 32 s-boxes and most processors are based on a 32-bit or a 64-bit architecture. Therefore we shall focus our study on the k-parallel multiplicative complexity of our method for k ∈ {2, 4}.

The parallelization of the method is slightly tricky since all the multiplicative terms g i,j • h i,j cannot be computed in parallel. Indeed, the resulting products are fed to the basis so that they are potentially involved in the linear combinations producing the next functions g i+1,j , h i+1,j , . . . , g m,j , h m,j . In order to fully parallelize our method we customize Algorithm 2 as follows. We keep a counter q of the number of products added to the basis. Each time a new f i+1 is to be decomposed, if the current counter q is not a multiple of k, then the first q 0 products g i+1,j • h i+1,j will be bundled with the last q 1 products g i,j • h i,j in the parallel Table 3.5: Achieved parameters for several s-boxes.

|B 1 | r t 1 , t 2 , . . . , t n C(S) n = 4 Serpent S 2 7 2 1, 1, 0, 1 5 Serpent S 7 7 2 1, 0, 1, 1 5 Serpent S 1 , S 3 -S 6 , S 8 7 2 1, 1, 1, 1 6 n = 5 SC2000 S 5 11 5 2, 2, 1,
q 0 = (k -q) mod k; q 1 = q mod k. ( 3.23)
We must then ensure that the functions {g i+1,j , h i+1,j } q 0 -1 j=0 are independent of the few last products {g i,j •h i,j } t i -1 j=t i -q 1 . This can be done at no cost for the g i+1,j 's which can be generated without the last q 1 products, and this adds a constraint on the linear system for the first q 0 searched h i+1,j functions.

We observed in our experiments that for small values of k, the parallelization constraint has a limited impact on Algorithm 2. We actually obtained the same parameters as in Table 3.5 for all the selected s-boxes (Serpent, SC2000, CLEFIA, and Khazad) for a parallelization degree of k = 2, except for the s-box S 3 of Serpent that requires 1 more multiplication. The decomposition for the s-boxes of SC2000, CLEFIA and Khazad given in appendix have been obtained for the 2-parallel version of Algorithm 2. For these decompositions, all the multiplications can be bundled by pair.

We also experimented on random s-boxes for parallelization degrees k = 2 and k = 4 with parameters n = 8, α = 8, δ = 16. These results are summarized in Table 3.7. We see that the obtained parallel multiplicative complexity is only one or two parallel multiplications more than this optimal C(S)/k (and sometimes achieves the optimal).

We obtained that 90% of the s-boxes have a 2-parallel multiplicative complexity of 31 (which means one more multiplication is needed in 50% of the case with respect to the theoretical optimum) and 32 for 10% of the cases. the random s-boxes are evaluated with 16 multiplications, which means 1 more multiplication in 50% of the cases.

Median case

We now report some experimental results achieved using our generalized decomposition method on different values for n, m, and λ. Table 3.8 compares the achievable parameters vs. the optimal estimate for random s-boxes. Note that in the table, the parameters |B 1 |, r, t 1 , t 2 , . . . , t n correspond to the parameters in the achievable decomposition for randomly chosen s-boxes. The last column gives the probability of obtaining a successful decomposition for random s-boxes and for randomly chosen coefficients in the basis computation as well as the decomposition step. In all the cases we made 10 trials to compute the probabilities (except for 8-bit s-boxes over F 2 2 where 100 trials were made). In the experiments, successive basis elements were added by products of random linear combinations of elements from the current basis. The basis B 1 was chosen such that the corresponding matrix for the first coordinate function resulted in full rank (implying that the spanning property of the basis B 1 was satisfied). The basis was successively updated with the t i products formed in the decomposition step of the ith coordinate function. While the parameter t 1 is invariant of the chosen s-box, the other t i are indeed dependent on it. As we see from Table 3.8, the probabilities increase with the size of the field used for the decomposition.

Table 3.9 gives the concrete parameters to achieve decomposition for s-boxes of popular block ciphers (namely PRESENT [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF], DES S1 and S8 [START_REF]Data Encryption Standard[END_REF], SC2000 S6 [START_REF] Shimoyama | The Block Cipher SC2000[END_REF], CLEFIA S0 and S1 [START_REF] Shirai | The 128-Bit Blockcipher CLEFIA (Extended Abstract)[END_REF] and KHAZAD [START_REF] Barreto | The Khazad Legacy-Level Block Cipher[END_REF]). Note that for all the cases considered the parameters from Table 3.9 yield a decomposition. As above, the last column of the table gives the success probability over the random choice of the coefficients in the basis computation as well as the decomposition step. Here again, in all the cases we made 10 trials to compute the probabilities (except for 8-bit s-boxes over F 2 2 where 100 trials were made). Table 3.9: Achievable parameters to decompose specific s-boxes.

s-box (λ, n) |B 1 | r t 1 , t 2 , . . . , t n C(S) proba. 4-bit s-boxes PRESENT [BKL+07]
(2,2) 5 2 1,1 4 0.3 (6,4)-bit s-boxes DES S1 [START_REF]Data Encryption Standard[END_REF] (2,3) 7 4 5,2 11 0.3 DES S8 [START_REF]Data Encryption Standard[END_REF] (2,3) 7 4 5,2 11 0.5 6-bit s-boxes SC2000 S6 [START_REF] Shimoyama | The Block Cipher SC2000[END_REF] (

Full-field case

We now focus on the full-field case, namely when n = m = 1. This case is basically the CRV decomposition method introduced in Section 2.3. In this case, we propose an improvement where we had some small structure to the basis to get a more efficient software implementation. Note that for this specific case, namely n = 1, the linear power classes introduced in Section 3.4 are equivalent to cyclotomic classes introduced in Section 2.3.

Improving CRV with CPRR

As suggested in [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF], CRV can be improved by using CPRR evaluations instead of ISW multiplications in the first phase of CRV. In Chapter 5, we demonstrate that depending on the field size the CPRR is indeed faster than ISW (i.e. when full-table multiplication cannot be afforded). Instead of multiplying two previously computed powers x α j and x α k , the new power

x α i is derived by applying the quadratic function x → x 2 w +1 for some w ∈ [[1, λ -1]].
In the masking world, securely evaluating such a function can be done with a call to CPRR. The new chain of cyclotomic classes

C α 1 =0 ∪ C α 2 =1 ∪ C α 3 ∪ . . . ∪ C α must then satisfy α i = (2 w + 1)α j for some j < i and w ∈ [[1, λ -1]].
The different conditions to get a solvable system in the case of the CRV decomposition (see Section 2.3) are recalled here:

1. the set L of cyclotomic classes is such that t • |L| ≥ 2 n ;
2. all the monomials can be reached by multiplying two monomials from x L , that is

{x i • x j mod (x 2 n -x) ; i, j ∈ L} = x [[0,2 n -1]] ; and
3. every class (but C 0 = {0}) have the maximal cardinality of n. Under this additional constraint, Condition 1 leads to the following inequality:

t • 1 + n • (r -1)) ≥ 2 n .
We have implemented the search of such chains of cyclotomic classes satisfying conditions 1,2, and 3 . We were able to validate that for every λ ∈ [ [4,10]] and for the parameters (r, t) given in [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF], we always find such a chain leading to a solvable system. For the sake of code compactness, we also tried to minimize the number of CPRR exponents 2 w + 1 used in these chains (since in practice each function x → x 2 w +1 is tabulated). For λ ∈ {4, 6, 7} a single CPRR exponent (either 3 or 5) is sufficient to get a satisfying chain (i.e. a chain of cyclotomic classes fulfilling the above conditions and leading to a solvable system). For the other values of λ, we could prove that a single CPRR exponent does not suffice to get a satisfying chain. We could then find satisfying chains for λ = 5 and λ = 8 using 2 CPRR exponents (specifically 3 and 5). For λ > 8, we tried all the pairs and triplets of possible CPRR exponents without success, we could only find a satisfying chain using the 4 CPRR exponents 3, 5, 9 and 17.

Optimizing CRV parameters.

We can still improve CRV by optimizing the parameters (r, t) depending on the ratio θ = C CPRR C ISW , where C CPRR and C ISW denote the costs of ISW and CPRR respectively. The cost of the CRV method satisfies

C CRV = (r -2) C CPRR + (t -1) C ISW = (r -2) • θ + t -1) C ISW ≥ (r -2) • θ + 2 λ (r -1) • λ + 1 -1 C ISW ,
where the inequality holds from conditions 1 and 3. This lower bound ensures that the system contains enough unknowns to be solvable. In practice, it was observed in [START_REF] Coron | Fast Evaluation of Polynomials over Binary Finite Fields and Application to Side-Channel Countermeasures[END_REF] that this is a sufficient condition most of the time to get a solvable system (and our experiments corroborate this fact). Our optimized version of CRV hence consists in using the parameter r minimizing the above lower bound and the corresponding t = (λ = 10).

As an illustration, Figure 3.3 plots the optimal parameter r with respect to the ratio θ for several values of λ. We observe that a ratio slightly lower than 1 implies a change of optimal parameters for all values of n except 4 and 9. In other words, as soon as CPRR is slightly faster than ISW, using a higher r (i.e. more cyclotomic classes) and therefore a lower t is a sound trade. For our implementations of ISW and CPRR (see Chapter 5.3.2), we obtained a ratio θ greater than 1 only when ISW is based on the full-table multiplication. In that case, no gain can be obtain from using CPRR in the first phase of CRV, and one should use the original CRV parameters. On the other hand, we obtained θ-ratios of 0.88 and 0.75 for half-table-based ISW and exp-log-based ISW respectively. For the parallel versions of the secure multiplications, these ratios become 0.69 (half-table ISW) and 0.58 (exp-log ISW). We can observe from Figure 3.3 that for θ ∈ [0.58, 0.88], the optimal CRV parameters are constants for all values of λ except for λ = 9 for which a gap occurs around θ ≈ 0.66. Figures 3.4-3.6 plot the d 2 constant in the CRV cost obtained with these ratios for different values of r for λ = 6, λ = 8, and λ = 10. These figures clearly illustrate the asymptotic gain that can be obtained by using optimized parameters.

For λ ∈ {6, 8, 10}, we checked whether we could find satisfying CPRR-based chains of cyclotomic classes, for the obtained optimal parameters. For λ = 6, the optimal parameters are (r, t) = (5, 3) (giving 3 CPRR plus 2 ISW) which are actually the original CRV parameters. We could find a satisfying chain for these parameters. For λ = 8, the optimal parameters are (r, t) = (9, 4) (giving 7 CPRR plus 3 ISW). For these parameters we could not find any satisfying chain. We therefore used the second best set of parameters that is (r, t) = (8, 5) (giving 6 CPRR plus 4 ISW) for which we could find a satisfying chain. For λ = 10, the optimal parameters are (r, t) = (14, 8) (giving 12 CPRR plus 7 ISW). For these parameters we could neither find any satisfying chain. So once again, we used the second best set of parameters, that is (r, t) = (13, 9) (giving 11 CPRR plus 8 ISW) and for which we could find a satisfying chain. All the obtained satisfying CPRR-based chains of cyclotomic classes are given in Table 3.10.

C 0 ∪ C 1 ∪ C 3 3 5 4 3 C 0 ∪ C 1 ∪ C 3 ∪ C 15 3,5 6 5 3 C 0 ∪ C 1 ∪ C 5 ∪ C 11 ∪ C 31 5 7 6 4 C 0 ∪ C 1 ∪ C 5 ∪ C 19 ∪ C 47 ∪ C 63 5 8 7 6 C 0 ∪ C 1 ∪ C 5 ∪ C 25 ∪ C 95 ∪ C 55 ∪ C 3 3,5 9 9 8 C 0 ∪ C 1 ∪ C 9 ∪ C 17 ∪ C 25 ∪ C 51 ∪ C 85 ∪ C 103 ∪ C 127 3,5,9,17 10 11 11 C 0 ∪ C 1 ∪ C 3 ∪ C 9 ∪ C 17 ∪ C 45 ∪ C 69 ∪ C 85 ∪ C 207 ∪ C 219 ∪ C 447 3,5,9,17 Optimized CRV parameters 8 8 5 C 0 ∪ C 1 ∪ C 5 ∪ C 25 ∪ C 95 ∪ C 55 ∪ C 3 ∪ C 9 3,5 10 13 9 C 0 ∪ C 1 ∪ C 3 ∪ C 15 ∪ C 17 ∪ C 27 ∪ C 51 ∪ C 57 ∪ C 85 ∪ C 123 ∪ C 159 ∪ C 183 ∪ C 205 3,5,9,17
Table 3.11 compares the performances of the original CRV method and the improved versions for our implementation of ISW (half-table and exp-log variants for the field multiplication. See Chapter 5 for more details) and CPRR. 1 For the improved methods, we give the ratio of asymptotic performances with respect to the original version. This ratio ranks between 79% and 94% for the improved version and between 75% and 93% for the improved version with optimized parameters.

Introduction

The second challenge we want to address in this thesis is the one of the composition of masked operations. In fact, once a sound representation of the s-box function is found, one need to carefully study how to implement it. As shown in Chapter 2, the independence property, i.e. the probing security, of the masking scheme can be compromised with misuse multiplications. Hence, one must carefully place some refresh gadgets in the implementation to produce fresh encodings of the sensitive variables. However, the use of such gadgets comes at a price in randomness consumption and efficiency.

In the past couple of years, several formal tools have been developed to evaluate the probing security of implementations at a given masking order. Among the most efficient ones, Barthe et al. developed maskVerif [START_REF] Barthe | Verified Proofs of Higher-Order Masking[END_REF] and Coron developed CheckMasks [START_REF] Coron | Formal Verification of Side-channel Countermeasures via Elementary Circuit Transformations[END_REF]. Both tools take as input a shared circuit and return a formal security proof when no attack is found. However, this evaluation is not tight and false negatives may occur and hence imply the addition of unnecessary refresh gadgets. Moreover, while such tools are very convenient to evaluate the security of concrete implementations, they suffer from an important limitation which is their exponential complexity in the size of the circuit and consequently in the masking order. As a result, these tools are impractical beyond a small number of shares (typically d = 5). In a recent work, Bloem et al. [START_REF] Bloem | Formal Verification of Masked Hardware Implementations in the Presence of Glitches[END_REF] further developed a new tool to verify the security of masked implementations subject to glitches, which is an important step towards provable and practical security of hardware implementations. However this tool still suffers from the same efficiency limitations as the previous ones.

The method of Barthe et al. [START_REF] Barthe | Strong Non-Interference and Type-Directed Higher-Order Masking[END_REF] allows one to safely compose t-NI and t-SNI gadgets and get probing security at any order. Nevertheless, it is not tight and makes use of more refresh gadgets than required. In many contexts, randomness generation is expensive and might be the bottleneck for masked implementations. For instance, Journault and Standaert describe an AES encryption shared at the order d = 32 for which up to 92% of the running time is spent on randomness generation [START_REF] Journault | Very High Order Masking: Efficient Implementation and Security Evaluation[END_REF]. In such a context, it is fundamental to figure out whether the number of t-SNI refresh gadgets inserted by Barthe et al.'s tool maskComp is actually minimal to achieve t-probing security. In this Chapter, we find out that it is not and we provide a new method which exactly identifies the concrete probing attacks in a Boolean shared circuit.

Let us take a simple example. We consider the small randomized circuit referred to as Circuit 1 and illustrated in Figure 4 4.2. However, it can be verified that for any masking order t, the initial circuit is t-probing secure without any additional refresh gadget. Therefore, in the following, this Chapter aims to refine the state-of-the-art method [START_REF] Barthe | Strong Non-Interference and Type-Directed Higher-Order Masking[END_REF] to only insert refresh gadgets when absolutely mandatory for t-probing security.

More specifically, the contribution of this chapter can be summarized as follows:

(1) We introduce formal definitions of the probing, non-interfering, and strong-non-interfering security notions for shared circuits based on concrete security games. Although these definitions are no more than a reformulation of existing security notions, we believe that they provide a simple and precise framework to reason about probing security.

[ (2) From the introduced game-based definitions, we provide a reduction of the probing security of a given standard shared circuit -i.e. a shared circuit composed of ISW multiplication gadgets, sharewise addition gadgets and SNI refresh gadgets-to the probing security of a simpler circuit of multiplicative depth 1 and for which the adversary is restricted to probe the multiplication inputs (which are linear combinations of the circuit inputs).

x 1 ] [x 2 ] [⊕] [⊗] Figure 4.1: Graph representation of Circuit 1. [x 1 ] [x 2 ] [⊕] R [⊗]
(3) We give an algebraic characterization of the final security game, which allows us to express the probing security of any standard shared circuit in terms of linear algebra.

(4) We show how to solve the latter problem with a new exact and proven method. Our method takes the description of any standard shared circuit and either produces a probing-security proof (valid at any order) or exhibits a probing attack (i.e. a set of t < d probes that reveal information on the circuit d-shared input for some d). We provide a concrete tool implementing our method in Sage.

(5) We apply our tool to the efficient implementation of the AES s-box developed by Goudarzi and Rivain in [GR17]. Based on the previous state of the art, this s-box was implemented using one SNI refresh gadget per multiplication gadget (to refresh one of the operands), hence making a total of 32 refresh gadgets (which was later on confirmed by the maskComp tool). Our new method formally demonstrates that the same d-shared implementation is actually t-probing secure with no refresh gadget for any d = t + 1. We provide implementation results and a performance analysis: this new implementation achieves an asymptotic gain up to 43%. The code can be found on GitHub [CRX].

(6) We extend our results to larger circuits by establishing new compositional properties on t-probing secure gadgets. In particular, these new composition properties perfectly apply to the case of SPN-based block ciphers. We also show that they apply to a wide range of Boolean circuits with common gadgets and input sets.

Approach

In Section 4.3, useful notions are introduced, security definitions for composition are formalized through concrete security games, and some useful security results are provided. Section 4.4

provides our security reduction for standard shared circuits. Section 4.5 then details our new method to exactly determine the probing security of a standard shared circuit. It also gives an upper bound on the number of required refresh gadgets together with an exhaustive method to make a standard shared circuit achieve tight probing security. In Section 4.6, our new method is extended to apply to larger circuits, and in particular to SPN-based block ciphers, with new compositional properties. Finally, Section 4.7 describes the new tool we implemented to experiment our method on concrete circuits.

Formal Security Notions

Notations

In this chapter, we denote by F 2 the finite field with two elements and by i, j the integer interval Z ∩ [i, j] for any two integers i and j. For a finite set X , we denote by |X | the cardinal of X and by x ← X the action of picking x from X independently and uniformly at random. For some (probabilistic) algorithm A, we further denote x ← A(in) the action of running algorithm A on some inputs in (with fresh uniform random tape) and setting x to the value returned by A.

Basic Notions

A Boolean circuit is a directed acyclic graph whose vertices are input gates, output gates, constant gates of fan-in 0 that output constant values, and operation gates of fan-in at most 2 and fan-out at most 1 and whose edges are wires. In this chapter we consider Boolean circuits with two types of operation gates: addition gates (computing an addition on F 2 ) and multiplication gates (computing a multiplication on F 2 ). A randomized circuit is a Boolean circuit augmented with random-bit gates of fan-in 0 that outputs a uniformly random bit.

A d-Boolean sharing of x ∈ F 2 is a random tuple (x 1 , x 2 , . . . , x d ) ∈ F d 2 satisfying x = d i=1 x i .
The sharing is said to be uniform if, for a given x, it is uniformly distributed over the subspace of tuples satisfying x = d i=1 x i . A uniform sharing of x is such that any m-tuple of its shares x i is uniformly distributed over F m 2 for any m ≤ d. In the following, a d-Boolean sharing of a given variable x is denoted by [x] when the sharing order d is clear from the context. We further denote by Enc a probabilistic encoding algorithm that maps x ∈ F 2 to a fresh uniform sharing [x].

A d-shared circuit C is a randomized circuit working on d-shared variables. More specifically, a d-shared circuit takes a set of n input sharings [x 1 ], . . . , [x n ] and computes a set of m output sharings [y 1 ], . . . , [y m ] such that (y 1 , . . . , y m ) = f (x 1 , . . . , x n ) for some deterministic function f . A probe on C refers to a wire index (for some given indexing of C's wires). An

evaluation of C on input [x 1 ], . . . , [x n ]
under a set of probes P refers to the distribution of the tuple of wires pointed by the probes in P when the circuit is evaluated on

[x 1 ], . . . , [x n ], which is denoted by C([x 1 ], . . . , [x n ]) P .
We consider a special kind of shared circuits which are composed of gadgets. In the chapter, we specifically consider three types of gadgets, namely ISW-multiplication gadgets ([⊗]),

ISW-refresh gadgets ([R]) and sharewise addition gadgets ([⊕]).

ExpReal(A, C):

1: (P, x 1 , . . . , x n ) ← A() 2: [x 1 ] ← Enc(x 1 ), . . . , [x n ] ← Enc(x n ) 3: (v 1 , . . . , v t ) ← C([x 1 ], . . . , [x n ]) P 4: Return (v 1 , . . . , v t )
ExpSim(A, S, C):

1: (P, x 1 , . . . , x n ) ← A() 2: (v 1 , . . . , v t ) ← S(P) 3: Return (v 1 , . . . , v t )

Game-Based Security Definitions

In the following, we recall the probing, non-interfering and strong non-interfering security notions introduced in [ISW03; BBD+16] and we formalize them through concrete security games. Each of these games is defined for a given n-input d-shared circuit C and it opposes an adversary A, which is a deterministic algorithm outputting a set of (plain) inputs x 1 , . . . , x n and a set of probes P, to a simulator S, which aims at simulating the distribution

C([x 1 ], . . . , [x n ]) P .

Probing Security.

We first recall the definition from [START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF]. Our game-based definition is then given with a proposition to state the equivalence of both notions.

Definition 4.3.2 (from [ISW03]). A circuit is t-probing secure if and only if any set of at most t intermediate variables is independent from the secret.

Probing Security Game. The t-probing security game is built based on two experiments as described in Figure 4.3. In both experiments, an adversary A outputs a set of probes P (indices of circuit's wires) such that |P| = t and n input values x 1 , . . . , x n ∈ F 2 .

In the first (real) experiment, referred to as ExpReal, the chosen input values x 1 , . . . , x n are mapped into n sharings [x 1 ], . . . , [x n ] with encoding algorithm Enc. The resulting encodings are given as inputs to the shared circuit C. The real experiment then outputs a random evaluation C([x 1 ], . . . , [x n ]) P of the chosen gates through a t-uple (v 1 , . . . , v t ).

In the second experiment, referred to as ExpSim, the probing simulator S takes the (adversary chosen) set of probes P and outputs a simulation of the evaluation C([x 1 ], . . . , [x n ]) P , which is returned by the simulation experiment. The simulator wins the game if and only if the two experiments return identical distributions.

Proposition 4.3.3. A shared circuit C is t-probing secure if and only if for every adversary

A, there exists a simulator S that wins the t-probing security game defined in Proof. From right to left, if for every adversary A, there exists a simulator S that wins the t-probing security game defined in Figure 4.3, then any set of probes is independent from the secret as S has no knowledge of the secret inputs. Thus C is trivially t-probing secure by Definition 4.3.2. From left to right, if the random experiments ExpReal(A, C) and ExpSim(A, S, C) do not output identical distributions, then there exists a set of at most t intermediate variables which cannot be perfectly simulated without the knowledge of the input secrets. As a consequence, the circuit is not t-probing secure by Definition 4.3.2.

A shared circuit C which is t-probing secure is referred to as a t-private circuit. It is not hard to see that a d-shared circuit can only achieve t-probing security for d > t. When a d-shared circuit achieves t-probing security with d = t + 1, we call it a tight private circuit.

Non-Interfering Security.

The non-interfering security notion is a little bit stronger. Compared to the probing security notion, it additionally benefits from making the security evaluation of composition of circuits easier. We recall its original definition from [START_REF] Barthe | Strong Non-Interference and Type-Directed Higher-Order Masking[END_REF] before we give an equivalent formal game-based definition.

Definition 4.3.4 (from [BBD+16]). A circuit is t-non-interfering (t-NI) if and only if any set of at most t intermediate variables can be perfectly simulated from at most t shares of each input.

Non-Interfering Security Game. The t-non-interfering (t-NI) security game is built based on two experiments as described in Figure 4.4. In both experiments, an adversary A outputs a set of probes P (indices of circuit's wires) such that |P| = t and n input sharings

[x 1 ], . . . , [x n ] ∈ F d 2 .
The first (real) experiment, referred to as ExpReal, simply returns an evaluation of C on input sharings [x 1 ], . . . , [x n ] under the set of probes P.

The second experiment, referred to as ExpSim, is defined for a two-round simulator S = (S 1 , S 2 ). In the first round, the simulator S 1 takes the (adversary chosen) set of probes P and outputs n sets of indices I 1 , . . . , I n ⊆ {1, . . . , d}, such that

|I 1 | = • • • = |I n | = t.
In the second round, in addition to the set of probes P, the simulator S 2 receives the (adversary chosen) input sharings restricted to the shares indexed by the sets I 1 , . Proof. From right to left, if for every adversary A, there exists a simulator S that wins the t-non interfering security game defined in Figure 4.3, then any set of probes can be perfectly simulated from sets of at most t shares of each input. Thus C is trivially t-non-interfering from Definition 4.3.4. From left to right, if the random experiments ExpReal(A, C) and ExpSim(A, S, C) do not output identical distributions, then there exists a set of at most t intermediate variables which cannot be perfectly simulated from sets I j of input shares whose cardinals are less than t. As a consequence, the circuit is not t-non interfering secure from Definition 4.3.4.

ExpReal(A, C):

1: (P, [x 1 ], . . . , [x n ]) ← A() 2: (v 1 , . . . , v t ) ← C([x 1 ], . . . , [x n ]) P 3: Return (v 1 , . . . , v t ) ExpSim(A, S, C): * 1: (P, [x 1 ], . . . , [x n ]) ← A() 2: I 1 , . . . , I n ← S 1 (P) 3: (v 1 , . . . , v t ) ← S 2 (P, [x 1 ] I 1 , . . . , [x n ] In ) 4: Return (v 1 , . . . , v t ) * For t-NI: |I 1 | = • • • = |I n | = t. For t-SNI: |I 1 | = • • • = |I n | = |P int | ≤ t.

Strong Non-Interfering Security.

The strong non-interfering security is a stronger notion than non-interfering security as it additionally guarantees the independence between input and output sharings. The latter property is very convenient to securely compose gadgets with related inputs. Proof. From right to left, if for every adversary A, there exists a simulator S that wins the t-non interfering security game defined in Figure 4.3, then any set of probes can be perfectly simulated from sets of at most |P int | = t 1 shares of each input. Thus C is trivially t-strong non-interfering from Definition 4.3.6. From left to right, if the random experiments ExpReal(A, C) and ExpSim(A, S, C) do not output identical distributions, then there exists a set of at most t intermediate variables which cannot be perfectly simulated from sets I j of input shares whose cardinals are less than t 1 . As a consequence, the circuit is not t-strong non interfering secure from Definition 4.3.6.

Useful Security Results

This section states a few useful security results. From the above definitions, it is not hard to see that for any shared circuit C we have the following implications:

C is t-SNI ⇒ C is t-NI ⇒ C is t-probing secure
while the converses are not true. While the ISW-multiplication (and refresh) gadget defined above was originally shown to achieve probing security, it actually achieves the more general notion of strong non-interfering security as formally stated in the following theorem: Proof of Lemma 4.3.9. Let I ⊆ {0, 1, . . . , t} such that |I| = t. From Definition 4.3.7, consider an adversary A which outputs a set of probes P matching the output shares [y] I . The t-SNI property implies that there exists an algorithm S performing a perfect simulation of

[y] I independently of [x 1 ], . . . , [x n ], that is P([x 1 ], . . . , [x n ], [y] I ) = P([x 1 ], . . . , [x n ]) • P([y] I ) . (4.1)
Moreover, since for a given y = f (x 1 , . . . , x n ), the sharing [y] is perfectly defined by [y] I , the above rewrites

P([x 1 ], . . . , [x n ], [y]) = P([x 1 ], . . . , [x n ]) • P([y]) , (4.2)
which implies the mutual independence between [y] and

[x 1 ], . . . , [x n ].
Let us now show that [y] is a uniform sharing i.e. the t-tuple [y] I is uniformly distributed over F t 2 , for any I ⊆ {0, 1, . . . , t} such that |I| = t. We proceed by contradiction: we assume that [y] is not a uniform sharing and then show that C cannot be t-SNI. If [y] is not a uniform sharing, then the t-tuple [y] I is not uniformly distributed over F t 2 . This implies that there exists a set J ⊆ I with J = ∅ such that the sum i∈J y i is not uniformly distributed over F 2 . Then for any y ∈ F 2 , we have i∈ 0,t \J

y i + i∈J y i = y , ( 4.3)
which implies that both [y] J and [y] 0,t \J are not uniformly distributed and statistically dependent on y. This implies that the tuple [y] J cannot be perfectly simulated independently of y which contradicts the t-SNI property.

A Security Reduction

This section provides a reduction for the t-probing security of a standard (t + 1)-shared circuit the probing security property as a linear algebra problem, which can then be solved efficiently as we show in Section 4.5.

C
In a nutshell, our Game 0 exactly fits the game-based definition of t-probing security given in the previous section. Then, with Game 1, we prove that verifying the t-probing security of a standard shared circuit C is exactly equivalent to verifying the t-probing security of the same circuit C where the attacker A is restricted to probe inputs of refresh gadgets, pairs of inputs of multiplication gadgets, and inputs and outputs of sharewise additions (i.e., no internal gadgets variables). Game 2 then shows that verifying the t-probing security of a standard shared circuit C with a restricted attacker A is equivalent to verifying the t-probing security of a functionally equivalent circuit C of multiplicative depth one where all the outputs of multiplication and refresh gadgets in C are replaced by fresh input sharings of the same values in the rest of the circuit. Finally, with Game 3, we show that we can even restrict the adversary to probe only pairs (x i , y j ) where x i (resp. y j ) is the i th share of x (resp. the j th share of y) and such that x and y are operands of the same multiplication in C. These three games are deeply detailed hereafter and proofs of their consecutive equivalence are provided at each step. An overview is displayed on Figure 4.5.

Game 1.

In a nutshell, our first game transition relies on the fact that each probe in a t-SNI gadget can be replaced by 1 or 2 probes on the input sharing(s) of the gadget. In particular, one probe on a refresh gadget is equivalent to revealing one input share, one probe on a multiplication gadget is equivalent to revealing two input shares (one share per input sharing). Formally, in the random experiments ExpReal(A, C) and ExpSim(A, S, C), the set of probes P returned by A, noted P in the following, has a different form explicitly defined below.

Let us associate an index g to each gadget in the standard shared circuit and denote by G the set of gadget indices. Let us further denote by G r , G m and G a the index sets of refresh gadgets, multiplication gadgets and addition gadgets, such that G = G r ∪ G m ∪ G a . Then we can denote by I g and J g the indices of circuit wires which are the shares of the (right and left) input operands of gadget g ∈ G (where J g = ∅ if gadget g is a refresh). Similarly, we denote by O g the indices of circuit wires which represent the output of gadget g ∈ G. From these notations, an admissible set of probes P from the adversary in the new game is of the form and |P | = t. That is, each of the t elements of P either is a pair of index in I g × J g for a multiplication gadget g, or a single index in I g for a refresh gadget g, or a single index in I g ∪ J g ∪ O g for an addition gadget. Note that in the latter case, the index can correspond to any wire in the addition gadget (which is simply composed of t + 1 addition gates).

P = P r ∪ P m ∪ P a ExpReal 1 (A, C): 1: (P , x 1 , . . . , x n ) ← A() 2: [x 1 ] ← Enc(x 1 ), . . . , [x n ] ← Enc(x n ) 3: (v 1 , . . . , v q ) ← C([x 1 ], . . . , [x n ]) P 4: Return (v 1 , . . . , v q ) ExpSim 1 (A, S, C): 1: (P , x 1 , . . . , x n ) ← A() 2: (v 1 , . . . , v q ) ← S(P ) 3: Return (v 1 , . . . , v q )
Let t m be the number of probes on multiplication gadgets, i.e. t m = |P m |, and t ar the number of probes on refresh or addition gadgets, i.e. t ar = |P a ∪ P r |, so that t m + t ar = t. The evaluation C([x 1 ], . . . , [x n ]) P then returns a q-tuple for q = 2t m + t ar , which is composed of the values taken by the wires of index i ∈ P a ∪ P r , and the values taken by the wires of index i and j with (i, j) ∈ P m . The new experiments ExpReal 1 (A, C) and ExpSim 1 (A, S, C), carefully written in Figure 4.6, each output a q-tuple and, as before, the simulator wins Game 1 if and only if the associated distributions are identical. Proof. We first show: ∀A 1 , ∃S 1 wins Game 1 ⇒ ∀A 0 , ∃S 0 wins the t-probing security game (4.4)

Let us consider an adversary A 0 that outputs some values x 1 , . . . , x n ∈ F 2 and a set of probes P. By definition, P can be partitioned into three subsets of probes, i.e. P = P a ∪ P r ∪ P m , where P a represents the probes on addition gadgets, P r the probes on refresh gadgets, and P m the probes on multiplication gadgets. Let us denote by P (g) r ⊆ P r (resp. P (g) m ⊆ P m ) the set of probes that point to the wires of the refresh gadget of index g ∈ G r (resp. the multiplication gadget of index g ∈ G m ). The t-SNI property of the refresh and multiplication gadgets (see Definition 4.3.7) implies that:

• For every g ∈ G r , there exists a simulator S (g) SNI that given the set of probes P • For every g ∈ G m , there exists a simulator S We define A 1 as the adversary that returns the same values x 1 , . . . , x n ∈ F 2 as A 0 and the set of probes P = P a ∪ P r ∪ P m defined from P as:

P r = g∈Gr P r (g) , P m = g∈Gm P m (g) , P a = P a ,
where P r (g) and P m (g) denote the sets of probes defined by the simulators S (g) SNI on input P (g) r and P (g) m respectively. From the left side of implication Equation (4.4), there exists a simulator S 1 that wins Game 1 for the inputs (x 1 , . . . , x n ) and the built set of probes P . We define the simulator S 0 as the simulator that computes P from P as explained above and then call S 1 to get a perfect simulation of C([x 1 ], . . . , [x n ]) P . Then S 0 applies the simulator S Let us now show:

∀A 0 , ∃S 0 wins the t-probing security game ⇒ ∀A 1 , ∃S 1 wins Game 1 (4.5)

By contraposition, we can equivalently show that ∃A 1 , ∀S 1 , S 1 fails in Game 1

⇒ ∃A 0 , ∀S 0 , S 0 fails in the t-probing security game (4.6)

Let us thus assume that an adversary A 1 exists which outputs some values x 1 , . . . x n and a set of probes P = P a ∪ P r ∪ P m such that no algorithm S 1 can output a perfect simulation of

C([x 1 ], . . . , [x n ]) P .
We show that we can then define an adversary A 0 for which no simulator S 0 can win the t-probing security game. The adversary A 0 outputs the same values x 1 , . . . x n as A 1 and the set of probes P = P a ∪ P r ∪ P m such that P a = P a and P r = P r (4.7)

We show in the following how to construct P m so that no simulator S 0 can output a perfect simulation of C([x 1 ], . . . , [x n ]) P .

If P m = ∅ then we have P = P and the statement directly holds. Let us now consider

P m = {(i, j)}.
From the left-side implication of 4.6, we get that no simulator S 1 can perform a perfect simulation of (v 1 , . . .

, v q ) = C([x 1 ], . . . , [x n ]) P , ( 4.8)
where q = t + 1. Without loss of generality we assume that v 1 and v 2 are the wires pointed by the indices i and j. We can assume that there exists a simulator S 0 computing a perfect simulation of (v 3 , . . . , v q ), i.e. the wires pointed by P a ∪ P r . (Otherwise we can simply define A 0 as returning the set of probes P a ∪ P r and Equation (4.6) directly holds). We deduce that no simulator can achieve a perfect simulation of (v 1 , v 2 ) given (v 3 , . . . , v q ). In a standard shared circuit, the shares of the input of a multiplication gadget are linear combinations of the input shares [x 1 ], . . . , [x N ] of the input of the circuit or the shares in output of refresh or multiplication gadgets. We hence get that v 1 and v 2 can be expressed as

v 1 = f 1 (x 1 , . . . , x N ) + g 1 (v 3 , . . . , v q ) + r 1 v 2 = f 2 (x 1 , . . . , x N ) + g 2 (v 3 , . . . , v q ) + r 2
for some deterministic function f 1 , f 2 , g 1 , g 2 and where (r 1 , r 2 ) ∈ {(0, 0), (0, r), (r, 0), (r, r)} for some uniform random r over F 2 . (Note that r 1 and r 2 cannot be uniform independent random elements of F 2 otherwise the (v 1 , v 2 ) could be straightforwardly simulated). We then have four cases:

• For (r 1 , r 2 ) = (0, 0), we have either

f 1 or f 2 non constant (otherwise (v 1 , v 2 ) could be simulated). If f 1 (resp. f 2 ) is non constant, then v 1 (resp. v 2
) cannot be simulated given (v 3 , . . . , v q ) and we define P m = {i} (resp. P m = {j}).

• For (r 1 , r 2 ) = (0, r), we have f 1 non constant (otherwise (v 1 , v 2 ) could be simulated).

Then v 1 cannot be simulated given (v 3 , . . . , v q ) and we define P m = {i}.

• For (r 1 , r 2 ) = (r, 0), we have f 2 non constant (otherwise (v 1 , v 2 ) could be simulated).

Then v 2 cannot be simulated given (v 3 , . . . , v q ) and we define P m = {j}.

• For (r 1 , r 2 ) = (r, r), we have f 1 +f 2 non constant (otherwise (v 1 , v 2 ) could be simulated). 1Then the product

v 1 • v 2 satisfies v 1 • v 2 = [f 1 + f 2 ](x 1 , . . . , x N ) + δ + r • r
where δ = [g 1 + g 2 ](v 3 , . . . , v q ) is a constant given (v 3 , . . . , v q ) and where r = v 2 is a uniform random element of F 2 . It is not hard to see that the distribution of v 1 •v 2 cannot be simulated without knowing [f 1 + f 2 ](x 1 , . . . , x N ). We then define P m = {ψ(i, j)} where ψ(i, j) denotes the index of the cross-product w i • w j computed in the target ISW-multiplication gadget, with w i and w j denoting the wires indexed by i and j.

For the general case where P m contains more than one pair, we can proceed as above to show that no S 0 can simulate C([x 1 ], . . . , [x n ]) P (1) where P (1) is obtained by replacing one pair (i, j) from P by a single index i, j or ψ(i, j) as described above. Then we reiterate the same principle to show that no S 0 can simulate C([x 1 ], . . . , [x n ]) P (2) where P (2) is obtained from P (1) by replacing one more pair (i, j) by a single index. And so on until the set of probes has no more pairs but only t wire indices as in the original probing security game.

[x 1 ] [x 2 ] [x 3 ] [⊕] R [⊗] [⊗] [⊗] [⊗] [v 1 ] [v 2 ] [v 3 ] [v 4 ] [v 5 ] [v 6 ] Circuit C [x 1 ] [x 2 ] [x 3 ] [x 4 ] [x 5 ] [x 6 ] [x 7 ] [x 8 ] [v 2 ] [v 3 ] [v 4 ] [v 5 ] [v 6 ] [⊕] R [⊗] [⊗] [⊗] [⊗] [v 1 ]
Circuit C ExpReal 2 (A, C):

1: C ← Flatten(C) 2: (P , x 1 , . . . , x N ) ← A() 3: [x 1 ] ← Enc(x 1 ), . . . , [x N ] ← Enc(x N ) 4: (v 1 , . . . , v q ) ← C ([x 1 ], . . . , [x N ]) P 5: Return (v 1 , . . . , v q )
ExpSim 2 (A, S, C):

1: C ← Flatten(C) 2: (P , x 1 , . . . , x N ) ← A() 3: (v 1 , . . . , v q ) ← S(P ) 4: Return (v 1 , . . . , v q ) Figure 4.8: Game 2.

Game 2.

Our second game transition consists in replacing the circuit C by a functionally equivalent circuit C of multiplicative depth one and with an extended input. In a nutshell, each output of a multiplication or a refresh gadget in C is replaced by a fresh new input sharing of the same value in the rest of the circuit. The resulting Game 2 is illustrated on Figure 4.8. Although the additional inputs x n+1 , . . . , x N are deterministic functions of the original inputs x 1 , . . . , x n , we allow the adversary to select the full extended input x 1 , . . . , x N for the sake of simplicity. This slight adversarial power overhead does not affect the equivalence between the games. Proof. Without loss of generality, we assume that the Flatten transformation does not change the gadget indexing. We first show: ∀A 2 , ∃S 2 wins Game 2 ⇒ ∀A 1 , ∃S 1 wins Game 1 (⇔ C t-probing secure) (4.9)

For each adversary A 1 returning (x 1 , . . . , x n ) and P , we define A 2 as the adversary that returns the same choice of probes P and the extended input (x 1 , . . . , x N ) such that the n first elements match the choice of A 1 and the Nn matches the decoded outputs of the corresponding multiplication and refresh gadgets. Then, by Lemma 4.3.9, the t-SNI property of multiplication and refresh gadgets implies that each sharing in the output of these gadgets is independent of the input sharings. Since all the probes in P on multiplication and refresh gadgets point to input shares only, the output of each such gadget can be replaced by a fresh uniform sharing of the underlying plain value (which deterministically depends on x 1 , . . . ,

x n ) without modifying the evaluation. We hence get that C(

Translation to linear algebra.

At this point, the problem of deciding the t-probing security of a Boolean standard shared circuit C has been equivalently reduced to the problem of deciding the t-probing security of a circuit C = Flatten(C) when the attacker is restricted to probes on multiplication and refresh gadgets' inputs, and intermediate variables of sharewise additions. In order to further reduce it, we translate the current problem into a linear algebra problem. In the following, we denote by x i,j the jth share of the ith input sharing [x i ] so that

[x i ] = (x i,0 , x i,1 , . . . , x i,t ) ,
for every i ∈ 1, N . Moreover, we denote by -→ x j ∈ F N 2 the vector composed of the jth share of each input sharing:

-→ x j = (x 0,j , x 1,j , . . . , x N,j ) .

As a result of the Flatten transformation, each probed variable in the q-tuple (v 1 , . . . , v q ) = C([x 1 ], . . . , [x N ]) P is a linear combination of the input sharings [x 1 ], . . . , [x N ]. Moreover, since the addition gadgets are sharewise, for every k ∈ 1, q , there is a single share index j such that the probed variable v k only depends of the jth shares of the input sharings, giving:

v k = - → a k • - → x j , ( 4.11)
for some constant coefficient vector -→ a k ∈ F N 2 . Without loss of generality, we assume that the tuple of probed variables is ordered w.r.t. the share index j corresponding to each v k (i.e. starting from j = 0 up to j = t). Specifically, the q-tuple (v 1 , . . . , v q ) is the concatenation of

t + 1 vectors - → v 0 = M 0 • -→ x 0 , - → v 1 = M 1 • -→ x 1 , . . . - → v t = M t • - → x t , ( 4.12)
where the matrix M j is composed of the row coefficient vectors -→ a k for the probed variable indices k corresponding to the share index j. Lemma 4.4.4. For any (x 1 , . . . , x N ) ∈ F N 2 , the q-tuple of probed variables (v 1 , . . . , v q ) = C([x 1 ], . . . , [x N ]) P can be perfectly simulated if and only if the M j matrices satisfy

Im(M T 0 ) ∩ Im(M T 1 ) ∩ • • • ∩ Im(M T t ) = ∅ .
Moreover, if the M j matrices are full-rank (which can be assumed without loss of generality), then the above equation implies that (v 1 , . . . , v q ) is uniformly distributed.

Proof. Without loss of generality we can assume that the M j matrices are full-rank since otherwise the probed variables v 1 , . . . , v q would be mutually linearly dependent and simulating them would be equivalent to simulating any subset (v k ) k∈K⊆ 1,q defining a free basis of (v 1 , . . . , v q ), and which would then induce full-rank matrices M j . Throughout this proof, we denote -→ x = (x 1 , . . . , x N ). We first show that a non-null intersection implies a non-uniform distribution of (v 1 , . . . , v q ) which is statistically dependent on -→ x . Indeed, a non-null intersection implies that there exist a non-null vector -

→ w ∈ F N 2 satisfying - → w = -→ u 0 • M 0 = -→ u 1 • M 1 = • • • = - → u t • M t . (4.13)
for some (constant) vectors -→ u 0 , . . . , -→ u t . It follows that

t j=0 - → u j • - → v j = t j=0 - → w • - → x j = - → w • - → x ,
which implies that the distribution of the q-tuple (v 1 , . . . , v q ) = ( -

→ v 0 • • • - → v t
) is non-uniform and dependent on -→ x . We now show that a null intersection implies a uniform distribution (which can then be easily simulated). The uniformity and mutual independence between the sharings [x 1 ], . . . , [x N ] implies that we can see -→

x 1 , . . . , -→ x t as t uniform and independent vectors on F N 2 , and -→

x 0 as -→ x 0 = - → x + -→ x 1 + • • • + - → x t .
The joint distribution of -→ v 1 , . . . , -→ v t is hence clearly uniform. Then each coordinate of -→ v 0 is the result of the inner product -→ r • -→ x 0 where -→ r is a row of M 0 . By assumption, there exists at least one matrix M j such that -→ r / ∈ Im(M T j ). It results that -→ r • -→ x j is a uniform random variable independent of -→ v 1 , . . . , -→ v t and the other coordinates of -→ v 0 (since M 0 is full-rank). Since the latter holds for all the coordinates of -→

x 0 we get overall uniformity of ( -→ v 0 • • • -→ v t ) which concludes the proof. Lemma 4.4.4 allows us to reduce the t-probing security of a standard shared circuit to a linear algebra problem. If an adversary exists that can choose the set of probes P such that the transposes of induced matrices M 1 , . . . , M t have intersecting images, then the distribution ExpReal 3 (A, C):

1: C ← Flatten(C) 2: (P , x 1 , . . . , x N ) ← A() 3: [x 1 ] ← Enc(x 1 ), . . . , [x N ] ← Enc(x N ) 4: (v 1 , . . . , v q ) ← C ([x 1 ], . . . , [x N ]) P 5: Return (v 1 , . . . , v q )
ExpSim 3 (A, S, C):

1: C ← Flatten(C) 2: (P , x 1 , . . . , x N ) ← A() 3: (v 1 , . . . , v q ) ← S(P ) 4: Return (v 1 , . . . , v q ) Figure 4.9: Game 3. of (v 1 , . . . , v q ) depends on (x 1 , . . . , x N ) and a perfect simulation is impossible (which means that the circuit is not probing secure). Otherwise, the tuple (v 1 , . . . , v q ) can always be simulated by a uniform distribution and the circuit is probing secure. This statement is the basis of our verification method depicted in the next section. But before introducing our verification method, we can still simplify the probing security game as shown hereafter by using Lemma 4.4.4.

Game 3.

In this last game, the adversary is restricted to probe the multiplication gadgets only. Formally, A returns a set of probes P = P r ∪ P m ∪ P a such that P r = ∅ and P a = ∅. Such a set, denoted P is hence composed of t pairs of inputs from g∈Gm I g × J g . The evaluation C([x 1 ], . . . , [x n ]) P then returns a q-tuple for q = 2t. The new experiments ExpReal 3 (A, C) and ExpSim 3 (A, S, C), displayed in Figure 4.6, each output a q-tuple and, as before, the simulator wins Game 3 if and only if the associated distributions are identical. For each adversary A 3 that returns a set of inputs (x 1 , . . . , x N ) and a set probes P , we define an adversary A 2 that outputs the same set of inputs and the same set of probes P . By assumption, there exists S 2 that can perfectly simulate C ([x 1 ], . . . , [x N ]) P and win Game 2. As a consequence, the simulator S 3 = S 2 wins Game 3 as well. We now show:

∀A 3 , ∃S 3 wins Game 3 ⇒ ∀A 2 ,
) ∩ Im(M 1 ) ∩ • • • ∩ Im(M t ) = ∅ .
Moreover, we have q ≤ 2t implying that at least one M j matrix has a single row and consequently the above intersection is of dimension one i.e. it is defined as the span of a single vector -→ w ∈ F N 2 :

Im(M 0 ) ∩ Im(M 1 ) ∩ • • • ∩ Im(M t ) = - → w . (4.17)
Since -→ w is the single row of at least one M j matrix we have that -→ w is directly induced by a probed variable v k . In other words, a sharing ( -→ w • -→ x 0 , . . . , -→ w • -→ x t ) appears in the circuit (either as input of some gadget, or as output of an addition gadget). We now argue that this sharing must appear in input of a multiplication gadget. Assume by contradiction that this sharing does not appear in input of a multiplication gadget, then it appears in a refresh or an addition gadget. Let us then denote by t ar the number of matrices M j that have -→ w as row (i.e. the jth share of the considered sharing has been probed). The remaining tt ar matrices M j have at least 2 rows (since otherwise their image does not include -→ w ). We deduce that q ≥ t ar + 2(tt ar ) = 2t + t ar which is impossible since q ≤ 2t. We hence obtain that -→ w must be induced by a sharing ( -→ w • -→ x 0 , . . . , -→ w • -→ x t ) in input of a multiplication gadget. We can then define A 3 as the adversary that outputs the same set of inputs than A 2 and a set of probes P defined according to P as follows:

• for every pair (i 1 , i 2 ) ∈ P m , include (i 1 , i 2 ) to P ,

• for every probe i ∈ P a ∪ P r , let j be the share index corresponding to the wire indexed by i, then include the wire index of the multiplication input share -→ w • -→ x j .

It is not hard to see that the M j matrices induced by the new set of probes P still satisfies Equation (4.17) which implies that no simulator S 3 can produce a perfect simulation of C ([x 1 ], . . . , [x N ]) P . In other words, our contrapositive statement Equation (4.16) holds which concludes the proof.

Probing-Security Verification for Standard Shared Circuits

In this section, we describe a formal verification method that for any t ∈ N checks whether a standard (t + 1)-shared circuit C achieves t-probing security. Specifically, our tool either provides a formal proof that C is t-probing secure for every t ∈ N (where C is a standard shared circuit with sharing order t + 1), or it exhibits a probing attack against C for a given t, namely it finds a set of probes P (indices of wires) in the (t + 1)-shared instance of C, such that |P| = t, for which the evaluation C([x 1 ], . . . , [x n ]) P cannot be simulated without some knowledge on the plain input (x 1 , . . . , x n ).

Linear Algebra Formulation

As demonstrated in the previous section, the t-probing security game for a standard (t + 1)shared circuit C can be reduced to a game where an adversary selects a set of probes P solely pointing to input shares of the multiplication gadgets of a flattened circuit C . In the following, we will denote by m the number of multiplication gadgets in C (or equivalently in C ) and by g ∈ 1, m the index of a multiplication gadget of C. We will further denote by [a g ] and [b g ] the input sharings of the g-th multiplication gadget so that we have

[a g ] = ( - → a g • -→ x 0 , . . . , - → a g • - → x t ) and [b g ] = ( - → b g • -→ x 0 , . . . , - → b g • - → x t ) , (4.18)
for some constant coefficient vectors -→ a g , -→ b g ∈ F N 2 , recalling that -→ x j denotes the vector with the jth share of each input sharing [x 1 ], . . . , [x N ]. In the following, the vectors { -→ a g , -→ b g } g are called the operand vectors.

In Game 3, the adversary chooses t pairs of probes such that each pair points to one share of [a g ] and one share of [b g ] for a multiplication gadget g. Without loss of generality, the set of pairs output by the adversary can be relabelled as a set of triplet P = {(g, j 1 , j 2 )} where g ∈ 1, m is the index of a multiplication gadget, j 1 and j 2 are share indices. For any triplet (g, j 1 , j 2 ) ∈ P the two input shares -→ a g • -→

x j 1 and -→ b g • -→

x j 2 are added to the (2t)-tuple of probed variables to be simulated. This set of triplets exactly defines a sequence of t + 1 matrices M 1 , . . . , M t , defined iteratively by adding -→ a g to the rows of M j 1 and -→ b g to the rows of M j 2 for each (g, j 1 , j 2 ) ∈ P. Equivalently, the matrix M j is defined as

M j = rows({ - → a g ; (g, j, * ) ∈ P} ∪ { - → b g ; (g, * , j) ∈ P}) , ( 4.19)
for every j ∈ 0, t where rows maps a set of vectors to the matrix with rows from this set. Lemma 4.4.4 then implies that a probing attack on C consists of a set of probes P = {(g, j 1 , j 2 )} such that the transposes of the induced M j have intersecting images. Moreover, since the total number of rows in these matrices is 2t, at least one of them has a single row -→ w . In particular, the image intersection can only be the span of this vector (which must match the row of all single-row matrices) and this vector belongs to the set of operand vectors

{ - → a g , - → b g } g .
In other words, there exists a probing attack on C if and only if a choice of probes P = {(g, j 1 , j 2 )} implies

Im(M T 0 ) ∩ Im(M T 1 ) ∩ • • • ∩ Im(M T t ) = - → w . (4.20) for some vector - → w ∈ { - → a g , - → b g } g .
In that case we further say that there is a probing attack on the operand vector -→ w . In the remainder of this section, we describe an efficient method that given a set of vector operands { -→ a g , -→ b g } g (directly defined from a target circuit C) determines whether there exists a parameter t and a set P = {(g, j 1 , j 2 )} (of cardinality t) for which Equation (4.20) can be satisfied. We prove that (1) if such sets P exist, our method returns one of these sets, (2) if not sets is returned by our method then the underlying circuit is t-probing secure for any sharing order (t + 1).

Method Description

The proposed method loops over all the vector operands -→ w ∈ { -→ a g , -→ b g } g and checks whether there exists a probing attack on -→ w (i.e. whether a set P can be constructed that satisfies Equation (4.20)).

For each -→ w ∈ { -→ a g , -→ b g } g the verification method is iterative. It starts from a set G 1 ⊆ 1, m defined as

G 1 = {g ; - → a g = - → w } ∪ {g ; - → b g = - → w } . (4.21)
Namely G 1 contains the indices of all the multiplication gadgets that have -→ w as vector operand. Then the set of free vector operands O 1 is defined as

O 1 = { - → b g ; - → a g = - → w } ∪ { - → a g ; - → b g = - → w } . (4.22)
The terminology of free vector operand comes from the following intuition: if a probing adversary spends one probe on gadget g ∈ G 1 such that -→ a g = -→ w to add -→ w to a matrix M j (or equivalently to get the share -→ w • -→ x j ), then she can also add -→ b g to another matrix M j (or equivalently get the share -→ b g • -→

x j ) for free. The adversary can then combine several free vector operands to make -→ w ∈ Im(M T j ) occur without directly adding -→ w to M j (or equivalently without directly probing -→ w • -→ x j ). This is possible if and only if -→ w ∈ O 1 .

The free vector operands can also be combined with the operands of further multiplications to generate a probing attack on -→ w . To capture such higher-degree combinations, we define the sequences of sets (G i ) i and (O i ) i as follows:

G i+1 = {g ; - → a g ∈ - → w + O i } ∪ {g ; - → b g ∈ - → w + O i } , ( 4.23)
and

O i+1 = { - → b g ; - → a g ∈ - → w + O i } ∪ { - → a g ; - → b g ∈ - → w + O i } . ( 4.24)
for every i ≥ 1. The rough idea of this iterative construction is the following: if at step i + 1 a probing adversary spends one probe on gadget g ∈ G i+1 such that -→ a g ∈ -→ w + O i , then she can add -→ a g together with some free vector operands of previous steps to M j in order to get -→ w ∈ Im(M T j ). Then she can also add -→ b g to another matrix M j , making -→ b g a new free vector operand of step i + 1.

Based on these definitions, our method iterates the construction of the sets G i and O i . At step i, two possible stop conditions are tested:

1. if G i = G i-1 ,
then there is no probing attack on -→ w , the method stops the iteration on -→ w and continues with the next element in the set of vector operands; 2. if -→ w ∈ O i , then there is a probing attack on -→ w , the method stops and returns True (with -→ w and the sequence of sets (G i , O i ) i as proof);

The method returns True if there exists a concrete probing attack on a vector -→ w ∈ { -→ a g , -→ b g } g for a certain sharing order t + 1. Otherwise, it will eventually stops with vector operand -→ w since the number of multiplications is finite and since G i ⊆ G i+1 for every i ≥ 1. When all the possible vector operands have been tested without finding a probing attack, the method returns False. Algorithm 3 hereafter gives a pseudocode of our method where NextSets denotes the procedure that computes (G i+1 , O i+1 ) from (G i , O i ).

Algorithm 3 Search probing attack

Input: A set of vector operands { -→ a g , -→ b g } g Output: True if there is probing attack on some -→ w ∈ { -→ a g , -→ b g } g and False otherwise

1: for all - → w ∈ { - → a g , - → b g } g do 2: (G 1 , O 1 ) ← NextSets(∅, ∅, { - → a g , - → b g } g , - → w ) 3: if - → w ∈ O 1 then return True 4:
for i = 1 to m do 5:

(G i+1 , O i+1 ) ← NextSets(G i , O i , { - → a g , - → b g } g , - → w ) 6: if G i+1 = G i then break 7: if - → w ∈ O i then return True return False
In the rest of the section we first give some toy examples to illustrate our methods and then provides a proof of its correctness.

Toy Examples

Two examples are provided hereafter to illustrate our iterative method in the absence then in the presence of a probing attack.

In the very simple example of

→ w 1 = -→ x 1 and - → w 2 = -→ x 1 + -→ x 2 .
The set of multiplications G is of cardinal one since it only contains one multiplication ( -→ w 1 , -→ w 2 ). Following the number of variables, the method proceeds at most in two steps:

1. As depicted in Algorithm 3, the method first determines whether there exists a probing attack on -→ w 1 . In this purpose, a first set G 1 is built, such that G 1 = ( -→ w 1 , -→ w 2 ) and

O 1 = - → w 2 . Since G 1 = ∅ and - → w 1 = - → w 2 ,
then a second set must be built. However, there is no multiplication left, that is G 2 = G 1 and so there is no attack on -→ w 1 .

2. The method then focuses on -→ w 2 . In this purpose, a dedicated set G 1 is built, such that

G 1 = ( - → w 2 , - → w 1 ) and O 1 = - → w 1 . Since G 1 = ∅ and - → w 2 = - → w 1 ,
then a second set must be built. However, there is no multiplication left, that is G 2 = G 1 and so there is no attack on -→ w 2 either. Since there is no input variable left, the method returns False, which means that there is no possible probing attack on this circuit.

→ w 1 = -→ x 1 , - → w 2 = -→ x 2 , - → w 3 = -→ x 3 , - → w 4 = -→ x 1 + -→ x 2 , and - → w 5 = -→ x 2 + -→ x 3 . The set of multiplications G is of cardinal three with ( - → w 1 , - → w 2 ), ( - → w 4 , - → w 5 )
, and ( -→ w 3 , -→ w 4 ). Following the number of variables, the method proceeds at most in five steps:

1. The method first determines whether there exists a probing attack on -→ w 1 . In this purpose, a first set

G 1 is built, such that G 1 = ( - → w 1 , - → w 2 ) and O 1 = - → w 2 . Since G 1 = ∅ and - → w 1 = - → w 2 , then a second set must be built. G 2 = G 1 ∪ {( - → w 4 , - → w 5 ), ( - → w 4 , - → w 3 )} since - → w 4 = - → w 1 + - → w 2 . However, - → w 1 / ∈ O 2 (=< - → w 2 , - → w 3 , - → w 5 >
), so a third set must be built. Since there is no multiplication left, that is G 3 = G 2 , there is no attack on -→ w 1 .

[ 2. The method then focuses on -→ w 2 . In this purpose, a dedicated set

x 1 ] = - → w 1 [x 2 ] = - → w 2 [x 3 ] = - → w 3 [⊕] - → w 4 [⊕] - → w 5 [⊗] [⊗] [⊗]
G 1 is built, such that G 1 = ( - → w 2 , - → w 1 ) and O 1 = - → w 1 . Since G 1 = ∅ and - → w 2 = - → w 1 , then a second set must be built. G 2 = G 1 ∪ {( - → w 4 , - → w 5 ), ( - → w 4 , - → w 3 )} since - → w 4 = - → w 2 + - → w 1 . And in that case, - → w 2 ∈ O 2 (=< - → w 1 , - → w 3 , - → w 5 >) since - → w 2 = - → w 3 + - → w 5 .

Thus the method returns

True and there exists an attack on -→ w 2 = -→ x 2 for some masking order t.

Proof of Correctness

This section provides a proof of correctness of the method. This proof is organized in two propositions which are based on some invariants in Algorithm 3. The first proposition shows that if the method returns True for some operand vector -→ w and corresponding sets (G i , O i ) then there exists a probing attack on -→ w (i.e. a set P can be constructed that satisfies Equation (4.20)). The second proposition shows that if the method returns False then there exists no probing attack for any -→ w , namely the underlying circuit is t-probing secure as soon as masked variables are masked with t + 1 shares. Invariant: ∀s ∈ N, ∃ t ∈ N such that with t carefully chosen probes on multiplications from G i , we are able to get:

• r matrices M j such that -→ w ∈ Im(M j ), 0 ≤ j ≤ r -1, where r = t + 1s;

• s matrices M j such that O i ⊆ Im(M j ), r ≤ j ≤ t.
We show that the invariant holds for i = 1. Let s ∈ N and let 1 = |O 1 |. If we place s probes on each multiplication gadget g ∈ G 1 , we can have r = s • 1 matrices M j = rows( -→ w ), and s matrices M j = rows(O 1 ). We thus get the desired invariant with t = r + s -1 = s( 1 + 1) -1.

We now show that the invariant holds for i + 1 if it holds for i. Let s ∈ N and let

i+1 = |O i+1 |.
By assumption, for s = s • ( i+1 + 1), there exists t such that with t carefully chosen probes on multiplications from G i , we are able to get:

• r matrices M j such that -→ w ∈ Im(M j ), 0 ≤ j ≤ r -1, where r = t + 1s ;

• s matrices M j such that O i ⊆ Im(M j ), r ≤ j ≤ t .
In what follows, the s last matrices are called the unfinished matrices. If we place s probes on each multiplication gadget g ∈ G i+1 , we can add a vector operand from -→ w + O i+1 to s • i+1 of the unfinished matrices. We thus obtain s • i+1 more matrices M j such that -→ w ∈ Im(M j ). We can further add all the i+1 operands from O i+1 to the s remaining unfinished matrices. We then get s matrices M j such that O i+1 ⊆ Im(M j ), which show the inductive statement.

From the above invariant, we can easily demonstrate the proposition statement. Indeed if we have -→ w ∈ O i for some i ∈ N then the invariant implies that for s = 1, there exists t ∈ N and P = {(g, j 1 , j 2 )} such that -→ w ∈ Im(M j ) for 0 ≤ j ≤ t and O i ⊆ Im(M t ), implying -→ w ∈ Im(M t ) as well. We then get t j=0 Im(M j ) = -→ w .

Proposition 4.5.2.

Let i > 1 such that G 1 ⊂ • • • ⊂ G i-1 = G i and - → w / ∈ O i . Then for any t ∈ N and P = {(g, j 1 , j 2 )} with |P| = t we have - → w / ∈ t j=0 Im(M T j ).
Proof of Proposition 4.5.2. Let us denote P = P 1 ∪ P 2 such that

P 1 = {(g, j 1 , j 2 ) ; g ∈ G i } and P 2 = {(g, j 1 , j 2 ) ; g / ∈ G i } with |P 1 | = t

Towards Efficient Construction of Tight t-Private Circuits

Our formal verification method exactly reveals all the t-probing attacks on standard shared circuits. A sound countermeasure to counteract these attacks is the use of refresh gadgets.

We discuss here how to transform a flawed standard shared circuit into a t-private circuit with exactly the minimum number of refresh gadgets.

In a first attempt, we easily show that refreshing the left operands of each multiplication in C is enough to provide t-probing security.

Proposition 4.5.3. A standard shared circuit C augmented with t-SNI refresh gadgets operating on the left operand of each multiplication gadget is t-probing secure.

Proof of Proposition 4.5.3. Let C be a standard shared circuit augmented with t-SNI refresh gadgets operating on the left operand of each multiplication gadget. From Corollary 4.4.3, the analysis of the t-probing security of C can be reduced to the analysis of the t-probing security of Flatten(C). In the latter, each multiplication takes as its left operand a new fresh encoding. Now let us assume that there exists a probing attack on C. We know from the linear algebra formulation above that this attack is characterized by a vector -→ w and a set of

t + 1 matrices such that Im(M 0 ) ∩ Im(M 1 ) ∩ • • • ∩ Im(M t ) = - → w . (4.25)
We also know that there exists at least one index 0 ≤ i ≤ t, such that matrix M i is completely defined by the row vector -→ w . Now let us assume that -→ w represents a probe on the left operand of a multiplication. Since this operand is a new fresh encoding that is used nowhere else, then it cannot be recovered from the linear combination of other operands. As a consequence, all the matrices must be defined by the same row vector -→ w . But at most t probes are available to target this last operand which is not enough to feed the t + 1 matrices and consequently leads to a contradiction. Let us now assume that -→ w represents a probe on the right operand of a multiplication. In that case, probes on right operands (including probe -→ w ) can feed up to t matrices in order to fulfill Equation (4.25). Without loss of generality, we assume these matrices to be M 0 , . . . M t-1 . The last matrix M t is then necessarily built from probes on left operands. Since all of them are fresh encodings, then Im(M t ) cannot include -→ w , which gives the second contradiction and completes the proof.

In a second attempt, we need to slightly modify Algorithm 3 so that it conducts an analysis on all the possible operands in order to return a complete list of the flawed ones. So far, it stops at the first flaw. With such a list for a standard shared circuit, we can show that refreshing only the flawed operands is enough to provide t-probing security. Proposition 4.5.4. A standard shared circuit C augmented with t-SNI refresh gadgets operating on each flawed operand, as revealed by our method, of its multiplication gadgets is t-probing secure.

Proof of Proposition 4.5.4. Let us consider a standard shared circuit C augmented with t-SNI refresh gadgets operating on each one of its α flawed operands. For each of these α flawed operands represented by the vector -→ w , there are a certain number β of sets of probes associated to sets of matrices (M j i ) 0≤i≤t for (1 ≤ j ≤ β) whose intersecting images are equal to -→ w . In each of these β sets of matrices, at least one matrix is exactly equal to -→ w . Refreshing the corresponding operand each time it is used in a multiplication makes it impossible to get a matrix equal to -→ w anymore in any of the β sets. As a consequence, all these sets of probes do not lead to a probing attack anymore. Furthermore, since we only turned operands into fresh encodings that are not reused, then this transformation do not lead to new probing attacks. Propositions 4.5.3 and 4.5.4 provide an upper bound of the required number of refresh gadgets in a standard shared circuit to achieve probing security at any order t. If we denote by m the number of multiplications in a standard shared circuit C and by o the number of flawed operands returned by our method, then C is to be augmented of at most r = min(m, o) refresh gadgets to achieve probing security at any order t. Given this upper bound, an iterative number of refresh gadgets from 1 to r can be inserted at each location in C in order to exhibit a tight private circuit with a minimum number of refresh gadgets.

Further Steps

Now that we are able to exactly determine the t-probing security of standard shared circuits, a natural follow-up consists in studying the t-probing security of their composition. In a first part, we establish several compositional properties, and then we show how they apply to the widely deployed SPN-based block ciphers. We eventually discuss the extension of our results to generic shared circuits.

Generic Composition

This section is dedicated to the statement of new compositional properties on tight private circuits. In a first attempt, we show that the composition of a t-private circuit whose outputs coincide with the outputs of t-SNI gadgets with another t-private circuit is still a t-private circuit.

Proposition 4.6.1. Let us consider a standard shared circuit C composed of two sequential circuits:

• a t-probing secure circuit C 1 whose outputs are all outputs of t-SNI gadgets,

• a t-probing secure circuit C 2 whose inputs are C 1 's outputs.

Then, C = C 2 • C 1 is t-probing secure.
Proof. As the outputs of the first circuit C 1 are the outputs t-SNI gadgets, we get from Lemma 4.3.9 that the input encodings of C 1 and the input encodings of C 2 are independent and uniformly distributed. Then, the proof is straightforward from Proposition 4.4.2. Basically, the analysis of C's t-probing security can be equivalently reduced to the analysis of the t-probing security of C = Flatten(C) in which each output of a t-SNI gadget is replaced by a fresh new input sharing of the corresponding value in the rest of the circuit, i.e. C 2 . As a consequence, C is t-probing secure if and only if both C 1 and C 2 are t-probing secure, which is correct by assumption.

In a second attempt, we establish the secure composition of a standard shared circuit that implements a (shared) linear surjective transformation through several sharewise addition gadgets, that we refer to as a t-linear surjective circuit, and a standard t-probing circuit.

Proposition 4.6.2. Let us consider a standard shared circuit C composed of two sequential circuits:

• a t-linear surjective circuit C 1 , exclusively composed of sharewise additions,

• a t-probing secure circuit C 2 whose inputs are C 1 's outputs. Then, C = C 2 • C 1 is t-probing secure.
Proof. We consider a standard shared circuit C with input -→ x = (x 1 , . . . , x n ) composed of a t-linear surjective circuit C 1 as input to a t-probing secure circuit C 2 . We denote by -→ y = (y 1 , . . . , y n ) the set of C 1 's outputs, or equivalently the set of C 2 's inputs. From Proposition 4.4.5, the t-probing security of C can be reduced to the t-probing security of circuit C = Flatten(C) for probes restricted to the multiplications' operands. In our context, C 1 is exclusively composed of sharewise additions, so the probes are restricted to C 2 . From Lemma 4.4.4, any set of probed variables on C 2 's multiplications operands (v 1 , . . . , v q ) can be written as the concatenation of the t + 1 vectors

- → v 0 = M 0 • - → y 0 , - → v 1 = M 1 • - → y 1 , . . . - → v t = M t • - → y t ,
where

Im(M T 0 ) ∩ Im(M T 1 ) ∩ • • • ∩ Im(M T t ) = ∅ . (4.26)
To achieve global t-probing security for C, we need to achieve a null intersection for matrices that apply on C's inputs instead of C 2 's inputs. As C 1 implements a linear surjective transformation f , there exists a matrix M f of rank n such that

∀ 0 ≤ i ≤ t, - → y i = M f • - → x i .
As a consequence, any set of probes (v 1 , . . . , v q ) in C as defined in Game 3 can equivalently be rewritten as the concatenation of the t + 1 vectors

- → v 0 = M 0 • M f • -→ x 0 , - → v 1 = M 1 • M f • -→ x 1 , . . . - → v t = M t • M f • - → x t .
By contradiction, let us assume that

Im(M T f • M T 0 ) ∩ Im(M T f • M T 1 ) ∩ • • • ∩ Im(M T f • M T t ) = ∅, that is, there exists a non-null vector - → w such that - → w ∈ Im(M T f • M T 0 ) ∩ Im(M T f • M T 1 ) ∩ • • • ∩ Im(M T f • M T t ). Equivalently, there exists - → z 0 , - → z 1 , . . . , - → z t such that - → w = M T f • M T 0 • - → z 0 = M T f • M T 1 • - → z 1 = . . . = M T f • M T 1 • - → z t .
From Equation (4.26), there exist at least two distinct indices i and j in {0, . . . , t}, such that

M T i • - → z i = M T j • - → z j . As - → w = M T f • M T i • - → z i = M T f • M T j • - → z j , the difference M T i • - → z i -M T j • - → z j belongs to M T f 's kernel. But from the surjective property of M f , M T
f has full column rank n , and thus a null kernel:

dim(Ker(M T f )) = n -dim(Im(M T f )) = 0. As a consequence, M T i • - → z i -M T j • - → z j = 0 and since M T i • - → z i = M T j • - → z j
we have a contradiction which completes the proof.

Eventually, we claim that two t-private circuits on independent encodings form a t-private circuit as well.

Proposition 4.6.3. Let us consider a standard shared circuit C composed of two parallel t-probing secure circuits which operate on independent input sharings. Then, C = C 1 C 2 is t-probing secure.

Proof. As the input sharings are independent, the result is straightforward from Lemma 4.4.4.

Application to SPN-Based Block Ciphers

An SPN-based block cipher is a permutation which takes as inputs a key k in {0, 1} κ and a plaintext p in {0, 1} n and outputs a ciphertext c in {0, 1} n , where n and κ are integers. As illustrated in Figure 4.11, it is defined by successive calls to a round function and by an optional expansion algorithm KS. The round function is a combination of a non linear permutation S and a linear permutation L. Note that if S's and KS's outputs are not t-SNI gadgets' outputs, then the linear surjective circuit can be extended to the last t-SNI gadgets' outputs of these circuits without loss of generality.

Proof. As S and KS are t-probing secure, it follows from Proposition 4.6.3, that when implemented in parallel on independent input encodings, their composition is t-probing secure as well. Then, as the output of their composition matches the outputs of t-SNI gadgets, then they can be sequentially composed with a t-probing secure circuit from Proposition 4.6.1. Finally, the composition of linear surjective circuits with t-probing secure circuits is ensured by Proposition 4.6.2, which completes the proof. Remark 4.6.5. This result can not be directly applied to the AES full block cipher as the outputs of the key schedule function are not SNI gadgets.

Extension to Generic Shared Circuits

We discuss hereafter two straightforward extensions of our work. Namely some constraints on gadgets that compose the standard shared circuits can be relaxed, and the considered circuit can easily be extended to work on larger finite fields.

On Standard Shared Circuits.

The method presented in this Chapter through Sections 4.4 and 4.5 aims to accurately establish the t-probing security of a standard shared circuit for any sharing order t + 1. Namely, it is restricted to Boolean shared circuits exclusively composed of ISW-multiplication gadgets, ISW-refresh gadgets, and sharewise addition gadgets. While the assumption on addition gadgets is quite natural, the restrictions made on the multiplication and refresh gadgets can be relaxed. The reduction demonstrated in Section 4.4 only expects the refresh gadgets to be t-SNI secure to ensure the equivalence between Game 1 and the initial t-probing security game. Afterwards, t-probing security is equivalently evaluated on a corresponding flattened circuit with probes on multiplications' operands only. Therefore, there is no restriction on the choice of refresh gadgets but their t-SNI security. While multiplication gadgets are also expected to be t-SNI secure for the equivalence between Game 1 and the initial t-probing security game to hold, this feature is not enough. To prove this equivalence, multiplication gadgets are also expected to compute intermediate products between every share of their first operand and every share of their second operand. Otherwise, our method could still establish the probing security of a circuit, but not in a tight manner, meaning that security under Game 3 would imply probing security but insecurity under Game 3 would not imply insecurity w.r.t. the original probing insecurity notion. Our method would hence allow false negatives, as state-of-the-art methods currently do. Beyond the advantages of providing an exact method, this restriction is not very constraining since not only the widely deployed ISW-multiplication gadgets but also the large majority of existing multiplication gadgets achieve this property.

On Circuits on Larger Fields.

Since ISW-multiplication gadgets and ISW-refresh gadgets can straightforwardly be extended to larger fields our reduction and verification method could easily be extended to circuits working on larger fields.

Application

Following the results presented in previous sections, we developed a tool in sage that takes as input a standard shared circuit and determines whether or not it is t-probing secure with Algorithm 3. Specifically, the standard shared circuit given as input to the tool is expressed as a set of instructions (XOR, AND, NOT, REFRESH) with operands as indices of either shared input values or shared outputs of previous instructions. Namely, the XOR instructions are interpreted as sharewise addition gadgets of fan-in 2, the NOT instructions as sharewise addition gadgets of fan-in 1 with the constant shared input (1, 0, . . . , 0), the AND instructions as ISW-multiplication gadgets of fan-in 2, and the REFRESH instructions as ISW-refresh gadgets of fan-in 1. As an application, we experimented our tool on several standard shared circuits. First, we analyzed the t-probing security of the small examples of Section 4.5 as a sanity check. Then, we investigated the t-probing security of the AES s-box circuit from [START_REF] Boyar | Logic Minimization Techniques with Applications to Cryptology[END_REF] and compared the result with what the maskComp tool produces. Additionally, we studied the impact of our tool to practical implementations (for both the randomness usage and the performance implications).

Application to Section 4.5 Examples

In order to have some sanity checks of our new method on simple standard shared circuits, we applied our tool to the examples given in Section 4.5, namely the standard shared circuits depicted in Figure 4.1 and Figure 4.10. Specifically, we first translated the two standard shared circuits into a list of instructions that is given to our tool. For each circuit, the first instruction gives the number of shared inputs. Then, each of the following instruction matches one of the four possible operations among XOR, AND, NOT, and REFRESH together with the indices of the corresponding one or two operands. The output of each such operation is then represented by the first unused index. At the end, from the generated list of instructions the tool derives a list of pairs of operands, namely the inputs to the multiplications in the circuit. Finally, Algorithm 3 is evaluated on the obtained list of operands.

The first example is based on a standard shared circuit that takes 2 shared inputs and then performs two operations, namely a sharewise addition (XOR) and an ISW-multiplication (AND). The AND instruction takes two inputs, namely the output of the XOR and one of the two inputs of the circuit, which means that there is only two possible target vectors for an attack to be mounted. They are displayed in the list list_comb. For both these two vectors successively displayed with variable comb, the tool generates their respective sets G 1 and O 1 , as defined in Section 4.5. Then since G 2 is equal to G 1 for both vectors, the tool outputs ---------------------------------- -----------------------------------( ' No attack found ') Figure 4.12: New method applied on example 1.

[x 1 ] [x 2 ] [⊕] [⊗] → ;; 2 XOR 1 2 AND 1 3 → list_comb = [1 ,3] ----------------------------------- comb = 1 = > NO ATTACK ( G2 = G1 ) G : [[(1 ,3) ] , []] O : [[3] , []]
- comb = 3 = > NO ATTACK ( G2 = G1 ) G : [[(1 ,3) ] , []] O : [[1] , []]
[x 1 ] [x 2 ] [x 3 ] [⊕] [⊕] [⊗] [⊗] [⊗] → ;; 3 XOR 1 2 XOR 2 3
AND 1 2 AND 4 5 AND 4 3 ---------------------------------- ---------------------------------- -----------------------------------( that no attack could be found. The circuit is thus t-probing secure. The complete process is described in Figure 4.12.

→ list_comb = [1 ,3 ,2 ,4 ,6] ----------------------------------- comb = 1 = > NO ATTACK ( G3 = G2 ) G : [[(1 ,2) ] , [(3 ,6) ,(3 ,4) ] , []] O : [[2] , [6 , 4] , []]
- comb = 3 = > NO ATTACK ( G3 = G2 ) G : [[(3 ,6) ,(3 ,4) ] , [(1 ,2) ] , []] O : [[6 , 4] , [2] , []]
- comb = 2 = > ATTACK G : [[(1 ,2) ] , [(3 ,6) ,(3 ,4) ]] O : [[1] , [6 , 4]]
The second example is based on a standard shared circuit that takes 3 shared inputs and then performs 5 operations, namely 2 sharewise additions (XOR) and 3 ISW-multiplications (AND). The three AND instructions take five distinct inputs, which means that there are five possible target vectors for an attack to be mounted. For the two first target vectors, no attack could be found as the tool expressed all the multiplications in the circuit with two sets G 1 and G 2 without finding any attack. For the third target vector, after the construction of G 2 an attack was found as the target vector belonged to the span of the set O 2 . The complete process is described in Figure 4.13. Moreover, we verified that by adding a refresh gadget on the operand on which our tool find an attack prior to the multiplication where it is used, the tool is not able any more to find an attack on the new circuit for this example. The results can be find in Figure 4.14.

Application to AES s-box

At Eurocrypt 2017, Goudarzi and Rivain [GR17] proposed an efficient software implementation of the s-box of the AES for higher-order masking. Based on the Boolean circuit of Boyer et al. [START_REF] Boyar | Logic Minimization Techniques with Applications to Cryptology[END_REF], their implementation evaluates the s-box on a state under bitslice representation with only 32 AND gates. In order to be t-probing secure without doubling the number of shares in the encoding of sensitive variables, a conservative choice was made to add a refresh ---------------------------------- ---------------------------------- ---------------------------------- ---------------------------------- -----------------------------------( ' No attack found ') Figure 4.14: New method applied on example 2 augmented with a refresh. gadget prior to each multiplication. As explained in Section 4.1, a major drawback of such conservative approach is the performance overhead induced by the number of calls to refresh gadgets due to the randomness usage.

[x 1 ] [x 2 ] [x 3 ] [⊕] [⊕] R [⊗] [⊗] [⊗] → ;;
→ ----------------------------------- list_comb = [3 , 8 , 6 , 1 , 4] ----------------------------------- comb = 3 = > NO ATTACK ( G3 = G2 ) G : [[(3 ,6) ,(3 ,4) ] , [(1 ,8) ] , []] O : [[6 , 4] , [8] , []]
- comb = 8 = > NO ATTACK ( G2 = G1 ) G : [[(1 ,8) ] , []] O : [[1] , []]
- comb = 6 = > NO ATTACK ( G2 = G1 ) G : [[(3 ,6) ] , []] O : [[3] , []]
- comb = 1 = > NO ATTACK ( G2 = G1 ) G : [[(1 ,8) ] , []] O : [[8] , []]
- comb = 4 = > NO ATTACK ( G2 = G1 ) G : [[(3 ,4) ] , []] O : [[3] , []]
In order to obtain efficient implementations of the AES s-box and to be tight on the number of randomness requirement, we have applied our tool to the circuit of the s-box reordered by Goudarzi and Rivain without any refreshing gadget. Interestingly, we obtained that no attack can be found for any masking order. More precisely, the tool first identified 36 distinct target vectors out of the 64 possible operands of multiplication gadgets (it can be easily checked on the circuit found in Section 6 of [GR17]). For each of the 36 target vectors, the corresponding set G 1 is constructed. Then, for every variable the algorithm stops as the respective sets G 2 are always equal to the respective sets G 1 . The complete report of the tool results can be found in Table 4.1. In the first and third columns of Table 4.1, the expressions of the target vectors as linear combinations of input variables or multiplications input are given and in the second and fourth columns, the corresponding sets G 1 are displayed, all in hexadecimal form.

To prove the security of the AES s-box circuit, our tool took only 427 ms. This speed is mainly due to the fact that for each possible target variable, only the set G 1 is computed. For comparison, we looked at the time taken by the maskVerif tool of [START_REF] Barthe | Verified Proofs of Higher-Order Masking[END_REF]. For a masking order t = 2, maskVerif found no attack in 35.9 sec and for t = 3 in approximately 10 hours.

For the sake of comparison, we also applied the maskComp tool on the same circuit. We obtained that maskComp adds refresh gadgets prior to each multiplication in the circuit, transforming it into a new t-NI secure circuit. Since our tool has shown that the circuit is t-probing secure with no refresh gadgets, adding those refresh gadgets implies an overhead in the t-probing security that can lead to less efficient practical implementations. As an illustration, we have implemented a bitslice version of the AES s-box circuit for a generic masking order to see the impact in performances between a full refresh approach (i.e. the conservative choice of Goudarzi and Rivain and the result of maskComp) and a no refresh approach (our new tool). Each of this two approaches produces a circuit that is at least t-probing secure for any masking order t and that is securely composable with other circuits (since maskComp produce a t-NI circuit and from the result of Section 4.6. To be consistent with the state of the art, the randomness in our implementations can be obtained from a TRNG with two different settings: a first setting with a free TRNG that outputs 32-bit of fresh randomness every 10 clock cycles (as in [GR17]) and a second setting with a constrained TRNG that outputs 32-bit of fresh randomness every 80 clock cycles (as in [START_REF] Journault | Very High Order Masking: Efficient Implementation and Security Evaluation[END_REF]). The performance results can be found in Table 4.2. For both approaches, the number of refresh gadgets used and the number of randomness needed are displayed. Then, the timing in clock cycles for both settings are shown. We can see that our tool allows to divide by 2 the number of required randomness and benefits from an asymptotic gain of up to 43% in speed. The comparison of the timings for several masking orders are depicted in Figure 4.15. Chapter 5 Implementation

Introduction

In this chapter, we present a case study on ARM (v7) architectures, which are today the most widespread in embedded systems (privileged targets of side-channel attacks). We provide an extensive and fair comparison between the different methods of the state of the art and the ones proposed in Chapter 3, and a benchmarking on optimized implementations of higher-order masked blockciphers. For this purpose, we follow a bottom-up approach and start by investigating the efficient implementation of the base-field multiplication, which is the core elementary operation of the ISW-based masking schemes. We propose several implementations strategies leading to different time-memory trade-offs. We then investigate the main building blocks of existing masking schemes, namely the ISW (and its variants) and CPRR schemes. We optimize the implementation of these schemes and we describe parallelized versions that achieve significant gains in performances. From these results, we propose fine-tuned variants of our generic decomposition methods for three cases (full field case, median case and Boolean case) and the algebraic decomposition methods, which allows us to compare them in a practical and optimized implementation context. We also investigate efficient polynomial methods for the specific s-boxes of two important blockciphers, namely AES and PRESENT.

As an additional contribution, we put forward an alternative strategy to polynomial methods which consists in applying bitslicing at the s-box level. More precisely, the s-box computations within a block cipher round are bitsliced so that the core nonlinear operation is not a field multiplication anymore (nor a quadratic polynomial) but a bitwise logical AND between two m-bit registers (where m is the number of s-box computations). This allows us to translate compact hardware implementations of the AES and PRESENT s-boxes into efficient masked implementations in software. This approach has been previously used to design blockciphers well suited for masking [START_REF] Grosso | LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations[END_REF] but, to the best of our knowledge, has never been used to derive efficient higher-order masked implementations of existing standard blockciphers such as AES or PRESENT. We further provide implementation results for full blockciphers and discuss the security aspects of our implementations.

Our results clearly demonstrate the superiority of the bitslicing approach (at least on 32-bit ARM architectures). Our masked bitslice implementations of AES and PRESENT are significantly faster than state-of-the-art polynomial methods with fine-tuned low-level implementations. In particular, an encryption masked at the order 10 only takes a few milliseconds with a 60 MHz clock frequency (specifically 8ms for AES and 5ms for PRESENT).

Each implementation presented in this chapter can be found on GitHub for public usage at the following link [CRX].

Approach

In this chapter, we describe the algorithmic and implementation tricks used to produce efficient implementation of protected block-ciphers with higher-order masking. All the implementation were made in ARM assembly and can be found on GitHub. To do so, we proceed with a bottom-up approach. First, we described the different building blocks that are used in the implementation of a block-ciphers, from the field multiplication to secure non-linear operations. Then, we give implementation performances for the evaluation of secure generic s-boxes following the results of Chapter 3. We also provide implementation results for structured s-boxes such as the one of the AES and the one of PRESENT. Finally, we describe and give implementation results for the two block-ciphers AES and PRESENT, using the different s-boxes implemented. Thank to the result of Chapter 4, the implementation of the AES can be done with minimal randomness consumption, as no refreshes of the sharings are needed.

Building Blocks

Field Multiplications

In this section, we focus on the efficient implementation of the multiplication over F 2 λ where λ is small (typically λ ∈ [ [4,10]]). The fastest method consists in using a precomputed table mapping the 2 2λ possible pairs of operands (a, b) to the output product a • b. The size of this table is given in Table 5.1 with respect to λ.

In the context of embedded systems, one is usually constrained on the code size and spending several kilobytes for (one table in) a cryptographic library might be prohibitive. That is why we investigate hereafter several alternative solutions with different time-memory trade-offs. Specifically, we look at the classical binary algorithm and exp-log multiplication methods. We also describe a tabulated version of Karatsuba multiplication, and another tablebased method: the half-table multiplication. The obtained implementations are compared in terms of clock cycles, register usage, and code size (where the latter is mainly impacted by precomputed tables).

In the rest of this section, the two multiplication operands in F 2 λ will be denoted a and b. These elements can be seen as polynomials a

(x) = λ-1 i=0 a i x i and b(x) = λ-1 i=0 b i x i over F 2 [x]/p(x)
where the a i 's and the b i 's are binary coefficients and where p is a degreeλ irreducible polynomial in F 2 [x]. In our implementations, these polynomials are simply represented as λ-bit strings a = (a λ-1 , . . . , a 0 ) 2 or equivalently a = λ-1 i=0 a i 2 i (and similarly for b).

Binary Multiplication

The binary multiplication algorithm is the most basic way to perform a multiplication on a binary field. It consists in evaluating the following formula:

a(x) • b(x) = • • • b λ-1 a(x)x + b λ-2 a(x) x + b λ-3 a(x) • • • x + b 0 a(x) , ( 5.1)
by iterating over the bits of b. A formal description is given in Algorithm 4.

(x), b(x) ∈ F 2 [x]/p(x) Output: a(x) • b(x) ∈ F 2 [x]/p(x) 1: r(x) ← 0 2: for i = λ -1 down to 0 do 3: r(x) ← x • r(x) mod p(x) 4: if b i = 1 then r(x) ← r(x) + a(x) return r(x) mod p(x)
The reduction modulo p(x) can be done either inside the loop (at Step 3 in each iteration) or at the end of the loop (at Step 6). If the reduction is done inside the loop, the degree of

x • r(x) is at most λ in each iteration. So we have x • r(x) mod p(x) = x • r(x) -p(x) if r λ-1 = 1 x • r(x) otherwise (5.2)
The reduction then consists in subtracting p(x) from x • r(x) if and only if r λ-1 = 1 and doing nothing otherwise. In practice, the multiplication by x simply consists in left-shifting the bits of r and the subtraction of p is a simple XOR. The tricky part is to conditionally perform the latter XOR with respect to the bit r λ-1 as we aim for a branch-free code. This is achieved using the arithmetic right shift1 instruction (sometimes called signed shift) to compute (r 1) ⊕ (r λ-1 × p) by putting r λ-1 at the sign bit position, which can be done in 3 ARM instructions (3 clock cycles) as follows:

LSL $tmp , $res , #(32 -n )

;; tmp = r_ {n -1} AND $tmp , $mod , $tmp , ASR #32 ;; tmp = p & ( tmp ASR 32) EOR $res , $tmp , $res , LSL #1 ;; r = ( r_ {n -1} * p ) ^( r << 1)

Step 4 consists in conditionally adding a to r whenever b i equals 1. Namely, we have to compute r ⊕ (b i • a). In order to multiply a by b i , we use the rotation instruction to put b i in the sign bit and the arithmetic shift instruction to fill a register with b i . The latter register is then used to mask a with a bitwise AND instruction. The overall Step 4 is performed in 3 ARM instructions (3 clock cycles) as follows:

ROR $opB , #31

;; b_i = sign ( opB ) AND $tmp , $opA , # opB , ASR #32 ;; tmp = a & ( tmp ASR 32) EOR $res , $tmp ;; r = r ^( a * b_i )

Variant. If the reduction is done at the end of the loop, Step 3 becomes a simple left shift, which can be done together with Step 4 in 3 instructions (3 clock cycles) as follows:

ROR $opB , #31 ;; b_i = sign ( opB ) AND $tmp , $opA , $opB , ASR #32 ;; tmp = a & ( tmp ASR 32) EOR $res , $tmp , $res , LSL #1 ;; r = ( a * b_i ) ^( r << 1)

The reduction must then be done at the end of the loop (Step 6), where we have r(x) = a(x) • b(x) which can be of degree up to 2λ -2. Let r h and r be the polynomials of degree at most λ -2 and λ -1 such that r(x) = r h (x) • x λ + r (x). Since we have r(x) mod p(x) = (r h (x) • x λ mod p(x)) + r (x), we only need to reduce the high-degree part r h (x) • x λ . This can be done by tabulating the function mapping the λ -1 coefficients of r h (x) to the λ -2 coefficients of r h (x) • x λ mod p(x). The overall final reduction then simply consists in computing

T [r λ] ⊕ (r • (2 λ -1)
), where T is the corresponding precomputed table.

Exp-Log Multiplication

Let g ∈ F 2 λ be a generator of the multiplicative group F * 2 λ . We shall denote by exp g the exponential function defined over [[0, 2 λ -1]] as exp g ( ) = g , and by log g the discrete logarithm function defined over F * 2 λ as log g = exp -1 g . Assume that these functions can be tabulated (which is usually the case for small values of λ). The multiplication between field elements a and b can then be efficiently computed as

a • b = exp g (log g (a) + log g (b) mod 2 λ -1) if a = 0 and b = 0 0 otherwise (5.3) Le us denote t = log g (a) + log g (b). We have t ∈ [[0, 2 λ+1 -2]] giving t mod 2 λ -1 = t -2 λ + 1 if t λ = 1 t otherwise (5.4)
where t λ is the most significant bit in the binary expansion t = λ i=0 t i 2 i , which can be rewritten as t mod 2 λ -1 = (t + t λ ) • (2 λ -1). This equation can be evaluated with 2 ARM instructions2 (2 clock cycles) as follows:

ADD $tmp , $tmp , LSR # n ;; tmp = tmp + tmp > > n AND $tmp , #(2^n -1)

;; tmp = tmp & (2^n -1)

Variant. Here again, a time-memory trade-off is possible: the exp g table can be doubled in order to handle a (λ + 1)-bit input and to perform the reduction. This simply amounts to considering that exp g is defined over

[[0, 2 λ+1 -2]] rather than over [[0, 2 λ -1]].
Zero-testing. The most tricky part of the exp-log multiplication is to manage the case where a or b equals 0 while avoiding any conditional branch. Once again we can use the arithmetic right-shift instruction to propagate the sign bit and use it as a mask. The test for zero can then be done with 4 ARM instructions (4 clock cycles) as follows:

Karatsuba Multiplication

The Karatsuba method is based on the following equation:

a • b = (a h + a )(b h + b ) x λ 2 + a h b h (x n + x λ 2 ) + a b (x λ 2 + 1) mod p(x) (5.5)
where a h , a , b h , b are the polynomials with degree at most λ 2 -1 such that a(x) = a h x λ 2 +a and b(x) = b h x λ 2 + b . The above equation can be efficiently evaluated by tabulating the following functions:

(a h + a , b h + b ) → (a h + a )(b h + b ) x λ 2 mod p(x) , (a h , b h ) → a h b h (x λ + x λ 2 ) mod p(x) , (a , b ) → a b (x λ 2 + 1) mod p(x) .
We hence obtain a way to compute the multiplication with 3 look-ups and a few XORs based on 3 tables of 2 λ elements.

In practice, the most tricky part is to get the three pairs (a h ||b h ), (a ||b ) and (a h +a ||b h +b ) to index the table with the least instructions possible. The last pair is a simple addition of the two first ones. The computation of the two first pairs from the operands a ≡ (a h ||a ) and b ≡ (b h ||b ) can then be seen as the transposition of a 2 × 2 matrix. This can be done with 4 ARM instructions (4 clock cycles) as follows:

EOR $tmp0 , $opA , $opB , LSR #( n /2) ;; tmp0 = [ a_h | a_l ^b_h ] EOR $tmp1 , $opB , $tmp0 , LSL #( n /2) ;; tmp1 = [ a_h | a_l | b_l ] BIC $tmp1 , #(2^n *(2^( n /2) -1) ) ;; tmp1 = [ a_l | b_l ] EOR $tmp0 , $tmp1 , LSR #( n /2) ;; tmp0 = [ a_h | b_h ]

Half-Table Multiplication

The half-table multiplication can be seen as a trade-off between the Karatsuba method and the full-table method. While Karatsuba involves 3 look-ups in three 2 λ -sized tables and the full-table method involves 1 look-up in a 2 2λ -sized table, the half-table method involves 2 look-ups in two 2 3λ 2 -sized tables. It is based on the following equation:

a • b = b h x λ 2 (a h x λ 2 + a ) + b (a h x λ 2 + a ) mod p(x) , (5.6)
which can be efficiently evaluated by tabulating the functions:

(a h , a , b h ) → b h x λ 2 (a h x λ 2 + a ) mod p(x) , (a h , a , b ) → b (a h x λ 2 + a ) mod p(x) .
Once again, the barrel shifter is useful to get the input triplets efficiently. Each look-up can be done with two ARM instructions (for a total of 8 clock cycles) as follows:

Performance

The obtained performance is summarized in Table 5.2 in terms of clock cycles, register usage, and code size. For clock cycles, the number in brackets indicates instructions that need to be done only once when multiple calls to the multiplication are performed (as in the secure multiplication procedure described in the next section). These are initialization instructions such as loading a table address into a register. For λ > 8, elements take two bytes to be stored (assuming λ ≤ 16) which implies an overhead in clock cycles and a doubling of the table size. For most methods, the clock cycles and register usage are constant w.r.t. λ ≥ 8, whereas the code size depends on λ. For the sake of illustration, we therefore additionally display the code size (and corresponding LUT sizes) in Figure 5.1 for several values of λ.

Remark 5.3.1. For λ > 8, elements take two bytes to be stored (assuming λ ≤ 16). Two options are then possible for look-up tables: one can either store each λ-bit element on a full 32-bit word, or store two λ-bit elements per 32-bit word (one per half-word). The former option has a strong impact on the LUT sizes, and hence on the code size, which is already expected to be important when λ > 8. Therefore we considered the latter option, which has an impact on performances since we either have to load two bytes successively, or to load one 32-bit word and select the good half-word (which is actually costlier than two loads). We observe that all the methods provide different time-memory trade-offs except for Karatsuba which is beaten by the exp-log method (v1) both in terms of clock cycles and code size. The latter method shall then always be preferred to the former (at least on our architecture). As expected, the full-table method is by far the fastest way to compute a field multiplication, followed by the half-table method. However, depending on the value of λ, these methods might be too consuming in terms of code size due to their large precomputed tables. On the other hand, the binary multiplication (even the improved version) has very poor performance in terms of clock cycles and it should only be used for extreme cases where the code size is very constrained. We consider that the exp-log method v2 (i.e. with doubled exp-table) is a good compromise between code size an speed whenever the full-table and half-table methods are not affordable (which might be the case for e.g. λ ≥ 8). In the following, we shall therefore focus our study on secure implementations using the exp-log (v2), half-table or full-table method for the base field multiplication.

Secure Non Linear Operations

In this section we describe optimized low-level implementations of the four following secure multiplications and one secure evaluation of quadratic functions: Each secure operation is described at the algorithmic level and at the implementation level (with possible implementation tricks). For the ISW-like multiplications and the CPRR evaluation, we also provide a parallelized version of the code Then, we provided some implementation results (in both clock cycles and code size) and compare the different schemes in terms of performances, randomness consumption, and security guarantees.

ISW (Ishai-Sahai-
Remark 5.3.2. For the rest of this section, the field multiplication between two elements a and b over F 2 λ , for any λ, is denoted by a • b.

ISW: the Standard Probing-Secure Multiplication

Let us recall the ISW multiplication scheme introduced in Chapter 2.

Algorithm 5 ISW (Ishai-Sahai-Wagner, Crypto'03)

Input: sharings (a 1 , . . . , a d ) ∈ {0, 1} 32×d and (b 1 , . . . , b d ) ∈ {0, 1} 32×d Output: sharing (c 1 , . . . , c d ) ∈ {0, 1} 32×d such that i c i = ( i a i ) • ( j b j ) 1: for i = 1 to d do 2: c i ← a i • b i 3: for i = 1 to d do 4: for j = i + 1 to d do 5: s ← {0, 1} 32 6: s ← (s ⊕ (a i • b j )) ⊕ (a j • b i ) 7: c i ← c i ⊕ s 8: c j ← c j ⊕ s return (c 1 , . . . , c d )
From two sharings (a 1 , . . . , a d ) and (b 1 , . . . , b d ), the ISW multiplication simply computes all the d 2 crossed products a i • b j which are then summed in d new shares c i with new random elements r i,j . Each new random element is involved twice in the new shares implying

i c i = i,j a i • b j = ( i a i ) • ( j b j ).
From the implementation viewpoint, we use the approach suggested in [START_REF] Coron | Higher Order Masking of Look-Up Tables[END_REF] that directly accumulates each intermediate result r i,j in the output share c i so that the memory cost is

O(d) instead of O(d 2
) when the r i,j 's are stored. In order to push forward the optimization, we also propose a version of the code where the nested loops are unrolled for specific values of d, namely when d is a power of 2. The performance of our low-level implementations is summarized in Table 5.3. We observe that unrolling the loops allows us to save 15% to 23% clock cycles with an overhead factor from 3 to 200 times the code size. The only case where the unrolling fully benefits in both time and memory is for d = 2.

BDF + : a Bounded-Moment Secure Multiplication

At Eurocrypt 2017, Barthe et al. introduced a new way to compute a secure multiplication specifically tailored for the bitwise context (i.e. for bitsliced implementations) [START_REF] Barthe | Parallel Implementations of Masking Schemes and the Bounded Moment Leakage Model[END_REF]. Their scheme handles registers holding all the shares of a given bit whereas in traditional ISW-based scheme, the shares of a variable are stored in different registers for security reasons. Nevertheless, Barthe et al. show that their multiplication is secure in the relaxed bounded moment model, which is argued to be sound in practice.

Intuitively the BDF + multiplication can be decomposed into different steps: the loading of the input shares a and b; the computation of the partial products between a and b; the loading of fresh randomness r; and the compression phase where these partial products are XORed all together and separated by the fresh randomness.

Its implementation is especially efficient when the number of shares d is equal to the size of the registers in the target architecture. This has been shown in [START_REF] Journault | Very High Order Masking: Efficient Implementation and Security Evaluation[END_REF] for the case d = 32. However, a question left open in the latter work is the scenario where the number of shares mismatches the register size. This issue is addressed hereafter.

For this purpose, we generalize the BDF + algorithm to a scenario where d can be lower than the register size. We propose a parallel version of this algorithm in which several sharings are stored in a register (e.g. 4 sharings of order d = 8 in one 32-bit register) and we describe an efficient way to perform sharing-wise rotations to keep good performance in such a non-optimal scenario. The main restriction is that our generalization only works for masking orders that are a power of 2 (so that the sharing size divides the register size), including the case d = 2 which was not taken into account in the original publication. The optimized BDF + multiplication is described in Algorithm 6.

Encoding. In order to make full use of the register when d is less than 32 (i.e. d is not equal to the architecture size), but d is a power of 2, we fill the input registers with k = 32/d words of d shares. We thus process k secure multiplications in parallel. More specifically, let us denote w 0 , . . . , w 31 the bits of a 32-bit register w (from MSB to LSB). For d = 16, w encodes 2 secret bits z 0 and z 1 such that 15 i=0 w i = z 0 and 31 i=16 w i = z 1 . For d = 8, w encodes 4 secret bits z 0 , z 1 , z 2 and z 3 such that 7 i=0 w i = z 0 and 15 i=8 w i = z 1 and 23 i=16 w i = z 2 and 31 i=24 w i = z 3 , and so on. Efficient sharing-wise rotation. Algorithm 6 can directly be applied on multi-sharing

Algorithm 6 BDF + (Barthe et al. , Eurocrypt'17) Input: shares a = (a 1 , • • • , a d ) ∈ {0, 1} 32 , shares b = (b 1 , • • • , b d ) ∈ {0, 1} 32 Output: shares c = (c 1 , • • • , c d ) ∈ {0, 1} 32 corresponding to a • b 1: x 1 ← a ∧ b 2: r ← {0, 1} 32 3: y 1 ← x 1 ⊕ r 4: if d = 2 then 5:
x 2 ← a ∧ ROT(b, 1) 6:

y 2 ← y 1 ⊕ x 2 7: c ← y 2 ⊕ ROT(r, 1) 8: for i = 1 to d/2 -1 do 9: if i mod 2 = 0 then 10: r ← {0, 1} 32 11: x 2i ← a ∧ ROT(b, i) 12: x 2i+1 ← ROT(a, i) • b 13: y 3i-1 ← y 3i-2 ⊕ x 2i 14: y 3i ← y 3i-1 ⊕ x 2i+1 15: y 3i+1 ← y 3i ⊕ ROT(r, i mod 2) 16: x d ← a ∧ ROT(b, d/2) 17: c ← y 3 (d-1)/2 +1 ⊕ x d return c
input registers. The only operation which needs to be modified accordingly is the rotation ROT(w, i). We propose an efficient low-level implementation for such a sharing-wise rotation. Our method relies on the observation that applying an i-bit rotation to every d-bit chunk in a word w can be obtained by the following equation:

ROT(w, i) = (w i) • mask d,i ⊕ (w d -i) • mask d,i (5.7)
where mask d,i is a selection mask defined as

mask d,i = 11 . . . 1 d-i 00 . . . 0 i • • • 11 . . . 1 d-i 00 . . . 0 i ,
and mask d,i denotes its complement. From this equation we can directly compute the sharingwise rotation. The main trick in the implementation is to efficiently deal with the generation of mask d,i and the sharing-wise rotation. The mask generation is decomposed into two steps. The first step allows to setup the mask correctly: mask d,0 is initialized with the value 0xFFFFFFFF. We then need a correction value which will be used to update the mask correctly. correction is initialized with values given in Table 5.4. Note that these operations are performed only once at the beginning of the multiplication. The second step will update the mask for the rotation according to the offset of the rotation given by the following formula:

mask d,i = mask d,0 ⊕ (correction i)
In practice, we only store mask d,0 and correction in two registers and we update them accordingly in each iteration of the loop. The cost of the update is 2 cycles. Note that we make use of another register in order to store mask d,1 (i.e. the rotation by 1) which is always needed to compute the rotations of the random values (instead of computing it again each time).

The rotation ROT(w, i) is then quite straightforward to implement as describes hereafter:

;; rotation of $w by $i AND $tmp , $mask , $w , LSL $i LSR $w , $w , $ (d -i ) BIC $w , $w , $mask EOR $w , $tmp , $w

Since the offsets of the shift lie in a register, we cannot benefit from the combined barrel shifter. Hence the overall cost of one rotation is 5 cycles. In Table 5.5, we report results of our implementation of the BDF + multiplication for d ranging from 2 to 32 for the generic version and an unrolled version (where the main advantage is to be able to hardcode the masks and values for the shifts). We observe that the unrolled version for d = 32 is faster and has less code size than for d = 16. This is easily explained by the fact that we can make full use of the barrel shifter in the case d = 32. Moreover, we observe that the unrolled version is 40% to 80% faster than the regular version. This is due to the fact that we can hardcode the masks, which makes the barrel shifter work again. The code size of the unrolled version ranges from 0.3 to 3 times the generic one. Note also that the code size of the generic version is decreasing as d grows because we compute the correction value iteratively (i.e. it needs log(32/d) iterations).

BBP + : Towards Optimal Randomness Consumption

Belaïd et al. at Eurocrypt 2016 [START_REF] Belaïd | Randomness Complexity of Private Circuits for Multiplication[END_REF] tackled the problem of minimizing the amount of randomness required in a secure multiplication. They described a generic algorithm which makes use of less randomness than ISW, reducing the former randomness requirement from

d (d-1) 2 to d 2 4 + d.
As opposed to the ISW multiplication (which achieves (d -1)-SNI security), this algorithm is only proven (d -1)-NI secure. The original description of this secure multiplication (see [START_REF] Belaïd | Randomness Complexity of Private Circuits for Multiplication[END_REF]) is generic for any masking order d ≥ 4 (specific algorithms for the case where d = 2 and 3 are given in their paper). However, it makes use of several conditional branches to process additional operations depending on the parity of the order d and/or of the loop index i.

We rewrote the algorithm such that all the conditional branches are removed, without affecting the correctness (see Algorithm 7). These changes lead to several improvements in practice: first replacing if/ statement with loops allows avoiding several conditional branches treatment that are quit expensive in ARM assembly. Moreover, by rewriting the algorithm in such a way, we can compute all the randomness on-the-fly and avoid multiple load and store instructions for the correction step. Such improvements come at the cost of a less generic algorithm (it only works for even orders d). For the sake of comparison, we have implemented both algorithms to show the performance gained in clock cycles and code size (see Table 5.6). We can see that our improvements allow a gain in timing ranging from 18% to 20% with an overhead of only 80 bytes of memory. Furthermore, we also unrolled the nested loops in order to get better results in timings. The timing gain ranges from 17% to 60% with an overhead factor between 3.5 and 50 for the code size for d ≥ 8 only. For smaller values of d, the unrolled version is better for both timing and code size. LoopRow(i, i + 3) 10:

. , c d ) ∈ {0, 1} 32×d such that i c i = ( i a i ) • ( j b j ) 1: c 1 ← a 1 • b 1 2: c 2 ← a 2 • b 2 3: for i = 3 to d -1 by 2 do 4: c i ← a i • b i 5: c i+1 ← a i+1 • b i+1 6: s i ← {0, 1}
c i ← c i ⊕ (r i,i+1 ⊕ a i • b i+1 ⊕ a i+1 • b i ) 11: LoopRow(i + 1, i + 3) 12: c i+1 ← c i+1 ⊕
c i ← c i ⊕ r ⊕ (a i • b j ⊕ a j • b i ) ⊕ s j-1 ⊕ (a i • b j-1 ⊕ a j-1 • b i ) 4: c j ← c j ⊕ r i,j

BPCZ: Towards Security against Horizontal Attacks

At CHES 2016, Battistello et al. described a horizontal side-channel attack on the standard ISW multiplication [START_REF] Battistello | Horizontal Side-Channel Attacks and Countermeasures on the ISW Masking Scheme[END_REF]. This attack essentially consists in reducing the noise in the . Such an attack is inherent to the ISW scheme and implies that despite the probing-security, increasing the masking order d implies increasingly high noise requirements for the masking countermeasure to bring security improvements (i.e., for the noise to be large enough after averaging, it has to increase before averaging).

Battistello et al. also proposed a mitigation of such a horizontal attack. Their multiplication, given in Algorithm 9, is similar to the standard ISW multiplication but the matrix of the crossed products a i • b j is computed differently (see Algorithm 10): refreshings are regularly inserted to avoid the repeated apparition of each share a i (resp. b i ). The RefreshMasks operation is a simple ISW-based refreshing as described later in Section 5.3.3. The authors also proved that their multiplication is (d -1)-SNI secure.

c i ← c i + s 9: c j ← c j + s return c 1 , ..., c d
The implementation of Algorithm 9 is straightforward (same as ISW). The main challenge is to efficiently implement Algorithm 10 in a recursive way. In fact, due to the restrictive amount of registers available, using functions to perform the recursion in ARM assembly becomes very costly. Each recursive call needs to have access to several informations: the correct set of input sharings, namely the start of #" X 1 , #" X 2 , #" Y 1 and #" Y 2 as well as the correct addresses for the output sharings. This means that several registers containing those information need to be pushed to the stack prior to each call to a recursive function and popped before the computation. As push and pop are basically load and store in ARM assembly the total cost of managing the inputs and outputs of a recursive function is approximately equal to a dozen of clock cycles for each recursive calls. This costs, on top of the associated jumps for each recursive function, is equivalent to the computation of a complete ISW multiplication.

Algorithm 10 MatMult Input: the d-sharings (x i ) i∈ [1..d] and (y i ) i∈ [1..d] of x * and y * respectively Output: the d 2 -sharing (M i,j ) i∈ [1..d],j∈ [1..d

] of x * • y * 1: if n = 1 then 2: # " M ← [x 1 • y 1 ] 3:
#" X (1) ← (x 1 , . . . , x d/2 ), #" X (1) ← (x d/2+1 , . . . , x d )

4:

#" Y (1) ← (y 1 , . . . , y d/2 ), #" Y (1) ← (y d/2+1 , . . . , y d ) 5:

# " M (1,1) ← MatMult( #" X (1) , #" Y (1) )

6:

#" X (1) ← RefreshMasks( #" X (1) ), #" Y (1) ← RefreshMasks( #" Y (1) )

7:

# " M (1,2) ← MatMult( #" X (1) , #" Y (2) )

8:

# " M (2,1) ← MatMult( #" X (2) , #" Y (1) )

9:

#" X (2) ← RefreshMasks( #" X (2) ), #" Y (2) ← RefreshMasks( #" Y (2) ) 10:

# " M (2,2) ← MatMult( #" X (2) , #" Y (2) ) Therefore and since we restrict ourselves in this study to d ≤ 32, we developed the MatMult procedure with macros. Specifically, for each masking order d that is a power of 2, we simply implement Algorithm 10 using macros for each possible input sharing size d ∈ {2, 4, . . . , 32}, which allows us to save several clock cycles. However the main drawback of implementing the MatMult procedure in such way is that the code size grows exponentially. To lower down the explosion of the code size, we have also implemented a version of the code where the terminal case macro (for d = 2) is implemented as a function. This allows us to divide by up to 5 the code size while having a performance decrease of around 20%. Both timing and code size for the BPCZ multiplication with the two versions of the MatMult procedure are given in Table 5.7.

11: # " M ← # " M (1,1) # " M (1,2) # " M (2,1) # " M (2,

CPRR evaluation.

The CPRR scheme was initially proposed in [START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF] as a variant of ISW to securely compute multiplications of the form x → x • (x) where is linear, without requiring refreshing. It was then shown in [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF]

c i ← c i + s 14: c j ← c j + s return c 1 , ...c d following equation f (x 1 + x 2 + • • • + x d ) = 1≤i<j≤d f (x i + x j + s i,j ) + f (x j + s i,j ) + f (x i + s i,j ) + f (s i,j ) + d i=1 f (x i ) + (d + 1 mod 2) • f (0) (5.8)
which holds for every (x i ) i ∈ (F 2 λ ) d , every (s i,j ) 1≤i<j≤d ∈ (F 2 λ ) d(d-1)/2 , and every quadratic function f over F 2 λ .

From a d-sharing (x 1 , x 2 , . . . , x d ), the CPRR scheme computes an output d-sharing (y 1 , y 2 , . . . , y d ) as follows:

1. for every 1 ≤ i < j ≤ d, sample two random values r i,j and s i,j over F 2 λ , 2. for every 1 ≤ i < j ≤ d, compute r j,i = r i,j + f (x i + s i,j ) + f (x j + s i,j ) + f ((x i + s i,j ) +

x j ) + f (s i,j ) , 3. for every 1 ≤ i ≤ d, compute y i = f (x i ) + j =i r i,j , 4. if d is even, set y 1 = y 1 + f (0).
According to 5.8, we then have d i=1 y i = f d i=1 x i ), which shows that the output sharing (y 1 , y 2 , . . . , y d ) well encodes y = f (x). The overall computation is summarized in Algorithm 11.

In [START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF][START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF] it is argued that in the gap where the field multiplication cannot be fully tabulated (2 2λ elements is too much) while a function f : F 2 λ → F 2 λ can be tabulated (2 λ elements fit), the CPRR scheme is (likely to be) more efficient than the ISW scheme. This is because it essentially replaces (costly) field multiplications by simple look-ups. We present in the next section the results of our study for our optimized ARM implementations.

Parallelization

Both ISW and CPRR schemes work on λ-bit variables, each of them occupying a full 32-bit register. Since in most practical scenarios, we have λ ∈ [ [4,8]], this situation is clearly suboptimal in terms of register usage, and presumably suboptimal in terms of timings. A natural idea to improve this situation is to use parallelization. A register can simultaneously store m := 32/λ values, we can hence try to perform m ISW/CPRR computations in parallel (which would in turn enable to perform m s-box computations in parallel). Specifically, each input share is replaced by m input shares packed into a 32-bit value. The ISW (resp. CPRR) algorithm loads packed values, and performs the computation on each unpacked λ-bit chunk one-by-one. Using such a strategy allows us to save multiple load and store instructions, which are among the most expensive instructions of ARMv7 assembly (3 clock cycles). Specifically, we can replace m load instructions by a single one for the shares a i , b j in ISW (resp. x i , x j in CPRR) and the random values r i,j , s i,j (read from the TRNG), we can replace m store instructions by a single one for the output shares, and we can replace m XOR instructions by a single one for some of the addition involved in ISW (resp. CPRR). On the other hand, we get an overhead for the extraction of the λ-bit chunks from the packed 32-bit values. But each of these extractions takes a single clock cycle (thanks to the barrel shifter), which is rather small compared to the gain in load and store instructions.

Remark 5.3.3. Note that using parallelization in our implementations does not compromise the probing security. Indeed, we pack several bytes/nibbles within one word of the cipher state but we never pack (part of) different shares of the same variable together. The probing security proofs hence apply similarly to the parallel implementations. 3

Refresh gadgets

ISW Refresh

The ISW-based mask refreshing is pretty similar to an ISW multiplication, but it is actually much faster since it involves no field multiplications and fewer additions (most terms being multiplied by 0). It simply consists in processing: for i = 1 .. d : for j = i + 1 .. d : r ← $; a i ← a i + r; a j ← a j + r;

A straightforward implementation of this process is almost 3 times faster than the fastest ISW multiplication, namely the full-table one (see Figure 5.2).

We can actually do much better. Compared to a standard ISW implementation, the registers of the field multiplication are all available and can hence be used in order to save several loads and stores. Indeed, the straightforward implementation performs di + 1 loads and stores for every i ∈ [ [1, d]], specifically 1 load-store for a i and di for the a j 's. Since we have some registers left, we can actually pool the a j 's loads and stores for several a i 's. To do so, we load several shares a i , a i+1 , . . . , a i+k with the LDM instruction (which has a cost of k + 2 instead of 3k) and process the refreshing between them. Then, for every

j ∈ [[i + k + 1, d]],
we load a j , perform the refreshing between a j and each of the a i , a i+1 , . . . , a i+k , and store a j back. Afterwards, the shares a i , a i+1 , . . . , a i+k are stored back with the STM instruction (which has a cost of k + 2 instead of 3k). This allows us to load (and store) the a j only once for the k shares instead of k times, and to take advantage of the LDM and STM instructions. In practice, we could deal with up to k = 8 shares at the same time, meaning that for d ≤ 8 all the shares could be loaded and stored an single time using LDM and STM instructions. The performance of our implementations of the ISW-based mask refreshing is given in Table 5.8 and plotted in Figure 5.2 for illustration. 4 The performances of our implementations of the ISW-based mask refreshing are plotted in Figure 5.2. Our optimized refreshing is up to 3 times faster than the straightforward implementation and roughly 10 times faster that the full-table-based ISW multiplication.

BDF + Refresh

Barthe et al. in [START_REF] Barthe | Parallel Implementations of Masking Schemes and the Bounded Moment Leakage Model[END_REF], along with their multiplication gadget, also provide a refreshing gadget described in Algorithm 12. It simply consists in XORing the share to refresh by a random value and a rotation of it. The iteration of the BDF + refresh (d -1)/3 times makes it SNI secure. The overall BDF + refresh needs d (d -1)/3 random bits and performs 2 (d -1)/3 additions and (d -1)/3 ROT. There are no particular implementations tricks except that we use the same ROT algorithm introduced in Section 5.3.2.2 in order to keep the correctness with the specific encoding. Implementation results can be found in Table 5 We differentiate two cases for the BDF + multiplication. A first case where we consider the multiplication alone, which is SNI until d = 3 and only NI secure afterwards. A second case where we consider the composition of the multiplication with one iteration of the BDF + refresh (described in Section 5.3.3), which is SNI secure up to d = 8 and only NI secure afterwards (see [START_REF] Barthe | Parallel Implementations of Masking Schemes and the Bounded Moment Leakage Model[END_REF]). The cost difference between these two versions is simply the cost of an elementary refresh (i.e., the addition of a share of zero). Finding the number of such refreshes that are required to be SNI at any order is an open problem. Note that for BDF + , the results are given for d calls to the multiplication (since each call allows to compute 32/d elements).

We note that we did not perform the same addition for the BBP + multiplication since it would imply the need of a more expensive SNI refresh on the output, which would contradict the goal of [START_REF] Belaïd | Randomness Complexity of Private Circuits for Multiplication[END_REF] to minimize randomness by mixing NI and SNI multiplications instead of solely SNI multiplications (and in particular, if an SNI multiplication is required, one could use the ISW one, or the BDF + up to order 8).

We also recall that this table does not mention the different risks of an unsatisfied (independence) assumption. Namely the fact that the BDF + multiplication can suffer from a reduced security order due to couplings while for the other algorithms, the main risk of security order reduction comes from transition-based leakages.

Based on the results in the previous sections, we can compare the performance of our implementations of the multiplications for bitsliced inputs with higher-order masking in ARM v7. We make the comparison for five masking orders, namely we also give the performance results for two sets of TRNG. For the first one (called the TRNG-1 settings in the following), we make the same assumption as in [GR17] that we need to wait 10 clock cycles to get a fresh 32-bit random word. For the second one (called the TRNG-2 settings in the following), we make the same assumption as in [START_REF] Journault | Very High Order Masking: Efficient Implementation and Security Evaluation[END_REF] that we need to wait 80 clock cycles to get a fresh 32-bit random word. Finally, in order to have a fair comparison between the four algorithms the implementation results are given for the computation of a multiplication between two shared 32-bit operands. This means that for the 3 ISW-based multiplication (ISW, BCPZ, BBP + ) the results are given for a single call to their respective functions, whereas for the BDF + multiplication the results are given for d calls to the function (since each calls allows to compute 32/d elements). The overall results are given in Tables 5.11 and 5.12 for respectively the TRNG-1 and the TRNG-2 settings. As illustration, we also plot the performances in clock cycles (log scale) for both TRNG-1 and TRNG-2 settings in Figure 5. As expected the BCPZ offers the worst performances because of the many refreshings which intend to provide resistance to horizontal side-channel attacks, for both of the TRNG settings.

The BBP + multiplication outperforms the ISW multiplication (up to 25% faster) even in the case where the randomness is cheap. The difference becomes more significant in the TRNG-2 context (up to 40% faster), since BBP + have reduced randomness requirements.

For the TRNG-2 settings, we can also observe that unrolling the loops does not offer an interesting tradeoff as the gain in timing is not very significant compared to the code size overhead.

As shown in Table 2 of [START_REF] Barthe | Parallel Implementations of Masking Schemes and the Bounded Moment Leakage Model[END_REF], the iteration of the BDF + refresh requires a bit less randomness than ISW one but is more computationally involved. This is well reflected in Tables 5.11 and 5.12: the ISW refresh has better performance than the BDF + refresh for the TRNG-1 setting while it is the opposite for the TRNG-2 setting. Overall, BDF + and BBP + multiplications provide the best performance in both TRNG settings thanks to their lower randomness requirements (compared to the classical ISW). Of course these two multiplications also have weaker security guaranties (in terms of composability and resistance against horizontal attacks). On the other hand, ISW and BCPZ offer better security guaranties and hence are more involved in terms of randomness requirements, making these differences more visible in the TRNG-2 setting.

ISW vs CPRR

As argued in Section 5.3.1.5, we consider three variants for the base field multiplication in the ISW scheme, namely the full-table method, the half-table method and the exp-log method (with doubled exp table). The obtained ISW variants are labeled ISW-FT, ISW-HT and ISW-EL in the following. The obtained performance are summarized in Table 5.13 where the clock cycles with respect to d have been obtained by interpolation. Note that we did not consider ISW-FT for n > 8 since the precomputed tables are too huge. The timings (for n ≤ 8) are further illustrated in Figure 5.5 with respect to d. The obtained performance are illustrated in Figure 5.5 with respect to d. Note that we did not consider ISW-FT for n > 8 since the precomputed tables are too huge.

d(d-1) 2 d(d-1) 2 d(d-1) 2 d(d -1)
These results show that CPRR indeed outperforms ISW whenever the field multiplication cannot be fully tabulated. Even the half-table method (which is more consuming in code-size) is slower than CPRR. For n ≤ 8, a CPRR evaluation asymptotically costs 1.16 ISW-FT, 0.88 ISW-HT, and 0.75 ISW-EL.

We implemented parallel versions of ISW and CPRR for n = 4 and n = 8. For the former case, we can perform m = 8 evaluations in parallel, whereas for the later case we can perform m = 4 evaluations in parallel. For n = 4, we only implemented the full-table multiplication

d(d-1) 2 4d(d -1) d(d -1) 8(d -1)
These results show the important gain obtained by using parallelism. For ISW, we get an asymptotic gain around 30% for 4 parallel evaluations (n = 8) compared to 4 serial evaluations, and we get a 58% asymptotic gain for 8 parallel evaluations (n = 4) compared to 8 serial evaluations. For CPRR, the gain is around 50% (timings are divided by 2) in both cases (n = 8 and n = 4). We also observe that the efficiency order keeps unchanged with parallelism, that is: ISW-FT > CPRR > ISW-HT > ISW-EL.

Register Usage for ISW and CPRR Implementations

The register usage of our implementations of ISW and CPRR is given in Table 5.16. For ISW, the bottleneck for "temporary variables" is the register usage of the multiplication. From the ISW loop, one can check that we do not need the multiplication operands once they have been multiplied. This allowed us to save 2 registers in the full-table and exp-log multiplications, and 1 register in the half-table multiplication. These savings are indicated under brackets in Table 5.16 (and they are taken into account in the total). Regarding parallel versions, ISW implementations need two more registers compared to standard implementations in order to store the extracted n-bit chunks from packed 32-bit values for a i and b j . In the case of CPRR, a single additional register is sufficient for manipulating the shares of x with respect to the two loop counters i and j. As it can be deduced from Table 5.16, our parallel implementations of ISW and CPRR hence uses 13 registers, except for ISW-HT that needs 14 registers (i.e. it uses the link register), which is pretty tight.

Generic Implementations

Boolean decomposition

We now describe our implementations of a bitsliced s-box layer protected with higher-order masking based on our decomposition method over F 2 . Our implementations evaluate 16 n × n s-boxes in parallel where n ∈ {4, 8}, and they are developed in generic 32-bit ARM assembly. They take n input sharings

[ #" x 1 ], [ #" x 2 ], . . . , [ #" x n ] defined as [ #" x i ] = ( #" x i,1 , #" x i,2 , . . . , #" x i,d ) such that d j=1 #" x i,j = #" x i (5.9)
where #" x i is a 16-bit register containing the i-th bit of the 16 s-box inputs. Our implementations then output n sharings [ #" y 0 ], [ #" y 1 ], . . . , [ #" y n ] corresponding to the bitsliced output bits of the s-box. Since we are on a 32-bit architecture with 16-bit bitsliced registers, we use a degree-2 parallelization for the multiplications. Namely, the 16-bit ANDs are packed by pairs and replaced by 32-bit ANDs which are applied on shares using the ISW scheme.

The computation is then done in three stages. First, we need to construct the shares of the elements of the minimal basis B 0 . Once the first stage is completed, all the remaining multiplications are done between linear combinations of the elements of the basis. Let us denote by [ #"

t i ] the sharings corresponding to the elements of the basis which are stored in memory. After the first stage we have {[ #"

t i ]} = {[ #" x u ] | u ∈ U}. Each new #" t i is defined as j<i a i,j #" t j i<j b i,j #" t j (5.10)
where denote the bitwise multiplication, and where {a i,j } j and {b i,j } j are the binary coefficients obtained from the s-box decomposition (namely the coefficients of the functions g i,j and h i,j in the span of the basis). The second stage hence consists in a loop on the remaining multiplications that 1. computes the linear-combination sharings [ #" r i ] = j<i a i,j [ #"

t j ] and [ #"

s i ] = j<i b i,j [ #" t j ] 2. refreshes the sharing [ #" r i ] 3. computes the sharing [ #" t i ] such that #" t i = #" r i #" s i
where the last step is performed for two successive values of i at the same time by a call to a 32-bit ISW-AND. The sums in Step 1 are performed on each share independently. The refreshing procedure is simply a ISW refresh as explained in Section 5.3.3. Once all the basis sharings [ #" t i ] have been computed, the third stage simply consists in deriving each output sharing [ #" y i ] as a linear combination of the [ #" t i ], which is refreshed before being returned.

Linear parts.

We now explain how to optimize the evaluation of the linear parts of the implementation. In fact during the evaluation of a decomposition, we need a large number of linear combinations of elements of the basis. This linear parts have significant impacts on the performances (see Table 5.18) for small masking order. Therefore, in our ARM implementation we try to propose optimization in order to reduce as much as possible this linear overheads. To do so, we use windowing technique to perform evaluations of elements in the basis. More precisely, the evaluation is computed with k = cardinality of the basis architecture size calls to a macro that performs v conditional XORS, where v is the architecture size. In our case, since the implementation is done on a 32-bit ARM architecture, v is equal to 32 and k is at most 4. Therefore, we test the size of the basis to perform the sound number of calls to the windowing macro. Moreover, we also define a macro just for the computation of the first coordinate function, which is composed of 31 conditional xors (since the first coordinate function is only composed of elements of B 0 ).

Median case decomposition

Based on our generic decomposition method, we now describe our implementation of an s-box layer protected with higher-order masking in ARM v7. We focused our study on the common scenario of a layer applying 16 8-bit s-boxes to a 128-bit state. We apply our generalized decomposition with parameters n = m = 2 and λ = 4 (medium case) to compare the obtained implementation to the ones for the two extreme cases.

Our implementation is based on the decomposition obtained for the CLEFIA S0 s-box with parameters (r, t 1 , t 2 ) = (7, 7, 4). Note that it would have the same performances with any other 8-bit s-box with the same decomposition parameters (which we validate on all our tested random 8-bit s-boxes). The input (x 1 , x 2 ) of each s-box is shared as ([x 1 ], [x 2 ]) where

[x i ] = (x i,1 , x i,2 , . . . , x i,d ) such that d j=1 x i,j = x i .
(5.11)

Note that for those chosen parameters (n, m, λ), the input x 1 and x 2 are 4-bit elements, i.e. the inputs of the 8-bit s-boxes are split into 2. The output of the computation is a pair ([y 1 ], [y 2 ]) where y 1 and y 2 are the two 4-bit coordinates of the s-box output.

The computation is then pretty regular. It can be summarize with the following pseudo-code:

Algorithm 13 S-box evaluation pseudo-code Input:

([x 1 ], [x 2 ]) Output: ([y 1 ], [y 2 ]) = S([x 1 ], [x 2 ]) 1: B = ([x 1 ], [x 2 ]) 2: for i = 3 to 21 do 3: B = compute_pairwise_products([u i ], [v i ]) ∪ B 4: ([y 1 ], [y 2 ]) = evaluate_sbox(B) 5: return ([y 1 ], [y 2 ])
We start from a basis that contains the input sharings

{[z 1 ], [z 2 ]} = {[x 1 ], [x 2 ]}.
Then for i = 3 to 21 each of the 18 multiplications is performed between two linear combinations of the elements of the basis, that is

[z i ] = [u i ] [v i ] ,
(5.12)

where denotes the ISW multiplication with refreshing of one of the operand and where

u i,j = k<i i,k (z k,j ) and v i,j = k<i i,k (z k,j ) for every j ∈ [1, d],
(5.13) for some linearized polynomials i,k and i,k obtained from the s-box decomposition. Once all the products have been computed, the output sharings [y 1 ] and [y 2 ] are simple linear combinations of the computed [z i ].

To make the most of the 32-bit architecture, the s-box evaluations are done eight-by-eight since we can fill a register with eight 4-bit elements. The ISW-based multiplications can then be parallelized as suggested in Section 5.3.2.6 except for the field multiplications between two shares. To perform those multiplications, we simply need to unpack the eight 4-bit elements in each 32-bit operand, and then to sequentially perform the 8 field multiplications. These field multiplications are fully tabulated which only takes 0.25KB of ROM on F 16 (following the results of Section 5.3.1).

Algebraic Decomposition

We implemented the search of sound algebraic decompositions for λ ∈ [ [4,10]]. Here again, we looked for full rank systems i.e. systems that would work with any target s-box. For each value of λ, we set r to the smallest integer satisfying condition (2) i.e. r ≥ log 2 (λ) -1, and then we looked for a t starting from the lower bound t ≥ 2(2 λ -λ(r+1)) λ(λ-1) (obtained from condition (1)) and incrementing until a solvable system can be found. We then increment r and reiterate the process with t starting from the lower bound, and so on. For λ ≤ 8, we found the same parameters as those reported in [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF]. For λ = 9 and λ = 10 (these cases were not considered in [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF]), the best parameters we obtained were (r, t) = (3, 14) and (r, t) = (4, 22) respectively. All these parameters are recalled in Table 5.17. Table 5.17: Obtained parameters for the algebraic decomposition method. To avoid redundancy with the linear combinations of the g i 's, the authors of [START_REF] Carlet | Algebraic Decomposition for Probing Security[END_REF] suggest to derive p i 's that have null linear parts. In order to save some memory spaces, we make the choice of searching for p i 's with linear parts and remove the linear terms i g i (x) in Equation (2.8). Hence, the goal is now to look for a decomposition S(x) = t i=1 p i q i (x) , where the p i 's contain linear terms.

Performance Comparisons

We now compare the performance results of the implementations of the four following decomposition methods (3 instantiations of our generic decomposition method and the algebraic decomposition ):

• Boolean case (λ = 1, n = 8) • Median case (λ = 4, n = m = 2)
• Plain field case (λ = 8, n = 1)

• Algebraic decomposition

For each implementation, the performances are compared for the computation of 16 s-boxes on a 32-bit ARM architecture. Table 5.18 summarizes the obtained performances in clock cycles with respect to the masking order d. 2,20]], this overhead is between 4% and 6% of the overall s-box computations for n = 8, and between 7% and 11% for n = 4 (and this ratio is asymptotically negligible). For d = 2, the overhead slightly exceeds the gain, but for every d ≥ 3, parallelizing the ISW-ANDs always results in an overall gain of performances. We observe that the Boolean case is asymptotically faster than the optimized implementations of CRV and AD methods (3.6 times faster for n = 8 and 5.7 times faster for n = 4). However, we also see that the linear coefficient is significantly greater for the Boolean case, which comes from the computation of the linear combinations in input of the ISW-ANDs (i.e. the sharings [ #" r i ] and [ #" s i ]). As an illustration, Figures 5.8 and 5.9 plots the obtained timings with respect to d. We see that for n = 4, our implementation is always faster than the optimized AD and CRV. On the other hand, for n = 8, our implementation is slightly slower for d ≤ 8. We stress that our implementations could probably be improved by optimizing the computation of the linear combinations. The RAM consumption and code size of our implementations are given in Table 5.19. We believe these memory requirements to be affordable for not-too-constrained embedded devices. This is especially significant for n = 8 where CRV and AD needs a high amount of storage for the lookup tables of the linearized polynomials. On the other hand, we observe a big gap regarding the RAM consumption. The Boolean method is indeed more consuming in RAM because of all the [ #"

t i ] sharings that must be stored while such a large basis is not required for the CRV and AD methods, and because of some optimizations in the computation of the linear combinations. Additionally, implementations based on our medium case decomposition might provide further interesting tradeoffs on smaller (8-bit or 16-bit) architectures where bitslice would be slowed down and where the optimized CRV-based implementation might be too consuming in terms of code size.

Structured S-boxes

Polynomial representation

As detailed in Chapter 2, there is exist two main approach to decompose the AES s-box, namely the Rivain-Prouff method and the Kim-Hong-Lim method. For PRESENT, the usual solution is to evaluate the F • G representation.

Bitslice representation

Secure Bitsliced AES S-box

For the AES s-box, we based our work on the compact representation proposed by Boyar et al. in [START_REF] Boyar | Logic Minimization Techniques with Applications to Cryptology[END_REF]. Their circuit is obtained by applying logic minimization techniques to the tower-field representation of Canright [START_REF] Canright | A Very Compact S-Box for AES[END_REF]. It involves 115 logic gates including 32 logical AND. The circuit is composed of three parts: the top linear transformation involving 23 XOR gates and mapping the 8 s-box input bits x 0 , x 1 , . . . , x 7 to 23 new bits x 7 , y 1 , y 2 , . . . , y 21 ; the middle non-linear transformation involving 30 XOR gates and 32 AND gates and mapping the previous 23 bits to 18 new bits z 0 , z 1 , . . . , z 17 ; and the bottom linear transformation involving 26 XOR gates and 4 XNOR gates and mapping the 18 previous bits to the 8 s-box output bits s 0 , s 1 , . . . , s 7 . In particular, this circuit improves the usual count of 34 AND gates involved in previous tower-field representations of the AES s-box.

Using this circuit, we can perform the 16 s-box computations of an AES round in parallel. That is, instead of having 8 input bits mapped to 8 output bits, we have 8 (shared) input 16-bit words X 0 , X 1 , . . . , X 7 mapped to 8 (shared) output 16-bit words S 1 , S 2 , . . . , S 8 . Each word X i (resp. S i ) contains the ith bits input bit (resp. output bit) of the 16 s-boxes. Each XOR gate and AND gate of the original circuit is then replaced by the corresponding (shared) bitwise instruction between two 16-bit words.

Parallelizing AND gates. For our masked bitslice implementation, a sound complexity unit is one call to the ISW-AND since this is the only nonlinear operation, i.e. the only operation with quadratic complexity in d (compared to other operations that are linear in d).

In a straightforward bitslice implementation of the considered circuit, we would then have a complexity of 32 ISW-AND. This is suboptimal since each of these ISW-AND is applied to 16-bit words whereas it can operates on 32-bit words. Our main optimization is hence to group together pairs of ISW-AND in order to replace them by a single ISW-AND with fully filled input registers. This optimization hence requires to be able to group AND gates by pair that can be computed in parallel. To do so, we reordered the gates in the middle non-linear transformation of the Boyar et al. circuit, while keeping the computation consistent. We were able to fully parallelize the AND gates, hence dropping our bitslice complexity from 32 down to 16 ISW-AND. We thus get a parallel computation of the 16 AES s-boxes of one round with a complexity of 16 ISW-AND, that is one single ISW-AND per s-box. Since an ISW-AND is (significantly) faster than any ISW multiplication, our masked bitslice implementation breaks through the barrier of one ISW field multiplication per s-box. Our reordered version of the Boyar et al. circuit is described in Figure 5.10. It can be checked that every two consecutive AND gates can be performed in parallel.

Remark 5.5.1. The Boyar et al. circuit involves many intermediate variables (denoted by t i )

that are sometimes needed multiple times. This strongly impact the performances in practice by requiring several loads and stores, which -as mentioned earlier-are the most expensive ARM instructions, and further implies a memory overhead. In order to minimize this impact, we also reordered the gates in the linear transformations so that all the intermediate variables can be kept in registers. This is only possible for linear transformations since they are applied on each share independently. On the other hand, the shares of the intermediate variables in input of an ISW-AND must be stored in memory as they would not fit altogether in the registers.

Secure Bitsliced PRESENT S-box

For our masked bitsliced implementation of the PRESENT s-box, we used the compact representation given by Courtois et al. in [START_REF] Courtois | Solving Circuit Optimisation Problems in Cryptography and Cryptanalysis[END_REF], which was obtained from Boyar et al. 's logic minimization techniques improved by involving OR gates. This circuit is composed of 4 nonlinear gates (2 AND and 2 OR) and 9 linear gates (8 XOR and 1 XNOR). Remark 5.5.2. An ISW-OR can be computed from an ISW-AND by using De Morgan's law, that is a ∨ b = ā • b, and since the negation in the masking world simply consists in complementing a single of the d shares (which can be efficiently done with a single instruction). One can also easily get an ISW-NAND and an ISW-NOR.

-top linear transformationy 14 = x 3 ⊕ x 5 y 1 = t 0 ⊕ x 7 y 15 = t 1 ⊕ x 5 y 17 = y 10 ⊕ y 11 y 13 = x 0 ⊕ x 6 y 4 = y 1 ⊕ x 3 y 20 = t 1 ⊕ x 1 y 19 = y 10 ⊕ y 8 y 12 = y 13 ⊕ y 14 y 2 = y 1 ⊕ x 0 y 6 = y 15 ⊕ x 7 y 16 = t 0 ⊕ y 11 y 9 = x 0 ⊕ x 3 y 5 = y 1 ⊕ x 6 y 10 = y 15 ⊕ t 0 y 21 = y 13 ⊕ y 16 y 8 = x 0 ⊕ x 5 t 1 = x 4 ⊕ y 12 y 11 = y 20 ⊕ y 9 y 18 = x 0 ⊕ y 16 t 0 = x 1 ⊕ x 2 y 3 = y 5 ⊕ y 8 y 7 = x 7 ⊕ y 11 -middle non-linear transformation - PRESENT has 16 parallel s-box computations per round, as AES. We hence get a bitsliced implementation with 16-bit words that we want to group for the calls to ISW-AND. However for the chosen circuit, we could not fully parallelize the nonlinear gates because of the dependency between three of them. We could however group the two OR gates after a slight reordering of the operations. We hence obtain a masked bitsliced implementation computing the 16 PRESENT s-boxes in parallel with 3 calls to ISW-AND. Our reordered version of the circuit is depicted in Figure 5.11. We clearly see that the two successive OR gates can be computed in parallel. For the sake of security, we also refresh one of the two input sharings in the 3 calls to ISW-AND. As for the bitslice AES s-box, the implied overhead is manageable.

t
t 1 = x 2 ⊕

Implementation and Performance

Table 5.20 gives the performance obtained for our masked bitslice implementations of the AES and PRESENT s-boxes. For comparison, we also recall the performances of the fastest polynomial methods for AES and PRESENT (i.e. parallel versions of KHL and F • G) as well as the fastest generic methods for n = 8 and n = 4 (i.e. parallel versions of the algebraic decomposition method for n = 8 and CRV for n = 4). The timings are further plotted in Figures 5.12 and 5.13 for the sake of illustration. These results clearly demonstrate the superiority of the bitslicing approach. Our masked bitsliced implementations of the AES and PRESENT s-boxes are significantly faster than state-of-the art polynomial methods finely tuned at the assembly level.

Cipher Implementations

This section finally describes masked implementations of the full PRESENT and AES blockciphers. These blockciphers are so-called substitution-permutation networks, where each round is composed of a key addition layer, a nonlinear layer and a linear diffusion layer. For both blockciphers, the nonlinear layer consists in the parallel application of 16 s-boxes.

The AES works on a 128-bit state (which divides into sixteen 8-bit s-box inputs) whereas PRESENT works on a 64-bit state (which divides into sixteen 4-bit s-box inputs). For detailed specifications of these blockciphers, the reader is referred to [FIP01] and [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF].

For both blockciphers, we follow two implementation strategies: the standard one (with parallel polynomial methods for s-boxes) and the bitsliced one (with bitsliced s-box masking).

For the sake of efficiency, we assume that the key is already expanded, and for the sake of security we assume that each round key is stored in (non-volatile) memory under a shared form. In other words, we do not perform a masked key schedule. Our implementations start by masking the input plaintext with d -1 random m-bit strings (where m is the block cipher bit-size) and store the d resulting shares in memory. These d shares then compose the sharing of the block cipher state that is updated by the masked computation of each round. When all the rounds have been processed, the output ciphertext is recovered by adding all the output shares of the state. For the bitsliced implementations, the translation from standard to bitsliced representation is performed before the initial masking so that it is done only once. Similarly, the translation back from the bitsliced to the standard representation is performed a single time after unmasking.

The secure s-box implementations are done as described in previous sections. It hence remains to deal with the key addition and the linear layers. These steps are applied to each share of the state independently. The key-addition step simply consists in adding each share of the round key to one share of the state. The linear layer implementations are described hereafter.

Standard AES linear layer.

We based our implementation on a classical optimized version of the unmasked block cipher. We use a transposed representation of the state matrix in order to store each row in a 32-bit register. The MixColumns can then be processed for each column simultaneously by working with row registers, and the ShiftRows simply consists of three rotate instructions.

Bitsliced AES linear layer.

The MixColumns step can be efficiently computed in bitslice representation by transforming the state matrix (b i,j ) i,j into a new state matrix: ). This gives The above equation can be efficiently evaluated in ARM assembly, taking advantage of the barrel shifter. The only subtlety is that the above rotate operations are on 16 bits whereas the ARM rotation works on 32 bits. But this can be simply circumvented by using left shift instead of left rotate with a final reduction of the exceeding bits. The obtained implementation takes 43 one-cycle instructions for the overall bitslice MixColumns.

Z k = X k ⊕ (W k ≪ 4) ⊕ (W k ≪ 8) ⊕ (W k ≪ 12) , (5.17
The ShiftRows is the most expensive step of the AES linear layer in bitslice representation. It must be applied on the bits of each vector W k (since each nibble of W k correspond to a different row of the state). Each row can be treated using 6 ARM instructions (6 clock cycles) as shown in the following code: This must be done for 3 rows, which makes 18 clock cycles per word W k , that is a total of 8 × 18 = 144 clock cycles.

PRESENT linear layer.

The linear layer of PRESENT, called the pLayer, consists in a permutation of the 64 bits of the state. In both representations, our implementation of this step use the straightforward approach where each bit is taken at a given position i in a source register and put at given position j in a destination register. Such a basic operation can be done in two ARM instructions (2 clock cycles), with a register $one previously set to 1, as follows:

AND $tmp , $src , $one , LSR # i EOR $dst , $tmp , LSL # j

In both representations, our pLayer implementation is hence composed of 64×2 instructions as above, plus the initialization of destination registers, for a total of 130 instructions for the standard representation and 132 for the bitslice representation.5

Translation to and from bitslice format.

For both blockciphers the bitslice translations (forward and backward) can be seen as bit permutations. They are hence implemented using a similar approach as for the pLayer of PRESENT. This requires around 2 × 64 = 128 cycles for PRESENT and 2 × 128 = 256 clock cycles for AES. Further note that in the case of PRESENT, the forward bitslice translation is exactly the pLayer transformation, which allows some code saving.

Performance

In our standard implementation of AES, we used the parallel versions of KHL and RP (with ISW-EL) for the s-box. For the standard implementation of PRESENT, we used the parallel versions of the F • G method and of the CRV method. The obtained performance are summarized in Table 5.21. The timings are further plotted in Figures 5.14 and 5.15 for illustration.

These results clearly confirm the superiority of the bitslice implementations in our context. The bitslice AES implementation asymptotically takes 38% of the timings of the standard AES implementation using the best parallel polynomial method for the s-box (namely KHL). This ratio reaches 18% for PRESENT (compared to the F • G method). It is also interesting to observe that PRESENT is slower than AES for standard masked implementations whereas it is faster for masked bitslice implementations. In the latter case, a PRESENT computation asymptotically amounts to 0.58 AES computation. This ratio directly results from the number of calls to ISW-AND which is 10 × 16 = 160 for AES (16 per round) and 31 × 3 = 93 for PRESENT (3 per round).

In order to illustrate the obtained performance in practice, Table 5.22 gives the corresponding timings in milliseconds for a clock frequency of 60 MHz. For a masking order of 10, our bitsliced implementations only take a few milliseconds.

Conclusion

In this thesis, we have studied efficient schemes to protect block ciphers against physical attacks. As the evaluation of the s-boxes is the main bottleneck, the first challenge was to find sound representation of the s-boxes. For this purpose, we studied the s-box as a polynomial over a finite field and proposed a generalization of an existing method to decompose any polynomial over any finite field. As opposed to solutions using SAT solvers, our decomposition technique can work for any s-box size. The main advantage of this generalized method is its efficiency in terms of multiplicative complexity and its flexibility with respect to its instantiations. Indeed, our implementation results showed interesting trade-offs between timing and memory costs. In fact, for small masking orders working on a full field allows to obtain fast implementation results but with some costs on code size, whereas median field allows to obtain slower implementation but with a tight memory usage. However, as the masking order grows, the Boolean field quickly becomes the best solution thanks to the bitslicing strategy.

Then, we analyzed the security of masking schemes in a theoretical framework and more specifically the composable security of secure implementations using ISW multiplication gadgets. By a security reduction with the use of game based techniques, we were able to reformulate the probing security of those particular circuits into a problem of linear algebra. From the linear algebra, we identified a criterion to determine whether or not a tight shared circuit is probing secure for any adversary. From this criterion, we have developed a formal verification tool that can determine, given the description of a secure circuit, if a probing attack is possible. For the AES s-box Boolean circuit, our verification tool determined that no refresh gadgets are required, as opposed to other verification tools that insert refresh gadgets after each multiplication. This led to a reduction of the randomness consumption by a factor of two in the implementation of the AES s-box with a bitslicing strategy.

Finally, we have implemented in ARM assembly most of the state-of-the-art masking schemes and different instantiations of our decomposition framework. We followed a bottomup approach that allowed us to obtain optimized implementations for the building blocks of the construction of protected block ciphers. We studied different techniques to perform secure multiplications with various trade-offs between efficiency, randomness consumption and practical security. Finally, we have studied the use of the bitslice strategy at the s-box level which allowed us to outperform all known polynomial-based solutions. Moreover, for the AES s-box the bitsliced implementation requires little randomness thanks to our verification tool. The numerous implementations developed during this thesis have been made available online for public use [CRX].

-113 -

Open Questions

Here, we give a few open problems and directions that might be interesting for future work. Question 6.1. How could homomorphic encryption benefit from our generic decomposition tool?

In homomorphic encryption, the problem of evaluating efficiently the s-box is similar to the one in masking schemes. In fact, to lower the impact of the growth of the noise in homomorphic encryption, one needs to find encryption schemes that have a minimal multiplicative depth. Therefore, one may want to adapt our generic decomposition method to target not only the multiplicative complexity but also the multiplicative depth and hence get efficient implementation of homomorphic encryption. Specifically, since the notion of parallel multiplicative complexity introduced in Chapter 3 is equivalent to the notion of multiplicative depth, as soon as the architecture size is big enough (see Chapter 3), our generic framework could be adapted to find representations that lower the multiplicative depth.

Question 6.2. Could we optimize SAT solver techniques to work on bigger s-boxes?

One major drawback of our generic decomposition framework is that it is a heuristic method. To get the tightest decomposition of a function with respect to the number of multiplications, the ideal solution is to use SAT solvers to find the exact representation of the s-box with the optimal multiplicative complexity. However, as the size of the s-box grows, the complexity of SAT solvers explodes. Hence, one interesting line of work would be to see if it is possible to reduce the number of equations that the SAT solvers try to solve to find representations in a reasonable amount of time. Question 6.3. Is our verification tool extendable to more generic problems?

Currently our verification tool introduced in Chapter 4 only works on Boolean circuit composed of ISW multiplications. It would be of interest to extend the results to more general circuits (e.g. arithmetic circuits), but also to more generic secure multiplication (namely multiplications that do not necessarily manipulate all the cross products). Moreover, we only applied our tool to the example given in Chapter 3. Applying the tool to other existing solutions such as generic decomposition techniques to reduce the randomness can hence be a interesting line of work.

Figures

Résumé

Depuis leur introduction à la fin des années 1990, les attaques par canaux auxiliaires sont considérées comme une menace majeure contre les implémentations cryptographiques. Parmi les stratégies de protection existantes, une des plus utilisées est le masquage d'ordre supérieur. Elle consiste à séparer chaque variable interne du calcul cryptographique en plusieurs variables aléatoires. Néanmoins, l'utilisation de cette protection entraîne des pertes d'efficacité considérables, la rendant souvent impraticable pour des produits industriels. Cette thèse a pour objectif de réduire l'écart entre les solutions théoriques, prouvées sûres, et les implémentations efficaces déployables sur des systèmes embarqués. Plus particulièrement, nous nous intéressons à la protection de chiffrement par bloc tel que l'AES, dont l'enjeu principal revient à protéger les boîtes-s avec un surcoût minimal. Nous essayons d'abord de trouver des représentations mathématiques optimales pour l'évaluation des boîtess en minimisant le nombre de multiplications (un paramètre déterminant pour l'efficacité du masquage, mais aussi pour le chiffrement homomorphe). Pour cela, nous définissons une méthode générique pour décomposer n'importe quelle fonction sur un corps fini avec une complexité multiplicative faible. Ces représentations peuvent alors être évaluées efficacement avec du masquage d'ordre supérieur. La flexibilité de la méthode de décomposition permet également de l'ajuster facilement selon les nécessités du développeur. Nous proposons ensuite une méthode formelle pour déterminer la sécurité d'un circuit évaluant des schémas de masquages. Cette technique permet notamment de déterminer de manière exacte si une attaque est possible sur un circuit protégé ou non. Par rapport aux autres outils existants, son temps de réponse n'explose pas en la taille du circuit, ce qui permet d'obtenir une preuve de sécurité quelque soit l'ordre de masquage employé. De plus, elle permet de diminuer de manière stricte l'emploi d'outils coûteux en aléas, requis pour renforcer la sécurité des opérations de masquages. Enfin, nous présentons des résultats d'implémentation en proposant des optimisations tant sur le plan algorithmique que sur celui de la programmation. Nous utilisons notamment une stratégie d'implémentation bitslice pour évaluer les boîtes-s en parallèle. Cette stratégie nous permet d'atteindre des records de rapidité pour des implémentations d'ordres élevés. Les différents codes sont développés et optimisés en assembleur ARM, un des langages les plus répandus dans les systèmes embarqués tels que les cartes à puces et les téléphones mobiles. Ces implémentations sont, en outre, disponibles en ligne pour une utilisation publique.

Mots Clés

cryptographie, attaques par canaux auxiliaires, implémentation efficace, contremesures, sécurité prouvée, assembleur.

Abstract

Since their introduction at the end of the 1990s, sidechannel attacks are considered to be a major threat against cryptographic implementations. Higher-order masking is considered to be one the most popular existing protection strategies. It consists in separating each internal variable in the cryptographic computation into several random variables. However, the use of this type of protection entails a considerable efficiency loss, making it unusable for industrial solutions. The goal of this thesis is to reduce the gap between theoretical solutions, proven secure, and efficient implementations that can be deployed on embedded systems. More precisely, I am analysing the protection of block ciphers such as the AES encryption scheme, where the main issue is to protect the s-boxes with minimal overhead in costs. I have tried, first, to find optimal mathematical representations in order to evaluate the s-boxes while minimizing the number of multiplications (a decisive parameter for masking schemes, but also for homomorphic encryption). For this purpose, I have defined a generic method to decompose any function on any finite field with a low multiplicative complexity. These representations can, then, be efficiently evaluated with higher-order masking. The flexibility of the decomposition technique allows also easy adjusting to the developer's needs. Secondly, I have proposed a formal method for measuring the security of circuits evaluating masking schemes. This technique allows to define with exact precision whether an attack on a protected circuit is feasible or not. Unlike other tools, its response time is not exponential in the circuit size, making it possible to obtain a security proof regardless of the masking order used. Furthermore, this method can strictly reduce the use of costly tools in randomness required for reinforcing the security of masking operations. Finally, we present the implementation results with optimizations both on algorithmic and programming fronts. We particularly employ a bitslice implementation strategy for evaluating the s-boxes in parallel. This strategy leads to speed record for implementations protected at high order. The different codes are developed and optimized under ARM assembly, one of the most popular programming language in embedded systems such as smart cards and mobile phones. These implementations are also available online for public use.

Definition 2 . 3 . 1 .

 231 [Cyclotomic class] Let n be the number of input bits of the s-box and let α ∈ [0; 2 n -2]. The cyclotomic class of α is the set C α defined by:

  From two d-sharings (a 1 , a 2 , . . . , a d ) and (b 1 , b 2 , . . . , b d ) of two m-bit strings a, b ∈ {0, 1} m , the ISW scheme computes an output d-sharing (c 1 , c 2 , . . . , c d ) of c = a ∧ b as follows:

Figure 3 . 1 :

 31 Figure 3.1: A circuit for AES with parallelizable AND gates.

Figure 3 . 2 :

 32 Figure 3.2: Number of Random S-boxes for each Multiplicative Complexity for n = 8

2 λ

 2 (r-1)•λ+1 as parameters for given bit-length n and cost ratio θ.

Figure 3 . 3 :

 33 Figure 3.3: Optimal r parameter w.r.t. the CPRR-ISW cost ratio θ for λ ∈ [[4, 8]].

Figure 3 . 4 :

 34 Figure 3.4: CRV d 2 const.(λ = 6).

Figure 3 . 5 :Figure 3

 353 Figure 3.5: CRV d 2 const.(λ = 8).

Figure 4 . 2 :

 42 Figure 4.2: Graph representation of Circuit 1 after maskComp.

Figure 4 . 3 :

 43 Figure 4.3: t-probing security game.

  Figure 4.3, i.e. the random experiments ExpReal(A, C) and ExpSim(A, S, C) output identical distributions.

Figure 4 . 4 ,

 44 i.e. the random experiments ExpReal(A, C) and ExpSim(A, S, C) output identical distributions.

Figure 4 . 4 :

 44 Figure 4.4: t-(S)NI security game.

Figure 4 . 4 .

 44 The only difference relies in the fact that the first-round simulator S 1 outputs n sets of indices I 1 , . . . ,I n ⊆ {1, . . . , d}, such that |I 1 | = • • • = |I n | = |P int | ≤t where P int ⊆ P refers to the probes on internal wires, i.e. the probes in P which do not point to outputs of C. Proposition 4.3.7. A shared circuit C is t-strong-non-interfering secure if and only if for every adversary A, there exists a simulator S that wins the t-SNI security game defined in Figure 4.4, i.e. the random experiments ExpReal(A, C) and ExpSim(A, S, C) output identical distributions.

Theorem 4 .

 4 3.8 ([BBD+16]). For any integers d and t such that t < d, the d-shared ISW-multiplication gadget [⊗] and the d-shared ISW-refresh gadget [R] are both t-SNI. The next lemma states a simple implication of the t-SNI notion: Lemma 4.3.9. Let C be a n-input (t + 1)-shared t-SNI circuit. Then for every (x 1 , . . . , x n ) ∈ F n 2 , an evaluation of C taking n uniform and independent (t+1)-Boolean sharings [x 1 ], . . . , [x n ] as input produces a sharing [y] (of some value y ∈ F 2 which is a function of x 1 , . . . , x n ) which is uniform and mutually independent of [x 1 ], . . . , [x n ].

Figure 4 . 5 :

 45 Figure 4.5: Overview of the sequence of games.

Figure 4

 4 Figure 4.6: Game 1.

Proposition 4 . 4 . 1 .

 441 A standard shared circuit C is t-probing secure if and only if for every adversary A, there exists a simulator S that wins Game 1 defined above, i.e. the random experiments ExpReal 1 (A, C) and ExpSim 1 (A, S, C) output identical distributions.

  of gadget g), outputs a set of probes P r (g) ⊆ I g (on the input sharesof gadget g) such that |P r (g) | = |P (g)r |, and given the input shares pointed by P r (g) , outputs a perfect simulation of the internal wires pointed by P (g) r ;

  SNI that given the set of probes P (g) m (on the internal wires of gadget g), outputs a set of pairs of probes P m (g) ⊆ I g × J g (on the input shares of each operand of gadget g) such that |P m (g) | = |P (g) m |, and given the input shares pointed by P m (g) , outputs a perfect simulation of the internal wires pointed by P (g) m ;

  SNI to get a perfect simulation of the internal wires pointed by P (g) r (resp. P (g) m ) from the input shares pointed by P r (g) (resp. P m (g) ) which are obtained from the evaluation C([x 1 ], . . . , [x n ]) P . This way S 0 obtains (and returns) a perfect simulation of C([x 1 ], . . . , [x n ]) P and the two experiments ExpReal(A 0 , C) and ExpSim(A 0 , S 0 , C) output identical distributions, which demonstrates the implication Equation (4.4).

Figure 4 . 7 :

 47 Figure 4.7: Illustration of the Flatten transformation.

Proposition 4 . 4 . 2 .

 442 A standard shared circuit C is t-probing secure if and only if for every adversary A, there exists a simulator S that wins Game 2 defined above, i.e. the random experiments ExpReal 2 (A, C) and ExpSim 2 (A, S, C) output identical distributions.

Proposition 4 . 4 . 5 .

 445 A standard shared circuit C is t-probing secure if and only if for every adversary A, there exists a simulator S that wins Game 3 defined above, i.e. the random experiments ExpReal 3 (A, C) and ExpSim 3 (A, S, C) output identical distributions. Proof. We first show: ∀A 2 , ∃S 2 wins Game 2 ⇒ ∀A 3 , ∃S 3 wins Game 3 (⇔ C t-probing secure) (4.14)

Figure 4 . 1 ,

 41 two variables are manipulated in multiplications in the circuit C: -

Figure 4 .

 4 Figure 4.10 provides a second Boolean circuit. It manipulates five variables -→ w i as operands of multiplication gadgets: -→ w 1 = -→ x 1 , -→ w 2 = -→ x 2 , -→ w 3 = -→ x 3 , -→ w 4 = -→ x 1 + -→ x 2 , and -→ w 5 = -→ x 2 + -→ x 3 . The set of multiplications G is of cardinal three with ( -→ w 1 , -→ w 2 ), ( -→ w 4 , -→ w 5 ), and ( -→ w 3 , -→ w 4 ). Following the number of variables, the method proceeds at most in five steps:

Figure 4 .

 4 Figure 4.10: Graph representation of a second Boolean circuit.

Proposition 4 . 5 . 1 .

 451 For every i ∈ N, if -→ w ∈ O i then there exists t ∈ N and P = {(g, j 1 , j 2 )}with |P| = t implying t j=0 Im(M T j ) = -→ w .Proof of Proposition 4.5.1. To prove this proposition, we demonstrate by induction the following invariant:

Figure 4 .

 4 Figure 4.11: Structure of an SPN-Based Block Cipher.

  ' Attack found : 2 in span[1 ,6 ,4] ')

Figure 4 .

 4 Figure 4.13: New method applied on example 2.

2 Figure 4 .

 24 Figure 4.15: Timings of a t-probing secure AES s-box implementation.

  EOR $tmp , $opB , $opA , LSL # n ;; tmp =[ a_h | a_l | b_h | b_l ] LDRB $res ,[ $tab1 , $tmp , LSR #( n /2) ;; res = T1 [ a_h | a_l | b_h ] EOR $tmp , $opA , $opB , LSL #(32 -n /2) ;; tmp =[ b_l |0..| a_h | a_l ] LDRB $tmp ,[ $tab2 , $tmp , ROR #(32 -n /2) ] ;; tmp = T2 [ a_h | a_l | b_l ]

  Wagner, Crypto'03): probing secure multiplication, BDF + (Barthe et al. , Eurocrypt'17): bounded-moment secure multiplication, BBP + (Belaïd et al. , Eurocrypt'16): ISW gadget with randomness saving, BCPZ (Battistello et al. , CHES'16): ISW gadget with additional refreshing, CPRR (Carlet et al. , CRYPTO'18): secure quadratic evaluation.

Algorithm 7

 7 BBP + (Belaïd et al. , Eurocrypt'16) w/o conditional branches Input: sharings (a 1 , . . . , a d ) ∈ {0, 1} 32×d and (b 1 , . . . , b d ) ∈ {0, 1} 32×d Output: sharing (c 1 , . .

  32

7:

  for i = 1 to d -1 by 2 do 8: r i,i+1 ← {0, 1} 32 9:

Algorithm 9 5 :

 95 BCPZ (Battistello et al. , CHES'16) Input: shares a i such that i a i = a, shares b i such that i b i = b Output: shares c i such that i c i = a • b 1: M i,j ← MatMult((x 1 , . . . , x d ), (y 1 , . . . , y d )) 2: for i = 1 to d do 3: c i ← M i,i4: for i = 1 to d do for j = i + 1 to d do 6: s ← F 7: s ← (s + M i,j ) + M j,i 8:

Figure 5 . 2 :

 52 Figure 5.2: Timings of mask refreshing.

  3 and Figure 5.4 respectively.

Figure 5 . 3 :

 53 Figure 5.3: Multiplication performances for TRNG-1 in clock cycles

Figure 5 . 4 :

 54 Figure 5.4: Multiplication performances for TRNG-2 in clock cycles

4 Figure 5 . 6 :

 456 Figure 5.6: Timings of (parallel) ISW and CPRR schemes for n = 8.

Figure 5 . 7 :

 57 Figure 5.7: Timings of (parallel) ISW and CPRR schemes for n = 4.

Figure 5 . 9 :

 59 Figure 5.8: Timings for n = 8.

Figure 5 .

 5 Figure 5.10: AES s-box circuit for efficient bitslice implementation.

Figure 5 .

 5 Figure 5.11: PRESENT s-box circuit for efficient bitslice implementation.

Figure 5 .

 5 Figure 5.12: Timings for 16 AES s-boxes.

Figure 5 .

 5 Figure 5.13: Timings for 16 PRESENT sboxes.

  c i,j = xtimes(b i,j ⊕ b i+1,j ) ⊕ b i+1,j ⊕ b i+2,j ⊕ b i+3,j ,(5.14)where xtimes denotes the multiplication by x over F 2 8 ≡ F 2 [x]/p(x) with p(x) = x 8 + x 4 +x 3 + x + 1.The xtimes has a simple Boolean expression, which is:(b 7 , b 6 , . . . , b 0 ) 2 xtimes -----→ (b 6 , b 5 , b 4 , b 3 ⊕ b 7 , b 2 ⊕ b 7 , b 1 , b 0 ⊕ b 7 , b 7 ) 2 (5.15)Let W k denotes the word corresponding to the kth bits of the state bytes b i,j , and letW (i,j) k denotes the (4 • i + j)th bit of W k (thatis the kth bit of the state byte b i,j ). The words Z k in output of the bitslice MixColumns satisfy Z kth bit of the output of xtimes(b i,j ⊕ b i+1,j

  )where ≪ denotes the rotate left operator on 16 bits. Following the Boolean expression of xtimes, the wordX k satisfies X k = Y k-1 if k ∈ {7, 6, 5, 2}, X k = Y k-1 ⊕ Y 7 if k ∈ {4, 3, 1}, and X 0 = Y 7 , with Y k = W k ⊕ (W k ≪ 4).

  = b1 ... b4b8b5b6b7 ... b16

Figure 5 .

 5 Figure 5.14: Timings of masked AES.

Figure 5 .

 5 Figure 5.15: Timings of masked PRESENT.

2 Secure Non-Linear Operations

  , I conclude in Chapter 6 with a brief summary of what I achieved and open questions that remain to be answered after this work. . . . . . . . . . . . . . . . . . . . . .

	Chapter 2

Preliminaries

Contents 2.1 Higher-Order Masking . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Masking Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Implementation Transformation . . . . . . . . . . . . . . . . . . . . 2.1.4 Probing security . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2.1 Ishai-Sahai-Wagner Multiplication . . . . . . . . . . . . . . . . . . . 2.2.2 Mask refreshing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Coron-Prouff-Rivain-Roche evaluation . . . . . . . . . . . . . . . . . 2.

3 Polynomial Methods for S-boxes

  . . . . . . . . . . . . . . . . . . . . 2.3.1 Coron-Roy-Vivek method . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Algebraic decomposition method . . . . . . . . . . . . . . . . . . . 2.3.3 Specific Methods for AES and PRESENT . . . . . . . . . . . . . . . 2.4 Bitslice Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 ISW Logical AND . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 ARM Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	-7 -

Table 2 .

 2 2: ARM instructions.

	Class Data instructions Memory instructions LDR, STR / LDM, STM Examples EOR, ADD, SUB, AND, MOV Branching instructions B, BX, BL	Clock cycles 1 3 or n + 2 3 or 4

Chapter 3 Decomposition Contents 3.1 Introduction

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Multiplicative Complexity of Generic S-boxes .

	. . . . . . . . . . . 3.3.1 Notations and notions . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Multiplicative Complexity Lower Bound for S-boxes . . . . . . . . . . 3.3.3 Some results for the Boolean case. . . . . . . . . . . . . . . . . . . . 3.3.4 Parallel Multiplicative Complexity . . . . . . . . . . . . . . . . . . . 3.4 Generic Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Decomposition of a Single Coordinate Function . . . . . . . . . . . . 3.4.2 S-box Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 Optimal parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 Basis Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Boolean case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.2 Median case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.3 Full-field case . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  1 , . . . , f m ) over F 2 λ , denoted M(f 1 , . . . , f m ) is the minimal multiplicative complexity over all polynomial chains for (f 1 , . . . , f m ). We consider a sequence of n-variate polynomials f 1 , . . . , f m in the algebra F 2 λ [x 1 , . . . , x n ]

	We will provide a heuristic method which given a sequence of n-variate polynomials over F 2 λ provides an evaluation scheme (or a circuit) with "small" multiplicative complexity. Following, Coron et al. [CRV14], Proposition 3.3.3 provides a Ω(2 nλ/2 m/λ) lower bound on this multiplicative complexity. As in [CRV14], the proof is a simple combinatorial argument inspired by [PS73].
	Proposition 3.3.3. Let λ ≥ 1, n ≥ 1, l ≥ 1 and m ≥ 1 be four integers. There ex-ists f 1 , . . . , f m ∈ F 2 λ [x 1 , . . . , x n ] a sequence of n-variate polynomials over F 2 λ such that M(f 1 , . . . , f m ) ≥ m2 nλ λ -(2n + m -1).
	Proof.

  r(λm + 2λnλ + 2) + λmn + m, and each parameter can take any value in F 2 λ . The number of sequence of n-variatepolynomials f 1 , . . . , f m ∈ F 2 λ [x 1 , . . . , x n ] with multiplicative complexity M(f 1 , . . . , f m ) = r is thus upper-bounded by 2 λ(r 2 λ+r(λm+2λn-λ+2)+λmn+m) .Since the total number of sequences of n-variate polynomials f 1

Table 3 .

 3

	1: Multiplicative complexities of various s-boxes.
	S-box S CTC2 PRESENT Piccolo RECTANGLE Lightweight block ciphers size n × m C(S) 3 × 3 3 4 × 4 4 4 × 4 4 4 × 4 4 CAESAR submissions LAC 4 × 4 4 Minalpher 4 × 4 5 Prøst 4 × 4 4 Ascon 5 × 5 5 ICEPOLE 5 × 5 6 PRIMATEs 5 × 5 {6, 7} AES and Keccak Keccak 5 × 5 5 AES 8 × 8 ≤ 32 Bitslice-oriented block ciphers NOKEON 4 × 4 4 Fantomas 8 × 8 ≤ 11 Robin 8 × 8 ≤ 12	Ref [CMH13] [CMH13] [Sto16] [Sto16] [Sto16] [Sto16] [Sto16] [Sto16] [Sto16] [Sto16] [Sto16] [BMP13] [DPAR00] [GLSV15] [GLSV15]

z 13 t 55 = z 16 ⊕ z 17 t 63 = t 49 ⊕ t 58 t 65 = t 61 ⊕ t 62 t 56 = z 12 ⊕ t 48 t 52 = z 7 ⊕ z 8 t 66 = z 1 ⊕ t 63 s 0 = t 59 ⊕ t 63 s 3 = t 53 ⊕ t 66 t 54 = z 6 ⊕ z 7 t 62 = t 52 ⊕ t 58 t 51 = z 2 ⊕ z 5 s 1 = t 64 ⊕ s 3 t 58 = z 4 ⊕ t 46 t 53 = z 0 ⊕ z 3 s 4 = t 51 ⊕ t 66 s 6 = t 56 ⊕ t 62 t 59 = z 3 ⊕ t 54 t 50 = z 2 ⊕ z 12 s 5 = t 47 ⊕ t 65 s 7 = t 48 ⊕ t 60

  y 12 ∧ y 15 t 23 = t 19 ⊕ y 21 t 34 = t 23 ⊕ t 33 z 2 = t 33 ∧ x 7 t 3 = y 3 ∧ y 6 t 15 = y 8 ∧ y 10 t 35 = t 27 ⊕ t 33 z 3 = t 43 ∧ y 16 t 5 = y 4 ∧ x 7 t 26 = t 21 ∧ t 23 t 42 = t 29 ⊕ t 33 z 4 = t 40 ∧ y 1 t 7 = y 13 ∧ y 16 t 16 = t 15 ⊕ t 12 z 14 = t 29 ∧ y 2 z 6 = t 42 ∧ y 11 t 8 = y 5 ∧ y 1 t 18 = t 6 ⊕ t 16 t 36 = t 24 ∧ t 35 z 7 = t 45 ∧ y 17 t 10 = y 2 ∧ y 7 t 20 = t 11 ⊕ t 16 t 37 = t 36 ⊕ t 34 z 8 = t 41 ∧ y 10 t 12 = y 9 ∧ y 11 t 24 = t 20 ⊕ y 18 t 38 = t 27 ⊕ t 36 z 9 = t 44 ∧ y 12 t 13 = y 14 ∧ y 17 t 30 = t 23 ⊕ t 24 t 39 = t 29 ∧ t 38 z 10 = t 37 ∧ y 3 t 4 = t 3 ⊕ t 2 t 22 = t 18 ⊕ y 19 z 5 = t 29 ∧ y 7 z 11 = t 33 ∧ y 4 t 6 = t 5 ⊕ t 2 t 25 = t 21 ⊕ t 22 t 44 = t 33 ⊕ t 37 z 12 = t 43 ∧ y 13 t 9 = t 8 ⊕ t 7 t 27 = t 24 ⊕ t 26 t 40 = t 25 ⊕ t 39 z 13 = t 40 ∧ y 5 t 11 = t 10 ⊕ t 7 t 31 = t 22 ⊕ t 26 t 41 = t 40 ⊕ t 37 z 15 = t 42 ∧ y 9 t 14 = t 13 ⊕ t 12 t 28 = t 25 ∧ t 27 t 43 = t 29 ⊕ t 40 z 16 = t 45 ∧ y 14 t 17 = t 4 ⊕ t 14 t 32 = t 31 ∧ t 30 t 45 = t 42 ⊕ t t41 z 17 = t 41 ∧ y 8 t 19 = t 9 ⊕ t 14 t 29 = t 28 ⊕ t 22 z 0 = t 44 ∧ y 15 t 21 = t 17 ⊕ y 20 t 33 = t 33 ⊕ t 24 z 1 = t 37 ∧ y 6 -bottom linear transformationt 46 = z 15 ⊕ z 16 t 49 = z 9 ⊕ z 10 t 61 = z 14 ⊕ t 57 t 48 = z 5 ⊕ t 64 = z 4 ⊕ t 59 t 57 = t 50 ⊕ t 53 t 67 = t 64 ⊕ t 65 t 47 = z 10 ⊕ z 11 t 60 = t 46 ⊕ t 57 s 2 = t 55 ⊕ t 67

Table 3 .

 3 2: Theoretical optimal parameters for our decomposition method.

	(λ, n) (1,4) (2,2) (4,1) (1,6) (2,3) (3,2) (6,1) (1,8) (2,4) (4,2) (8,1)	|B 1 | 7 8 9 4 5 6 3 4 14 15 8 9 10 6 7 8 4 5 6 24 25 28 29 30 15 16 17 18 19 8 9 10 11 12 13 5 6 7 8 9 10	r 4-bit s-boxes t 1 , t 2 , . . . , t n 2,1,1,1 1,1,1,1 1,1,1,1 2,1 1,1 1,1 1 1 6-bit s-boxes 4,3,2,2,2,2 4,3,2,2,2,2 4,2,2 3,2,2 3,2,2 3,2 3,2 2,2 3 2 2 8-bit s-boxes 17 9,7,6,5,4,4,4,3 18 9,7,5,5,4,4,4,3 19 9,6,5,5,4,4,4,3 20 8,6,5,5,4,4,4,3 21 8,6,5,5,4,4,4,3 9,5,4,4 10 8,5,4,4 11 8,5,4,3 12 7,5,4,3 13 7,5,4,3 8,4 7,4 6,4 6,3 5,3 10 5,3 7 6 5 4 3 3	C(S) 7 7 8 4 4 5 2 3 22 23 12 12 13 8 9 9 5 5 6 59 59 59 59 60 31 31 31 31 32 17 17 17 17 17 18 11 10 10 10 10 10	(λ, n) (1,9) (3,3) (9,1) (1,10) (2,5) (5,2) (10,1)	|B 1 | 35 36 37 13 14 15 16 8 9 10 49 50 51 25 26 27 13 14 15 16 17 18 19 9 10 11 12 13 14 15	r 25 26 27 9 10 11 12 6 7 8 38 39 40 19 20 21 10 11 12 13 14 15 16 7 8 9 10 11 12 13	t 1 , t 2 , . . . , t n 9-bit s-boxes 14,10,8,7,6,6,5,5,5 14,10,8,7,6,6,5,5,5 13,10,8,7,6,6,5,5,5 13,6,5 12,6,5 11,6,5 11,6,5 7 6 6 10-bit s-boxes 20,14,12,10,9,8,8,7,7,7 20,14,12,10,9,8,8,7,7,7 20,14,12,10,9,8,8,7,7,7 20,11,9,7,7 20,11,9,7,7 19,11,9,7,7 16,7 15,7 14,7 13,7 12,7 11,7 11,7 12 11 10 9 8 7 7	C(S) 91 92 92 33 33 33 34 13 13 14 140 141 142 73 74 74 33 33 33 33 33 33 34 19 19 19 19 19 19 20

Table 3 .

 3 3: Achievable smallest randomized basis computed according to Algorithm 1.

	(λ, n) |B 1 | r	(1,4) 7 2	4-bit s-boxes (2,2) 4 1	(4,1) 3 1	5-bit s-boxes (1,5) (5,1) 10 4 4 2	(1,6) 14 7	6-bit s-boxes (2,3) (3,2) 8 6 4 3	(6,1) 4 2	7-bit s-boxes (1,7) (7,1) 19 4 11 2
	(λ, n) |B 1 | r	(1,8) 26 17	8-bit s-boxes (2,4) (4,2) 14 8 9 5	(8,1) 5 3	(1,9) 35 25	9-bit s-boxes (3,3) 13 9	(9,1) 5 3	(1,10) 49 38	10-bit s-boxes (2,5) (5,2) 25 11 19 8	(10,1) 6 4

Table 3 .

 3 4: Optimal parameters with rank-drop improvements.

	n 4 5 6 7 8 8 9 10 32 δ 4 8 8 16 16 32 32 32 32 32 32 32 32 32 32	|B 1 | 7 11 12 15 16 23 24 31 32 47 48 63 64 65 66 67	r 2 5 6 8 9 15 16 22 23 37 38 52 15,12,11,9,9,8,7,7,7,6 t 1 , t 2 , . . . , t n 1,1,1,1 2,1,1,1,1 1,1,1,1,1 3,2,2,2,1,1 2,2,2,2,1,1 4,3,3,2,2,2,2 3,3,3,2,2,2,2 7,5,5,4,4,3,3,3 6,5,5,4,4,3,3,3 10,8,7,6,6,5,5,5,4 9,8,7,6,6,5,5,5,4 53 15,12,10,9,9,8,7,7,7,6 54 15,12,10,9,8,8,7,7,7,6 55 15,12,10,9,8,8,7,7,6,6 56 14,12,10,9,8,8,7,7,6,6	C(S) 6 11 11 19 19 33 33 56 56 93 93 143 143 143 143 143	Gain 1 2 2 4 4 5 5 5 5 3 3 2 2 2 2 2

Table 3

 3

	SC2000 S 6 Khazad & CLEFIA (S 0 , S 1 )	15 31 31 31	n = 6 8 n = 8 22 22 22	1, 1 3, 2, 2, 2, 1, 1 11, 5, 5, 4, 4, 3, 3, 3 9, 6, 5, 4, 4, 4, 3, 3 11, 5, 5, 4, 4, 3, 3, 3	12 19 61 61 61
	C(S) # s-boxes (over 1000)	59 9	60 536	61 455
	version of our improved decomposition, where

.6: Results of Algorithm 2 for random s-boxes (n = 8, α = 8, δ = 16).

Table 3 .

 3 8: Optimal and achievable parameters for random s-boxes.

	Optimal/Achievable Optimal Achievable Optimal Achievable Optimal Achievable Optimal Achievable Optimal Achievable Optimal Achievable	(λ, n) (2,2) (2,2) (2,3) (2,3) (3,2) (3,2) (2,4) (2,4) (4,2) (4,2) (3,3) (3,3)	|B 1 | 4-bit s-boxes r 5 2 5 2 6-bit s-boxes 8 4 8 4 6 3 6 3 8-bit s-boxes 16 11 16 11 10 7 10 7 9-bit s-boxes 15 11 15 11	t 1 , t 2 , . . . , t n 1,1 1,1 4,2,2 5,2,2 3,2 4,2 8,5,4,3 9,6,5,3 6,4 7,4 11,6,5 14,6,5	C(S) 4 4 12 13 8 9 31 34 17 18 33 36	proba. -0.2 -0.3 -0.9 -0.02 -1.0 -0.8

Table 3 .

 3 10: Cyclotomic classes with CPRR.

	λ 4	r 3	t 2	L Original CRV parameters	exp. 2 w + 1

Table 3 .

 3 11: Performances of CRV original version and improved version (with and without optimized parameters).

	λ = 6 (HT) λ = 6 (EL) λ = 8 (HT) λ = 8 (EL) λ = 10 (EL) λ = 8 (HT) 4 λ = 8 (EL) 4	Original CRV ([CRV14]) # ISW # CPRR clock cycles 5 0 142.5 d 2 + O(d) 5 0 167.5 d 2 + O(d) 10 0 285 d 2 + O(d) 10 0 335 d 2 + O(d) 19 0 997.5 d 2 + O(d) 10 0 775 d 2 + O(d) 10 0 935 d 2 + O(d)	# ISW 2 2 5 5 10 5 5	CRV with CPRR ([CPRR15]) # CPRR clock cycles 3 132 d 2 + O(d) 3 142 d 2 + O(d) 5 267.5 d 2 + O(d) 5 292.5 d 2 + O(d) 9 858 d 2 + O(d) 5 657.5 d 2 + O(d) 5 737.5 d 2 + O(d)	Optimized CRV with CPPR ratio # ISW # CPRR clock cycles 93% 2 3 132 d 2 + O(d) 85% 2 3 142 d 2 + O(d) 94% 4 6 264 d 2 + O(d) 87% 4 6 284 d 2 + O(d) 86% 8 11 827 d 2 + O(d) 85% 4 6 634 d 2 + O(d) 79% 4 6 698 d 2 + O(d)	ratio 93% 85% 93% 85% 83% 82% 75%

  .1 with [⊕] a t-NI sharewise addition, [⊗] a t-SNI multiplication, and two Boolean sharings [x 1 ] and [x 2 ]. Applying Barthe et al's tool maskComp on this circuit automatically inserts a t-SNI refresh gadget in the cycle formed by gates [x 1 ], [⊕], and [⊗] as represented in Figure

Proposition 4.3.5. A

  . . , I n , denoted [x 1 ] I 1 , . . . , [x n ] In , and outputs a simulation of C([x 1 ], . . . , [x n ]) P , which is returned by the simulation experiment. The simulator wins the game if and only if the two experiments return identical distributions.

shared circuit C is t-non-interfering secure if and only if for every adversary A, there exists a simulator S that wins the t-non-interfering security game defined in

  Definition 4.3.6 (Strong non-interfering security from [BBD+16]). A circuit is t-strong non-interfering (t-SNI) if and only if any set of at most t intermediate variables whose t 1 on the internal variables ( i.e. intermediate variables except the output's ones) and t 2 on output variables can be perfectly simulated from at most t 1 shares of each input.

Strong Non-Interfering Security Game. The t-strong-non-interfering (t-SNI) security game is similar to the t-NI security game depicted in

  as defined in Section 4.3. Through a sequence of games we obtain a broad simplification of the problem of verifying whether C is probing secure or not. At each step of our reduction, a new game is introduced which is shown to be equivalent to the previous one, implying that for any adversary A, there exists a simulator S that wins the new game if and only if the circuit C is t-probing secure. We get a final game (see Game 3 hereafter) in which only the inputs of the multiplication gadgets can be probed by the adversary and the circuit is flattened into an (equivalent) circuit of multiplicative depth one. This allows us to express

		equivalent circuit of multiplicative depth 1
	Game 0 t probes on a st. shared circuit	Game 1	Game 2	Game 3
	no probe on internal variables	probes only on multiplications' inputs

  [x 1 ], . . . , [x n ]) P in Game 1 and C ([x 1 ], . . . , [x N ]) P in Game 2 output identical distributions. We can then simply define S 1 as the simulator S 2 winning against the defined adversary A 2 . We thus get a simulator that outputs the same distribution as ExpReal 1 from which we get Equation (4.9). Let us now show:∀A 1 , ∃S 1 wins Game 1 (⇔ C t-probing secure) ⇒ ∀A 2 , ∃S 2 wins Game 2 (4.10)For each adversary A 2 returning (x 1 , . . . , x N ) and P , we define A 1 as the adversary that returns the same choice of probes P and the truncated input with the n first elements of (x

1 , . . . , x n ). For the same reason as above, the evaluations C([x 1 ], . . . , [x n ]) P in Game 1 and

C ([x 1 ], . . . , [x N ]

) P in Game 2 then output identical distributions and we can simply define S 2 as the simulator S 1 winning against the defined adversary A 1 . We thus get a simulator that outputs the same distribution as ExpReal 2 from which we get Equation (4.10). Corollary 4.4.3. A standard shared circuit C is t-probing secure if and only if the standard shared circuit Flatten(C) is t-probing secure.

  N ) the set of inputs and by P the set of probes returned by A 2 . As previously, we denote P = P a ∪ P r ∪ P m such that P a are the probes on addition gadgets, P r are probes on refresh gadgets inputs, and P m are probes on pairs of inputs of multiplication gadgets. We further denote by M 0 , . . . , M t the induced matrices from the probes P as defined inLemma 4.4.4. By assumption of the contrapositive statement Equation (4.16), we have Im(M 0

	∃S 2 wins Game 2 (⇔ C t-probing secure)	(4.15)
	which is equivalent to show the contrapositive statement:
	∃A 2 , ∀S 2 fails Game 2 ⇒ ∃A 3 , ∀S 3 fails Game 3 (⇔ C t-probing secure)	(4.16)
	We denote by (x 1 , . . . , x

  Proposition 4.6.4. Let C be a standard shared circuit implementing an SPN block cipher as pictured in Figure 4.11. And let C S and C KS be the standard shared (sub-)circuits implementing S and KS respectively. If both conditions 1. C S 's and C KS 's outputs are t-SNI gadgets' outputs, 2. C S and C KS are t-probing secure (for any sharing order t + 1), are fulfilled, then C is also t-probing secure.

Table 4 .

 4 1: Results for AES s-box circuit.

	Target 8E 72	G 1 {(8E, 80), (96875, 8E)} {(9, 72), (C2D0B, 72)}	Target C6	G 1 {(C6, 86), (418605, C6)}

2 + 905.5 t + 872 1069 t 2 + 132 t + 872 Table 4.2: Performance results of the implementation AES s-box depending on the number of refresh gadgets.

Table 5 .

 5 1: Size of the full multiplication table (in kilobytes) w.r.t. λ.

	λ = Table size 0.25 KB 4	5 1 KB 4 KB 16 KB 64 KB 512 KB 1048 KB 6 7 8 9 10

Table 5 .

 5 2: Multiplication performances.

	bin mult v1 clock cycles (λ ≤ 8) 10λ + 3 (+3) 7λ + 3 (+3) bin mult v2 clock cycles (λ > 8) 10λ + 4 (+3) 7λ + 15 (+3) registers 5 5 code size (λ ≤ 8) 52 2 λ-1 + 48	exp-log v1 exp-log v2 18 (+2) 16 (+2) 35 (+2) 31 (+2) 5 (+1) 5 (+1) 2 λ+1 + 48 3 • 2 λ + 40 3 • 2 λ + 42 2 kara. half-tab 19 (+2) 10 (+3) 38 (+2) n/a 6 (+1) 5 (+1) 3λ 2 +1 + 24 2 2λ + 12 full-tab 4 (+3) n/a 5

Table 5 .

 5 3: Implementation results for the ISW multiplication over F 2

	clock cycles 8 16 75 291 1155 4611 18435 164 164 164 code size (bytes) 2 4 32 2 4 8 16 164 Unrolled ISW 58 231 949 3876 15682 132 464 1848 7500 30324 d 32 Straight ISW 164	register usage random usage 10 d (d -1)/2 8 d (d -1)/2

Table 5 .

 5

		4: Possible values for correction
		d correction 0x5555555 0x11111111 0x01010101 0x00010001 2 4 8 16
		Table 5.5: Performance results for BDF + (generic and unrolled)
	clock cycles 4 8 16 BDF + generic n/a 77 146 285 n/a n/a 248 244 240 n/a code size (bytes) d 2 32 2 4 8 16 32 BDF + unrolled 34 47 81 149 120 280 356 504 808 748	registers random usage 13 (d -1)/4 13 (d -1)/4
	;; mask update
	EOR	$mask , $mask , $correction
	LSL	$correction , $correction , #1

r Algorithm 8 LoopRow Procedure Input: indexes

  i, t randoms (s j ) j∈{3,...,d-1}1: for j = d down to t by 2 do

	2: 3:	r i,j ← {0, 1} 32

Table 5 .

 5 6: Implementation results for the BBP + multiplication

	d Original BBP + Optimized BBP + Unrolled BBP +	clock cycles 8 16 n/a 334 1204 4552 17680 n/a 344 344 code size (bytes) 2 4 32 2 4 8 16 344 88 274 970 3658 14218 428 428 428 428 36 161 775 3018 11920 100 344 1544 5996 23732 32 344 428	register usage random usage 12 d + d 2 /4 12 d + d 2 /4 11 d + d 2 /4
	targeted values by averaging them. More precisely, during the computation of Algorithm 5, each share a i (resp. b i ) is manipulated d times. Hence one can average the noise and reduce it by a factor √ d (in a standard deviation metric)

  that this scheme (in a slightly modified version) could actually be used to securely evaluate any quadratic function f over F 2 λ . The method is based on the Algorithm 11 Quadratic Evaluation Input: shares a i such that i a i = a, a look-up table for a algebraic degree-2 function h Output: share c i such that i c i = h(a)

	1: for i = 0 to d do 2: c i = h(a i )
	3: for i = 0 to d do 4: for j = i + 1 to d do
	5: 6: 7: 8: 9: 10: 11: 12: 13:	s ← F 2 λ s ← F 2 λ t ← s t ← t + h(a i + s ) t ← t + h(a j + s ) t ← t + h((a i + s ) + a j ) t ← t + h(s ) s ← t

Table 5 .

 5 8: Timings of the ISW-based mask refreshing.

	Straightforward version Optimized version		7.5 d 2 + 1.5 d -7 ≤ 2.5 d 2 + 2.5 d + 2
	1,000 clock cycles 1,500 2,000	ISW-FT multiplication ISW-based mask refreshing Optimized version
	500
	2	4	6	8	10
			d

Table 5 .

 5 .9. 1} 32 2: c ← a ⊕ r ⊕ ROT(r, 1) return c 9: Implementation results for the BDF + refresh

	Algorithm 12 BDF + Refresh Input: shares a Output: shares c
	1: r ← {0, clock cycles d 2 4 8 16 32 BDF + Refresh 25 25 25 25 16 116 116 116 116 110 code size (bytes) 2 4 8 16 32	register usage random usage 10 d
	5.3.

4 Performance and Comparisons 5.3.4.1 Secure Multiplications Comparison We

  now compare the four multiplication algorithms over F 2 , i.e. when working on the Boolean field. In Table5.10 we gather the four multiplications we studied in this section and we compare them at an algorithmic level. Namely, we give the operation counts (in terms of 32-bit XOR, 32-bit AND, and sharing-wise ROT) to perform a secure 32-bit AND between two sharings. The NI/SNI row specifies if the considered multiplication is SNI-or NI-secure. The row "max use of shares" represents (informally) the level of protection against horizontal side-channels attacks: O(d) means that each share is processed a linear number in d times (i.e. no protection) and O(1) means that each share is processed a constant number of times (i.e. protection).

Table 5 .

 5 2, 4, 8, 16 and 32. Moreover, 10: Comparison of the multiplications at the algorithmic level.

	Algorithm:		ISW	BDF + (BM model)	BDF + w. (BM model) refresh	BBP +	BCPZ
	NI/SNI:			SNI	SNI (up to d = 3)	SNI (up to d = 8)	NI	SNI
	Max shares:	use	of	O(d)	O(d)	O(d)	O(d)	O(1)
	XOR-32 count: AND-32 count:		2d(d -1) d 2	d(3d/2 -1) d 2	d(3d/2 + 1) d 2	(7d 2 -6d)/4 d 2	d 2 log(d) + 2d d 2
	ROT count: Random bits:		0 16d(d -1)	d(5d/4 -1) 32d (d -1)/4	5d 2 /4 32d (d -1)/4 + 32	0 8d 2 + 16d -1	0 16d 2 log(d) + d

Table 5 .

 5 11: Multiplication performances for TRNG-1.

	clock cycles	TRNG-1	code size (bytes)

Table 5 .

 5 12: Multiplication performances for TRNG-2.

	clock cycles	TRNG-2	code size (bytes)

Table 5 .

 5 13: Performance of ISW and CPRR schemes.

	ISW-FT Clock cycles (for n ≤ 8) 21.5 d 2 -0.5 d 28.5 d 2 -0.5 d ISW-HT Clock cycles (for n > 8) n/a n/a Code size (bytes) 184 + 2 2n 244 + 2 3n 2 +1 Random usage (bytes)	ISW-EL 33.5 d 2 -0.5 d 52.5d 2 -4.5d + 12 37d 2 -14 d CPRR 25d 2 -8 d 196 + 2 n 280 + 3 • 2 n

Table 5 .

 5 Timings of ISW and CPRR schemes.for ISW, since we consider that a 256-byte table in code is always affordable. For n = 8 on the other hand, we did not implement the full-table, since we consider that a 64-KB table in code would be to much in most practical scenarios. Tables 5.14 and 5.15 give the obtained performance in terms of clock cycles and code size. For comparison, we give both the performance of the m-parallel case and that of the m-serial case. We also exhibit the asymptotic ratio i.e. the ratio between the d 2 constants of the serial and parallel case. These performance are illustrated onFigures 5.6 and 5.7. Figures 5.6 and 5.7 give the obtained performance in terms of clock cycles. 14: Performance of parallel ISW and CPRR schemes for n = 8.

		1,000 2,000 3,000 clock cycles	ISW FT ISW HT ISW EL CPRR
			2	4	6	8	10
					d
	Clock cycles Asympt. ratio Code size	Figure 5.5: ISW-HT 4 ISW-HT × 4 77.5 d 2 -1.5 d + 2 114d 2 -2d 68% 100% 8.6 KB 8.1 KB	ISW-EL 4 95.5 d 2 -1.5 d + 2 134 d 2 -2 d ISW-EL × 4 70% 100% 1.5 KB 0.9 KB	CPRR 4 54 d 2 -22 d 100 d 2 -32 d CPRR × 4 54% 100% 580 B 408 B
	Random usage	d(d-1) 2	2d(d -1)		d(d-1) 2		2d(d -1)	d(d -1)	4d(d -1)

Table 5 .

 5 15: Performances of parallel ISW and CPRR schemes for n = 4.

	Clock cycles Asympt. ratio Code size	ISW-FT 8 ISW-FT × 8 72 d 2 172d 2 -4d 42% 100% 804 B 388 B	CPRR 8 94 d 2 -42 d -3 200 d 2 -64 d CPRR × 8 47% 100% 596 B 168 B
	Random usage

Table 5

 5

		.16: Register usage
	ISW-FT/EL ISW-HT CPRR	Input/output LUT & TRNG addresses addresses 3 2 3 2 2 2	Loop counters 2 2 2	ISW / CPRR Temporary Total variables variables 1 5 (-2) 11 1 5 (-1) 12 2 4 12

Table 5 .

 5 18: Performances in clock cycles.Boolean case. For the Boolean case, it is worth noticing that packing and unpacking the bitslice registers for the parallelization of the ISW-ANDs implies a linear overhead in d. For

	CRV 4 × 4 s-boxes λ = 8 2576 d 2 + 5476 d + 2528 2376 d 2 + 3380 d + 5780 656 d 2 + 19786 d + 5764 2757 d 2 + 17671 d + 2402 AD Boolean case Median case 4 × 4 s-boxes 16 s-boxes 2 × 8 2 × 8 s-boxes 2 × 8 s-boxes 16 s-boxes n/a λ = 4 337 d 2 + 563 d + 434 564 d 2 + 270 d + 660 59 d 2 + 1068 d + 994 n/a

d ∈ [[

Table 5 .

 5 19: Code sizes and RAM consumptions.Median case. These results show that the median case is slightly less efficient in terms of timings. However, it provides an interesting tradeoff in terms of memory consumption. Indeed the bitslice implementation has the drawback of being quite consuming in terms of RAM (with 644d bytes needed) and the CRV-based implementation has the drawback of having an important code size (27.5 KB) which is mainly due to the half-table multiplication and the tabulation linearized polynomials over F 256 . In terms of code size, the median case is the best. The median case offers a nice alternative when both RAM and code size are constrained. It also needs the same amount of randomness than the CRV decomposition and more than twice less than the bitslice decomposition.

	λ = 8 Code size RAM λ = 4 Code size RAM	CRV 4 × 4 s-boxes 27.5 KB 80d bytes 2 × 8 s-boxes 3.2 KB 24d bytes	AD 4 × 4 s-boxes 11.2 KB 188d bytes 2 × 8 s-boxes 2.6 KB 64d bytes	Boolean case 16 s-boxes 4.6KB 644d bytes 16 s-boxes 2.2 KB 132d bytes	Median case 2 × 8 8.7 KB 92d bytes n/a n/a n/a

  2 = y 12 • y 15 t 23 = t 19 ⊕ y 21 t 34 = t 23 ⊕ t 33 z 9 = t 44 • y 12 t 3 = y 3 • y 6 t 15 = y 8 • y 10 t 35 = t 27 ⊕ t 33 z 10 = t 37 • y 3 t 5 = y 4 • x 7 t 26 = t 21 • t 23 t 42 = t 29 ⊕ t 33 z 4 = t 40 • y 1 t 7 = y 13 • y 16 t 16 = t 15 ⊕ t 12 z 14 = t 29 • y 2 z 6 = t 42 • y 11 t 8 = y 5 • y 1 t 18 = t 6 ⊕ t 16 t 36 = t 24 • t 35 z 13 = t 40 • y 5 t 10 = y 2 • y 7 t 20 = t 11 ⊕ t 16 t 37 = t 36 ⊕ t 34 z 15 = t 42 • y 9 t 12 = y 9 • y 11 t 24 = t 20 ⊕ y 18 t 38 = t 27 ⊕ t 36 z 7 = t 45 • y 17 t 13 = y 14 • y 17 t 30 = t 23 ⊕ t 24 t 39 = t 29 • t 38 z 8 = t 41 • y 10 t 4 = t 3 ⊕ t 2 t 22 = t 18 ⊕ y 19 z 5 = t 29 • y 7 z 16 = t 45 • y 14 t 6 = t 5 ⊕ t 2 t 25 = t 21 ⊕ t 22 t 44 = t 33 ⊕ t 37 z 17 = t 41 • y 8 t 9 = t 8 ⊕ t 7 t 27 = t 24 ⊕ t 26 t 40 = t 25 ⊕ t 39 z 11 = t 33 • y 4 t 11 = t 10 ⊕ t 7 t 31 = t 22 ⊕ t 26 t 41 = t 40 ⊕ t 37 z 12 = t 43 • y 13 t 14 = t 13 ⊕ t 12 t 28 = t 25 • t 27 t 43 = t 29 ⊕ t 40 z 2 = t 33 • x 7 t 17 = t 4 ⊕ t 14 t 32 = t 31 • t 30 t 45 = t 42 ⊕ t 41 z 3 = t 43 • y 16 t 19 = t 9 ⊕ t 14 t 29 = t 28 ⊕ t 22 z 0 = t 44 • y 15 t 21 = t 17 ⊕ y 20 t 33 = t 32 ⊕ t 24 z 1 = t 37 • y 6 -bottom linear transformationt 46 = z 15 ⊕ z 16 t 49 = z 9 ⊕ z 10 t 61 = z 14 ⊕ t 57 t 48 = z 5 ⊕ z 13 t 55 = z 16 ⊕ z 17 t 63 = t 49 ⊕ t 58 t 65 = t 61 ⊕ t 62 t 56 = z 12 ⊕ t 48 t 52 = z 7 ⊕ z 8 t 66 = z 1 ⊕ t 63 s 0 = t 59 ⊕ t 63 s 3 = t 53 ⊕ t 66 t 54 = z 6 ⊕ z 7 t 62 = t 52 ⊕ t 58 t 51 = z 2 ⊕ z 5 s 1 = t 64 ⊕ s 3 t 58 = z 4 ⊕ t 46 t 53 = z 0 ⊕ z 3 s 4 = t 51 ⊕ t 66 s 6 = t 56 ⊕ t 62 t 59 = z 3 ⊕ t 54 t 50 = z 2 ⊕ z 12 s 5 = t 47 ⊕ t 65 s 7 = t 48 ⊕ t 60 t 64 = z 4 ⊕ t 59 t 57 = t 50 ⊕ t 53 t 67 = t 64 ⊕ t 65 t 47 = z 10 ⊕ z 11 t 60 = t 46 ⊕ t 57 s 2 = t 55 ⊕ t 67

  x 1 t 7 = x 3 ⊕ t 5 t 2 = x 1 • t 2 t 8 = x 3 ∨ t 5 t 3 = x 0 ⊕ t 2 t 9 = t 7 ∨ t 6 y 3 = x 3 ⊕ t 3 y 2 = t 6 ⊕ t 8 t 4 = t 1 • t 3 y 0 = y 2 ⊕ t 7 t 5 = t 4 ⊕ x 1 y 1 = t 3 ⊕ t 9 t 6 = t 1 ⊕ y 3

Table 5 .

 5 20: Performance of secure bitsliced s-boxes and comparison.

	Bitslice AES s-box (16 ) KHL (2× 8 ) Alg. decomp. for n = 8 (4× 4 ) Bitslice PRESENT s-box (16 ) F • G (2× 8 ) CRV for n = 4 (2× 8 )	Clock cycles 288 d 2 + 1097 d + 1080 764 d 2 + 512 d + 538 2376 d 2 + 3812 d + 5112 61.5 d 2 + 178.5 d + 193 376 d 2 -168 d + 204 295 d 2 + 667 d + 358	Code size 3.1 KB 4 KB 10.3 KB 752 B 1.4 KB 2.1 KB

Table 5 .

 5 21: Performances of masked blockciphers implementation.

	Bitslice AES Standard AES (KHL ) Standard (AES RP-HT ) Standard (AES RP-EL ) Bitslice PRESENT Standard PRESENT (F • G ) Standard PRESENT (CRV )	Clock cycles 2880 d 2 + 13675 d + 11872 7640 d 2 + 6229 d + 6311 9580 d 2 + 5129 d + 7621 10301 d 2 + 6561 d + 7633 1906.5 d 2 + 10972.5 d + 7712 11656 d 2 + 341 d + 9081 9145 d 2 + 45911 d + 11098	Code (KB) 7.5 4.8 12.4 4.1 2.2 1.9 2.6	Random (bytes) 320d(d -1) 560d(d -1) 400d(d -1) 400d(d -1) 372d(d -1) 496d(d -1) 248d(d -1)

Table 5 .

 5 22: Timings for masked bistlice AES and PRESENT with a 60 Mhz clock.

	d = 2 0.89 ms 1.39 ms 1.99 ms 2.7 ms 8.01 ms d = 3 d = 4 d = 5 d = 10 Bitslice PRESENT 0.62 ms 0.96 ms 1.35 ms 1.82 ms 5.13 ms Bitslice AES

The original version of the RP scheme[START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF] actually involved a weak mask refreshing procedure which was exploited in[START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF] to exhibit a flaw in the s-box processing. The CPRR variant of ISW was originally meant to patch this flaw but the authors observed that using their scheme can also improve the performances. The security of the obtained variant of the RP scheme was recently verified up to masking order 4 using program verification techniques[START_REF] Barthe | Verified Proofs of Higher-Order Masking[END_REF].

The authors of[START_REF] Kim | A Fast and Provably Secure Higher-Order Masking of AES S-Box[END_REF] suggest to perform d

= d 2 • d with a full tabulated multiplication but this would actually imply a flaw as described in[START_REF] Coron | Higher-Order Side Channel Security and Mask Refreshing[END_REF]. That is why we use a CPRR evaluation for this multiplication.

Note that some conventions exist for the first four registers R0-R3, also called argument registers, and serving to store the arguments and the result of a function at call and return respectively.

We only count the calls to ISW and CPRR since other operations are similar in the three variants and have linear complexity in d.

Indeed if f1 = f2 then (v1, v2) can be simulated by (g1(• • • ) + r , g2(• • • ) + r ) for some uniform random r .

This instruction performs a logical right-shift but instead of filling the vacant bits with 0, it fills these bits with the leftmost bit operand (i.e. the sign bit).

Note that for λ > 8, the constant 2 λ -1 does not lie in the range of constants enabled by ARM (i.e. rotated 8-bit values). In that case, one can use the BIC instruction to perform a logical AND where the second argument is complemented. The constant to be used is then 2 λ which well belongs to ARM constants whatever the value of λ.

Putting several shares of the same variable in a single register would induce a security flaw in the probing model where full registers can be probed. For this reason, we avoid doing so and we stress that parallelization does not result in such an undesired result. However, it should be noted that in some other relevant security models, such as the single-bit probing model or the bounded moment leakage model[START_REF] Barthe | Parallel Implementations of Masking Schemes and the Bounded Moment Leakage Model[END_REF], this would not be an issue anyway.

Note that the timings of the optimized version cannot be fully interpolated with a quadratic polynomial but we provide a tight quadratic upper bound (see Table

5.8).

We do not count the initialization of the register $one which is done once and not for each share.

Acknowledgments

Acknowledgments

Louis Goubin, Antoine Joux, Tancrède Lepoint, Chantal Lundvel, Michele Minelli, Matthieu Rivain et Junwei Wang. Mes conjugaisons de franglais, mon fin palet, les heures à faire du

Acknowledgments vii