Cryptology ePrint Archive: Report 2005/211

Games and the Impossibility of Realizable Ideal Functionality

Anupam Datta and Ante Derek and John C. Mitchell and Ajith Ramanathan and Andre Scedrov

Abstract: A cryptographic primitive or a security mechanism can be specified in a variety of ways, such as a condition involving a game against an attacker, construction of an ideal functionality, or a list of properties that must hold in the face of attack. While game conditions are widely used, an ideal functionality is appealing because a mechanism that is indistinguishable from an ideal functionality is therefore guaranteed secure in any larger system that uses it. We relate ideal functionalities to games by defining the \textit{set} of ideal functionalities associated with a game condition and show that under this definition, which reflects accepted use and known examples, bit commitment, a form of group signatures, and some other cryptographic concepts do not have any realizable ideal functionality.

Category / Keywords: foundations / universaly composability, bit commitment, group signatures, symmetric encryption

Publication Info: Third Theory of Cryptography Conference, TCC 2006, Proceedings

Date: received 5 Jul 2005, last revised 9 Mar 2006

Contact author: aderek at cs stanford edu

Available formats: PDF | BibTeX Citation

Version: 20060310:043551 (All versions of this report)

Discussion forum: Show discussion | Start new discussion