Problemy Peredachi Informatsii
General information
Latest issue
Impact factor
Guidelines for authors

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Probl. Peredachi Inf.:

Personal entry:
Save password
Forgotten password?

Probl. Peredachi Inf., 2003, Volume 39, Issue 1, Pages 103–117 (Mi ppi208)  

This article is cited in 28 scientific papers (total in 28 papers)

One-Way Functions

L. A. Levin

Abstract: The existence of one-way functions (owf) 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.

Full text: PDF file (2362 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2003, 39:1, 92–103

Bibliographic databases:

UDC: 621.391:519.2

Citation: L. A. Levin, “One-Way Functions”, Probl. Peredachi Inf., 39:1 (2003), 103–117; Problems Inform. Transmission, 39:1 (2003), 92–103

Citation in format AMSBIB
\by L.~A.~Levin
\paper One-Way Functions
\jour Probl. Peredachi Inf.
\yr 2003
\vol 39
\issue 1
\pages 103--117
\jour Problems Inform. Transmission
\yr 2003
\vol 39
\issue 1
\pages 92--103

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. A. Semenov, “O slozhnosti obrascheniya diskretnykh funktsii iz odnogo klassa”, Diskretn. analiz i issled. oper., ser. 1, ser. 1, 11:4 (2004), 44–55  mathnet  mathscinet
    2. Freivalds R., “Knot theory, Jones polynomial and quantum computing”, Mathematical foundations of computer science 2005, Lecture Notes in Comput. Sci., 3618, Springer, Berlin, 2005, 15–25  crossref  mathscinet  zmath  isi
    3. Aaronson S., “The learnability of quantum states”, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 463:2088 (2007), 3089–3114  crossref  mathscinet  zmath  adsnasa  isi
    4. D. Grigoriev, A. Kojevnikov, S. J. Nikolenko, “Algebraic cryptography: new constructions and their security against provable break”, St. Petersburg Math. J., 20:6 (2009), 937–953  mathnet  crossref  mathscinet  zmath  isi
    5. Dowe D.L., “Foreword re C. S. Wallace”, Computer Journal, 51:5 (2008), 523-560  crossref  isi  elib
    6. Hirsch E.A., Itsykson D.M., “An infinitely-often one-way function based on an average-case assumption”, Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence, 5110, 2008, 208–217  mathscinet  zmath  isi
    7. Kojevnikov A., Nikolenko S.I., “New combinatorial complete one-way functions”, Stacs 2008: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, 2008, 457–466  mathscinet  zmath  isi
    8. E. A. Hirsch, D. M. Itsykson, “Infinitely frequently one-sided function based on an assumption on complexity in the mean”, St. Petersburg Math. J., 21:3 (2010), 459–468  mathnet  crossref  mathscinet  zmath  isi
    9. A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183  mathnet  crossref  mathscinet  zmath  isi
    10. Hagar A., “Active fault-tolerant quantum error correction: the curse of the open system”, Philos. Sci., 76:4 (2009), 506–535  crossref  isi
    11. Birget J.C., “On the Circuit-Size of Inverses”, Internat J Found Comput Sci, 22:8 (2011), 1925–1938  crossref  mathscinet  zmath  isi
    12. S. Yu. Erofeev, V. A. Romankov, “Postroenie odnostoronnikh funktsii na osnove nerazreshimosti problemy endomorfnoi svodimosti v gruppakh”, PDM, 2011, prilozhenie k № 4, 32–33  mathnet
    13. A. P. Davydow, S. I. Nikolenko, “Circuit complexity of linear functions: gate elimination and feeble security”, J. Math. Sci. (N. Y.), 188:1 (2013), 35–46  mathnet  crossref  mathscinet
    14. S. Yu. Erofeev, V. A. Romankov, “O postroenii vozmozhno odnostoronnikh funktsii na osnove algoritmicheskoi nerazreshimosti problemy endomorfnoi svodimosti v gruppakh”, PDM, 2012, no. 3(17), 13–24  mathnet
    15. S. I. Nikolenko, D. S. Tugaryov, “A complete one-way function based on a free finite rank $\mathbb Z\times\mathbb Z$-module”, J. Math. Sci. (N. Y.), 192:3 (2013), 307–315  mathnet  crossref  mathscinet
    16. Erofeev S.Yu., Romankov V.A., “O vozmozhnosti postroeniya odnostoronnikh funktsii na osnove nerazreshimosti problemy endomorfnoi svodimosti v gruppakh”, Vestnik omskogo universiteta, 2012, no. 2, 53–56  mathscinet  elib
    17. de Castro A., “One-Way-Ness in the Input-Saving (Turing) Machine”, Physica A, 415 (2014), 473–478  crossref  isi
    18. Birget J.C., “Semigroups and One-Way Functions”, Int. J. Algebr. Comput., 25:1-2 (2015), 3–36  crossref  mathscinet  zmath  isi
    19. L. V. Sakharova, “Avtomodelnost zadachi teplovoi konvektsii, osrednennoi po tonkomu sloyu”, Mezhdunar. nauch.-issled. zhurn., 2016, no. 7-4(49), 94–97  mathnet  crossref
    20. de Castro A., “Quantum One-Way Permutation Over the Finite Field of Two Elements”, Quantum Inf. Process., 16:6 (2017), UNSP 149  crossref  mathscinet  isi  scopus
    21. Currin A., Korovin K., Ababi M., Roper K., Kell D.B., Day Ph.J., King R.D., “Computing Exponentially Faster: Implementing a Non- Deterministic Universal Turing Machine Using Dna”, J. R. Soc. Interface, 14:128 (2017), 20160990  crossref  isi  scopus
    22. Feinstein C.A., “Why Do We Live in a Quantum World?”, Phys. Essays, 30:1 (2017), 57–59  crossref  isi  scopus
    23. Kavokin A., Baumberg J., Malpuech G., Laussy F., “Microcavities, 2Nd Edition”, Microcavities, 2Nd Edition, Series on Semiconductor Science and Technology, 21, Oxford Univ Press, 2017, 1–592  crossref  isi
    24. Levin L.A., Venkatesan R., “An Average Case Np-Complete Graph Colouring Problem”, Comb. Probab. Comput., 27:5 (2018), 808–828  crossref  mathscinet  zmath  isi  scopus
    25. Sotiraki K. Zampetakis M. Zirdelis G., “Ppp-Completeness With Connections to Cryptography”, 2018 IEEE 59Th Annual Symposium on Foundations of Computer Science (Focs), Annual IEEE Symposium on Foundations of Computer Science, ed. Thorup M., IEEE Computer Soc, 2018, 148–158  crossref  mathscinet  isi  scopus
    26. Du Shi-Yu, Zhang Yi-Ming, Luo Kan, Huang Qing, “Design of the Nature-Inspired Algorithms Library and Its Significance For New Materials Research and Development”, J. Inorg. Mater., 34:1 (2019), 27–36  crossref  isi  scopus
    27. Liu Ya., Pass R., “on One-Way Functions and Kolmogorov Complexity”, 2020 IEEE 61St Annual Symposium on Foundations of Computer Science (Focs 2020), Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2020, 1243–1254  crossref  mathscinet  isi  scopus
    28. Maguire Ph., Moser Ph., Maguire R., “Are People Smarter Than Machines?”, Croat. J. Philos., 20:58 (2020), 103–123  isi
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:1330
    Full text:542
    First page:1

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021