More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties

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\u27s 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\u27s 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\u27s strength in handling indirectly-addressed arrays