Abstract:
We initiate the study of compression that preserves the solution to an instance of problem rather than preserving the instance itself. Our focus is on the compressibility of NP problems. We consider NP problems that have long instances but relatively short witnesses. The question is, can one 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 rather than the length of original input. Such compression enables to succinctly store instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. We give a new classification of NP with respect to compression. This classification forms a stratification of NP that we call the VC hierarchy. The hierarchy is based on a new type of reduction called W-reduction and there are compression-complete problems for each class. Our motivation for studying this issue stems from the vast cryptographic implications compressibility has. For example, we say that SAT is compressible if there exists a polynomial p(.,.) so that given a formula consisting of m clauses over n variables it is possible to come up with an equivalent (w.r.t satisfiability) formula of size at most p(n, log m). Then given a compression algorithm for SAT we provide a construction of collision resistant hash functions from any one-way function. This task was shown to be impossible via black-box reductions [Simon 98], and indeed the construction presented is inherently non-black-box. Another application of SAT compressibility is a cryptanalytic result concerning the limitation of everlasting security in the bounded storage model when mixed with (time) complexity based cryptography. In addition, we study an approach to constructing an Oblivious Transfer Protocol from any one-way function. This approach is based on compression for SAT that also has a property that we call witness retrievability. However, we mange to prove severe limitations on the ability to achieve witness retrievable compression of SAT.

Abstract:
We initiate the study of the compressibility of NP problems. We consider NP problems that have long instances but relatively short witnesses. The question is, can one 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 rather than the length of original input. Such compression enables to succinctly store instances until a future setting will allow solving them, either via a technological or algorithmic breakthrough or simply until enough time has elapsed. We give a new classification of NP with respect to compression. This classification forms a stratification of NP that we call the VC hierarchy. The hierarchy is based on a new type of reduction called W-reduction and there are compression-complete problems for each class. Our motivation for studying this issue stem from the vast cryptographic implications compressibility has. For example, suppose that SAT is compressible, that is there exist a polynomial p(.,.) so that given a formula consisting of m clauses over n variables it is possible to come up with an equivalent (w.r.t satisfiability) formula of size at most p(n, log m). Then if the reduction is what we call witness retrievable we provide a construction of an Oblivious Transfer Protocol from any one-way function. Using the terminology of Impagliazzo [Imp95], this implies that Minicrypt=Cryptomania. Other implications of SAT compressibility (without the witness retrievability) are: (i) the construction of collision resistant hash function from any one-way function and (ii) a cryptanalytic result concerning the limitation of everlasting security in the bounded storage model when mixed with (time) complexity based cryptography.