Paper 2020/1246

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.

Metadata
Available format(s)
PDF
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
2020-10-09: received
See all versions
Short URL
https://ia.cr/2020/1246
License
Creative Commons Attribution
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.