Aarhus University Seal

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

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

DOI

  • Gianluca Brian, University of Rome La Sapienza
  • ,
  • Antonio Faonio, Institut Mines-Télécom
  • ,
  • MacIej Obremski, Centre for Quantum Technologies, National University of Singapore
  • ,
  • Joao Ribeiro, Imperial College London, Carnegie Mellon University
  • ,
  • Mark Simkin, Ethereum Foundation
  • ,
  • MacIej Skorski, University of Luxembourg, Sensyne Health
  • ,
  • Daniele Venturi, University of Rome La Sapienza

We show that the most common flavors of 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. Third, we prove lower bounds on the amount of bounded leakage required for simulation with sub-constant error, showing that our reductions are nearly optimal. In particular, our results imply that useful general simulation of noisy leakage based on statistical distance and mutual information is impossible. We also provide a complete picture of the relationships between different noisy-leakage models. 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. Remarkably, this lifting procedure makes only black-box use of the underlying schemes. 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.

Original languageEnglish
JournalIEEE Transactions on Information Theory
Volume68
Issue12
Pages (from-to)8197-8227
Number of pages31
ISSN0018-9448
DOIs
Publication statusPublished - Dec 2022

Bibliographical note

Publisher Copyright:
© 1963-2012 IEEE.

    Research areas

  • black-box reductions, bounded leakage, dense leakage, Leakage-resilient cryptography

See relations at Aarhus University Citationformats

ID: 296228789