CryptoDB
Bit Security: optimal adversaries, equivalence results, and a toolbox for computational/statistical security analysis
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2024 |
| 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. |
BibTeX
@inproceedings{tcc-2024-34795,
title={Bit Security: optimal adversaries, equivalence results, and a toolbox for computational/statistical security analysis},
publisher={Springer-Verlag},
author={Daniele Micciancio and Mark Schultz-Wu},
year=2024
}