{'fraction_non_alphanumeric': 0.040395179313657915, 'fraction_numerical': 0.015351839087662134, 'mean_word_length': 4.517169854805255, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
PrivPy: Enabling Scalable and General Privacy-Preserving Computation

We introduce PrivPy, a practical privacy-preserving collaborative computation framework. PrivPy provides an easy-to-use and highly compatible Python programming front-end which supports high-level array operations and different secure computation engines to allow for security assumptions and performance trade-offs. We also design and implement a new secret-sharing-based computation engine with highly efficient protocols for private arithmetics over real numbers: a fast secure multiplication protocol, a garbled-circuit-based secure comparison protocol, and optimized array/matrix operations that are essential for “big data” applications. PrivPy provides provable privacy and supports general computation. We demonstrate the scalability of PrivPy using machine learning models (e.g. logistic regression and convolutional neural networks) and real-world datasets (including a 5000-by-1-million private matrix).


Introduction
Privacy is an important issue in big data age. It is often desirable to pool data from multiple sources for better mining results. However, the direct sharing of sensitive data threatens users' privacy and is often prohibited by laws. How to protect privacy while mining valuable information is a problem demanding prompt solutions.
Two main techniques used for privacy-preserving computation include randomization and cryptography [1]. The former protects privacy by introducing uncertainty [39]. Recent works on differential privacy [25] are the latest representatives. Example applications include [69,12,66,6]. They are often efficient, but the amount of randomization necessary to maintain adequate privacy depends directly on the number of occasions where information about the data is to be released. As a result, in a scenario where many sources are contributing data to the computation for many iterations, one usually must add a large amount of noise to maintain differential privacy, making the accuracy far from useful. There are some noiseless models (e.g. [7]), but they rely on strong assumptions about the data distribution.
In Cryptography, privacy-preserving computation is often cast into a secure multi-party computation (SMC) problem. SMC could provide accurate results and reveal no information about the data except for the final outputs. Typical methods include Yao's garbled circuit (GC), fully homomorphic encryption (FHE) and secret sharing (SS). Theoretically, GC and FHE can compute any given function securely [72], but for general computation, GC involves heavy communication, while HE incurs heavy computation. Secret sharing such as Shamir's [64] supports extremely efficient private addition. Multiplication, on the other hand, involves interactions among players and is much more expensive. Another performance issue with cryptographic approaches is the handling of decimal numbers. Most systems [33,8,19,18] support integer operations natively and are inefficient for real number operations, due to heavy use of expensive operations such as secure bit-level operations [17,11,45,38]. In this paper, we focus on providing a practical SMC, as it is easy, if necessary, to introduce randomization into our framework to protect the final results [59,49].
The challenges to achieving practical privacy go beyond performance and scalability. Steep learning curve and high development cost are among the major factors hindering the adoption of privacy solutions. Many existing solutions either require considerable expertise in cryptography, or use special programming languages [62,33,76,19,55]. Some solutions like [74,70], though providing interfaces compatiable with common languages (e.g. C++), only support very basic operations. These issues make it hard for programmers not familiar with cryptography to implement complex machine learning algorithms.
We introduce PrivPy, an efficient and easy-to-program framework for privacy-preserving collaborative computation. PrivPy achieves the goal with two key designs: First, instead of a custom language (e.g. [8,19,51]), PrivPy uses intuitive Python APIs to facilitate private computation, as well as a tool for automatic code-level rewriting and optimization. Second, though supporting different back-ends, PrivPy provides an efficient computation engine that natively supports real-number operations. Concretely, we make the following contributions: 1) Programming interfaces. Using data type encapsulation and automatic code optimization, we provide a very clean Python language integration with privacyenabled common operations and high-level primitives, including broadcasting that manipulates arrays of different shapes, and the ndarray methods, two Numpy [68] features widely utilized to implement machine learning algorithms. With these convenient interfaces, developers can compose their applications or port complex machine learning algorithms onto PrivPy with minimal effort.
2) Support for multiple back-ends. The language interface is flexible and supports multiple computation back-ends, allowing trade-offs among different performance and security assumptions. Our current implementation supports both the SPDZ back-end and our own computation engine.
3) An efficient private computation engine. We introduce two new protocols with native support for real numbers: a multiplication protocol and a garbled-circuitbased comparison protocol, both with provable accuracy and privacy. These protocols support efficient secure operations for real numbers of arbitrary precision. 4) Validation on large-scale datasets. We demonstrate the practicality of our system for machine learning algorithms, such as logistic regression and convolutional neural network (CNN), on real-world datasets (including a 5000-by-1-million matrix) and application scenarios, including model training and inference. It only takes about 1 second for CNN in PrivPy to perform inference on an image using complex models. To our knowledge, this is the first practical modern CNN implementation using noise-free privacy-preserving method.
The paper is organized as follows. Section 2 reviews recent researches on privacy-preserving computation. Section 3 formulates the problem and provides an overview of the system design. Section 4 provides an introduction of our computation engine. Section 5 details our computation protocols. Section 6 describes optimizations to reduce computational and communicational cost. Section 7 shows the evaluation results. We conclude in Section 8.

Related Work
Secure multi-party computation (SMC) allows players to compute a function over their collective inputs while protecting the privacy of their inputs. They make use of various cryptographic primitives such as garbled circuit (GC) [72], homomorphic encryption (HE) [28], oblivious transfer (OT) [60] or secret sharing (SS) [64]. Several systems have implemented certain SMC protocols. FairplayMP [5], EMP [70] and Obliv-C [74] implement GC. HElib [29] is a library for fully homomorphic encryption (FHE) using the BGV scheme [10]. [52] utilize the BGV scheme to perform statistics analysis. However, neither pure GC nor FHE is efficient for general-purpose computations, especially for complex ones, due to high communication and/or computation cost [63,61].
There are also many SMC frameworks using additive secret sharing. Some are algorithm-specific, e.g. [30,58,23,24]. VIFF [18] provides general SMC by precomputing triples for multiplication, at the cost of lots of communication. SPDZ [19] provides active security, by keeping MACs of secret data. [4,40] optimize the preprocessing phase of SPDZ. Sharemind [8] is a commercial end-to-end SMC framework which provides passive security with three semi-honest servers. The prototypes of SPDZ and Sharemind natively support integer data types only, while depending expensive secure bitlevel operations, such as secure bit decomposition, secure shifting and secure truncation, to support real numbers. These bit-level operations involve heavy communication (i.e. O(m) large integers are transferred for the operations in a m-bit integer field) [17,11,45,38,22]. In comparison, PrivPy avoids these expensive operations and only transfers O(1) integers for each multiplication.
Other systems use a mixture of secure computation protocols. TASTY [33] is a tool for secure two-party computation, which automatically converts between GC and HE representation. ABY [21] is a framework that combines arithmetic sharing, boolean sharing and Yao sharing together. However, it is still up to the application to decide which kind of sharing to use, making the learning curve steep. [20] adds an HDL-based front-end to ABY, but its interfaces are too limited for programmers to build complex algorithms. L1 [62] is an intermediate language for secure computation with mixed protocols, which only supports simple computation. [9] uses GC and HE to implement simple linear algorithms, but the performance is not practical, and the programming interfaces it provides are not intuitive. SecureML [55] combines GC, OT and SS to implement secure algorithms. However, it does not provide any language front-end. PrivPy is a mixed protocol solution too, but it natively integrates the GC output into the secret sharing, requiring no learning curve on the application programmer side.
Language-wise, PICCO [76] performs a source-tosource compilation for the programs written in an extension of C. However, the compilation is expensive both in time and space (proportional to the circuit size), and every change to the input size requires a fresh compilation. Systems such as [44,46,33,19] suffer from similar problems (e.g., it takes 10 minutes for SPDZ to compile 10, 000 independent multiplications with its optimizations). Newer compliers such as ObliVM [51], though providing on-the-fly circuit generation, is still a domainspecific language, and the complied operations are not efficient enough according to their report. PrivPy, on the other hand, eliminates the entire pre-compilation overhead and stays compatible with Python.
3 System Design

Problem formulation
We can formulate the problem that PrivPy solves as the following SMC problem: there are n clients C i (i = 1, 2, . . . , n). Each C i has a set of private data D i as its input. The goal is to use the union of all D i 's to compute some function o = f (D 1 , D 2 , . . . , D n ). D i can be records collected independently by C i , and C i 's can use them to jointly train a model. D i can be even a secret model held by C i . In this situation, C i can perform inference on others' private data without revealing its model. For the computation, we have the following requirements: 1) Privacy: During the computation, no information, other than the output o, is revealed to the participants. 2) Precision: The output o should be (almost) the same as the cleartext version. 3) Generality: f can be a combination of any numerical operations including both calculation and comparison. 4) Efficiency: f can be evaluated fast enough. 5) Scalability: The solution should be able to scale to support a large number of participants and data items. Fig. 1 shows an overview of PrivPy architecture, which has two main components: the language front-end and the computation engine back-end. The front-end runs at the client side, providing programming interfaces and code optimizations. The back-end runs on the servers, performing the core privacy-preserving computation. We decouple the front-end and back-end so that we can leverage different back-ends.

Programming language front-end
The front-end provides convenient Python APIs, with which users can write programs easily. A PrivPy program is a valid Python program with NumPy-style data type definitions. Fig. 2 shows an example PrivPy program that computes the logistic function f (x) = 1/(1 + e −x ) using the Euler method [67]. The public variable start is the initial point, and iter cnt is the number of iterations.
Basic semantics. The program itself (lines 2-9) is a plain Python program, which can run in a raw Python environment with cleartext input, and the user only needs to add two things to make it private-preserving in PrivPy: (i) Declaring the private variables. Line 1 declares a private variable x as the input from the client clientID.
(ii) Getting results back. Line 10 allows clients to recover the cleartext of the private variable result.
Supporting both scalar and array data types. PrivPy supports both scalars and arrays of any shape. While invoking the ss method, PrivPy detects the type and the shape of x automatically. Following the NumPy [68] semantics, we also provide broadcasting which allows operations between a scalar and an array, as well as between arrays of different shapes, making programming in PrivPy very convenient. That is why the logistic function in Fig. 2 works correctly even when x is a private array. As far as we know, no existing SMC front-ends support such elegant Python program, as they either are domain-specific or do not support high-level array operations such as broadcasting.

Expressive programming language.
Unlike many domain-specific front-ends [33,62,8,19], programs run in PrivPy do not need pre-compilation and there is no need to generate complex circuits for each program input before the computation starts. Users can specify loops on arbitrary conditions, as long as the conditions only rely on public variables (e.g. Line 5 in Fig. 2). Line 7 in Fig. 2 shows a loop relies on the public variable iter cnt, which can be an arbitrarily large positive integer.Other branches with public conditions, such as while and if, are also unrestrictive.
Parsing and optimizing automatically.
With the program written by users, the parse parses it to basic privacy-preserving operations supported by the back-end of PrivPy, and the optimizer automatically rewrites the program to improve efficiency (see Section 6 for details).

Computation engines
We realize that applications have very distinct requirements on security assumptions as well as performance. Thus, we decide to decouple the language front-end from the back-end computation engines. We can support any computation engine as long as they support basic operations such as addition, multiplication and comparison. We can easily port the language front-end to reuse the language tools and even machine learning algorithms. In our current prototype, we support a legacy computation engine as well as our own.
Active security with SPDZ engine. We support SPDZ by adding a very thin wrapper to handle the communications with our language front-end. The advantage of SPDZ is that it provides active security. However, SPDZ uses secure bit-level operations for operations on real numbers. Aside from the lower performance, SPDZ performs lots of pre-compilation of code, taking too much time and memory, especially for large inputs. This is mainly because: 1) the size of the generated circuit becomes very large for complex algorithms and large inputs; 2) building dependency trees and merging independent operations are memory hungry in SPDZ compilation. Thus, we design our own engine to avoid such cost.
High-performance passive security with PrivPy engine. We have developed a computation engine combining secret sharing scheme and garbled circuits. Our model provides passive security like Sharemind [8]. However, our computation protocols provide much better performance. Moreover, we optimize the computation engine for batch operations that are essential in largescale data mining problems. We detail the engine in the next two sections.

Assumptions
Moving the computation from clients to these servers effectively reduces the number of parties and thus improves system performance and scalability. Our computation engine uses independent semi-honest servers to perform computations, based on the following two assumptions: 1) there is no server conspiring with other servers to break the protocol; and 2) all communication channels are secure so that adversaries cannot see/modify anything in these channels.
To ensure 2), in PrivPy prototype, we use standard Secure Sockets Layer (SSL) for all communications. Assumption 1) is trickier, and at least two ways can help to realize it. First, there is a growing number of independent and competing cloud computing providers. Second, like the Blockchain protocol, we can use quorum election [54] to bound the probability of collusion. Third, trusted computing technologies such as Intel SGX [14,65] can make the computations on the servers more trustworthy. With these industry trends, it is feasible to find a small number of non-colluding computing servers. The actual method and incentive policy are beyond the scope of the paper. Actually, many well-known SMC frameworks such as [24,49,8,76,51,74] are based on such assumptions of semi-honest servers. And as stated above, such assumptions are rather rational.

Computation engine architecture
We use secret sharing scheme for private computation: a private variable x is split into two shares: x 1 and x 2 , and the shares are stored in the servers shown in Fig. 3. S 1 and S 2 are the primary servers. They work both as secret share storage and as computation engines. S 1 only touches all the x 1 's, while S 2 only handles x 2 's. To implement operations, we adopt two assistant servers, S a and S b , which only provide computation but no storage.
Our engine includes two subsystems. The secret sharing storage (SS store) subsystem provides (temporary) storage of shares of private inputs and intermediate results, and enforces correct access permission from different clients. SS store is partitioned into two parts, one on S 1 and the other on S 2 . The private operation (PO) subsystem runs on the four servers and provides an execution environment for private operations. Each server reads its share from the SS subsystem, executes a PO, and writes the shares of the result back to the SS store. With SS store and PO, our computation provides good scalability and efficiency.

An example workflow
With our computation engine, we present the PrivPy workflow using the code in Fig. 2 as an example.
Step 1: Setup. Before the computation starts, all participants first get a consensus on the program to execute, the private data input, and system configuration parameters.
Step 2: Program preparation. The parser in the frontend parses the program into basic operations. Then the optimizer optimizes the program. Once the program is ready, it is passed to the back-end for computation.
Step 3: Pooling secret shares. Each client computes the secret shares for private variables from itself, and sends the resulting shares to the SS store on the servers.
Step 4: Executing the POs on servers. After receiving all expected shares of secrets, the servers start the private computation without any client involvement.
Step 5: Revealing the final results to the clients. When the server invokes the reveal() method, the clients are notified to find the result shares in the SS store, and finally recover the cleartext result.

Mathematical preliminaries
We first review some mathematical preliminaries used in PrivPy for readers not familiar with the area.
Additive secret sharing. PrivPy uses the classic additive secret sharing scheme. Assume x is a non-negative integer and φ is a large integer. Let Z φ be the additive group of integers module φ . Given x 1 and x 2 in Z φ , we call them two shares of x as long as x = x 1 + x 2 mod φ . We then define the function S(x) = (r, x − r mod φ ), where r is a randomly picked integer in Z φ . We can see that S(x) is additively homomorphic in Z φ , i.e. the output of S(x) + S(y) is the shares of x + y mod φ . It is easy to see that both r and (x − r mod φ ) are uniformly random in Z φ , and in PrivPy, the two non-colluding servers S 1 and S 2 manage these shares independently. Thus, neither server learns anything about the private variable x.
Supporting real numbers. Note that the S(·) function above is defined on non-negative integers only. To map real numbers to Z φ , we use a typical discretization approach. Given a real number Actually, our representation is close to the fixed-point representation [11]. The reason why we do not use the floating-point representation is due to its inefficiency for basic operations (e.g. to perform secure addition with floating-point representation, we need to align the radix points, which is time-consuming) [38,2]. Meanwhile, fixed-point representations have been proved to be practical enough even for complex data mining tasks [53,34]. Note that negative numbers are mapped into the range [ φ 2 , φ ). Assuming all inputs and (accumulated) intermediate results are all within [−b, b], there will never be any unexpected sign flipping caused by overflowing φ 2 . We will show later that combining this frequently used mapping scheme with our PO design, we can get much more efficient POs than existing approaches.
Regarding precision, as the scaling factor is k, the precision is thus 1 k . For instance, assuming b = 2 32 and φ is 2 256 , we can set k = 2 128 then the precision is 2 −128 ≈ 3 × 10 −39 , which is enough for most real-life data mining applications. Of course, we can set k bigger to get better precision, as long as k < φ 2b . We will show later that the selection of k is actually a trade-off between precision and correctness of the POs. For simplicity, in this paper, we always set k to be the square root of φ . Thus, the users can use a single parameter φ to control the precision and computation cost.

The multiplication PO
Intuitively, for two real numbers x and y, as [[x]] = S( x) = (x 1 , x 2 ) and [[y]] = S( y) = (y 1 , y 2 ), i.e., x = x 1 +x 2 mod φ and y = y 1 + y 2 mod φ , we can calculate the product as: x * y = x 1 y 1 + x 2 y 2 + x 1 y 2 + x 2 y 1 mod φ . S 1 and S 2 can locally compute the terms x 1 y 1 and x 2 y 2 respectively, but as they are not allowed to exchange shares (otherwise the private data would be revealed), it is challenging to compute x 1 y 2 and x 2 y 1 . Homomorphic encryption based approaches [27] are quite costly. Secret sharing frameworks like [8,18,19] support efficient secure integer multiplication. To support real numbers, however, they use similar mapping schemes like that in PrivPy or other schemes to map real numbers to integers, but they all suffer from the wrap-round problem [17,41,11]. To solve this, they mask the shares with random integers sampled from a larger field, and use secure bit-level operations, such as bit decomposition and truncation, which require O(m) invocations of sending shares [17,11,45], where m is the bit length of the computation field. SecureML [55] provides builtin support for real numbers. However, its multiplication is similar to that of [18,19] which requires generation of multiplication triples, which is time-consuming. Steps: a) Server S 1 generates two random integer r x ∈ Z φ and r y ∈ Z φ , and sends them to c) S 1 sends x 1 to S a and sends y 1 to S b . S 2 sends x 2 to S b and sends y 2 to S a .
f) S a sends z a1 to S 1 and sends z a2 to S 2 . S b sends z b1 to S 1 and sends z b2 to S 2 .
We propose a much faster approach for secure multiplication using two assistant servers, which needs only O(1) invocations of sending shares and does not need the generation of multiplication triples, as Protocol 1 shows. An important detail is that the mapping scheme scales its input using a scaling factor k, thus each product term like x 1 y 2 contains the factor k 2 . Thus we need to adjust the result by dividing the factor. Next, we prove that this simple yet efficient multiplication scheme is correct and secure, and is free from the wrap-round problem. Analysis. (Correctness). We can verify that (x 1 , x 2 ) and (y 1 , y 2 ) in step b are the shares of x and y respectively. Define I(t) as an indicator function that converts an integer t in Z φ to the signed representation: Ignoring the rounding effect, we have I(x 1 ) + I(x 2 ) = kx and I(y 1 ) + I(y 2 ) = ky (we will prove it later). Thus I(x 1 )I(y 1 ) + I(x 1 )I(y 2 ) + I(x 2 )I(y 1 ) + I(x 2 )I(y 2 ) = (I(x 1 ) + I(x 2 ))(I(y 1 ) + I(y 2 )) = k 2 xy, which means the modular sum of z 1 , z 2 , z a and z b produced in step d is kxy mod φ , i.e. xy. Steps e to g calculate this sum and result shares are z 1 and z 2 produced in step g. Now we come back to prove that, with extremely high probability, I(x 1 ) + I(x 2 ) = kx and I(y 1 ) + I(y 2 ) = ky. First, we introduce two theorems (Please see Appendix .1 and Appendix .2 for the proofs of the theorems.).
Theorem 1 means that I(x 1 ) + I(x 2 ) = kx as long as sign(I(x 1 ) + I(x 2 )) = sign(x). The same applies to y. The following theorem shows that the probability Pr[sign(I(x 1 ) + I(x 2 )) = sign(x)] is extremely high.
Theorem 2. Given a private real number x, denoting the event sign(I(x 1 ) + I(x 2 )) = sign(x) as FAIL, we have As Theorem 2 shows, if we denote the event that sign(I(x 1 ) + I(x 2 )) = sign(x) and sign(I(y 1 ) + I(y 2 )) = sign(y) as SUCCESS, we have Pr Only steps c and f involve communications. And the numbers transfered between the servers are all randomly distributed integers generated by the secret sharing function. Therefore, no information is leaked to the servers.
(Complexity). Note that the random integers sharing in step a can be optimized by letting S 1 and S 2 use the same random number generator with the same seed so that we can avoid the transfer for these random integers. Thus there are 8 invocations: four in step c and four in step f , which is constant and independent of the bit length of φ .

The comparison PO
The (improved) Garbled Circuit(GC) [72] is one of the most communication-efficient secure comparison protocols [15,42]. The measurement in [21] also demonstrates this. PrivPy integrates GC with the secret sharing scheme in a novel way, and thus is more efficient than existing SS frameworks (e.g. [19,8]) which use expensive secure bit-level operations to implement comparison.
To integrate GC with secret sharing, previous approaches, such as [21,26], rely on conversions between arithmetic sharing and Yao's circuit sharing. Specifically, to compare [[x]] and [[y]], they convert each arithmetic share of x and y to two Yao's circuit shares, and perform addition circuits to get the Yao's circuit shares of x and y. Then they evaluate the comparison circuit, and finally convert the comparison result (represented using circuit sharing) back to arithmetic sharing. Our comparison protocol performs GC directly on the arithmetic shares, and does not need this type of conversion. Eliminating the conversions is the key factor making our comparison protocol more efficient. Protocol 2 details the process.
To implement GC, we use the free XOR construction [43,42]. Besides, we use the half-and trick [75] to reduce the size of garbled AND gates. We can further b) S 1 sends z 1a to S a and sends z 1b to S b . S 2 sends z 2a to S a and sends z 2b to S b . e) S a and S b generate random bits bita and bitb respectively. They collaboratively compute (bita ⊕ bitb ⊕ (z a −z b )) using GC, where ⊕ means XOR. c is the output of GC.
f) S a sends bita to S 1 and S 2 .
Then S b sends z b1 to S 1 and sends z b2 to S 2 .
optimize GC performance by moving the circuit generation and transfer to the setup phase, like [42] does.
Analysis. (Correctness). It is obvious that z a and z b at step c are shares of z = x − y. The purpose of step d is to convert integers to regular signed integers so that we can use GC to compare. This step produces z a , z b . Note that as Theorem 2 establishes, we have sign(z a + z b ) = sign(z). Clearly, z has the same sign as (x − y), so x y = z 0 = z a (−z b ). Thus, we can now perform GC directly on z a and (−z b ) to get the comparison result, without using the conversion in [21].
At step e, the comparison result is masked by two random bits bita and bitb generated independently by S a and S b , like [42] does. After receiving bita and the shares of bitb (step f ), S 1 and S 2 recover the shares of the original comparison result (step g). When bita = 1, they perform [ [1]] − S(bitb ⊕ c) to flip the bit. Finally, (z 1 , z 2 ) is the share of the result.
(Security). During the entire process, S 1 and S 2 only generate and receive secret shares. S a and S b perform the comparison between themselves, and the comparison result is masked by the random bits bita and bitb. Each server thus only sees random integers or garbled bits.
(Complexity). Apart from the communication triggered by GC, there are 8 invocations: four in step b and four in step f . In GC, following [42], we move the circuit generation and transfer to the setup phase. Thus, in the online phase of GC, S a only needs to send 3(l φ + 1)κ bits to S b , where l φ is the bit length of φ and κ is the PROTOCOL 3: Multiplication with public variables.
Input: Shares of a private variable SS(x) = (x 1 , x 2 ) and a constant k Output: z 1 and z 2 : shares of z = x * k Steps: Server S 1 calculates z 1 = x 1 * k mod φ . Server S 2 calculates z 2 = x 2 * k mod φ .
security parameter of GC. In this paper, we set κ = 128.

Derived POs
We can compose multiple basic POs and form a more complex derived PO. For example, we can use the Newton-Raphson algorithm [73] to implement division.
To implement the logistic function f (x) = 1 1+e −x , we use the Euler method [67]. We also implement other common maths functions using similar numerical methods, such as sqrt, log, exp and max pooling. We omit the details due to space limitation.

POs for performance optimization
We provide the following two sets of POs whose functionality is already covered by the basic POs, but the separate versions can significantly improve performance in certain cases. Programmers can use these POs directly. Array POs for performance optimization.
Many machine learning algorithms heavily utilize array operations. Therefore, we batch up array operations to reduce communication rounds. Specifically, we batch up independent data transfers among the servers and thus significantly reduce the fixed overhead. Multipy by public variables. In a case where an operation involves both public and private variables, we can optimize performance by revealing the public variables. Multiplication benefits from the optimization the most, as S 1 and S 2 only need to multiply their shares by the public variables directly and there is no necessary communication between servers.

Python Front-end and Optimizations
As discussed in Section 3, PrivPy provides a programming interface that is compatibility with plain Python code. In this section, we focus on the implementation and optimization of the programming interfaces.

Python Interfaces
PrivPy library implement the following features: Private array types. The private array class in PrivPy encapsulates arrays of any shape. Users only need to pass a private array to the constructor, then the constructor automatically detects the shape of the array. Like the array type in Numpy [68], our private array supports broadcasting, i.e. PrivPy can handle arithmetic operations with arrays of different shapes by "broadcasting" the smaller arrays. We also implement the ndarray methods in Numpy. Appendix .3 lists the ndarray methods we have implemented currently in the appendix. Broadcasting and ndarray methods are rather useful for implementing common machine learning algorithms which usually handles arrays of different shapes.
Operator overloading. We overload operators for private data classes, so standard operators such as +, −, * , > , = work on both private and public data, or a combination. The implementation of these overloaded operators chooses the right POs to use based on data types. Support for large arrays. Mapping the data onto secret shares unavoidably increases the data size. Thus, realworld datasets that fit in memory in cleartext may fail to load in the private version. For example, the 1000, 000 × 5048 matrix we use in our experiments require over 200 GB memory when mapped into a 256-bit long integer space. It is hard for application programmers to design new algorithms to handle the memory limit. Thus we provide a LargeArray class that transparently uses disks as the back storage for arrays too large to fit in memory. Fig. 2 has shown an example code of the logistic function written using our front-end. Fig. 4 shows an example of matrix factorization, which decomposes a large private matrix x to two latent matrices P and Q. We stress that PrivPy implements ndarray methods of Numpy. Therefore, users can first implement matrix factorization just as implementing it in plain Python with Numpy package as usual, then only need to replace the Numpy package with PrivPy package and add private variables declaration. Actually, by replacing all privpy with numpy, line 2-13 of Fig. 4 can run directly in raw Python environment with cleartext inputs.

Rejecting unsupported statements
We allow users to write legal Python code that we cannot run correctly, such as branches with private conditions (actually, most SMC tools do not support private conditions [76,51]. Those that do [76,74]only support limited scenarios). In order to minimize users' surprises at runtime, we perform AST level static checking to either rewrite or reject unsupported statements at the initialization phase. For example, for an expression containing private variables, if it is a simple case like res = a if cond else b, we will automatically rewrite it to res = b + cond * (a -b). On more complex cases, we prompt the user at the initialization phase whether they 0.3 0.87 9.07e-3 9.0e-3 0.89

PrivPy implementation.
We implement the main program of PrivPy with Python. We hand-code GCbased comparison in C++ with the Crypto++ library. We compile the C++ code using gcc -O3, and wrap it into Python code. We use SSL with 1024-bit key to protect all communications. We measure that the round-trip time of sending a 10-byte message with SSL is about 0.1 ms.

Parameter setting.
In the following benchmarks, we fix the bit length of φ to 256 for simplicity. We also set the scaling factor k = 128, thus the precision is 2 −128 ≈ 3 × 10 −39 . This is enough for most common applications. We repeat each experiment 100 times and report the average values.

Basic operations
To demonstrate the performance of basic operations in PrivPy, we evaluate the fundamental POs, as well as the basic secret sharing process.
Fundamental POs. The fundamental POs are +, × and >. We compare two versions of these POs based on the operand types: two private variables, and one private variable with one public variable. Table 1 shows the result, and we have the following observations: a) × and > are slower than +, due to communication. b) × with a public is 30× faster than the two-private version, due to the multiply-by-public optimization. c) + with a public number is slower than the normal version. This is because the servers should map public variables during the computation. We are developing a variable analysis tool to automatically identify POs involving public variables, so that the client can preprocess them.
Derived POs with numerical methods. Derived POs in Section 5.5 approximate non-linear operations using iter-  ative numerical methods. We evaluate the relative error and execution time with different numbers of iterations. For division, we use the default initial value of 1.0e−8, and evaluate the expression of 1/x. For the logistic function, we use the default starting value of 0. Figure 5 plots the relative error and execution time with different number of iterations and different values of the input x. We can see the per-iteration time is reasonably short and the algorithm converges fast.
Note that different from cleartext algorithms, as the servers do not see the outcome of each iteration, they cannot tell whether the result has converged or not. Thus, we need to set a conservative iteration limit as a tradeoff between result accuracy and computation time. For all our experiments, we use 50 iterations, and it takes about 30 ms to compute a division or logistic function.
Client-server interaction overload We evaluate the client time consumption (including computation and communication) of the secret sharing process ss and the result recover process reveal. Figure 6 shows that even with 1000 clients and 1000-dimension vectors, it takes only less 0.6 seconds for the servers to collect/reveal all the vectors from/to all the clients.

Effectiveness of optimizations
Now we show the improvement with batch operations and the code optimizer.
Batch array operations. We compare the performance of batch PO operations with the scalar PO implementation. We evaluate two common operations: element-wise multiplication and element-wise comparison on vectors. We vary the number of elements and measure the time  x * y1 + x * y2 + + x * yn x * (y1 + y2 + + yn) consumption. Figure 7 shows the result. The optimized element-wise multiplication is about 25× faster than the unoptimized, while the optimized element-wise comparison is about 12× faster. Thus, batching up significantly accelerates the computation, especially for "big data" tasks that usually involves many dimensions.
Other code optimizations. We evaluate the common factor extraction and expression vectorization. As these hand-written anti-patterns are usually small, we range the expression size from 2 to 10. Figure 8 shows that the optimizations lead to 2.5× performance improvement for five-term expressions in both situations.

Comparison with existing approaches
We compare the performance of PrivPy with existing approaches. We only choose systems that at least support both additions and multiplications. HElib [29] is an implementation of (leveled) FHE, which has a parameter m controlling the depth of circuits. We use a choice of small m = 4096 only allowing shallow circuits. Even so, HElib is less efficient than PrivPy. Obliv-C [74] is a highly optimized garbled circuit implementation. And to support real numbers, we convert each real number to a large integer by multiplying a scaling factor, following the sample code [32]. P4P+HE P4P [24] is a practical additive secret sharing based system. Following [3], we add a partial-HE (i.e. 1024-bit Paillier [57]) based multiplication on to P4P. SPDZ [19] As described in Section 3, we port SPDZ into the PrivPy framework. We evaluate both the native SPDZ (the Raw SPDZ in the following discussion), and SPDZ with PrivPy front-end (SPDZ + PrivPy). In this paper, SPDZ runs on two servers for two-party computation. We compare the performance of +, × and >. Table 2 presents the latency of basic scalar operations, and Table 3 shows the throughput. Note that not all frameworks above support multi-core CPUs like PrivPy. Therefore, to evaluate their throughputs, we run multiple independent processes of these frameworks and add up the throughput. We also ignore the time for compilation, program loading and pre-computation of Obliv-C and SPDZ, though it is non-negligible. Even so, PrivPy still performs much better. Our key observations include: 1) For +, PrivPy, P4P and SPDZ have similar performance, as they are all secret-sharing-based. HElib and Obliv-C need to evaluate encrypted or garbled circuits and handle carry bits for secure addition, thus slower than the secret-sharing-based tools.
2) For ×, as Table 2 shows, secret-sharing-based tools, such as SPDZ and PrivPy, show a 5× improvement over Obliv-C for a single multiplication, by using secret sharing servers instead of HE or garbled circuits. Moreover, as Table 3 shows, the multiplication throughput of PrivPy is over 30× better than others, thanks to our efficient multiplication PO.
3) SPDZ uses expensive secure bit-level operations. PrivPy and Obliv-C implement comparison using GC, which is more efficient than the secure bit-level operations. The main reason that PrivPy is slower than Obliv-C for a single comparison is that PrivPy compares 256bit integers while Obliv-C works only on 64-bit ones. However, thanks to our optimization, the throughput of PrivPy is 2× higher than that of Obliv-C and 7× higher than that of SPDZ. 4) SPDZ + PrivPy has similar performance as the raw SPDZ, showing minimal cost of our front-end porting.
Note that although SPDZ provides active security by generating and keeping MACs of private data and may introduce extra cost, the cost mainly resides at the precomputation phase, while updating MACs in the online phase can be done efficiently with simple operations and involves no extra communication and thus brings little impact on the overall performance. As we evaluate the performance of online phase and ignore the time for precomputation, the big gap of performance between SPDZ and PrivPy presented above still comes from the computaion protocol itself, as we analyzed in Section 5.
Another thing to note is that, in the above evaluation we do not compare with Sharemind [8], which is as far as we know state-of-the-art SMC framework based on passive security, as it is a closed-source commercial product and we do not have the access. However, according to the report of [22], PrivPy performs about 16× better than Sharemind for the throughput of fixed-point multiplication, even if their experiments ran on faster servers. Another notable system is SecureML [55], which provides builtin support for decimal numbers like PrivPy. But it does not provide any language front-end. However, according to the report in [55], the overall through-

Performance in real algorithms
PrivPy supports real learning algorithms with large-scale datasets. Here we evaluate both model training and inference. For training, we use three real datasets and three algorithms. For inference, we evaluate traditional feedforward neural network and convolutional neural network. And as our front-end supports both PrivPy engine and SPDZ engine, we run the same code on both PrivPy and PrivPy + SPDZ. It takes a long time to pre-compile the code to run on SPDZ (e.g. it takes 16 minutes to compile logistic regression on 1000 instances of the Adult dataset in SPDZ) or even crashes. PrivPy does not suffer from this problem. Again, we ignore the compilation and precomputation time in the evaluation. The result shows the efficiency and practicability of PrivPy.

Model training on secret datasets
We use three real-world datasets. We treat the records in these datasets private and train models using them. 2) CreditCard [16] consists of 284, 807 credit card transactions with 28 numeric features each.
3) Movielens [31] contains 1 million movie ratings from thousands of users. We encode it to a 1000, 000 × 5048 matrix. As it is too large to fit into memory, we treat it as a disk-backed LargeArray. Moreover, we evaluate the following three algorithms.
Logistic regression (LR) [30]. We train logistic regression using Stochastic Gradient Descent (SGD), which calculates the gradients of the weights in each iteration.
K-means [58]. K-means is a method for unsupervised clustering, which updates the centroids and the clusters of the instances in each iteration. In all k-means evaluations, we set the number of clusters to 5.
Matrix factorization (MF) [6]. It decomposes a large matrix into two smaller latent matrices for efficient prediction, which performs several matrix multiplications in each iteration. In this paper, we decompose each m × n matrix to a m × 5 matrix and a 5 × n matrix. Table 4 summarizes the average time consumed by each instance with different batch sizes in an iteration.
The key observations are: 1) batch operations bring perinstance performance improvements in all algorithms; 2) SPDZ fails to handle larger scale cases, as its precompilation module runs out of memory and crashes for the reasons we have discussed in Section 3.2; and 3) PrivPy uses the LargeArray to handle the largest Movielens dataset, and the program works ok.
To verify the accuracy, we compute the RRMSE (Relative Root Mean Squared Error) of the resulting model parameters between PrivPy and the cleartext version after each iteration for the Adult and Creditcard dataset. Unlike [55], which suffers from large precision loss because it replaces standard activation functions with simplified versions, PrivPy supports direct approximations of these functions (Section 5.5) and the precision loss is negligible. Figure 9 shows that the RRMSE is small (1e−9 range and 1e−11 on average) even after 2, 000 iterations. We verify that the computation error is negligible and the prediction accuracy on the two datasets is the same as the cleartext version.

Neural network (NN) inference
We use MNIST dataset [47] with 70, 000 labeled handwritten digits [13] with 28 × 28 pixels each. We use three example neural networks for handwritten digits recognition to evaluate the inference performance, by treating both the model and the data as private. Note that we do not present the results of neural networks on SPDZ, as SPDZ is able to compile none of these cases successfully.    processing images in batch. This is acceptable considering the privacy guarantee. We verify that the classification result is the same as the cleartext version. To the best of our knowledge, this is the first practical implementation of a real convolutional neural network using a noise-free privacy-preserving method.

Conclusion and Future Work
To design a "practical" privacy-preserving computation system, there are many trade-offs to make, such as performance, security, ease of programming, and compatibility with existing code etc. PrivPy strives to make a right trade-off with a few key design choices: 1) providing compatible Python programming interfaces with the support for multiple back-ends; 2) designing a new computation engine that allows very fast multiplication and comparison, and supports real numbers and arrays natively; and 3) using code optimizer/checkers to avoid common mistakes. Compared with existing SMC frameworks, PrivPy is more efficient and practical. PrivPy opens up many future directions. Firstly, we are improving the PrivPy back-end to provide active security like SPDZ while preserving high efficiency. Secondly, we would like to port existing machine learning libraries to our front-end. Thirdly, we will port more existing frameworks with unique security features to our programming interface. Last but not least, we will also improve fault tolerance mechanism to the servers.

.3 Numpy features implemented in PrivPy
In PrivPy front-end, we provide two Numpy features widely utilized to implement machine learning algorithms: broadcasting and ndarray methods. Broadcasting allows operations between arrays of different shapes, by "broadcasting" the smaller one automatically, as long as their dimensionalities match (see [36] for details). For example, given a scalar x, a 4 × 3 array A, a 2×4×3 array B and a 2×1×3 array C, the expressions x A, A B and B C are all legal in PrivPy, where can be +, ×and > etc. Note that in PrivPy, the above variables can be either public or private.
We also implement most of the ndarray methods of Numpy, with which application programmers can manipulate arrays conveniently and efficiently, except for the methods related with IO (we leave IO as the future work). Table 8 lists the ndarray methods we have implemented. Please see [37] for details of numpy.ndarray .   all  any  append  argmax  argmin  argparition  argsort  clip  compress  copy  cumprod  cumsum  diag  dot  fill  flatten  item  itemset  max  mean  min  ones  outer  partition  prod  ptp  put  ravel  repeat  reshape  resize  searchsorted  sort  squeeze  std  sum  swapaxes  take  tile  trace  transpose var zeros