Kolmogorov One-Way Functions Revisited

Cryptography

Casal, Filipe¹ 

关键词: Kolmogorov complexity;    one-way functions;    cryptography;    complexity theory;   

DOI  :  10.3390/cryptography2020009

学科分类：工程和技术（综合）

来源: mdpi

【 摘 要 】

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.

【 授权许可】

CC BY