Paper 2020/423
On Oneway Functions and Kolmogorov Complexity
Yanyi Liu and Rafael Pass
Abstract
We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial $t(n)\geq (1+\varepsilon)n, \varepsilon>0$, the following are equivalent:  Oneway functions exists (which in turn is equivalent to the existence of secure privatekey encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more);  $t$time bounded Kolmogorov Complexity, $K^t$, is mildly hardonaverage (i.e., there exists a polynomial $p(n)>0$ such that no $\PPT$ algorithm can compute $K^t$, for more than a $1\frac{1}{p(n)}$ fraction of $n$bit strings). In doing so, we present the first natural, and wellstudied, computational problem characterizing the feasibility of the central privatekey primitives and protocols in Cryptography.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint.
 Keywords
 oneway functionsKolmogorov complexityaveragecase hardness
 Contact author(s)

yl2866 @ cornell edu
rafael @ cs cornell edu  History
 20200924: last of 3 revisions
 20200415: received
 See all versions
 Short URL
 https://ia.cr/2020/423
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/423, author = {Yanyi Liu and Rafael Pass}, title = {On Oneway Functions and Kolmogorov Complexity}, howpublished = {Cryptology ePrint Archive, Paper 2020/423}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/423}}, url = {https://eprint.iacr.org/2020/423} }