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.

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.