Paper 2005/211

Games and the Impossibility of Realizable Ideal Functionality

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


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.

Available format(s)
Publication info
Published elsewhere. Third Theory of Cryptography Conference, TCC 2006, Proceedings
universaly composabilitybit commitmentgroup signaturessymmetric encryption
Contact author(s)
aderek @ cs stanford edu
2006-03-10: revised
2005-07-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anupam Datta and Ante Derek and John C.  Mitchell and Ajith Ramanathan and Andre Scedrov},
      title = {Games and the Impossibility of Realizable Ideal Functionality},
      howpublished = {Cryptology ePrint Archive, Paper 2005/211},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.