|
This article is cited in 8 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.
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:
-
А. А. Семенов, “О сложности обращения дискретных функций
из одного класса”, Дискретн. анализ и исслед. опер., 11:4 (2004), 44–55
 -
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
 -
Aaronson S., “The learnability of quantum states”, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 463:2088 (2007), 3089–3114
 -
Д. Ю. Григорьев, А. Кожевников, С. И. Николенко, “Алгебраическая криптография: новые конструкции и их надëжность относительно
доказуемого взлома”, Алгебра и анализ, 20:6 (2008), 119–147 ; 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
-
Dowe D.L., “Foreword re C. S. Wallace”, Computer Journal, 51:5 (2008), 523-560
-
Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 21:3 (2009), 130–144
-
А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118 ; A. A. Kozhevnikov, S. I. Nikolenko, “On complete one-way functions”, Problems Inform. Transmission, 45:2 (2009), 168–183
-
Hagar A., “Active fault-tolerant quantum error correction: the curse of the open system”, Philos. Sci., 76:4 (2009), 506–535
|
| Number of views: |
| This page: | 381 | | Full text: | 112 | | References: | 9 | | First page: | 1 |
|
Terms of Use