International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for Free

Authors:
Gianluca Brian , Sapienza University of Rome
Antonio Faonio , EURECOM
Maciej Obremski , National University of Singapore
João Ribeiro , Imperial College London
Mark Simkin , Aarhus University
Maciej Skórski , University of Luxembourg
Daniele Venturi , Sapienza University of Rome
Download:
DOI: 10.1007/978-3-030-77886-6_14 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2021
Abstract: We show that noisy leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to a small statistical simulation error and a slight loss in the leakage parameter. The latter holds true in particular for one of the most used noisy-leakage models, where the noisiness is measured using the conditional average min-entropy (Naor and Segev, CRYPTO'09 and SICOMP'12). Our reductions between noisy and bounded leakage are achieved in two steps. First, we put forward a new leakage model (dubbed the dense leakage model) and prove that dense leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to small statistical distance. Second, we show that the most common noisy-leakage models fall within the class of dense leakage, with good parameters. We also provide a complete picture of the relationships between different noisy-leakage models, and prove lower bounds showing that our reductions are nearly optimal. Our result finds applications to leakage-resilient cryptography, where we are often able to lift security in the presence of bounded leakage to security in the presence of noisy leakage, both in the information-theoretic and in the computational setting. Additionally, we show how to use lower bounds in communication complexity to prove that bounded-collusion protocols (Kumar, Meka, and Sahai, FOCS'19) for certain functions do not only require long transcripts, but also necessarily need to reveal enough information about the inputs.
Video from EUROCRYPT 2021
BibTeX
@inproceedings{eurocrypt-2021-30805,
  title={The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for Free},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-77886-6_14},
  author={Gianluca Brian and Antonio Faonio and Maciej Obremski and João Ribeiro and Mark Simkin and Maciej Skórski and Daniele Venturi},
  year=2021
}