The leakage-resilience limit of a computational problem is equal to its unpredictability entropy

摘要: A cryptographic assumption is the (unproven) mathematical statement that a certain computational problem (e.g. factoring integers) computationally hard. The leakage-resilience limit of assumption, and hence search problem, maximal number bits information can be leaked (adaptively) about an instance, without making easy to solve. This implies security underlying scheme against arbitrary side channel attacks by unbounded adversary as long less than leakage resilience limit. The hardness typically characterized running time fastest (known) algorithm for solving it. We propose consider, another natural complexity-theoretic quantity, success probability best polynomial-time (which exponentially small). refer its negative logarithm unpredictability entropy defined up additive logarithmic term). A main result paper are equal. demonstrates, first time, practical relevance studying algorithms even problems believed hard, if too small interest. With this view, we look at probabilistic polynomial learning with errors lattice have in recent years gained cryptography. We also introduce concept witness compression problems, namely reduction which witnesses shorter. length smallest achievable corresponds non-adaptive limit, it shown equal problem. independent theoretical An example implication our 3-SAT n variables compressed from (the variable assignments) 0.41 bits.