@TechReport{Dartmouth:TR2005-551,
author = {Alexander Iliev and Sean Smith},
title = {{More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties}},
institution = {Dartmouth College, Computer Science},
address = {Hanover, NH},
number = {TR2005-551},
year = {2005},
month = {July},
URL = {http://www.cs.dartmouth.edu/reports/TR2005-551.pdf},
abstract = {
We investigate the use of trustworthy devices, which function as
trusted third parties (TTPs), to solve general two-party Secure
Function Evaluation (SFE) problems. We assume that a really
trustworthy TTP device will have very limited protected memory and
computation environment---a \emph{tiny TTP}. This precludes trivial
solutions like "just run the function in the TTP".
Traditional scrambled circuit evaluation approaches to SFE have a very
high overhead in using indirectly-addressed arrays---every array
access's cost is linear in the array size. The main gain in our
approach is that array access can be provided with much smaller
overhead---$O(\sqrt{N}\log N)$. This expands the horizon of problems
which can be efficiently solved using SFE. Additionally, our technique
provides a simple way to deploy arbitrary programs on tiny TTPs.
In our prototype, we use a larger (and expensive) device, the IBM 4758
secure coprocessor, but we also speculate on the design of future tiny
devices that could greatly improve the current prototype's efficiency
by being optimized for the operations prevalent in our algorithms.
We have prototyped a compiler for the secure function definition
language (SFDL) developed in the Fairplay project. Our compiler
produces an arithmetic circuit, augmented with \emph{array access
gates} which provide more efficient secure access to arrays. We then
have a circuit interpreter in the 4758 to evaluate such a circuit on
given inputs. It does this gate by gate, requiring very little
protected space. We report on the performance of this prototype, which
confirms our approach's strength in handling indirectly-addressed
arrays.
}
}