The Leakage-Resilience Limit of a Computational Problem is Equal to its Unpredictability Entropy
Divesh Aggarwal and Ueli Maurer
A cryptographic assumption is the (unproven) mathematical statement that a certain computational problem (e.g. factoring integers) is computationally hard. The leakage-resilience limit of a cryptographic assumption, and hence of a computational search problem, is the maximal number of bits of information that can be leaked (adaptively) about an instance, without making the problem easy to solve. This implies security of the underlying scheme against arbitrary side channel attacks by a computationally unbounded adversary as long as the number of leaked bits of information is less than the leakage resilience limit.
The hardness of a computational problem is typically characterized by the running time of the fastest (known) algorithm for solving it. We propose to consider, as another natural complexity-theoretic quantity, the success probability of the best polynomial-time algorithm (which can be exponentially small). We refer to its negative logarithm as the unpredictability entropy of the problem (which is defined up to an additive logarithmic term).
A main result of the paper is that the leakage-resilience limit and the unpredictability entropy are equal. This demonstrates, for the first time, the practical relevance of studying polynomial-time algorithms even for problems believed to be hard, and even if the success probability is too small to be of practical interest. With this view, we look at the best probabilistic polynomial time algorithms for the learning with errors and lattice problems that have in recent years gained relevance in cryptography.
We also introduce the concept of witness compression for computational problems, namely the reduction of a problem to another problem for which the witnesses are shorter. The length of the smallest achievable witness for a problem also corresponds to the non-adaptive leakage-resilience limit, and it is also shown to be equal to the unpredictability entropy of the problem. The witness compression concept is also of independent theoretical interest. An example of an implication of our result is that 3-SAT for $n$ variables can be witness compressed from $n$ bits (the variable assignments) to $0.41 n$ bits.
BibTeX Citation
@inproceedings{AggMau11,
author = {Divesh Aggarwal and Ueli Maurer},
title = {The Leakage-Resilience Limit of a Computational Problem is Equal to its Unpredictability Entropy},
editor = {D. H. Lee and X. Wang},
booktitle = {Advances in Cryptology - Asiacrypt 2011},
pages = 686-701,
series = {Lecture Notes in Computer Science},
volume = 7073,
year = 2011,
publisher = {Springer-Verlag},
}