On the bit security of cryptographic primitives

Micciancio D, Walter M. 2018. On the bit security of cryptographic primitives. Eurocrypt: Advances in Cryptology, LNCS, vol. 10820, 3–28.

Download (ext.)
OA https://eprint.iacr.org/2018/077 [Submitted Version]

Conference Paper | Published | English

Scopus indexed
Author
Micciancio, Daniele; Walter, MichaelISTA

Corresponding author has ISTA affiliation

Department
Series Title
LNCS
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.
Publishing Year
Date Published
2018-03-31
Publisher
Springer
Acknowledgement
Research supported in part by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under the SafeWare program. Opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views, position or policy of the Government. The second author was also supported by the European Research Council, ERC consolidator grant (682815 - TOCNeT).
Volume
10820
Page
3 - 28
Conference
Eurocrypt: Advances in Cryptology
Conference Location
Tel Aviv, Israel
Conference Date
2018-04-29 – 2018-05-03
IST-REx-ID
300

Cite this

Micciancio D, Walter M. On the bit security of cryptographic primitives. In: Vol 10820. Springer; 2018:3-28. doi:10.1007/978-3-319-78381-9_1
Micciancio, D., & Walter, M. (2018). On the bit security of cryptographic primitives (Vol. 10820, pp. 3–28). Presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78381-9_1
Micciancio, Daniele, and Michael Walter. “On the Bit Security of Cryptographic Primitives,” 10820:3–28. Springer, 2018. https://doi.org/10.1007/978-3-319-78381-9_1.
D. Micciancio and M. Walter, “On the bit security of cryptographic primitives,” presented at the Eurocrypt: Advances in Cryptology, Tel Aviv, Israel, 2018, vol. 10820, pp. 3–28.
Micciancio D, Walter M. 2018. On the bit security of cryptographic primitives. Eurocrypt: Advances in Cryptology, LNCS, vol. 10820, 3–28.
Micciancio, Daniele, and Michael Walter. On the Bit Security of Cryptographic Primitives. Vol. 10820, Springer, 2018, pp. 3–28, doi:10.1007/978-3-319-78381-9_1.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Web of Science

View record in Web of Science®

Search this title in

Google Scholar