Paper 2022/693

Unified View for Notions of Bit Security

Shun Watanabe, Tokyo University of Agriculture and Technology
Kenji Yasunaga, Tokyo Institute of Technology
Abstract

A theoretical framework of the bit security of cryptographic primitives/games was first introduced in a pioneering work by Micciancio and Walter (Eurocrypt 2018), and an alternative framework was introduced by the authors (Asiacrypt 2021). First, we observe that quantitative results in the latter framework are preserved even if adversaries are allowed to output the failure symbol. With this slight modification, we show that the notion of bit security in the latter framework is equivalent to that in the former framework up to constant bits. Also, we demonstrate that several existing notions of advantages can be captured in a unified way. Based on this equivalence, we show that the reduction algorithm of Hast (J. Cryptology, 2004) gives a tight reduction of the Goldreich-Levin hard-core predicate to the hardness of one-way functions. These two results resolved open problems that remained. Furthermore, in the latter framework, we show that all games we need to care about are decision games. Namely, for every search game G, there is the corresponding decision game G′ such that G has λ-bit security if and only if G′ has λ-bit security. The game G′ consists of the real and the ideal games, where attacks in the ideal game are never approved. Such games often appear in game-hopping security proofs. The result justifies such security proofs because they lose no security. Finally, we provide a distribution replacement theorem. Suppose a game using distribution Q in a black-box manner is λ-bit secure, and two distributions P and Q are computationally λ-bit secure indistinguishable. In that case, the game where Q is replaced by P is also λ-bit secure.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in ASIACRYPT 2023
Keywords
Bit SecurityOperational ApproachGoldreich-Levin Theorem
Contact author(s)
shunwata @ cc tuat ac jp
yasunaga @ c titech ac jp
History
2023-09-26: last of 4 revisions
2022-06-01: received
See all versions
Short URL
https://ia.cr/2022/693
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/693,
      author = {Shun Watanabe and Kenji Yasunaga},
      title = {Unified View for Notions of Bit Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/693},
      year = {2022},
      url = {https://eprint.iacr.org/2022/693}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.