CryptoDB
Unified View for Notions of Bit Security
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | ASIACRYPT 2023 |
| Abstract: | We study the framework of Watanabe and Yasunaga (Asiacrypt 2021) that enables us to evaluate the bit security of cryptographic primitives/games with an operational meaning. First, we observe that their quantitative results preserve even if adversaries are allowed to output the failure symbol in games. With this slight modification, we show that the notion of bit security by Watanabe and Yasunaga is equivalent to that of Micciancio and Walter (Eurocrypt 2018) 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. We show that all games we need to care about in their framework 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. |
BibTeX
@inproceedings{asiacrypt-2023-33399,
title={Unified View for Notions of Bit Security},
publisher={Springer-Verlag},
author={Shun Watanabe and Kenji Yasunaga},
year=2023
}