|
Алгебра и анализ, 2009, том 21, выпуск 3, страницы 130–144
(Mi aa1142)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Статьи
Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем
Э. А. Гирш, Д. М. Ицыксон С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, г. Санкт-Петербург, Россия
Аннотация:
Мы предполагаем существование вычислимой за полиномиальное время функции $f$, обратная к которой не вычислима вероятностным полиномиальным в среднем алгоритмом. Криптографическое определение односторонней функции, однако, другое: даже для слабо односторонней функции успешный противник может не уметь обращать её на полиномиальной доле входов. Несмотря на это препятствие, мы показываем, как можно построить одностороннюю на бесконечной последовательности длин входов функцию, основанную на функции $f$.
Ключевые слова:
односторонняя функция, сложность в среднем случае.
Поступила в редакцию: 29.05.2008
Образец цитирования:
Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 21:3 (2009), 130–144; St. Petersburg Math. J., 21:3 (2010), 459–468
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/aa1142 https://www.mathnet.ru/rus/aa/v21/i3/p130
|
Статистика просмотров: |
Страница аннотации: | 362 | PDF полного текста: | 120 | Список литературы: | 43 | Первая страница: | 24 |
|