Sonia Belaïd
email: sonia.belaid@cryptoexperts.com

Jean-Sébastien Coron
email: jean-sebastien.coron@uni.lu

Emmanuel Prouff
email: emmanuel.prouff@ssi.gouv.fr

Matthieu Rivain
email: matthieu.rivain@cryptoexperts.com

Abdul Rahman Taleb
email: abdul.taleb@cryptoexperts.com

Random Probing Security: Verification, Composition, Expansion and New Constructions

Keywords: Compiler, Masking, Automated verification, Random probing model +

The masking countermeasure is among the most powerful countermeasures to counteract side-channel attacks. Leakage models have been exhibited to theoretically reason on the security of such masked implementations. So far, the most widely used leakage model is the probing model defined by Ishai, Sahai, and Wagner at (CRYPTO 2003). While it is advantageously convenient for security proofs, it does not capture an adversary exploiting full leakage traces as, e.g., in horizontal attacks. Those attacks target the multiple manipulations of the same share to reduce noise and recover the corresponding value. To capture a wider class of attacks another model was introduced and is referred to as the random probing model. From a leakage parameter p, each wire of the circuit leaks its value with probability p. While this model much better reflects the physical reality of side channels, it requires more complex security proofs and does not yet come with practical constructions. In this paper, we define the first framework dedicated to the random probing model. We provide an automatic tool, called VRAPS, to quantify the random probing security of a circuit from its leakage probability. We also formalize a composition property for secure random probing gadgets and exhibit its relation to the strong non-interference (SNI) notion used in the context of probing security. We then revisit the expansion idea proposed by Ananth, Ishai, and Sahai (CRYPTO 2018) and introduce a compiler that builds a random probing secure circuit from small base gadgets achieving a random probing expandability property. We instantiate this compiler with small gadgets for which we verify the expected properties directly from our automatic tool. Our construction can tolerate a leakage probability up to 2 -8 , against 2 -25 for the previous construction, with a better asymptotic complexity.

Introduction

Most cryptographic algorithms are assumed to be secure against black-box attacks where the adversary is limited to the knowledge of some inputs and outputs to recover the manipulated secrets. However, as revealed in the late nineties [START_REF] Paul | Differential power analysis[END_REF], when implemented on physical devices, they become vulnerable to the more powerful side-channel attacks which additionally exploit the physical emanations such as temperature, time, power consumption, electromagnetic radiations.

As such attacks may only require cheap equipment and can be easily mounted in a short time interval, the community had to adapt quickly by looking for efficient countermeasures. The most widely deployed approach to counteract side-channel attacks was simultaneously introduced in 1999 by Chari et al. [START_REF] Chari | Towards sound approaches to counteract power-analysis attacks[END_REF] and by Goubin and Patarin [START_REF] Goubin | DES and differential power analysis (the "duplication" method)[END_REF] and is now called masking. Basically, the idea is to split each sensitive variable x of the implementation into n shares such that n -1 of them are generated uniformly at random and the last one is computed as the combination of x and all the previous shares according to some group law * . When * is the (bitwise) addition, we talk about linear sharing (aka Boolean masking). The adversary thus needs to get information on all the shares of x to recover information on the sensitive value. This countermeasure is really simple to implement for linear operations which are simply applied on each share separately. However, things are getting trickier for non-linear operations where it is impossible to compute the result without combining shares.

To reason about the security of masked implementations, the community introduced leakage models. One of the most broadly used is the probing model, introduced by Ishai, Sahai, and Wagner [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF]. In a nutshell, a circuit is claimed to be t-probing secure if the exact values of any set of t intermediate variables do not reveal any information on the secrets. As leakage traces are assumed to reveal noisy functions of the manipulated data, this model is motivated by the difficulty to recover information from the combination of t variables from their noisy functions in masking schemes (as t grows). Nevertheless, the probing model fails to capture the huge amount of information resulting from the leakage of all manipulated data, and in particular from the repeated manipulation of identical values (see horizontal attacks in [START_REF] Battistello | Horizontal side-channel attacks and countermeasures on the ISW masking scheme[END_REF]). Therefore, after a long sequence of works building and analyzing masking schemes with respect to their security in the probing model [START_REF] Rivain | Provably secure higher-order masking of AES[END_REF][START_REF] Coron | Higher-order side channel security and mask refreshing[END_REF][START_REF] Belaïd | Private multiplication over finite fields[END_REF], the community is now looking for security in more practical models.

The noisy leakage model was originally considered by Chari et al. in [START_REF] Chari | Towards sound approaches to counteract power-analysis attacks[END_REF] and was later formalized by Prouff and Rivain in [START_REF] Prouff | Masking against side-channel attacks: A formal security proof[END_REF] as a specialization of the only computation leaks model [START_REF] Micali | Physically observable cryptography (extended abstract)[END_REF] in order to better capture the reality of the physical leakage. Informally, a circuit is secure in the noisy leakage model if the adversary cannot recover the secrets from a noisy function of each intermediate variable of the implementation. While realistic, this model is not convenient for security proofs, and therefore masking schemes continued to be verified in the probing model relying on the not tight reduction that was formally established by Duc, Dziembowski, and Faust [START_REF] Duc | Unifying leakage models: From probing attacks to noisy leakage[END_REF].

The latter reduction actually came with an intermediate leakage model, called random probing model, to which the security in the noisy leakage model reduces to. In the random probing model, each intermediate variable leaks with some constant leakage probability p. A circuit is secure in this model if there is a negligible probability that these leaking wires actually reveal information on the secrets. It is worth noting that this notion advantageously captures the horizontal attacks which exploit the repeated manipulations of variables throughout the implementation. Classical probingsecure schemes are also secure in the random probing model but the tolerated leakage probability (a.k.a. leakage rate) might not be constant which is not satisfactory from a practical viewpoint. Indeed, in practice the side-channel noise might not be customizable by the implementer.

Only a few constructions [START_REF] Ajtai | Secure computation with information leaking to an adversary[END_REF][START_REF] Andrychowicz | Circuit compilers with O(1/ log(n)) leakage rate[END_REF][START_REF] Ananth | Private circuits: A modular approach[END_REF] tolerate a constant leakage probability. These three constructions are conceptually involved and their practical instantiation is not straightforward. The first one from Ajtai et al. and its extension [START_REF] Andrychowicz | Circuit compilers with O(1/ log(n)) leakage rate[END_REF] are based on expander graphs. The tolerated probability is not made explicit. The third work [START_REF] Ananth | Private circuits: A modular approach[END_REF] is based on multi-party computation protocols and an expansion strategy; the tolerated probability is around 2 -26 and for a circuit with |C| gates, the complexity is O(|C| • poly(κ)) for some parameter κ but the polynomial is not made explicit.

Following the long sequence of works relying on the probing security, formal tools have recently been built to supervise the development of masking implementations proven secure in the probing model. Namely, verification tools are now able to produce a security proof or identify potential attacks from the description of a masked implementation at up to some masking orders (i.e., < 5) [START_REF] Barthe | Verified proofs of higher-order masking[END_REF][START_REF] Coron | Formal verification of side-channel countermeasures via elementary circuit transformations[END_REF][START_REF] Belaïd | Tight private circuits: Achieving probing security with the least refreshing[END_REF]. In the same vein, compilers have been built to automatically generate masked implementations at any order given the high level description of a primitive [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF][START_REF] Belaïd | Tight private circuits: Achieving probing security with the least refreshing[END_REF][START_REF] Belaïd | Tornado: Automatic generation of probing-secure masked bitsliced implementations[END_REF]. Nevertheless, no equivalent framework has yet been proposed to verify the security of implementations in the random probing model.

Our contributions. In this paper, we aim to fill this huge gap by providing a framework to verify, compose, and build random probing secure circuits from simple gadgets. Our contributions are three-fold.

Automatic verification tool. As a first contribution, we define a verification method that we instantiate in a tool to automatically exhibit the random probing security parameters of any small circuit defined with addition and multiplication gates whose wires leak with some probability p. In a nutshell, a circuit is (p, f )-random probing secure if it leaks information on the secret with probability f (p), where f (p) is the failure probability function. From these notations, our tool named VRAPS (for Verifier of Random Probing Security), based on top of a set of rules that were previously defined to verify the probing security of implementations [START_REF] Barthe | Verified proofs of higher-order masking[END_REF], takes as input the description of a circuit and outputs an upper bound on the failure probability function. While it is limited to small circuits by complexity, the state-of-the-art shows that verifying those circuits can be particularly useful in practice (see e.g. the maskVerif tool [START_REF] Barthe | Verified proofs of higher-order masking[END_REF]), for instance to verify gadgets and then deduce global security through composition properties and/or low-order masked implementations. The source code of VRAPS is publicly available. 7Composition and expanding compiler. We introduce a composition security property to make gadgets composable in a global random probing secure circuit. We exhibit the relation between this new random probing composability (RPC) notion and the strong non-interference (SNI) notion which is widely used in the context of probing security [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF]. Then, we revisit the modular approach of Ananth, Ishai, and Sahai [START_REF] Ananth | Private circuits: A modular approach[END_REF] which uses an expansion strategy to get random probing security from a multi-party computation protocol. We introduce the expanding compiler that builds random probing secure circuits from small base gadgets. We formalize the notion of random probing expandability (RPE) and show that a base gadget satisfying this notion can be securely used in the expanding compiler to achieve arbitrary/composable random probing security. As a complementary contribution, our verification tool, VRAPS, is extended to verify the newly introduced RPC and RPE properties.

Instantiation. We instantiate the expanding compiler with new constructions of simple base gadgets that fulfill the desired RPE property, which is verified by VRAPS. For a security level κ, our instantiation achieves a complexity of O(κ 7.5 ) and tolerates a constant leakage probability p ≈ 0.0045 > 2 -8 . In comparison, and as a side contribution, we provide a precise analysis of the construction from [START_REF] Ananth | Private circuits: A modular approach[END_REF] and show that it achieves an O(κ 8.2 ) complexity for a much lower tolerated leakage probability (p ≈ 2 -26 ). Finally, we note that our framework probably enables more efficient constructions based on different base gadgets; we leave such optimizations open for future works.

Preliminaries

Along the paper, K shall denote a finite field. For any n ∈ N, we shall denote [n] the integer set [n] = [1, n] ∩ Z. For any tuple x = (x 1 , . . . , x n ) ∈ K n and any set I ⊆ [n], we shall denote

x| I = (x i ) i∈I . Any two probability distributions D 1 and D 2 are said ε-close, denoted D 1 ≈ ε D 2 , if their statistical distance is upper bounded by ε, that is SD(D 1 ; D 2 ) := 1 2 x |p D 1 (x) -p D 2 (x)| ≤ ε ,
where p D 1 (•) and p D 1 (•) denote the probability mass functions of D 1 and D 2 .

Circuit Compilers

In this paper, an arithmetic circuit over a field K is a labeled directed acyclic graph whose edges are wires and vertices are arithmetic gates processing operations over K. We consider three types of arithmetic gate:

an addition gate, of fan-in 2 and fan-out 1, computes an addition over K, a multiplication gate, of fan-in 2 and fan-out 1, computes a multiplication over K, a copy gate, of fan-in 1 and fan-out 2, outputs two copies of its input.

A randomized arithmetic circuit is equipped with an additional type of gate:

a random gate, of fan-in 0 and fan-out 1, outputs a fresh uniform random value of K.

A (randomized) arithmetic circuit is further formally composed of input gates of fan-in 0 and fanout 1 and output gates of fan-in 1 and fan-out 0. Evaluating an -input m-output circuit C consists in writing an input x ∈ K in the input gates, processing the gates from input gates to output gates, then reading the output y ∈ K m from the output gates. This is denoted by y = C(x). During the evaluation process, each wire in the circuit is assigned with a value on K. We call the tuple of all these wire values a wire assignment of C (on input x).

Definition 1 (Circuit Compiler).

A circuit compiler is a triplet of algorithms (CC, Enc, Dec) defined as follows:

-CC (circuit compilation) is a deterministic algorithm that takes as input an arithmetic circuit C and outputs a randomized arithmetic circuit C. -Enc (input encoding) is a probabilistic algorithm that maps an input x ∈ K to an encoded input x ∈ K . -Dec (output decoding) is a deterministic algorithm that maps an encoded output y ∈ K m to a plain output y ∈ K m .

These three algorithms satisfy the following properties:

-Correctness: For every arithmetic circuit C of input length , and for every x ∈ K , we have

Pr Dec C( x) = C(x) x ← Enc(x) = 1 , where C = CC(C).
-Efficiency: For some security parameter λ ∈ N, the running time of CC(C) is poly(λ, |C|), the running time of Enc(x) is poly(λ, |x|) and the running time of Dec y is poly(λ, | y|), where poly(λ, q) = O(λ k 1 q k 2 ) for some constants k 1 , k 2 .

Linear Sharing and Gadgets

In the following, the n-linear decoding mapping, denoted LinDec, refers to the function n K n → K defined as

LinDec : (x 1 , . . . , x n ) → x 1 + • • • + x n ,
for every n ∈ N and (x 1 , . . . , x n ) ∈ K n . We shall further consider that, for every n, ∈ N, on input ( x 1 , . . . , x ) ∈ (K n ) the n-linear decoding mapping acts as LinDec : ( x 1 , . . . , x ) → (LinDec( x 1 ), . . . , LinDec( x )) .

Let us recall that for some tuple x = (x 1 , . . . , x n ) ∈ K n and for some set

I ⊆ [n], the tuple (x i ) i∈I is denoted x| I .
Definition 2 (Linear Sharing). Let n, ∈ N. For any x ∈ K, an n-linear sharing of x is a random vector x ∈ K n such that LinDec( x) = x. It is said to be uniform if for any set

I ⊆ [n] with |I| < n the tuple x| I is uniformly distributed over K |I| . A n-linear encoding is a probabilistic algorithm LinEnc which on input a tuple x = (x 1 , . . . , x ) ∈ K outputs a tuple x = ( x 1 , . . . , x ) ∈ (K n ) such that x i is a uniform n-sharing of x i for every i ∈ [ ].
In the following, we shall call an (n-share, -to-m) gadget, a randomized arithmetic circuit that maps an input x ∈ (K n ) to an output y ∈ (K n ) m such that x = LinDec( x) ∈ K and y = LinDec( y) ∈ K m satisfy y = g(x) for some function g. In this paper, we shall consider gadgets for three types of functions (corresponding to the three types of gates): the addition g : (x 1 , x 2 ) → x 1 + x 2 , the multiplication g : (x 1 , x 2 ) → x 1 • x 2 and the copy g : x → (x, x). We shall generally denote such gadgets G add , G mult and G copy respectively. Definition 3 (Standard Circuit Compiler). Let λ ∈ N be some security parameter and let n = poly(λ). Let G add , G mult and G copy be n-share gadgets respectively for the addition, multiplication and copy over K. The standard circuit compiler with sharing order n and base gadgets G add , G mult , G copy is the circuit compiler (CC, Enc, Dec) satisfying the following:

1. The input encoding Enc is an n-linear encoding. 2. The output decoding Dec is the n-linear decoding mapping LinDec. 3. The circuit compilation CC consists in replacing each gate in the original circuit by an n-share gadget with corresponding functionality (either G add , G mult or G copy ), and each wire by a set of n wires carrying a n-linear sharing of the original wire. If the input circuit is a randomized arithmetic circuit, each of its random gates is replaced by n random gates, which duly produce a n-linear sharing of a random value.

For such a circuit compiler, the correctness and efficiency directly holds from the correctness and efficiency of the gadgets G add , G mult and G copy .

Random Probing Leakage

Let p ∈ [0, 1] be some constant leakage probability parameter. This parameter is sometimes called leakage rate in the literature. Informally, the p-random probing model states that during the evaluation of a circuit C each wire leaks its value with probability p (and leaks nothing otherwise), where all the wire leakage events are mutually independent. In order to formally define the random-probing leakage of a circuit, we shall consider two probabilistic algorithms:

-The leaking-wires sampler takes as input a randomized arithmetic circuit C and a probability p ∈ [0, 1], and outputs a set W, denoted as

W ← LeakingWires(C, p) ,
where W is constructed by including each wire label from the circuit C with probability p to W (where all the probabilities are mutually independent). -The assign-wires sampler takes as input a randomized arithmetic circuit C, a set of wire labels W (subset of the wire labels of C), and an input x, and it outputs a |W|-tuple w ∈ (K∪{⊥}) |W| , denoted as

w ← AssignWires(C, W, x) ,
where w corresponds to the assignments of the wires of C with label in W for an evaluation on input x.

We can now formally define the random probing leakage of a circuit.

Definition 4 (Random Probing Leakage). The p-random probing leakage of a randomized arithmetic circuit C on input x is the distribution L p (C, x) obtained by composing the leaking-wires and assign-wires samplers as

L p (C, x) id = AssignWires(C, LeakingWires(C, p), x) .
Remark 1. By convention the output wires of C (i.e. the wires incoming output gates) are excluded by the LeakingWires sampler whereas the input wires of C (i.e. the wires connecting input gates to subsequent gates) are included. Namely the output set W of LeakingWires(C, p) does not include any output wire label of C. This is because when composing several circuits (or gadgets), the output wires of a circuit are the input wires in a next circuit. This also relates to the widely admitted only computation leaks assumption [START_REF] Micali | Physically observable cryptography (extended abstract)[END_REF]: the processing of a gate leaks information on its input values (and information on the output can be captured through information on the input).

Definition 5 (Random Probing Security). A randomized arithmetic circuit C with • n ∈ N input gates is (p, ε)-random probing secure with respect to encoding Enc if there exists a simulator Sim such that for every x ∈ K :

Sim(C) ≈ ε L p (C, Enc(x)) . (1)
A circuit compiler (CC, Enc, Dec) is (p, ε)-random probing secure if for every (randomized) arithmetic circuit C the compiled circuit C = CC(C) is (p, |C| • ε)-random probing secure where |C| is the size of original circuit.

As in [START_REF] Ananth | Private circuits: A modular approach[END_REF] we shall consider a simulation with abort. In this approach, the simulator first calls the leaking-wires sampler to get a set W and then either aborts (or fails) with probability ε or outputs the exact distribution of the wire assignment corresponding to W. Formally, for any leakage probability p ∈ [0, 1], the simulator Sim is defined as

Sim( C) = SimAW( C, LeakingWires( C, p)) (2)
where SimAW, the wire assignment simulator, either returns ⊥ (simulation failure) or a perfect simulation of the requested wires. Formally, the experiment

W ← LeakingWires( C, p) out ← SimAW( C, W) leads to Pr[out = ⊥] = ε and out | out = ⊥ id = AssignWires( C, W, Enc(x)) | out = ⊥ . (3)
It is not hard to see that if we can construct such a simulator SimAW for a compiled circuit C, then this circuit is (p, ε)-random probing secure.

Formal Verification

In this section we show how to compute the simulation failure probability f (p) as a function of the leakage probability p for the base gadgets. Since even for simple gadgets this tasks would be difficult to perform by hand, we use a formal verification tool to compute f (p).

Simulation Failure probability

We first derive an upper bound on the simulation failure probability as a function of the leakage probability p. We consider a compiled circuit C composed of s wires labeled from 1 to s and a simulator SimAW as defined in previous section. For any sub-set W ⊆ [s] we denote by δ W the value defined as follows:

δ W = 1 if SimAW( C, W) = ⊥, 0 otherwise.
The simulation failure probability ε in (3) can then be explicitly expressed as a function of p. Namely, we have ε = f (p) with f defined for every p ∈ [0, 1] by:

f (p) = W⊆[s] δ W • p |W| • (1 -p) s-|W| . (4)
Letting c i be the number of sub-sets W ⊆ [s] of cardinality i for which δ W = 1, namely for which the simulation fails, we have c i = |W|=i δ W and hence (4) simplifies to

f (p) = s i=1 c i • p i • (1 -p) s-i . (5)
For any circuit C achieving t-probing security, the values δ W with |W| ≤ t are equal to zero, and therefore the corresponding c i 's are zero, which implies the following simplification:

f (p) = s i=t+1 c i • p i • (1 -p) s-i .
Moreover, by definition, the coefficients c i satisfy:

c i s i (6)
which leads to the following upper-bound for f (p):

f (p) s i=t+1 s i • p i • (1 -p) s-i .
Example: evaluating f (p) for the 2-share ISW multiplication gadget (ISW-2). This gadget takes at input the 2-sharings (x 0 , x 1 ) and (y 0 , y 1 ) of x and y respectively, and outputs the 2-sharing

(z 0 , z 1 ) = (x 0 • y 0 + r 0 , x 1 • y 1 + r 0 + x 0 • y 1 + x 1 • y 0 )
where r 0 is a random value. The processing is composed of the following intermediate results, where each variable is assigned a wire:

c 0 = x 0 * y 0 z 0 = c 0 + r 0 c 1 = x 1 * y 1 c 2 = c 1 + r 0 c 3 = x 0 * y 1 c 4 = c 2 + c 3 c 5 = x 1 * y 0 z 1 = c 4 + c 5
When the same variable is involved as input of several operations, a copy gadget (with 1 input wire and 2 output wires) is applied to duplicate it. Consequently, each new use of the same variable as input of an operation adds 2 wires to the final count of overall wires. It may be checked that the circuit corresponding to ISW-2 is composed of 21 wires, excluding the 2 output wires. Since it is 1-SNI but not 2-SNI, every set with a single wire can be simulated, which is not the case for all pairs of wires. Actually, 51 among the latter pairs cannot be simulated. If we continue the test for the sets of cardinality from 3 to 21, we get the following list of coefficients c i , 1 ≤ i ≤ 21, computed with the verification tool described in the next section: 0, 51, 754, 4827, 18875, 52994, 115520, 203176, 293844, 352702, 352715, 293930, 203490, 116280, 54264, 20349, 5985, 1330, 210, 21, 1. Directly injecting these coefficients in [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF] gives the expression of f (p) for ISW-2.

Verification method

For any compiled circuit C and any simulator defined as in Section 2.3, the computation of the function f (p) for any probability p essentially amounts to computing the values of the coefficients c i 's appearing in [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF]. If no assumption is made on the circuit, this task seems difficult to carry out by hand. Actually, it may be checked that an exhaustive testing of all the possible tuples of wires for a gadget with s wires has complexity lower bounded by 2 s , which gives 2 21 for a simple gadget like the ISW multiplication gadget with two shares per input. Here, we introduce a verification tool, that we call VRAPS, enabling to automatically test the perfect simulation for any set of wires of size lower than or equal to some threshold β. The role of the latter threshold is simply to control the verification duration (which can be long if the circuit to test is complex). Our tool implicitly defines a simulator that may fail with a probability ε = f (p) satisfying [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF].

The verification tool takes as input the representation of a compiled circuit C and a test parameter β, and outputs the list of coefficients c 1 , ..., c β . It is assumed that C takes as input the n-linear encoding Enc(x) of vector x = (x 1 , . . . , x ) defined in K . It is moreover assumed that C is composed of s wires respectively denoted by w 1 , ..., w s . In the following, we consider s-tuples in the form of u = (u 1 , . . . , u s ) ∈ {0, 1} s together with the common rule u ⊂ u iff for every i ∈ [s], u i = 1 ⇒ u i = 1 (in this case u will be said to be included in u). An s-tuple u for which there exists an assignment of the wires in W = {w i ; i ∈ [s], u i = 1} such that the simulation fails shall be called a failure tuple. Such a tuple shall be said to be incompressible if no tuple t ⊂ t is a failure tuple. The main idea of the proposed verification tool is to test the simulation failure only on incompressible failure tuples whose Hamming weight ranges from 1 to β. The steps are described in Algorithm 1.

Algorithm 1 Verification tool

Input: a compiled circuit C with s wires and a threshold β s Output: a list of β coefficients c1, ..., c β 1: p ← [] will be used to store a list of failure tuples 2: c ← (0, . . . , 0) will be used to store the output coefficients 3: for h = 1 to β do 4:

h ← listTuples(s,h) list of s-tuples of Hamming weight h 5:

( p h , f 1 h ) ← eliminateFromSmaller( h , p)
select tuples including an incompressible failure tuple 6: f 1 h : the elements of h which are not incompressible (i.e. which include at least one element from p ) -p h : the elements of h which are incompressible (i.e. h \ f 1 h ) The function failureTest takes as input the second list p h and checks if a perfect simulation can be achieved for each wire family W corresponding to a tuple in p h . Basically, for each wire family, a sequence of rules taken from maskVerif [START_REF] Barthe | Verified proofs of higher-order masking[END_REF] is tested to determine whether W can be perfectly simulated. It outputs f 2 h , the list of incompressible failure s-tuples of Hamming weight h. In a nutshell, each wire w i in W is considered together with the algebraic expression ϕ i (•) describing its assignment by C as a function of the circuit inputs and the random values returned by the random gates, then the three following rules are successively and repeatedly applied on all the wires families W (see [START_REF] Barthe | Verified proofs of higher-order masking[END_REF] for further details): rule 1: check whether all the expressions ϕ i (•) corresponding to wires w i in W contain all the shares of at least one of the coordinates of x; rule 2: for every ϕ i (•), check whether a random r (i.e. an output of a random gate) additively masks a sub-expression e (which does not involve r) and appears nowhere else in the other ϕ j (•) with j = i; in this case replace the sum of the so-called sub-expression and r by r, namely e + r ← r; rule 3: apply mathematical simplifications on the tuple.

f 2 h ← failureTest( C, p h ) identify failure tuples in p h 7: p ← p ∪ f 2 h update list of incompressible failure tuples 8: c ← updateCoeffs(c, f 1 h ∪ f 2 h ) update
Function updateCoeffs takes as input the current array of β coefficients c i for 1 i β and the concatenation of both lists of potential failure tuples f 1 h and f 2 h . For each failure tuple, these coefficients are updated.

Link with the tool maskVerif . This tool was introduced in [START_REF] Barthe | Verified proofs of higher-order masking[END_REF] to automatically and formally verify higher-order masking implementations, and has further been improved to verify the t-NI and t-SNI security properties. Essentially, this tool verifies each property by analyzing the dependency of sets of fixed number of wires (say t) with a specific number of input shares. In our case, the size of the wires' sets which must be tested (to decide whether the corresponding coefficient c i must be incremented or not) is a priori not bounded, or (for efficiency reasons) is bounded by a threshold β that is not a security parameter but an efficiency one. Moreover, our testing must take intermediate failures into account. Although maskVerif does not directly allows to answer our specific needs, we could have exploited its rules directly in our tool with dedicated add-ons. However we wanted to provide an easy-to-understand global tool and we therefore re-implemented the common parts (essentially those enabling to decided whether a given set of wires can be simulated or not).

Optimization 1 (grouping the wires). In most of the compiled circuits that we usually considered, several wires are always assigned the same value. Grouping those wires altogether allows us to significantly reduce the number of wires to be considered by the verification tool. Let us denote by s the number of groups, by α i the size of the i-th group and by w i a representative of the i-th group. Then, Algorithm 1 can be almost directly applied to the shortened list of s wires (instead of s). The single main difference is that the updateCoeffs procedure also takes into account the weights α i when updating the coefficients c i . For instance, considering h = 3, and the tuple (1, 1, 1, 0, ..., 0) with respective weights α 1 = 2 (for w 1 ), α 2 = 1 (for w 2 ) and α 3 = 3 (for w 3 ), the function would increase c 3 with 6, c 4 with 6, c 5 with 4 and c 6 with 1. The latter evaluation is performed using a recursive function which evaluates the number of partitions of an integer j into h parts with the constraints that each part should be at least one. When this optimization is applied, it may be observed that the updateCoeffs procedure also starts to update some coefficients c i for i > β. These updated coefficients can be used as lower bounds of the final c i values. They will be called c inf i in the rest of this paper. c sup i will be used to denote the maximal possible value for c i , namely the binomial coefficient s i .

Optimization 2 (using the 'longest failure tuple'). To build all the potential failure tuples, a strategy consists in exhaustively testing all the s-tuples with Hamming weight below the Hamming weight of the longest incompressible attack tuple. Once this set, let say U inc , has been built, the set of all potential failure tuples can be deduced by executing the following procedure:

-for one u inc ∈ U inc define U failure = {u ∈ {0, 1} s ; u inc ⊂ u}. -for every new u inc ∈ U inc , update U failure = U failure ∪ {u ∈ {0, 1} s ; u inc ⊂ u}
Implementation. An implementation of Algorithm 1 has been developed in Python. This tool, named VRAPS, has been open sourced at:

https://github.com/CryptoExperts/VRAPS
Small examples. In order to illustrate our automatic verification of gadgets in the random probing model, we give the list of coefficients and the subsequent failure functions obtained for three known gadgets from the literature, namely the 2-share and 3-share multiplication gadgets introduced by Ishai, Sahai, and Wagner in [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF] and a 3-share multiplication gadget from [START_REF] Belaïd | Randomness complexity of private circuits for multiplication[END_REF] with an optimal number of random variables to achieve security in the 2-probing model. Descriptions for these three gadgets are given below together with an approximation of the corresponding failure function f produced by our tool. Operations are performed according to the standard priority rules. Sharings x and y denote the inputs, sharings z denote the outputs, and r i are random variables. Copy gates are implicit when variables are used more than once. Hereafter O(p 5 ) is to be interpreted as p tends to 0.

2-share ISW multiplication gadget (ISW-2):

z 0 = x 0 • y 0 + r 0 z 1 = x 1 • y 1 + r 0 + x 0 • y 1 + x 1 • y 0 ⇒ f (p) = 51p 2 + 754p 3 + 4827p 4 + O(p 5 )
3-share multiplication gadget from [START_REF] Belaïd | Randomness complexity of private circuits for multiplication[END_REF] (EC16-3):

   z 0 = x 0 • y 0 + r 0 + x 0 • y 2 + x 2 • y 0 z 1 = x 1 • y 1 + r 1 + x 0 • y 1 + x 1 • y 0 z 2 = x 2 • y 2 + r 0 + r 1 + x 1 • y 2 + x 2 • y 1 ⇒ f (p) = 1116p 3 + 44909p 4 + O(p 5 )
3-share ISW multiplication gadget (ISW-3):

       z 0 = x 0 • y 0 + r 0 + r 1 z 1 = x 1 • y 0 + (x 0 • y 1 + r 0 ) + x 1 • y 1 + r 2 z 2 = x 2 • y 0 + (x 0 • y 2 + r 1 )+ (x 2 • y 1 + (x 1 • y 2 + r 2 )) + x 2 • y 2 ⇒ f (p) = 1219p 3 + 55756p 4 + O(p 5 )
For our three examples, our verification tool (Algorithm 1) has been launched respectively with β = s = 21 for ISW-2, with β = 9 < s = 57 for ISW-3 and with β = 13 < s = 52 for EC16-3. In the two later cases, the missing coefficients c i with i > β have been either set to 0 or to s i . This allowed us to define a lower bound f inf and an upper bound f sup for the functions f corresponding to ISW-3 and EC16-3. The behavior of these functions is plotted in Figures 1 to 3.

Composition

This section aims to provide composition properties for random-probing secure gadgets. In a nutshell, we aim to show how to build random probing secure larger circuits from specific random probing secure building blocks.

Random Probing Composability

We introduce hereafter the random probing composability notion for a gadget. In the following definition, for an n-share, -to-m gadget, we denote by I a collection of sets I = (I 1 , . . . , I ) with

I 1 ⊆ [n], . . . , I ⊆ [n]
where n ∈ N refers to the number of shares. For some x = ( x 1 , . . . , x ) ∈ (K n ) , we then denote

x| I = ( x 1 | I 1 , . . . , x | I ) where x i | I i ∈ K |I i |
is the tuple composed of the coordinates of the sharing x i of indexes included in I i .

I ← Sim G 1 (W, J ) out ← Sim G 2 x| I yields Pr (|I 1 | > t) ∨ . . . ∨ (|I | > t) ≤ ε (7)
and

out id = AssignWires(G, W, x) , y| J where J = (J 1 , . . . , J m ) and y = G( x). Let f : R → R. The gadget G is (t, f )-RPC if it is (t, p, f (p))-RPC for every p ∈ [0, 1].
In the above definition, the first-pass simulator Sim G 1 determines the necessary input shares (through the returned collection of sets I) for the second-pass simulator Sim G 2 to produce a perfect simulation of the leaking wires defined by the set W together with the output shares defined by the collection of sets J . Note that there always exists such a collection of sets I since I = ([n], . . . , [n]) trivially allows a perfect simulation whatever W and J . However, the goal of Sim G 1 is to return a collection of sets I with cardinals at most t. The idea behind this constraint is to keep the following composition invariant: for each gadget we can achieve a perfect simulation of the leaking wires plus t shares of each output sharing from t shares of each input sharing. We shall call failure event the event that at least one of the sets I 1 , . . . , I output of Sim G 1 has cardinality greater than t. When (t, p, ε)-RPC is achieved, the failure event probability is upper bounded by ε according to [START_REF] Battistello | Horizontal side-channel attacks and countermeasures on the ISW masking scheme[END_REF]. A failure event occurs whenever Sim G 2 requires more than t shares of one input sharing to be able to produce a perfect simulation of the leaking wires (i.e. the wires with label in W) together with the output shares in y| J . Whenever such a failure occurs, the composition invariant is broken. In the absence of failure event, the RPC notion implies that a perfect simulation can be achieved for the full circuit composed of RPC gadgets. This is formally stated in the next theorem.

Composition Security

Theorem 1 (Composition). Let t ∈ N, p, ε ∈ [0, 1], and CC be a standard circuit compiler with (t, p, ε)-RPC base gadgets. For every (randomized) arithmetic circuit C composed of |C| gadgets, the compiled circuit CC(C) is (p, |C| • ε)-random probing secure. Equivalently, the standard circuit compiler CC is (p, ε)-random probing secure.

Proof. Let W denote the leaking wires of the randomized circuit CC(C) with probability p for each wire. We now build a simulator Sim taking as inputs CC(C) and W and that perfectly simulates W with probability at least (1 -|C| • ε) from the simulators of the (t, p, ε)-RPC base gadgets.

We start with splitting set W into |C| distinct subsets W i for i ∈ {1, . . . , |C|} such that each W i stands for the output of LeakingWires when applied to the i'th gadget G i of CC(C) with probability p. Then, we start from end gadgets whose outputs coincide with the circuit's outputs. We execute their Sim G i 1 with W i and J = ∅, to get the sets I of required inputs. Then, we target their parents, that are gadgets whose outputs are inputs of end gadgets. For each such gadget G i , we execute Sim G i 1 with W i and J as defined by children sets I, to get the new sets I of required inputs. The simulation goes through the circuit from bottom to top by applying the Sim G 1 simulators to get the W i and I/J sets. The simulation fails if at least one set I is of cardinal greater than t. For |C| gadgets, this happens with probability 1 -(1 -ε) |C| ≤ |C| • ε. Otherwise, the simulation runs the Sim G 2 simulators from top to bottom by randomly picking the initial (x i ) I , which completes the construction of our global simulator Sim.

Relation with Standard Probing Composition Notions

We first reformulate the Strong Non-Interference notion introduced in [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF] with the formalism used for our definition of the Random Probing Composability.

Definition 7 (Strong Non-Interference (SNI)). Let n, and t be positive integers. An n-share gadget G : (K n ) → K n is t-SNI if there exists a deterministic algorithm Sim G 1 and a probabilistic algorithm Sim G 2 such that for every set J ⊆ [n] and subset W of wire labels from G satisfying |W| + |J| t, the following random experiment with any x ∈ (K n )

I ← Sim G 1 (W, J) out ← Sim G 2 x| I yields |I 1 | |W|, . . . , |I | |W| (8)
and

out id = AssignWires(G, W, x) , y| J (9)
where I = (I 1 , . . . , I ) and y = G( x).

Then, we demonstrate that gadgets satisfying the t-SNI notion are also random probing composable for specific values that we explicit in the following proposition, whose proof is available in Appendix A.

Proposition 1. Let n, and t be positive integers and let G be a gadget from

(K n ) to K n . If G is t-SNI,
then it is also (t/2, p, ε)-RPC for any probability p and ε satisfying:

ε = s i= t 2 +1 s i p i (1 -p) s-i , ( 10
)
where s is the number of wires in G.

Verification of Gadget Composability

Our random probing verification tool (Algorithm 1) can be easily extended to define a simulator for the (t, p, ε)-random probing composability of a gadget for some t and some p. This essentially amounts to extend Algorithm 1 inputs with a multi-set O and to modify the failureTest procedure in order to test the simulation for each tuple in the input list p n augmented with the outputs coordinates with indices in O. Then, our extended algorithm is called for every set O composed of at most t indices in each of the sets J 1 , . . . , J m . The output for the call with input set O is denoted by c O = (c O 1 , . . . , c O β ). For our simulator construction, the probability ε satisfies

ε = s i=1 c i • p i • (1 -p) s-i ,
where s denotes the number of wires in the tested gadget. Moreover, the c i 's satisfy

c i = max O c O i .
Example. As an illustration of the proposition, let us consider the well deployed 3-share ISW multiplication gadget G ISW-3 : (K 3 ) 2 → (K 3 ) displayed in Section 3 and satisfying 2-SNI from [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF].

Considering implicit copy gadgets that are mandatory in the circuit definition when a variable is reused, the corresponding circuit contains s = 57 wires. From Proposition 1, this gadget is also (1, p, ε ISW )-RPC for any probability p and ε ISW such that ) and by replacing the missing coefficients c i with i > β by their upper bound s i (see [START_REF] Barthe | Parallel implementations of masking schemes and the bounded moment leakage model[END_REF]). It may be checked for small values of p the failure probability ε ISW is smaller than ε ISW which directly implies that the simulation induced by our verification tool is tighter than that deduced from Proposition 1.

ε ISW = 57 i=2 s i p i (1 -p) 57-i .

Expansion

Constructing random-probing-secure circuit compilers with a gadget expansion strategy has been proposed by Ananth, Ishai and Sahai in [START_REF] Ananth | Private circuits: A modular approach[END_REF]. Such strategy was previously used in the field of multiparty computation (MPC) with different but close security goals [START_REF] Cohen | Efficient multiparty protocols via log-depth threshold formulae -(extended abstract)[END_REF][START_REF] Hirt | Player simulation and general adversary structures in perfect multiparty computation[END_REF]. Note that such approach is called composition in [START_REF] Ananth | Private circuits: A modular approach[END_REF] since it roughly consists in composing a base circuit compiler several times. We prefer the terminology of expansion here to avoid any confusion with the notion of composition for gadgets as considered in Section 4 and usual in the literature -see for instance [START_REF] Barthe | Strong non-interference and type-directed higher-order masking[END_REF][START_REF] Belaïd | Private multiplication over finite fields[END_REF][START_REF] Belaïd | Tight private circuits: Achieving probing security with the least refreshing[END_REF].

We recall hereafter the general principle of the gadget expansion strategy and provide an asymptotic analysis of the so-called expanding circuit compiler. Then we propose an implementation of this strategy which relies on the new notion of gadget expandability. In contrast, the construction of [START_REF] Ananth | Private circuits: A modular approach[END_REF] relies on a t-out-n secure MPC protocol in the passive security model. The advantage of our notion is that it can be achieved and/or verified by simple atomic gadgets leading to simple and efficient constructions. After introducing the gadget expandability notion, we show that it allows to achieve random-probing security with the expansion strategy. We finally explain how to adapt the verification tool described in Section 3 to this expandability notion.

Expansion Strategy

The basic principle of the gadget expansion strategy is as follows. Assume we have three n-share gadgets G add , G mult , G copy and denote CC the standard circuit compiler for these base gadgets. We can derive three new n 2 -share gadgets by simply applying CC to each gadget:

G (2) add = CC(G add ), G (2)
mult = CC(G mult ) and G

(2) copy = CC(G copy ). Let us recall that this process simply consists in replacing each addition gate in the original gadget by G add , each multiplication gate by G mult and each copy gate by G copy , and by replacing each wire by n wires carrying a sharing of the original wire. Doing so, we obtain n 2 -share gadgets for the addition, multiplication and copy on K. This process can be iterated an arbitrary number of times, say k, to an input circuit C:

C CC ---→ C 1 CC ---→ • • • CC ---→ C k .
The first output circuit C 1 is the original circuit in which each gate is replaced by a base gadget G add , G mult or G copy . The second output circuit C 2 is the original circuit C in which each gate is replaced by an n 2 -share gadget

G (2) add , G (2)
mult or G

(2) copy as defined above. Equivalently, C 2 is the circuit C 1 in which each gate is replaced by a base gadget. In the end, the output circuit C k is hence the original circuit C in which each gate has been replaced by a k-expanded gadget and each wire as been replaced by n k wires carrying an (n k )-linear sharing of the original wire. The underlying compiler is called expanding circuit compiler which is formally defined hereafter. Definition 8 (Expanding Circuit Compiler). Let CC be the standard circuit compiler with sharing order n and base gadgets G add , G mult , G copy . The expanding circuit compiler with expansion level k and base compiler CC is the circuit compiler (CC (k) , Enc (k) , Dec (k) ) satisfying the following:

1. The input encoding Enc (k) is an (n k )-linear encoding. 2. The output decoding Dec is the (n k )-linear decoding mapping. 3. The circuit compilation is defined as

CC (k) (•) = CC • CC • • • • • CC k times (•)
The goal of the expansion strategy in the context of random probing security is to replace the leakage probability p of a wire in the original circuit by the failure event probability ε in the subsequent gadget simulation. If this simulation fails then one needs the full input sharing for the gadget simulation, which corresponds to leaking the corresponding wire value in the base case. The security is thus amplified by replacing the probability p in the base case by the probability ε (assuming that we have ε < p). If the failure event probability ε can be upper bounded by some function of the leakage probability: ε < f (p) for every leakage probability p ∈ [0, p max ] for some p max < 1, then the expanding circuit compiler with expansion level k shall result in a security amplification as

p = ε 0 f --→ ε 1 f --→ • • • f --→ ε k = f (k) (p) ,
which for an adequate function f (e.g. f : p → p 2 ) provides exponential security. In order to get such a security expansion, the gadgets must satisfy a stronger notion than the composability notion introduced in Section 4 which we call random probing expandability; see Section 5.3 below.

Asymptotic Analysis of the Expanding Compiler

In this section we show that the asymptotic complexity of a compiled circuit

C = CC (k) (C) is | C| = O |C| • κ e
for security parameter κ, for some constant e that we make explicit.

Let us denote by N = (N a , N c , N m , N r ) T the column vector of gate counts for some base gadget G, where N a , N c , N m , N r stands for the number of addition gates, copy gates, multiplication gates and random gates respectively. We have three different such vectors

N add . = (N add,a , N add,c , N add,m , N add,r ) T N mult . = (N mult,a , N mult,c , N mult,m , N mult,r ) T N copy . = (N copy,a , N copy,c , N copy,m , N copy,r ) T
for the gate counts respectively in the base addition gadget G add , in the base multiplication gadget G mult and in the base copy gadgets G copy . Let us define the 4 × 4 square matrix M as

M = N add | N copy | N mult | N rand with N rand = (0, 0, 0, n) T ,
where the definition N rand holds from the fact that the standard circuit compiler replaces each random gate by n random gates.

It can be checked that applying the standard circuit compiler with base gadgets G add , G mult and G copy to some circuit C with gate-count vector N C gives a circuit C with gate-count vector N C = M • N C . It follows that the kth power of the matrix M gives the gate counts for the level-k gadgets as:

M k = M • M • • • M k times = N (k) add | N (k) copy | N (k) mult | N (k) rand with N (k) rand =     0 0 0 n k    
where

N (k) add , N (k)
M = Q • Λ • Q -1 , we get M k = Q • Λ k • Q -1 with Λ k =     λ k 1 λ k 2 λ k 3 λ k 4    
where λ 1 , λ 2 , λ 3 , λ 4 are the eigenvalues of M . We then obtain an asymptotic complexity of

| C| = O |C| • (λ k 1 + λ k 2 + λ k 3 + λ k 4 ) = O |C| • max(λ 1 , λ 2 , λ 3 , λ 4 ) k
for a compiled circuit C = CC (k) (C) (where the constant in the O(•) depends on Q and shall be fairly small). Interestingly, if multiplication gates are solely used in the multiplication gadget (i.e. N add,m = N copy,m = 0) which is the case in the constructions we consider in this paper, it can be checked that (up to some permutation) the eigenvalues satisfy

(λ 1 , λ 2 ) = eigenvalues(M ac ) , λ 3 = N k mult,m and λ 4 = n k
where M ac is the top left 2 × 2 block matrix of M i.e.

M ac = N add,a N copy,a N add,c N copy,c .

We finally get

| C| = O |C| • N k max with N max = max(eigenvalues(M ac ), N mult,m ) . (11)
In order to reach some security level ε = 2 -κ for some target security parameter κ and assuming that we have a security expansion p → f (k) (p), the expansion level k must be chosen so that f (k) (p) ≤ 2 -κ . In practice, the function f is of the form

f : p → i≥d c i p i ≤ (c d + O(p)) p d .
where O(p) is to be interpredted as p tends to 0. In the rest of this paper, we shall say that such a function has amplification order d. We can then rewrite [START_REF] Belaïd | Tight private circuits: Achieving probing security with the least refreshing[END_REF] as

| C| = O |C| • κ e with e = log N max log d . ( 12
)

Random Probing Expandability

In the evaluation of random probing composability, let us recall that the failure event in the simulation of a gadget means that more that t shares from one of its inputs are necessary to complete a perfect simulation. For a gadget to be expandable we need slightly stronger notions than random probing composability. As first requirement, a two-input gadget should have a failure probability which is independent for each input. This is because in the base case, each wire as input of a gate leaks independently. On the other hand, in case of failure event in the child gadget, the overall simulator should be able to produce a perfect simulation of the full output (that is the full input for which the failure occurs). To do so, the overall simulator is given the clear output (which is obtained from the simulation of the base case) plus any set of n -1 output shares. This means that whenever the set J is of cardinal greater than t, the gadget simulator can replace it by any set J of cardinal n -1.

Definition 9 (Random Probing Expandability). Let f : R → R. An n-share gadget G :

K n × K n → K n is (t, f
)-random probing expandable (RPE) if there exists a deterministic algorithm Sim G 1 and a probabilistic algorithm Sim G 2 such that for every input ( x, y) ∈ K n × K n , for every set J ⊆ [n] and for every p ∈ [0, 1], the random experiment

W ← LeakingWires(G, p) (I 1 , I 2 , J ) ← Sim G 1 (W, J) out ← Sim G 2 (W, J , x| I 1 , y| I 2 )
ensures that 1. the failure events

F 1 ≡ |I 1 | > t and F 2 ≡ |I 2 | > t verify Pr(F 1 ) = Pr(F 2 ) = ε and Pr(F 1 ∧ F 2 ) = ε 2 (13)
with ε = f (p) (in particular F 1 and F 2 are mutually independent), 2. J is such that J = J if |J| ≤ t and J ⊆ [n] with |J | = n -1 otherwise, 3. the output distribution satisfies

out id = AssignWires(G, W, ( x, y)) , z| J (14)
where z = G( x, y).

The RPE notion can be simply extended to gadgets with 2 outputs: the Sim G 1 simulator takes two sets J 1 ⊆ [n] and J 2 ⊆ [n] as input and produces two sets J 1 and J 2 satisfying the same property as J in the above definition (w.r.t. J 1 and J 2 ). The Sim G 2 simulator must then produce an output including z 1 | J 1 and z 2 | J 1 where z 1 and z 2 are the output sharings. The RPE notion can also be simply extended to gadgets with a single input: the Sim G 1 simulator produces a single set I so that the failure event (|I| > t) occurs with probability lower than ε (and the Sim G 2 simulator is then simply given x| I where x is the single input sharing). For the sake of completeness, and since we only focus in 2 → 1 and 1 → 2 gadgets in this paper, the RPE definition for the 1 → 2 case is given in Appendix B.

It is not hard to check that the above expandability notion is stronger that the composability notion introduced in Section 4. Formally, we have the following reduction:

Proposition 2. Let f = R → R and n ∈ N. Let G be an n-share gadget. If G is (t, f )-RPE then G is (t, f )-RPC, with f (•) = 2 • f (•).
Proof. We consider a (t, f )-RPE n-share gadget G : K n × K n → K n . The (t, 2 • f )-random composability property is directly implied by the (t, f )-random probing expandability by making use of the exact same simulators and observing that

Pr (|I 1 | > t) ∨ (|I 2 | > t) ≤ Pr(|I 1 | > t) + Pr(|I 2 | > t) = 2 • ε.
The case of 1 → 2 gadgets is even more direct.

Expansion Security

Definition 9 of random probing expandability is valid for base gadgets. For level-k gadgets G (k) = CC (k-1) (G) where G ∈ {G add , G mult , G copy } is a base gadget, we provide a generalized definition of random probing expandability.

Adequate subsets of [n k

]. We first define the notion of "adequate" subsets of [n k ], instead of only bounded subsets. For this we define recursively a family S k ∈ P([n k ]), where P([n k ]) denotes the set of all subsets of [n k ], as follows:

S 1 = {I ∈ [n], |I| ≤ t} S k = {(I 1 , . . . , I n ) ∈ (S k-1 ∪ [n k-1 ]) n , I j ∈ S k-1 ∀ j ∈ [1, n] except at most t}
In other words, a subset I belongs to S k if among the n subset parts of I, at most t of them are full, while the other ones recursively belong to S k-1 ; see Figure 9 in Appendix C.1 for an illustration with n = 3 and t = 1.

Generalized definition of Random Probing Expandability. We generalize Definition 9 as follows. At level k the input sets I 1 and I 2 must belong to S k , otherwise we have a failure event. As in Definition 9, the simulation is performed for an output subset J with J

= J if J ∈ S k , otherwise J = [n k ] \ {j } for some j ∈ [n k ].

Definition 10 (Random Probing Expandability with {S

k } k∈N ). Let f : R → R and k ∈ N. An n k -share gadget G : K n k × K n k → K n k is (S k , f
)-random probing expandable (RPE) if there exists a deterministic algorithm Sim G 1 and a probabilistic algorithm Sim G 2 such that for every input ( x, y) ∈ K n k × K n k , for every set J ∈ S k ∪ [n k ] and for every p ∈ [0, 1], the random experiment

W ← LeakingWires(G, p) (I 1 , I 2 , J ) ← Sim G 1 (W, J) out ← Sim G 2 (W, J , x| I 1 , y| I 2 ) ensures that 1. the failure events F 1 ≡ I 1 / ∈ S k and F 2 ≡ I 2 / ∈ S k verify Pr(F 1 ) = Pr(F 2 ) = ε and Pr(F 1 ∧ F 2 ) = ε 2 (15)
with ε = f (p) (in particular F 1 and F 2 are mutually independent), 2. the set J is such that J = J if J ∈ S k , and J = [n k ] \ {j } for some j ∈ [n k ] otherwise, 3. the output distribution satisfies

out id = AssignWires(G, W, ( x, y)) , z| J ( 16
)
where z = G( x, y).

The notion of random probing expandability from Definition 10 naturally leads to the statement of our main theorem; the proof is given in Appendix C.1.

Theorem 2. Let n ∈ N and f : R → R. Let G add , G mult , G copy be n-share gadgets for the addition, multiplication and copy on K. Let CC be the standard circuit compiler with sharing order n and base gadgets G add , G mult , G copy . Let CC (k) be the expanding circuit compiler with base compiler CC. If the base gadgets G add , G mult and G copy are (t, f )-RPE then, G

(k) add = CC (k-1) (G add ), G (k) mult = CC (k-1) (G mult ), G (k) copy = CC (k-1) (G copy ) are (S k , f (k)
)-RPE, n k -share gadgets for the addition, multiplication and copy on K.

The random probing security of the expanding circuit compiler can then be deduced as a corollary of the above theorem together with Proposition 2 (RPE ⇒ RPC reduction) and Theorem 1 (composition theorem).

Corollary 1. Let n ∈ N and f : R → R. Let G add , G mult , G copy be n-share gadgets for the addition, multiplication and copy on K. Let CC be the standard circuit compiler with sharing order n and base gadgets G add , G mult , G copy . Let CC (k) be the expanding circuit compiler with base compiler CC. If the base gadgets G add , G mult and G copy are

(t, f )-RPE then CC (k) is (p, 2 • f (k) (p))-random probing secure.

Relaxing the Expandability Notion

The requirement of the RPE property that the failure events F 1 and F 2 are mutually independent might seem too strong. In practice it might be easier to show or verify that some gadgets satisfy a weaker notion. We say that a gadget is (t, f )-weak random probing expandable (wRPE) if the failure events verify Pr(F 1 ) ≤ ε, Pr(F 2 ) ≤ ε and Pr(F 1 ∧F 2 ) ≤ ε 2 instead of ( 22) in Definition 9. Although being easier to achieve and to verify this notion is actually not much weaker as the original RPE. We have the following reduction of RPE to wRPE; see Appendix C.3 for the proof. when (|J 1 | ≤ t) and (|J 2 | > t) and the reverse when (|J 1 | > t) and (|J 2 | ≤ t). To handle these scenarios, our tool loops over the output sets of shares of cardinal equal or less than t for the first output, and it determines whether there exists a set of n -1 shares of the second output that a simulator can perfectly simulate with the leaking wires and the former set. This leads to function f (12) and reversely to function f (21) . From these four verification steps, we can deduce f such that the copy gadget is (t, f )-wRPE:

∀p ∈ [0, 1], f (p) = max(f (1) (p), f (2) (p), f (12) (p), f (21) (p)).

Once gadgets have been proven (t, f )-weak RPE, they are also proven to be (t, f )-RPE from Proposition 3 with f : p → f (p) + 3 2 f (p) 2 . Examples of such computations for 3-share gadgets are provided in Section 6.

New Constructions

In this section, we exhibit and analyze (1, f )-wRPE gadgets for the addition, multiplication, and copy (on any base field K) to instantiate the expanding circuit compiler. These gadgets are sound in the sense that their function f has amplification order strictly greater than one. As explained in previous sections, an amplification order strictly greater than one guarantees that there exists a probability p max ∈ [0, 1] such that ∀p ≤ p max , f (p) ≤ p, which is necessary to benefit from the expansion. For 2-input gadgets, f is defined as the maximum between f 1 , f 2 , and √ f 12 . Therefore, the constraint on the amplification order also applies to the functions f 1 , f 2 , and √ f 12 . For the function f 12 , this means that the amplification order should be strictly greater than two.

We start hereafter with an impossibility result, namely there are no (2-share, 2-to-1) (1, f )-RPE gadgets such that f has an amplification order greater than one. Then, we provide concrete instantiations of addition, multiplication, and copy gadgets based on 3 shares which successfully achieve (1, f )-RPE for amplification order greater than one and can be used in the expansion compiler.

About 2-Share Gadgets

Consider a gadget G with a 2-share single output z = (z 0 , z 1 ) and two 2-share inputs x = (x 0 , x 1 ) and y = (y 0 , y 1 ). We reasonably assume that the latter are the outputs of gates with fan-in at most two (and not direct input shares). For G to be (1, f )-RPE with f of amplification order strictly greater than one, then f 12 must be of amplification strictly greater than two. In other words, we should be able to exhibit a simulator such that one share of each input is enough to simulate anyone of the output shares and an arbitrary couple of leaking wires. But the output wire z 0 and both input gates of the second output share z 1 represent the full output and require the knowledge of both inputs to be simulated. Therefore, f 12 has a non-zero coefficient in p and is thus not of amplification order strictly greater than two. We thus restrict our investigation to n-share gadgets, with n ≥ 3 to instantiate our compiler.

In the upcoming gadget descriptions, notice that variables r i are fresh random values, operations are processed with the usual priority rules, and the number of implicit copy gates can be deduced from the occurrences of each intermediate variable such that n occurrences require n -1 implicit copy gates. Also, the function expression below each gadget corresponds to the function obtained from our verification tool when verifying weak random probing expandability. It implies that the gadget is (t, f )-wRPE for t usually equal to one except when defined otherwise. A more complete description of each function (with more coefficients) is available in Appendix D.1.

Addition Gadgets

The most classical masked addition schemes are sharewise additions which satisfy the simpler probing security property. Basically, given two input n-sharings x and y, such an addition computes the output n-sharing z as z 1 ← x 1 + y 1 , z 2 ← x 2 + y 2 , . . . , z n ← x n + y n . Unfortunately, such elementary gadgets do not work in our setting. Namely consider an output set of shares J of cardinality t. Then, for any n, there exists sets W of leaking wires of cardinality one such that no set I of cardinality ≤ t can point to input shares that are enough to simulate both the leaking wire and the output shares of indexes in J. For instance, given a set J = {1, . . . , t}, if W contains x t+1 , then no set I of cardinal ≤ t can define a set of input shares from which we can simulate both the leaking wire and z 1 , . . . , z t . Indeed, each z i for 1 ≤ i ≤ t requires both input shares x i and y i for its simulation. Thus, a simulation set I would contain at least {1, . . . , t} and t + 1 for the simulation of the leaking wire. I would thus be of cardinal t + 1 which represents a failure event in the random probing expandability definition. As a consequence, such a n-share addition gadget could only be (t, f )-RPE with f with a first coefficient c 1 as defined in Section 3 strictly positive. In other words, f would be of amplification order one such that ∀p ∈ [0, 1], f (p) ≥ p.

In the following, we introduce two 3-share addition gadgets. From our automatic tool, both are (1, f )-wRPE with f of amplification order strictly greater than one. Basically, in our first addition gadget G 1 add , both inputs are first refreshed with a circular refreshing gadget as originally introduced in [START_REF] Barthe | Parallel implementations of masking schemes and the bounded moment leakage model[END_REF]:

G 1 add : z 0 ← x 0 + r 0 + r 1 + y 0 + r 3 + r 4 z 1 ← x 1 + r 1 + r 2 + y 1 + r 4 + r 5 f max (p) = √ 10p 3/2 + O(p 2 ) z 2 ← x 2 + r 2 + r 0 + y 2 + r 5 + r 3
The second addition gadget G 2 add simply rearranges the order of the refreshing variables:

G 2 add : z 0 ← x 0 + r 0 + r 4 + y 0 + r 1 + r 3 z 1 ← x 1 + r 1 + r 5 + y 1 + r 2 + r 4 f max (p) = √ 69p 2 + O(p 3 ) z 2 ← x 2 + r 2 + r 3 + y 2 + r 0 + r 5
In each gadget, x and y are the input sharings and z the output sharing; f max additionally reports the maximum of the first non zero coefficient (as defined in Section 3) of the three functions f 1 , f 2 , and f 12 , as defined in the previous section, obtained for the random probing expandability automatic verifications. A further definition of these functions can be found in Appendix D.1. Note that both gadgets G 1 add and G 2 add are built with 15 addition gates and 6 implicit copy gates.

Multiplication Gadget

We start by proving an impossibility result: no 3-share multiplication gadget composed of direct products between input shares satisfies (1, f )-RPE with amplification order strictly greater than one. Consider such a gadget G with two 3-input sharings x and y whose shares are directly multiplied together. Let (x i • y j ) and (x k • y ) be two such products such that i, j, k, ∈ [3] and i = k and j = . If both results are leaking, then the leakage can only be simulated using the four input shares. Namely, {i, k} ⊆ I 1 and {j, } ⊆ I 2 . This scenario represents a failure since cardinals of I 1 and I 2 are both strictly greater than one. As a consequence, function f 12 which records the failures for both inputs is defined with a coefficient c 2 at least equal to one. Hence f 12 is not of amplification greater than two and f cannot be of amplification order greater than one. Regular 3-share multiplication gadgets consequently cannot be used as base gadgets of our compiler.

To circumvent this issue, we build a 3-share multiplication gadget G 1 mult whose both inputs are first refreshed, before any multiplication is performed:

u 0 ← x 0 + r 5 + r 6 ; u 1 ← x 1 + r 6 + r 7 ; u 2 ← x 2 + r 7 + r 5 v 0 ← y 0 + r 8 + r 9 ; v 1 ← y 1 + r 9 + r 10 ; v 2 ← y 2 + r 10 + r 8 z 0 ← u 0 • v 0 + r 0 + u 0 • v 1 + r 1 + u 0 • v 2 + r 2 z 1 ← u 1 • v 0 + r 1 + u 1 • v 1 + r 4 + u 1 • v 2 + r 3 z 2 ← u 2 • v 0 + r 2 + u 2 • v 1 + r 3 + u 2 • v 2 + r 0 + r 4 f max (p) = √ 83p 3/2 + O(p 2 )

Copy Gadget

We exhibit a 3-share (1, f )-wRPE copy gadget G 1 copy with f of amplification order strictly greater than one:

v 0 ← u 0 + r 0 + r 1 ; w 0 ← u 0 + r 3 + r 4 v 1 ← u 1 + r 1 + r 2 ; w 1 ← u 1 + r 4 + r 5 f max (p) = 33p 2 + O(p 3 ) v 2 ← u 2 + r 2 + r 0 ; w 2 ← u 2 + r 5 + r 3
It simply relies on two calls of the circular refreshing from [START_REF] Barthe | Parallel implementations of masking schemes and the bounded moment leakage model[END_REF] on the input. This last gadget is made of 6 addition gates and 9 implicit copy gates.

Complexity and Tolerated Probability

Following the asymptotic analysis of Section 5.2, our construction yields the following instantiation of the matrix This corresponds to the maximum value p for which we have f (p) < p which is a necessary and sufficient condition for the expansion strategy to apply with (t, f )-RPE gadgets.

M M =     15
As explained in Sec. 5.2, we can compute the new gate count vectors for each of the compiled gadgets G

2(k) add , G 1(k) copy , G 1(k)
mult by computing the matrix M k . In Fig. 5, we plot the total number of gates (N a + N c + N m + N r ) in each of the compiled gadgets as a function of the level k. For instance, for level k = 9 the number of gates in the compiled gadgets is around 10 12 . For the latter level and assuming a leakage probability of p = 0.0045 (which is the maximum we can tolerate), we achieve a security of ε ≈ 2 -76 . On its right side, Fig. 6 plots the values taken by the function f such that the gadgets G 1 add , G 2 add , G 1 mult and G 1 copy are (t, f )-RPE.

Comparison with Previous Constructions

In this section, we compare our scheme to previous constructions. Specifically, we first compare it to the well-known Ishai-Sahai-Wagner (ISW) construction and discuss the instantiation of our scheme from the ISW multiplication gadget. Then we exhibit the asymptotic complexity (and tolerated leakage probability) of the Ananth-Ishai-Sahai compiler and compare their results to our instantiation.

Comparison with ISW

The classical ISW construction [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF] is secure in the t-probing model when the adversary can learn any set of t intermediate variables in the circuit, for n = 2t + 1 shares. This can be extended to t probes per gadget, where each gadget corresponds to a AND or XOR gate in the original circuit. Using Chernoff bound, security in the t-probing model per gadget implies security in the p-random probing model, where each wire leaks with probability p, with p = O(t/|G|), where |G| is the gadget size. Since in ISW each gadget has complexity O(t 2 ), this gives p = O(1/t). Therefore, in the p-random probing model, the ISW construction is only secure against a leakage probability p = O(1/n), where the number of shares n must grow linearly with the security parameter κ in order to achieve security 2 -κ . This means that ISW does not achieve security under a constant leakage probability p; this explains why ISW is actually vulnerable to horizontal attacks [START_REF] Battistello | Horizontal side-channel attacks and countermeasures on the ISW masking scheme[END_REF], in which the adversary can combine information from a constant fraction of the wires.

ISW-based instantiation of the expanding compiler. In our instantiation, we choose to construct a new 3-share multiplication gadget instead of using the ISW multiplication gadget from [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF].

In fact, ISW first performs a direct product of the secret shares before adding some randomness, while we proved in Section 6 that no such 3-share multiplication gadget made of direct products could satisfy (1, f )-RPE with amplification order strictly greater than one. Therefore the ISW gadget is not adapted for our construction with 3 shares. Table 1 displays the output of our tool when run on the ISW gadget for up to 7 shares with different values for t. It can be seen that an amplification order strictly greater than one is only achieved for t > 1, with 4 or more shares. And an order of 3/2 is only achieved with a minimum of 4 shares for t = 2, whereas we already reached this order with our 3-share construction for t = 1. If we use the 4-share ISW gadget with appropriate 4-share addition and copy gadgets instead of our instantiation, the overall complexity of the compiler would be greater, while the amplification order would remain the same, and the tolerated leakage probability would be worse (recall that our instantiation tolerates a maximum leakage probability p ≈ 2 -8 , while 4-share ISW tolerates p ≈ 2 -9.83 ). Clearly, the complexity of the 4-share ISW gadget (N a , N c , N m , N r ) = [START_REF] Prouff | Masking against side-channel attacks: A formal security proof[END_REF]30,[START_REF] Damgård | Secure multiparty AES[END_REF][START_REF] Barthe | Parallel implementations of masking schemes and the bounded moment leakage model[END_REF] is higher than that of our 3-share multiplication gadget (N a , N c , N m , N r ) = (28, [START_REF] Micali | Physically observable cryptography (extended abstract)[END_REF][START_REF] Belaïd | Private multiplication over finite fields[END_REF][START_REF] Belaïd | Tight private circuits: Achieving probing security with the least refreshing[END_REF]. In addition, using 3-share addition and copy gadgets (as in our case) provides better complexity than 4-share gadgets. Hence to reach an amplification order of 3/2, a 4-share construction with the ISW gadget would be more complex and would offer a lower tolerated leakage probability.

For higher amplification orders, the ISW gadgets with more than 4 shares or other gadgets can be studied. This is a open construction problem as many gadgets can achieve different amplification orders and be globally compared.

Complexity of the Ananth-Ishai-Sahai Compiler

The work from [START_REF] Ananth | Private circuits: A modular approach[END_REF] provides a construction of circuit compiler (the AIS compiler) based on the expansion strategy described in Section 5 with a (p, ε)-composable security property, analogous to our (t, f )-RPE property. To this purpose, the authors use an (m, c)-multi-party computation (MPC) protocol Π. Such a protocol allows to securely compute a functionality shared among m parties and tolerating at most c corruptions. In a nutshell, their composable circuit compiler consists of multiple layers: the bottom layer replaces each gate in the circuit by a circuit computing the (m, c)-MPC protocol for the corresponding functionality (either Boolean addition, Boolean multiplication, or copy). The next k -1 above layers apply the same strategy recursively to each of the resulting gates. As this application can eventually have exponential complexity if applied to a whole circuit C directly, the top layer of compilation actually applies the k bottom layers to each of the gates of C independently and then stitches the inputs and outputs using the correctness of the XOR-encoding property. Hence the complexity is in

O(|C| • N k g ) , ( 18
)
where |C| is the number of gates in the original circuit and N g is the number of gates in the circuit computing Π. The authors of [START_REF] Ananth | Private circuits: A modular approach[END_REF] prove that such compiler satisfies (p, ε)-composition security property, where p is the tolerated leakage probability and ε is the simulation failure probability. Precisely:

ε = N c+1 g • p c+1 (19)
Equations ( 18) and ( 19) can be directly plugged into our asymptotic analysis of Sec. 5.2, with N g replacing our N max and where c + 1 stands for our amplification order d. The obtained asymptotic complexity for the AIS compiler is

O |C| • κ e with e = log N g log c + 1 . ( 20
)
This is to be compared to e = log Nmax log d in our scheme. Moreover, this compiler can tolerate a leakage probability

p = 1 N 2 g .
The authors provide an instantiation of their construction using an existing MPC protocol due to Maurer [START_REF] Ueli | Secure multi-party computation made simple (invited talk)[END_REF]. From their analysis, this protocol can be implemented with a circuit of

N g = (4m-c)• m-1 c 2 +2m m c
gates. They instantiate their compiler with this protocol for parameters m = 5 parties and c = 2 corruptions, from which they get N g = 5712. From this number of gates, they claim to tolerate a leakage probability p = 1 5712 2 ≈ 2 -25 and our asymptotic analysis gives a complexity of O |C| • κ e with e ≈ 7.87 according to [START_REF] Ishai | Private circuits: Securing hardware against probing attacks[END_REF]. In Appendix E, we give a detailed analysis of the Maurer protocol [START_REF] Ueli | Secure multi-party computation made simple (invited talk)[END_REF] in the context of the AIS compiler instantiation. From our analysis, we get the following number of gates for the associated circuit:

N g = (6m -5) • m -1 c 2 + m(2k -2) + 2k 2
where k = m c .

Using the parameters m = 5 and c = 2 from the AIS compiler instantiation [START_REF] Ananth | Private circuits: A modular approach[END_REF], we get N g = 8150. This yields a tolerated leakage probability of p ≈ 2 -26 and an exponent e = log 8150/log 3 ≈ 8.19 in the asymptotic complexity O |C| • κ e of the AIS compiler. These results are to be compared to the p ≈ 2 -8 and e ≈ 7.5 achieved by our construction. In either case (N g = 5712as claimed in [START_REF] Ananth | Private circuits: A modular approach[END_REF] or N g = 8150 according to our analysis), our construction achieves a slightly better complexity while tolerating a much higher leakage probability. We stress that further instantiations of the AIS scheme (based on different MPC protocols) or of our scheme (based on different gadgets) could lead to better asymptotic complexities and/or tolerated leakage probabilities. This is an interesting direction for further research.

Implementation Results

In this section, we describe and report the performances of a proof-of-concept implementation of the expanding compiler with our base gadgets as well as a protected AES implementation. The source code of these implementations are publicly available at: https://github.com/CryptoExperts/poc-expanding-compiler All implementations were run on a laptop computer (Intel(R) Core(TM) i7-8550U CPU, 1.80GHz with 4 cores) using Ubuntu operating system and various C, python and sage libraries.

Circuit Compiler

First, we developed an implementation in python of a compiler CC, that given three n-share gadgets G add , G mult , G copy and an expansion level k, outputs the compiled gadgets G 2 shows the complexity of the compiled gadgets from Section 6 using the compiler with several expansion levels k, as well as their execution time in milliseconds when run in C on randomly generated 8bit integers. For the generation of random variables, we consider that an efficient external random number generator is available in practice, and so we simply use the values of an incremented counter variable to simulate random gates. It can be observed that both the complexity and running time grow by almost the same factor with the expansion level, with multiplication gadgets being the slowest as expected. Base gadgets with k = 1 roughly take 10 -4 ms, while these gadgets expanded 2 times (k = 3) take between 10 -2 and 10 -1 ms. The difference between the linear cost of addition and copy gadgets, and the quadratic cost of multiplication gadgets can also be observed through the gadgets' complexities.

AES Implementation

We describe hereafter a proof-of-concept AES implementation protected with our instantiation of the expanding compiler. We start by describing the underlying AES circuit (over K = GF(256)), followed by an analysis of the implementation in C of the complete algorithm.

AES circuit. We first describe the non-linear part of the AES, namely the sbox computation. For the field exponentiation (x → x 254 over GF(256)), we use the circuit representation of the processing proposed in [START_REF] Damgård | Secure multiparty AES[END_REF] and presented in Fig. 7. It corresponds to the addition chain [START_REF] Ajtai | Secure computation with information leaking to an adversary[END_REF][START_REF] Ananth | Private circuits: A modular approach[END_REF][START_REF] Barthe | Verified proofs of higher-order masking[END_REF][START_REF] Belaïd | Randomness complexity of private circuits for multiplication[END_REF][START_REF] Belaïd | Private multiplication over finite fields[END_REF][START_REF] Goubin | DES and differential power analysis (the "duplication" method)[END_REF][START_REF] Hirt | Player simulation and general adversary structures in perfect multiparty computation[END_REF]36,55,72,127,254) and it has been chosen due to its optimality regarding the number of multiplications (11 in total). Each time an intermediate result had to be reused, a copy gate (marked with ) has been inserted. For the second part of the sbox, the affine function is implemented according to the following equation:

Affine(x) = (((((((207x) 2 + 22x) 2 + 1x) 2 + 73x) 2 + 204x) 2 + 168x) 2 + 238x) 2 + 5x + 99
with the necessary copy gates. Similarly, the inverse of the affine function is implemented for the sbox inversion as follows:

Affine -1 (x) = (((((((147x) 2 + 146x) 2 + 190x) 2 + 41x) 2 + 73x) 2 + 139x) 2 + 79x) 2 + 5x + 5
The rest of the operations (MixColumns, ShiftRows, AddRoundKey) are considered as in a standard AES, while adding the necessary copy gates.

Gate count: Table 3 displays the gate count vectors for AES-128 encryption/decryption procedures as well as for their building blocks. The sbox (resp. sbox inversion) gate count vector was computed as the sum of the gate count vectors of both the exponentiation and affine (resp. affine inversion) functions. We recall that N a , N c , N m , N r stand for the number of addition gates, copy gates, multiplication gates, and random gates, respectively.

Using the gadgets G 2 add , G 1 mult and G 1 copy proposed in Sec. 6 for the compilation of the AES algorithm, we obtain the instantiation given in Equation [START_REF] Duc | Unifying leakage models: From probing attacks to noisy leakage[END_REF] of the matrix M introduced in Sec. with our 3-share gadgets that tolerate a leakage probability of p ≈ 2 -8 , a 27-share (k = 3) AES-128 takes almost 200 milliseconds to encrypt or decrypt a message.

where z = G (k+1) ( x, y). We distinguish two cases: either J * ∈ S k+1 (normal case), or J * = [n k+1 ] (saturated case).

Normal case: J * ∈ S k+1 . By definition of the expanding compiler, we have that a level-(k + 1) gadget G (k+1) is obtained by replacing each gate of the base gadget by the corresponding level-k gadget and by replacing each wire of the base gadget by n k wires carrying a (n k )-linear sharing of the original wire. In particular G (k+1) has n k+1 output wires which can be split in n groups of n k wires, each group being the output of a different G (k) gadget. We split the set J * accordingly so that We first describe the simulator Sim G (k+1)

J * = J * 1 ∪ • • • ∪ J * n ,
1 that takes the leaking wires W * and the output wires J * ∈ S k+1 to be simulated and produce the sets

I * 1 ⊆ [n k+1 ] and I * 2 ⊆ [n k+1
] of required inputs. The simulator Sim G (k+1) 1 starts by defining a set W base which is initialized to ∅; this will correspond to the set of leaking wires for the base gadget. Then the simulation goes through all the level-k gadgets composing G (k+1) from bottom to top i.e. starting with the level-k gadgets producing the output sharing up to the level-k gadgets processing the input sharings. Let us denote by {G (k) j } j these level-k gadgets. For each G (k) j , one runs the simulator Sim 1 from the (S k , f (k) )-RPE property on input W j and J j defined as follows. The set of leaking wires W j is defined as the subset of W * corresponding to the wires of G (which are not on the bottom layer), the set J is defined as the set I 1 or I 2 output from Sim 1 for the child gadget G (k) j (for which Sim 1 has already been run). Whenever a failure event occurs for a G (k) j gadget, namely when the set I (either I 1 or I 2 ) output from Sim 1 is such that I / ∈ S k , we add the index of the wire corresponding to this input in the base gadget G to the set W base . Once the Sim 1 simulations have been run for all the G (k) j gadgets, ending with the top layers, we get the final sets I corresponding to the input shares. Each of these sets corresponds to an n k -sharing as input of a G (k) j gadget, which corresponds to a wire as input of the base gadget among the 2 • n wires carrying the two input n-sharings of the base gadget. We denote by I * 1,1 , . . . , I * 1,n and I * 2,1 , . . . , I * 2,n the corresponding sets so that defining

I * 1 = I * 1,1 ∪ . . . ∪ I * 1,n and I * 2 = I * 2,1 ∪ . . . ∪ I * 2,n , (24)
the tuple x * | I * 1 and y * | I * 2 contains the shares designated by the final I sets. At the end of the Sim G (k+1) 1 simulation, the set W base contains all the labels of wires in the base gadget G for which a failure event has occurred in the simulation of the corresponding G (k) j gadget. Thanks to the (S k , f (k) )-RPE property of these gadgets, the failure events happen (mutually independently) with probability ε k which implies

W base id = LeakingWires(G, ε k ) (25)
Recall that |J base | ≤ t. We can then run Sim G 1 to obtain:

(I 1,base , I 2,base ) = Sim G 1 (W base , J base ) . (26)
For all 1 ≤ i ≤ n, if i ∈ I 1,base , we force I * 1,i ← [n k ], so that the corresponding i-th input wire of the base gadget can be computed from the corresponding input wires in I * 1,i . The simulator Sim G (k+1) 1 then returns (I * 1 , I * 2 ) as output. The (t, f )-RPE property of the base gadget G implies that the base failure events |I 1,base | = n and |I 2,base | = n are ε k+1 -mutually unlikely, where ε k+1 = f (ε k ). We argue that for all 1 ≤ i ≤ n, I * 1,i / ∈ S k ⇐⇒ i ∈ I 1,base . Namely if a failure event has occurred for a set I * 1,i (i.e. I * 1,i / ∈ S k ) then we must have i ∈ I 1,base . Indeed, if a failure event has occurred for a set I * 1,i then the label of the ith input wire (for the first sharing) of the base gadget G has been added to W base and Sim G 1 has no choice but to include this index to the set I 1,base so that Sim G 2 can achieve a perfect simulation of the wire assignment (as required by the RPE property of G). Moreover if i ∈ I ). We deduce that the failure events F * 1 and F * 2 are also ε k+1 -mutually unlikely, as required by the (S k+1 , f (k+1) )-RPE property of G (k+1) .

We now describe the simulator Sim G The simulator then goes through all the G (k) j gadgets from input to output and for each of them runs the simulator Sim 2 of the RPE property on inputs W j , J j , x| I 1 and y| I 2 where W j and J j are the sets from the first phase of the simulation for the gadget G We must now fix δ 1 , δ 2 , δ 12 ≥ 0 to satisfy (30), with ε := ε + 3ε 2 /2 and δ 1 + δ 2 + δ 12 ≤ p succ = 1 -(ε 1 + ε 2 -ε 12 ). We fix δ 12 = (ε ) 2 -ε 12 ; this gives Pr(F 1 ∧ F 2 ) = (ε ) 2 , and from (29) we obtain δ 12 ≥ 0 as required. We let:

δ 1 := ε -ε 1 -δ 12
which gives Pr(F 1 ) = ε as required. Moreover we obtain using (29):

δ 1 = ε + 3 2 ε 2 -ε 1 -(ε + 3 2 ε 2 ) 2 -ε 12 ≥ 3 2 ε 2 -ε 2 + 3ε 3 + 9 4 ε 4 ≥ ε 2 • 1 2 -3ε - 9 4
ε 2 ≥ 0 for ε ≤ 0.14.

We obtain similar conditions for δ 2 := ε -ε 2 -δ 12 . Finally, we have

δ 1 + δ 2 + δ 12 = ε -ε 1 -δ 12 + ε -ε 2 -δ 12 + δ 12 = 2ε -ε 1 -ε 2 -(ε ) 2 + ε 12 = p succ + 2ε -(ε ) 2 -1
≤ p succ + 2ε -1 ≤ p succ for ε < 0.14.

as required.

D Instantiation

D.1 Verification functions

In this section, we give the whole set of coefficients obtained for gadgets in Section 6. When sets of coefficients are completed with . . . , then a bound of the subsequent function can be obtained from the binomial coefficients as explained in Section 3. In such cases, the number of coefficients (as the number of wires in the circuit) is given in a last column. Verification timings are also given in the tables by running the tool a laptop computer (Intel(R) Core(TM) i7-8550U CPU, 1.80GHz with 4 cores) using Ubuntu operating system.

E Complexity of the MPC Protocol in the AIS Compiler

In the following we compute the complexity and the value of N g in the instantiation of the AIS compiler [START_REF] Ananth | Private circuits: A modular approach[END_REF]. First, using this compiler, given a circuit C to compile, each gate G is implemented using a functionality F associated to the MPC protocol. Such a functionality F receives m shares of each input and then reconstructs them to obtain original values. This reconstruction can be done with 2(m -1) addition gates. Then after computing the gate G, m additive shares of the output are computed twice. This step consists of one gate for G, and 2(m -1) gates for the additive sharing along with 2(m -1) random gates. 8 So each gate G to compile is replaced by 6m -5 gates, each computed jointly by the m parties in the MPC protocol. Next, we state the complexity of the protocol from [START_REF] Ueli | Secure multi-party computation made simple (invited talk)[END_REF]. Each gate in a functionality F is jointly computed by all m parties. In the beginning, each party holds one share of each input.

The first step consists in a k-secret sharing of each input share where k = m c . For an input of m shares, each party will hold a total of m m-1 c shares. For two inputs, this step has a complexity of m(2k -2).

The second step is either performing an addition or a multiplication, depending on the gate G associated to the functionality. An addition simply means each party locally adding all its shares, holding a complexity of m m-1 c . In case of a multiplication gate, each party will locally compute the sum of the product of the shares of both inputs, and then share its local result using a secret sharing scheme as in the first step. This procedure holds a complexity of m-1 c 2 for computing the result, m(2k -2) for the secret sharing, and 2k 2 copy gates. Clearly, the cost of the second step is more important for the multiplication and can be upper bounded by 9 m -1

c 2 + m • (2k -2) + 2k 2 .
In the final step, every party broadcasts its shares to all other parties, and then adds all the shares it receives. The complexity of this step is m c . Considering the cost of replacing each gate G in the circuit to compile by 6m -5 gates, and the cost to compute each of these gates using the protocol Π, the total number of gates N g is upper bounded by (6m -5) • m -1 c 2

coefficients 9 :

 9 end for 10: return c The function listTuples outputs the list of all s-tuples with Hamming weight h with h ∈ [s]. The function eliminateFromSmaller takes as input the list h of current tuples of Hamming weight h and the list of incompressible failure tuples p . It returns two lists:

Fig. 1 :

 1 Fig. 1: Values taken by f inf (p) for ISW-3 (red) and EC16-3 (green) compared to the function p → p (black).

Fig. 2 :

 2 Fig. 2: Values of log(f inf (p)) (red) and log(fsup(p)) (blue) for ISW-3.

Fig. 3 :

 3 Fig. 3: For values p ranging from 1 to 0, values of log(f inf (p)) for ISW-3 (red) and EC16-3 (green) together with the values of log(f (p)) for ISW-2 (blue).

Figure 4

 4 Figure 4 displays for p ∈ [0, 1] the values taken by ε ISW (in red). It also displays (in green) the values ε ISW obtained by calling our verification tool on the same gadget G ISW-3 with β = 5 (seeAlgorithm 1) and by replacing the missing coefficients c i with i > β by their upper bound s i (see[START_REF] Barthe | Parallel implementations of masking schemes and the bounded moment leakage model[END_REF]). It may be checked for small values of p the failure probability ε ISW is smaller than ε ISW which directly implies that the simulation induced by our verification tool is tighter than that deduced from Proposition 1.

Fig. 4 :

 4 Fig. 4: Values taken by εISW and ε ISW as a function of p ∈ [0, 1].

  are the gate-count vectors for the level-k gadgets G respectively. Let us denote the eigen decomposition of M as

  The upper boundf (p) ≤ c d p d with c d = c d + O(p) implies f (k) (p) < (c d p) d k .Hence, to satisfy the required security f (k) (p) ≤ 2 -κ while assuming c d p < 1, the number k of expansions must satisfy:k log d (κ) -log d (-log 2 (c d p)) .

= 9 . 2 .

 92 The eigenvalues of M ac are 3 and 21, which gives N max = 21. We also have a random probing expandability with function f of amplification order d = 3 Hence we get e = log N max log d = log 21 log 1.5 ≈ 7.5 which gives a complexity of | C| = O |C| • κ 7.5 . Finally, it can be checked from the coefficients of the RPE functions given in Appendix D that our construction tolerates a leakage probability up to p max ≈ 0.0045 > 2 -8 .

Fig. 5 :

 5 Fig. 5: Number of gates for G 2(k) add , G 1(k) copy, G 1(k) mult circuits with respect to the level k. Fig. 6: Values taken by the function f for (t, f )-RPE

Fig. 6 :

 6 Values taken by the function f for (t, f )-RPE

  as a C function. The variables' type is given as a command line argument. Table

Fig. 7 :

 7 Fig. 7: Circuit for the exponentiation x → x 254 .

  the gadgets G (k) j on the bottom layer, the set J j is set to one of the J * i (with indices scaled to range in [n k ]). For all the other gadgets G (k) j

(k+1) 2 that

 2 takes as input x * | I * 1 and y * | I * 2 and produces a perfect simulation of AssignWires(G (k+1) , W * , ( x * , y * )), z| J * where z = G (k+1) ( x, y). Let x b and y b denote the n-linear sharings obtained by applying the linear decoding to each group of n k shares in x * and y * , so that the elements of x b and y b correspond to the input wires in the base gadget G. The assignment expansion property implies that a perfect assignment of the wires of G (k+1) on input x * and y * can be derived from an assignement of the wires of the base gadget G on input x b and y b . The simulator makes use of this property by first runningout base ← Sim G 2 (W base , J base , x b | I 1,base , y b | I 2,base ) ,(27)Note that the input values x b | I 1,base and y b | I 2,base can be obtained from the corresponding shares in I * 1 and I * 2 . Thanks to the (t, f )-RPE property of G and by construction of I 1,base and I 2,base , this outputs a distribution satisfying out base id = AssignWires(G, W base , ( x b , y b )), z b | J base (28)

j

  , I 1 and I 2 are the corresponding sets produced by the Sim 1 simulator for G (k) j , and x and y are the inputs of G (k) j in the evaluation of G (k+1) ( x * , y * ). Provided that the partial inputs x| I 1 and y| I 2 are perfectly simulated, this call to Sim 2 produces a perfect simulation of AssignWires(G (k) j , W j , ( x, y), z| J j where z = G (k) j ( x, y).In order to get perfect simulations of the partial inputs x| I 1 and y| I 2 , the simulator proceeds as follows. For the top layer of G (k) gadgets (the ones processing the input shares) the shares x| I 1 and y| I 2 can directly be taken from the inputs x * | I * 1 and y * | I * 2 . For the next gadgets the shares x| I 1 and y| I 2 match the shares z| J output from the call to Sim 2 for a parent gadget. The only exception occurs in case of a failure event.

ε 2 -

 2 ε 12 ), Sim G ], I 2 ) with probability p 1 = δ 1 /p succ (I 1 , [n]) with probability p 2 = δ 2 /p succ ([n], [n]) with probability p 12 = δ 12 /p succ (I 1 , I 2 )with probability 1-(p 1 + p 2 + p 12 )for some δ 1 , δ 2 , δ 12 ≥ 0 such that δ 1 + δ 2 + δ 12 ≤ p succ . We hence getPr(F 1 ) = ε 1 + δ 1 + δ 12 Pr(F 2 ) = ε 2 + δ 2 + δ 12Pr(F 1 ∧ F 2 ) = ε 12 + δ 12

Table 1 :

 1 Complexity, amplification order and maximum tolerated leakage probability of the ISW multiplication gadgets. Some leakage probabilities were not computed accurately by VRAPS for performances reasons. An interval on these probabilities is instead given by evaluating lower and upper bound functions f inf and fsup of f (p).

	# shares	Complexity	t	Amplification	log 2 of maximum tolerated
		(Na, Nc, Nm, Nr)		order	leakage probability
	3	(12, 15, 9, 3)	1	1	-
	4	(24, 30, 16, 6)	1 2	1 3/2	--9.83
			1	1	-
	5	(40, 50, 25, 10)	2	3/2	-11.00
			3	2	-8.05
			1	1	-
	6	(60, 75, 36, 15)	2 3	3/2 2	-13.00 [-9.83, -7.87]
			4	2	[-9.83, -5.92]
			1	1	-
			2	3/2	[-16.00, -14.00]
	7	(84, 105, 49, 21)	3	2	[-12.00, -7.87]
			4	5/2	[-12.00, -2.27]
			5	2	[-12.00, -3.12]

Table 2 :

 2 Complexity and execution time (in ms, on an Intel i7-8550U CPU) for compiled gadgets G

	2(k) add , G 1(k) copy, G 1(k) mult

Table 4 :

 4 Standard and n-share AES-128 execution time (in ms, on an Intel i7-8550U CPU) using compiled gadgets G

	2(k) add , G 1(k) copy, G 1(k) mult .
	AES Version	Execution Time (in ms) Encryption Decryption
	Standard (no sharing)	0.06	0.05
	3-share (k = 1)	1.08	1.07
	9-share (k = 2)	11.71	10.26
	27-share (k = 3)	200.29	197.70

id

= AssignWires(G, W, ( x, y)) , z| J *

  where each set J * i pertains to the ith group of output wires. By definition of S k , since J * ∈ S k+1 , we must have J * i ∈ S k for all 1 ≤ i ≤ n, except at most t of them for whichJ * i = [n k ].We define J base as the set of indexes i such that J * i / ∈ S k . Therefore we must have |J base | ≤ t.

  1,base then by construction we have set I * 1,i = [n k ] and therefore I * 1,i / ∈ S k . This implies that if |I 1,base | ≤ t then I * 1 ∈ S k+1 (and the same happens for I * 2 w.r.t. I 2,base

See https://github.com/CryptoExperts/VRAPS

Acknowledgments. This work is partly supported by the French FUI-AAP25 VeriSiCC project.

Assume that we can show or verify that a gadget is wRPE with the following failure event probabilities Pr(F 1 ) = f 1 (p) , Pr(F 2 ) = f 2 (p) and Pr(F 1 ∧ F 2 ) = f 12 (p) , for every p ∈ [0, 1]. Then the above proposition implies that the gadget is (p, f )-RPE with

We shall base our verification of the RPE property on the above equation as we describe hereafter.

Verification of Gadget Expandability

We can easily adapt our automatic tool to verify the weak random probing expandability for base gadgets (Definition 9). Basically, the verification is split into two steps that we first describe for the case of addition and multiplication gadgets with fan-in 2 and fan-out 1.

In a first step, our tool computes the function f to check the (t, f )-wRPE property for output sets of shares of cardinal at most t. For 2-input gadgets, this step leads to the computation of coefficients c i corresponding to three failure events F 1 , F 2 , and F 1 ∧F 2 as defined above but restricted to output sets of shares of cardinal less than t. The process is very similar to the verification of random probing composability but requires to separate the failure events counter into failure events for the first input

In the following, we denote the three functions formed from the corresponding coefficients as f

2 , and f

Then, in a second step, our tool verifies that there exists at least one set of n -1 shares for each output, such that the simulation failure is limited by f (p) for some probability p ∈ [0, 1]. In that case, it still loops on the possible output sets of shares (of cardinal n -1) but instead of computing the maximum coefficients, it determines whether the simulation succeeds for at least one of such sets. A failure event is recorded for a given tuple if no output sets of cardinal n -1 can be simulated together with this tuple from at most t shares of each input. As for the first verification step, we record the resulting coefficients for the three failure events to obtain functions f

2 , and f

(2) [START_REF] Chari | Towards sound approaches to counteract power-analysis attacks[END_REF] . From these two steps, we can deduce f such that the gadget is (t, f )-wRPE:

The computation of f for a gadget to satisfy (t, f )-weak random probing expandability is a bit trickier for copy gadgets which produce two outputs. Instead of two verification steps considering both possible ranges of cardinals for the output set of shares J, we need to consider four scenarios for the two possible features for output sets of shares J 1 and J 2 . In a nutshell, the idea is to follow the first verification step described above when both J 1 and J 2 have cardinal equal or less than t and to follow the second verification step described above when both J 1 and J 2 have greater cardinals. This leads to functions f (1) and f (2) . Then, two extra cases are to be considered, namely 5.2. Applying the same complexity analysis done previously on the gate count vectors, we display in Fig. 8 the total number of gates in the AES-128 encryption/decryption procedures as functions of the level k. For instance, for the same security level of 2 -76 exhibited in Sec. 6.5 for the gadgets of Fig. 5, the AES-128 would have to be compiled at a level k = 9, and would count around 10 16 gates. Implementation in C: An n-share AES-128 implementation was developed in C from the above description. Compiled gadgets from Section 8.1 were used for basic operations (addition, multiplication, copy), as generated using our circuit compiler described in Sec. 8.1. We chose the C 8-bit unsigned integer type, and considered operations in GF(256). For the generation of random values, we assume the availability of an efficient (pseudo)random number generator, and so we simply considered the values of an incremented counter variable to simulate the cost. Table 4 shows the AES-128 execution time on a 16-byte message with 10 pre-computed subkeys, using compiled gadgets G

mult , with respect to the expansion level k and sharing order n = 3 k . It can be seen that the execution time increases with the expansion level with a similar growth as in Table 2. This is because the complexity of the AES circuit strongly depends on the gadgets that are used to replace each gate in the original arithmetic circuit. For example,

A Proof of Proposition 1

Proof. Since G is t-SNI there exist two simulators Sim G 1 and Sim G 2 satisfying ( 8) and ( 9) for any J ⊆ [n] and any W satisfying |W| + |J| t. This is in particular true for every W and every J both of cardinality lower than or equal to

B Random Probing Expandability for 1-to-2 Gadgets

We provide hereafter the formal definition of the RPE notion for gadgets with 1 input sharing and 2 output sharings.

Definition 11 (Random Probing Expandability). Let f = R → R. An n-share gadget G :

)-random probing expandable (RPE) if there exists a deterministic algorithm Sim G 1 and a probabilistic algorithm Sim G 2 such that for every input x ∈ K n , for every pair of sets J 1 ⊆ [n] and J 2 ⊆ [n], and for every p ∈ [0, 1], the random experiment

ensures that 1. the failure event probability satisfies

where ( y, z) = G( x).

C Expandability

C.1 Illustration of the subsets S k

Fig. 9: Illustration of all elements of S1 and some elements of S2, for n = 3 and t = 1.

C.2 Proof of Theorem 2

The proof of the theorem relies on what we shall call the assignment expansion property. Throughout the proof we shall denote ε k = f (k) (p). We call level-k gadget a gadget that has been expanded

where G is a base gadget (or a level-1 gadget) among G add , G mult , G copy . We proceed by induction to show that the level-k gadgets are (S k , f (k) )-RPE. The base case is one of the theorem hypotheses, namely the base gadgets G add , G mult and G copy (i.e. the level-1 gadgets) are (t, f )-RPE, which is equivalent to (S 1 , f )-RPE. We must then show the induction step: assuming that the level-k gadgets are (S k , f (k) )-RPE, show that the level-(k + 1) gadgets are (S k+1 , f (k+1) )-RPE. For the sake of simplicity, we depict our proof by assuming that all the gadgets are 2-to-1 gadget (which is actually not the case for copy gadgets). The proof mechanism for the general case (with 2-to-1 and 1-to-2 gadgets) is strictly similar but heavier on the form.

In order to show that G (k+1) is (S k+1 , f (k+1) )-RPE we must construct two simulators Sim G (k+1)

and Sim G (k+1) 2 that satisfy the conditions of Definition 10 for the set of subsets S k+1 . More precisely, we must construct two simulators Sim G (k+1) 1 and Sim G (k+1) 2 such that for every ( x * , y * ) ∈ K n k+1 × K n k+1 , and for every set J * ∈ S k+1 ∪ [n k+1 ], the random experiment

ensures that 1. the failure events

2. the set J * is such that

In that case the simulation needs the full input x = (x 1 , . . . , x n k ) (and/or y = (y 1 , . . . , y n k )), while we have set |I 1 | = n k -1 (and/or |I 2 | = n k -1) to satisfy the RPE requirements of the parent gadget in the first simulation phase. Nevertheless, for such cases a perfect simulation of the plain value x = LinDec( x) (and/or y = LinDec( y)) is included to out base by construction of W base . We can therefore perfectly simulate the missing share from the n k -1 other shares and the plain value x (or y). We thus get a perfect simulation of AssignWires(G (k) j , W j , ( x, y), z| J j for all the level-k gadgets G (k) j which gives us a perfect simulation of AssignWires(G (k+1) , W * , ( x * , y * )), z| J * . Saturated case: J * = [n k+1 ]. The saturated case proceeds similarly. The difference is that we must simulate all n k+1 output shares of the level-(k + 1) gadget, except for one share index j * that can be chosen by the simulator.

The simulator Sim G (k+1)

1 is defined as previously. Since J * = [n k+1 ], we must define

This implies that for the gadgets G (k) j on the output layer, the sets J j are all equal to [n k ] as well. The set W base is defined as previously, and the simulator Sim G (k+1) 1 returns (I * 1 , I * 2 ) as previously. The failure events F * 1 and F * 2 are still ε k+1mutually unlikely, as required by the (S k+1 , f (k+1) )-RPE property of G (k+1) .

The simulator Sim G (k+1) 2 is defined as previously. In particular, from the running of the base gadget simulator Sim G 2 , we obtain a perfect simulation of the output wires z b | J base for some J base with |J base | = n -1. Combined with the perfect simulation of the output wires corresponding to the output sets J j from the gadgets G (k) j on the output layer, with |J j | = n k -1, we obtain a subset J of output wires for our level-(k + 1) gadget with |J | = n k+1 -1 as required. Eventually this gives us a perfect simulation of AssignWires(G (k+1) , W * , ( x * , y * )), z| J . This terminates the proof of Theorem 2.

C.3 Proposition 3

We give here the proof of Proposition 3.

Proof. Let Sim G

1 be the simulator from the (t, f )-wRPE property. This simulator outputs I 1 and

where

We show how to construct Sim G 1 which outputs I 1 and

where

and such that I 1 ⊆ I 1 and I 2 ⊆ I 2 . In particular, the latter implies that we can keep the same Sim G 2 simulator since it is always given the same input shares plus additional input shares to achieve the same simulation as before.

The simulator Sim {0, 0, 0, 9, 600, . . . }

D.3 Multiplication Gadgets

Hereafter are the coefficients c i as defined in Section 3 for multiplication gadget G mult defined in Section 6.

D.4 Copy Gadgets

Hereafter are the coefficients c i as defined in Section 3 for the copy gadget G copy defined in Section 6.