Bit Security: optimal adversaries, equivalence results, and a toolbox for computational-statistical security analysis

Daniele Micciancio; Mark Schultz-Wu

Paper 2024/1506

Bit Security: optimal adversaries, equivalence results, and a toolbox for computational-statistical security analysis

Daniele Micciancio

, University of California, San Diego

Mark Schultz-Wu

, University of California, San Diego

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.

Note: Same content as proceedings version, with only formatting differences

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in TCC 2024
Keywords: Bit security computational security statistical security Le Cam distance
Contact author(s): daniele @ cs ucsd edu
mdschult @ ucsd edu
History: 2024-09-30: approved; 2024-09-25: received; See all versions
Short URL: https://ia.cr/2024/1506
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1506,
      author = {Daniele Micciancio and Mark Schultz-Wu},
      title = {Bit Security: optimal adversaries, equivalence results, and a toolbox for computational-statistical security analysis},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1506},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1506}
}