Communications in Cryptology IACR CiC

Bit Security as Cost to Demonstrate Advantage


Keewoo Lee
Keewoo Lee
UC Berkeley, USA
keewoo dot lee at berkeley dot edu


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.


Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key exchange - A new hope. In Thorsten Holz and Stefan Savage, editors, USENIX Security 2016, 327–343. August 2016. USENIX Association.
Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. In 31st FOCS, 544–553. October 1990. IEEE Computer Society Press.
Mihir Bellare, Anand Desai, Eric Jokipii, and Phillip Rogaway. A concrete security treatment of symmetric encryption. In 38th FOCS, 394–403. October 1997. IEEE Computer Society Press.
Daniel J. Bernstein and Andreas Hülsing. Decisional second-preimage resistance: when does SPR imply PRE? In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923 of LNCS, 33–62. December 2019. Springer, Heidelberg.
Daniel J. Bernstein and Tanja Lange. Non-uniform cracks in the concrete: the power of free precomputation. In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, 321–340. December 2013. Springer, Heidelberg.
Shi Bai, Adeline Langlois, Tancrède Lepoint, Damien Stehlé, and Ron Steinfeld. Improved security proofs in lattice-based cryptography: using the nyi divergence rather than the statistical distance. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part I, volume 9452 of LNCS, 3–24. November / December 2015. Springer, Heidelberg.
Mihir Bellare and Phillip Rogaway. Introduction to modern cryptography. 2005.
Ziv Bar-Yossef. The complexity of massive data set computations. University of California, Berkeley, 2002.
Shafi Goldwasser and Yael Tauman Kalai. Cryptographic assumptions: A position paper. In Eyal Kushilevitz and Tal Malkin, editors, TCC 2016-A, Part I, volume 9562 of LNCS, 505–522. January 2016. Springer, Heidelberg.
Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In 21st ACM STOC, 25–32. May 1989. ACM Press.
Oded Goldreich. The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, 2004. ISBN 0-521-83084-2.
Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, 99–108. June 2011. ACM Press.
Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396, 1999.
Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014. ISBN 9781466570269.
Neal Koblitz and Alfred Menezes. Another look at non-uniformity. Groups Complex. Cryptol., 5(2):117–139, 2013.
Daniele Micciancio and Michael Walter. Gaussian sampling over the integers: efficient, generic, constant-time. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, 455–485. August 2017. Springer, Heidelberg.
Daniele Micciancio and Michael Walter. On the bit security of cryptographic primitives. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, 3–28. April / May 2018. Springer, Heidelberg.
Moni Naor. On cryptographic assumptions and challenges (invited talk). In Dan Boneh, editor, CRYPTO 2003, volume 2729 of LNCS, 96–109. August 2003. Springer, Heidelberg.
Thomas Pöppelmann, Léo Ducas, and Tim Güneysu. Enhanced lattice-based signatures on reconfigurable hardware. In Lejla Batina and Matthew Robshaw, editors, CHES 2014, volume 8731 of LNCS, 353–370. September 2014. Springer, Heidelberg.
Chris Peikert. A decade of lattice cryptography. Found. Trends Theor. Comput. Sci., 10(4):283–424, 2016.
Yury Polyanskiy and Yihong Wu. Information theory. ?
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, 37th ACM STOC, 84–93. May 2005. ACM Press.
Mike Rosulek. The joy of cryptography. 2021.
Shun Watanabe and Kenji Yasunaga. Bit security as computational cost for winning games with high probability. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, 161–188. December 2021. Springer, Heidelberg.
Shun Watanabe and Kenji Yasunaga. Unified view for notions of bit security. In Jian Guo and Ron Steinfeld, editors, ASIACRYPT 2023, Part VI, volume 14443 of LNCS, 361–389. December 2023. Springer, Heidelberg.

PDFPDF Open access

Submitted: 2023-12-29
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Keewoo Lee, "Bit Security as Cost to Demonstrate Advantage," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/an5txol7.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.