We initiate the study of 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,
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.
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 by Simon, and indeed the construction
presented is inherently non-black-box. Another application of SAT
compressibility is a cryptanalytic result oncerning the limitation f
verlasting security in the bounded storage model when mixed with (time)
complexity based cryptography.
Joint work with Moni Naor.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.