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; Daniel Kraschewski; Jörn Müller-Quade

Paper 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, 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.

Note: overdue polishing and minor corrections

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. accepted for oral presentation at ICITS 2012 workshop track
Keywords: non-interactive secure computation universal composability tamper-proof hardware information-theoretic security oblivious transfer
Contact author(s): kraschew @ ira uka de
History: 2018-11-23: last of 3 revisions; 2012-03-22: received; See all versions
Short URL: https://ia.cr/2012/135
License: CC BY

BibTeX

@misc{cryptoeprint:2012/135,
      author = {Nico Döttling and Daniel Kraschewski and Jörn Müller-Quade},
      title = {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},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/135},
      year = {2012},
      url = {https://eprint.iacr.org/2012/135}
}