Bit Security as Cost to Demonstrate Advantage

Keewoo Lee

doi:10.62056/an5txol7

Bit Security as Cost to Demonstrate Advantage

Authors

Keewoo Lee

UC Berkeley, USA
keewoo dot lee at berkeley dot edu

Keywords: bit security security definition Hellinger distance

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.

References

[ADPS16]

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. https://doi.org/?

Google Scholar ePrint

[AGHP90]

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. https://doi.org/10.1109/FSCS.1990.89575.

Google Scholar ePrint

[BDJR97]

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. https://doi.org/10.1109/SFCS.1997.646128.

Google Scholar ePrint

[BH19]

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. https://doi.org/10.1007/978-3-030-34618-8_2.

Google Scholar ePrint

[BL13]

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. https://doi.org/10.1007/978-3-642-42045-0_17.

Google Scholar ePrint

[BLL⁺15]

Shi Bai, Adeline Langlois, Tancrède Lepoint, Damien Stehlé, and Ron Steinfeld. Improved security proofs in lattice-based cryptography: using the Ré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. https://doi.org/10.1007/978-3-662-48797-6_1.

Google Scholar ePrint

[BR05]

Mihir Bellare and Phillip Rogaway. Introduction to modern cryptography. 2005.

Google Scholar ePrint

[BY02]

Ziv Bar-Yossef. The complexity of massive data set computations. University of California, Berkeley, 2002.

Google Scholar ePrint

[Can17]

Clément Canonne. A short note on distinguishing discrete distributions. 2017.

Google Scholar ePrint

[GK16]

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. https://doi.org/10.1007/978-3-662-49096-9_21.

Google Scholar ePrint

[GL89]

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. https://doi.org/10.1145/73007.73010.

Google Scholar ePrint

[Gol04]

Oded Goldreich. The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press, 2004. ISBN 0-521-83084-2. https://doi.org/10.1017/CBO9780511721656.

Google Scholar ePrint

[GW11]

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. https://doi.org/10.1145/1993636.1993651.

Google Scholar ePrint

[HILL99]

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. https://doi.org/?

Google Scholar ePrint

[KL14]

Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014. ISBN 9781466570269.

Google Scholar ePrint

[KM13]

Neal Koblitz and Alfred Menezes. Another look at non-uniformity. Groups Complex. Cryptol., 5(2):117–139, 2013. https://doi.org/10.1515/GCC-2013-0008.

Google Scholar ePrint

[MW17]

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. https://doi.org/10.1007/978-3-319-63715-0_16.

Google Scholar ePrint

[MW18]

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. https://doi.org/10.1007/978-3-319-78381-9_1.

Google Scholar ePrint

[Nao03]

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. https://doi.org/10.1007/978-3-540-45146-4_6.

Google Scholar ePrint

[PDG14]

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. https://doi.org/10.1007/978-3-662-44709-3_20.

Google Scholar ePrint

[Pei16]

Chris Peikert. A decade of lattice cryptography. Found. Trends Theor. Comput. Sci., 10(4):283–424, 2016. https://doi.org/10.1561/0400000074.

Google Scholar ePrint

[PW]

Yury Polyanskiy and Yihong Wu. Information theory. ?

Google Scholar ePrint

[Reg05]

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. https://doi.org/10.1145/1060590.1060603.

Google Scholar ePrint

[Ros21]

Mike Rosulek. The joy of cryptography. 2021.

Google Scholar ePrint

[WY21]

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. https://doi.org/10.1007/978-3-030-92078-4_6.

Google Scholar ePrint

[WY23]

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. https://doi.org/10.1007/978-981-99-8736-8_12.

Google Scholar ePrint

PDF Open access