Browsing by Author "Mohassel, Payman"

Now showing 1 - 8 of 8
  • Thumbnail Image
    ItemOpen Access
    Design and Implementation of Maliciously Secure Two-Party Computation Based on Garbled Circuits
    (2017) Afshar, Arash; Mohassel, Payman; Safavi-Naini, Reyhaneh Alsadat; Barker, Kenneth Edwin; Jacobson, Michael John Jr; Sanders, Barry Cyril; Kerschbaum, Florian
    In this thesis we design and implement three approaches to provide efficient Secure Two- Party Computation (2PC) protocols that are secure in presence of malicious adversaries. The field of secure two-party computation enables two mutually distrusting parties, each with their own private input, to run a computation of an arbitrary program. At the end of the computation, nothing about their private input is leaked except for what can be learned from the output of the computation. The seminal work of Yao in 1986 provided the first proof that such a computation is feasible using the so called garbled circuits and given an Oblivious Transfer protocol. In this thesis, we follow Yao’s garbled circuit approach and focus on efficient protocols that are secure against malicious adversaries. We examine three different categories of optimization. In each category, we present a 2PC protocol, prove its security, and implement it as a proof of concept to demonstrate its running time in practice. Non-interactive Secure Computation: In this category, we offer the first implementation of a malicious 2PC protocol that reduces the required rounds of interaction between the two parties to only two rounds (i.e., each party sends only one message to the other party). Mixed Secure Two-Party Computation: In the second category we target big and complex programs and break them into subprograms. Then, we compute each subprogram using the most efficient 2PC protocol that is suitable for it. Finally, we securely connect these subprograms together. The goal is to reduce the overhead of the garbled circuits significantly, which results in a more efficient overall 2PC protocol for programs with specific properties. Secure Computation for Random Access Machine Programs: In the third category, we target programs that require random access to the memory (as opposed to a sequential access). We present the first efficient maliciously-secure protocol for computing such programs.
  • Thumbnail Image
    ItemOpen Access
    Efficient Non-Interactive Secure Two-Party Computation for Equality and Comparison
    (2015-05-22) Karimian Ardestani, Negin; Mohassel, Payman
    Multi-party computation is receiving more and more attention as its application in more areas prove promising. In this research, our focus is on secure two-party computation. In particular, we propose non-interactive constructions for securely computing private equality testing and greater-than testing protocols. Our first construction is a private equality testing (PET) protocol. What distinguishes our construction from the state of the art is that it is single-round and secure against malicious adversaries. Our second construction is a private greater-than testing (PGT) protocol (i.e. the Yao's Millionaires problem) which is also single-round but only secure in the semi-honest model. Our protocols are based on the Peikert-Vaikuntanathan-Waters maliciously secure oblivious transfer and a collision resistant hash function. We formally prove that the PET protocol and the PGT protocol provide computational security. In this research, we developed our protocol for PET and run experiments to test it. The results provide evidence of efficiency of our protocol.
  • Thumbnail Image
    ItemOpen Access
    Efficient Shared Memory Algorithms for Bounding Space
    (2018-04-26) Aghazadeh, Zahra; Woelfel, Philipp; Higham, Lisa; Raynal, Michel; Yanushkevich, Svetlana; Mohassel, Payman; Li, Zongpeng
    It is the state of the art that computer systems use multi-core architectures. In order to exploit the benefits of parallelism, multiple processors have to cooperate and concurrently communicate by executing operations on shared objects. It is challenging in shared memory algorithms to deal with the inherent asynchrony of processes. To overcome this difficulty and to achieve high efficiency, algorithm designers often assume unbounded space. This work focuses on designing time-efficient shared memory algorithms while avoiding unbounded space. One example is that of making shared objects writable: Many standard primitives (for instance, compare-and-swap or fetch-and-add) do not provide a Write() operation that unconditionally changes the object's state to the one provided as a parameter. Adding Write() operations without sacrificing efficiency is challenging if space is limited. We provide a space-efficient solution for making synchronization primitives writable with optimal step complexity. A special case of making an object writable is to augment non-resettable objects with Reset() operations. We show how our general transformation can be improved to achieve optimal space implementations of long-lived test-and-set objects with time-efficient Reset() operations. Another example concerns the ABA problem: Even though a process retrieves the same value twice in a row from a shared object, it is still possible that the value of the object has changed multiple times. We investigate the time and space complexity of detecting ABAs in shared memory algorithms for systems with bounded base objects. To that end, we propose a new primitive called an ABA-detecting register, and we give an efficient implementation of this type using asymptotically optimal number of bounded registers. Finally we deal with a more general unbounded space problem: Many applications employ the tagging technique, where shared objects get augmented with additional values, called tags. Unbounded tags are mainly used in those applications, because bounding them is too complicated and error prone. We introduce a new primitive that provides an abstraction for avoiding unbounded tags. Also, we propose optimally time-efficient implementations of this primitive from bounded objects. In addition to straightforward applications that use tags directly, our implementations can also often be used for memory reclamation.
  • Thumbnail Image
    ItemOpen Access
    Fast Computation on Encrypted Polynomials and Applications
    (2010) Mohassel, Payman
    In this paper we design fast algorithms for computing on encrypted polynomials. More specifically, we design efficient algorithms for encrypted FFT, polynomial multiplication, division, and multipoint evaluation. The encryption scheme we need only has to be additively homomorphic. The above set of algorithms are useful building blocks for many applications in secure computation. We explore a few of them in this paper. First, we use the new algorithms to design a protocol for batch oblivious polynomial evaluation (OPE). Batch OPE can be seen as a generalization of k-out-n oblivious transfer and batch private keyword search. The computational complexity of our protocol is nearly linear in the degree of the polynomial and does not grow with the number of points evaluated at the polynomial. Second, we design two different protocols for the private set intersection problem both of which roughly require linear computation and communication. One is based on the batch OPE protocol we design, and the other is an adaptation of the ideas of [Kissner and Song, CRYPTO 2005] using the more efficient encrypted polynomial multiplication we introduce in this paper. While we mostly focus on security against semi-honest adversaries, our algorithmic ideas, in essence, yield nearly linear size arithmetic circuits for the set intersection and the batch OPE problems. Implementing these circuits via the new and efficient compiler of [Damgard and Orlandi, CRYPTO 2010] leads to protocols with linear complexity for the private set intersection and batch OPE with security against malicious adversaries based on standard and general assumptions.
  • Thumbnail Image
    ItemOpen Access
    Highly Efficient Commodity-based Two-Party Computation for Smartphones
    (2015-05-06) Orobets, Ostap; Mohassel, Payman
    Secure Two-Party Computation (2PC) enables a set of parties to compute a function of their inputs while keeping these inputs private. While theoretical solutions for solving 2PC problems were known for decades, efficient implementations have been developed only recently. The delay in implementation was caused by a number of factors, including a substantial performance overhead and limitations of the standard implementation techniques. These difficulties are compounded in mobile devices, which have even additional restrictions on memory, computational power, and bandwidth. There exist low-cost general-purpose protocols for semi-honest parties that can be executed efficiently even on smartphones. However, for the malicious case current protocols are much less efficient. This thesis introduces the first protocol for mobile phones that is secure in the presence of malicious players and a semi-honest, non-colluding server. The protocol takes advantage of a commodity-based setting, where one or multiple servers provide participants with computational material that makes 2PC efficient. Our protocol has two phases: In an offline phase - where no party knows which function is to be computed nor who else is participating - each party interacts with the server and downloads a file. Later, in the online phase, when two parties decide to execute a 2PC together, they can use the files they have downloaded earlier to execute the computation at low cost. We implement our protocol on Android smartphones and desktops and experimentally show that our mobile solution is more efficient than most of the semi-honest mobile applications in this field. The online phase for evaluating a single AES circuit requires only 2.5 seconds and can be further reduced to 1.2 seconds (amortized time) with multiple executions.
  • Thumbnail Image
    ItemOpen Access
    Learning decision trees through black-box queris
    (2011) Barati, Masoud; Safavi-Naeini, Reyhaneh; Mohassel, Payman
  • Thumbnail Image
    ItemOpen Access
    New Techniques for Private Function Evaluation
    (2015-12-04) Sadeghian, SeyedSaeed; Mohassel, Payman; Safavi-Naini, Reyhaneh Alsadat; Høyer, Peter; Woelfel, Philipp; Scheidler, Renate; Butler, Kevin
    In this thesis, we study the problem of general-purpose private function evaluation (PFE) wherein a single party P1 holds a circuit C, while each Pi for 1<=i<=m holds a private input xi, and the goal is for a subset (or all) of the parties to learn C(x1,…,xm) but nothing else. We pursue the design of PFE with better concrete and/or asymptotic complexity for a variety of settings. We put forth a general framework for designing PFE as the first alternative general approach to universal circuits. In this framework, the task of hiding the circuit topology and securely evaluating its gates are addressed independently through two functionalities we call CTH (Circuit Topology Hiding) and PGE (Private Gate Evaluation). We instantiate our framework using the building blocks of several well-known general MPC constructions, obtaining more efficient PFE than prior work for two-party PFE, multi-party PFE and PFE for arithmetic circuits. Next, we propose the first general framework for designing actively secure PFE, not based on universal circuits. On the theoretical side, our framework yields the first actively secure PFE with linear complexity in the circuit size. On the practical side, we obtain the first actively secure PFE for arithmetic circuits with O(glogg) complexity where g is the circuit size, significantly improving over previous constructions with complexity O(g^5). Despite its inefficiency, we identify various advantages for PFE based on universal circuits. Valiant's construction (STOC 1976) yields universal circuits with the optimal asymptotic complexity, and has been employed in several recent works. But somewhat surprisingly, no implementations of the construction exist. We look back at this construction, and provide a more approachable description. This enables us to provide constant factor improvements and the first implementation. A more accurate comparison made possible through our implementation shows that the improved Valiant's UC performs better than the theoretical estimate, and in fact is almost always smaller than the UC construction of Kolesnikov and Schneider (FC 2008). We also observe, for the first time, that the same construction can be adapted to yield size-optimized universal arithmetic circuits (UAC).
  • Thumbnail Image
    ItemOpen Access
    Oblivious Decision Programs from Oblivious Transfer: Efficient Reductions
    (2011-09-16T00:32:43Z) Mohassel, Payman; Niksefat, Salman
    In this paper, we design efficient protocols for a number of \emph{private database query} problems. Consider a general form of the problem where a client who holds a private input interacts with a server who holds a private decision program (e.g. a decision tree or a branching program) with the goal of evaluating his input on the decision program without learning any additional information. Many known private database queries such as Symmetric PIR, and Private Keyword Search can be formulated as special cases of this problem. We design \emph{computationally efficient} protocols for the above general problem, and a few of its special cases. In addition to being one-round and requiring a small amount of work by the client (in the RAM model), our protocols only require a small number of exponentiations (independent of the server's input) by both parties. Our constructions are, in essence, efficient and black-box reductions of the above problem to $1$-out-of-$2$ oblivious transfer. We prove our protocols secure (private) against \emph{malicious} adversaries in the standard ideal/real world simulation-based paradigm. The majority of the existing work on the same problems focus on optimizing communication. However, in some environments (supported by a few experimental studies), it is the computation and not the communication that may be the performance bottleneck. Our protocols are suitable alternatives for such scenarios.