Cryptology ePrint Archive: Report 2012/135

David & Goliath Oblivious Affine Function Evaluation - Asymptotically Optimal Building Blocks for Universally Composable Two-Party Computation from a Single Untrusted Stateful Tamper-Proof Hardware Token

Nico Döttling and Daniel Kraschewski and Jörn Müller-Quade

Abstract: In a seminal work, Katz (Eurocrypt 2007) showed that parties being able to issue tamper-proof hardware can implement universally composable secure computation without a trusted setup. Our contribution to the line of research initiated by Katz is a construction for general, information-theoretically secure, universally composable two-party computation based on a single stateful tamper-proof token. We provide protocols for multiple one-time memories, multiple commitments in both directions, and also bidirectional oblivious transfer. From this, general secure two-party computation (and even one-time programs) can be implemented by known techniques. Moreover, our protocols have asymptotically optimal communication complexity.

The central part of our work is a construction for oblivious affine function evaluation (OAFE), which can be seen as a generalization of the oblivious transfer primitive: Parametrized by a finite field F and a dimension k, the OAFE primitive allows a designated sender to choose an affine function f:F->F^k, such that hidden from the sender a designated receiver can learn f(x) for exactly one input x in F of his choice. All our abovementioned results build upon 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 23 Nov 2018

Contact author: kraschew at ira uka de

Available format(s): PDF | BibTeX Citation

Note: overdue polishing and minor corrections

Version: 20181123:180802 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]