---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Daniele
foaf_name: Micciancio, Daniele
foaf_surname: Micciancio
- foaf_Person:
foaf_givenName: Michael
foaf_name: Walter, Michael
foaf_surname: Walter
foaf_workInfoHomepage: http://www.librecat.org/personId=488F98B0-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1007/978-3-319-78381-9_1
bibo_volume: 10820
dct_date: 2018^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: On the bit security of cryptographic primitives@
...