Paper 2016/496

All Complete Functionalities are Reversible

Daniel Kraschewski, Dakshita Khurana, Hemanta K. Maji, Manoj Prabhakaran, and Amit Sahai

Abstract

Crepeau and Santha, in 1991, posed the question of reversibility of functionalities, that is, which functionalities when used in one direction, could securely implement the identical functionality in the reverse direction. Wolf and Wullschleger, in 2006, showed that oblivious transfer is reversible. We study the problem of reversibility among 2-party SFE functionalities, which also enable general multi-party computation, in the information-theoretic setting. We show that any functionality that enables general multi-party computation, when used in both directions, is reversible. In fact, we show that any such functionality can securely realize oblivious transfer when used in an a priori fixed direction. This result enables secure computation using physical setups that parties can only use in a particular direction due to inherent asymmetries in them.

Note: This is the full version of the original publication.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2016
Keywords
completenessreversibilitysecure computation
Contact author(s)
dakshita @ cs ucla edu
History
2016-05-22: received
Short URL
https://ia.cr/2016/496
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/496,
      author = {Daniel Kraschewski and Dakshita Khurana and Hemanta K.  Maji and Manoj Prabhakaran and Amit Sahai},
      title = {All Complete Functionalities are Reversible},
      howpublished = {Cryptology ePrint Archive, Paper 2016/496},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/496}},
      url = {https://eprint.iacr.org/2016/496}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.