Bit Security: Optimal Adversaries, Equivalence Results, and a Toolbox for Computational-statistical Security Analysis w/ Daniele Micciancio
#Abstract
We investigate the notion of bit-security for decisional cryptographic properties, as originally proposed in (Micciancio & Walter, Eurocrypt 2018), and its main variants and extensions, with the goal clarifying the relation between different definitions, and facilitating their use.
Specific contributions of this paper include:
(1) identifying the optimal adversaries achieving the highest possible MW advantage, showing that they are deterministic and have a very simple threshold structure;
(2) giving a simple proof that a competing definition proposed by (Watanabe & Yasunaga, Asiacrypt 2021) is actually equivalent to the original MW definition; and
(3) developing tools for the use of the extended notion of computational-statistical bit-security introduced in (Li, Micciancio, Schultz & Sorrell, Crypto 2022), showing that it fully supports common cryptographic proof techniques like hybrid arguments and probability replacement theorems.
On the technical side, our results are obtained by introducing a new notion of "fuzzy" distinguisher (which we prove equivalent to the "aborting" distinguishers of Micciancio and Walter), and a tight connection between the MW advantage and the Le Cam metric, a standard quantity used in statistics.
#About the Speaker
Daniele Micciancio received his PhD in computer science from the Massachusetts Institute of Technology in 1998, and joined the faculty of the University of California, San Diego, in 1999, where he is currently a professor in the computer science and engineering department.
His primary research areas are cryptography and theoretical computer science. Daniele is most known for his work on the complexity of lattice problems, lattice algorithms, and the foundation of lattice-based cryptography.
He received the Matchey Award (FOCS 1998), Sprowls Award (MIT EECS, 1999), CAREER Award (NSF, 2001), Hellman Fellowship (2001), Sloan Fellowship (2003), and two 20-years Test of Time Awards (FOCS 2022, FOCS 2024).
In 1999 he was appointed Fellow of the IACR for his pioneering work on lattice cryptography and the complexity of lattice problems.
#More Information
Want more information, recordings of the presentations, slides, and other resources from the meetup? Visit this meetup's resource page at https://fhe.org/meetups/070
#Never Miss an Update
The newsletter where we post community announcements: https://fheorg.substack.com/
The discord server where you can discuss FHE related topics with the community: https://discord.fhe.org
Make sure to join either (or both) of these to stay informed about future events!