All complete functionalities are reversible

Dakshita Khurana; Daniel Kraschewski; Hemanta K. Maji; Manoj M Prabhakaran; Amit Sahai

doi:10.1007/978-3-662-49896-5_8

All complete functionalities are reversible

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Crépeau 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.

Original language	English (US)
Title of host publication	Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Marc Fischlin, Jean-Sebastien Coron
Publisher	Springer
Pages	213-242
Number of pages	30
ISBN (Print)	9783662498958
DOIs	https://doi.org/10.1007/978-3-662-49896-5_8
State	Published - 2016
Event	35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016 - Vienna, Austria Duration: May 8 2016 → May 12 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9666
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
Country/Territory	Austria
City	Vienna
Period	5/8/16 → 5/12/16

Keywords

Fixed-role reduction
Information-theoretic security
Reversibility of functionalities
Secure function evaluation
UC-security

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-662-49896-5_8

Library availability

Discover UIUC Full Text

Cite this

Khurana, D., Kraschewski, D., Maji, H. K., Prabhakaran, M. M., & Sahai, A. (2016). All complete functionalities are reversible. In M. Fischlin, & J.-S. Coron (Eds.), Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 213-242). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9666). Springer. https://doi.org/10.1007/978-3-662-49896-5_8

All complete functionalities are reversible. / Khurana, Dakshita; Kraschewski, Daniel; Maji, Hemanta K. et al.
Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Marc Fischlin; Jean-Sebastien Coron. Springer, 2016. p. 213-242 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9666).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Khurana, D, Kraschewski, D, Maji, HK, Prabhakaran, MM & Sahai, A 2016, All complete functionalities are reversible. in M Fischlin & J-S Coron (eds), Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9666, Springer, pp. 213-242, 35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016, Vienna, Austria, 5/8/16. https://doi.org/10.1007/978-3-662-49896-5_8

Khurana D, Kraschewski D, Maji HK, Prabhakaran MM, Sahai A. All complete functionalities are reversible. In Fischlin M, Coron JS, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer. 2016. p. 213-242. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-49896-5_8

Khurana, Dakshita ; Kraschewski, Daniel ; Maji, Hemanta K. et al. / All complete functionalities are reversible. Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Marc Fischlin ; Jean-Sebastien Coron. Springer, 2016. pp. 213-242 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{23b7fcfbc9ab4213b8a956fff8155dd6,

title = "All complete functionalities are reversible",

abstract = "Cr{\'e}peau 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.",

keywords = "Fixed-role reduction, Information-theoretic security, Reversibility of functionalities, Secure function evaluation, UC-security",

author = "Dakshita Khurana and Daniel Kraschewski and Maji, {Hemanta K.} and Prabhakaran, {Manoj M} and Amit Sahai",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2016.; 35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016 ; Conference date: 08-05-2016 Through 12-05-2016",

year = "2016",

doi = "10.1007/978-3-662-49896-5_8",

language = "English (US)",

isbn = "9783662498958",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "213--242",

editor = "Marc Fischlin and Jean-Sebastien Coron",

booktitle = "Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "Germany",

}

TY - GEN

T1 - All complete functionalities are reversible

AU - Khurana, Dakshita

AU - Kraschewski, Daniel

AU - Maji, Hemanta K.

AU - Prabhakaran, Manoj M

AU - Sahai, Amit

N1 - Publisher Copyright: © International Association for Cryptologic Research 2016.

PY - 2016

Y1 - 2016

N2 - Crépeau 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.

AB - Crépeau 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.

KW - Fixed-role reduction

KW - Information-theoretic security

KW - Reversibility of functionalities

KW - Secure function evaluation

KW - UC-security

UR - http://www.scopus.com/inward/record.url?scp=84964964196&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84964964196&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-49896-5_8

DO - 10.1007/978-3-662-49896-5_8

M3 - Conference contribution

AN - SCOPUS:84964964196

SN - 9783662498958

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 213

EP - 242

BT - Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Fischlin, Marc

A2 - Coron, Jean-Sebastien

PB - Springer

T2 - 35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016

Y2 - 8 May 2016 through 12 May 2016

ER -

All complete functionalities are reversible

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this