Publications

Ph.D. Thesis

Alex Iliev's thesis (PDF).

Abstract

The theory community has worked on Secure Multiparty Computation (SMC) for more than two decades, and has produced many protocols for many settings. One common thread in these works is that the protocols cannot use a Trusted Third Party (TTP), even though this is conceptually the simplest and most general solution. Thus, current protocols involve only the direct players---we call such protocols self-reliant. They often use blinded boolean circuits, which has several sources of overhead, some due to the circuit representation and some due to the blinding.

However, secure coprocessors like the IBM 4758 have actual security properties similar to ideal TTPs. They also have little RAM and a slow CPU. We call such devices Tiny TTPs. The availability of real tiny TTPs opens the door for a different approach to SMC problems. One major challenge with this approach is how to execute large programs on large inputs using the small protected memory of a tiny TTP, while preserving the trust properties that an ideal TTP provides. In this thesis we have investigated the use of real TTPs to help with the solution of SMC problems.

We start with the use of such TTPs to solve the Private Information Retrieval (PIR) problem, which is one important instance of SMC. Our implementation utilizes a 4758.

The rest of the thesis is targeted at general SMC. Our SMC system, Faerieplay, moves some functionality into a tiny TTP, and thus avoids the blinded circuit overhead.

Faerieplay consists of a compiler from high-level code to an arithmetic circuit with special gates for efficient indirect array access, and a virtual machine to execute this circuit on a tiny TTP while maintaining the typical SMC trust properties. We report on Faerieplay's security properties, the specification of its components, and our implementation and experiments. These include comparisons with the Fairplay circuit-based two-party system, and an implementation of the Dijkstra graph shortest path algorithm. We also provide an implementation of an oblivious RAM which supports similar tiny TTP-based SMC functionality but using a standard RAM program. Performance comparisons show Faerieplay's circuit approach to be considerably faster, at the expense of a more constrained programming environment when targeting a circuit.

Workshop Paper

Faerieplay on Tiny Trusted Third Parties. We present our work to overcome barriers to the deployment of Secure Multiparty Computation assisted by a Trusted Third Party (TTP) in the form of hardware-based trustworthy devices, like the IBM 4758 secure coprocessor. We focus on the effective use of tiny TTPs ( T3Ps). To eliminate the difficulty of programming a small secure device while preserving critical trust properties, in concurrent work we designed and prototyped an efficient system, called Faerieplay, to execute arbitrary programs on T3Ps securely. To eliminate the performance and cost obstacles of using secure coprocessors, we are currently examining the potential hardware design for a T3P optimized for bottleneck operations. We estimate that such a T3P could outperform the 4758 by several orders of magnitude, while also having a gate-count of only 30K-60K, one to three orders of magnitude smaller than the 4758 or hardened CPU systems like AEGIS. We are currently proceeding with a proof-of-concept prototype on a Xilinx FPGA.

Technical Reports

Towards Tiny Trusted Third Parties. Here we outline our hardware design for a tiny TTP, which is optimized for operations like emulating a re-encrypting sorting network. These operations dominate the running time of Oblivious RAM and Practical PIR algorithms. More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties. Here we describe our circuit-based Secure Multiparty Computation (SMC) system, which uses tiny TTPs, and improves efficiency with indirect arrays. Indirect arrays are a major weakness with exisiting non-TTP protocols.

Software

Maintained by Alex Iliev

Last modified: May 25, 2015