Search

We introduce COINN - an efficient, accurate, and scalable framework for oblivious deep neural network (DNN) inference in the two-party setting. In our system, DNN inference is performed without revealing the client's private inputs to the server or revealing server's proprietary DNN weights to the client. To speedup the secure inference while maintaining a high accuracy, we make three interlinked innovations in the plaintext and ciphertext domains: (i) we develop a new domain-specific low-bit quantization scheme tailored for high-efficiency ciphertext computation, (ii) we construct novel techniques for increasing data re-use in secure matrix multiplication allowing us to gain significant performance boosts through factored operations, and (iii) we propose customized cryptographic protocols that complement our optimized DNNs in the ciphertext domain. By co-optimization of the aforesaid components, COINN brings an unprecedented level of efficiency to the setting of oblivious DNN inference, achieving an end-to-end runtime speedup of 4.7×14.4× over the state-of-the-art. We demonstrate the scalability of our proposed methods by optimizing complex DNNs with over 100 layers and performing oblivious inference in the Billion-operation regime for the challenging ImageNet dataset. Our framework is available at https://github.com/ACESLabUCSD/COINN.git.

Privacy-preserving deep learning computing becomes popular these days as it helps protect, for example, both user data and deep neural network (DNN) model parameters at the same time with cryptographic techniques. In particular, significant efforts have been made to leverage secure two-party computation schemes for preventing user/model data from disclosure during DNN inference. Nevertheless, the existing works require manual intervention while converting trained models into secure computation programs, which is not scalable to modern deep networks efficiently. In this work, we propose a compiler framework, TONIC, to do the conversion automatically with scalability. Given a pre-trained DNN model, TONIC converts it into one of two secure two-party computation languages, i.e., ObliVM and ABY. Based on tailored backends built on top of a DNN compiler, TVM, our case studies show that TONIC is able to automatically convert popular DNN models, such as CryptoNets and MobileNetV2, into the corresponding programs for secure computations.

One of the most challenging aspects in secure computation is offering protection against active adversaries, who may arbitrarily alter the behavior of corrupted parties. A powerful paradigm due to Goldreich, Micali, and Wigderson (GMW), is to follow a two-step approach: (1) design a passively secure protocol π for the task at hand; (2) apply a general compiler to convert π into an actively secure protocol π' for the same task. In this work, we implement the first two-party actively secure protocol whose design is based on the general GMW paradigm. Our implementation applies to a passively secure π based on garbled circuits, using a sublinear zero-knowledge proof to ensure correctness of garbling. The main variant of our protocol makes a black-box use of an underlying oblivious transfer primitive by following the "certified oblivious transfer" blueprint of Ishai et al. (Eurocrypt 2011) and Hazay et. al. (TCC 2017). We also analyze a conceptually simpler but less efficient variant that makes a non-black-box use of oblivious transfer. Our protocol has several important advantages. It supports non-interactive secure computation (NISC), where a receiver posts an "encryption" of its input and gets back from a sender an "encryption" of the output. The efficiency of this NISC protocol is enhanced by using an offline non-interactive preprocessing, where the sender publishes a single garbled circuit together with a proof of correctness, while the receiver need not even be online. The online work of both the sender and the receiver is lightweight, with a small overhead compared Yao's passively secure protocol depending mostly on the input size rather than the circuit size.

We propose a new secure equality testing (SET) protocol, namely SET-OT, for two-party setting by using a recently introduced Private Set Membership Protocol (PSM) based on Oblivious Transfer (OT) as a building block. We designed our equality test in such a way that the test result will not be revealed in clear text, which is desired in several cryptographic protocols. The advantage of using OT is that with the help of OT Extension (OTE) protocols, the cost of asymmetric operations per OT operations reduces when the number of OT executions increases. This makes our protocol competitive especially for the cases where the number of equality tests to be invoked is high. When the number of equality test increases, the time complexity of SET-OT converges to one asymmetric key decryption operation, this operation is the dominant part in terms of computational cost. SET-OT has a better performance in terms of the communication rounds and data transmission cost than state-of-the-art solutions: three communication rounds and 2.9 KB of data transmission are the communication costs of performing equality testing protocol for 20-bit string pairs. In addition to our complexity analysis, we also present test results to validate our claim on performance.

Secure Two Party Computation (2PC) has the potential to facilitate a wide range of real life applications where privacy of the computation and participants is critical. Nevertheless, this potential has not translated to widespread industry acceptance due to performance issues. Over the years a significant research effort has focused on optimising the performance of 2PC. The computation complexity has been continually improved and recently, following circuit optimisations and hardware support for cryptographic operations, evaluations of 2PC on a single host currently produce efficient results. Unfortunately, when evaluated on remote hosts, the performance remains prohibitive for practical purposes. The bottleneck is believed to be the bandwidth. In this work we explore the networking layer of 2PC implementations and show that the performance bottleneck is inherent in the usage of TCP sockets in implementations of 2PC schemes. Through experimental evaluations, we demonstrate that other transport protocols can significantly improve the performance of 2PC, making it suitable for practical applications.

Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.

Group exponentiation is an important operation used in many public-key cryptosystems and, more generally, cryptographic protocols. To expand the applicability of these solutions to computationally weaker devices, it has been advocated that this operation is outsourced from a computationally weaker client to a computationally stronger server, possibly implemented in a cloud-based architecture. While preliminary solutions to this problem considered mostly honest servers, or multiple separated servers, some of which honest, solving this problem in the case of a single (logical), possibly malicious, server, has remained open since a formal cryptographic model was introduced in [20]. Several later attempts either failed to achieve privacy or only bounded by a constant the (security) probability that a cheating server convinces a client of an incorrect result.In this paper we solve this problem for a large class of cyclic groups, thus making our solutions applicable to many cryptosystems in the literature that are based on the hardness of the discrete logarithm problem or on related assumptions. Our main protocol satisfies natural correctness, security, privacy and efficiency requirements, where the security probability is exponentially small. In our main protocol, with very limited offline computation and server computation, the client can delegate an exponentiation to an exponent of the same length as a group element by performing an exponentiation to an exponent of short length (i.e., the length of a statistical parameter). We also show an extension protocol that further reduces client computation by a constant factor, while increasing offline computation and server computation by about the same factor.

Numerous cryptographic protocols and mechanisms have been developed to solve computer security challenges, and these techniques vary considerably with respect to security assumptions, performance tradeoffs, and applicability to problems. Secure hardware primarily uses the mechanism of isolation to solve a broad class of computer security problems, ranging from private information retrieval to verifiable computation. In this talk, I will contrast the two approaches by focusing on the application of remote outsourced computation. I will describe a spectrum of approaches that vary in their use of cryptography and isolation to achieve secure remote computation. I will end with describing challenges that remain in the deployment of secure hardware.

Machine learning models hosted in a cloud service are increasingly popular but risk privacy: clients sending prediction requests to the service need to disclose potentially sensitive information. In this paper, we explore the problem of privacy-preserving predictions: after each prediction, the server learns nothing about clients' input and clients learn nothing about the model. We present MiniONN, the first approach for transforming an existing neural network to an oblivious neural network supporting privacy-preserving predictions with reasonable efficiency. Unlike prior work, MiniONN requires no change to how models are trained. To this end, we design oblivious protocols for commonly used operations in neural network prediction models. We show that MiniONN outperforms existing work in terms of response latency and message sizes. We demonstrate the wide applicability of MiniONN by transforming several typical neural network models trained from standard datasets.

While the feasibility of constant-round and actively secure MPC has been known for over two decades, the last few years have witnessed a flurry of designs and implementations that make its deployment a palpable reality. To our knowledge, however, existing concretely efficient MPC constructions are only for up to three parties. In this paper we design and implement a new actively secure 5PC protocol tolerating two corruptions that requires 8 rounds of interaction, only uses fast symmetric-key operations, and incurs 60% less communication than the passively secure state-of-the-art solution from the work of Ben-Efraim, Lindell, and Omri [CCS 2016]. For example, securely evaluating the AES circuit when the parties are in different regions of the U.S. and Europe only takes 1.8s which is 2.6x faster than the passively secure 5PC in the same environment. Instrumental for our efficiency gains (less interaction, only symmetric key primitives) is a new 4-party primitive we call Attested OT, which in addition to Sender and Receiver involves two additional "assistant parties" who will attest to the respective inputs of both parties, and which might be of broader applicability in practically relevant MPC scenarios. Finally, we also show how to generalize our construction to n parties with similar efficiency properties where the corruption threshold is t ≈ √n, and propose a combinatorial problem which, if solved optimally, can yield even better corruption thresholds for the same cost.

We propose a new, constant-round protocol for multi-party computation of boolean circuits that is secure against an arbitrary number of malicious corruptions. At a high level, we extend and generalize recent work of Wang et al. in the two-party setting. Namely, we design an efficient preprocessing phase that allows the parties to generate authenticated information; we then show how to use this information to distributively construct a single "authenticated" garbled circuit that is evaluated by one party. Our resulting protocol improves upon the state-of-the-art both asymptotically and concretely. We validate these claims via several experiments demonstrating both the efficiency and scalability of our protocol: Efficiency: For three-party computation over a LAN, our protocol requires only 95 ms to evaluate AES. This is roughly a 700X improvement over the best prior work, and only 2.5X slower than the best known result in the two-party setting. In general, for n-party computation our protocol improves upon prior work (which was never implemented) by a factor of more than 230n, e.g., an improvement of 3 orders of magnitude for 5-party computation. Scalability: We successfully executed our protocol with a large number of parties located all over the world, computing (for example) AES with 128 parties across 5 continents in under 3 minutes. Our work represents the largest-scale demonstration of secure computation to date.

We propose a simple and efficient framework for obtaining efficient constant-round protocols for maliciously secure two-party computation. Our framework uses a function-independent preprocessing phase to generate authenticated information for the two parties; this information is then used to construct a single "authenticated" garbled circuit which is transmitted and evaluated. We also show how to efficiently instantiate the preprocessing phase with a new, highly optimized version of the TinyOT protocol by Nielsen et al. Our protocol outperforms existing work in both the single-execution and amortized settings, with or without preprocessing: In the single-execution setting, our protocol evaluates an AES circuit with malicious security in 37 ms with an online time of 1 ms. Previous work with the best overall time requires 62 ms (with 14 ms online time); previous work with the best online time (also 1 ms) requires 124 ms overall.If we amortize over 1024 executions, each AES computation requires just 6.7 ms with roughly the same online time as above. The best previous work in the amortized setting has roughly the same total time but does not support function-independent preprocessing. Our work shows that the performance penalty for maliciously secure two-party computation (as compared to semi-honest security) is much smaller than previously believed.

Self-stabilization refers to the ability of systems to recover after temporal violations of conditions required for their correct operation. Such violations may lead the system to an arbitrary state from which it should automatically recover. Today, beyond recovering functionality, there is a need to recover security and confidentiality guarantees as well. To the best of our knowledge, there are currently no self-stabilizing protocols that also ensure recovering confidentiality, authenticity, and integrity properties. Specifically, self-stabilizing systems are designed to regain functionality which is, roughly speaking, desired input output relation, ignoring the security and confidentiality of computation and its state. Distributed (cryptographic) protocols for generic secure and privacy-preserving computation, e.g., secure Multi-Party Computation (MPC), usually ensure secrecy of inputs and outputs, and correctness of computation when the adversary is limited to compromise only a fraction of the components in the system, e.g., the computation is secure only in the presence of an honest majority of involved parties. While there are MPC protocols that are secure against a dishonest majority, in reality, the adversary may compromise all components of the system for a while; some of the corrupted components may then recover, e.g., due to security patches and software updates, or periodical code refresh and local state consistency check and enforcement based on self-stabilizing hardware and software techniques. It is currently unclear if a system and its state can be designed to always fully recover following such individual asynchronous recoveries. This paper introduces Secure Self-stabilizing Computation which answers this question in the affirmative. Secure self-stabilizing computation design ensures that secrecy of inputs and outputs, and correctness of the computation are automatically regained, even if at some point the entire system is compromised. We consider the distributed computation task as the implementation of virtual global finite satiate machine (FSM) to present commonly realized computation. The FSM is designed to regain consistency and security in the presence of a minority of Byzantine participants, e.g., one third of the parties, and following a temporary corruption of the entire system. We use this task and settings to demonstrate the definition of secure self-stabilizing computation. We show how our algorithms and system autonomously restore security and confidentiality of the computation of the FSM once the required corruption thresholds are again respected.

Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds? We provide a positive answer to this question. We define a new type of encryption, called functionally equivocal encryption (FEE), and show that when Yao's scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function. Combining our scheme with non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-rounds multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. A number of extensions and applications are described within.

In many areas such as bioinformatics, pattern recognition, and signal processing, Hidden Markov Models (HMMs) have become an indispensable statistical tool. A fundamental building block for these applications is the Forward algorithm which computes the likelihood to observe a given sequence of emissions for a given HMM. The classical Forward algorithm requires that one party holds both the model and observation sequences. However, we observe for many emerging applications and services that the models and observation sequences are held by different parties who are not able to share their information due to applicable data protection legislation or due to concerns over intellectual property and privacy. This renders the application of HMMs infeasible. In this paper, we show how to resolve this evident conflict of interests using secure two-party computation. Concretely, we propose Priward which enables two mutually untrusting parties to compute the Forward algorithm securely, i.e., without requiring either party to share her sensitive inputs with the other or any third party. The evaluation of our implementation of Priward shows that our solution is efficient, accurate, and outperforms related works by a factor of 4 to 126. To highlight the applicability of our approach in real-world deployments, we combine Priward with the widely used HMMER biosequence analysis framework and show how to analyze real genome sequences in a privacy-preserving manner.

Cloud computing offers an attractive and cost-efficient computing platform and hence it has been widely adopted by the industry and the government. At the same time, cloud computing poses a serious security challenge because sensitive data must often be outsourced to third party entities that can access the data and perform computations on them. Partial homomorphic encryption is promising for secure computation, since it allows programs to be executed over encrypted data. Despite advances in cryptographic techniques have improved the expressivity of such programs, integration with mainstream languages has seen little progress. To this end, we present SecureScala, a domain-specific language in Scala that allows expressing secure programs without requiring any cryptographic knowledge. SecureScala is based on a novel combination of free monads and free applicative functors and supports parallel execution and static analyzability. We evaluate our approach through several case studies, demonstrate its expressivity, and show that it incurs in limited performance overhead.

Motivated by the impossibility of achieving fairness in secure computation [Cleve, STOC 1986], recent works study a model of fairness in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty to every other party that did not receive the output. These works show how to design protocols for secure computation with penalties that tolerate an arbitrary number of corruptions. In this work, we improve the efficiency of protocols for secure computation with penalties in a hybrid model where parties have access to the “claim-or-refund” transaction functionality. Our first improvement is for the ladder protocol of Bentov and Kumaresan (Crypto 2014) where we improve the dependence of the script complexity of the protocol (which corresponds to miner verification load and also space on the blockchain) on the number of parties from quadratic to linear (and in particular, is completely independent of the underlying function). Our second improvement is for the see-saw protocol of Kumaresan et al. (CCS 2015) where we reduce the total number of claim-or-refund transactions and also the script complexity from quadratic to linear in the number of parties. We also present a ‘dual-mode’ protocol that offers different guarantees depending on the number of corrupt parties: (1) when s < n/2 parties are corrupt, this protocol guarantees fairness (i.e., either all parties get the output or none do), and (2) when t > n/2 parties are corrupt, this protocol guarantees fairness with penalties (i.e., if the adversary gets the output, then either the honest parties get output as well or they get compensation via penalizing the adversary). The above protocol works as long as t+s < n, matching the bound obtained for secure computation protocols in the standard model (i.e., replacing “fairness with penalties” with “securitywith-abort” (full security except fairness)) by Ishai et al. (SICOMP 2011). Keywords: Bitcoin, secure computation, fairness., National Science Foundation (U.S.) (Grant CNS-1350619), National Science Foundation (U.S.) (Grant CNS1414119), Alfred P. Sloan Foundation (Research Fellowship), Microsoft (Faculty Fellowship)

Secure multi-party computation (SMPC) is a cryptographic tool that enables a set of parties to jointly compute any function of their inputs while keeping the privacy of inputs. The paper "High Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority" in this ACM CCS 2016 [4] presents a new protocol which its implementation carried out over 1,300,000 AESs per second and was able to support 35,000 login queries of Kerberos authentication per second. This poster/demo presents the design of the implementation and demonstrates the Kerberos authentication over here. The design will show how this high-throughput three-party computation can be done using simple servers. The demonstration proves that secure multiparty computation of Kerberos authentications in large organizations is now practical.

This paper extends the choice available for secure real number implementations with two new contributions. We will consider the numbers represented in form a-φ b where φ is the golden ratio, and in form (-1)s.2e where e is a fixed-point number. We develop basic arithmetic operations together with some frequently used elementary functions. All the operations are implemented and benchmarked on SHAREMIND secure multi-party computation framework. It turns out that the new proposals provide viable alternatives to standard floating- and fixed-point implementations from the performance/error viewpoint in various settings. However, the optimal choice still depends on the exact requirements of the numerical algorithm to be implemented.

When a group of individuals and organizations wish to compute a stable matching---for example, when medical students are matched to medical residency programs---they often outsource the computation to a trusted arbiter in order to preserve the privacy of participants' preferences. Secure multi-party computation offers the possibility of private matching processes that do not rely on any common trusted third party. However, stable matching algorithms have previously been considered infeasible for execution in a secure multi-party context on non-trivial inputs because they are computationally intensive and involve complex data-dependent memory access patterns. We adapt the classic Gale-Shapley algorithm for use in such a context, and show experimentally that our modifications yield a lower asymptotic complexity and more than an order of magnitude in practical cost improvement over previous techniques. Our main improvements stem from designing new oblivious data structures that exploit the properties of the matching algorithms. We apply a similar strategy to scale the Roth-Peranson instability chaining algorithm, currently in use by the National Resident Matching Program. The resulting protocol is efficient enough to be useful at the scale required for matching medical residents nationwide, taking just over 18 hours to complete an execution simulating the 2016 national resident match with more than 35,000 participants and 30,000 residency slots.

In this paper, we describe a new information-theoretic protocol (and a computationally-secure variant) for secure three-party computation with an honest majority. The protocol has very minimal computation and communication; for Boolean circuits, each party sends only a single bit for every AND gate (and nothing is sent for XOR gates). Our protocol is (simulation-based) secure in the presence of semi-honest adversaries, and achieves privacy in the client/server model in the presence of malicious adversaries. On a cluster of three 20-core servers with a 10Gbps connection, the implementation of our protocol carries out over 1.3 million AES computations per second, which involves processing over 7 billion gates per second. In addition, we developed a Kerberos extension that replaces the ticket-granting-ticket encryption on the Key Distribution Center (KDC) in MIT-Kerberos with our protocol, using keys/ passwords that are shared between the servers. This enables the use of Kerberos while protecting passwords. Our implementation is able to support a login storm of over 35,000 logins per second, which suffices even for very large organizations. Our work demonstrates that high-throughput secure computation is possible on standard hardware.

We present the first complexity-theoretic secure steganographic protocol which, for any communication channel, is provably secure, reliable, and has nearly optimal bandwidth. Our system is unconditionally secure, i.e. our proof does not rely on any unproven complexity-theoretic assumption, like e.g. the existence of one-way functions. This disproves the claim that the existence of one-way functions and access to a communication channel oracle are both necessary and sufficient conditions for the existence of secure steganography, in the sense that secure and reliable steganography exists independently of the existence of one-way functions.

The secure two-party computation (S2PC) protocols SHADE and GSHADE have been introduced by Bringer et al. in the last two years. The protocol GSHADE permits to compute different distances (Hamming, Euclidean, Mahalanobis) quite efficiently and is one of the most efficient compared to other S2PC methods. Thus this protocol can be used to efficiently compute one-to-many identification for several biometrics data (iris, face, fingerprint).In this paper, we introduce two extensions of GSHADE. The first one enables us to evaluate new multiplicative functions. This way, we show how to apply GSHADE to a classical machine learning algorithm. The second one is a new proposal to secure GSHADE against malicious adversaries following the recent dual execution and cut-and-choose strategies. The additional cost is very small. By preserving the GSHADE's structure, our extensions are very efficient compared to other S2PC methods.

Secure sum protocol allows computing sum of individual data of a group of cooperating parties without divulging the individual data to other parties. Protocols exist in the literature for the secure sum computation but these protocols presume the network to be secure. We propose secure sum computation protocol when the network lines are insecure. When a cooperating party sends its private data to another party, the data can be encrypted using either symmetric or asymmetric cryptographic techniques. We also proposed a protocol which is suitable against colluding neighbors who may try to learn the secret data of some party. It ensures that an intruder cannot learn the data over the network. We show that how we achieve better security during secure sum computation.

We consider how to perform privacy-preserving analyses on private data from different data providers and containing personal information of many different individuals. We combine differential privacy and secret sharing based secure multiparty computation in the same system to protect the privacy of both the data providers and the individuals. We have implemented a prototype of this combination and have found that the overhead of adding differential privacy to secure multiparty computation is small enough to be usable in practice.

Sharemind is an efficient framework for secure multiparty computations (SMC). Its efficiency is in part achieved through a large set of primitive, optimized SMC protocols that it makes available to applications built on its top. The size of this set has brought with it an issue not present in frameworks with a small number of supported operations: the set of protocols must be maintained, as new protocols are still added to it and possible optimizations for a particular sub-protocol should be propagated into larger protocols working with data of different types. To ease the maintenance of existing and implementation of new protocols, we have devised a domain-specific language (DSL) and its optimizing compiler for specifying protocols for secure computation. In this paper, we give the rationale of the design, describe the translation steps, the location of the compiler in the whole Sharemind protocol stack, and the results obtained with this system.

Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency. We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao's (semi-honest) 2PC protocol. We demonstrate the practicality of our protocol with an implementation based on the JustGarble framework of Bellare et al. (S&P 2013). The implementation incorporates various optimizations including the most recent techniques for efficient circuit garbling. We perform experiments on several benchmarking circuits, in different setups. Our experiments confirm that, despite providing a more demanding security guarantee, our protocol has performance comparable to existing information-theoretic 3PC.

The paper considers the problem of organization the computations over encrypted data. This problem has become increasingly important due to the expansion of the cloud computing and the need for suitable measures to protect it. Different primitives were proposed to solve the problem in a limited context, such as garbled circuits, fully homomorphic encryption, functional encryption, secure multiparty computations and so on. However, the development of real secure computing system requires some general theory for organization of secure computing, using a systemic approach. We propose to divide all the functionality that the secure computing system must support into the several layers; the interaction between them would be done through the interfaces. Presented six-layer analytical model under the title "Secure computing interface stack" ("SCIS") is intended to standardize and facilitate the work of researchers and developers in the field of cryptographically secure computing, i.e. such systems in which the untrusted parties process the sensitive data in encrypted form without decrypting at the any stage of processing. For each layer we outline the problems researchers deal with, reveal a range of issues that must be addressed, and provide a brief overview of the relative works. We survey and compare known secure computation systems analyzing them within our model and derive some new ideas for improvements of existing CSCS.

Yao's garbled circuit technique is often used in outsourced computation. Current approaches divide the computation to two or more servers. The assumption is that the servers collaborate in offering the outsourced computation, but do not share data. This seems somewhat paradoxical in the current cloud economy. We therefore propose oblivious outsourcing where one server is unaware that other servers are involved. We present a garbled circuit generation outsourcing scheme built on lattice-based cryptography implementing this model. Our scheme does not increase the cost of circuit evaluation, but achieves a speed up of 98% (factor 55) for circuit generation.

We study the problem of how to efficiently outsource a sensitive computation on secret inputs to a number of untrusted workers, under the assumption that at least one worker is honest.In our setting there is a number of clients C_1,…,Cn with inputs x1,…,xn. The clients want to delegate a secure computation of f(x1,…,xn) to a set of untrusted workers W1,…,Wm. We want do so in such a way that as long at there is at least one honest worker (and everyone else might be actively corrupted) the following holds 1) the privacy of the inputs is preserved 2) the output of the computation is correct (in particular workers cannot change the inputs of honest clients). We propose a solution where the clients' work is minimal and the interaction pattern simple (one message to upload inputs, one to receive results), while at the same time reducing the overhead for the workers to a minimum. Our solution is generic and can be instantiated with any underlying reactive MPC protocol where linear operations are ``for free''. In contrast previous solutions were less generic and could only be instantiated for specific numbers of clients/workers.

Oblivious RAMs (ORAMs) have traditionally been measured by their bandwidth overhead and client storage. We observe that when using ORAMs to build secure computation protocols for RAM programs, the size of the ORAM circuits is more relevant to the performance. We therefore embark on a study of the circuit-complexity of several recently proposed ORAM constructions. Our careful implementation and experiments show that asymptotic analysis is not indicative of the true performance of ORAM in secure computation protocols with practical data sizes. We then present SCORAM, a heuristic compact ORAM design optimized for secure computation protocols. Our new design is almost 10x smaller in circuit size and also faster than all other designs we have tested for realistic settings (i.e., memory sizes between 4MB and 2GB, constrained by 2-80 failure probability). SCORAM makes it feasible to perform secure computations on gigabyte-sized data sets.

For the past few years, research works on the topic of secure outsourcing of cryptographic computations has drawn significant attention from academics in security and cryptology disciplines as well as information security practitioners. One main reason for this interest is their application for resource constrained devices such as RFID tags. While there has been significant progress in this domain since Hohenberger and Lysyanskaya have provided formal security notions for secure computation delegation, there are some interesting challenges that need to be solved that can be useful towards a wider deployment of cryptographic protocols that enable secure outsourcing of cryptographic computations. This position paper brings out these challenging problems with RFID technology as the use case together with our ideas, where applicable, that can provide a direction towards solving the problems.

In recent years, the availability of GPS-enabled smartphones have made location-based services extremely popular. A multitude of applications rely on location information to provide a wide range of services. Location information is, however, extremely sensitive and can be easily abused. In this paper, we introduce the first protocols for secure computation of distance and for proximity testing over a sphere. Our secure distance protocols allow two parties, Alice and Bob, to determine their mutual distance without disclosing any additional information about their location. Through our secure proximity testing protocols, Alice only learns if Bob is in close proximity, i.e., within some arbitrary distance. An important difference between our protocols and existing techniques is that our protocols are the first not to require parties to privately negotiate a common map. Our protocols rely on three different representations of Earth, which provide different trade-offs between accuracy and performance. We show, via experiments on a prototype implementation, that our protocols are practical on resource-constrained smartphone devices. Our distance computation protocols runs in 54 to 78 ms on a commodity Android smartphone. Similarly, our proximity tests require between 1.2 s and 2.8 s on the same platform. The imprecision introduced by our protocols is very small, i.e., between 0.1% and 2% on average, depending on the distance.

Recent work demonstrates the feasibility and practical use of secure two-party computation [5, 9, 15, 23]. In this work, we present the first Graphical Processing Unit (GPU)-optimized implementation of an optimized Yao's garbled-circuit protocol for two-party secure computation in the honest-but-curious and 1-bit-leaked malicious models. We implement nearly all of the modern protocol advancements, such as Free-XOR, Pipelining, and OT extension. Our implementation is the first allowing entire circuits to be generated concurrently, and makes use of a modification of the XOR technique so that circuit generation is optimized for implementation on SIMD architectures of GPUs. In our best cases we generate about 75 million gates per second and we exceed the state of the art performance metrics on modern CPU systems by a factor of about 200, and GPU systems by about a factor of 2.3. While many recent works on garbled circuits exploit the embarrassingly parallel nature of many tasks that are part of a secure computation protocol, we show that there are still various forms and levels of parallelization that may yet improve the performance of these protocols. In particular, we highlight that implementations on the SIMD architecture of modern GPUs require significantly different approaches than the general purpose MIMD architecture of multi-core CPUs, which again differ from the needs of parallelizing on compute clusters. Additionally, modifications to the security models for many common protocols have large effects on reasonable parallel architectures for implementation.

The Portable Circuit Format (PCF) system presented by Kreuter et al.[kmsb13] addressed an important bottleneck in the tools developed by the research community for secure computation. The PCF system is based on the idea that circuits can be represented as programs that emit gates on certain state transitions. By dealing with programs rather than circuits, functions have much smaller representations, the PCF compiler is able to apply automatic optimizations to much larger functions, and the runtime system requires far less memory. We present our future plans for the PCF system and our current work-in-progress.

Secure computation has high computational resource requirements during run-time. Secure computation optimization can lower these requirements, but has high computational resource requirements during compile-time. This prevents automatic optimization of most larger secure computations. In this paper we present an efficient optimization algorithm that does no longer require the use of a theorem prover. For a secure computation with m statements of which n are branching statements we lower the complexity from O(2^(2^n) m) to O(m^5 2^n). Using an implementation of our algorithm we can extend automatic optimization to further examples such as the AES key schedule.

In this paper, we discuss the design choices and initial experiences with a domain-specific language and its optimizing compiler for specifying protocols for secure computation. We give the rationale of the design, describe the translation steps, the location of the compiler in the whole Sharemind protocol stack, and the results we have obtained with the system.

The problem of secure two-party computation has received great attention in the years that followed its introduction by Yao. The solutions proposed follow one of the two research directions of either using homomorphic encryption techniques or implementing Yao's "Garbled Circuit" solution. The latter requires circuits to implement a given functionality. Recently, the compiler CBMC-GC was introduced, the first compiler capable of translating programs written in a general purpose language (ANSI-C) into circuits suitable for secure two-party computation. In this paper, we discuss the current limitations of CBMC-GC and propose directions for future research.

In secure multi-party computation, mutually distrusting parties cooperatively compute functions of their private data; in the process, they only learn certain results as per the protocol (e.g., the final output). The realization of these protocols uses cryptographic techniques to avoid leaking information between the parties. A protocol for a secure computation can sometimes be optimized without changing its security guarantee: when the parties can use their private data and the revealed output to infer the values of other data, then this other data need not be concealed from them via cryptography.In the context of automatically optimizing secure multi-party computation, we define two related problems, knowledge inference and constructive knowledge inference. In both problems, we attempt to automatically discover when and if intermediate variables in a protocol will (eventually) be known to the parties involved in the computation. We formally state the two problems and describe our solutions. We show that our approach is sound, and further, we characterize its completeness properties. We present a preliminary experimental evaluation of our approach.

There are a number of domain-specific programming languages for secure computation. Out of those, the ones that are based on generic programming languages support mixing different protocol primitives and enable implementing a wider, possibly more efficient range of protocols. On the one hand, this may result in better protocol performance. On the other hand, this may lead to insecure protocols. In this paper we present a security type system that enables mixing protocol primitives in a generic programming language, but also ensures that well-typed programs are secure in the semi-honest model. Consequently, a compiled protocol must be secure. We show an extension of the L1 language with our security type system and evaluate the implementation of two protocols from the literature. This shows that our type system supports the provably secure implementation even of complex protocols.

Secure two-party computation is used as the basis for a large variety of privacy-preserving protocols, but often concerns about the low performance hinder the move away from non-private solutions.In this paper we present an improved implementation of Yao's garbled circuit protocol in the semi-honest adversaries setting which is up to 10 times faster than previous implementations. Our improvements include (1) the first multi-threaded implementation of the base oblivious transfers resulting in a speedup of a factor of two, (2) techniques for minimizing the memory footprint during oblivious transfer extensions and processing of circuits, (3) compilation of sub-circuits into files, and (4) caching of circuit descriptions and network packets. We implement improved circuit building blocks from the literature and present for the first time performance results for secure evaluation of the ultra-lightweight block cipher PRESENT within 7 ms online time.

Many secure data analysis tasks, such as secure clustering and classification, require efficient mechanisms to convert the intermediate encrypted integers into the corresponding encryptions of bits. The existing bit-decomposition algorithms either do not offer sufficient security or are computationally inefficient. In order to provide better security as well as to improve efficiency, we propose a novel probabilistic-based secure bit-decomposition protocol for values encrypted using public key additive homomorphic encryption schemes. The proposed protocol guarantees security as per the semi-honest security definition of secure multi-party computation (MPC) and is also very efficient compared to the existing method. Our protocol always returns the correct result, however, it is probabilistic in the sense that the correct result can be generated in the first run itself with very high probability. The computation time of the proposed protocol grows linearly with the input domain size in bits. We theoretically analyze the complexity of the proposed protocol with the existing method in detail.

In theory secure computation offers a solution for privacy in many collaborative applications. However, in practice poor efficiency of the protocols prevents their use. Hand-crafted protocols are more efficient than those implemented in compilers, but they require significantly more development effort in programming and verification. Recently, Kerschbaum introduced an automatic compiler optimization technique for secure computations that can make compilers as efficient as hand-crafted protocols. This optimization relies on the structure of the secure computation program. The programmer has to implement the program in such a way, such that the optimization can yield the optimal performance. In this paper we present an algorithm that rewrites the program -- most notably its expressions -- optimizing their efficiency in secure computation protocols. We give a heuristic for whole-program optimization and show the resulting performance gains using examples from the literature.

We present a novel framework for the description and analysis of secure computation protocols that is at the same time mathematically rigorous and notationally lightweight and concise. The distinguishing feature of the framework is that it allows to specify (and analyze) protocols in a manner that is largely independent of time, greatly simplifying the study of cryptographic protocols. At the notational level, protocols are described by systems of mathematical equations (over domains), and can be studied through simple algebraic manipulations like substitutions and variable elimination. We exemplify our framework by analyzing in detail two classic protocols: a protocol for secure broadcast, and a verifiable secret sharing protocol, the second of which illustrates the ability of our framework to deal with probabilistic systems, still in a purely equational way.

The practical application of Secure Two-Party Computation is hindered by the difficulty to implement secure computation protocols. While recent work has proposed very simple programming languages which can be used to specify secure computations, it is still difficult for practitioners to use them, and cumbersome to translate existing source code into this format. Similarly, the manual construction of two-party computation protocols, in particular ones based on the approach of garbled circuits, is labor intensive and error-prone.The central contribution of the current paper is a tool which achieves Secure Two-Party Computation for ANSI C. Our work is based on a combination of model checking techniques and two-party computation based on garbled circuits. Our key insight is a nonstandard use of the bit-precise model checker CBMC which enables us to translate C programs into equivalent Boolean circuits. To this end, we modify the standard CBMC translation from programs into Boolean formulas whose variables correspond to the memory bits manipulated by the program. As CBMC attempts to minimize the size of the formulas, the circuits obtained by our tool chain are also size efficient; to improve the efficiency of the garbled circuit evaluation, we perform optimizations on the circuits. Experimental results with the new tool CBMC-GC demonstrate the practical usefulness of our approach.

Traditional approaches to generic secure computation begin by representing the function f being computed as a circuit. If f depends on each of its input bits, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for non-trivial functions since each party must "touch" every bit of their input lest information about the other party's input be leaked. This seems to rule out many applications of secure computation (e.g., database search) in scenarios where inputs are huge.Adapting and extending an idea of Ostrovsky and Shoup, we present an approach to secure two-party computation that yields protocols running in sublinear time, in an amortized sense, for functions that can be computed in sublinear time on a random-access machine (RAM). Moreover, each party is required to maintain state that is only (essentially) linear in its own input size. Our approach combines generic secure two-party computation with oblivious RAM (ORAM) protocols. We present an optimized version of our approach using Yao's garbled-circuit protocol and a recent ORAM construction of Shi et al.We describe an implementation of our resulting protocol, and evaluate its performance for obliviously searching a database with over 1 million entries. Our implementation outperforms off-the-shelf secure-computation protocols for databases containing more than 218 entries.

On the one hand, compilers for secure computation protocols, such as FairPlay or FairPlayMP, have significantly simplified the development of such protocols. On the other hand, optimized protocols with high performance for special problems demand manual development and security verification. The question considered in this paper is: Can we construct a compiler that produces optimized protocols? We present an optimization technique based on logic inference about what is known from input and output. Using the example of median computation we can show that our program analysis and rewriting technique translates a FairPlay program into an equivalent -- in functionality and security -- program that corresponds to the protocol by Aggarwal et al. Nevertheless our technique is general and can be applied to optimize a wide variety of secure computation protocols.

Secure computation, e.g. using Yao's garbled circuit protocol, allows two parties to compute arbitrary functions without disclosing their inputs. A profitable application of secure computation is business optimization. It is characterized by a monetary benefit for all participants and a high confidentiality of their respective input data. In most instances the consequences of input disclosure, e.g. loss of bargaining power, outweigh the benefits of collaboration. Therefore these optimizations are currently not performed in industrial practice.Our demo shows such an optimization as a secure computation. The joint economic lot size (JELS) is the optimal order quantity between a buyer and supplier. We implemented Yao's protocol in JavaScript, such that it can be executed using two web browsers. This has the additional benefit that the software can be offered as a service (SaaS) and can be easily integrated with other SaaS offerings, e.g. using mash-up technology.

We consider the classical problem of synchronous broadcast with dishonest majority, when a public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting.We argue that the communication model adopted by Hirt and Zikas is unrealistically pessimistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary number of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework.We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine.

Although cryptographic algorithms are designed to resist at least thousands of years of cryptoanalysis, implementing them with either software or hardware usually leaks additional information which may enable the attackers to break the cryptographic systems within days. A Side Channel Attack (SCA) is such a kind of attack that breaks a security system at a low cost within a short time. SCA uses side-channel leakage, such as the cryptographic implementations' execution time, power dissipation and magnetic radiation. This paper presents a countermeasure to protect software-based cryptography from SCA by emulating the behavior of the secure hardware circuits. The emulation is done by introducing two simple complementary instructions to the processor and applying a secure programming style. We call the resulting secure software program a Virtual Secure Circuit (VSC). VSC inherits the idea of a secure logic circuit, a hardware SCA countermeasure. It not only maintains the secure circuits' generality without limitation to a specific algorithm, but also increases its flexibility. Experiments on a prototype implementation demonstrated that the new countermeasure considerably increases the difficulty of the attacks by 20 times, which is in the same order as the improvement achieved by the dedicated secure hardware circuits. Therefore, we conclude that VSC is an efficient way to protect cryptographic software.