Content area
Full Text
Theory Comput Syst (2013) 52:162178 DOI 10.1007/s00224-012-9418-z
One-Way Functions Using Algorithmic and Classical Information Theories
Lus Antunes Armando Matos Alexandre Pinto
Andr Souto Andreia Teixeira
Published online: 25 July 2012 Springer Science+Business Media, LLC 2012
A very preliminary version of this paper appeared in Proceedings of the 6th International Conference on Computability in Europe, Azores, Portugal, July 2010, pages 346356.
L. Antunes A. Matos A. Teixeira ( )
Computer Science Department, Faculdade de Cincias da Universidade do Porto, Rua Campo Alegre 1021/1055, 4169-007 Porto, Portugale-mail: mailto:[email protected]
Web End [email protected]
L. Antunese-mail: mailto:[email protected]
Web End [email protected]
A. Matose-mail: mailto:[email protected]
Web End [email protected]
L. Antunes A. Souto A. Teixeira
Security and Quantum Information Group, Instituto de Telecomunicaes, Av. Rovisco Pais 1, 1049-001 Lisboa, Portugal
A. Soutoe-mail: mailto:[email protected]
Web End [email protected]
A. MatosLaboratrio de Inteligncia Articial e Cincias de Computadores, Rua Campo Alegre 1021/1055, 4169-007 Porto, Portugal
A. PintoInstituto Superior da Maia, Avenida Carlos Oliveira Campos, 4475-690 Castelo da Maia AviosoS. Pedro, Portugale-mail: mailto:[email protected]
Web End [email protected]
A. PintoHASLab, Instituto de Engenharia de Sistemas e Computadores, Rua Alves Redol. 9, 1000-029 Lisboa, Portugal
A. SoutoMathematical Department, Instituto Superior Tcnico da Universidade Tcnica de Lisboa, Avenida Rovisco Pais, 1049-001 Lisboa, Portugal
Theory Comput Syst (2013) 52:162178 163
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(Kt(x|f (x))). These results are in both directions. More pre
cisely, conditions on E(Kt(x|f (x))) that imply that f is a weak one-way function,
and properties of E(Kt(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 nd 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, dening Kolmogorov one-way functions and prove some relationships between the new proposal and the classical denition 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...