Dartmouth College Computer Science Technical Report series CS home TR home TR search TR listserv By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z By number: 2020, 2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties
Alexander Iliev, Sean Smith
Dartmouth TR2005-551

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.

PDF (707KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
Alexander Iliev and Sean Smith, "More Efficient Secure Function Evaluation Using Tiny Trusted Third Parties." Dartmouth Computer Science Technical Report TR2005-551, July 2005.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.