Paper 2022/655
Bit Security as Cost to Observe Advantage: Towards the Definition from THE BOOK
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)
- 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
-
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} }