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

Gianluca Brian, Antonio Faonio, Maciej Obremski, João Ribeiro, Mark Simkin, Maciej Skórski, and Daniele Venturi

##### 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.

Note: Minor revisions.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2021
DOI
10.1007/978-3-030-77886-6_14
Keywords
Information theoryLeakage-resilient cryptography
Contact author(s)
brian @ di uniroma1 it
antonio faonio @ eurecom fr
obremski math @ gmail com
jlourenc @ andrew cmu edu
simkin @ cs au dk
maciej skorski @ uni lu
venturi @ di uniroma1 it
History
2021-09-17: last of 3 revisions
See all versions
Short URL
https://ia.cr/2020/1246

CC BY

BibTeX

@misc{cryptoeprint:2020/1246,
author = {Gianluca Brian and Antonio Faonio and Maciej Obremski and João Ribeiro and Mark Simkin and Maciej Skórski and Daniele Venturi},
title = {The Mother of All Leakages: How to Simulate Noisy Leakages via Bounded Leakage (Almost) for Free},
howpublished = {Cryptology ePrint Archive, Paper 2020/1246},
year = {2020},
doi = {10.1007/978-3-030-77886-6_14},
note = {\url{https://eprint.iacr.org/2020/1246}},
url = {https://eprint.iacr.org/2020/1246}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.