Bit Security as Cost to Demonstrate Advantage

Keewoo Lee

Paper 2022/655

Bit Security as Cost to Demonstrate Advantage

Keewoo Lee, UC Berkeley

Abstract

We revisit the question of what the definition of bit security should be, previously answered by Micciancio-Walter (Eurocrypt 2018) and Watanabe-Yasunaga (Asiacrypt 2021). Our new definition is simple, but (i) captures both search and decision primitives in a single framework like Micciancio-Walter, and (ii) has a firm operational meaning like Watanabe-Yasunaga. It also matches intuitive expectations and can be well-formulated regarding Hellinger distance. To support and justify the new definition, we prove several classic security reductions with respect to our bit security. We also provide pathological examples that indicate the ill-definedness of bit security defined in Micciancio-Walter and Watanabe-Yasunaga.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. IACR CiC
Keywords: bit security security definition Hellinger distance
Contact author(s): keewoo lee @ berkeley edu
History: 2024-04-06: revised; 2022-05-27: received; See all versions
Short URL: https://ia.cr/2022/655
License: CC BY

BibTeX

@misc{cryptoeprint:2022/655,
      author = {Keewoo Lee},
      title = {Bit Security as Cost to Demonstrate Advantage},
      howpublished = {Cryptology ePrint Archive, Paper 2022/655},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/655}},
      url = {https://eprint.iacr.org/2022/655}
}