The Tale of One-way Functions
<|reference_start|>The Tale of One-way Functions: 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.<|reference_end|>
@article{levin2000the,
    title={The Tale of One-way Functions},
    author={Leonid A. Levin},
    journal={Problems of Information Transmission (= Problemy Peredachi
  Informatsii), 39(1):92-103, 2003},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0012023},
    primaryClass={cs.CR cs.CC}
}