domain: phys spi

text:
Antonin Borot

Arnaud Malvache

Xiowei Chen

Aurélie Jullien

Jean-Paul Geindre

Patrick Audebert

Gérard Mourou

Fabien Quéré

Rodrigo Lopez-Martens

Attosecond control of collective electron motion in plasmas

Today, light fields of controlled and measured waveform can be used to guide electron motion in atoms and molecules with attosecond precision. Here, we demonstrate attosecond control of collective electron motion in plasmas driven by extreme intensity (≈ 10 18 W/cm 2 ) light fields. Controlled few-cycle near-infrared light waves are tightly focused at the interface between vacuum and a solid-density plasma, where they launch and guide subcycle motion of electrons from the plasma with characteristic energies in the multi-kiloelectronvolt range -two orders of magnitude more than what has been achieved so far in atoms and molecules. Basic spectroscopy of the coherent extreme ultraviolet radiation emerging from the light-plasma interaction allows us to probe this collective motion of charge with sub-100-attosecond resolution. This is an important step towards attosecond control of charge dynamics in laser-driven plasma experiments.

 and condensed matter [9, 10] -with typical energies * These authors contributed equally to this work.

1

).

Light-driven plasma mirrors

When an intense femtosecond laser pulse interacts with a solid, its rising edge strongly ionizes the surface atoms, creating a layer of plasma with near-solid electronic density (∼ 10 23 cm -3 ), which becomes highly reflectivea so-called plasma mirror -for light at wavelengths greater than a few tens of nanometers [START_REF] Rolland | Generation of 130-fsec midinfrared pulses[END_REF][START_REF] Kapteyn | Prepulse energy suppression for high-energy ultrashort pulses using self-induced plasma shuttering[END_REF][START_REF] Doumy | Complete characterization of a plasma mirror for the production of high-contrast ultraintense laser pulses[END_REF][START_REF] Dromey | The plasma mirror -A subpicosecond optical switch for ultrahigh power lasers[END_REF][START_REF] Thaury | Plasma mirrors for ultrahigh-intensity optics[END_REF].

During the interaction with the pulse, the plasma layer can only expand by a small fraction of the optical laser wavelength, λL, which leads to the formation of a very sharp interface with vacuum extending over a distance λL (Fig. 1b), typically of the order of a few tens of nanometers. At this steep plasma-vacuum interface, the laser field behaves like in the usual case of light reflection at a metallic surface. The total electric-field inside the plasma is zero due to screening by the dense conducting plasma.

On a macroscopic scale, the boundary conditions on the oscillating electromagnetic field at the interface imply that the component Et of the laser electric field parallel to the surface is continuous and therefore vanishes. In contrast, its component En normal to the surface can exhibit a discontinuity : it has an oscillation amplitude that jumps from 0, in the conducting medium, to a maximum of 2EL sin θ, where θ is the incidence angle of the laser with respect to the target normal. At light intensities close to 10 18 W/cm 2 , the amplitude of the laser electric-field normal to the plasma-vacuum interface can thus exceed the teravolt per meter and therefore accelerate electrons from the plasma up to very high kinetic energies on the time scale of a single optical cycle.

On a microscopic scale, there is of course no such field discontinuity. Electrons at the plasma surface are periodically dragged in and out of the target by the En component of the oscillating laser field, while the much heavier ions of the plasma are left behind. This creates a charge separation field on the time scale of the laser cycle, which screens En over a finite length. For everyday light intensities, this screening length is very small, typically on the Angström scale, hence justifying the usual boundary condition at conductor surfaces. In the intense laser field, however, the excursion of surface electrons into vacuum can reach several tens of nanometers (Fig. 1b) -a significant fraction of the laser wavelength -with kinetic energies of the order of the ponderomotive energy Up = e 2 E 2 n /4mω 2 L (e and m electron charge and mass, ωL laser angular frequency) in the light field -typically several tens of kiloelectronvolts (keV) for light intensities in the range 10 17 to 10 18 W/cm 2 . In our experiment, we probe this large-amplitude collective motion of charge with sub-100-as resolution. This we achieve by recording the laser waveform-dependent emission of extreme-ultraviolet (XUV) light triggered by the subcycle motion of the surface electrons within the solid plasma layer.

Coherent wake emission

As shown in Fig. 1b, electrons at the plasma surface are pulled out into vacuum when, during each laser cycle, the force -eEn exerted by the laser electric-field points toward vacuum. Later in the laser cycle, as En decreases in magnitude, some of the electrons involved in the screening are pushed back towards the dense plasma because the space charge field they experience from other electrons exceeds the laser field En. Finally, when En changes sign, all the electrons are accelerated back towards the plasma layer. Once they pass the region of the plasma above critical density Nc, where the laser light is screened by the high electronic density, they escape the grip of the laser field and travel field free. For 800 nm light, this occurs at a depth x in the plasma, where the local density is n(x) > Nc = m 0 ω 2 L /e 2 = 1.7 × 10 21 cm -3 (Fig. 1b). During this process, electrons carry away the energy they acquired in the light field: this is the so-called Brunel absorption [START_REF] Brunel | Not-so-resonant, resonant absorption[END_REF][START_REF] Bonnaud | Laser interaction with a sharp-edged overdense plasma[END_REF]. The combined effect of both the laser and space charge fields is to make faster electrons return to the plasma surface at later times during the laser cycle. In the overdense region of the plasma, however, faster electrons can now freely catch up with slower moving electrons that returned earlier during the cycle: as a result, Brunel electrons pulled out of the plasma around the same time in the laser cycle eventually bunch together to form a local electron density peak of a few Nc inside the plasma [START_REF] Thaury | High-order harmonic and attosecond pulse generation on plasma mirrors: basic mechanisms[END_REF]. Lower energy electrons bunch earlier at lower electronic densities closer to the plasma surface and higher energy electrons bunch later at higher electronic densities deeper inside the plasma layer. This electron density peak has a typical duration of the order of 100 as and travels across the plasma at typical velocities ranging from 0.1 to 0.3 times the speed of light for the laser intensities considered here [START_REF] Thaury | High-order harmonic and attosecond pulse generation on plasma mirrors: basic mechanisms[END_REF]. In its wake, it pushes the background plasma electrons that collectively oscillate at the local plasma frequency ωp(x) = n(x)e 2 /m 0. In the steep plasma density gradient, these plasma oscillations, which are initially longitudinal electrostatic modes, can couple to transverse electromagnetic modes and thus radiate light at the plasma frequency ωp(x) [START_REF] Kruer | The physics of laser plasma interaction[END_REF]. This can be seen as the time-reverse of resonant absorption [START_REF] Hinkel-Lipsker | Analytic expressions for mode conversion in a plasma with a linear density profile[END_REF], where laser light is partially converted into collective electron oscillations in a gradient of plasma density (both effects correspond to linear mode conversion mechanisms [START_REF] Hinkel-Lipsker | Analytic expressions for mode conversion in a plasma with a linear density profile[END_REF][START_REF] Sheng | Emission of electromagnetic pulses from laser wakefields through linear mode conversion[END_REF]). This emission, known as coherent wake emission or CWE [START_REF] Quéré | Coherent Wake Emission of High-Order Harmonics from Overdense Plasmas[END_REF], consists of a sub-femtosecond burst of coherent radiation, superimposed with the laser light reflected at the plasma surface [START_REF] Nomura | Attosecond phase locking of harmonics emitted from laser-produced plasmas[END_REF], with a spectrum extending into the extreme ultraviolet (XUV) up to ωmax = N solid /Nc ωL, emitted from the region of solid plasma density N solid (Fig. 1b). Experimentally, the measured CWE spectrum results from the interference in time of successive light bursts triggered by the attosecond bunching of returning Brunel electrons inside the plasma with each laser cycle (Fig. 1c-d). The total emission spectrum can therefore be expressed as :

S(ω) = N j=1 sj(ω)e iωτ j 2 (1)
where sj(ω) is the complex spectrum emitted in the j th laser cycle, corresponding to an attosecond pulse centered at time τj. When driven by a laser pulse containing many wave cycles, CWE consists of a long train of attosecond pulses -one per laser cycle -and a measured XUV spectrum made up of odd and even harmonics of the laser frequency ωL. In our experiment, we measure the CWE spectrum generated by a laser waveform containing only a few controlled oscillations of NIR light. We exploit the fact that the waveform-driven collective dynamics of Brunel electrons are directly mapped onto the time structure of the emitted attosecond pulse train or APT (Fig. 1b-c) and that even subtle changes in the subcycle charge dynamics induced by different NIR waveforms can lead to dramatic changes in the measured XUV spectrum (Fig. 1d) [START_REF] Heissler | Toward single attosecond pulses using harmonic emission from solid-density plasmas[END_REF].

Waveform-dependent emission spectra

In the experiment, we use p-polarized 5-femtosecond (FWHM), 0.8-micron wavelength laser pulses focused at oblique incidence down to 1.7 µm spot size onto a moving optically polished glass surface [START_REF] Borot | High-harmonic generation from plasma mirrors at kilohertz repetition rate[END_REF] at peak light intensities close to 10 18 W/cm 2 (more details in supporting online materials). The waveform of the laser electric-field can be written in complex form as EL(t) = E0 aL(t, α)e -i((ω L +αt/2τ 2 0 )t+φ 0) , where E0 is the peak electric-field strength, aL(t, α) is the normalized amplitude envelope, α the linear frequency chirp of the pulse, τ0 the Fourier-transform limited pulse duration, φ0 its carrier-envelope (CE) phase (defined on Fig. 1c) and ωL the carrier wave frequency (the variation of the pulse temporal width τ with α is detailed in supporting online materials). The CE phase drift of the laser system can be stabilized down to 200-milliradian (rms), corresponding to a sub-100-as jitter of the few-cycle NIR light waveform with respect to the pulse envelope.

Fig. 2b shows the measured CWE spectra in the 7ωL-10ωL spectral range as a function of the relative CE phase of Fourier-transform limited 5-fs laser pulses, i.e. with zero frequency chirp. Peaks separated by ωL are clearly observed, as one would expect in experiments using a many-cycle laser waveform. However, as the CE phase of the pulse changes, the positions of these harmonic-like peaks no longer correspond to integer multiples nωL of the laser frequency, but instead linearly drift with a slope of ≈ ωL/2π. Fig. 2 a-c-d display the same measurements performed for different frequency chirps, both positive and negative. These results

show that the effect of the CE phase on the CWE spectrum also depends on the frequency chirp of the NIR waveform. For α < 0, the peaks are slightly narrower and their position still drifts linearly with relative CE phase, while just changing the sign of the chirp (α > 0) almost suppresses the effect of the CE phase on the measured position of the peaks in the spectrum. The reproducible changes in the plasma emission spectrum induced by only π/10 changes in the CE phase of the driving laser field show that we control the collective plasma electron dynamics underlying CWE with sub-200 attosecond precision.

Collective attosecond electron dynamics

The spectroscopy of CWE provides information on the collective attosecond dynamics of Brunel electrons. To demonstrate this, we developed a simple model, inspired from the one developed in [START_REF] Brunel | Not-so-resonant, resonant absorption[END_REF] and similar to the one described in [START_REF] Heissler | Toward single attosecond pulses using harmonic emission from solid-density plasmas[END_REF], which gives direct insight into the measurements of Fig.

Moiré patterns

Measuring the sensitivity of CWE spectra (Fig. 2) to the waveform of the driving light provides a measure of how accurately we can control the ultrafast charge dynamics unfolding within the plasma. The sensitivity of the harmonic generation process to the CE phase results from the combination of two effects. First, due to the global temporal drift of the APT it induces, a change in the CE phase changes the intensities at which each individual attosecond XUV burst in the APT is generated. Second, a change in intensity modifies the subcycle emission time of each XUV burst because it changes the time it takes for the returning Brunel electrons to reach the dense part of the plasma where they cross and trigger CWE [START_REF] Quéré | Phase Properties of Laser High-Order Harmonics Generated on Plasma Mirrors[END_REF][START_REF] Thaury | Coherent dynamics of plasma mirrors[END_REF]. For a few-cycle pulse envelope, the combination of these two effects leads to a dependence of the APT time structure on the CE phase of the pulse. This effect is clearly visible in Fig. 3d-e, where the temporal spacings between individual attosecond pulses (i.e. the distances between vertical stripes) vary with the CE phase of the driving waveform. Using our model, we can calculate the whole CWE spectrum (from 2ωL to ω max p ), i.e. the Fourier transform of the APT of Fig. 3e , as a function of CE phase. The outcome of this calculation, displayed in Fig. 4a, is compared to the results of a much more comprehensive simulation, carried out using a 2D particle-in-cell (PIC) code (more details in supporting online materials), in Fig. 4b, showing a remarkable agreement. In both cases, spectra exhibit a central portion consisting of well-resolved harmonic-like peaks whose position in frequency linearly drifts with CE phase. This central portion corresponds to our experimental spectral detection window and here our model perfectly matches the experiment (Fig. 2b).

Another feature revealed by our model is that outside the experimental detection window, at both ends of the spectrum, the harmonic-like structure of CWE becomes blurred but still exhibits the same periodic dependence on the CE phase of the laser pulse. This global structure corresponds to a moiré pattern, a wellknow interference effect ubiquitously observed in nature [START_REF] Amidror | I The Theory of the Moiré Phenomenon[END_REF]. Indeed, a pair of attosecond pulses spaced by ∆ti = τi+1 -τi = TL + δti (with TL the laser period) in the APT produces a sinusoidal interference pattern in the frequency domain of periodicity ∆ωi = 2π/∆ti. The total spectrum originates from the superposition of such interference patterns between all the different pairs of attosecond pulses generated during the light-plasma interaction. It is only when these sinusoidal patterns are in phase that well-contrasted harmonic-like peaks occur in the spectrum. In our case, considering the simple spectral interference pattern created by the beating of the three most intense XUV light bursts in the APT for different values of CE phase (Fig. 4c-d) is enough to qualitatively understand the complex features of the whole CWE spectra of Fig. 4, as well as the drift of the harmonic-like peaks with the CE phase, observed experimentally for a Fourier-transform limited laser waveform (5-fs laser pulse). This phenomenon also explains why the well-contrasted peaks in the spectrum cannot be strictly interpreted as harmonic of the driving laser frequency.

In the harmonic spectra, the positions of the harmonic-like peaks corresponding to contrast revival in the moiré pattern, which depend on the temporal spacings between different pairs of attosecond pulses in the APT are therefore directly determined by the waveform of the laser light. This is how our experiment probes the temporal drift of the APT as a function of CE phase. Experiments carried out for different frequency chirps support this interpretation. For a non-chirped laser waveform, the time spacing between neighboring attosecond pulses naturally increases in time during the laser pulse, regardless of the CE phase value (Fig. 3e). This effect can be compensated by using a positively chirped laser waveform, for which the linearly decreasing light period from one wave cycle to the next balances the increasing delay between successively generated attosecond pulses induced by the temporal variation of the pulse envelope. Under these conditions, an almost perfectly periodic train of evenly spaced attosecond pulses can be generated (Fig. 3f). Here, as the CE phase changes, the position of the whole APT still drifts with respect to the pulse envelope as before but this drift no longer leads to changes in its temporal structure. This is why for a positively chirped waveform, the experimental CWE spectrum exhibits very little dependence on the CE phase (Fig. 2g andh). In contrast, a negative frequency chirp in time throughout the pulse will increase the uneven time spacing between pulses in the APT (Fig. 3d). The dependence of the CWE spectrum on the CE phase is therefore similar to the case of a non-chirped laser waveform, except that the harmonic-like peaks become narrower due to the greater number of attosecond pulses interfering in time during the longer frequency-chirped pulse envelope (Fig. 2a).

Controlling laser-driven plasmas

In summary, our experiment is the first demonstration of attosecond control of collective electronic processes in laser-driven plasmas and with it the successful extension of attosecond optical techniques to plasma physics.

Simply by spectrally resolving the coherent XUV radiation emitted by a solid illuminated by an intense fewcycle laser field of controlled waveform, we get an accurate temporal picture of the field-driven motion of charge through the thin layer of plasma formed at the surface. These experiments open the door to direct attosecond probing of the collective electronic response of a plasma to ultra-intense laser fields. As few-cycle laser pulses with orders of magnitude more peak-power will become accessible in the near future, our work is the first step towards controlling attosecond electronic processes in plasmas at relativistic light intensities, which is the key to developing ultrafast plasma-based particle accelerators and X-ray sources for applications.

One optical cycle Frequency (in ω L ) spectra as a function of the CE phase of a two-cycle (5-fs Fourier limit) NIR pulse in the same conditions as described in Fig. 2B. The spectrum consists of a region with well-contrasted harmonic-like peaks surrounded by intervals with lower contrast but still a periodic CE phase dependence. This corresponds to the moiré pattern produced by the spectral interference between the unevenly spaced attosecond pulses displayed in (c) and (d) left, for two different CE phase values. The moiré pattern resulting from the interference between the three most intense pulses in the APT is displayed in (c) and (d), right. The beating of the sinusoidal waves with slightly different frequencies resulting from the different timing between adjacent attosecond pulses leads to a blurring of the overall signal except when waves happen to be in phase. Moreover, as the CE phase is decreased from (c) to (d), the spacing between the attosecond pulses increases, thereby shifting the constructive interference pattern to lower harmonic frequencies and giving rise to the linear drift observed in the experiment.

T L =2π /ω L π /2

2 .

 2 Fig.3dto f show the temporal intensity profile of the APTs predicted by our model as a function of the CE phase φ0 of the three different NIR waveforms (Fig.3a to c). The intensity of the APTs are plotted as a function of t/TL + φ0/2π (horizontal axis): a vertical line in this plot therefore corresponds to an event that drifts linearly in time with changing CE phase. Fig.3shows that the main effect of the CE phase is to shift the temporal position of APT relative to the pulse envelope. This is because the subcycle motion of the electrons is temporally locked to the NIR waveform, and a change of ∆φ in the CE phase thus delays the electron trajectory crossing times inside the plasma by ≈ ∆φ/ωL, which is directly mapped onto the APT structure. More generally, by controlling the waveform of the NIR driving light, we can control the electron crossing time, and thereby the timing of emission of XUV light by the plasma, with sub-100-as precision.

Figure 1 :

 1 Figure 1: Schematic and principle of the experiment. (a) experimental set-up. Controlled few-cycleNIR light waveforms are focused at 1 kHz repetition rate onto a rotating glass surface[START_REF] Borot | High-harmonic generation from plasma mirrors at kilohertz repetition rate[END_REF] at a peak intensity around 10 18 W/cm 2 . The coherent XUV radiation emitted by the plasma created at the target surface is spectrally resolved. (b) Sketch of the charge dynamics at the plasma surface within a single NIR light cycle. The intense NIR electric-field (red) first pulls electrons out of the plasma and then pushes them back into the dense plasma layer, where their different trajectories (black lines) cross to form a few-100-as charge density wave that triggers background plasma oscillations in its wake. These oscillations radiate light in the form of attosecond XUV bursts (blue) with spectral components ωp dependent on the plasma density (bottom left axis). (c) Sketch of the attosecond pulse train (APT, blue) generated by a two-cycle NIR waveform (red) with arbitrary CE phase φ0. The unevenly spaced emission times τj show the influence of the light waveform on the time structure of the APT. (d) Build-up of the time-integrated spectrum. The purple areas sj(ω) show the spectra of the individual attosecond bursts for each laser cycle. The total measured spectrum S(ω) results from the spectral interference of all the XUV bursts produced during the laser pulse.

Figure 2 :Figure 3 :

 23 Figure 2: Waveform-dependent plasma emission spectra. Experimental (top row) and modeled (bottom row) CWE spectra obtained for different few-cycle NIR light waveforms (CE phase and linear frequency chirp) with 0.8 micron central wavelength. The experimental setup allows us to record XUV photon energies ranging from 11 and 15.5 eV, corresponding to harmonics 7 to 10 of the central frequency ωL of the NIR laser. The relative CE phase scale of the experimental scans is calibrated against the absolute CE phase values used in the model assuming an exponentially decaying plasma density gradient of λL/100 at the target surface and a peak intensity for a non-chirped pulse of 4 × 10 17 W/cm 2 .

Figure 4 :

 4 Figure 4: Moiré patterns in plasma emission spectra. (a) 1D model and (b) 2D PIC simulation of CWE


Théo Ryffel
email: theo.ryffel@ens.fr

David Pointcheval
email: david.pointcheval@ens.fr

Francis Bach
email: francis.bach@ens.fr

ARIANN: Low-Interaction Privacy-Preserving Deep Learning via Function Secret Sharing

We propose ARIANN, a low-interaction framework to perform private training and inference of standard deep neural networks on sensitive data. This framework implements semi-honest 2-party computation and leverages function secret sharing, a recent cryptographic protocol that only uses lightweight primitives to achieve an efficient online phase with a single message of the size of the inputs, for operations like comparison and multiplication which are building blocks of neural networks. Built on top of PyTorch, it offers a wide range of functions including ReLU, MaxPool and BatchNorm, and allows to use models like AlexNet or ResNet18. We report experimental results for inference and training over distant servers. Last, we propose an extension to support n-party private federated learning.

Introduction

The massive improvements of cryptography techniques for secure computation over sensitive data [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF][START_REF] Chillotti | Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[END_REF][START_REF] Keller | Overdrive: making spdz great again[END_REF] have spurred the development of the field of privacy-preserving machine learning [START_REF] Shokri | Privacy-preserving deep learning[END_REF][START_REF] Al-Rubaie | Privacy-preserving machine learning: Threats and solutions[END_REF]. Privacy-preserving techniques have become practical for concrete use cases, thus encouraging public authorities to use them to protect citizens' data, for example in covid-19 apps [START_REF] Kaur | An efficient multi-party scheme for privacy preserving collaborative filtering for healthcare recommender system[END_REF][START_REF] Dugan | A survey of secure multiparty computation protocols for privacy preserving genetic tests[END_REF][START_REF] Park | Information technology-based tracing strategy in response to COVID-19 in South Korea-privacy controversies[END_REF][START_REF] Reichert | Privacy-preserving contact tracing of covid-19 patients[END_REF].

However, tools are lacking to provide end-to-end solutions for institutions that have little expertise in cryptography while facing critical data privacy challenges. A striking example is hospitals which handle large amounts of data while having relatively constrained technical teams. Secure multiparty computation (SMPC) is a promising technique that can efficiently be integrated into machine learning workflows to ensure data and model privacy, while allowing multiple parties or institutions to participate in a joint project. In particular, SMPC provides intrinsic shared governance: because data are shared, none of the parties can decide alone to reconstruct it. This is particularly suited for collaborations between institutions willing to share ownership on a trained model.

Use case. The main use case driving our work is the collaboration between healthcare institutions such as hospitals or clinical research laboratories. Such collaboration involves a model owner and possibly several data owners like hospitals. As the model can be a sensitive asset (in terms of intellectual property, strategic asset or regulatory and privacy issues), standard federated learning [START_REF] Konečnỳ | Federated learning: Strategies for improving communication efficiency[END_REF][START_REF] Bonawitz | Towards federated learning at scale: System design[END_REF] that does not protect against model theft or model retro-engineering [START_REF] Hitaj | Deep models under the gan: information leakage from collaborative deep learning[END_REF][START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF] is not suitable.

Based on this use case, we will make the following assumptions: first, the parties involved in the computation are in the Wide Area Network (WAN) setting: they are located typically in different countries, are well connected and can communicate large amounts of information over the network with a reasonable latency. They also have access to relatively limited computing power compared 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

arXiv:2006.04593v1 [cs.

LG] 8 Jun 2020 to data centers, but are likely to remain online for long periods of time. Last, parties are honestbut-curious, [START_REF] Goldreich | Foundations of Cryptography: volume 2, Basic Applications[END_REF]Chapter 7.2.2] and care about their reputation. Hence, they have little incentive to deviate from the original protocol, but they will use any information available in their own interest.

Contributions. By leveraging function secret sharing (FSS) [START_REF] Boyle | Function secret sharing[END_REF][START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], we propose the first lowinteraction framework for private deep learning which drastically reduces communication to a single round for basic machine learning operations, and achieves the first private evaluation benchmark on ResNet18.

• We build on existing work on function secret sharing to design compact and efficient algorithms for comparison and multiplication, which are building blocks of neural networks. They are highly modular and can be assembled to build complex workflows. • We show how these blocks can be used in machine learning to implement operations for secure evaluation and training of arbitrary models on private data, including MaxPool and BatchNorm.

We achieve single round communication for comparison, convolutional or linear layers. • Last, we provide an implementation 1 and demonstrate its practicality both in LAN (local area network) and WAN settings by running secure training and inference on CIFAR-10 and Tiny Imagenet with models such as AlexNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and ResNet18 [START_REF] He | Deep residual learning for image recognition[END_REF].

Related work. Related work in privacy-preserving machine learning encompasses SMPC and homomorphic encryption (HE) techniques.

HE only needs a single round of interaction but does not support efficiently non-linearities. For example, nGraph-HE [START_REF] Boemer | nGraph-HE: a graph compiler for deep learning on homomorphically encrypted data[END_REF] and its extensions [START_REF] Boemer | nGraph-HE2: A high-throughput framework for neural network inference on encrypted data[END_REF] build on the SEAL library [START_REF]Microsoft SEAL (release 3.0[END_REF] and provide a framework for secure evaluation that greatly improves on the CryptoNet seminal work [START_REF] Gilad-Bachrach | Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy[END_REF], but it resorts to polynomials (like the square) for activation functions.

SMPC frameworks usually provide faster implementations using lightweight cryptography. MiniONN and DeepSecure [START_REF] Liu | Oblivious neural network predictions via minionn transformations[END_REF][START_REF] Bita Darvish Rouhani | Deepsecure: Scalable provably-secure deep learning[END_REF] use optimized garbled circuits [START_REF] Andrew | How to generate and exchange secrets[END_REF] that allow very few communication rounds, but they do not support training and alter the neural network structure to speed up execution.

Other frameworks such as ShareMind [START_REF] Bogdanov | Sharemind: A framework for fast privacypreserving computations[END_REF], SecureML [START_REF] Mohassel | Secureml: A system for scalable privacy-preserving machine learning[END_REF], SecureNN [START_REF] Wagh | Securenn: Efficient and private neural network training[END_REF] or more recently FALCON [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF] rely on additive secret sharing and allow secure model evaluation and training. They use simpler and more efficient primitives, but require a large number of rounds of communication, such as 11 in [START_REF] Wagh | Securenn: Efficient and private neural network training[END_REF] or 5 + log 2 (l) in [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF] (typically 10 with l = 32) for ReLU. ABY [START_REF] Demmler | Aby-a framework for efficient mixed-protocol secure two-party computation[END_REF], Chameleon [START_REF] Sadegh Riazi | Chameleon: A hybrid secure computation framework for machine learning applications[END_REF] and more recently ABY 3 [START_REF] Mohassel | Aby3: A mixed protocol framework for machine learning[END_REF] mix garbled circuits, additive or binary secret sharing based on what is most efficient for the operations considered. However, conversion between those can be expensive and they do not support training except ABY 3 . Last, works like Gazelle [START_REF] Juvekar | {GAZELLE}: A low latency framework for secure neural network inference[END_REF] combine HE and SMPC to make the most of both, but conversion can also be costly.

Works on trusted execution environment are left out of the scope of this article as they require access to dedicated hardware [START_REF] Hunt | Chiron: Privacy-preserving machine learning as a service[END_REF]. Data owners which cannot afford these secure enclaves might be reluctant to use a cloud service and to send their data.

[[f ]] 0 , [[f ]] 1 ) of a function f satisfy f (x) = [[f ]] 0 (x) + [[f ]] 1 (x)
[f α ]] j of f α : x → (x ≥ α), to obtain a shared output ([[f α ]] 0 (x), [[f α ]] 1 (x)) = [[f α (y + α)]] = [[(y + α) ≥ α]] = [[y ≥ 0]].
[9, 10] have shown the existence of such function shares for comparison which perfectly hide y and the result. From on now, to be consistent with the existing literature, we will denote the function keys

(k 0 , k 1 ) := ([[f ]] 0 , [[f ]] 1 ).
Note that for a perfect comparison, y + α should not wrap around and become negative. Because y is in practice small compared to the n-bit encoding amplitude, the failure rate is less than one comparison in a million, as detailed in Appendix C.1.

Security model. We consider security against honest-but-curious adversaries, i.e., parties following the protocol but trying to infer as much information as possible about others' input or function share. This is a standard security model in many SMPC frameworks [START_REF] Bogdanov | Sharemind: A framework for fast privacypreserving computations[END_REF][START_REF] Ben-Efraim | Optimizing semi-honest secure multiparty computation for the internet[END_REF][START_REF] Sadegh Riazi | Chameleon: A hybrid secure computation framework for machine learning applications[END_REF][START_REF] Wagh | Securenn: Efficient and private neural network training[END_REF] and is aligned with our main use case: parties that would not follow the protocol would face major backlash for their reputation if they got caught. The security of our protocols relies on indistinguishability of the function shares, which informally means that the shares received by each party are computationally indistinguishable from random strings. A formal definition of the security is given in [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF].

About malicious adversaries, i.e., parties who would not follow the protocol, as all the data available are random, they cannot get any information about the inputs of the other parties, including the parameters of the evaluated functions, unless the parties reconstruct some shared values. The later and the fewer values are reconstructed, the better it is. As mentioned by [START_REF] Boyle | Secure computation with preprocessing via function secret sharing[END_REF], our protocols could be extended to guarantee security with abort against malicious adversaries using MAC authentication [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF], which means that the protocol would abort if parties deviated from it.

Function Secret Sharing Primitives

Our algorithms for private equality and comparison are built on top of the work of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], so the security assumptions are the same as in this article. However, our protocols achieve higher efficiency by specializing on the operations needed for neural network evaluation or training.

Equality test

We start by describing private equality which is slightly simpler and gives useful hints about how comparison works. The equality test consists in comparing a public input x to a private value α.

Evaluating the input using the function keys can be viewed as walking a binary tree of depth n, where n is the number of bits of the input (typically 32). Among all the possible paths, the path from the root down to α is called the special path. Figure 1 illustrates this tree and provides a compact representation which is used by our protocol, where we do not detail branches for which all leaves are 0. Evaluation goes as follows: two evaluators are each given a function key which includes a distinct initial random state (s, t) ∈ {0, 1} λ × {0, 1}. Each evaluator starts from the root, at each step i goes down one node in the tree and updates his state depending on the bit x[i] using a common correction word CW (i) ∈ {0, 1} 2(λ+1) from the function key. At the end of the computation, each evaluation outputs t. As long as

x[i] = α[i],
the evaluators stay on the special path and because the input x is public and common, they both follow the same path. If a bit x[i] = α[i] is met, they leave the special path and should output 0 ; else, they stay on it all the way down, which means that x = α and they should output 1.

The main idea is that while they are on the special path, evaluators should have states (s 0 , t 0 ) and (s 1 , t 1 ) respectively, such that s 0 and s 1 are i.i.d. and t 0 ⊕ t 1 = 1. When they leave it, the correction word should act to have s 0 = s 1 but still indistinguishable from random and t 0 = t 1 , which ensures t 0 ⊕ t 1 = 0. Each evaluator should output its t j and the result will be given by t 0 ⊕ t 1 . The formal description of the protocol is given below and is composed of two parts: first, in Algorithm 1, the KeyGen algorithm consists of a preprocessing step to generate the functions keys, and then, in Algorithm 2, Eval is run by two evaluators to perform the equality test. It takes as input the private share held by each evaluator and the function key that they have received. They use G : {0, 1} λ → {0, 1} 2(λ+1) , a pseudorandom generator, where the output set is {0, 1} λ+1 ×{0, 1} λ+1 , and operations modulo 2 n implicitly convert back and forth n-bit strings into integers.

Intuitively, the correction words CW (i) are built from the expected state of each evaluator on the special path, i.e., the state that each should have at each node i if it is on the special path given some initial state. During evaluation, a correction word is applied by an evaluator only when it has t = 1. Hence, on the special path, the correction is applied only by one evaluator at each bit.

Initialisation: Sample random α $ ← Z 2 n Sample random s (1) j $ ← {0, 1} λ and set t (1) j ← j, for j = 0, 1 1 for i = 1..n do 2 (s L j || t L j , s R j || t R j ) ← G(s (i) j ) ∈ {0, 1} λ+1 × {0, 1} λ+1 , for j = 0, 1 3 if α[i] then cw (i) ← (0 λ || 0, s L 0 ⊕ s L 1 || 1) 4 else cw (i) ← (s R 0 ⊕ s R 1 || 1, 0 λ || 0); 5 CW (i) ← cw (i) ⊕ G(s (i) 0 ) ⊕ G(s (i) 1 ) ∈ {0, 1} λ+1 × {0, 1} λ+1 6 state j ← G(s (i) j ) ⊕ (t (i) j • CW (i) ) = (state j,0 , state j,1 ), for j = 0, 1 7 Parse s (i+1) j || t (i+1) j = state j,α[i] ∈ {0, 1} λ+1 , for j = 0, 1 8 CW (n+1) ← (-1) t (n+1) 1 • 1 -s (n+1) 0 + s (n+1) 1 mod 2 n 9 return k j ← [[α]] j || s (1)
j || CW (1) || • • • || CW (n+1) , for j = 0, 1
Algorithm 1: KeyGen: key generation for equality to α If at step i, the evaluator stays on the special path, the correction word compensates the current states of both evaluators by xor-ing them with themselves and re-introduces a pseudorandom value s

(either s R 0 ⊕ s R 1 or s L 0 ⊕ s L 1 )
, which means the xor of their states is now (s, 1) but those states are still indistinguishable from random. On the other hand, if x[i] = α[i], the new state takes the other half of the correction word, so that the xor of the two evaluators states is (0, 0). From there, they have the same states and both have either t = 0 or t = 1. They will continue to apply the same corrections at each step and their states will remain the same with t 0 ⊕ t 1 = 0. A final computation is performed to obtain shared

[[T ]] modulo 2 n of the result bit t = t 0 ⊕ t 1 ∈ {0, 1} shared modulo 2.
From the privacy point of view, when the seed s is (truly) random, G(s) also looks like a random bit-string (this is a pseudorandom bit-string). Each half is used either in the cw or in the next state, but not both. Therefore, the correction words CW (i) do not contain information about the expected states and for j = 0, 1, the output k j is independently uniformly distributed with respect to α and Input: (j, k j , [[y]] j ) where j ∈ {0, 1} refers to the evaluator id

1 Parse k j as [[α]] j || s (1) || CW (1) || • • • || CW (n+1) 2 Publish [[α]] j + [[y]] j mod 2 n and get revealed x = α + y mod 2 n 3 Let t (1) ← j 4 for i = 1..n do 5 state ← G(s (i) ) ⊕ (t (i) • CW (i) ) = (state 0 , state 1 ) 6 Parse s (i+1) || t (i+1) = state x[i] s (1)
1-j , in a computational way. As a consequence, at the end of the evaluation, for j = 0, 1, T j also follows a distribution independent of α. Until the shared values are reconstructed, even a malicious adversary cannot learn anything about α nor the inputs of the other player.

Function keys should be sent to the evaluators in advance, which requires one extra communication of the size of the keys. We use the trick of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] to reduce the size of each correction word in the keys, from 2(1 + λ) to (2 + λ) by reusing the pseudo-random λ-bit string dedicated to the state used when leaving the special path for the state used for staying onto it, since for the latter state the only constraint is the pseudo-randomness of the bitstring.

Comparison

Our major contribution to the function secret sharing scheme is regarding comparison (which allows to tackle non-polynomial activation functions for neural networks): we build on the idea of the equality test to provide a synthetic and efficient protocol whose structure is very close from the previous one. Instead of seeing the special path as a simple path, it can be seen as a frontier for the zone in the tree where x ≤ α. To evaluate x ≤ α, we could evaluate all the paths on the left of the special path and then sum up the results, but this is highly inefficient as it requires exponentially many evaluations.

Our key idea here is to evaluate all these paths at the same time, noting that each time one leaves the special path, it either falls on the left side (i.e., x < α) or on the right side (i.e., x > α). Hence, we only need to add an extra step at each node of the evaluation, where depending on the bit value x[i], we output a leaf label which is 1 only if x[i] < α[i] and all previous bits are identical. Only one label between the final label (which corresponds to x = α) and the leaf labels can be equal to one, because only a single path can be taken. Therefore, evaluators will return the sum of all the labels to get the final output.

The full description of the comparison protocol is detailed in Appendix A, together with a detailed explanation of how it works.

Application to Deep Learning

We now apply these primitives to a private deep learning setup in which a model owner interacts with a data owner. The data and the model parameters are sensitive and are secret shared to be kept private. The shape of the input and the architecture of the model are however public, which is a standard assumption in secure deep learning [START_REF] Liu | Oblivious neural network predictions via minionn transformations[END_REF][START_REF] Mohassel | Secureml: A system for scalable privacy-preserving machine learning[END_REF].

Additive sharing workflow

All our operations are modular and follow this additive sharing workflow: inputs are provided secret shared and are masked with random values before being revealed. This disclosed value is then consumed with preprocessed function keys to produce a secret shared output. Each operation is independent of all surrounding operations, which is known as circuit-independent preprocessing [START_REF] Boyle | Secure computation with preprocessing via function secret sharing[END_REF] and implies that key generation can be fully outsourced without having to know the model architecture. This results in a fast runtime execution with a very efficient online communication, with a single round of communication and a message size equal to the input size for comparison. Preprocessing is performed by a trusted third party to build the function keys. This is a valid assumption in our use case as such third party would typically be an institution concerned about its image, and it is very easy to check that preprocessed material is correct using a cut-and-choose technique [START_REF] Zhu | The cut-and-choose game and its application to cryptographic protocols[END_REF].

Machine Learning operations

Matrix Multiplication (MatMul). As mentioned by [START_REF] Boyle | Secure computation with preprocessing via function secret sharing[END_REF], multiplication fit in this additive sharing workflow. We use Beaver triples [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF] to compute

[[z]] = [[x • y]] from [[x]], [[y]]
]] + • [[a]] + δ • + [[c]] = [[z]].
Matrix multiplication is identical but uses matrix Beaver triples [START_REF] Dahl | Private Image Analysis with MPC[END_REF].

ReLU activation function is supported as a direct application of our comparison protocol, which we combine with a point wise multiplication.

Convolution can be computed as a single matrix multiplication using an unrolling technique as described in [START_REF] Kumar Chellapilla | High performance convolutional neural networks for document processing[END_REF] and illustrated in Figure 3 in Appendix C.2.

Argmax operator used in classification to determine the predicted label can also be computed in a constant number of rounds using pairwise comparisons as shown by [START_REF] Hannun | Privacy-preserving contextual bandits[END_REF]. The main idea here is, given a vector (x 0 , . . . , x m-1 ), to compute the matrix M ∈ R m-1×m where each row M i = (x i+1 mod m , . . . , x i+m+1 mod m ). Then, each element of column j is compared to x j , which requires m(m -1) parallel comparisons. A column j where all elements are lower than x j indicates that j is a valid result for the argmax.

MaxPool can be implemented by combining these two methods: the matrix is first unrolled like in Figure 3 and the maximum of each row in then computed using parallel pairwise comparisons. More details and an optimization when the kernel size k equals 2 are given in Appendix C.3.

BatchNorm is implemented using a approximate division with Newton's method as in [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF]: given an input x = (x 0 , . . . , x m-1 ) with mean µ and variance σ 2 , we return γ • θ • ( x -µ) + β. Variables γ and β are learnable parameters and θ is the estimate inverse of √ σ 2 + with 1 and is computed iteratively using:

θ i+1 = θ i • (3 -(σ 2 + ) • θ 2 i )/2.
More details can be found in Appendix C.4. More generally, for more complex activation functions such as softmax, we can use polynomial approximations methods, which achieve acceptable accuracy despite involving a higher number of rounds [START_REF] Pan | An improved newton iteration for the generalized inverse of a matrix, with applications[END_REF][START_REF] Nicholas | Accuracy and stability of numerical algorithms[END_REF][START_REF] Hannun | Privacy-preserving contextual bandits[END_REF]. Table 1 summarizes the online communication cost of each operation, and shows that basic operations such as comparison have a very efficient online communication. We also report results from [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF] which achieve good experimental performance.

Training phase using Autograd

These operations are sufficient to evaluate real world models in a fully private way. To also support private training of these models, we need to perform a private backward pass. As we overload operations such as convolutions or activation functions, we cannot use the built-in autograd functionality of PyTorch. Therefore, we have developed a custom autograd functionality, where we specify how to compute the derivatives of the operations that we have overloaded. Backpropagation also uses the same basic blocks than those used in the forward pass.

Extension to Private Federated Learning

This 2-party protocol between a model owner and a data owner can be extended to an n-party federated learning protocol where several clients contribute their data to a model owned by an orchestrator server. This approach is inspired by secure aggregation [START_REF] Bonawitz | Practical secure aggregation for privacy-preserving machine learning[END_REF] but we do not consider here clients being phones which means we are less concerned with parties dropping before the end of the protocol. In addition, we do not reveal the updated model at each aggregation or at any stage, hence providing better privacy than secure aggregation.

At the beginning of the interaction, the server and model owner initializes its model and builds n pairs of additive shares of the model parameters. For each pair i, it keeps one of the shares and sends the other one to the corresponding client i. Then, the server runs in parallel the training procedure with all the clients until the aggregation phase starts. Aggregation for the server shares is straightforward, as the n shares it holds can be simply locally averaged. But the clients have to average their shares together to get a client share of the aggregated model. One possibility is that clients broadcast their shares and compute the average locally. However, to prevent a client colluding with the server from reconstructing the model contributed by a given client, they hide their shares using masking. This can be done using correlated random masks: client i generates a seed, sends it to client i + 1 while receiving one from client i -1. Client i then generates a random mask M i using its seed and another M i-1 using the one of client i -1 and publishes its share masked with M i -M i-1 . As the masks cancel each other out, the computation will be correct.

m 1 - m - Comparison m 1 7 m 2m MatMul m 1 × m 2 , m 2 × m 3 1 1 m 1 m 2 + m 2 m 3 m 1 m 3 Linear m1 × m2, {m2 × m3} 1 1 m 1 m 2 + m 2 m 3 m 1 m 3 Convolution m × m, {k, s} 1 1
((m -k)/s + 1) 2 k 2 + k 2 ∼ m 2 k 2 ReLU m 2 10 3m 4m Argmax m 2 - m 2 - MaxPool m × m, {k, s} 3
12(k 2 -1) ((m -k)/s + 1) 2 (k 4 + 2) ∼ 5m 2 BatchNorm m × m 9 335 18m 2 ∼ 56m 2

Experiments

We follow a setup very close to [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF] and assess inference and training performance of several networks on the datasets MNIST [START_REF] Lecun | MNIST handwritten digit database[END_REF], CIFAR-10 [30], 64×64 Tiny Imagenet and 224×224 Tiny ImageNet [START_REF] Wu | Tiny imagenet challenge[END_REF][START_REF] Russakovsky | Imagenet large scale visual recognition challenge[END_REF], presented in Appendix D.1. More precisely, we assess 5 networks as in [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF]: a fully-connected network (Network-1), a small convolutional network with maxpool (Network-2), LeNet [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF], AlexNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] and VGG16 [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]. Furthermore, we also include ResNet18 [START_REF] He | Deep residual learning for image recognition[END_REF] which to the best of our knowledge has never been studied before in private deep learning. The description of these networks is taken verbatim from [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF] and is available in Appendix D.2.

Our implementation is written in Python. To use our protocols that only work in finite groups like Z 2 32 , we convert our input values and model parameters to fixed precision. To do so, we rely on the PySyft library [START_REF] Ryffel | A generic framework for privacy preserving deep learning[END_REF] which extends common deep learning frameworks including PyTorch with a communication layer for federated learning and supports fixed precision. The experiments are run on Amazon EC2 m5d.4xlarge machines with 16 cores and 64GB of RAM, and we report our results both in the LAN and in the WAN setting. Latency is of 70ms for the WAN setting and is considered negligible in the LAN setting. Last, all values are encoded on 32 bits.

Evaluation inference time.

Comparison of experimental runtimes should be taken with caution, as different implementations and hardware may result in significant differences even for the same [34-36, 47, 48], in the LAN setting and particularly in the WAN setting thanks to our reduced number of communication rounds. For example, our implementation of Network-1 is 2× faster than the best previous result by [START_REF] Mohassel | Aby3: A mixed protocol framework for machine learning[END_REF] in the LAN setting and 18× faster in the WAN setting compared to [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF]. For bigger networks such as AlexNet on CIFAR-10, we are still 13× faster in the WAN setting than [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF]. Results are given for a batched evaluation, which allows parallelism and hence faster execution as in [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF]. For larger networks, we reduce the batch size to have the preprocessing material (including the function keys) fitting into RAM.

Test accuracy. Thanks to the flexibility of our framework, we can train each of these networks in plain text and need only one line of code to turn them into private networks, where all parameters are secret shared. We compare these private networks to their plaintext counterparts and observe that the accuracy is well preserved as shown in Table 3. If we degrade the encoding precision, which by default considers values in Z 2 32 , and the fixed precision which is by default of 3 decimals, performance degrades as shown in Appendix B.

Training. We can either train from scratch those networks or fine tune pre-trained models. Training is an end-to-end private procedure, which means the loss and the gradients are never accessible in plain text. We use stochastic gradient descent (SGD) which is a simple but popular optimizer, and support both hinge loss and mean square error (MSE) loss, as other losses like cross entropy which is used in clear text by [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF] cannot be computed over secret shared data without approximations. We report runtime and accuracy obtained by training from scratch the smaller networks in Table 4. Note that because of the number of epochs, the optimizer and the loss chosen, accuracy does not match best known results. However, the training procedure is not altered and the trained model will be strictly equivalent to its plaintext counterpart. Training cannot complete in reasonable time for larger networks, which are anyway available pre-trained. Note that training time includes the time spent building the preprocessing material, as it cannot be fully processed in advance and stored in RAM.

Discussion. For larger networks, we could not use batches of size 128. This is mainly due to the size of the comparison function keys which is currently proportional to the size of the input tensor, with a multiplication factor of nλ where n = 32 and λ = 128. Optimizing the function secret sharing protocol to reduce those keys would lead to massive improvements in the protocol's efficiency.

Our implementation actually has more communication than is theoretically necessary according to Table 1, suggesting that the experimental results could be further improved. As we build on top of PyTorch, using machines with GPUs could also potentially result in a massive speed-up, as an important fraction of the execution time is dedicated to computation.

Last, accuracies presented in Table 3 and Table 4 do not match state-of-the-art performance for the models and datasets considered. This is not due to internal defaults of our protocol but to the simplified training procedure we had to use. Supporting losses such as the logistic loss, more complex optimizers like Adam and dropout layers would be an interesting follow-up.

B Encoding precision

We have studied the impact of lowering the encoding space of the input to our function secret sharing protocol from Z 2 32 to Z 2 k with k < 32. Finding the lowest k guaranteeing good performance is an interesting challenge as the function keys size is directly proportional to it. This has to be done together with reducing fixed precision from 3 decimals down to 1 decimal to ensure private values aren't too big, which would result in higher failure rate in our private comparison protocol. We have reported in What we observe is that 3 decimals of precision is the most appropriate setting to have an optimal precision while allowing to slightly reduce the encoding space down to Z 2 24 or Z 2 28 . Because this is not a massive gain and in order to keep the failure rate in comparison very low, we have kept Z 2 32 for all our experiments.

C Implementation details C.1 Failure rate of FSS comparison in practical scenarios

Our comparison protocol can fail if y + α wraps around and becomes negative. We can't act on α because it must be completely random to act as a perfect mask and to make sure the revealed x = y + α mod 2 n does not leak any information about y, but the smaller y is, the lower the error probability will be. [START_REF] Boyle | Secure computation with preprocessing via function secret sharing[END_REF] suggests a method which uses 2 invocations of the protocol to guarantee perfect correctness but because it incurs an important runtime overhead, we rather show that the failure rate of our comparison protocol is very small and is reasonable in contexts that tolerate a few mistakes, as in machine learning. More precisely, we quantify it on real world examples, namely on Network-2 and on the 64×64 Tiny Imagenet version of VGG16, with a fixed precision of 3 decimals, and find respective failure rates of 1 in 4 millions comparisons and 1 in 100 millions comparisons. Such error rates do not affect the model accuracy, as Table 3 shows.

C.2 Unrolling convolutions

C.3 MaxPool and optimisation

Figure 4 illustrates how MaxPool uses ideas from matrix unrolling and argmax computation. Notations present in the figure are consistent with the explanation of argmax using pairwise comparison in Section 4.3. The m × m matrix is first unrolled to a m 2 × k 2 matrix. It is then expanded on k 2 layers, each of which each shifted by a step of 1. Next, m 2 k 2 (k 2 -1) pairwise comparisons are then applied simultaneously between the first layer and the other ones, and for each x i we sum the result of its k -1 comparison and check if it equals k -1. We multiply this boolean by x i and sum up along a line (like x 1 to x 4 in the figure). Last, we restructure the matrix back to its initial structure. In addition, when the kernel size k is 2, rows are only of length 4 and it can be more efficient to use a binary tree approach instead, i.e. compute the maximum of columns 0 and 1, 2 and 3 and the max of the result: it requires log 2 (k 2 ) = 2 rounds of communication and only approximately (k 2 -1)(m/s) 2 comparisons, compared to a fixed 3 rounds and approximately k 4 (m/s) 2 .

Interestingly, average pooling can be computed locally on the shares without interaction because it only includes mean operations, but we didn't replace MaxPool operations with average pooling to avoid distorting existing neural networks architecture.

C.4 BatchNorm approximation

The BatchNorm layer is the only one in our implementation which is a polynomial approximation. Moreover, compared to [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF], the approximation is significantly coarser as we don't make any costly initial approximation and we reduce the number of iterations of the Newton method from 4 to only 3. Typical relative error can be up to 20% but as the primary purpose of BatchNorm is to normalise data, having rough approximations here is not an issue and doesn't affect learning capabilities, as our experiments show. However, it is a limitation for using pre-trained networks: we observed on AlexNet adapted to CIFAR-10 that training the model with a standard BatchNorm and evaluating it with our approximation resulted in poor results, so we had to train it with the approximated layer.

D Datasets and Networks Architecture D.1 Datasets

This section is taken almost verbatim from [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF].

We select 4 datasets popularly used for training image classification models: MNIST [START_REF] Lecun | MNIST handwritten digit database[END_REF], CIFAR-10 [30], 64×64 Tiny Imagenet and 224×224 Tiny ImageNet [START_REF] Wu | Tiny imagenet challenge[END_REF].

MNIST MNIST [START_REF] Lecun | MNIST handwritten digit database[END_REF] is a collection of handwritten digits dataset. It consists of 60,000 images in the training set and 10,000 in the test set. Each image is a 28×28 pixel image of a handwritten digit along wit a label between 0 and 9. We evaluate Network-1, Network-2, and the LeNet network on this dataset. CIFAR-10 CIFAR-10 [30] consists of 50,000 images in the training set and 10,000 in the test set. It is composed of 10 different classes (such as airplanes, dogs, horses etc.) and there are 6,000 images of each class with each image consisting of a colored 32×32 image. We perform private training of AlexNet and inference of VGG16 on this dataset. Tiny ImageNet Tiny ImageNet [START_REF] Wu | Tiny imagenet challenge[END_REF] consists of two datasets of 100,000 training samples and 10,000 test samples with 200 different classes. The first dataset is composed of colored 64×64 images and we use it with AlexNet and VGG16. The second is composed of colored 224×224 images and is used with ResNet18.

D.2 Model description

We have selected 6 models for our experimentations.

Network-1 A 3-layered fully-connected network with ReLU used in SecureML [START_REF] Mohassel | Secureml: A system for scalable privacy-preserving machine learning[END_REF].

Network-2 A 4-layered network selected in MiniONN [START_REF] Liu | Oblivious neural network predictions via minionn transformations[END_REF] with 2 convolutional and 2 fullyconnected layers, which uses MaxPool in addition to ReLU activation.

LeNet This network, first proposed by LeCun et al. [START_REF] Lecun | Gradient-based learning applied to document recognition[END_REF], was used in automated detection of zip codes and digit recognition. The network contains 2 convolutional layers and 2 fully connected layers.

AlexNet AlexNet is the famous winner of the 2012 ImageNet ILSVRC-2012 competition [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF]. It has 5 convolutional layers and 3 fully connected layers and it can batch normalization layer for stability and efficient training.

VGG16 VGG16 is the runner-up of the ILSVRC-2014 competition [START_REF] Simonyan | Very deep convolutional networks for large-scale image recognition[END_REF]. VGG16 has 16 layers and has about 138M parameters.

ResNet18 ResNet18 [START_REF] He | Deep residual learning for image recognition[END_REF] is the runner-up of the ILSVRC-2015 competition. It is a convolutional neural network that is 18 layers deep, and has 11.7M parameters. It uses batch normalisation and we're the first private deep learning framework to evaluate this network.

D.3 Model Architecture

Model architectures of Network-1 and Network-2, together with LeNet, and the adaptations for CIFAR-10 of AlexNet and VGG16 are precisely depicted in Appendix D of [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF]. Note that in the CIFAR-10 version AlexNet, authors have used the version with BatchNorm layers, and we have kept this choice. For the 64×64 Tiny Imagenet version of AlexNet, we used the standard architecture from PyTorch to have a pretrained network. It doesn't have BatchNorm layers, and we have adapted the classifier part as illustrated in Figure 5. Note also that we permute ReLU and Maxpool where applicable like in [START_REF] Wagh | Falcon: Honest-majority maliciously secure framework for private deep learning[END_REF], as this is strictly equivalent in terms of output for the network and reduces the number of comparisons. More generally, we don't proceed to any alteration of the network behaviour except with the approximation on BatchNorm. This improves usability of our framework as it allows to take a pre-trained neural network from a standard deep learning library like PyTorch and to encrypt it generically with a single line of code.

Figure 1 :

 1 Figure 1: (left) Binary decision tree with the special path for n = 3. Given an input x = (x 1 ...x n ) 2 , at each level i, one should take the path labeled by the value in the square equal to the bit value x i . (right) Flat representation of the tree.

Figure 2 :

 2 Figure 2: (Left) Binary decision tree with all the paths corresponding to x ≤ α for n=3. (Right) Flat representation of the tree.

  and using a triple ([[a]], [[b]], [[c]] := [[a • b]]), where all values are secret shared in Z 2 n . The mask is here [[(-a, -b)]] and is used to reveal (δ, ) := (x -a, y -b). The functional keys are the shares of ([[a]], [[b]], [[c]]) and are used to compute δ • [[b

Figure 3

 3 Figure 3 illustrates how to transform a convolution operation into a single matrix multiplication.

Figure 3 :

 3 Figure 3: Illustration of unrolling a convolution with kernel size k = 2 and stride s = 2.

Figure 4 :

 4 Figure 4: Illustration of MaxPool with kernel size k = 2 and stride s = 2.

Table 1 :

 1 Theoretical online communication complexity of our protocols. Input sizes into bracket are those of the layers' parameters, where k stands for the kernel size and s for the stride. Communication is given in number of values transmitted, and should be multiplied by their size (typically 4 bytes).

	Protocol	Input size	Rounds	Communication
			Ours	[48]	Ours	[48]
	Equality

Table 2 :

 2 Inference time over several popular network architectures.

	Model	Dataset	LAN Time (s) WAN Time (s) Online Comm. (MB) Batch Size
	Network-1 MNIST	0.004	0.055	0.013	128
	Network-2 MNIST	0.096	0.234	0.33	128
	LeNet	MNIST	0.129	0.289	0.46	128
	AlexNet	CIFAR-10	0.303	0.696	1.46	128
	AlexNet 64×64 ImageNet 0.723	1.36	2.56	128
	VGG16	CIFAR-10	4.50	8.14	16.1	32
	VGG16	64×64 ImageNet 11.4	35.9	102	16
	ResNet18 224×224 ImageNet 43.3	80.8	220	4

Table 3 :

 3 Accuracy of network architectures trained in plain text, tested in the private setting.

	Model	Dataset	Private Accuracy Normal Accuracy
	Network-1 MNIST	98.1	98.1
	Network-2 MNIST	99.0	99.0
	LeNet	MNIST	99.4	99.4
	AlexNet	CIFAR-10	60.6	60.7
	AlexNet	64×64 Tiny ImageNet	33.3	33.7
	VGG16	CIFAR-10	88.8	88.8
	VGG16	64×64 Tiny ImageNet	41.1	41.3

Table 4 :

 4 Training time and accuracy for networks privately trained from scratch (except AlexNet).

	Model	Dataset	LAN Time (h) Accuracy Nb of epochs
	Network-1 MNIST	5.46	97.8	15
	Network-2 MNIST	82	87.3	12
	LeNet	MNIST	51	96.6	6
	AlexNet	CIFAR-10	58	62.3	4
	protocol. However, our inference runtimes reported in Table 2 compare favourably with existing
	work including

Table 5 :

 5 Table 5 our findings on Network-1, which is pre-trained and then evaluated in a private fashion. Decimals Z 2 12 Z 2 16 Z 2 20 Z 2 24 Z 2 28 Z 2 32 Accuracy (in %) of Network-1 given different precision and encoding spaces

	1	-	-	-	-	-	9.5
	2	69.4 96.0 97.9 98.1 98.0 98.1
	3	10.4 76.2 96.9 98.1 98.2 98.1
	4	9.7	14.3 83.5 97.4 98.1 98.2

All code and implementations will be made available on GitHub.

return [[T ]] j ← (-1) j • t (n+1) • CW (n+1) + s (n+1) mod 2 nAlgorithm 2: Eval: evaluation of the function key for zero test y = 0

Acknowledgments

We would like to thank Geoffroy Couteau, Chloé Hébant and Loïc Estève for helpful discussions throughout this project. We are also grateful for the long-standing support of the OpenMined community and in particular its dedicated cryptography team, including Yugandhar Tripathi, S P Sharan, George-Cristian Muraru, Muhammed Abogazia, Alan Aboudib, Ayoub Benaissa, Sukhad Joshi and many others. This work was supported in part by the European Community's Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 339563 -CryptoCloud) and by the French project FUI ANBLIC. The computing power was graciously provided by the French company ARKHN.

A Function Secret Sharing -Comparison

One can observe the great similarity of structure of the comparison protocol given in Algorithm 3 and 4 with the equality protocol from Algorithm 1 and 2: the equality test is performed in parallel with an additional information out i at each node, which holds a share of either 0 when the evaluator stays on the special path or if it has already left it at a previous node, or a share of α[i] when it leaves the special path. This means that if α[i] = 1, leaving the special path implies that x[i] = 0 and hence x ≤ α, while if α[i] = 0, leaving implies x[i] = 1 so x > α and the output should be 0. The final share out n+1 corresponds the previous equality test.

Note that in all these computations modulo 2 n , while the bitstrings s (i) j and σ (i) j are in {0, 1} λ , they are always either the same for the two players or compensated by the CW (i) and CW (i) leaf respectively, hence they cancel. In the end, the sum [[T ]] j of the out i 's is a share of 1 either if out n+1 was a share of 1 (i.e. x = α) or if one of the other out i was, which is possible only if

Let G : {0, 1} λ → {0, 1} 4(λ+1) be a pseudorandom generator, where the output is seen as a pair of pairs of elements in {0, 1} λ+1 , and so ({0, 1} λ+1 × {0, 1} λ+1 ) × ({0, 1} λ+1 × {0, 1} λ+1 ).

7 for j = 0, 1 do 8 state j ← G(s

) = ((state j,0 , state j,1 ), (state j,0 , state j,1 ))

Algorithm 3: KeyGen: key generation for comparison to α Input: (j, k j , [[y]] j ) where j ∈ {0, 1} refers to the evaluator id