Creating and sharing knowledge for telecommunications

Kolmogorov One-Way Functions Revisited

Souto, A. ; Casal, F. ; Rasga, J.

Designs, Codes, and Cryptography Vol. 2, Nº 2, pp. 9 - 9, April, 2018.

ISSN (print): 0925-1022
ISSN (online): 1573-7586

Scimago Journal Ranking: 0,74 (in 2018)

Digital Object Identifier: 10.3390/cryptography2020009

Download Full text PDF ( 289 KBs)

We study characterizations of one-way functions in terms of time-bounded Kolmogorov complexity. As the main contribution, we propose definitions for strong and weak Kolmogorov one-way functions and show that these are equivalent to classical strong and weak one-way functions, respectively. The new definitions were motivated by the fact that the expected value approach is not able to characterize strong one-way functions as we prove in the paper.