Alex Iliev's thesis (PDF).
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.
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
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.
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.
Maintained by Alex Iliev
Last modified: May 25, 2015