Welcome to the resource topic for 2024/1506
Title:
Bit Security: optimal adversaries, equivalence results, and a toolbox for computational-statistical security analysis
Authors: Daniele Micciancio, Mark Schultz-Wu
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.
ePrint: https://eprint.iacr.org/2024/1506
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .