Following ground-breaking advances in the field of machine learning, an increasing number of real-world applications, such as image and speech recognition [17,19,26,48], perform classification and prediction tasks using Neural Network (NN) inference. NN inference has also found numerous applications in domains that operate on real-time data. Wearable sensors for health monitoring [36,38], smart devices [34,54] and autonomous vehicles [32,56] are typical classes of embedded systems that collect data and perform a classification task in real-time.
In this paper we consider the scenario of NN inference algorithms running locally on an embedded device (rather than on a cloud computer), as employed by many popular smart applications and end-user health monitoring devices [34,54]. This scenario is preferred in cases where data privacy is paramount (which may be compromised in the cloud either during transmission or by the cloud service itself), or where network connectivity is unreliable, e.g., in autonomous driving [32,56].
Even in the scenario of local inference, however, the privacy of the directly or indirectly involved data is not fully guaranteed. By pushing trained NN models to end-user devices, the NN model providers may be inadvertently making the privacy-sensitive training data partially recoverable to skilled attackers, which is particularly concerning in situations that deal with medical records, health data and biometrics. Membership Inference [37,44,47] and Model Inversion [11,12] attacks target the sensitive data that a NN model was trained on. When executed in a white-box setting, i.e. with detailed knowledge of the NN model (including specific values of weight parameters), both types of attacks have been shown to outperform attacks without such knowledge [11,31], by reducing the false-positive rate during training data recovery.
Knowledge of some NN model's parameters is a natural requirement of white-box attacks. Di erential power analysis (DPA) of the embedded device [23] can provide this knowledge, paving the way for stealing privacy-relevant training data. DPA is a form of sidechannel attack in which an adversary recovers sensitive data involved in the computation of the device, by ob-serving its power consumption. Recent work has demonstrated that DPA can be successfully launched against NN inference models to reverse-engineer the number of layers and neurons in each layer, the activations as well as the values of its various parameters [3,10,55].
Motivated by the above privacy concerns, we ask whether model providers can be better equipped to limit the leakage of private information from the NN models they deploy. Specifically, we address the problem of protecting the internal NN parameters-which, in the above spirit, we consider to be secrets-against DPA. We assume the attacker has physical access to the device executing NN inference (e.g., by purchasing a health monitoring device) and can therefore control its inputs, and observe its outputs and power consumption. Our proposed DPA protection mechanism is masking [5,16], a form of secret sharing. We present a suite of masked operations fundamental in NN inference that are resistant against DPA. Masked computations are carried out in a finite ring and performed in a shared fashion, i.e., they may only operate on randomized shares of a secret, without reconstructing it.
Two characteristics of NN inference algorithms make their masking a challenging task. The first is related to data representation, as NN inference operates on numerical values which are usually represented by floating-point arithmetic. Masking of floating-point values is problematic due to significant precision losses during secret sharing and complex floating-point semantics. In this work we use fixed-point arithmetic for masking NN inference, as it represents numerical values using (signed or unsigned) bounded integers, which in turn are amenable to masking, with marginal losses in prediction accuracy [14,27].
The second is related to masking of the required operations themselves, which include primitive operations on fixed-point numbers as well as operations unique to NN inference. Multiplication in fixed-point arithmetic requires a truncation operation, which must be masked as well. We perform masked truncation by adapting an approach originally proposed in the context of multiparty computation [35]. Among the non-linear operations, masking of the activations requires a masked sign operation, which we accomplish using the bitwise representation of signed integers and masked multiplication.
After obtaining a complete set of masked operations for NN inference, we turn our focus to computational and randomness requirements. To improve the e ciency of masked NN inference along both axes, we take into account its intrinsic characteristics, such as the chaining of layer operations, and propose e cient masked al-gorithms that are resistant against DPA. Consider the dot product operation (which takes up a bulk of the NN inference): instead of a straightforward substitution of primitive addition, multiplication and truncation by their masked counterparts, we fuse the masked primitives into a masked dot product that is more ecient and minimizes precision loss due to truncation. As for randomness requirements, given the large number of secret weight parameters (compared to the number of secret key values of cryptographic algorithms), we devise e ective ways to reduce the demands for randomness that is required for the weight parameters to be secret-shared, as well as to perform masked operations on them.
In summary our contribution are: 1. We devise a library of masked operations fundamental in NN inference; we call each of them a gadget.
We prove the security of our gadgets under the notion of 1-strong-non-interference (1-SNI) [2]. This notion guarantees that an attacker observing single points in the shared computation cannot learn any information on the secrets, and that 1-SNI gadgets can be securely composed into larger constructions. 2. We show how to compose our proposed gadgets into larger constructions, e.g., Multi-Layer Perceptron (MLP) inference models. We reason about their security both formally-using again the notion of 1-SNI-and experimentally, using Test Vector Leakage Assessment (TVLA), a standard methodology for the security evaluation of DPA targets. 3. We describe a tightening of the randomness requirements for our proposed inference models. Our approach vastly reduces the required random numbers, a scarce resource in embedded devices, from linear in the number of NN parameters to linear in the depth of the NN, without impacting security guarantees. 4. Finally, we provide secure implementations of MLP and Convolutional NN (CNN) inference in a publicly available C library, and experimentally evaluate the runtime penalty incurred by our proposed constructions, as well as the improvements of the tightening. We provide results for both x86 and ARM, across di erent NN architectures. We show that our masked inference models do not hinder the accuracy performance and incur about a 5-fold slowdown for MLP and 2-3-fold slowdown for CNN (including the cost of generating the required amount of random numbers), comparable to or lower than the slowdowns su ered by commonly encountered masked cryptographic software [42] (3-to 20-fold).
Masking of NN in the context of DPA has only been explored very recently [9,10]. The prior work targets a special class of NN, namely Binarized NN (BNN) [39], which operate mostly on Boolean values, and implements a masked version of the latter on an FPGA. To our knowledge, our work is the first to support implementing arbitrary masked Feedforward NN.
Side-channel attacks exploit physical characteristics of computational systems, such as timing [24], power consumption [23] and electromagnetic emanations [13], to recover confidential data of the computation. In their seminal work on Di erential Power Analysis (DPA) [23], Kocher et al. show that an attacker able to observe power traces of a cryptographic implementation, i.e., variations of power consumption during the steps of the computation, can exploit the correlation between the values produced along the computation and the amount of power required to process them, in order to recover cryptographic secrets.
The main objective of this work is to devise algorithms for NN inference that are resistant against Power Analysis. The pre-trained NNs are executed as bare-metal applications on a microprocessor. Given a classification input, the microprocessor performs an inference round using the NN model. The parameters constitute the secrets of the NN. Our threat model assumes a non-invasive, passive attacker [49] that is able to probe the power consumption of the processing unit. The attacker knows the algorithm executed on the microprocessor, but doesn't have access to the exact implementation. The attacker is non-invasive since they cannot depackage the processing unit in order to read secrets directly from the wires of the device. The attacker is passive as they observe the device's behavior during the processing without tampering with its functionality, e.g., they don't inject faults to the computation or provide malformed inputs. Finally, the attacker is bounded, i.e., there is a limit on the number of probes that monitor the device's power consumption. Attackers that violate these assumptions, e.g., by using an unlimited number of probes [25] fall outside the scope of this work.
Example Setting Human Activity Recognition (HAR) uses mobile sensors of real-time and embedded systems to enable a wide array of applications such as life-logging, healthcare, senior care etc. Deep Learning is a beneficial technology for HAR, as it improves the inference accuracy without burdening the underlying hardware [18,29,57]. A malicious user with access to a sensor-based device can launch DPA to reverse engineer the parameters of the trained network performing HAR. We demonstrate DPA on a MLP with a single hidden layer of 512 neurons (common in HAR tasks [29]) that expects as input motion readings and classifies them into one of 14 possible activities. The attacker provides multiple inference inputs to the device, recording the input and the device's power consumption for the inference round. The power consumption of an inference round for input i is the power trace t i ; each power trace consists of the same number of samples. The power consumption of the device for the trace t i at sample s is denoted by t i [s]. As a result, the attacker has collected sets of inputs I and power traces T (|I| = |T |).
Having recorded each inference input, the attacker targets the multiplication operation between inputs and weights of the fully connected layer, and makes a guess w g for the value of a specific weight. Using the guessed value and the set of inference inputs the attacker computes the set V = {v i := HW (i • w g )|i oe I}, where HW returns the Hamming weight of a value. Then, the attacker computes Pearson's correlation fl V,Ts , where
|i oe I} is the set of power consumption values at sample s. Figure 1 shows the values of fl for each sample of the power traces, for a total of 10K power traces, for an MLP performing HAR. Around sample 11K we observe a correlation peak, i.e., a high linear relationship between v i and the power consumption at sample 11K, which indicates that at this point of the computation the MLP performs a multiplication between an input and the value w g . By performing multiple such correlation tests for di erent weight guesses, the attacker can eventually recover the weights of the MLP [3,49]. In our work we aim to provide NN inference algorithms that eliminate any correlations between the values processed by the device and its power consumption.
NN are computing systems that, given some input, ultimately render a decision, e.g., assign to the input a particular classification label. In the context of classification, Neural networks (NN) can be thought of as mathematical functions that map an input vector to a vector of probabilities, each representing the likelihood for one of the classification outcomes.
Feedforward neural networks (FNN) are the quintessential deep learning model and form the basis of many NN applications. They are called feedforward because information flows through the computation without any feedback. They are called networks because they can be thought of as composition of multiple functions. Each function represents a layer of computation, and the composition of multiple functions forms a chain of layers. The length of this chain is the depth of the network. The last layer of the chain is the output layer. All other layers are referred to as the hidden layers.
The number of units in a layer, named neurons, defines the layer's width. Each neuron's output is defined by an expression of the form Activation( q (weight• input) + bias): the results of the preceding layer form the inputs of the neuron, which undergo a linear transformation-i.e., a weighted summation followed by a bias addition-, and a non-linear activation step. An entire FNN architecture can be specified by its parameters along with the type of each layer. An architecture such that all the neurons in one layer are connected to the neurons in the next layer, i.e., it is Fully Connected (FC), and undergo a linear transformation followed by an activation function is known as a MLP. A MLP whose weight parameters are either -1 or 1 is a BNN. A FNN that uses convolutional layer and potentially pooling and FC layers is a CNN.
Fixed-point arithmetic is an approximation of real arithmetic that lends itself well to representation on computational platforms. Fixed-point numbers allocate a fixed amount of bits to represent their fractional part. An immediate caveat is that for a given word size ¸, a fixedpoint number can represent a smaller range of decimals compared to a floating-point number. The fixed number of bits of the fractional part brings, however, the advantage that operations over fixed-point numbers can be carried out by means of simpler circuits. As an example, addition in fixed-point arithmetic amounts to addition over integers that implement wrap-around semantics when overflows occur. This trade-o between precision/range and simplicity of data representation and operations has made fixed-point arithmetic a popular choice on embedded systems and more generally environments with constrained resources.
Fixed-Point numbers can be represented by signed or unsigned machine integers parameterized by two positive numbers ¸and ¸d, where ¸is the bit-length of the integer word, and ¸d < ¸. A fixed-point number x can be now interpreted as a fraction whose numerator is the two's complement representation of the ¸-bit integer x and whose denominator is 2 ¸d . That is, in fixed-point representation there is an implicit binary point between bits ¸d + 1 and ¸d. A fixed-point number x can be decomposed into x 1 •2 ¸d +x 2 , where x 1 is a (signed) integer and x 2 oe [0, 2 ¸d ).
Fixed-point arithmetic comes in signed or unsigned forms, depending on whether the bits of the numerator are interpreted as signed or unsigned numbers. The difference in sign representation results in di erent representation ranges of a (¸, ¸d) fixed-point number, namely
for signed and Ë 0, 2 ¸≠1 2 ¸d È for unsigned. Addition over fixed-point numbers is straightforward: it amounts to addition over (signed) integers. Multiplication is more complicated as it results in a fixed-point number with 2 • ¸d bits representing the result's fractional part. The solution is an extra operation that truncates ¸d bits from the computed product. For the fixed-point number x = x 1 • 2 ¸d + x 2 , we define the truncation operation as ÂxÊ := x 1 , which is equivalent to a right-shift by ¸d bits of x.
Masking [5,16], the most widely used countermeasure against DPA, is a form of secret sharing [46] in which a secret is split into shares that can be combined using a suitable function to recover the secret. Let Z L be a finite ring of L elements. A (t + 1)-sharing of an element x oe Z L is a (t + 1)-tuple ÈxÍ = Èx 0 , . . . , x t Í oe Z t+1 L such that x 0 ı . . . ı x t = x and x i oe $ Z L for i oe [0, t), where ı oe {+, ü}. Symbol + denotes ring addition, ü is bitwise XOR, and oe $ denotes uniform random selection of an element from a set. Intuitively, t of the shares are drawn at random, and the (t + 1)-th share is computed from x and the rest of the shares. If ı = +, we speak of (t + 1)-arithmetic sharing and denote the (t + 1)-tuple by ÈxÍ L . If ı = ü, we speak of (t + 1)-Boolean sharing and denote the (t + 1)-tuple by ÈxÍ B . Unless stated otherwise, we assume (t + 1)-arithmetic sharings, or simply sharings, over Z L and write ÈxÍ. In rest of the paper we use masking and sharing interchangeably.
We call each element of a sharing ÈxÍ a share and denote the i-th share by ÈxÍ i . Given a sharing ÈxÍ, we denote its set of shares by S x . We use uppercase letters for matrices and vectors, and lowercase for scalars. Sharings of matrices and vectors are defined as pointwise sharings of their elements. For an n ◊ m matrix
Our proposed algorithms use masking as the DPA countermeasure [5,16]. Ishai NN inference can be organized as a sequence of operations, each applied layer after layer, giving it a compositional structure. Motivated by this characteristic of NN inference, we provide a set of secure basic NN operations which can in turn be securely composed into full NN inference algorithms. The standard notion of tprobing security, however, does not guarantee that the composition of t-probing secure functions is also secure [8]. In this paper, we prove all our algorithms secure under the notion of strong non-interference (SNI) [2] that enables reasoning about security in a compositional fashion. Gadgets, i.e., fundamental units of a larger con-struction, whose inputs are (t + 1)-sharings and that are shown to satisfy SNI, can be composed into algorithms that satisfy probing security.
Broadly, strong non-interference di ers from the weaker notion of non-interference (NI) (which is a rephrased notion of t-probing security proposed after the latter) by distinguishing output shares from intermediate shares (for NI the output shares are also considered to be intermediate). When output shares are considered in isolation, their joint distribution must be uniform, i.e., they must be independent of the input shares. When considered in conjunction with intermediate shares, their joint distribution may only depend on as many input shares as the number of intermediate shares considered. These two properties allow SNI gadgets to be composed safely with other NI gadgets in a construction, as their output shares reveal no information on their input shares. We restate (and slightly reformulate) here the notions of NI and SNI, originally introduced by Barthe et al. [2].
and the shares in V can be perfectly simulated from ÈA 0 , . . . , A n≠1 Í.
Èx 0 Í, . . . , Èx n≠1 Í and output sharing ÈoÍ. G is t-strongnon-interferent, t-SNI for short, if, for every set S ™ S o of at most t output shares and every set V of t Õ := t≠ |S| intermediate shares, there exist n sets A 0 , . . . , A n≠1 such that, for all i,
and the shares in V and S can be perfectly simulated from ÈA 0 , . . . , A n≠1 Í.
2-sharing into the result sharing ÈzÍ. It is easy to see that both gadgets are correct: recombining the sharing ÈzÍ by computing ÈzÍ 0 + ÈzÍ 1 results in x + y for both gadgets. The gadget on the left is 1-NI as each of the intermediate results depends on at most one of the shares of each input sharing ÈxÍ, ÈyÍ. More precisely, using Definition 1 with n = 2 and t = 1, for the intermediate share ÈzÍ 0 we have that it can be simulated by the 2-tuple of sets ÈA 0 , A 1 Í = È{ÈxÍ 0 }, {ÈyÍ 0 }Í. The same can be shown for ÈzÍ 1 and therefore the gadget is 1-NI. The same gadget is not, however, 1-SNI: using Definition 2 with n = 2 and t = 1, for the output share set S = {ÈzÍ 0 } we have
but the share ÈzÍ 0 oe S cannot be simulated from Èÿ, ÿÍ.
In order to turn the shared addition algorithm into a 1-SNI gadget, an additional source of fresh randomness is required, denoted r in the gadget on the right. The intermediate shares ÈwÍ 0 and ÈwÍ 1 are defined using this random value and can thus be simulated from the empty set, which settles the case S = ÿ in Definition 2. For the case S = {ÈzÍ 0 }, we get as above: t Õ = 0, hence
However, unlike with the gadget on the left, ÈzÍ 0 can be simulated from the empty set: we have ÈzÍ 0 = (ÈxÍ 0 ≠ r) + ÈyÍ 0 . Since r is uniformly sampled from Z L , this output share is uniform, too. The same can be shown for the case S = {ÈzÍ 1 }.
given 2-sharings ÈxÍ and ÈyÍ, return 2-sharing ÈzÍ s.t. z = x + y. The gadget on the right receives an additional input, r oe $ Z L .
To see why NI is not composable, consider a call to the addition gadget on the left above, followed by a call to another gadget, name it G, with input sharings ÈzÍ, ÈxÍ. Under NI, an intermediate result in G that can be perfectly simulated from shares ÈzÍ 0 and ÈxÍ 1 does not reveal any information on neither x nor z. In this case however, due to the preceding addition gadget we have that ÈzÍ 0 = ÈxÍ 0 + ÈyÍ 0 , which implies that the ability to simulate ÈzÍ 0 and ÈxÍ 1 results in leakage of the value of x. In the rest of this paper we focus on devising gadgets that are 1-SNI and therefore lend themselves to implementing secure NN inference.
In this section we present our masking scheme for secure Neural Network (NN) inference. The main ideas behind our approach are to use a finite ring of integers to represent numeric values as fixed-point numbers, to arithmetically mask this representation, and finally to design operations that take masked representations of numeric values as input, and return them as output.
The masked NN hold their masked parameters. At each inference round, the masked NN must mask the unshared input and refresh the parameters' masks (but never recover them). In order to design operations over masked representations of fixed-point values, we begin with gadgets for basic operations (primitives) common in NN inference. We show masked implementations of these primitives and prove them to be 1-SNI. An intermediate result is the value stemming from a primitive operation in an algorithm's statement. In the case of multiple operations in a single statement, evaluation order is dictated first by parentheses, in their absence by the "multiplication-before-addition" rule, and is otherwise left-to-right. We provide some security proofs and lemma statements in the main paper and include the rest of the proofs in the Appendix, along with auxiliary shared algorithms. The correctness of our algorithms follows directly from recombining their output shares; the correctness of our constructions follows by composing correct gadgets. We then give examples of masking the computation of network layers by composing suitable masked gadgets for the basic operations. Crucially, we tap into the strength of SNI, which guarantees that such compositions preserve the security properties a orded by masking. Finally, we give an example full construction by implementing a MLP.
For our secure NN inference, we use a finite ring (Z L , +, •) of integers to represent signed fixed-point arithmetic. An integer x oe Z L with ¸d bits allocated for its fractional part, where ¸d < ¸:= log 2 L, represents the numeric value tc(x) 2 ¸d where tc(x) interprets x in two's complement and returns its signed value. At the same time, x-being an element of Z L -readily lends itself to arithmetic masking, as described in Section 3.3, i.e., it can be split into shares ÈxÍ = Èx 0 , x 1 Í, where x 1 oe $ Z L and x 0 = x ≠ x 1 . The sharings of the gadgets that follow in the rest of this section represent signed fixed-point values.
Dot Product These operations are fundamental in the linear components of FNN. In MLP, each neuron computes a dot product between inputs and weight param-eters. In CNN, each feature is extracted by convolving part of the input with a kernel, i.e., by performing a dot product between the two. Algorithm 2 describes a masked dot product gadget. It uses sharing ÈcÍ as an accumulator and performs point-wise secure multiplication between the elements of its two input vectors.
Algorithm 2 DotProd(ÈAÍ, ÈBÍ, r): shared dot product
Algorithm 2 is similar to the secure multiplication gadget between two masked secrets [42]. It uses a single fresh random number to mask the accumulator variable. It is crucial that the accumulator is masked first, before proceeding with the point-wise masked multiplications. Alternatively, each masked multiplication can use a fresh random number, but this would require as many random numbers as the size of the vectors. The correctness of the algorithm follows by expanding ÈcÍ 0 + ÈcÍ 1 and arriving to c. We show below that the optimization of using a single random number does not compromise security:
Proof. We use Definition 2 with t = 1 and distinguish two cases. In the first, we consider the output shares, i.e., S = {ÈcÍ 0 } or S = {ÈcÍ 1 }, hence t Õ = 0 and V = A 0 = A 1 = ÿ. We have:
Due to the random value r, both ÈcÍ 0 and ÈcÍ 1 are uniform and thus can be perfectly simulated by the empty sets of shares ÈA 0 , A 1 Í.
In the second case we consider the intermediate shares, i.e., S = ÿ, hence t Õ = 1. We show in Table 1 all single intermediate shares forming set V (left), and the tuples of sets of input shares with cardinality at most 1 that can perfectly simulate them (right).
Sets of input shares Truncation The arithmetic 2-sharings we use for masked NN inference represent signed integers, which in turn when interpreted as fixed-point integers represent decimal numbers. As explained in Section 3.2, one of the benefits of using the fixed-point representation of decimals is that decimal addition and multiplication can be immediately performed in fixed-point by means of signed integer addition and multiplication. In the case of multiplication, an extra truncation step is, however, required in order to keep the number of bits that represent the fraction part constant. More precisely, the result of each signed integer multiplication must be followed by the truncation of the result's ¸d least significant bits.
In the context of multi-party computation of machine learning models, Mohassel et al. [35] show a probabilistically approximately correct way to truncate an arithmetic 2-sharing. Their approach is easy and e cient to implement, and it incurs a small error on the least significant bit of the reconstructed result, with high probability. We recall here a theorem from the prior work:
Broadly, Theorem 5 states that, under some assumptions and with high probability, the truncated individual shares denoted by ÈÂxÊÍ 0 and ÈÂxÊÍ 1 may have an o -by-one error from the un-shared truncated value ÂxÊ when recombined. That is, in contrast to all other shared algorithms in this paper, the truncation operation may incur a precision loss. Moreover, if the assumptions of Theorem 5 are not satisfied, the truncation operation may result in a faulty value altogether. Specifically, for the shared truncation to return a value o -by-one from its unshared counterpart, the unshared value x must fall into a specific region of Z L , parameterized by the value ¸t. Additionally the random number r used in the sharing ÈxÍ must be in the range [2 ¸t , 2 ¸≠¸t ), therefore the probability of a correct result increases exponentially with the value of ¸t. We discuss the choice of appropriate values for ¸t further in Section 8. Algorithm 3 shows our rendering of Theorem 5 as a 1-SNI algorithm. The main di erence between the two is the additional fresh randomness at the end of Algorithm 3, which guarantees 1-SNI.
Activation These functions constitute the nonlinear component of NN inference. In the context of this work we consider the rectifier function defined as ReLU (x) = max(0, x). A straightforward way to compute ReLU (x) in fixed-point arithmetic is via its derivative ReLU Õ : Z ae {0, 1}:
Computing ReLU Õ (x) essentially amounts to checking the sign of x. The fixed-point representation that we consider in this work uses signed integers, which are in turn represented in two's complement. The sign of the number therefore equals its most significant bit (MSB). However, the shared representation of the MSB is not simply given by the MSB of the two shares, as
In our approach we use known transformation functions between arithmetic and Boolean sharing. We transform the arithmetic 2-sharing ÈxÍ to its corresponding Boolean 2-sharing ÈxÍ B , which satisfies ÈxÍ B 0 üÈxÍ B 1 = ÈxÍ B . We then compute the MSB of x by bit extraction.
Algorithm 4 shows how to compute ReLU Õ . First it calls the ArithToBoolean gadget, to transform the sharing from arithmetic to Boolean. It then extracts the MSB of the Boolean shares. If their XOR is zero then-according to two's complement representation-
x is positive, so ReLU Õ must return 1, otherwise it must return 0. Hence, we negate one of the extracted bits (Line 3, via ü 1). Finally, to return a value that is arithmetically shared, we transform the Boolean 2-sharing of the extracted bit to an arithmetic sharing.
ArithToBoolean and BooleanToArith were originally introduced by Goubin [15] and shown to be 1-NI. They have since been optimized and extended to higherorders of protection [7] as well as shown to be 1-SNI [6]. The conversion gadgets require 2 fresh random numbers each, in order to guarantee 1-SNI, so Algorithm 4 expects an array R consisting of 4 fresh random numbers.
ReLU Õ is the first non-primitive gadget so far, constructed by composition of other 1-SNI gadgets. We provide a lemma useful in proving non-primitive gadgets.
Let G be a 1-SNI gadget over input sharings Èx 0 Í, . . . , Èx n≠1 Í, output sharing ÈoÍ. Each output share of G can be perfectly simulated from the empty set.
Theorem 7. The ReLU Õ gadget (Alg. 5) is 1-SNI.
The final step toward computing the ReLU activation is to multiply the result of ReLU Õ (x) with x. Algorithm 5 implements the shared ReLU activation, using the Mul gadget to multiply two sharings. Mul is well studied in the side-channel literature [20,42] and has been shown to be SNI. While Algorithm 5 performs a multiplication, notice that it is not followed by a truncation operation. This is due to the first operand of the multiplication being the result of ReLU Õ (x) which is either 0 or 1. This implies that the final multiplication result will be either 0 or x, neither of which requires truncating excess fractional bits. Algorithm 5 expects a vector of 5 fresh random numbers as parts of its inputs: 4 dedicated to the shared ReLU Õ computation, and 1 to Mul. after their linear and non-linear components and are meant to provide a summary statistic of nearby elements of a layer. A commonly used statistic is that of the maximum element, i.e., MaxPool. To compute MaxPool over n shared elements, we iteratively compute the maximum of two values: the i-th element and the maximum of the i ≠ 1 previous elements and return the result of the (n ≠ 1)st maximum operation.
The above scheme allows us to focus on the problem of computing the maximum of two values, max(x, y). We observe that ReLU is a special case of max with y = 0 and use the same idea of extracting the sign of a value, only this time of the di erence x ≠ y. We do this via the comparison function Cmp(x, y) := ReLU Õ (x ≠ y). The result of Cmp, i.e., the sign bit of x ≠ y, along with its negation can now be used to compute the maximum as max(x, y) = Cmp(x, y) • x + (Cmp(x, y) ü 1) • y.
Algorithm 6 implements shared MaxPool. At iteration i, the shared Cmp(ÈX i+1 Í, Èy i Í) gadget returns a tuple of sign sharings Ès i Í, Ès Õ i Í where
The sign sharings are multiplied with the current shared element ÈX i+1 Í and the previous maximum Èy i Í, resp., and their results are added to compute the maximum of the two.
As with ReLU , the two shared multiplications do not need to be followed by a shared truncation, as one of their operands is always a sign sharing, representing either 0 or 1. The Cmp gadget (shown in the Appendix) closely follows the shared ReLU Õ gadget: it prepends Al-gorithm 4 with a shared subtraction operation and appends it with an additional call to BooleanToArith for the complementary sign sharing. Due to these two additional operations, shared Cmp requires 6 fresh random numbers. Shared MaxPool requires 9 random numbers per binary max computation, for a total of 9(n ≠ 1) for a MaxPool of n elements.
Theorem 8 summarizes the security proofs for the remaining gadgets of basic operations.
We demonstrate how the gadgets for basic operations defined in the previous section can be composed into layer operations, and provide a full construction of a shared MLP. We compose the DotProd, Trunc, Add gadgets into the Linear gadget of Algorithm 7, which computes the linear component of a FC connected layer. To avoid unnecessary loss of precision we perform truncation once per neuron, after the dot product and before bias addition. The Linear gadget requires a number of fresh randoms linear in the layer's width m. A convolutional gadget can be constructed (and shown to be 1-SNI) using the same gadgets and invoking them in the same order (see Appendix). The di erence lies in the selection of inputs that are multiplied with the convolution kernel in the DotProd gadget.
Algorithm 7 Linear(ÈIÍ, ÈW Í, ÈBÍ, R): shared FC linear component
The Activation gadget, shown in Algorithm 8, is straightforward and computes the non-linear component of a layer by applying the ReLU gadget to all neurons of a layer. As each call to ReLU requires 5 fresh random numbers the total cost of the activation layer in terms of fresh randoms is 5m where m the layer's width.
3: return ÈZÍ
The layer operations are composed exclusively of 1-SNI gadgets. Thus, by Lemma 6, all their intermediate and output shares can be simulated by tuples containing empty sets of shares. The proof of security for the layer operations follows directly from this observation. Theorem 9. The Linear, Activation gadgets are 1-SNI.
Having access to 1-SNI layer operations, we can compose multiple layers in a larger chain construction and form a shared MLP. In Algorithm 9 we show a shared MLP with n shared inputs, a single hidden layer of width m and an output layer of width k. It requires (3 + 5)m + 3k fresh random numbers in total, i.e., linear in the size of the network's width. The precision loss that can be incurred in the network, when compared to its unmasked fixed-point counterpart, grows with the depth of the network, as each linear layer operation requires a truncation step. Similarly to the layer operations, the security of Algorithm 9 follows directly from the 1-SNI layer gadgets.
Algorithm 9 FNN: 2-shared MLP. (1 hidden layer)
In Section 5 we provided masked gadgets whose composition leads to masked FNN inference algorithms. We reasoned about their security in the probing model by showing the inference algorithms to be 1-SNI. This implies that an attacker probing 1 intermediate result of the masked computation cannot recover any informa-tion on the secret, i.e., the network's parameters. The probing model however, relies on some assumptions, e.g., that each intermediate result leaks independently [40]. In this section we investigate the leakage behavior of our proposed algorithm in practice, and experimentally validate its security.
This is a leakage evaluation methodology [45] that uses Welch's t-test to asses the security for implementations of masked algorithms. TVLA requires the collection of two power measurement datasets: one where the inputs to the masked implementation are fixed to a specific value, and one where the input of each measurement is random. We then compute the so-called fixed-vs-random t-test values for the two datasets on all points (i.e., samples) of the measurement traces and test the hypothesis that the traces in the two datasets have the same means on all points. High t-test values indicate violation of the null hypothesis, i.e., that the traces have the same means on all points. By increasing the degree of freedom of the t-test, i.e., the number of measurement traces in the datasets, the confidence on accepting or rejecting the null hypothesis also increases. Usually a predefined threshold is set to reject the null hypothesis based on the t-test value. In common industry standards for TVLA, the t-value threshold is set to |th| = 4.5. When the tvalues on all points of the traces are lower than the threshold, it confirms that there are no leakages on the traces. Attacking an implementation whose t-test values lie within |th| is expected to have the same success rate as a random guess [43].
Experimental Setup We use a STM32F407IG 32bit ARM Cortex-M4 CPU, clocked at 168Mhz and with 1MB of internal flash memory, to execute our masked implementations as bare-metal applications. We collect power measurements using a LeCroy oscilloscope with a sampling rate of 1GS/s (GS =giga-samples) in order to collect approximately 6 samples per clock cycle.
The CPU is part of the Pinata Development board [41], which bypasses the on-board voltage regulator and provides less-noisy power signals.
Figure 2 shows a diagram of our collection setup. A control unit (a PC) generates the input sharings as well as any random sources required by the gadgets, and communicates them to the board. The board reads the parameters and sets a trigger signal, prior to and after executing the masked algorithm, and communicates the algorithm's result to the control. The oscilloscope captures the power measurement within the trigger window and communicates it to the control unit: we call each power measurement collected in this way a trace. For reproducibility purposes, we use an AES-based seeded pseudo-random number generator (PRNG) to generate the random numbers required for the input and parameter sharings and for the fresh random numbers of the gadget computation. Evaluation We evaluate a masked C implementation of a MLP similar to the one presented in Algorithm 9, with an architecture of 2 inputs, a single hidden layer of 2 neurons, and an output layer of width 2. We chose this minimal architecture to keep the number of samples collected for each trace small, while still being able to exercise all the basic and layer operations described in Section 5. Following Algorithm 9, our implementation expects as input the input and parameter sharings (ÈIÍ, ÈW 1Í, ÈB1Í etc.) as well as the fresh random numbers (R), and outputs a classification probability vector. The sharings and fresh randoms are generated o ine (in the control unit). In our TVLA we use the non-specific t-test, which makes no assumptions on the leakage model of the board and targets all intermediate shares. During trace collection we interleave (at random) the traces of the fixed and random datasets to avoid any external influences or dependencies on the internal state of the board.
Figure 3 shows fixed vs random t-test results for the whole inference computation of the MLP described in the previous paragraph. We have performed three experiments. In the first, called PRNG-O , instead of using the PRNG to supply the random values used in sharings and the fresh random numbers, we set these values to a constant. This is the baseline, as the lack of randomness in the sharings should result in high leakage. This conjecture is confirmed in Figure 3 (a): at 100K traces, we see clear deviations from set threshold |th| = 4.5, for samples throughout the trace, rejecting the null hypothesis and indicating the existence of power leakage.
In the second experiment, called PRNG-On, we use the seeded PRNG to supply the random values. The result is shown in Figure 3 (b): at 1 million traces, there is no indication of exploitable power leakage, as the t-test values fall within the desired threshold, for all sample points along the whole trace, validating that our masked gadgets do eliminate first-order power leakage. In the third experiment, we increase the order of the t-test in the TVLA. A second-order TVLA checks the hypothesis that two datasets have the same second statistical moments (i.e., no second-order leakage). Figure 3 (c) invalidates this hypothesis by showing values outside of th, which indicate that there are still second-order leakages in the traces. Since our implementations are 1-SNI, they do not have first-order leakage but do not protect against second-order leakage. With this experiment we validate the correctness of our measurement setup and the security protection of our gadgets.
In Section 5.3 we gave an example of a shared MLP with n inputs, a single hidden layer of width m and an output layer of width k and found that, for an inference round, masking of the shared layer operations requires a number of randoms linear in the layer's width. In addition to masking operations, at each inference round the inputs as well as the weights of the MLP must be masked with fresh random numbers, increasing the randomness requirements to linear in the number of parameters of the MLP. Random numbers are an expensive resource, as their generation requires either hardware support or frequent invocation of PRNG routines.
In this section we describe our approach to tightening the number of required fresh randoms for masking of both the NN parameters and operations involved in a layer. The key observation that enables this tightening is that within a layer, each neuron's (in the case of MLP) or feature's (in the case of CNN) computation can be done in parallel. The main ideas behind our tightening approach are i) to re-use the same random numbers in the sharings of the parameters of a layer, and ii) to re-use the fresh random numbers in the gadgets across di erent neurons/features of the same layer. We show that, despite aggressively re-using random numbers, the gadgets of Section 5 can be made to satisfy 1-SNI.
We begin with tightening the number of randoms in a layer's parameter sharings and propose to use a single random number for all parameters of a layer. We focus on the DotProd gadget as both MLP and CNN compute their linear components first. Theorem 10 formalizes the idea behind using a single random number in sharings of parameters of a layer and a single random number in sharings of inputs. Its proof is similar to that of Theorem 4 after swapping the parameter (and input) shares for a single random number.
We use Definition 2 with t = 1 and distinguish two cases. In the first, we consider the output shares, i.e., S = {ÈcÍ 0 } or S = {ÈcÍ 1 }, hence t Õ = 0 and V = A 0 = A 1 = ÿ. We have:
Due to the random value r, both ÈcÍ 0 and ÈcÍ 1 are uniform and can be perfectly simulated by the empty sets of shares ÈA 0 , A 1 Í.
In the second case we consider the intermediate shares, i.e., S = ÿ, hence t Õ = 1. We show in Table 1 all single intermediate shares forming set V (left), and the tuples of sets of input shares with cardinality at most 1 that can perfectly simulate them (right).
Sets of input shares
Sets of input shares that can perfectly simulate the intermediate shares.
We now turn to tightening the fresh random numbers required for sharing layer operations. We discuss the Linear gadget of MLP; the goal is to use the same fresh random values across its neurons. More precisely, the DotProd, Add and Trunc gadgets, which Linear is composed of, can use the same fresh random values at each neuron. The reason is that their computations are completely parallel. We can therefore rewrite Algorithm 7 so that it requires R oe $ Z 3 L instead of R oe $ Z 3m L and re-uses the random values R 0 , R 1 and R 2 at each invocation of DotProd, Add and Trunc respectively, across the m neurons. A similar type of reasoning can be applied to the Activation gadget. All invocations of ReLU at di erent neurons can use the same random sources. Therefore we can rewrite Algorithm 8 so that it requires
Following the above observations, a theorem similar to Theorem 9 can be easily shown for the tightened version of the Linear and Activation gadgets.
We make two remarks. First, the bias parameter tightening does not compromise 1-SNI of the Add gadget as all the calls to Add are invoked in parallel, and the results of DotProd are masked by R 0 . Second, the results of each neuron of a layer depend on the same fresh random numbers. This satisfies the condition of Theorem 10 that both its inputs (i.e., the results of the previous layer) and its parameters can use a single fresh random value each. We can therefore apply the tightening strategy in a chain of layers.
Table 3 compares the randomness requirements of the original gadgets described in Section 5 and their tightened versions described in this section, which re-use random numbers. The original layer gadgets (Linear, Activation) require a number of randoms linear in their parameter count. The tightened versions require a constant number of randoms, without compromising the 1-SNI security property of the gadgets. We have experimentally confirmed that the tightening has no discernible impact on the leakage behavior of our implementations. We have performed the same fixed-vsrandom t-test experiment as in Section 6 with PRNGon for the tightened implementation and for 1 million traces. Figure 3 (d) shows that, as in the original version, there is no indication of power leakage.
The tightened Linear and Activation gadgets can be readily used in CNN inference. The MaxPool gadget, however, is not amenable to our tightening approach. The reason is that the output of MaxPool depends on the intermediate shares it introduces (which hold the max value up to the i-th iteration). Using the same random values for these intermediate shares would cancel
Total
Table 3. Randomness requirements for a layer of n inputs and m neurons, invoking the Linear and Activation gadgets.
the masks and result in leakage. In practice, this is not problematic as MaxPool is commonly performed over 4 elements, so its randomness requirements do not depend on the number of CNN parameters. Multiple invocation of the MaxPool gadget can reuse the same random numbers, as their results are independent of each other.
In this section we investigate the performance characteristics of our proposed gadgets and pursue the following questions: 1) How much overhead does the shared NN inference incur, compared to its unshared counterpart?, 2) How much does the shared NN inference impact the model's accuracy?
We describe first a simple computational cost model and use it to provide a complexity analysis for shared and unshared inference. The complexity model counts primitive operations of the same type; it ignores loads and stores from memory. It consist of 4 types, namely addition, multiplication, bitwise, and comparison operations. We apply the model at the layer level, and compare the operation counts per type, for the unshared and shared NN inference. We focus our analysis on FC layers and the MaxPool operation. The gadgets used in FC layers also appear in convolution layers, so their results transfer directly. Since our shared NN gadgets rely on fixed-point representation of the numeric values of the network, we use the fixed-point representation for unshared NN inference to perform a fair comparison. Each cell of Table 4 shows how often each type of operation (shown in columns) occurs, for every unshared subcomponent (shown in rows) of. We have implemented the unshared ReLU as (x > 0) ú x, to allow a fair comparison with the shared ReLU gadget. The truncation operation is implemented as a right-shift. Asymp- totically, for a FC layer, the cost of inference is linear in the product of its number of inputs and its width. The rows in Table 5 are now the shared gadgets we presented in Section 5. The operation counts per type can be inferred from the corresponding gadget. For example, the Add gadget is invoked m times and performs 4 primitive additions; therefore, its entry in column ADD has a count of 4 • m. Notice that there is no CMP operation, as we perform comparison by 0 by means of the ReLU Õ or Cmp gadgets. ReLU and MaxPool are the most complicated gadgets as they make use of the Mul, BooleanToArith and ArithToBoolean (the implementations of the conversion and comparison gadgets along with a detailed operation breakdown of all basic gadgets are shown in Appendices A, C. Asymptotically, the cost of shared NN inference is still linear in the layer size. However, the dominating factor m • n is multiplied by a constant factor of 4.
We evaluate the performance of our unshared, shared and tightened implementations of NN inference in terms of runtime and accuracy. We investigate whether the operation overhead incurred by the sharing matches the slowdown predicted by our simple complexity model in the previous section, and whether sharing influences the accuracy of NN models.
We have trained NN of di erent classes (MLP, CNN, BNN) in PyTorch on the MNIST dataset, extracted their floating-point parameters, and converted them to fixed-point parameters for shared inference. We choose a collection of NN ranging from standard networks for MNIST [30], to models that were used in prior work related to secure inference [10,35,53]. We scale up these networks by increasing the depth, width, and number of channels to further evaluate how our algorithms respond. The architectures we work with are common in the domain of HAR [18].
Inference Library We have implemented the shared algorithms for secure inference in a C library 1 .
The library includes the unshared, fixed-point counterparts of the algorithms, which we use as a baseline. For each NN model we provide four inference implementations. The unshared implementation is straightforward and implements ReLU (x) as (x > 0) • x to match the behavior of the shared implementation. The shared implementations follow the algorithms of Section 5 and use a software PRNG (KECCAK-based [4]) to generate the random numbers that they require for sharing the inputs and parameters, as well as those for layer operations. We have implemented three shared versions. shared-prngoff doesn't generate random values but uses constants in their place. The intention of this version is twofold: it is meant to separate the cost of sharing from the cost of randomness generation, and it serves as a baseline for comparing implementations with di erent randomness requirements. shared-original uses a number of randoms linear in the size of each layer and in the number of the model's parameters. Finally, shared-tightened uses a constant number of random numbers for each layer as well as for the parameters of each layer, as described in Table 3 of Section 7.
We represent fixed-point numbers using signed 32bit integers. Our shared implementations substitute each fixed-point value by a tuple of shared values, effectively doubling the memory requirements of their unshared counterparts. We defer a space optimized version of our library for future work.
We recall from Section 5.2 that the Trunc gadget's probability of correctness is parametric to the value ¸t < ¸= 32, and discuss how to choose values for ¸t, ¸d. ¸t constrains the range of integers in Z L that can be shared. In detail, only the integers in [0, 2 ¸t ) fi [2 ¸≠¸t , 2 ¸d ) = [≠1025, 1025). Accuracy Our goal is to evaluate the impact of sharing, and specifically the additional precision losses of shared truncation, in the accuracy performance of fixed-point NN inference. We use the accuracy % of unshared as our baseline and report the di erences in accuracy % with the baseline for the shared-original and shared-tightened implementations (columns Acc. " in Table 6). We observe small di erences in the range [≠0.33, 0.19] % (negative numbers indicate losses).
Neither the class nor the architecture of NN suggest trends for the accuracy ". Tightening the randomness requirements has no significant impact on the accuracy " as the tightened algorithms perform the same number of truncation operations, but on di erent random values. This is reflected in the small di erences in the accuracy " between shared-original and sharedtightened. Optimizing the accuracy of the unshared DNN by means of training, and translating the models from floating-point to fixed-point arithmetic constitute orthogonal concerns. We omit results on the accuracy of shared-prng-off since its main goal is to provide runtime insights.
Runtime We measure the runtime of the four implementations of each DNN in a desktop Intel-i7-4770@3.40GHz with 16GB RAM. Working with x86 allows us to evaluate larger networks so we use it to investigate how our algorithms scale. We measure runtime in cycles using CPU time-stamp counters and report them in Table 6. Figure 4 shows the slowdown of the shared implementations relative to the unshared version. We note that in MLP models shared-prng-off is about 5.5 times slower than unshared across all networks, which matches the complexity analysis of the previous section. shared-original incurs slowdowns larger than an order of magnitude in all MLP. shared-tightened reverses the "trend": compared to unshared its slowdown is negligibly larger than that of shared-prng-off compared to unshared. We also report in Figure 4 the slowdown of a MLP executed in ARM Cortex-M4, as embedded devices are the nominal target of power analysis attacks. Due to memory limitations, the MLP executed in ARM expects 250 inputs. The depth and width of hidden layers as well as the underlying execution platform have no impact on the MLP implementations' slowdown as it remains the same across MLP models and platforms. The BNN implementation's slowdown follow that of the MLP models, which is expected as our library handles BNN by setting their weight parameters as either -1 or 1, and otherwise treats them as regular MLP.
CNN models demonstrate di erent slowdown characteristics when compared to MLP, but also between di erent CNN architectures. Broadly in CNN, sharedprng-off shows smaller slowdown that in MLP. We attribute this to the better data locality between subsequent calls to the dot product operation of a convolutional layer. The slowdown of shared-original in CNN is again smaller when compared to its equivalent of MLP (an order of magnitude). CNN models have a vastly smaller number of parameters compared to MLP and require less random values to mask them in sharedoriginal. shared-tightened in CNN has the same impact as in MLP, i.e., it makes the slowdown minimally larger than that of shared-prng-off. Finally, we see that between the two CNN models, the one with fewer FC layers (and total number of neurons) performs much faster, despite the fact that it's convolution layers have a much larger number of channels.
The above trends demonstrate that shared convolution layers perform invariably better than FC layers. We consider the reported slowdowns to be encouraging toward the general direction of application of masking in NN inference. The 2.3-5.6◊ slowdown of shared NN inference is lower than the slowdowns su ered by com-monly encountered masked cryptographic algorithms, e.g., masked AES [42], in software implementations. [51]. BoMaNet's masked circuits have been used to implement only MLP architectures and no formal guarantees of its masked circuits is provided. The constructions they provide are shown to experimentally satisfy 1-NI security, however in principle, we conjecture they could be refined to also satisfy 1-SNI.
BNN MLP inference utilizes the fact that parameters are binary values perform space and time optimizations. As an example, a dot product computation over n elements can be carried out as an XNOR operation between two n-bit registers. The constructions in BoMaNet are specific to such BNN characteristics and do not extend to non-binarized NN that have parameters of arbitrary values. While BoMaNet's masked adder and MSB extraction for the ReLU computation could be extended to non-binarized NN, implementing masked multiplication by means of LUT is prohibited when dealing with arbitrary weight values. On the flipside, while our library can implement NN inference for any value representable in fixed-point arithmetic, including BNN (by simply representing weights as fixedpoint 1 or -1), our gadgets are not optimized to exploit the binary weights (e.g., by performing dot product via a single XNOR). In terms of randomness requirements, BoMaNet does not exploit the layered structure of NN inference to reduce its randomness requirements. Each secret parameter requires a fresh random value to be masked and so does each non-linear operation. Finally, BoMaNet's secure circuits have been used to implement a 2-layer MLP and have not been applied to CNN.
BoMaNet uses additional flip-flops to partially account for known issues related to hardware glitches in CMOS circuitry [33]. Our work considers platform specific leakage characteristics, e.g., glitches or transition based leakage [1], an orthogonal question.
Secure Multi-Party Computation (MPC) A large body of work uses secret sharing techniques for NN and machine learning models in the context of MPC, both for training [28,35,53] and inference [21,22,52].
Masking and MPC target orthogonal security properties, e.g., a party in MPC might be the exclusive owner of a secret that must be protected against DPA. In masking there is a single party that holds all t+1 shares at all times, and an attacker observing at most t shares must learn no information about the secret. In MPC, there are at least two parties and a number of shares. An attacker, being either one of the parties or an external observer of the parties' communication, must at no point of hold all shares of the secret. Compared to masking, MPC incurs additional computational overhead due to communication and cryptographic assumptions which are not present in masking. Without including the communication overhead, prior work on secure inference [35,53] reported total runtimes of 4.88 and 0.043 seconds per inference for a MLP with two hidden layers of 128 neurons. The cycles of our shared-tightened implementation (MLP 128-128 of Table 6) translate to runtime of 0.001753 seconds, i.e., at least an order of magnitude faster than the MPC based approaches.
We have proposed a library of masked gadgets, resistant against DPA, that are the first to our knowledge that can be safely composed into full MLP and CNN constructions. We demonstrated the security of our construction formally and experimentally. We described how to reduce the random number requirements of our NN constructions, and showcased that they incur about a 2-5◊ slowdown to their unmasked counterparts, with minimal, if any, accuracy impairment. We set as future work to apply our library to more complex DNN targeting advanced datasets, as well as expanding to di erent architectures such as recurrent NN.
Algorithms 10 [6], 11 [6], 12 are used by the gadgets that appear in the main paper. for j from 0 to m do 3:
ÈX i,j Í := DotProd(ÈKÍ, ÈI i≠h:i+h,j≠w:j+w Í, R 3(i+m•j) )
ÈY i,j Í := Trunc(ÈX i,j Í, R 3(i+m•j)+1 )
ÈZ i,j Í := Add(ÈY i,j Í, Èb i Í, R 3(i+m•j)+2 )
We provide here the proofs for the lemmas and theorems stated in the main paper. We also provide proofs of security for the auxiliary algorithms of Appendix A. The numbers of the theorems and lemmas correspond to the numbers of theorems and lemmas in the main paper. Proof : We distinguish two cases. In the first, we consider the output shares, i.e., S = {ÈyÍ 0 } or S = {ÈyÍ 1 }, hence t Õ = 0 and V = A 0 = ÿ, where ÈyÍ 0 = ÈBooleanToArith(ÈwÍ B , R 2 , R 3 )Í 0 and ÈyÍ 1 = ÈBooleanToArith(ÈwÍ B , R 2 , R 3 )Í 1 . From Lemma 6 we have that both ÈyÍ 0 , ÈyÍ 1 can be simulated by ÈA 0 Í. In the second case, we consider the intermediate shares, i.e., S = ÿ, hence t Õ = 1. From Lemma 6 we have that both ÈzÍ 0 , ÈzÍ 1 can be simulated by ÈÿÍ. Consequently, ÈwÍ 0 , ÈwÍ 1 can also be simulated by ÈÿÍ as they only depend on shares of ÈzÍ. Proof : From Lemma 6 and Lemma 14, Lemma 15 we have that the shares Èy i Í, Ès i Í i , Ès Õ i Í, Èw i Í, (i oe {0, . . . , n ≠ 1}) can be perfectly simulated by the empty set of shares. We distinguish two cases: