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:
Search ePrint
Search Google
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.
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},
  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
}