Creating and sharing knowledge for telecommunications

Teixeira, A.T. ; Antunes, L. ; Matos, A. ; Pinto, A. ; Souto, A.

Theory of Computing Systems Vol. 52, Nº 1, pp. 162 - 178, January, 2013.

ISSN (print): 1433-0490

ISSN (online): 1432-4350

Journal Impact Factor: 0,533 (in 2014)

Digital Object Identifier: 10.1007/s00224-012-9418-z

Abstract

We prove several results relating injective one-way functions, time-bounded conditional Kolmogorov complexity, and time-bounded conditional entropy.

First we establish a connection between injective, strong and weak one-way functions and the expected value of the polynomial time-bounded Kolmogorov complexity, denoted here by E(K t (x|f(x))). These results are in both directions. More precisely, conditions on E(K t (x|f(x))) that imply that f is a weak one-way function, and properties of E(K t (x|f(x))) that are implied by the fact that f is a strong one-way function. In particular, we prove a separation result: based on the concept of time-bounded Kolmogorov complexity, we find an interval in which every function f is a necessarily weak but not a strong one-way function.

Then we propose an individual approach to injective one-way functions based on Kolmogorov complexity, defining Kolmogorov one-way functions and prove some relationships between the new proposal and the classical definition of one-way functions, showing that a Kolmogorov one-way function is also a deterministic one-way function. A relationship between Kolmogorov one-way functions and the conjecture of polynomial time symmetry of information is also proved.

Finally, we relate E(K t (x|f(x))) and two forms of time-bounded entropy, the unpredictable entropy H unp, in which “one-wayness” of a function can be easily expressed, and the Yao+ entropy, a measure based on compression/decompression schema in which only the decompressor is restricted to be time-bounded.

First we establish a connection between injective, strong and weak one-way functions and the expected value of the polynomial time-bounded Kolmogorov complexity, denoted here by E(K t (x|f(x))). These results are in both directions. More precisely, conditions on E(K t (x|f(x))) that imply that f is a weak one-way function, and properties of E(K t (x|f(x))) that are implied by the fact that f is a strong one-way function. In particular, we prove a separation result: based on the concept of time-bounded Kolmogorov complexity, we find an interval in which every function f is a necessarily weak but not a strong one-way function.

Then we propose an individual approach to injective one-way functions based on Kolmogorov complexity, defining Kolmogorov one-way functions and prove some relationships between the new proposal and the classical definition of one-way functions, showing that a Kolmogorov one-way function is also a deterministic one-way function. A relationship between Kolmogorov one-way functions and the conjecture of polynomial time symmetry of information is also proved.

Finally, we relate E(K t (x|f(x))) and two forms of time-bounded entropy, the unpredictable entropy H unp, in which “one-wayness” of a function can be easily expressed, and the Yao+ entropy, a measure based on compression/decompression schema in which only the decompressor is restricted to be time-bounded.

© 2021, IT - Instituto de Telecomunicações | All Rights Reserved