Cryptology ePrint Archive: Report 2020/1246

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

Gianluca Brian and Antonio Faonio and Maciej Obremski and Joăo Ribeiro and Mark Simkin and 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.

Category / Keywords: foundations / Information theory, Leakage-resilient cryptography

Date: received 8 Oct 2020, last revised 15 Oct 2020

Contact author: brian at di uniroma1 it,antonio faonio@eurecom fr,obremski math@gmail com,j lourenco-ribeiro17@imperial ac uk,simkin@cs au dk,maciej skorski@uni lu,venturi@di uniroma1 it

Available format(s): PDF | BibTeX Citation

Note: Added some references.

Version: 20201015:102836 (All versions of this report)

Short URL: ia.cr/2020/1246


[ Cryptology ePrint archive ]