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)
Abstract
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.
