Paper 2022/655

Bit Security as Cost to Observe Advantage: Towards the Definition from THE BOOK

Keewoo Lee
Abstract

We revisit the question of what should be the definition of bit security, 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 easily well-estimated in terms of Kullback-Leibler divergence. Along the way of defining bit security and justifying our definition, we raise undervalued concepts such as allowing aborts in security games, considering partial adversaries, and verifiability in security games.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Bit security Security definitions Kullback-Leibler divergence
Contact author(s)
activecondor @ snu ac kr
History
2022-05-31: approved
2022-05-27: received
See all versions
Short URL
https://ia.cr/2022/655
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/655,
      author = {Keewoo Lee},
      title = {Bit Security as Cost to Observe Advantage: Towards the Definition from THE BOOK},
      howpublished = {Cryptology ePrint Archive, Paper 2022/655},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/655}},
      url = {https://eprint.iacr.org/2022/655}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.