RUS  ENG JOURNALS   PERSONS   ORGANISATIONS   CONFERENCES   VIDEO LIBRARY   PERSONAL OFFICE   LIBRARY
General information
Latest issue
Archive
Impact factor

Search
RSS
Latest issue
Current issues
Archive issues
What is RSS



Probl. Peredachi Inf.:
Year:
Volume:
Issue:
Page:
Find



Search through the site:
Find



Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register



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

This article is cited in 8 papers


PDF version     HTML version

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.

UDC: 621.391:519.2

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

Citation in format AMSBIB:
\Bibitem{1}
\by L.~A.~Levin
\paper One-Way Functions
\jour Probl. Peredachi Inf.
\yr 2003
\vol 39
\issue 1
\pages 103--117
\mathnet{http://mi.mathnet.ru/ppi208}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2101668}
\zmath{http://www.zentralblatt-math.org/zmath/search/?an=1077.94007}
\transl
\jour Problems Inform. Transmission
\yr 2003
\vol 39
\issue 1
\pages 92--103
\crossref{http://dx.doi.org/10.1023/A:1023634616182}


Linking options:
  • http://mi.mathnet.ru/eng/ppi208
  • http://mi.mathnet.ru/eng/ppi/v39/i1/p103

    Full text (in Russian): PDF file (2362 kB)
    References (in Russian): PDF file   HTML файл

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

    Review databases:

    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. А. А. Семенов, “О сложности обращения дискретных функций из одного класса”, Дискретн. анализ и исслед. опер., 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. Д. Ю. Григорьев, А. Кожевников, С. И. Николенко, “Алгебраическая криптография: новые конструкции и их надëжность относительно доказуемого взлома”, Алгебра и анализ, 20:6 (2008), 119–147  mathnet  mathscinet; 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  crossref  isi
    5. Dowe D.L., “Foreword re C. S. Wallace”, Computer Journal, 51:5 (2008), 523-560  crossref  isi
    6. Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 21:3 (2009), 130–144  mathnet  mathscinet
    7. А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118  mathnet  mathscinet; A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183  crossref  isi
    8. Hagar A., “Active fault-tolerant quantum error correction: the curse of the open system”, Philos. Sci., 76:4 (2009), 506–535  crossref  isi
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:381
    Full text:112
    References:9
    First page:1
     
    Contact us:
     Terms of Use  Registration © Steklov Mathematical Institute RAS, 2010
    © Branch of Mathematical Sciences, Russian Academy of Sciences, 2010