RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Алгебра и анализ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Алгебра и анализ, 2009, том 21, выпуск 3, страницы 130–144 (Mi aa1142)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Статьи

Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем

Э. А. Гирш, Д. М. Ицыксон

С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, г. Санкт-Петербург, Россия

Аннотация: Мы предполагаем существование вычислимой за полиномиальное время функции $f$, обратная к которой не вычислима вероятностным полиномиальным в среднем алгоритмом. Криптографическое определение односторонней функции, однако, другое: даже для слабо односторонней функции успешный противник может не уметь обращать её на полиномиальной доле входов. Несмотря на это препятствие, мы показываем, как можно построить одностороннюю на бесконечной последовательности длин входов функцию, основанную на функции $f$.

Ключевые слова: односторонняя функция, сложность в среднем случае.

Полный текст: PDF файл (262 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
St. Petersburg Mathematical Journal, 2010, 21:3, 459–468

Реферативные базы данных:

MSC: 68Q15
Поступила в редакцию: 29.05.2008

Образец цитирования: Э. А. Гирш, Д. М. Ицыксон, “Бесконечно часто односторонняя функция, основанная на предположении о сложности в среднем”, Алгебра и анализ, 21:3 (2009), 130–144; St. Petersburg Math. J., 21:3 (2010), 459–468

Цитирование в формате AMSBIB
\RBibitem{HirIts09}
\by Э.~А.~Гирш, Д.~М.~Ицыксон
\paper Бесконечно часто односторонняя функция, основанная на предположении о~сложности в~среднем
\jour Алгебра и анализ
\yr 2009
\vol 21
\issue 3
\pages 130--144
\mathnet{http://mi.mathnet.ru/aa1142}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2588765}
\zmath{https://zbmath.org/?q=an:1205.68164}
\transl
\jour St. Petersburg Math. J.
\yr 2010
\vol 21
\issue 3
\pages 459--468
\crossref{https://doi.org/10.1090/S1061-0022-10-01103-9}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000277451000005}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84861235113}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/aa1142
  • http://mi.mathnet.ru/rus/aa/v21/i3/p130

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


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

    Эта публикация цитируется в следующих статьяx:
    1. Hirsch E.A., Itsykson D., Monakhov I., Smal A., “On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography”, Theory Comput. Syst., 51:2 (2012), 179–195  crossref  mathscinet  zmath  isi  elib  scopus
  • Алгебра и анализ St. Petersburg Mathematical Journal
    Просмотров:
    Эта страница:265
    Полный текст:78
    Литература:25
    Первая стр.:24
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020