International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Bit Security as Cost to Demonstrate Advantage

Authors:
Keewoo Lee , UC Berkeley
Download:
DOI: 10.62056/an5txol7
URL: https://cic.iacr.org//p/1/1/1
Search ePrint
Search Google
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.

BibTeX
@article{cic-2024-34117,
  title={Bit Security as Cost to Demonstrate Advantage},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 1},
  url={https://cic.iacr.org//p/1/1/1},
  doi={10.62056/an5txol7},
  author={Keewoo Lee},
  year=2024
}