Hervé Chabanne
email: herve.chabanne@morpho.com

Houssem Maghrebi
email: houssem.maghrebi@ul.com

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

Linear Repairing Codes and Side-Channel Attacks

To strengthen the resistance of countermeasures based on secret sharing, several works have suggested to use the scheme introduced by Shamir in 1978, which proposes to use the evaluation of a random ddegree polynomial into n d+1 public points to share the sensitive data. Applying the same principles used against the classical Boolean sharing, all these works have assumed that the most efficient attack strategy was to exploit the minimum number of shares required to rebuild the sensitive value; which is d + 1 if the reconstruction is made with Lagrange's interpolation. In this paper, we highlight first an important difference between Boolean and Shamir's sharings which implies that, for some signal-to-noise ratio, it is more advantageous for the adversary to observe strictly more than d + 1 shares. We argue that this difference is related to the existence of so-called exact linear repairing codes, which themselves come with reconstruction formulae that need (much) less information (counted in bits) than Lagrange's interpolation. In particular, this result implies that, contrary to what was believed, the choice of the public points in Shamir's sharing has an impact on the countermeasure strength. As another contribution, we exhibit a positive impact of the existence of linear exact repairing schemes; we indeed propose to use them to improve the state-of-the-art multiplication algorithms dedicated to Shamir's sharing. We argue that the improvement can be effective when the multiplication operation in the base field is at least two times smaller than in its sub-fields.

Introduction

In the late nineties, attacks called Side-Channel Analysis (SCA) have been exhibited against cryptosystems implemented in embedded devices. Since the seminal works [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF][START_REF] Kocher | Differential Power Analysis[END_REF], the attacks have been refined and, in particular, the initial principle has been generalized in order to exploit several instantaneous leakage points simultaneously. This led to the introduction of the higher-order SCA attacks [START_REF] Messerges | Using Second-order Power Analysis to Attack DPA Resistant software[END_REF]. To defeat the latter ones, whose practicality has been argued in several papers [START_REF] Lomné | Behind the Scene of Side Channel Attacks[END_REF][START_REF] Oswald | Practical Second-order DPA Attacks for Masked Smart Card Implementations of Block Ciphers[END_REF][START_REF] Standaert | The world is not enough: Another look on secondorder dpa[END_REF], secret sharing techniques (aka masking) are currently the most promising type of countermeasures. They can indeed be applied to get implementations with a scalable security, parametrized by the number of shares and some physical properties of the device [START_REF] Chari | A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards[END_REF][START_REF] Prouff | Higher-Order Side Channel Security and Mask Refreshing[END_REF]. The core idea of secret sharing, originally introduced in [START_REF] Shamir | How to Share a Secret[END_REF], is to split any sensitive variable a manipulated by the device into several (say n) shares a i , and to process elementary operations on them while maintaining the property that any tuple of d < n intermediate results is independent of any secret-dependent value. The latter property is usually called d th -order security property and the set of all the tuples of shares allowing for the reconstruction of a is called reconstruction set and is denoted by R a (it contains all the tuples I ⊆ [1..n] such that a may be reconstruced from (a i ) i∈I ) 4 . Let L = (L 1 , . . . , L n ) denote the random variable in R n associated to the noisy observation of the sharing a = (a 1 , . . . , a n ) (itself viewed as a random variable) and let MI denotes the mutual information operator. The core idea behind the d th -order security is that the complexity of extracting information from a sharing satisfying the latter property increases linearly with min I∈Ra i∈I MI(a i ; L i )

-1
2 . For a given order d the security challenge is therefore to minimize the product of mutual information for every I ∈ R a . In the literature, the most classical sharing is the Boolean one in which n is chosen equal to d + 1 and the shares a i satisfy a = a 1 + • • • + a n , with + being the Boolean (xor) addition. To recover a from a Boolean sharing, the adversary needs information on all the coordinates of a (i.e. R a is reduced to the tuple {1, 2, . . . , n}) and the attack complexity, quantified by the minimum number τ Bool of realizations of a that must be observed to succeed with some probability β, hence satisfies:

τ Bool > α ×   i∈[1..d+1] MI(a i ; L i )   -1 2 . ( 1
)
where α is a some constant term depending on both β and the cardinality of the definition set of the a i [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF][START_REF] Prouff | Higher-Order Side Channel Security and Mask Refreshing[END_REF].

State of the Art. The simplicity of the Boolean sharing is an advantage from an implementation complexity point of view but, on the flip side, it helps the attacker: the information on the shared data is relatively easy to rebuild from the observed shares. Starting from this remark, Prouff and Roche in [START_REF] Prouff | Higher-order glitches free implementation of the aes using secure multi-party computation protocols[END_REF] and Goubin and Martinelli in [START_REF] Goubin | Protecting aes with shamir's secret sharing scheme[END_REF] proposed indepedently to apply Shamir's secret sharing (SSS for short) instead of Boolean sharing: the core principle of SSS is to split any sensitive variable a into n 2d + 1 shares a i which correspond to the evaluation, in n distinct non-zero public elements, of a random degree-d polynomial with constant term a [START_REF] Shamir | How to Share a Secret[END_REF]. The d th -order security property comes as a direct consequence of the so-called collusion resistance of Shamir's sharing which essentially ensures that at least d+1 evaluations (aka shares a i ) must be involved to recover a. For an (n, d)-SSS sharing of a i (namely a splitting with n shares and a degreed polynomial), R a is exactly {I ⊆ [1.

.n]; #I > d} and the reconstruction is done by polynomial interpolation. At the cost of an increase of the implementation timing complexity (compared to that obtained for Boolean sharing), the authors of [START_REF] Goubin | Protecting aes with shamir's secret sharing scheme[END_REF][START_REF] Prouff | Higher-order glitches free implementation of the aes using secure multi-party computation protocols[END_REF] argue, with simulations and experiments, that the intrinsic complexity of SSS significantly increases the value min I∈Ra;#I=d+1 i∈I MI(a i ; L i )

-1
2 and hence the security. This type of informational argumentation is also the cornerstone of Balasch et al. 's work [START_REF] Balasch | Inner Product Masking Revisited[END_REF], which is based on the concept of Inner Product (IP) sharing [START_REF] Dziembowski | Leakage-resilient circuits without computational assumptions[END_REF], or of Wang et al. 's work [START_REF] Wang | Inner product masking for bitslice ciphers and security order amplification for linear leakages[END_REF]. Implicitely, it assumes that the minimum of the product of mutual information is achieved for a (d + 1)-tuple and, under this assumption, the mimimum number τ SSS of realizations of the SSS sharing that must be observed to recover a should satisfiy:

τ SSS > α × min I⊆[1..n];#I=d+1 i∈I MI(a i ; L i ) -1 2 . (2)
Contributions. The previous hypothesis about the lower bound on τ SSS is motivated by the assumption that the most efficient way to attack an (n, d)-SSS sharing is to observe exactly d + 1 shares. The underlying remarks are that (1) observing strictly less than d + 1 shares leaks no information on the shared variable (by security property of SSS) and (2) observing strictly more than d + 1 shares will merely provide the attacker with more noise than information since d + 1 shares are already sufficient to rebuild a (by interpolation) 5 . One of the goals of this paper essentially aims at coming back on the second point which has been assumed, without being proved, in all previous works studying SSS in the SCA context. We actually highlight in the first part of this paper an important difference between Boolean and SSS sharings which implies that, for some signalto-noise ratio, it is more advantageous for the adversary to observe strictly more than d + 1 shares. This observation is illustrated in Section 3 and it is confirmed by real attack experiments on an ATMega328p architecture. For instance, Fig. 1 hereafter shows that for a noise standard deviation σ ∈ [0.2; 0.5], it is more interesting for the adversary to target 4 shares instead of 3 when attacking a (5, 2)-SSS sharing 6 . Our observation implies that the complexity of attacks against SSS may be lower than what was believed in previous studies (i.e. ( 2)) since the minimum of the product of mutual information must be processed over the full reconstruction set (and not only for the tuples of size d + 1):

τ SSS > α × min I⊆[1..n];#I d+1 i∈I MI(a i ; L i ) -1 2 . (3)
We argue that this property of SSS is directly related to the existence of linear exact repairing structures for Reed-Solomon codes [START_REF] Guruswami | Repairing reed-solomon codes[END_REF]39]. The latter ones can indeed be viewed as polynomial interpolation formula that optimize the amount of information which needs to be extracted from a reconstruction tuple to recover the shared value. We exhibit two important consequences of this observation:

firstly, it implies that the choice of the public points in SSS sharing plays a role in the security (and the efficiency) of the countermeasure, secondly, it implies that it may be more efficient for an adversary to extract strictly less than m bits of information on d > d + 1 shares, than to extract m bits of information on exactly d + 1 shares (when Lagrange's interpolation is applied).

The core idea behind the second point is that the difficulty of extracting m/t bits of information from a noisy observation of an m-bit variable a i decreases approximately exponentially with t (see the illustration of this assertion in Appendix A). Consequently, a template attack exploiting d > d + 1 shares, but needing only εm bits of information, ε ∈ [0 : 1), for γ of them (and exactly m bits for the remaining d -γ) with γ > d -d -1,7 may be more efficient than a classical template attack exploiting m bits of information on exactly d+1 shares. Of course, this efficiency gain cannot be true for any amount of noise since it is known that the complexity of a side-channel attack increases exponentially with the number of exploited shares, the basis of the exponentiation being the noise standard deviation σ (assumed to be the same for all the shares). Figure 6 illustrates our argumentation in the particular case (n, d) = (5, 2), d = 4, γ = 3 and ε = 0.5. It corresponds to the attack results reported in Fig. 1.

(5,2) Shamir's Secret Sharing

a in GF(2 m ) a 1 a 2 a 3 a 4 a 5
Coding theory Side Channel Theory

Classical approach

Mapping from GF(2 m ) to GF(2 m/2 ) 2 a 1 a 2 a 3 a 4 a 5 a 1 a 2 a 3 a 4 a 5

𝑎1 1 𝑎1 2 𝑎2 1 𝑎2 2 𝑎3 1 𝑎3 2 𝑎4 1 𝑎4 2 𝑎5 1 𝑎5 2
Need 𝟑𝒎 bits to rebuild a Need 𝟓 𝒎 𝟐 𝑏𝑖𝑡𝑠 to rebuild a Estimate 𝑃𝑟(𝐿 𝑎1), 𝐿(𝑎2), 𝐿(𝑎3) 𝑎) Estimate 𝑃𝑟(𝐿 𝑎1), 𝐿(𝑎2), 𝐿(𝑎3), 𝐿(𝑎5) 𝑎) a 1 a 2 a3 a 4 a 5

𝐿(•)

a 1 a 2 a 3 a 4 a 5

𝐿(•)

Classical approach

Mapping from GF(2 m ) to GF(2 m/2 ) 2 )

𝑎1 1 𝑎1 2 𝑎2 1 𝑎2 2 𝑎3 1 𝑎3 2 𝑎4 1 𝑎4 2 𝑎5 1 𝑎5 2
Fig. 2. Side-channel and linear repairing codes for Shamir's sharing.

In the second part of the paper, we exhibit a positive impact of the existence of linear exact repairing schemes for SSS by proposing an improvement of the state-of-the-art multiplication algorithms dedicated to this sharing. Our new proposal continues the line of studies made e.g. in [START_REF] Goubin | Protecting aes with shamir's secret sharing scheme[END_REF] and [START_REF] Castagnos | High-order masking by using coding theory and its application to AES[END_REF] on the original scheme by Ben-Or et al. [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF], and improves them when the multiplication operation in GF(2 m ) is at least two times smaller than in the sub-fields.

Preliminaries on Shamir's Secret Sharing and Coding Theory

In this section we introduce the concepts involved in the subsequent sections. In particular, we recall the principles of linear exact repair schemes and we specify the recent constructions introduced in [START_REF] Guruswami | Repairing reed-solomon codes[END_REF] to fit with our context (where we are focussing on the problem of secret reconstruction and not on the problem of decoding which is more general).

Shamir's Secret Sharing and Reed-Solomon Codes

In a seminal paper [START_REF] Shamir | How to Share a Secret[END_REF], Shamir proposed to split a secret a ∈ GF(2 m ) into n shares such that no tuple of shares with cardinality lower than a so-called threshold d < n depends on a. Shamir's protocol consists in associating a with a random polynomial P a (X) . = a + d i=1 u i X i of degree lower than d and with constant term a = P a (0) (this essentially amount to randomly generate the d coefficients u i in GF(2 m )). Then, the polynomial P a (X) is evaluated in n distinct public non-zero elements α 1 , . . . , α n in GF(2 m ) to define a so-called (n, d)-sharing (a 1 , a 2 , • • • , a n ) of a such that a i = P a (α i ). To re-construct a from its sharing, polynomial interpolation is first applied to re-construct the polynomial from a subset U of at least d + 1 among its n evaluations a i and then, it is evaluated in 0. Actually, using Lagrange's interpolation formula, the two steps can be combined in a single one thanks to the equality:

a = ai∈U a i × β i , (4)
where the (public) constants β i are defined as

β i = n k=1,k =i α k α i + α k . (5)
The set U is sometimes called reconstruction set. The vector composed of the n weights β i is denoted by β and ( 4) is called reconstruction.

As initially observed by McEliece and Sarwate in [START_REF] Mceliece | On sharing secrets and reed-solomon codes[END_REF], the sharing of a described above may be viewed as an encoding with a Reed-Solomon linear code. Generally speaking, a linear code C of length n and dimension k over a finite field

K is a k-dimensional subspace of K n . It is denoted by C[n, k].
A Reed-Solomon code is a particular linear code whose definition is recalled hereafter. Definition 1 (Reed-Solomon Code). The Reed-Solomon code RS(S, d+1) ⊆ K n of dimension d + 1 over a finite field K and with evaluation subset S = {α 0 , α 1 , α 2 , • • • , α n } of K is the subspace: RS(S, d + 1) = {(P (α 0 ), P (α 1 ), . . . , P (α n )); P (X) ∈ K[X] and deg(P ) d} .

Reed-Solomon codes are Maximum Distance Separable (MDS) codes, which means that any tuple of d + 1 symbols (that is, any tuple of d + 1 evaluations of a polynomial P (X) ∈ RS(S, d + 1)) can be used to recover the entire codeword (that is, P (X) itself). In terms of RS codes, the sharing of a variable a with SSS is an encoding with a Reed-Solomon code RS({0, α 1 , . . . , α n }, d + 1):

(a, a 1 , • • • , a n ) = (a, u 1 , • • • , u d ) × G , (6)
with G the matrix (α j i ) i∈[0;n],j∈[0;d] and α 0 . = 0 (with the convention 0 0 = 1). After denoting by G i the ith column of G, it may indeed be checked that we have:

a i = P a (α i ) = a + d j=1 u j α j i = (a, u 1 , . . . , u d ) • G i .
The reconstruction of a then simply corresponds to a simple decoding which will be the matrix representation of Lagrange's interpolation recalled in [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF]. For simplicity we will sometimes say that a = (a, a 1 , • • • , a n ) is a sharing of a, which will mean that a can be recovered from (a part of) {a 1 , • • • , a n }.

Linear Exact Repairing Codes

The reconstruction of a by Lagrange's Interpolation (4) requires the full knowledge of at least d + 1 shares a i ∈ GF(2 m ), that is (d + 1) × m bits. The theory of Linear Exact Repairing Schemes aims at defining methods allowing for the reconstruction of a ∈ GF(2 m ) from its sharing with strictly (much) less than (d + 1) × m bits. This goal is achieved by exploiting partial information on strictly more than d + 1 shares. If the total amount of partial information is strictly less than RB Lagrange , the goal is achieved. During the last few years, there have been several publications tackling this issue in the context of RS codes (see e.g. [START_REF] Dimakis | A survey on network codes for distributed storage[END_REF][START_REF] Shanmugam | A repair framework for scalar MDS codes[END_REF]), or more generally, for MDS codes (see e.g. [START_REF] Cadambe | Optimal repair of MDS codes in distributed storage via subspace interference alignment[END_REF][START_REF] Dimakis | Network coding distributed storage systems[END_REF][START_REF] Suh | On the existence of optimal exact-repair MDS codes for distributed storage[END_REF]). Before presenting the recent constructions of LERS for RS codes introduced in [START_REF] Guruswami | Repairing reed-solomon codes[END_REF], let us recall hereafter the definition of a field trace.

Definition 2 (Field Trace). Let q be a power of a prime integer and let t be a strictly positive integer, then the field trace tr K/F from K = GF(q t ) to F = GF(q) is defined for every β ∈ K by

tr K/F (β) = β + β q + β q 2 + • • • + β q t-1 .
In a linear repairing scheme, the reconstruction of the shared value a ∈ K involves, for each share a i , zero or more elements of F ⊆ K of the form tr K/F (γ i,j a i ) for some well-chosen field elements γ i,j ∈ K. A linear exact repair scheme can then be described by the field elements γ i,j used for all the shares a i , along with a (linear) repair algorithm. Minimizing the number of these elements is the main goal when designing an LERS. It is called the Repair Bandwith RB LERS of the LERS and it is formally defined as the maximum number of sub-symbols in F which must be exploited to recover P a (α ) when α ranges over S. It may be observed that, in the context of SSS, we only need an efficient reconstruction scheme for α = 0 (i.e. for a = P a (0)) and thus, we will use RB LERS as an upper bound and will denote by LERS 0 a repairing scheme trying to minimize RB LERS only for α = 0.

In the following section, we give, for the specific case of Reed-Solomon codes applied for secret sharing, the main outlines of the method recently proposed in [START_REF] Guruswami | Repairing reed-solomon codes[END_REF] to construct the field elements γ i,j described previously together with an efficient repair algorithm. The presentation is completed in Appendix D by a detailed presentation of an example given in [START_REF] Guruswami | Repairing reed-solomon codes[END_REF] and by Sage scripts that we made available at [START_REF] Anonymous | Sage Scripts for Examples of Exact Linear Repairing Codes[END_REF].

Explicit Constructions for Reed-Solomon Codes

In the specific case of Reed-Solomon codes RS({0, α 1 , . . . , α n }, d+1) defined over K = GF(2 m ), [START_REF] Guruswami | Repairing reed-solomon codes[END_REF]Theorem 4] implies that the construction of a LERS 0 over F = GF(2 m t ) for some field extension t is equivalent to find a set {p 1 , . . . , p t } of t polynomials of degree n -d -1 in K such that:

dim F ({p 1 (0), . . . , p t (0)}) = t (7)
and

RB LERS0 n i=1 dim F ({p 1 (α i ), . . . , p t (α i )}) .
Once such a family of polynomials is found with RB LERS0 < t(d + 1) (otherwise the bandwidth is worst than the trivial one), coefficients ζ j and µ i,j with j ∈ [1..t] are built so that

ζ j = p j (0) (8)
and

µ i,j = p j (α i ) × β i , (9)
where the β i are defined as in [START_REF] Cadambe | Optimal repair of MDS codes in distributed storage via subspace interference alignment[END_REF].

Then, the last step of the LERS 0 design consists in computing, for any α i , a basis B i = {γ i,j } j for the smallest vector space over F containing {µ i,j ; j ∈ [1; t]} as a subset (by definition the size of the basis is at most t, and actually is frequently strictly lower, which is a core observation to understand the soundness of the decoding with an LERS scheme). With the bases in hand, the reconstruction of a = P a (0) for any polynomial P a of degree lower than d consists in the following steps where we recall that each a i equals P a (α i ) by SSS construction:

-for any i ∈ [1..n]; compute 8 the values tr K/F (µ i,j a i ), with j ∈ [1..t], from the elements in {tr K/F (γ i,j a i ); γ i,j ∈ B i }, -for any j ∈ [1; t]; evaluate tr K/F (ζ j a) = n i=1 tr K/F (µ i,j a i ) (10)
and, eventually, recover the shared value thanks to the following equality

a = t j=1 ν j tr K/F (ζ j a) , (11)
where {ν 1 , . . . , ν t } is the dual basis of {ζ 1 , . . . , ζ t }.

It may be observed that Equations ( 10) and ( 11) together give the following alternative to Lagrange reconstruction Formula (4)

a = n i=1 t j=1 ν j tr K/F (µ i,j a i ) = n i=1 t j=1 ν j tr K/F (p j (α i )β i a i ) . ( 12
)
The core observation in [START_REF] Guruswami | Repairing reed-solomon codes[END_REF] is that, surprisingly, for some a i (and hence some P a (α i )) the size of all the elements required to build the set {tr K/F (µ α,j a i ); j ∈ [1; t]} may be smaller than the size of a i . This implies that the total number of bits required to recover P (0) from ( 10) and [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF], which actually equals RB LERS × m t , may be smaller than (d+1)m (corresponding to a direct polynomial interpolation).

In the following section we argue that the existence of efficient LERS for Reed-Solomon codes impacts the security evaluation of Shamir's sharing in the context of side-channel analyses. In particular, we argue that the choice of the public points plays a non-negligible role in the security provided by this sharing and we exhibit (through several simulations and experiments) contexts in which state-of-the-art attacks are suboptimal.

Side-Channel Analysis of Shamir's Secret Sharing Scheme

We first recall that a scheme is said to be d th -order secure if any set of at most d intermediate results during the processing reveals no information about a secret (sensitive) value. When the (n, d)-sharing of Shamir is involved to secure the implementation, the recovery of the shared values requires the knowledge of at least d + 1 shares among the n = 2d + 1 possible ones. As already discussed in the introduction, all previous works on SSS assume that the most efficient way to attack such a sharing of a is to exploit exactly d + 1 shares. If the shared value is assumed to belong to GF(2 m ), then this implies that the literature implicitly assumes that, as for Boolean sharing/masking, (d + 1) × m bits are necessary and sufficient to rebuild a. This section aims at coming back on this assumption and, more precisely, at answering the two following questions while having in mind the recent results on LERS described in previous section:

Question 1. For a given pair of sharing parameters (n, d) and a given representation of the base field GF(2 m ), does any combination of d+1 shares (a i ) i∈I,#I=d+1

give the same amount of information an a. Actually, an attacker is spoilt for the choice of the combination of d + 1 shares to use among the several available ones. Our goal here is to check if all d + 1 combination of shares leak the same amount of information under the same fixed noise level for each share. The result of this investigation may bring some insights on the choice of the optimal (d+1)-combination of shares, if any exits, that an attacker should consider when performing his attack.

Question 2. For a given pair of sharing parameters (n, d) and a given representation of the base field GF(2 m ), is there some (d + 2)-combination of shares whose observation leads to a better attack than any other one with exactly d + 1 shares? We shall see that the answer to this question depends on the amount of noise in each observation (actually we will argue that the answer is positive if and only if the signal-to-noise ratio is lower than some bound).

Preliminar Observations from Simulated Leakage Measurements

To address the questions above, we performed profiling attacks against simulated traces corresponding to the manipulation of the shares of a (n, d)-sharing for n = 5 and d = 2. This allows us to study the impact of the noise on the attacks efficiency, and to draw some conclusions. Our analyses are confirmed, in Section 3.3, by practical attack experiments against real acquisitions captured on the ChipWhisperer platform [START_REF] O'flynn | Chipwhisperer: An open-source platform for hardware embedded security research[END_REF].

Target Implementation. It is assumed that the adversary has access to a noisy observation of the five elements a 1 , . . . , a 5 of the (5, 2)-sharing of a secret value a ∈ GF(2 8 ).

Leakage Model. The observation i of each share a i is assumed to be the sum of two mutually independent parts: a deterministic function f of the share a i and a Gaussian noise N i such that i = f (a i ) + N i . To generate our traces, we considered two types of deterministic functions: the Hamming weight (which has been argued to be a sound approximation for many device technologies -see e.g. [START_REF] Mangard | Power Analysis Attacks -Revealing the Secrets of Smartcards[END_REF]) and the identity. The noises N i are assumed to be mutually independent, to have zero mean and to have the same fixed variance σ 2 (the rationale behind this assumption is to have the same noise level for each share). It may be checked that, under our assumptions, the distribution of i | a i has a normal distribution with mean f (a i ) and variance σ 2 . Such a normal distribution is hereafter denoted by

x ∈ R → φ f (ai),σ 2 (x).
Attack Strategy. To evaluate the security of the (5, 2)-sharing, we performed a higher-order template attack following the procedure described in [START_REF] Lomné | How to estimate the success rate of higher-order side-channel attacks[END_REF]. The idea behind this choice was to directly address the most powerful adversary who follows a maximum likelihood approach without modelling error. Let j ∈ R 5 denotes the j th observation of the 5-tuple ( 1 , . . . , 5 ) and let 1,j , ..., 5,j denote its coordinates, then for any hypothesis â ∈ GF (2 8 ) on a, the likelihood distinguisher 9 is defined as d ML (â) = N j=1 p â( j ), where N denotes the number of observations and where p â denotes the probability density function (pdf) of the leakage which, under the Gaussian assumption, satisfies:

p â( j ) = 1 256 4 a2∈GF(2 8 ) • • • a5∈GF(2 8 ) 5 i=1 φ f (ai),σ 2 ( i,j ) , (13)
where we recall that we have 4)). In [START_REF] Lomné | How to estimate the success rate of higher-order side-channel attacks[END_REF] authors have demonstrated that, for a d th -order Boolean masking, (13) can be expressed as a higher-order convolution product whose evaluation complexity is O(d). To continue using this efficient procedure in the context of Shamir's secret sharing, we propose hereafter to apply the simple linear change of variables a i → a i . = a i × βi β1 and â → â

a 1 = 1 β1 (â + 5 i=2 a i × β i ) (see (
. = â× 1 β1 so that a 1 = â ⊕ 5 i=2 a i , which
enables us to apply the convolution trick to compute the score d ML (â × β -1 1 ).

Attack Results. For each possible combination of 3 shares, the left-hand side of Fig. 3 plots the number of traces (in y-axis) required to achieve a success rate of 100% according to an increasing noise standard deviation (in x-axis). We stress the fact that for each value of the standard deviation, the success rate has been averaged over 1.000 tries. It may first be observed that the different triplet of shares that have been tested leak differently on the shared variable a (even if all the shares have been affected by the same amount of noise). For instance, for a noise standard deviation comprised in [0.5, 1.5], the number of traces needed to always succeed in recovering the shared variable is around two times when exploiting the triplet of shares (a 1 , a 2 , a 3 ) instead of (a 2 , a 3 , a 4 ). To confirm this observation, we changed the public points α i used for the sharing (see [START_REF] Balasch | Inner Product Masking Revisited[END_REF]). Results are plotted in the right-hand side of Fig. 3, where our previous observation is confirmed but for a different ordering of the triplets of shares. This simulations led us to answer positively to Question 1: some combination of d+1 shares bring to the adversary more information than others in Shamir's sharing.

To address Question 2, we performed another set of simulations to check if there exist an SNR range for which exploiting the leakage on 4 shares is more efficient than any other combination of 3 shares. In Fig. 4, we show a comparison between the template attack results when considering all combination of 3 and 4 shares. The experiences are repeated 1.000 times for each combination of shares. For a specific interval of noise standard deviation (between 0.3 and 0.5), it may be observed that some combinations of 4 shares outperform all other combination of 3 shares. The same observation stands when changing the set of public points as described in the right-hand side of Fig. 4. We sum-up hereafter our main observations:

the shares are not leaking the same amount of leakage despite the fact that the same quantity of noise has been added to them, exploiting the leakage of 4 shares is more efficient than any other attack strategy based on 3 shares for some values of the noise standard deviation. when comparing the two sides of Fig. 4, it may be observed that the optimal combination of 4 shares to recover the secret value changes with respect to the used public points. So, the amount of information leaked by the shares depends on the set of public points used to share the secret value.

Impact on the Existence of an LERS on the Efficiency of SCA against SSS

The existence of efficient LERS for some choices of public points and of field representations (aka the existence of reconstruction formulae as in ( 10)- [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF] or in [START_REF] Huang | Secret Sharing with Optimal Decoding and Repair Bandwidth[END_REF]) explains the observations made for previous experiments. Indeed, it implies that the statistical dependency between the value a and the tuple of shares involved in the attack can be revealed by extracting partial information on some of the shares, which renders the exploitation of the noisy observations of these shares more tolerant to error. Even if the reconstructions formulae are not directly involved in the template attacks we have performed, their existence is implicitly used by the maximum likelihood distinguisher to capture the dependency. From the designer point of view, a direct consequence is that the set of Number of queries to achieve 100% of success rate (0, 1, 2) (0, 1, 3) (0, 1, 4) (0, 2, 3) (0, 2, 4) (0, 3, 4) (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4) (0, 1, 2, 3) (0, 1, 2, 4) (0, 1, 3, 4) (0, 2, 3, 4) (1, 2, 3, 4) Fig. 4. Evolution of the number of queries (in y-axis) to achieve a success rate of 100% according to an increasing noise standard deviation (x-axis) for public points {5, 237, 175, 221, 198} ⊆ GF(2 8 ) (on the left-hand side) and {169, 63, 106, 49, 112} (on the left-hand side).

public points and the field representation must be carefully chosen to make the construction of efficient LERS as difficult as possible. In Section 4, we show a constructive impact of LERS by proposing enhancements of the secure multiplication of data shared with SSS.

Attack results on Real Device

In order to confirm our observations on simulated traces, we conducted some practical attacks on the ChipWhisperer platform. The experimental setup is described in what follows.

We have implemented a (5, 2) secret sharing on an 8-bit AVR microprocessor atxmega128d3 and we acquired power-consumption traces thanks to the ChipWhisperer-Lite (CW1173) basic board. For the leakage profiling step, we have collected 128.000 traces to estimate the mean and the variance for each share. These statistical estimation results have first been used to check that the shares observations have roughly the same variance (i.e. are impacted by the same level of noise) which is in-line with our simulation setup. However, the standard deviation of the noise of the acquired traces was actually outside the suitable area where the combinations of 4 shares outperform the combination of 3 shares. The estimated noise standard deviation is about 0.7. Thus, we have acquired 15.000 traces for the attack phase and we have performed the template attack by exploiting the leakage of all combinations of 4 and 3 shares. As expected, the attack results have demonstrated that any combinations of 4 shares is efficient with respect to the measures noise standard deviation. To decrease the noise level and to fit the suitable interval, we filtered the acquired traces to reach a noise standard deviation value equal to 0.5. Finally, we re-performed our higher-order template attack. The success rate of the attack for each combination of share is shown in Fig. 5. Success Rate (0, 1, 3, 4) (0, 1, 2) (0, 1, 3) (0, 1, 4) (0, 2, 3) (0, 2, 4) (0, 3, 4) (1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4) Fig. 5. Success rate of the template attack according to an increasing number of traces.

Fig. 5 shows that exploiting the leakage of the shares (0, 1, 3, 4) is more suitable in terms of attack efficiency than exploiting any other tuple of 3 shares.

Impact of LERs to Improve Existing Multiplication Schemes for SSS

In this section we describe a constructive impact of the existence of an LERS by showing that they can be used to improve the multiplication of data shared by SSS.

Basics on the Multiplication for SSS

To define a d th -order masking scheme for a block cipher implementation where each intermediate result is split with Shamir's technique, one must specify a secure method for the processing of field multiplications over GF(2 m ). Most of (if not all) existing protocols start from a multiplication scheme introduced by Ben-Or et al. in the context of the Multi-Party Computation Theory [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF]. For this protocol to work, the number of shares n per variable must be at least 2d + 1 and for n = 2d + 1, it is proved that it satisfies a security property encompassing the d th -order SCA security [START_REF] Prouff | Higher-order glitches free implementation of the aes using secure multi-party computation protocols[END_REF]. We give hereafter the adaptation of [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF] in the SCA context as proposed in [START_REF] Prouff | Higher-order glitches free implementation of the aes using secure multi-party computation protocols[END_REF][START_REF] Roche | Higher-order glitch free implementation of the AES using secure multi-party computation protocols -extended version[END_REF] ti ← βi × Pu(αi) × Pv(αi) 3: end for Compute a sharing (Qi(αj)) j≤n for every ti 4: for i = 1 to n do 5:

for k = 1 to d do 6:

ω k ← rand(GF(2 n )) 7:
end for 8:

for j = 1 to n do 9:

Qi(αj) ← ti + d k=1 ω k × α k j 10: end for 11: end for Compute the share wi = Pw(αi) for w = u × v 12: for i = 1 to n do 13:

wi ← n j=1 Qj(αi) 14: end for The completeness of Algorithm 1 is discussed in [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF]. Its d th -order SCA security can be straightforwardly deduced from the proof given by Ben-Or et al. in [START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF] in the secure multi-party computation context. Eventually, for n = 2d+1 (which is the parameter choice which optimizes the security/efficiency overhead), the complexity of Algorithm 1 in terms of additions and multiplications is O(d 3 ). ). The code C is the so-called generalized Reed-Solomon code defined with respect to the evaluation points S and the multiplier vector β by:

C = {(β i P (α i )) i∈[1;n] ; P (X) ∈ GF(2 m )[X] and deg(P (X) n} . ( 14
)
On one hand, the tuple (t

1 , • • • , t n ) in Algorithm 1 forms a sharing of w = u × v such that c = (w, t 1 , • • • , t n ) ∈ C
and a reconstruction algorithm is simply given by the sum of the t i (this is a direct consequence of Lagrange's interpolation formula). On the other hand, loop 4-11 (over indices i and j) and loop 12-14 may be viewed as a transcoding transcoding C →C that securely transforms the sharing c ∈ C of w into a new sharing c in C. Eventually, it can be observed that the algorithm completeness holds because the constant term of the polynomial P w (X) . = n j=1 Q j (X) associated to the codeword C has constant term the n-reconstruction i β i ×t i . Algorithm 1 involves n multiplications and the evaluations of n degree-d polynomials in n points (which makes n 2 × d multiplications for a naive implementation and O(n log 2 n) multiplications using FFT-based polynomial division11 [START_REF] Coron | On the use of shamir's secret sharing against side-channel analysis[END_REF]). In [START_REF] Castagnos | High-order masking by using coding theory and its application to AES[END_REF], the authors observe that the addition of a random sharing c 0 .

= (0, c 0 1 , . . . , c 0 n ) ∈ C of 0 to c makes it possible to reduce the number of polynomials to evaluate from n to d + 1, without compromising the security at order d. The core idea is to precede the transcoding by a shortening of the sharing ĉ .

= (t 1 + β 1 • c 0 1 , • • • , t n + β n • c 0 n ) into ( n-d i=1 ĉi , ĉn-d+1 , • • • , ĉn ).
The security essentially holds because the sharing c 0 may correspond to any polynomial of degree lower than or equal to n, which implies that at least n -1 shares/evaluations are required to recover all the information about the sharing (see [START_REF] Castagnos | High-order masking by using coding theory and its application to AES[END_REF] for more details about the proof). Eventually, a last improvement can be obtained by applying to loop 12-14 (in Algorithm 1) an idea initially proposed in [START_REF] Goubin | Protecting aes with shamir's secret sharing scheme[END_REF]: since polynomials Q i (X) (and hence also P w (X)) all have degree d, the evaluation can be made in only d + 1 points (e.g. the d + 1 first public points α 1 , . . . , α d+1 ) and Algorithm 1 can output only the d + 1 shares w 1 , . . . , w d+1 . When needed, the remaining evaluations/shares w d+2 , . . . , w n can then be deduced by applying the following formula where the Lagrange's coefficients β j,i . = d+1 k =j,k=1 (α i -α k )/(α j -α k ) have been pre-computed and can be public 12 :

w d+1+i = d+1 j=1 w j × β j,i . (15)
This enables to exchange the (d + 1)dn evaluations (needed for the transcoding) to d(d + 1) 2 + (n -d -1)(d + 1). Let c u and c v respectively denote the tuples of shares corresponding to the codewords in C associated to u and v. Bellow, we sum-up the resulting secure multiplication scheme and the cost in terms of field multiplications in the case n = 2d + 1 (which is the optimal choice):

-[build the Sharing in C ] c = c u • c v • β (4d + 2 mult.) -[add the random sharing of 0 in C ] ĉ = c + c 0 • β (2d + 1 mult.) -[reduce dimension of the sharing] ĉ-= n-d i=1 ĉi , ĉn-d+1 , • • • , ĉn -[transcode ĉ-into a sharing in C] (d(d + 1) 2 + d(d + 1) mult.)
Performances. Clearly, the complexity of the multiplication is driven by the cost of the transcoding step which is in O(d 3 ) while the other steps are in O(d). For efficiency reasons, e.g. when the cost of the field multiplication is significantly lower in GF(2 m/2 ) than in GF(2 m ), it is preferred to work on the vector space GF(2 m/2 ) 2 instead of GF(2 m ). This is for instance the case in software for m = 8, since the field multiplication can be tabulated in GF [START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF] (and hence corresponds to a table access) but not in GF(256) (and hence often takes several dozens of CPU cycles -see e.g. [15] -). Working in GF(2 m/2 ) 2 instead of GF(2 m ) essentially amounts to represent ĉ-∈ GF(2 m ) d+1 as the pair

(ĉ - 1 , ĉ- 2 ) ∈ GF(2 m/2 ) d+1 × GF(2 m/2
) d+1 and to process the transcoding over GF(2 m/2 ) 2 both for ĉ-1 and ĉ-2 . This leads to exchange d(d + 1) 2 + d(d + 1) multiplications over GF(2 m ) for the following number of multiplications over GF(2 m/2 ):

Comp soa = 2d(d + 1) 2 + 2d(d + 1) .

Before describing how the existence of efficient LERS can be used to improve the state of the art multiplication algorithms for SSS, we specify hereafter the description made in Section 2.3 for the particular case involved in the description of our improvement proposal.

LERS For Reed-Solomon Codes in the Particular case t = 2

Let us focus on a Reed-Solomon code RS(S, d + 1) defined over K = GF(2 m ) and with S . = {0, α 1 , . . . , α n }. When t = 2, the basis B i of {µ i,1 , µ i,2 } defined in Section 2.3 for every i ∈ [1 . . . n] is either of cardinal 2 if µ i,1 and µ i,2 are linearly independent over F, or of cardinal 1 otherwise. In the first case, its two elements γ i,1 and γ i,2 may simply be set to µ i,1 and µ i,2 respectively. In the second case, we fix γ i,2 = 0 and the single basis element γ i,1 can for instance be defined such that:

γ i,1 =    µ i,1 if µ i,1 = 0, µ i,2 if µ i,1 = 0 and µ i,1 = 0, 0 otherwise.
The set of pairs (i, j) such that γ i,j has been assigned a non-zero value by the latter process is denoted by R and is called reconstruction set. By construction, we have R ⊆ {(i, j); α i ∈ S\{0}, j ∈ [1; 2]} and #R = RB LERS . Moreover, we denote by R 1 (resp. R 2 ) the subset of R containing the pairs (i, j) with j = 1 (resp j = 2). They form a partition of R and they are the same for any polynomial P of degree lower than or equal to d.

Eventually, for the case t = 2, we may conclude that for any polynomial P a of degree lower than or equal to d: Fact 1 (memory) To reconstruct a = P a (0) thanks to the Formula (12), it is sufficient to store the elements w i,j = tr K/F (γ i,j a i ) ∈ F with the (i, j) ∈ R. Hence, the overall scheme leads to replace the storage of the (d + 1) × m bits needed for the classical reconstruction with Lagrange Interpolation, by the storage of RB LERS × m 2 bits.

Fact 2 (processing) The reconstruction of a = P a (0) can always be done thanks to the following formula which is deduced from ( 9)-( 10):

a = ν 1 (i,1)∈R1 w i,1 + ν 2 (i,2)∈R2 w i,2 + (i,1)∈R1,#Bi=1 µ i,2 µ i,1 w i,1 . (16)
where {ν 1 , ν 2 } is the dual basis of {ζ 1 , ζ 2 }. Note that the coefficients µ i,2 /µ i,1 belong to F by construction. Fact 3 (security) The elements w i,j form a sharing of a and this sharing still satisfies the d th -order security property since, by construction, at least d + 1 shares are necessary to rebuild w.

Remark 1. For the new multiplication protocol exhibited in Section 4.4, we will prefer to use the following equation which is equivalent to [START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF]:

P (0) = ν 1 (i,1)∈R1 τ i × w i,1 tr K/F (ζ1w) + ν 2 (i,2)∈R2 w i,2 tr K/F (ζ2w) . ( 17
)
where τ i is constant with respect to P (X) and is defined such that:

τ i = 1 + ν2µi,2 ν1µi,1 if #B i = 1 1 otherwise. (18)
In [START_REF] Guruswami | Repairing reed-solomon codes[END_REF]Theorem 10] it is proved that for Reed-Solomon codes RS(S, d + 1) with #S = n and t = 2, there always exits an LERS with the bandwidth RB LERS being at most 3n/2n (which leads to a reconstruction of a with strictly less than 3n 4 m bits instead of (d + 1)m).

As an illustration of the concepts presented in this section, the example given in [START_REF] Guruswami | Repairing reed-solomon codes[END_REF] is detailed in Appendix D. It corresponds to the case of a code RS(S, 9+1) over the field K GF(256) with S = {g 0 , . . . , g 13 } where g is a primitive element of K. This example is completed by Sage scripts available at [START_REF] Anonymous | Sage Scripts for Examples of Exact Linear Repairing Codes[END_REF].

Improvement From LERS

To simplify the presentation, we apply our proposal in the particular case where the linear exact repairing codes recalled in Sec. 2.3 are applied for K = GF(2 m ), F = GF(2 m/2 ) and t = 2. For this parameters, we assume that an LERS exists for a Reed-Solomon code with evaluation set S = {α 1 , . . . , α n } and order 2d + 1 (this implies that n is greater than n = 2d+1). We assume that the latter LERS has repair bandwidth RB LERS < 2(2d + 1) and we denote by (ζ 1 , ζ 2 } the basis defined in [START_REF] Coron | On the use of shamir's secret sharing against side-channel analysis[END_REF] and by (ν 1 , ν 2 ) the corresponding dual basis over GF(2 m/2 ). For our description we assume that coefficients µ αi,j and γ i,j , and also the reconstruction set R, have been defined as specified in Sec. 4.3. Eventually, to properly define the evaluation of polynomials in GF(2 m 2 )[X] in the public elements α i ∈ S, we shall assume that they belong to F = GF(2 m/2 ) and, when needed, that their m 2 -bit representation is (artificially) extended to an m-bit representation (in GF(2 m )) by simply left-padding with 0 (e.g. the element 3 ∈ GF(2 m 2 ) becomes 03 in GF(2 m )). 13For our new proposal, we assume that the two values u and v whose multiplication has to be secured are respectively represented by the (n , d + 1)polynomial sharings (P u (α i )) αi∈S and (P v (α i )) αi∈S (we hence have u = P u (0) and v = P v (0)). Note that contrary to the classical SSS sharing, we need n to be strictly greater than 2d + 1 in order to get an efficient LERS.

Sharing of w = uv in C . As in Algorithm 1, we start by building a sharing (w 1 , . . . , w n ) of w = uv in the product code C by simply defining w i , for i ∈ [1; n ], such that:

w i = P u (α i ) × P v (α i ) . = P w (α i )
By construction, it may be observed that C is a sub-code of the Reed-Solomon code with parameters [n + 1, 2d + 1]; this implies that w can be rebuild from RB LERS coordinates w i,j ∈ GF(2 m/2 ) of the w i 's, by applying Formula ( 16) (instead of 2d + 1 elements w i ∈ GF(2 m ) when classical Lagrange's interpolation is applied). From the coefficients γ i,j associated to our LERS for the code RS(n + 1, 2d+1) (hence with (i, j) in the reconstruction set R), we deduce the new shares w i,j ∈ GF(2 m/2 ) from the the shares w i ∈ GF(2 m ) by processing14 :

w i,j = tr K/F (γ i,j w i ) . (19)
We recall that R 1 and R 2 respectively denote {(i, j) ∈ R, j = 1} and {(i, j) ∈ R, j = 2}. The set {w i,j ; (i, j) ∈ R 1 } may hence be viewed as a sharing of the first coordinate of P (0) in GF(2 m/2 ) 2 (aka tr K/F (ζ 1 P (0)) with the notations in Section 2.3), while the set {w i,j ; (i, j) ∈ R 2 } is the sharing of the second coordinate (aka tr K/F (ζ 2 P (0))). By construction, the sharing of w defined by evaluating [START_REF] Ishai | Circuits: Securing Hardware against Probing Attacks[END_REF] for (i, j) ∈ R has size RB LERS . Now, applying the same ideas as described in previous section:

Reduce dimension of the sharings. We generate two independent Boolean sharings of 0 in GF(2 m/2 ) that we respectively denote by {c 0 i,j ; (i, j) ∈ R 1 } and {c 0 i,j ; (i, j) ∈ R 2 }. Then, we build the two following new sharings of tr K/F (ζ 1 P (0)) and tr K/F (ζ 2 P (0)) respectively:

ĉ1 = {ĉ 1,1 , ĉ1,2 , . . . , ĉ1,#R1 } = {τ i × w i,j + c 0 i,j ; (i, j) ∈ R 1 }
and ĉ2 = {ĉ 2,1 , ĉ2,2 , . . . , ĉ2,#R2 } = {w i,j + c 0 i,j ; (i, j) ∈ R 2 } , where τ i is defined as in [START_REF] Huang | Secret Sharing with Optimal Decoding and Repair Bandwidth[END_REF]. Then, if #R 1 and/or #R 2 are greater than d + 1, we shorten the sharings as described in previous section. For j = 1, 2, we get:

ĉ- j = #Rj -d i=1 ĉj,i , ĉj,#Rj-d+1 , • • • , ĉj,#Rj . Transcodings in C over GF(2 m
2 ). Eventually, we conclude the processing as in previous section by transcoding ĉ-1 and ĉ-2 into two new sharings in the Reed-Solomon code with parameters [n + 1, 2d + 1] over GF(2 m/2 ) which themselves form a sharing of w in the Reed-Solomon code with parameters [n + 1, 2d + 1] over GF(2 m ) (with basis (ν 1 , ν 2 )).

Completeness. By construction, it may be checked that we have:

i ĉ- 1,i = #R1-d i=1 ĉ1,i + ĉ1,#R1-d+1 + • • • + ĉ1,#R1 (20)
= (i,j)∈R1 τ i × w i,j + (i,j)∈R1 c 0 i,j = tr K/F (ζ 1 w) , (21)
which comes at a direct consequence of ( 17) and the fact that the c 0 i,j forms a Boolean sharing of 0. Since the same holds for the sharing ĉ-2 , we deduce that the input of the first (resp. second) transcoding is a sharing of the first (resp. second) coordinate of w in GF(2 m 2 ). If one denote by P w,1 (X) (resp. P w,2 (X)) the random degree-d polynomial in GF(2 m 2 ) corresponding to the sharing at input of the first (resp. second) transcoding, then it may be checked that P w (X) . = ν 1 P w,1 (X) + ν 2 P w,1 (X) is a random degree-d polynomial over GF(2 m ) and (d + 1, d + 1)-SSS sharing is given by its evaluation P w (X)(α i ) = ν 1 P w,1 (α i ) + ν 2 P w,2 (α i ) in the public elements α i ∈ S.

Extension to t > 2. The construction can be directly generalized to any extension order t = 2 k (i.e. under the assumption that there exists an efficient LERS for the Reed-Solomon code C = RS(S, 2d + 1) with K = GF(2 m ) and F = GF(2 m/t )). This will lead to the construction of t sharings ĉ-1 , ĉ-2 , . . . , ĉt instead of 2, and to t transcodings in the code C over GF(2 m/t ). The corresponding reconstruction sets are denoted by R 1 , R 2 , . . . , R t .

Efficiency. A core observation here is that the size of each sharing ĉj is min(#R j , d + 1). Hence, the complexity of the transcoding step is:

Comp new = d(d + 1) t j=1 min(#R j , d + 1) + t(n -d -1)(d + 1)
which is, in the least favourable case, comparable to the complexity Comp soa of the state-of-the-art schemes and which is better, for almost all choices of d and n, if one of the R j has cardinality lower than d + 1.

Conclusion

In this paper, we highlighted an important difference between Boolean and Shamir's sharings which implies that, for some signal-to-noise ratio, it is more advantageous for the adversary to observe strictly more than d+1 shares. We argue that this difference is related to the existence of so-called exact linear repairing codes, which themselves come with reconstruction formulae that need (much) less information (counted in bits) than Lagrange's interpolation. In particular, this result implies that, contrary to what was believed, the choice of the public points in Shamir's sharing has an impact on the countermeasure strength. In the second part of the paper, we then exhibited a positive impact of the existence of linear exact repairing schemes; we indeed proposed to use them to improve the state-of-the-art multiplication algorithms dedicated to Shamir's sharing. We think that this work opens promising avenues on the design of LERS taking into account the constraints of the SCA contexts.

A Information Extraction from Noisy Observations of 8-bit Values

In the following figure, we plot the number of queries to achieve a success rate of 100% when performing a template attack which tries to recover, from noisy observations, either the full value of the manipulated data a or its 4 least significant bits.

B Bounds for the Bandwidth of Exact Linear Repairing codes

When t is sufficiently large, RB LERS is bounded below by (t × RL)/(RL -d),

where RL denotes the repair locality and corresponds to the maximum number of α i ∈ S that are required to recover P (α ) whatever α ∈ S. For very large values of t, several schemes have been proposed for which the lower bound is achieved (see e.g. [START_REF] Cadambe | Optimal repair of MDS codes in distributed storage via subspace interference alignment[END_REF][START_REF] Suh | On the existence of optimal exact-repair MDS codes for distributed storage[END_REF]). When t is small, it is clear that the lower bound above cannot be achieved since we have RB LERS d + t. It must however be observed that this latter bound is much better than the naive one t × (d + 1). Explicit constructions have recently been proposed that lead to good RB LERS in practice (e.g. [START_REF] Guruswami | Repairing reed-solomon codes[END_REF], [START_REF] Huang | Secret Sharing with Optimal Decoding and Repair Bandwidth[END_REF] and [39]).

C Formal Definition of an Exact Linear Repairing Schemes

Definition 3 (Linear Exact Repair Scheme). Let S = {α 1 , α 2 , • • • , α n } be an evaluation subset of a finite field K and let RS(S, d + 1) ⊆ K n be the corresponding Reed-Solomon code. A linear exact repair scheme for this code over a subfield F of K is composed of the following steps:

for each α ∈ S, and for each α ∈ S\{α }, a set of queries Q α (α ) ⊆ K, for each α ∈ S and any polynomial P (X) ∈ K[X] with degree lower than d + 1, a linear reconstruction algorithm that computes

P (α ) = t i=1 λ i × ν i ,
for coefficients λ i ∈ F and a basis {ν 1 , ν 2 , • • • , ν t } for K over F, so that the coefficients λ i are F-linear combinations of the queries in α∈S/{α } {tr K/F (γ × P (α); γ ∈ Q α (α )} .

The repair bandwith RB LERS of an LERS is the maximum number of subsymbols which must be returned by the nodes to recover P (α ). It is defined by:

RB LERS = max α ∈S α∈S/{α } #Q α (α ) .

D Example

Let us consider the example given in [START_REF] Guruswami | Repairing reed-solomon codes[END_REF]. Let latter example considers the code RS(S, 9 + 1) over the field K GF(256) with S = {g 0 , . . . , g 13 } where g is a primitive element of K (which implies n = 14 and d = 9 for the notations used in previous section). It is assumed that α = g 0 = 1 and α i = g i for i ∈ [1; 13] and t = 2 (hence F GF( 16)). To build the family of two polynomials satisfying [START_REF] Chari | A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards[END_REF] and ( 8), [START_REF] Guruswami | Repairing reed-solomon codes[END_REF] proposes a pretty restrictive (but yet effective) approach: they randomly generate two polynomials p 1 (X) and p 2 (X) of degree n -d -1 = 3 with roots 16 in S and test (1) if the space spanned by p 1 (α ) and p 2 (α ) has full rank and (2) if the sum of the dimensions of the spaces spanned by the pairs (p 1 (α i ), p 2 (α i )) when i ranges in [1; 13] is lower than some threshold judged as good (at least smaller than 20 in order to get a reconstruction better than the simple interpolation which needs 10 bytes, or identically 20 nibbles, corresponding to 10 polynomial evaluations). In the paper, the authors fix the threshold to 16.

For this example, we have ζ 1 = p 1 (1) and ζ 2 = p 2 (1). For the field representation GF(256) GF(2)[X]/(X 8 + X 4 + X 3 + X 2 + 1), we found that the 3-degree polynomials p 1 (X) = X 3 + 38X 2 + 200X + 29 and p 2 (X) = X 3 + 105X 2 + 213X + 58 enables to achieve our fixed threshold (16). 10) and [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF], it is possible to reconstruct P (1) for any polynomial P (X) of degree lower than or equal to 9 with only 64 bits of information 17 on the 14 shares P (α i ) (instead of the 80 bits required by using Lagrange's Interpolation Formula). Indeed, from the table above and Equations [START_REF] Dimakis | A survey on network codes for distributed storage[END_REF] and [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF], we get that:

the 4-bit field elements tr K/F (µ αi,j P (α)) corresponding to µ αi,j = 0 do not need to be stored, for all pairs of 4-bit field elements µ αi,1 and µ αi,2 which are linearly dependent over GF [START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF] (these are the elements with light-gray background), it is only necessary to save a single trace evaluation, say tr K/F (µ α,1 P (α)), and the second one can be deduced by simply multiplying it by the value τ i ∈ GF [START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF] such that τ i µ αi,1 = µ αi,2 (which necessarily exists since they linearly dependent over GF [START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF]).

With the notations defined in Section 4.3, a reconstruction set for the code RS(S, 9 + 1) is given by: R 1 = {(3, 1), (4, 1), (6, 1), (7, 1), (8, 1), (9, 1), (10, 1), (11, 1), (12, 1), (13, 1)} and R 2 = {(1, 2), (2, 2), (5, 2), (8, 2), (11, 2), (13, 2)} 16 The intuition is that having polynomials such that at least p1(αi) = 0 or p2(αi) = 0 for some i ∈ [1; 13] automatically reduces the dimension of the corresponding set {pj(αi) : j ∈ [1; 2]}, which helps to satisfy (8). 17 always the same whatever P (X) and R = R ∪ R 2 .

Eventually, we may conclude that for any polynomial P (X) of degree lower than or equal to 9: Fact 1 (memory) To reconstruct w = P (1), it is sufficient to store the 4-bit elements w i,j = tr K/F (γ i,j P (α)) with (i, j) ∈ R. Since #R = RB LERS = 16, the overall scheme leads to save 10 * 4 = 40 bits for the storage of the sharing of P (1) in RS(S, 9 + 1) (and the set R is the same for any P (X)). Fact 2 (processing) The reconstruction of P (1) can always be done by evaluating ( 16) at the cost of RB LERS = 16 additions over GF [START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF] and 2 + 4 multiplications by a constant scalar over GF [START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF].

Fig. 1 .

 1 Fig. 1. For a (5, 2)-SSS sharing and different choice of tuples of shares, the number of observations required to achieve a 100% success rate (in y-axis) versus the noise standard deviation of the noise (in x-axis).

Fig. 3 .

 3 Fig.3. Evolution of the number of queries (y-axis) to achieve a success rate of 100% according to an increasing noise standard deviation (in x-axis) for public points {125, 246, 119, 104, 150} ⊆ GF(2 8 ) (on the left-hand side) and {86, 23, 115, 107, 189} (on the left-hand side).

10 . 1

 101 Algorithm Secure Multiplication For Shamir's Secret Sharing Input: two integers n and d such that n ≥ 2d + 1, the (n, d)-sharings (ui)i = (Pu(αi))i and (vi)i = (Pv(αi))i of u and v respectively. The n distinct points αi, the interpolation values β = (β1, • • • , βn). Output: the (n, d)-sharing (wi)i . = (Pw(αi))i of w = u × v. Compute a Boolean n-sharing (t1, • • • , tn) of w 1: for i = 1 to n do 2:

4. 2

 2 Link with Error Correcting Codes Theory and State-Of-The-Art Improvements Algorithm 1 may be rewritten in terms of coding theory, essentially because, as recalled in Section 2, an (n, d)-sharing with Shamir's scheme exactly corresponds to an encoding by a Reed-Solomon code with parameters [n + 1, d + 1] [25]. Let • denote the Hadamard product between vectors (aka the componentwise product) and let C denote the latter code and let C denote the code built from C by taking all the vectors β • c • c with c, c ∈ C and β = (1, β 1 , • • • , β n ) (recall that the β i are interpolation values specified for the Reed-Solomon code with parameters [n+1, d+1]

  The observations have been simulated to satisfy = f (a) + b where b is drawn from the normal distribution N (0, σ 2 ) with σ ∈[START_REF] Anonymous | Sage Scripts for Examples of Exact Linear Repairing Codes[END_REF][START_REF] Cadambe | Optimal repair of MDS codes in distributed storage via subspace interference alignment[END_REF] and where the deterministic part f (a) has been defined such that f (a) . = 8 i=1 α i a[i] with the α i generated at random from the normal distribution N (1, 0.2 2 ) and kept fixed for all the attacks 15 .

  µ αi,1 0 0 76 68 0 238 57 157 220 80 115 204 131 µ αi,2 248 21 120 0 127 0 211 56 0 171 33 147 45 By using the coefficients ζ 1 , ζ 2 and (µ αi,j ) i∈[1;13],j∈[1;2] as specified in Formula (

  7-9, 2016, Revised Selected Papers, volume 10146 of Lecture Notes in Computer Science, pages 174-191. Springer, 2016. 39. M. Ye and A. Barg. Explicit constructions of MDS array codes and RS codes with optimal repair bandwidth. In IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, July 10-15, 2016, pages 1202-1206. IEEE, 2016.

  Fig.6. Number of queries (in y-axis) to achieve a success rate of 100% for the extraction of either 8 bits or 4 bits or 2 bits with respect to the noise standard deviation (in x-axis).

	Number of queries to achieve 100% of success rate	10 3 10 4	Template attack targeting 8 bits among 8 Template attack targeting 4 bits among 8 Template attack targeting 2 bits among 8

This work has been done when the author was working at Safran Identity and Security. † This work has been done when the author was working at Safran Identity and Security.

It may be checked that, by construction and due to the d th -order security, every I ∈ Ra has size at least d + 1.

For the secure multiplication proposed in[START_REF] Ishai | Circuits: Securing Hardware against Probing Attacks[END_REF], recent works have shown that attacks exploiting the n 2 shares ai × bj of a × b may lead to more efficient attacks than targeting only the n shares of a or b, when n is greater than O(1/t) and t is an upper bound of the mutual information for each share[START_REF] Battistello | Horizontal side-channel attacks and countermeasures on the ISW masking scheme[END_REF][START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF]. Our work completes these works by exploiting algebraic dependencies in Shamir's sharing.

Recent works (see e.g.[START_REF] Battistello | Horizontal side-channel attacks and countermeasures on the ISW masking scheme[END_REF] and[START_REF] Grosso | Masking Proofs are Tight (and How to Exploit it in Security Evaluations[END_REF]) have indeed argued that several manipulations of the same share could be used to improve the efficiency of attacks exploiting only

d + 1 shares to defeat a d-secure masking. But they cannot explain the important difference observed in Fig.1.

This condition implies that the amount of information (counted in bits) needed to rebuild the shared value is bounded above by (d -γ)m + γεm which is lower than (d + 1)m.

Since (γj,j)j forms a basis, this can be done by only processing linear combinations of the tr K/F (γi,jai).

In practice, one often makes use of the equivalent (averaged) log-likelihood distinguisher.

The protocol is an improved version of the protocol originally proposed by Ben-Or et al.[START_REF] Ben-Or | Completeness theorems for noncryptographic fault-tolerant distributed computation[END_REF], due to Gennaro et al. in[START_REF] Gennaro | Simplified vss and fact-track multiparty computations with applications to threshold cryptography[END_REF].

The constant terms being important in this complexity the naive approach is always more efficient for practical choices of n and d.

As argued in[START_REF] Renner | Protection des algorithmes cryptographiques embarqués[END_REF], the processing of (15) can be simply made securely at order d without requiring additional multiplications.

This introduces the restriction #S < 2 m 2 -1 which has no important impact in practice.

Note that this processing is for free if the field representation of GF(2 m ) has been carefully chosen.

The idea was to simulate a leakage close to the Hamming weight model but with the weights associated to the bit-coordinates of a differing with an average amplitude in [-0.2, +0.2].