Jamie Sikora

André Chailloux

Iordanis Kerenidis

Strong connections between quantum encodings, non-locality and quantum cryptography

Encoding information in quantum systems can offer surprising advantages but at the same time there are limitations that arise from the fact that measuring an observable may disturb the state of the quantum system. In our work, we provide an in-depth analysis of a simple question: What happens when we perform two measurements sequentially on the same quantum system? This question touches upon some fundamental properties of quantum mechanics, namely the uncertainty principle and the complementarity of quantum measurements. Our results have interesting consequences, for example they can provide a simple proof of the optimal quantum strategy in the famous Clauser-Horne-Shimony-Holt game. Moreover, we show that the way information is encoded in quantum systems can provide a different perspective in understanding other fundamental aspects of quantum information, like non-locality and quantum cryptography. We prove some strong equivalences between these notions and provide a number of applications in all areas.

Quantum information studies how information is encoded in quantum systems and how it can be observed through measurements. On one hand, the exponential number of amplitudes that describe the state of a quantum system can be used in order to encode a vast amount of classical information into the state of a quantum system. Hence, we can use quantum information to resolve many distributed tasks much more efficiently than with classical information [START_REF] Raz | Proc. 31st Annual ACM Symposium on Theory of Computing[END_REF][START_REF] Buhrman | [END_REF][3]. On the other hand, quantum information does not always offer advantages, since every time an observer measures a quantum system its state may collapse and information may become irretrievable. For example, Holevo's theorem [4], asserts that one quantum bit can be used to transmit only one bit of classical information and no more.

The intricate interplay between encoding information in quantum systems and measurement interference is at the heart of some fundamental results in quantum information, from Bell inequalities [5] to quantum key distribution [START_REF] Bennett | IEEE Inter. Conf. on Computer Systems and Signal Processing[END_REF]. Our goal is to deepen our understanding of the connections between quantum encodings, non-locality, and quantum cryptography and provide new insight on the power and limitations of quantum information, by looking at it through these various lenses.

This paper links three seemingly unrelated concepts in quantum information (encodings, non-local games, and cryptographic primitives) via properties of sequential non-commuting measurements. The technical part of this paper examines quantum encodings and bounds the success of sequentially measuring an encoding of two bits (or strings) to learn their XOR. We then show how these bounds can be used to study not only encodings, but non-local games and cryptographic tasks as well. The conceptual part of this paper discusses how the applications we consider are all equivalent in some sense. When viewing each as extracting information from a quantum encoding, we are able to preserve the three notions: [START_REF] Raz | Proc. 31st Annual ACM Symposium on Theory of Computing[END_REF] hiding the XOR in the encoding, [START_REF] Buhrman | [END_REF] providing perfect security in the cryptographic task, and (3) satisfying the non-signaling principle in the non-local game.

In addition to providing philosophical insights towards each of these quantum tasks, we combine the technical and conceptual tools in this paper to give applications in all areas.

QUANTUM ENCODINGS AND COMPLEMENTARITY OF MEASUREMENTS

One of the fundamental postulates of quantum mechanics is Heisenberg's uncertainty principle which shows that it is impossible to perfectly ascertain the momentum and position of a particle. More precisely, entropic uncertainty relations provide explicit bounds on the entropy of the outcome distributions of the different measurements. For example, if we consider two measurements in the computational and Hadamard bases, then no matter the state of the quantum system, there is always some entropy in at least one of the outcome distributions, hence the measurement outcomes cannot be perfectly predicted simultaneously.

Another important notion, which is more closely related to quantum encodings, is the complementarity of quantum measurements. Complementarity analyzes what happens to the outcome distributions of measurements when performed sequentially on the same system. We say that two measurements are perfectly complementary, if after having performed the first measurement, no more information can be extracted by performing the second measurement on the post-measured state. This is, for example, the case with a Hadamard and a computational basis measurement, or any measurement after a complete projective measurement. On the other hand, they are non-complementary if after measuring with one, the outcome distribution of the second is unaffected.

We make the connection of complementarity and quantum encodings clearer by considering the following scenario: Let us consider two different observables that take binary values x 0 ∈ {0, 1} and x 1 ∈ {0, 1} according to some known distribution. Assume that given one copy of a quantum system (of any dimension) in state ρ x0,x1 , i.e., a quantum encoding of the bits x 0 , x 1 , there exists a quantum measurement, i.e., a decoding procedure, that correctly measures x 0 with probability p 0 and a different measurement that correctly measures x 1 with probability p 1 . We would like to analyze these probabilities and more specifically the average decoding probability (p 0 + p 1 )/2.

Uncertainty relations show that when the measurements are "incompatible" the average decoding probability cannot be too large. For example, for the computational and Hadamard bases one can show this probability is always at most cos 2 (π/8). There are many cases where we do not know the different measurement operators, only the probabilities they succeed. For example, one may not know the measurements used in an implicit strategy in a cryptographic protocol or quantum non-local game where the only defining property of the strategy is the success probability. Could we still provide some interesting bound on the average decoding probability that would hold independent of the measurement operators, possibly by relating it to some other property of the quantum encoding?

We provide such bounds by relating the average decoding probability to the decoding probability of some other function f (x 0 , x 1 ) of the bits. Classically, it is straightforward to relate the probability of decoding f (x 0 , x 1 ) to the probabilities of decoding each bit x i ; in the quantum world, this task is delicate. Suppose we want to compute the XOR of the two bits (i.e., compute whether the two bits have the same value or not), and for this we perform the measurement for each bit x i in sequence. Once the first bit is decoded, the post-measured state is an eigenstate of the first operator, hence the probability of then correctly decoding the second bit may have changed.

Much of the previous literature about measuring the post-measured state concerns ideas surrounding Heisenburg's uncertainty principle (see, for example, [START_REF] Ozawa | [END_REF] and the references therein). In a setting more related to this paper, post-measurement information has been used for state discrimination [8,9]. This is useful for cryptography in the bounded-storage model [10] and the noisy-storage model [11,12].

LEARNING RELATIONS

Our first contribution is an analysis of the process of sequentially performing two measurements on the same quantum state: Let |ψ be a pure state and {C, 1 -C}, {D, 1 -D} be two projective measurements such that cos 2 (α) := C|ψ , where C and D correspond to correctly measuring. Through geometric arguments, we bound the probability that both measurements succeed (give the correct guess) or both fail (give the incorrect guess) as: In the language of quantum encodings, we can use [START_REF] Raz | Proc. 31st Annual ACM Symposium on Theory of Computing[END_REF] to provide the following learning relation for bits, and extend it to strings. (The proof of Equation (1) and Theorem 1, below, can be found in the appendix.) Theorem 1. For any quantum encoding of bits x 0 and x 1 , Pr[learning x 0 ⊕ x 1 ] ≥ (2c -1) 2 , where we define c := 1 2 Pr[learning

cos 2 (α -β) ≥ CD|ψ 2 2 + (1 -C)(1 -D)|ψ
x 0 ] + 1 2 Pr[learning x 1 ]. For x 0 , x 1 ∈ {0, 1} n , if c ≥ 1/2, then we have Pr[learning x 0 ⊕ x 1 ] ≥ Pr[learning (x 0 , x 1 )] ≥ c(2c -1) 2 .
The probability of learning a bit (or a bit string) is the maximum over all quantum measurements of correctly measuring the bit (or bit string). Theorem 1 shows that, independent of the measurements, the average probability of correctly measuring two observables cannot be very large unless at the same time the probability of correctly measuring both or none of the observables is large as well. A similar result has been obtained for a restricted class of encodings, those based on hyperbits [13].

We can now define a measure of complementarity Γ, as the difference between the probability of decoding the XOR of the two bits and the probability had the measurements been non-complementary. By Equation [START_REF] Raz | Proc. 31st Annual ACM Symposium on Theory of Computing[END_REF],

|Γ| = CD|ψ 2 2 + (1 -C)(1 -D)|ψ 2 2 -C|ψ 2 2 D|ψ 2 2 -(1 -C)|ψ 2 2 (1 -D)|ψ 2 2 ≤ 1 2 sin(2β) sin(2α). ( 2
)
Note Γ is zero for non-complementary measurements and our bound can be saturated, e.g., when C = D we have Γ = 1 2 sin(2β) sin(2α), and for C = 1 -D we have Γ = -1 2 sin(2β) sin(2α).

THE CLAUSER-HORNE-SHIMONY-HOLT GAME AS A QUANTUM ENCODING

Non-locality is a fundamental property of quantum information. Here, two space-like separated parties, Alice and Bob, initially share some resource and do not communicate further. We study the joint probability distributions of measurement outcomes that can arise when Alice and Bob perform measurements locally. Bell inequalities provide bounds on the possible distributions when the initial resource is classical and we are interested in the maximum violation when Alice and Bob share quantum entanglement.

One can describe Bell inequalities as games between Alice and Bob. For example, in the Clauser-Horne-Shimony-Holt (CHSH) game [14], Alice receives a random x ∈ {0, 1} and outputs a ∈ {0, 1} and Bob receives a random y ∈ {0, 1} and outputs b ∈ {0, 1}. The quantum value of the game, ω * (CHSH), is the maximum probability that a ⊕ b = yx over all initial states and all measurement operators. There is a quantum strategy to win this game with probability cos 2 (π/8); moreover, Tsirelson's bound shows this value is optimal [15].

Recently, non-locality has been studied from the point of view of information. The goal is to understand quantum mechanics through information principles: for example, why is there a quantum strategy for the CHSH game with probability exactly cos 2 (π/8) and not more? Information causality, one such postulate about information transmission, asserts that any theory that abides to it must comply with Tsirelson's bound for the CHSH game [16]. To make the connection between non-locality and quantum information more clear, let us see how we can recast the CHSH game as a quantum encoding: Once Alice receives x and measures a, Bob's post-measurement state can be seen as an encoding of a and x. When y = 0, Bob needs to output a and when y = 1, he needs to output a ⊕ x. Hence, we can write the value as

ω * (CHSH) = 1 2 (Pr[Bob learns a]+Pr[Bob learns a⊕x]
). Note that the non-signaling condition of CHSH implies the probability of Bob guessing Alice's input x is 1/2 or equivalently the probability of learning the XOR of a and a ⊕ x is 1/2 (in this case, we say that the encoding "hides" the XOR). With this perspective, Theo-rem 1 provides an alternative proof of Tsirelson's bound, since solving the inequality (2ω * (CHSH)-1) 2 ≤ 1/2 gives ω * (CHSH) ≤ cos 2 (π/8).

LEARNING RELATIONS AND OBLIVIOUS TRANSFER

Another area where quantum information has had great impact is cryptography. The properties of quantum information, for example, the uncertainty principle, enable secure key distribution protocols [START_REF] Bennett | IEEE Inter. Conf. on Computer Systems and Signal Processing[END_REF], however, when the two parties do not trust each other, there are only partial advantages. For example, quantum protocols for coin flipping or bit commitment can only restrict cheating to a probability of 1/ √ 2 or 0.739, respectively [START_REF] Kitaev | Presentation at the 6th workshop on quantum information processing (QIP 2003)[END_REF][START_REF] Chailloux | Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science[END_REF][START_REF] Chailloux | Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science[END_REF]. We wish to relate the ability to perform cryptographic primitives to non-locality and quantum encodings.

We look at oblivious transfer (OT), defined below.

Definition 1 (Imperfect oblivious transfer). A quantum oblivious transfer protocol with correctness p, denoted here as OT p , is an interactive protocol with no inputs, between Alice and Bob such that:

• Alice outputs two independent, uniformly random bits (z 0 , z 1 ) or Abort and Bob outputs uniformly random bit b and another bit w or Abort. • If Alice and Bob are honest, w = z b with probability p. • Alice and Bob can abort only if cheating is detected.

• If p = 1 we say the protocol is perfect.

Ideally at the end of the protocol, Bob should only learn the value of z b and Alice should remain oblivious to which bit Bob learned [START_REF] Wiesner | [END_REF]21].

We also examine quantum oblivious string transfer protocols with correctness p, denoted here as OT n p which is defined analogously to an imperfect oblivious transfer protocol except z 0 and z 1 are n-bit strings.

Oblivious transfer is the most important task in providing security between distrustful parties, since any complex operation can be rendered secure using secure oblivious transfer [START_REF] Kilian | STOC '88: Proceedings of the 20th ACM symposium on Theory of computing[END_REF]. Using Theorem 1, we prove a series of new results for oblivious transfer [START_REF]We use a non-composable definition of security which makes our impossibility results even stronger[END_REF]. First, we extend the oblivious transfer bounds in [START_REF] Chailloux | [END_REF] to oblivious string transfer, and show that in any protocol, either Alice can learn Bob's index or Bob can learn both of Alice's strings with probability at least 58.52% (proof in the appendix). Second, we consider the case when cheating Bob wants to learn the XOR of Alice's bits. Note that most definitions enforce that Bob gets no information about Alice's other bit (instead of the XOR of her bits). Classically, the two definitions are equivalent [START_REF] Damgård | Advances in Cryptology -CRYPTO 2006[END_REF]. Quantumly, we use the XOR definition that relates directly to the CHSH game (discussed in the next section). Proof. We show how to use oblivious transfer to construct a coin flipping protocol. A quantum coin flipping protocol with correctness p, denoted CF p , is an interactive protocol with no inputs, between Alice and Bob such that:

• The protocol is aborted with probability 1-p when Alice and Bob are honest. • If the protocol is not aborted, then they both output a randomly generated bit c.

We say that the coin flipping protocol has cheating probabilities A CF and B CF where

• A CF := max c∈{0,1} Pr[Bob accepts outcome c], • B CF := max c∈{0,1} Pr[Alice accepts outcome c].
The coin flipping protocol is as follows.

1. Alice and Bob perform the OT p protocol so they have outputs (z 0 , z 1 ) and (b, w) respectively. We see that when Alice and Bob are honest, Alice aborts in this protocol with probability 1 -p, since p is the probability that Bob receives the correct bit in the OT p protocol. If Alice does not abort, the outcome of the coin flipping protocol is random.

Cheating Alice: Let A OT denote the probability Alice can learn b in the OT p protocol (without Bob aborting) and let A CF denote the probability Alice can force honest Bob to accept a desired outcome in the coin flipping protocol. It is straightforward to see that A OT = A CF .

Cheating Bob: Let B OT denote the probability Bob can learn z 0 ⊕ z 1 in the OT p protocol (without Alice aborting) and let B CF denote the probability Bob can force honest Alice to accept a desired outcome in the coin flipping protocol. Using our XOR learning relation for bits, and an analysis similar to the one in [START_REF] Chailloux | [END_REF] and Pr[Bob learns z 0 ⊕ z 1 ] = 1 2 , we have p ≤ cos 2 (π/8), which shows that the secure oblivious transfer protocol in [START_REF] Bennett | Advances in Cryptology CRYPTO 1982[END_REF] is optimal. Last, by relating oblivious transfer and bit commitment protocols [START_REF] Chailloux | [END_REF], we prove that in any OT protocol with p = 1, Alice can learn Bob's index or Bob can learn the XOR of Alice's bits with probability at least 59.9% (proof in the appendix).

EQUIVALENCES BETWEEN CHSH-TYPE GAMES, SECURE OBLIVIOUS TRANSFER AND QUANTUM ENCODINGS

So far, we have used Theorem 1 to provide results about the CHSH game and oblivious transfer. We now show that these applications are deeply connected and can be extended to more intricate non-local games and oblivious transfer variants. Such non-local games are important since knowing their Bell inequality violations brings us that much closer to understanding the true power of quantum entanglement and the hope of characterizing it as a resource via the right information postulate(s).

We now consider secure OT n p protocols where Alice can obtain no information about Bob's index b (without him aborting) and Bob can obtain no information about z 0 ⊕ z 1 (without Alice aborting).

We also consider the following generalization of the CHSH game. The value of the game, ω * (CHSH n ), is the maximum probability which Alice and Bob can win.

The CHSH game is the special case when n = 1 (we omit the subscript 1 in this case).

A relationship between learning probabilities and quantum games is pointed out in [START_REF] Oppenheim | [END_REF], where they show that in any physical theory, the amount of non-locality and uncertainty of the theory are tightly linked. In our equivalences, we strengthen the quantum connection by conserving the notions of security / non-signaling / hidden XOR and we deal with the interactivity of oblivious transfer protocols. Theorem 3. The following four statements are equivalent for every n ∈ N:

1. There is a quantum encoding of x 0 , x 1 ∈ {0, 1} n that hides the XOR and (3. =⇒ 1.). Let |Ω AB be the final joint state of the OT n p protocol for honest Alice and Bob. Suppose Alice measures to learn (z 0 , z 1 ) which are distributed uniformly. Let ρ z0,z1 be Bob's post-measured state. Then, {ρ z0,z1 : z 0 , z 1 } and π being the uniform distribution satisfy the hidden XOR condition, since Alice does not abort (both parties are honest), and the protocol is secure. We now describe a procedure to decode each z c , for c ∈ {0, 1}, with probability p.

We may assume Bob measures his part of the state |Ω AB (instead of decoding ρ z0,z1 ) since it does not matter if Alice measures before or after Bob. Suppose |Ω b AB is the post-measured joint state when Bob partially measures |Ω AB to obtain his index b. Since Bob will not abort and the protocol is secure, we know b is hidden from Alice. Again, by Uhlmann's theorem, Bob can transform |Ω 0 to |Ω 1 and vice versa via a unitary acting on B. Hence Bob can measure |Ω AB to learn b, collapse the state to |Ω b and then apply the unitary mapping |Ω b to |Ω c . He then uses the decoding procedure of the OT n p protocol to learn z c with probability p.

(4. =⇒ 1.). Let |Ω AB be the state that Alice and Bob share before receiving x and y in a CHSH n game strategy that succeeds with probability p. Suppose Alice measures to learn a (conditioned on x). Let ρ a,x be Bob's post-measured state which occurs with probability π a,x . We define the necessary states and probabilities by relabelling a → x 0 and x ⊕ a → x 1 . Then, Bob has no information about x 0 ⊕ x 1 = a ⊕ (x ⊕ a) = x from non-signaling, and the average decoding probability for x 0 and x 1 is p.

Since trivially (2. =⇒ 3.), we conclude the proof of Theorem 3.

We can also prove an equivalence between quantum encodings of n pairs of bits that hide the XOR of each pair and the n-fold repetitions of CHSH and OT, defined below.

Definition 3 (n-fold repetition of oblivious transfer).

A quantum n-fold repetition of oblivious transfer protocol with correctness p, denoted here as OT ⊗n p , with cheating probabilities A OT ⊗n and B OT ⊗n , is defined analogously to an imperfect oblivious string transfer protocol except b is an n-bit string (so z b takes values from each of Alice's strings according to b). We say an OT ⊗n p protocol is secure if Alice can gain no information about the string b (without Bob aborting) and if Bob can gain no information about the string z 0 ⊕ z 1 (without Alice aborting).

Definition 4 (n-fold repetition of CHSH

a i ⊕ b i = x i • y i , for all i ∈ {1, . . . , n}.
The value of the game, ω * (CHSH ⊗n ), is the maximum probability which Alice and Bob can win. Theorem 4. The following four statements are equivalent for every n ∈ N:

1. There is an encoding of x 0 , x 1 ∈ {0, 1} n that hides the XOR and

1 2 n c∈{0,1} n Pr[learn x c ] = p, where x c ∈ {0, 1} n is defined as (x c ) i := (x ci ) i . 2.
There is a secure, non-interactive OT ⊗n p protocol. 3. There is a secure OT ⊗n p protocol. 4. There is a strategy for winning the game CHSH ⊗n with probability p.

APPLICATIONS OF EQUIVALENCES

Our equivalences provide new ways of looking at nonlocal games and cryptographic primitives, through the lens of quantum encodings. Apart from conceptual tools, we can use the equivalences to prove a number of results in all areas.

First, using Theorem 1 for encodings that hide the XOR with n = 1 and Theorem 4, we have an alternative proof of the optimality of Tsirelson's bound, ω * (CHSH) ≤ cos 2 (π/8).

Using Theorem 1 for encodings that hide the XOR and Theorem 3, we provide a new upper bound on the value of

CHSH n , ω * (CHSH n ) ≤ 1 2 + 1 √ 2 n+1 . It is an interesting
open question to compute the exact quantum value of this game, especially since it is a simple generalization of the CHSH game for which the quantum value is not known to be implied by information causality.

There is an alternative way of upper bounding the value of this game numerically using semidefinite programming (SDP) [27]. We provide below the values for small n. We see that the SDP relaxation gives a tighter bound than ours for n ≤ 3, but the numerical results suggest that our bound outperforms the SDP bound for larger values of n.

Value n = 1 n = 2 n = 3 n = 4 n = 5
Lower Bound 0.750 0.625 0.562 0.531 0.515 Conjectured Value 0.853 0.750 0.676 0.625 0.588 SDP Relaxation 0.853 0.780 0.743 0.725 0.716

Our Bound 1 0.853 0.750 0.676 0.625

The table above also includes our conjectured optimal value, below.

Conjecture 1. ∀n ∈ N, ω * (CHSH n ) = 1 2 + 1 2 1 2 n . Similarly, for secure OT n p , we have p ≤ 1 2 + 1 √ 2 n+1
(again, for n = 1, we can get the optimal p ≤ cos 2 (π/8)). Second, by Theorem 4 and the perfect parallel repetition property of CHSH [28], i.e., the fact that if Alice and Bob play n games in parallel, the probability of winning all games is exactly (cos 2 (π/8)) n , we have for any secure OT ⊗n p protocol, p ≤ (cos 2 (π/8)) n , which is attainable by using n secure OT cos 2 (π/8) protocols. In other words, secure oblivious transfer admits perfect parallel repetition.

ROBUSTNESS OF EQUIVALENCES

Similar results can also be obtained in the case of a weighted average decoding probability defined as q Pr[learning x 0 ] + (1 -q) Pr[learning x 1 ], for q ∈ [0, 1]. When the XOR is hidden, and q = 1/2, Theorem 1 shows that the above quantity is at most cos 2 (π/8). A similar analysis shows that for any q, this value is at most

1 2 + 1 2 q 2 + (1 -q) 2 . ( 3
)
It is also interesting to see that such a learning relation is related to the CHSH game where Bob gets input y = 0 with probability q and input y = 1 with probability 1 -q while Alice still gets a uniform input. Using a similar method than in Theorem 3, we can show that this game has value at most 1 2 + 1 2 q 2 + (1 -q) 2 . We can show the optimality of this bound using the semidefinite programming characterization of the bias of XOR games in [28].

DISCUSSION

We have provided new relations between the average decoding probability of two bits (or strings) and the probability of decoding their XOR. Moreover, we have shown precise equivalences between quantum encodings, CHSHtype games, and oblivious transfer, showing that nonlocality and cryptographic primitives are often two facets of the same quantum mechanical behaviour. Last, we used our equivalences to prove new results for non-local games and oblivious transfer protocols.

As we have mentioned, it is an open question to compute the quantum value of the game CHSH n through semidefinite programming or by proving stronger learning relations. Moreover, we would like to find an information postulate that implies that any theory that abides to it must win this game with exactly the quantum value (similar to information causality for the case of CHSH).

(1 -C)(1 -D)|ψ 2 2 = sin 2 (β) (1 -C)|Y 2 2 = sin 2 (β) x 1 + x 2 Π C |Z 2 .
Notice that

1 = C|Z 2 2 + (I -C)|Z 2 2 = Π C |Z 2 2 + Π C |Z 2 2 .
We define

A := Π C |Z 2 2 = 1 -Π C |Z 2 2
. This yields

CD|ψ 2 2 + (1 -C)(1 -D)|ψ 2 2 = cos 2 (β) x 0 + x 2 Π C |Z 2 2
+ sin 2 (β)

x 1 + x 2 Π C |Z 2 2 = cos 2 (β) (x 0 + x 2 A) + sin 2 (β) (x 1 + x 2 (1 -A)) = cos 2 (β)x 0 + sin 2 (β) (x 1 + x 2 ) +A cos 2 (β)x 2 -sin 2 (β)x 2 = cos 2 (β)x 0 + sin 2 (β) (1 -x 0 ) +A cos 2 (β)x 2 -sin 2 (β)x 2 . (4)
Define A(ρ, σ) := arccos F (ρ, σ) to be the angle between two states ρ and σ, which is a metric (see p. 413 in [START_REF] Nielsen | Quantum computation and quantum information[END_REF]).

Since Y |Y = 0, we have

A(|Y , |X ) ≥ π/2 -A(|X , |Y ).
This implies that

x 0 = cos (arccos | Y |X |) ≤ cos (π/2 -arccos √ x 0 ) = sin (arccos √ x 0 ) = √ 1 -x 0 .
This yields x 0 ≤ 1 -x 0 . In addition, notice that ψ|Z = 0, which implies that

Z| (cos(β)|Y + sin(β)|Y ) = 0 ⇐⇒ cos 2 (β)| Z|Y | 2 = sin 2 (β)| Z|Y | 2 ⇐⇒ cos 2 (β)x 2 = sin 2 (β)x 2 .
This gives us the bound,

CD|ψ 2 2 + (1 -C)(1 -D)|ψ 2 2 ≥ x 0 . (5)
To conclude, we have arccos(

√ x 0 ) = A(|X , |Y ) ≤ A(|X , |ψ ) + A(|ψ , |Y ) ≤ α + β,
yielding x 0 ≥ cos 2 (α + β) which concludes the proof of the lower bound.

For the upper bound, we have x 0 ≤ 1 -x 0 and cos 2 (β)x 2 = sin 2 (β)x 2 , hence,

CD|ψ 2 2 + (1 -C)(1 -D)|ψ 2 2 ≤ 1 -x 0 , from (4). We now show 1 -x 0 ≤ cos 2 (β -α). Since x 0 = | Y |X |, we have arccos x 0 = A(|Y , |X ) ≤ A(|X , |ψ ) + A(|Y , |ψ ) = π/2 -(β -α). so x 0 ≥ cos(π/2 -(β -α)) = sin(β -α) implying 1 -x 0 ≤ cos 2 (β -α), as desired.
Proof of Theorem 1. The proof of the first statement in the theorem relies on the following decoding strategy: First, we apply the decoding procedure for learning the first bit and then we apply the second decoding procedure on the post-measurement state. The probability of decoding the XOR is the probability that both decoding procedures succeed (give correct guesses for each bit) or they both fail (give incorrect guesses for each bit).

We prove the theorem using the following (equivalent) setting. We suppose two parties, Alice and Bob, share a joint pure state |Ω AB such that Alice performs a projective measurement M = {M x0,x1 } x0,x1∈{0,1} on A to determine x 0 and x 1 and the post-measured state is Bob's encoding of x 0 and x 1 . Let p i be the maximum probability that Bob can learn bit x i , for i ∈ {0, 1}. We note that without loss of generality, Bob can perform a projective measurement to guess the value of x i with maximum probability [START_REF] Nielsen | Quantum computation and quantum information[END_REF]. Let P = {P 0 , P 1 } be Bob's projective measurement that allows him to guess x 0 with probability p 0 = cos 2 (α) ≥ 1 2 and Q = {Q 0 , Q 1 } be Bob's projective measurement that allows him to guess x 1 with probability p 1 = cos 2 (β) ≥ 1 2 (these measurements are on B only). Consider the following projections (on A ⊗ B):

C = x0,x1 M x0,x1 ⊗ P x0 and D = x0,x1 M x0,x1 ⊗ Q x1 .
C (resp. D) is the projection on the subspace where Bob guesses correctly x 0 (resp. x 1 ) after applying P (resp. Q). Consider the strategy where Bob applies the two measurements P and Q one after the other to learn (x 0 , x 1 ), from which he can calculate x 0 ⊕ x 1 . If both guesses are correct or if both guesses are incorrect then his guess for x 0 ⊕ x 1 is correct.

Let Bob perform the following projective measurement to learn both bits:

R = {R x0,x1 := Q x1 P x0 Q x1 } x0,x1∈{0,1} .
The measurement where Bob guesses both bits correctly when applying R is

E = x0,x1 M x0,x1 ⊗ R x0,x1 = DCD,
with outcome probability Ω|E|Ω = CD|Ω

||CD|Ω || 2 2 + ||(I -C)(I -D)|Ω || 2 2 ≥ cos 2 (α + β) by (1). Note that c := p 0 + p 1 2 = cos 2 (α) + cos 2 (β) 2 ≥ 1 2
and for such values of α, β, we have cos(α+β) ≥ cos 2 (α)+ cos 2 (β) -1. Therefore, Pr[Bob can learn x 0 ⊕ x 1 ] ≥ cos 2 (α + β) ≥ (2c -1) 2 .

For the second statement, ideally, we would like to extend our proof approach from bits to strings, but unfortunately this statement is not true anymore if x 0 and x 1 are strings. Instead, the analysis in [START_REF] Chailloux | [END_REF] can be generalized to strings to show Pr[learning (x 0 , x 1 )] ≥ cos 2 (α) + cos 2 (β) 2 cos 2 (α+β).

If c ≥ 1/2, then by the same reasoning as above, we have Pr[learning (x 0 , x 1 )] ≥ c(2c -1) 2 . The statement about the XOR follows directly from the above statement.

Proofs of the security bounds for oblivious transfer protocols

We now provide proofs of the lower bounds of 59.9% and 58.52% for any oblivious transfer and oblivious string transfer protocol, respectively, with p = 1, by relating them to bit commitment. A quantum bit commitment protocol, denoted BC, is an interactive protocol with no inputs, between Alice and Bob, with two phases:

• Commit phase: Bob chooses a random b and interacts with Alice to commit to b.

• Reveal phase: Alice and Bob interact to reveal b to Alice. • If the parties are honest, Alice accepts the value of b.

We say that the bit commitment protocol has cheating probabilities A BC and B BC where We present a bit commitment protocol based on oblivious string transfer [START_REF] Chailloux | [END_REF]. Let B OT n denote the probability Bob can learn z 0 ⊕ z 1 in the OT n 1 protocol without Alice aborting. Notice that Bob must send (c, z c ) if he wants to reveal c in the BC protocol. Therefore, by letting q be the probability the OT n p is not aborted by Alice using Bob's optimal bit commitment strategy, we have B BC = qc, where From Theorem 1, we know that Bob has a strategy to learn (z 0 , z 1 ) with probability,

• B BC := max    b∈{0,1}
B OT n ≥ qc(2c -1) 2 ,
noting that B BC ≥ 1/2 =⇒ c ≥ 1/2. We now use the lower bound for bit commitment [START_REF] Chailloux | Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science[END_REF], which states that there is a parameter t ∈ [0, 1] such that

B BC ≥ 1 -1 - 1 √ 2 t 2 and A BC ≥ 1 2 + t 2 .
The above bound yields the lower bound max{A OT n , B OT n } ≥ 0.5852, which is independent of n. If n = 1, we can use the stronger bound in Theorem 1 to get B OT ≥ q(2c -1) 2 , improving the lower bound to the desired value max{A OT , B OT } ≥ 0.599.

2 2 ≥

 22 FIG. 1: (Color online) Simple scenario for the lower bound in Equation (1): Two-outcome projective measurements on a pure state in two dimensions. By successive measurements, one can learn the XOR by learning both bits correctly or by learning both bits incorrectly. This occurs with probability cos 2 (α) cos 2 (α + β) + sin 2 (α) cos 2 (α + β) = cos 2 (α + β).

Theorem 2 .

 2 For any OT p protocol, we have p ≤ Pr[Alice learns b] Pr[Bob learns z 0 ⊕ z 1 ] + 1 .

2 .

 2 If no one aborted, then Alice sends randomly chosen d ∈ R {0, 1} to Bob. 3. Bob sends b and w to Alice. 4. If z b from Bob is inconsistent with Alice's bits then Alice aborts. Otherwise, they both output c = b ⊕ d.

Definition 2 (

 2 CHSH n game). The CHSH n game is a game between Alice and Bob where: • Alice and Bob are allowed to create and share an entangled state |ψ before the game starts. Once the game starts, there is no further communication between Alice and Bob. • Alice receives a random string x ∈ {0, 1} n and Bob receives a random bit y ∈ {0, 1}. • Alice outputs a ∈ {0, 1} n and Bob outputs b ∈ {0, 1} n . • Alice and Bob win if a i ⊕ b i = y x i , for all i ∈ {1, . . . , n}.

  Conditioned on Alice receiving x and outputting a, Bob has the state Tr A |ψ a,x⊕a ψ a,x⊕a | = ρ a,x⊕a . If Bob gets y = 0, he must output b = a. If Bob gets y = 1, he must output b = a ⊕ x. The probability they win the CHSH n game with this strategy is hence equal to p.

2 2 = cos 2 (β) C|Y 2 2 = cos 2 2 .

 22222 We now write |Y = γ 0 |X + γ 1 |X + γ 2 |Z , where|Z 2 = 1, X|Z = X |Z = 0, and |γ 0 | = √ x 0 , |γ 1 | = √ x 1 , and |γ 2 | = √ x 2 for some x 0 , x 1 , x 2 ∈ [0, 1].Using this expression for |Y , we haveCD|ψ (β) x 0 + x 2 Π C |Z 2 Since |ψ = cos(α)|X +sin(α)|X = cos(β)|Y + sin(β)|Y , we can write |Y = γ 0 |X + γ 1 |X + γ 2 |Z , with |γ 0 | = x 0 , |γ 1 | = x 1 ,and |γ 2 | = x 2 for some x 0 , x 1 , x 2 ∈ [0, 1]. Using this expression for |Y , we have

2 2 .

 2 The measurement where Bob guesses both bits incorrectly when applying R isF = x0,x1 M x0,x1 ⊗ R x0, x1 = (I -D)(I -C)(I -D).The probability of this measurement outcome is Ω|F |Ω = (I -C)(I -D)|Ω

2 2 .

 2 With this strategy, Bob can guess x 0 ⊕ x 1 with probability

•

  A BC := Pr[Alice can learn b after commit phase].

1 .

 1 Commit phase: Alice and Bob perform the OT n 1 protocol such that Alice gets the output (z 0 , z 1 ) ∈ {0, 1} n × {0, 1} n and Bob gets the output (b, w) ∈ {0, 1} × {0, 1} n . Here, b is the committed bit. 2. Reveal phase: If no one aborted, then Bob sends (b, w) to Alice. 3. If (b, w) from Bob is inconsistent with (z 0 , z 1 ) then Alice aborts. Otherwise, she accepts b as the committed bit. Let A OT n denote the probability Alice can learn b in the OT n 1 protocol without Bob aborting. Clearly we have A OT n = A BC .

  learns z b |Alice did not abort OT n 1 ].

  1} n |z 0 , z 1 z 0 , z 1 | ⊗ ρ z0,z1 , for some ρ z0,z1 in Bob's space B. Since Alice has no information about b, Bob can use ρ z0,z1 and measurements {M 0 z0 } z0∈{0,1} n , {M 1 z1 } z1∈{0,1} n to learn the value of Alice's first and second string, respectively, with Pr[Bob learns z 0 ] = Pr[Bob learns z 1 ] = p. Consider some purification |ψ z0,z1 ∈ A ⊗ B of ρ z0,z1 where A is controlled by Alice. Let ⊗ A 3 ⊗ A with (U x ⊗ I B )|Ω 0 = |Ω x . We define the CHSH n strategy: 1. Alice and Bob share the state |Ω 0 and receive random x ∈ {0, 1} n and y ∈ {0, 1}, respectively. 2. Alice applies (U x ) such that Alice and Bob share the state |Ω x . She measures the space A 2 in the computational basis to get her outcome a. 3. Bob applies the measurement {M y b } b∈{0,1} n on his space B to determine his outcome b.

	1 2	c∈{0,1} Pr[learn x c ] =
	p.
	2. There is a secure, non-interactive OT n p protocol. 3. There is a secure OT n p protocol.
	4. There is a strategy for winning the game CHSH n
	with probability p.
	(2. =⇒ 4.). Suppose there is a secure, non-interactive
	OT n p protocol. Without loss of generality [33], Alice and Bob's joint state from the non-interactive OT n p protocol is 1/2 n z0,z1∈{0,|Ω := 1 z0,z1∈{0,1} n 2 n |z 0 ⊕ z 1 A1 |z 0 A2 |z 1 A3 |ψ z0,z1 AB ,
	|Ω

Proof. We provide four reductions.

(1. =⇒ 2.). Let {ρ x0,x1 : x 0 , x 1 ∈ {0, 1} n } be a set of quantum states and {π x0,x1 : x 0 , x 1 ∈ {0, 1} n } be a probability distribution satisfying the properties of statement 1 of Theorem 3. Alice chooses x 0 , x 1 with probability π x0,x1 and sends ρ x0,x1 to Bob. Alice outputs

(z 0 , z 1 ) := ((1 -a)x 0 + ax 1 + d 1 , (1 -a)x 1 + ax 0 + d 2 ),

for random choices of a ∈ {0, 1} and d 1 , d 2 ∈ {0, 1} n that she sends to Bob. The first bit randomizes the success probabilities for Bob (so he has an equal probability of learning z 0 and z 1 ) and the d 1 , d 2 bit strings ensure that Alice's outcomes are random. Bob picks a random bit b and measures to learn z b depending on a, d 1 , d 2 . In particular, the probability of learning z b for b ∈ {0, 1} is equal to the average decoding probability of x 0 and x 1 , hence equal to p. Note that z 0 ⊕ z 1 = x 0 ⊕ x 1 ⊕ d 1 ⊕ d 2 is hidden from Bob and Alice cannot learn b (since Bob does not send any message), thus this protocol is secure. x to be the post-measured state assuming Alice measured A 1 to get x, and ρ x := Tr A2A3A |Ω x Ω x | to be Bob's state. We have ρ x = ρ 0 , ∀x ∈ {0, 1} n , since Bob has no information about z 0 ⊕ z 1 . By Uhlmann's theorem, for all x ∈ {0, 1} n , there exists unitary U x on A 2

  ). An n-fold repetition of CHSH, denoted CHSH ⊗n , is a game between Alice and Bob where: • Alice and Bob are allowed to create and share an entangled state |ψ before the game starts. Once the game starts, there is no further communication between Alice and Bob. • Alice receives a random x ∈ {0, 1} n and Bob receives a random y ∈ {0, 1} n . • Alice outputs a ∈ {0, 1} n and Bob outputs b ∈ {0, 1} n . • Alice and Bob win if

Appendix

Proof of Equation ( 1) and Theorem 1

Recall Equation (1) reproduced below,

We first prove the lower bound. Define the following states:

We


Sonia Belaïd
email: sonia.belaid@ens.frfouque

Pierre-Alain Fouque

Benoît Gérard
email: benoit.gerard@irisa.fr

Side-Channel Analysis of Multiplications in GF(2 128 ) Application to AES-GCM

Keywords: Field Multiplication, Authenticated Encryption, AES-GCM, Side-Channel

In this paper, we study the side-channel security of the field multiplication in GF(2 n ). We particularly focus on GF(2 128 ) multiplication which is the one used in the authentication part of AES-GCM but the proposed attack also applies to other binary extensions. In a hardware implementation using a 128-bit multiplier, the full 128-bit secret is manipulated at once. In this context, classical DPA attacks based on the divide and conquer strategy cannot be applied. In this work, the algebraic structure of the multiplication is leveraged to recover bits of information about the secret multiplicand without having to perform any key-guess. To do so, the leakage corresponding to the writing of the multiplication output into a register is considered. It is assumed to follow a Hamming weight/distance leakage model. Under these particular, yet easily met, assumption we exhibit a nice connection between the key recovery problem and some classical coding and Learning Parities with Noise problems with certain instance parameters. In our case, the noise is very high, but the length of the secret is rather short. In this work we investigate different solving techniques corresponding to different attacker models and eventually refine the attack when considering particular implementations of the multiplication.

Introduction

The multiplication in GF (2 128 ) is used in several cryptographic algorithms to diffuse a secret parameter. Two widely deployed examples are the authentication encryption mode AES-GCM and the mode of operation OCB. While it is important to guarantee the security of such algorithms against black-box attacks, e.g. using the knowledge of the inputs and outputs, it becomes mandatory to thwart side-channel attacks for an industrial use.

The main motivation of this work is to show that such multiplication, although manipulating huge part of the secret at once, can be attacked by a side-channel adversary. Hence, in a major part of this work we consider that the multiplication is an atomic operation (that is performed using a 128-bit multiplier) what is the worst case for an attacker. In an additional part we show that, as one may expect, considering designs having intermediate results indeed provides more leakages and thus lead to more powerful attacks.

As already mentioned, we focus on the application to AES-GCM. Proposed by McGrew and Viega in [START_REF] Mcgrew | The Galois/Counter Mode of Operation (GCM)[END_REF] and standardized by NIST since 2007, this authenticated encryption algorithm aims to provide both confidentiality and integrity. It combines an encryption based on the widely used AES algorithm in counter mode and an authentication based on the GHASH function involving multiplications in GF (2 128 ). This latter one mixes ciphertexts, potential additional data and a secret parameter derived from the encryption key to produce a tag. The security of the algorithm has been analyzed by many authors but despite significant progress in these attacks [START_REF] Procter | On weak keys and forgery attacks against polynomial-based MAC schemes[END_REF][START_REF] Handschuh | Key-recovery attacks on universal hash function based MAC algorithms[END_REF][START_REF] Olavi Saarinen | Cycling attacks on GCM, GHASH and other polynomial MACs and hashes[END_REF] there is currently no real attack on this mode. The most efficient attacks are the ones described by Ferguson when the tag is very short (32 bits) [START_REF] Ferguson | Authentication weaknesses in GCM[END_REF] and by Joux when the nonces are reused [START_REF] Joux | Authentication Failures in NIST version of GCM[END_REF].

In the particular case of AES-GCM, attacking the multiplier will provide to the attacker the knowledge of the authentication key H. Due to the malleability of the counter mode, the knowledge of the authentication key induces a huge security breach and thus protecting the multiplier is of real importance in contexts where a side-channel attacker is considered. Notice that if the multiplication is protected, then the simple additional countermeasure that consists in masking the tag register is enough to thwart the proposed attack.

Related Work. Some of the algorithms that we consider here come from the coding theory and we think it is a nice view to cast many side-channel attacks. Indeed, a secret value H for instance is encoded as the different leakage values obtained by the adversary. Usually, these leakages allow to recover H, but here for 128 bits, the Hamming weight does not give enough information. Moreover, we only get noisy versions of the leakage values and these values form the codeword with errors. The errors are independent from each other and the noise level is rather high as in many stream cipher cryptanalysis. Given these values, the goal of the adversary is to recover the original message H and the adversary faces a classical decoding problem.

As for the AES-GCM, Jaffe describes in [START_REF] Jaffe | A first-order DPA attack against AES in counter mode with unknown initial counter[END_REF] a very efficient Differential Power Analysis attack on its encryption counter mode. Basically, the main idea is to use a DPA attack on the two first rounds of the AES block cipher. Then, as most of the plaintext is the same between two evaluations, it is possible to recover the secret key by guessing parts of the first and second round subkeys. This attack is particularly efficient since it also allows to recover the counter if it is hidden. However, the implementations of AES are now well protected using masking and many papers proposed such countermeasures [START_REF] Chari | Towards sound approaches to counteract power-analysis attacks[END_REF][START_REF] Rivain | Provably secure higher-order masking of AES[END_REF][START_REF] Coron | Higher order masking of look-up tables[END_REF][START_REF] Grosso | Efficient masked S-boxes processing -A step forward[END_REF], so that we can assume that it is not possible to recover the secret key on the encryption part.

Our Contributions. In this paper, we consider a particular leakage model where only the storage of values leaks information to the adversary. We assume that each time a value is written in the large register, a noisy version of the Hamming distance or the Hamming weight of this value can be known by the adversary. For instance, in the context of the AES-GCM authentication, the first time the register is written, we can learn the Hamming weight of the multiplication result between the authentication key H and some known value M . Our key point is that the least significant bit of the Hamming weight can be expressed as a linear function of the bits of H. If we are able to find 128 such equations, then it is easy to recover H. However, in side-channel attacks, we only access to noisy versions of the Hamming weight and then, the problem becomes more difficult. Classically, this problem has been known as the Learning Parities with Noise (LPN) [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF] and it is famous to have many applications in cryptography. We then consider many attacker models, according to whether the inputs M are known, can be chosen and repeated. If we consider only the tag generation algorithm, additional authentication data can be input to the encryption and these values are first authenticated. We think that this model is powerful and allows us to consider many attacks on different implementations. For instance, since we only consider the writing in the accumulator of the polynomial evaluation, we do not take into account the way the multiplication is implemented and our attack also works even though the multiplication is protected against side-channel attacks.

In the first part of this paper, we consider inputs that are non controlled by the adversary. This is the case for instance in AES-GCM with the authentication of encrypted messages. We show through practical experiments that the proposed attacks may even be successful for reasonable levels of noise if averaging traces is allowed. Then, we consider methods to choose the input values for instance for the additional data or for the tag verification algorithm (e.g., with ciphertexts whose tag is incorrect), so that to improve the basic attacks. In the final part, we discuss three examples. The first one is the mode of operation OCB in which the same multiplication is used and lead to the same attacks. The specificity in this algorithm comes from the uncontrolled messages which are actually advantageously structured for our needs. The second one is a multiplication used in a context of re-keying, which is an alternative of masking. A new secret key is computed for each encryption through a multiplication which is performed differently. The previous attacks do not work in this model. The last example consider classical implementations of the field multiplication in GF(2 128 ) to show how the inner steps can improve the complexities of the aforementioned attacks.

2 Backgrounds, Leakage and Attacker Models 2.1 AES-GCM description AES-GCM is an authenticated encryption algorithm which aims to provide both confidentiality and integrity. It combines an encryption based on the widely used AES algorithm in counter mode and an authentication with the Galois mode. The so-called hash key H used for the authentication is derived from the encryption key K as H = AES K (0 128 ). The ciphertext of the encryption is denoted as C 1 , . . . , C n where the blocks C i have length 128 bits except C n which is of size u (u 128). Similarly, the additional authenticated data is composed of 128-bit blocks A 1 , . . . , A m where the last one has size ν (ν 128). Eventually, we denote by (X i ) 0 i m+n+1 the intermediate results of function GHASH with X m+n+1 being the output exclusively ored with an encryption of the initial counter to form the tag. Figure 1 illustrates the procedure with the previously defined notations. For the sake of simplicity we will use a single letter M for

⊗P H A1 X1 A2 ⊗P H X2 . . . Am||0 128-u ⊗P H Xm C1 ⊗P H Xm+1 . . . Cn||0 128-ν ⊗P H Xm+n (128m + u||128n + ν) ⊗P H Xm+n+1
Fig. 1. AES-GCM authentication both kinds of outputs (A i or C i ). Then, the definition of the GHASH function can be simply described by the following recursion

X i+1 = (X i ⊕ M i+1 ) ⊗ P H, (1)
where ⊗ P is the Galois Field multiplication described below.

Galois Field Multiplication. The multiplication ⊗ P H is performed in the field GF (2 128 ) between 128-bit data. For AES-GCM, the Galois' extension is defined by the primitive polynomial

P (Y ) = Y 128 + Y 7 + Y 2 + Y + 1.
We denote by α a root of this polynomial P . An element Q in GF (2 128 ) can be represented by a vector of coefficient (q 0 , q 1 , . . . , q 127 ) where Q = 0 i<128 q i α i . In the following we denote by Q either the element of GF(2 128 ) or the corresponding vector.

To avoid ambiguities we will differentiate field multiplication (⊗ P ) from matrix/vector multiplication (•). Since attacks we present in the paper heavily rely on the linearity of multiplication in GF(2 128 ), we will use a matrix representation of the multiplication. Namely, let Q and R be two elements of GF(2 128 ), the result of the multiplication Q ⊗ P R can be seen as a matrix/vector product Q P • R where Q P is a matrix obtained by concatenating columns representing coefficients of Q ⊗ P α i :

Q P =      q 0 q 127 • • • q 1 ⊕ q 127 ⊕ q 126 q 1 q 0 ⊕ q 127 • • • q 2 ⊕ q 123 ⊕ q 1 ⊕ q 127 ⊕ q 122 . . . . . . . . . . . . q 127 q 126 • • • q 0 ⊕ q 127 ⊕ q 126 ⊕ q 121      .

Attacker Context

Leakage Model. A usual assumption (see for instance [START_REF] Mangard | Power analysis attacksrevealing the secrets of smart cards[END_REF]) when there is no information on the implementation is to consider that all the variables V i written in the registers of a cryptographic computation leak the sum of their Hamming weight (HW) and a independent noise ε σ which follows a Gaussian distribution with a null mean and standard deviation σ (denoted by N (0, σ)):

L (HW) i = HW(V i ) + ε σ , ε σ ∼ N (0, σ).
A common generalization of this leakage model when the attacker is given the successive stored variables is to consider the Hamming distance (HD) between two consecutive data V i-1 and V i :

L (HD) i = HD(V i , V i-1 ) + ε σ = HW(V i ⊕ V i-1 ) + ε σ .
This generalization depends on the implementation. If a register is initialized to zero before storing a variable V i , the Hamming distance between both stored data is exactly the Hamming weight of V i . However, in the case of a sum for instance, we can reasonably assume that the new computed variable overwrites the stored one (intermediate result), leaking the Hamming distance between them. In the following and in order to cover most embedded devices, we consider both models.

Attacker Model. Now we defined the models for information leakage, we discuss the attacker capabilities. From the axiom "Only Computation Leaks" of Micali and Reyzin [START_REF] Micali | Physically observable cryptography (extended abstract)[END_REF], we only give the attacker the leakage of the manipulated data. Furthermore, in the most part of this paper, we restrict the leaking data to the multiplication's output to cover all the implementations. We now discuss the three characteristics that define the attacker model.

Known/Chosen Inputs. For the known operands of the Galois field multiplication, we consider the two classical attacker models namely the known message model (e.g., ciphertexts) and the chosen message model (e.g., additional data to authenticate). These two models will be respectively considered in Section 3 and Section 4.

Limited/Unlimited Queries. The attacker may face limitation in the number of queries. Such limitation may be due to time constraints but we may also consider an attacker querying for forged tag verifications in which case an error-counter may limit the number of invalid tag verifications.

Enabled/Disabled Averaging. Eventually, the attacker may be able to average traces obtained for the same computation. This is the case in the chosen messages setting but it may also be the case in the known messages setting when for instance the first blocks to authenticate have a specific format. If such feature is available, then the attacker may execute λ times each computation and average the corresponding traces. Since the leakage model considers an additive Gaussian noise, this decreases the standard deviation of the noise from σ to σ/ √ λ.

Attack Paths. We present hereafter the key idea of this paper and some preliminary results.

Main Observation. The cornerstone of the attacks presented in Section 3 and Section 4 is the fact that the less significant bit (further referred to as LSB) of the Hamming weight of a variable (equivalently distance between two variables) is a linear function of its bits. While a side-channel attacker generally uses a divideand-conquer strategy to recover small parts of the key by making guesses, it is not possible anymore as the size of chunks gets large. This prevents attackers from targeting whole 128-bit variables. Nevertheless, in the particular case where the intermediate variable is the output of a linear function involving a public input and the key, then it means that the LSB of the Hamming weight is a linear function of this input and the key. If we denote by lsb 0 (HW(M ⊗ P H)) (or also b 0 ) the bit 0 of the Hamming weight of the product M ⊗ P H, we get

lsb 0 (HW(M ⊗ P H)) = 0 i 127   0 j 127 (M ⊗ P α i ) j   h i . (2)
This is precisely what is exploited in the attacks we present. Obviously this work can also be applied to any algorithm in which such multiplication appears and is not restricted to AES-GCM.

First Block. Observing Equation 1, we see that we only know the input of the multiplication with H for the first block of data X 1 since the input of further blocks will depend on H. Moreover, since X 0 is zero, we are in a context where Hamming distance and Hamming weight leakages are equivalent and we thus only refer to the Hamming weight in the following. While the linearity of its parity bit is a very good thing from an attacker point of view, the drawback is that this value is highly influenced by the measurement noise. Assume that we use the following decision procedure to guess the bit from a leakage value,

b 0 def = lsb 0 ( HW(M ⊗ P H) + ε σ ) ,
where • is the rounding operator. Then, we obtain a noisy bit of information that we can model as follows

b 0 = lsb 0 (HW(M ⊗ P H)) ⊕ b N . (3)
where the error-bit b N is the potential error due to the Gaussian noise. This errorbit follows a Bernoulli distribution with a parameter p such that the probability of no error is

1 -p = ∞ i=-∞ 2i+0.5 2i-0.5 φ 0,σ (t)dt (4) with φ 0,σ (x) = e -x 2 2σ 2 /(σ √ 2π
), ∀x ∈ R the probability density function of the Gaussian law with null mean and standard deviation σ. In Table 1 we provide a few values of this Bernoulli parameter for several standard deviations. Note that we generally evaluate the complexity of an attack according to the Signalto-Noise Ratio which is the ratio between the signal variance and the noise variance. For 8-bit implementations 4 , we consider this SNR around 0.2 [START_REF] Mangard | Hardware countermeasures against DPA? a statistical analysis of their effectiveness[END_REF][START_REF] Belaïd | Masking and leakage-resilient primitives: One, the other(s) or both?[END_REF] which is a typical value both for hardware [START_REF] Katashita | Evaluation of DPA Characteristics of SASEBO for Board Level Simulation[END_REF] and software implementations [START_REF] Durvaux | Efficient Removal of Random Delays from Embedded Software Implementations Using Hidden Markov Models[END_REF]. It corresponds to a signal variance of 8 (with the chosen leakage model) and a noise variance of 10 (standard deviation around 3). While we do not have reference measurements for 128-bit implementations, we can assume that the noise standard deviation is close, that is around 3.

Other Blocks. The generation of traces is expensive for an attacker and in some models it may also be limited. Therefore the number of traces is generally the main criteria when evaluating the complexity of an attack. In the context of the AES-GCM, the authentication is performed through a chained sequence of multiplications. This is quite frustrating for an attacker to only consider the first block when so much information is available. We will discuss in Section 3 and Section 4 how to exploit some of the following multiplications to obtain more bits of information from a single trace.

Other Leakage Bits. As mentioned above, we only exploit the LSB of the leakage for the attacks because it directly depends on a linear combination of the key bits. However, it is also strongly impacted by the noise which involves multiple errors in the system. In this paragraph, we discuss the complexities of considering further bits of leakage. We first focus on the impact of noise on each of them. In this purpose, Table 1 gives the values of the parameters of the Bernoulli law followed by each one of them. They are computed using (4) with i varying from -7σ to 7σ to capture at least 1f 00 -2.56 • 10 -10 % of the values. The

ε ε ε ε ε 1 0.5 -4.6 10 -3 1.3 10 -1 4.7 10 -4 ε ε ε ε 2 0.5 -1.7 10 -9 3.8 10 -1 8.0 10 -2 1.8 10 -4 ε ε ε 3 0.5 -ε 4.3 10 -1 2.3 10 -1 1.2 10 -2 2.0 10 -7 ε ε 4 0.5 -ε 4.5 10 -1 3.2 10 -1 6.1 10 -2 1.1 10 -4 ε ε 5 0.5 -ε 4.6 10 -1 3.7 10 -1 1.3 10 -1 1.9 10 -3 ε ε
results are directly related to the number of errors in the system which decrease together with the increase of the bits indices. However, the resulting systems are made of equations of higher degrees (exponential with the index):

b i = 0 j1<•••<j 2 i 127   1 2 i 0 k 127 (M ⊗ P α k ) j h k   , ∀ 0 i 7.
and thus are more complicated to solve. In particular, the methods capturing the errors removal like LPN and linear decoding unfortunately do not apply on nonlinear systems 5 . We thus have to consider first a solver on the error-free system of equations and then complete its complexity with the errors removal. To the best of our knowledge, one of the most efficient solver is the algorithm F5 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero F5[END_REF] provided by Faugere and based on the Gröbner bases. While the solving complexity of the (error-free) quadratic system may be reasonable, it gets computationally impractical when considering the most significant bits6 .

Known Inputs

As described in the previous section, for each observed first multiplication, an attacker obtains a noisy Hamming weight value of the output. The LSB of the Hamming weight being linearly dependent on the key (see Equation 2), the attacker can gather many measurements to form a linear system having the authentication key H as solution. In this section we discuss different techniques to solve this noisy linear system. First we propose a simple procedure that allows the attacker to recover the key. Then, we investigate enhancements and other techniques that help decreasing the attack complexity in presence of higher noise.

Naive Attack

From Equation 2, the (noisy) linear system formed from t messages (M ( ) ) 0 t can be written as follows:

S =        0 i 127 0 j 127 (M (0) ⊗ P α i ) j h i = b 0 (0)
. . .

0 i 127 0 j 127 (M (t-1) ⊗ P α i ) j h i = b 0 (t-1)
.

(

) 5
The values b 0 ( ) are obtained as in Equation 3 that is we simply round the leakage observations to the closest integer and extract the least significant bits.

Once the system S is correctly defined in GF(2), we can efficiently and directly solve it (e.g., calling mzd solve left of the library m4ri [START_REF] Albrecht | The M4RI Library -Version 20130416[END_REF]) if these two conditions are fulfilled: i) S contains at least as many linearly independent equations as the number of unknown variables (128),

ii) there is no error in the bits b 0 ( )

(i.e., b 0 ( ) = b ( ) 0 ).
First, the probability of obtaining a full-rank matrix from k k-bit messages, is

0 i k-1 1 -2 i-k .
In our context (that is k = 128), this probability is close to 0.3. To obtain a full-ranked matrix with high probability (say 0.9) the number of additional messages m must satisfy 1 -1 j 2 m 1 -0 i k-1 1 -2 i-k 0.9. For k = 128, a single additional message (m = 1) makes the equation holds. Note however that the full rank condition does not need to be fulfilled to recover the key. If it is not the attacker should first recover a solution of the system and the kernel of the linear application then test all the solutions to eventually recover the key.

Second, we consider the negative impact of the measurement noise. The latter introduces errors in the system which thus cannot be solved with classical techniques. A simple (naive) solution is to consider that one of the b 0 (i) 's is erroneous and to solve k times the system with the k possible vectors b 0 ⊕ α i . If the key is not found we can incrementally test all other numbers of errors until the correct key is found. Notice that the inversion is only done once: solving the system with a different vector b 0 only requires a matrix/vector multiplication. If e errors are made among the k messages, then the correct key will be found in at most C (e) k matrix/vector products:

C (e) k = e i=0 k i . (6)
When the number of errors grows, it quickly becomes computationally hard. For instance, for e = 6 and k = 128, C

k ≈ 2 32 . In the next section we investigate techniques to decrease the number of errors in S.

Improved Attack

In this section, we propose two improvements for the attack. The first one consists in an optimal decision to guess the Hamming weight LSB. This criterium can also be used to advantageously select 128 traces among many more to limit the errors. The second improvement is to show that an attacker can actually use the leakage obtained from the two first multiplications and not only from the first one.

Reducing the Noise.

An Optimal Decision Rule. We propose here to use the LLR statistics (for Log Likelihood Ratio) to derive a bit value b 0 in average closer to b 0 than b 0 from a leaked Hamming weight. This statistics is extensively used in classical cryptanalysis (an application to linear cryptanalysis can be found in [START_REF] Baignères | How far can we go beyond linear cryptanalysis[END_REF]) since the Neyman-Pearson lemma states that for a binary hypothesis test the optimal 7 decision rule is to compare the LLR to a threshold. The LLR of a leakage is given by: LLR(

) = log(P[b 0 = 0| ]) -log(P[b 0 = 1| ]).
The bit b 0 is equally likely equal to 0 or 1 since we have an a priori uniform distribution for the secret. Thus, using Bayes relation we obtain that

LLR( ) = log (P[ |b 0 = 0]) -log (P[ |b 0 = 1]) with P[ |b 0 = i] = 128 w=0 P[ |b 0 = i, HW( ) = w]P[HW( ) = w].
If the result of LLR( ) is positive it means that the parity bit is likely to be equal to 0. Otherwise, we should assume it is equal to 1. We thus define:

b 0 def = 0 if LLR( ) 0, 1 otherwise.
Such technique will decrease the error rate since it boils down to select the most probable value for b 0 . Unfortunately it turns out that it has a small impact on the number of errors made, but its combination with the following technique will be useful as illustrated in Figure 2.

Selecting Traces. Nevertheless, when more than k traces are available, it would be of interest to only select the k most reliable ones to decrease the number of errors in the system. Basically, we would like to take into account the confidence we have in a given bit. For instance, assuming a 0 parity bit from a leakage 64.01 seems more reliable than for a leakage equal to 64.49. Interestingly, the higher the absolute value of the LLR is for a given trace, the more confident we are in the choice. Therefore, an attacker should select the n samples with the highest LLR values to form the system. The point is that those k samples may not be linearly independent. Two solutions can then be used: i) one may only consider a subset of these k samples, solve the system and brute force the remaining bits, ii) or one may choose k linearly independent samples from the highest LLR values.

Finding the set of k linearly independent samples maximizing this sum is a combinatorial optimization problem which may be quite hard, thus we use a simple "first come/first selected" algorithm that provides a set of k samples. The algorithm iteratively looks for the sample with the highest absolute LLR value that increases the system rank. Eventually, the red curve models the optimal with the 128 best traces (having the highest LLR values but not necessarily linearly independent). As mentioned, we can observe that the use of the LLR does not significantly improve the attack (black and green curves very close). However, the chosen selection of the best LLR allows the attack to resist higher levels of noise: 0.4 (resp. 0.5) instead of 0.3 (resp. 0.4) to achieve the same Bernoulli parameter. Notice that we cannot distinguish the red curve from the blue one. This proximity means that while the "first come/first selected" approach is not optimal it is not worth working on a refined algorithm since the improvement will be bounded by the distance between both curves.

Averaging Traces. In the context where the attacker can monitor few multiplications with the same input, we can also consider another commonly used method which consists in averaging the traces. As claimed in Section 2 and experimentally confirmed in Section 3.3, repeating the traces m times allows to divide the noise standard deviation by √ m. Figure 3 gives the complexity of removing the errors (averaged from 10,000 tests computed from Eq. 6) according to the number of repetitions of 128 traces for several levels of noise. Note that the full complexity of the attack also includes the system solving (a single inversion in k 3 and C (e) k -1 matrix/vector products in k 2 ). Considering it, we can claim that with less than 2 16 traces (i.e., 500 repetitions), the attacker can practicaly recover the key for σ 2 up to 10 (σ ≈ 3).

Saving Traces with Further Blocks. Up to now we only considered the first multiplication since not knowing H implies not knowing the input of the second multiplication (indeed X 2 = (M 1 ⊗ P H ⊕ M 2 ) ⊗ P H). Nonetheless, re-writting this equality as

X 2 = M 1 ⊗ P H 2 ⊕ M 2 ⊗ P H,
we observe that X 2 also is a linear function of H since squaring is linear over GF [START_REF] Baignères | How far can we go beyond linear cryptanalysis[END_REF]. Denoting by S the matrix corresponding to the squaring operation, then

X 2 = (M 1 • S ⊕ M 2 ) ⊗ P H.
Thus a linear relation can also be obtained from the second multiplication substituting M 1 • S ⊕ M 2 to M in Equation 2. And this is also true in the Hamming distance model since

X 1 ⊕ X 2 = (M 1 • S ⊕ M 1 ⊕ M 2 ) ⊗ P H.
This observation is of great importance since it significantly improves the complexity of the attacks with a number of required traces divided by a factor two.

Experimental Results

We illustrate here the necessity of averaging and we confirm the corresponding decreasing of the noise by giving the results obtained on real experiments.

Settings. We implemented the GHASH function on the Virtex-5 FPGA of a SASEBO board and acquired traces from an EM probe. We obtained 10 5 traces that we separated in two 5 • 10 4 trace sets (Set 1 and Set 2). We then built templates using Set 1 and a projection obtained using the same technique as in [START_REF] Durvaux | Efficient selection of time samples for higherorder DPA with projection pursuits[END_REF]. Afterwards we performed the first part of the attack (that is guessing parity bits of Hamming weights with the LLR technique) using this template.

We then attacked both sets of traces.

Results. In Table 2 we provide the results we obtained. For a given number of averaging (av.) we report (i) the noise standard deviation σ, (ii) the simulated error rate obtained from this standard deviation (10 7 simulations) and (iii) the error rates obtained when applying the template to Set 1 and Set 2. First, we see that doubling the number of averaging roughly leads to a reduction of noise standard deviation by a factor √ 2 as we would expect. Second, the attack performs better on the first set since it is the one that have been used to build templates. For Set 1, the error rates actually correspond to theoretical approximations based on the noise standard deviation. We also see that the error rates obtained for Set 2, while obviously deviating from expected values, are significantly decreasing with the number of averaging. Indeed, when averaging is possible, the obtained features show that an attack can be mount easily. As one can see, Table 2 does not contain data for error rates corresponding to less than 4 averagings. This is due to the fact that the deviation from 0.5 is too small to be estimated using 50,000 traces. We did not managed to get more traces since experiments with higher levels of averaging confirm our predictions.

Solving the System with more Errors and Advanced algorithms

There are many algorithms to recover the authentication key from noisy Hamming weight LSBs. In the case where more than n multiplications are observed, the attacker will obtain an overdefined linear system. In other words, the attacker will get redundant linear relations involving bits of the key H. Guessed LSBs extracted from leaking multiplication can thus be seen as forming a noisy codeword that encodes the authentication key H using the code defined by the linear relations of the form of Equation 2. Recovering the key is then equivalent to decoding the noisy codeword.

Learning Parities with Noise Algorithms. The Learning Parities with Noise (LPN) problem is the problem of recovering x ∈ GF(2) k given many pairs (a, (a, s) ⊕ e) with a ∈ GF(2) k samples randomly chosen, (a, s) denotes the scalar product and e is a Bernoulli distribution of parameter p. The most efficient algorithms to solve the LPN problem are based on the Blum-Kalai-Wasserman algorithm [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF]. This algorithm tries to perform Gaussian elimination in a smart way but cancelling many bits with one single xor. The idea is to use many samples and xoring those that have many bits in common. However, this algorithm is exponential in the number of samples, time and memory of order 2 O(k/ log k) where k is the size of the secret values. This algorithm has been improved by Fouque and Levieil in [START_REF] Levieil | An improved LPN algorithm[END_REF] but it allows to reduce the constant in the exponent. In practice, it requires a huge number of samples but since here the size is relatively short k = 128, we could use such algorithms. However, since the noise involves a Bernoulli parameter p getting closer to 1/2, it expects 2 40 bytes of memory and 2 34 queries when the standard deviation σ equals 0.5, while it grows to 2 241 bytes of memory and 2 334 queries when σ equals 2. Lyubashevsky gave in [START_REF] Lyubashevsky | The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem[END_REF] a variant of BKW with running time 2 O(k/ log log k) for k 1+ε samples. A further modification proposed more recently by Kirchner in [START_REF] Kirchner | Improved generalized birthday attack[END_REF] achieved better runtimes for small values of p. This algorithm runs in time O(2

√ k ) with O(k) samples when p = O(1/ √ k).
Linear Decoding. Since inputs are not controlled by the attacker, the corresponding linear code is random. Decoding over random linear codes is known to be a hard problem (NP problem). The currently best algorithm that solves this problem is the one presented by Becker et al. in [START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF] which has complexity O(2 0.0494n ) (where n is the code length). Nevertheless, using such algorithm only makes sense if the noise is low enough to ensure that the actual key-codeword is the closest to the noisy word obtained by the attacker. Indeed if the noise is too high, then the channel capacity will decrease below the code rate and thus the closest codeword to the obtained noisy one may not be the one the attacker looks for. Using the binary symmetric channel model 8 we obtain that for a standard deviation σ of 0.5 the code length should be at least 128 0.107 ≈ 1200 which would yield a complexity 2 59.28 using [START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF]. Obviously the attacker has better using less than 1200 relations and test more than a single key candidate. To do so she will need a list-decoding algorithm. For cryptographic parameters (that is a key that can be very badly ranked), the only known solution is to see the linear code as a punctured Reed-Muller code and to use a Fast Walsh transform to obtain probabilities for each possible codeword. Since this technique has complexity O(k2 k ) with k the code dimension, it is not straightforwardly applicable here. We discuss in Section 4 how we can take profit of controlling inputs to use such decoding algorithm.

Complexities Evaluation

In this section, we built a system of equations from a new trick, that is the use of a single leakage bit. Then, we discussed methods to solve it involving step by step decoding (Eq. 6) and LLR statistics and the existing tools: LPN and linear decoding. We now propose a comparison of the methods complexities through Table 3 both in terms of number of samples C s and of computation time C t . As for the LLR method combined with the step by step error removal (Equation 6) the time complexity C t includes not only the errors removal C (e) k but also the the linear system solving (a single inversion in k 3 and C (e) k -1 matrix/vector products in k 2 ). As for the number of samples C s , it is divided by two in all methods thanks to the smart use of the second GCM block X 2 . We remark that for low levels of noise (at least until σ = 0.4), linear decoding is the best method to choose both in terms of number of samples and time complexity. Afterwards, it depends on the number of available samples. Concretely, the more traces we have the less time we need.

Chosen Inputs

Let us now consider techniques that may be used to recover the key in the model where the attacker is able to control multiplication inputs. A first idea is that in such context averaging should be considered as obviously enabled 9 and thus measurement noise could be decreased by repeating inputs. Two other ideas are: i) structuring the messages to make the system easier to solve, ii) choosing messages to be able to exploit more than two multiplications.

The following is dedicated to the discussion of these two ideas.

Structured Messages

In Section 3 we saw that recovering the key could be seen as a decoding problem. The difficulty arose from the fact that the linear code corresponding to our attack is and have a high dimension (128). Assuming the attacker is now able to control inputs of the multiplication, she may choose the underlying code.

Choice of the Code. The question is now which code should we use? As a cryptanalyst the requirements for a linear code may be different from the one found in coding theory.

List Decoding. First, an attacker aims at recovering the key. She has computing power and can enumerate many key candidates before finding the correct one. Such a feature means that a list decoding algorithm should be available for the chosen code. Moreover, the list size is not of the same order of magnitude that can be found in coding theory. Ideally, we would like to obtain a list of all key candidates ordered by probabilities of being the correct one. Obviously such a list cannot be created since its size would be 2 128 . Nevertheless, using the key enumeration algorithm of [START_REF] Veyrat-Charvillon | An optimal key enumeration algorithm and its application to sidechannel attacks[END_REF], an attacker can enumerate keys from ordered lists of key chunks. If the linear code underlying the attack is a concatenated code then such algorithm can be used. Indeed, the corresponding matrix of the system would be a block diagonal matrix. Each block corresponds to a smaller linear code that may be fully decoded, that is the attacker obtains a list of all possible keys with the corresponding probabilities.

Soft Information. Second, since the noise may be high, we would like to take profit of the whole available information and not only consider obtained bits b 0 or b 0 . We illustrated in Section 3.2 the gain obtained when considering LLR statistics to take into account the relations reliabilities. Here, we would like a code which decoding algorithm can exploit such soft information.

Taking into account the aforementioned constraints, we opted for a concatenating code of smaller random linear codes. The latters can efficiently be decoded using a Fast Walsh Transform (FWT) as mentioned in Section 2. We thus aim at obtaining a matrix corresponding to the system S of the form

    S 0 S 1 . . .     •   H   =    b 0 . . . b t    . (7)
Generating Structured Inputs. To generate the inputs that yield a matrix similar to the one in [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF], the attacker has to consider the application

ϕ : M →   0 j 127 lsb j M ⊗ P α 0 , . . . , 0 j 127 lsb j M ⊗ P α 127  
that maps an input M to the corresponding vector of coefficients for the system S. To generate the bloc S c , she chooses inputs in the kernel of ϕ |Ic where indices in I c correspond to columns outside block S c . A basis of these kernels are efficiently computed using Gauss eliminations.

Simulations. To illustrate the method results, we give two graphs. The left one presents the averaged rank of the correct key among all the 2 128 possible ones from the key chunks probabilities according to the noise standard deviations for 256 samples (blue) and 1024 samples (red). The right one is a security graph [START_REF] Veyrat-Charvillon | Security evaluations beyond computing power[END_REF] which draws the evolution of the bounds of the correct key rank according to the number of samples for σ = 0.5.

Saving Traces

A second way, for the attacker, to take profit of the control she has on inputs is to leverage on Ferguson observation [START_REF] Ferguson | Authentication weaknesses in GCM[END_REF]. During the specification process of AES-GCM, Ferguson observed that it was possible to obtain a tag that is linearly dependent on the authentication key H in the particular case where the polynomial corresponding to the tag only has non-zero coefficients in positions where the exponent of H is a power of two. This observation relies on the linearity of the squaring operation as mentioned in Section 3.

We saw that this observation allows to exploit the two first multiplications but if the attacker has the control on the inputs she can choose them to do more. Again, this trick can be used either in case of Hamming weight or Hamming distance. The only limitation is that the number of blocks to authenticate grows exponentially in the number of exploitable multiplications. The trade-off will depend on the available time for getting traces and on a potential limitation in the number of queries. To illustrate this we show how an attacker can exploit 3 multiplications in a single trace. From Eq. 1, we obtain the expression of the four first X i 's when M 2 is set to 0:

X 1 = M 1 ⊗ P H, X 3 = M 1 ⊗ P H 3 ⊕ M 3 ⊗ P H, X 2 = M 1 ⊗ P H 2 , X 4 = M 1 ⊗ P H 4 ⊕ M 3 ⊗ P H 2 ⊕ M 4 ⊗ P H.
We see that relations obtained from X 1 , X 2 and X 4 only involve power-of-two of H which means that the relation is a linear function of H. For instance

X 4 = (M 1 • S • S ⊕ M 3 • S ⊕ M 4
) ⊗ P H, and because she knows S and can choose M 4 , the attacker can obtain the input of its choice for the fourth multiplication.

Other Applications

In this section, we discuss different applications of the presented attacks. We first consider the OCB mode of operation on which the proposed attacks allow to recover the masks. Then, we look at another multiplication on which our attacks unpractical. Finally, we give some hints on the complexity of our attacks if the attacker has access to the inner parts of the multiplication.

OCB Mode of Operation

In OCB mode of operation, the masks added before and after the encryption of each block are computed with a multiplication in GF (2 128 ). As in AES-GCM, the process uses a secret constant computed by encrypting the message zero with the secret encryption key. Despite some small differences between the versions OCB1 and OCB2, in both cases, a secret value (E K (0 128 )) is multiplied by a power of two. Thus, the scenario is easier than for the uncontrolled setting since the messages are very sparse. Plus, their shape is close to the one considered in the controlled setting. As a consequence, the secret constant can be recovered in OCB1 and OCB2 at least as well as (but generally easier than) in AES-GCM and allows to recover the masks which are supposed to protect the encryption.

Re-keying

In [START_REF] Medwed | Fresh re-keying: Security against side-channel and fault attacks for lowcost devices[END_REF], Medwed et al. propose to multiply known uniformly distributed 128bit messages r with a 128-bit secret master key k to generate session keys in the context of re-keying. Each resulting session key is then used for a single encryption of a plaintext block. Doing so, only the generation of the session keys is required to resist Differential Power Analysis attacks. Therefore, the authors only mask this operation but the resulting session key can still leak its (noisy) Hamming weight. The context is thus the same than in AES-GCM but the multiplication is different, the variables being defined on GF(2 8 )[y]/y 16 + 1.

Re-using the matrix/vector modelization, we can represent the message r being multiplied with the key k by a (16 × 16) matrix R p as follows: ). As we can see, only the sum of all the key bytes can be recovered if the attack is successful. However, no individual key bit can be determined. If we extended the attack to more leakage bits, we could (at most) successively recover all the bits of the Hamming weight of the key. It is worth noting that the non-applicability of the attack directly comes from the multiplication's polynomial. Any polynomial with an even number of monomials makes the attack fail when considering only the LSB of the Hamming weight.

R p =      r 0 r m-1 • • • r 1 r 1 r 0 • • •

Specific Implementations

Previously, we considered a secure multiplication on GF(2 128 ) for which we just had access to the result. Doing so, we covered all the multiplier implementations like [START_REF] Daniel | Faster binary-field multiplication and faster binary-field macs[END_REF] including the protected ones (e.g., with masking). We now show that making assumptions on the multiplier implementation improves the efficiency of our attack. As explained in [START_REF] Mcgrew | The Galois/Counter Mode of Operation (GCM)[END_REF][START_REF] Yang | A high speed architecture for galois/counter mode of operation (GCM)[END_REF], a usual method to implement a multiplier is to split one of the two operands in smaller blocks (a (128×128)-bit multiplier does not generally fit the area requirements) and perform intermediate multiplications which are progressively accumulated. In the full version of this paper, we focus on two such multipliers with one or the other operand being split. When the secret key is split, the attacker can follow a divide-and-conqueer strategy to recover each block. Nevertheless, when the message is split, the attacker cannot practically enumerate all the possible secret keys. In this case the scenario is still easier than the generic one since we focus on sparse messages of at most n bits.

Figure 2

 2 represents the averaged experimental values (on 10.000 samples) of the Bernoulli parameter p for 500 messages in different scenarios. The black curve represents the use of function round to fix b 0 . The green one represents the LLR without selection of the best traces while the blue one integers this selection among the first linearly independent traces.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Bernoulli parameter with rounding (black), LLR (green), traces selection (blue) and best LLR traces (red)

Fig. 4 .Fig. 5 .

 45 Fig. 4. Key rank for 256 (blue) and 1024 (red) samples

  the r i in GF(2 8 ). From this matrix, we can easily write the equation involving the LSB b 0 of the Hamming weight of the result: with • the multiplication in GF(28

Table 1 .

 1 Bernoulli parameter p for different levels of noise with all ε 10 -9

	std dev σ	1 st bit	Bernoulli parameter p 2 nd bit 3 rd bit 4 th bit 5 th bit 6 th bit 7 th bit
	0.5	3.1 10 -1	2.7 10 -3

Table 2 .

 2 Noise levels and error rates obtained from EM traces.

	av.	σ	error rates	av.	σ	error rates
			simul	Set 1 Set 2			simul Set 1 Set 2
	1 1.958	n/c	n/c n/c	6 0.770	0.466 0.454 0.467
	2 1.287	n/c	n/c n/c	8 0.637	0.414 0.407 0.457
	3 1.063 0.5 -2.26 10 -3 n/c n/c	10 0.579	0.378 0.370 0.422
	4 0.882	0.486	0.483 0.495	12 0.520	0.333 0.338 0.404

Table 3 .

 3 Complexities of recovering the key with LLR and Eq. 6, LPN and linear decoding according to the level of noise Cs/Ct Cs/Ct Cs/Ct Cs/Ct Cs/Ct LLR and Eq. 6 2 8 /2 21 2 8 /2 21 2 8 /2 22 2 8 /2 65 2 8 /2 107 LPN (LF Algo) 2 7 /2 21 2 7 /2 23 2 26 /2 28 2 32 /2 34 2 48 /2 50 Linear decoding 2 6 /2 6 2 6 /2 7 2 7 /2 11 2 8 /2 25 2 9 /2 62

	P M ethod P P P P	P P σ 0.1	0.2	0.3	0.4	0.5

Notice that our attacks also work on 8-bit implementations where they are more efficient since the attacker can capture intermediate leakage on 8-bit values.

A linearised system would be involve too many variables to be efficiently solved.

The complexities related to each bit can be computed with the package[START_REF] Bettale | Magma Package: Hybrid Approach for Solving Multivariate Polynomial Systems over Finite Fields[END_REF].

Except maybe in pathological cases.