Paper 2018/077

On the Bit Security of Cryptographic Primitives

Daniele Micciancio and Michael Walter


We introduce a formal quantitative notion of ``bit security'' for a general type of cryptographic games (capturing both decision and search problems), aimed at capturing the intuition that a cryptographic primitive with $k$-bit security is as hard to break as an ideal cryptographic function requiring a brute force attack on a $k$-bit key space. Our new definition matches the notion of bit security commonly used by cryptographers and cryptanalysts when studying search (e.g., key recovery) problems, where the use of the traditional definition is well established. However, it produces a quantitatively different metric in the case of decision (indistinguishability) problems, where the use of (a straightforward generalization of) the traditional definition is more problematic and leads to a number of paradoxical situations or mismatches between theoretical/provable security and practical/common sense intuition. Key to our new definition is to consider adversaries that may explicitly declare failure of the attack. We support and justify the new definition by proving a number of technical results, including tight reductions between several standard cryptographic problems, a new hybrid theorem that preserves bit security, and an application to the security analysis of indistinguishability primitives making use of (approximate) floating point numbers. This is the first result showing that (standard precision) 53-bit floating point numbers can be used to achieve 100-bit security in the context of cryptographic primitives with general indistinguishability-based security definitions. Previous results of this type applied only to search problems, or special types of decision problems.

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2018
Bit SecurityInformation TheoryIndistinguishability
Contact author(s)
michael walter @ ist ac at
2019-05-27: last of 4 revisions
2018-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniele Micciancio and Michael Walter},
      title = {On the Bit Security of Cryptographic Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2018/077},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.