However, all known protocols employing tamper-proof hardware are either indirect, i.e. additional computational assumptions must be used to obtain general two party computations, or a large number of devices must be used. Unfortunately, issuing multiple independent tamper-proof devices requires much stronger isolation assumptions. This work is the extended version of a recent result of the same authors, where for the first time a protocol was presented that realizes universally composable two party computations (and even one-time programs) with information-theoretic security using only a single tamper-proof device issued by one of the mutually distrusting parties. Now, we present the first protocols for multiple one-time memories (OTMs), and reusable and bidirectional commitment and oblivious transfer (OT) primitives in this setting. All these constructions have only linear communication complexity and are thus asymptotically optimal. Moreover, the computation complexity of our protocols for k-bit OTMs/commitments/OT is dominated by O(1) finite field multiplications with field size 2^k, what is considerably more efficient than any other known construction based on untrusted tamper-proof hardware alone.
The central part of our contribution is a construction for oblivious affine function evaluation (OAFE), which can be seen as a generalization of the well known oblivious transfer primitive: Parametrized by a finite vector space F_q^k, the OAFE primitive allows a designated sender party to choose an arbitrary affine function f:F_q -> F_q^k, such that hidden from the sender party a designated receiver party may learn f(x) for exactly one function argument x of its choice. All our abovementioned results build on this primitive and it may also be of particular interest for the construction of garbled arithmetic circuits.
Category / Keywords: cryptographic protocols / non-interactive secure computation, universal composability, tamper-proof hardware, information-theoretic security, oblivious transfer Publication Info: accepted for oral presentation at ICITS 2012 workshop track Date: received 12 Mar 2012, last revised 26 Apr 2013 Contact author: kraschewski at kit edu Available format(s): PDF | BibTeX Citation Version: 20130426:081758 (All versions of this report) Short URL: ia.cr/2012/135 Discussion forum: Show discussion | Start new discussion