HackerPapers

arXiv:cs/0012023cs.CR

The Tale of One-way Functions

Leonid A. Levin

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

The existence of one-way functions is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant to this problem. For instance, it gives the first combinatorial complete owf, i.e., a function which is one-way if any function is. There are surprisingly many subtleties in basic definitions. Some of these subtleties are discussed or hinted at in the literature and some are overlooked. Here, a unified approach is attempted.

arXiv comments
Small changes. 16 pages in English; 18 pages in Russian (KOI8 encoding, translated by Alexander Shen)
Journal reference
Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, 2003
DOI
Subjects
cs.CRCryptography and Security cs.CCComputational Complexity

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Apr 2022 to Apr 2022. Found in 1 HN submission from Mar 2021 to Mar 2021. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. The existence of true one-way functions depends on Kolmogorov complexity 1 comment

    • Identifying the connection between one-way functions and Kolmogorov complexity is truly impressive. But the article oversimplified a few things that may be misleading for someone. 1. One-way functions are not all cryptography. Some constructions may need stronger assumptions…

      gnullView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.