On the compressibility of n p instances and cryptographic applications

Abstract

We study compression that preserves the solution to an instance of a problem rather than preserving the instance itself. Our focus is on the compressibility of NP decision problems. We consider NP problems that have long instances but relatively short witnesses. The question is whether one can efficiently compress an instance and store a shorter representation that maintains the information of whether the original input is in the language or not. We want the length of the compressed instance to be polynomial in the length of the witness and polylog in the length of original input. Such compression enables succinctly storing instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. In this paper, we first develop the basic complexity theory of compression, including reducibility, completeness, and a stratification of NP with respect to compression. We then show that compressibility (say, of SAT) would have vast implications for cryptography, including constructions of one-way functions and collision resistant hash functions from any hard-on-average problem in NP and cryptanalysis of key agreement protocols in the "bounded storage model" when mixed with (time) complexity-based cryptography. © 2010 Society for Industrial and Applied Mathematics.