More Like this

1. On One-way Functions and Kolmogorov Complexity

   https://doi.org/10.1109/FOCS46700.2020.00118  

   Liu, Yanyi; Pass, Rafael (November 2020, FOCS'20)

   null (Ed.)
2. On One-Way Functions and Sparse Languages

   Liu, Yanyi; Pass, Rafael (November 2023, Springer)
3. On One-way Functions and Kolmogorov Complexity

   Liu, Yanyi; Pass, Rafael (January 2020, IEEE Symposium on Foundations of Computer Science (FOCS))

   null (Ed.)

   We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n) ≥ (1 + ε)n, ε > 0, the following are equivalent: • One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more); • t-time bounded Kolmogorov Complexity, Kt, is mildly hard-on-average (i.e., there exists a polynomial p(n) > 0 such that no PPT algorithm can compute Kt, for more than a 1 − 1/p(n) fraction of n-bit strings). In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography. 

   more » « less
4. On One-Way Functions and Sparse Languages

   Yanyi Liu and Rafael Pass (November 2023, TCC'23)
5. Non-interactive Secure Computation from One-Way Functions

   https://doi.org/10.1007/978-3-030-03332-3_5  

   Badrinarayanan, Saikrishna; Jain, Abhishek; Ostrovsky, Rafail; Visconti, Ivan (January 2018, Advances in Cryptology - ASIACRYPT 2018)