Revision #1 Authors: Danny Harnik, Naor Moni

Accepted on: 21st June 2006 00:00

Downloads: 2754

Keywords:

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.

TR06-022 Authors: Danny Harnik, Moni Naor

Publication: 17th February 2006 16:11

Downloads: 3248

Keywords:

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.