Time Bounded Incompressible Theorem Reversed

Abstract

Security of data is crucial in nowadays societies. One of the most basic security protocols are the zero-knowledge protocols where a prover convinces a verifier of the knowledge of a secret information without revealing that piece of information. The tradicional approach to prove the security of these protocols is based on the (im)possibility of simulation of the interactions. A more fundamental way to prove the security is based solely on the information conveyed about proof. In order to establish that connection and quantifying the number of possible transformations that one can use in these protocols, we use Kolmogorov complexity and in particular we focus on the incompressibility theorem. In this paper we study the counterpart of this theorem by, instead of providing the number of x such that for a fixed y, Kt(x|y) ≈ Kt(x), we study for a fixed y the number of x such that Kt(x|y) ≈ Kt(x). As a second contribution of this paper we present an extension of the results regarding Kolmogorov one-way functions started in [3]. This cryptographic primitives have the property to be easy to compute but hard to invert and are a basilar ingredient for digital security.