CryptoDB
The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for Free
| Authors: |
|
|---|---|
| Download: |
|
| 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
}