On the Bit Security of Cryptographic Primitives

被引:23
|
作者
Micciancio, Daniele [1 ]
Walter, Michael [2 ]
机构
[1] Univ Calif San Diego, San Diego, CA USA
[2] IST Austria, Klosterneuburg, Austria
来源
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2018, PT I | 2018年 / 10820卷
关键词
D O I
10.1007/978-3-319-78381-9_1
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:3 / 28
页数:26
相关论文
共 50 条
  • [21] Implementation and characterization of flash-based hardware security primitives for cryptographic key generation
    Oh, Mi-Kyung
    Lee, Sangjae
    Kang, Yousung
    Choi, Dooho
    ETRI JOURNAL, 2023, 45 (02) : 346 - 357
  • [22] Optimize cryptographic symmetric primitives performance
    Institute of Software, School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China
    不详
    Beijing Daxue Xuebao Ziran Kexue Ban, 2008, 5 (733-738):
  • [23] New cryptographic primitives (plenary lecture)
    Knapskog, Svein Johan
    SEVENTH INTERNATIONAL CONFERENCE ON COMPUTER INFORMATION SYSTEMS AND INDUSTRIAL MANAGEMENT APPLICATIONS, PROCEEDINGS, 2008, : 3 - 7
  • [24] Notions of reducibility between cryptographic primitives
    Reingold, O
    Trevisan, L
    Vadhan, S
    THEORY OF CRYPTOGRAPHY, PROCEEDINGS, 2004, 2951 : 1 - 20
  • [25] A Calculus for Concurrent Processes with Cryptographic Primitives
    Wang, Huanbao
    APPLIED SCIENCE, MATERIALS SCIENCE AND INFORMATION TECHNOLOGIES IN INDUSTRY, 2014, 513-517 : 3397 - 3400
  • [26] DUALITY BETWEEN 2 CRYPTOGRAPHIC PRIMITIVES
    ZHENG, Y
    MATSUMOTO, T
    IMAI, H
    LECTURE NOTES IN COMPUTER SCIENCE, 1991, 508 : 379 - 390
  • [27] Energy-Efficient Cryptographic Primitives
    Miller, D. Michael
    Sasao, Tsutomu
    FACTA UNIVERSITATIS-SERIES ELECTRONICS AND ENERGETICS, 2018, 31 (02) : I - III
  • [28] Implementing Cryptographic Primitives in the Symbolic Model
    Laud, Peeter
    NASA FORMAL METHODS, 2011, 6617 : 267 - 281
  • [29] Improving security in Image Steganography using MSB Bit differencing and Cryptographic algorithm
    Shrilekha
    Reddy, N. V. Subba
    PROCEEDINGS OF THE 2018 INTERNATIONAL CONFERENCE ON COMPUTATIONAL TECHNIQUES, ELECTRONICS AND MECHANICAL SYSTEMS (CTEMS), 2018, : 228 - 230
  • [30] The sponge construction as a source of secure cryptographic primitives
    Borowski, Mariusz
    2013 MILITARY COMMUNICATIONS AND INFORMATION SYSTEMS CONFERENCE (MCC), 2013,