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

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

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



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Пробл. передачи информ., 2009, том 45, выпуск 2, страницы 101–118 (Mi ppi1982)  

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

Большие системы

О полных односторонних функциях

А. А. Кожевников, С. И. Николенко

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

Аннотация: Полные конструкции играют важную роль в теоретической информатике. Однако в криптографии до недавних пор полные конструкции либо отсутствовали, либо носили сугубо теоретический характер. В 2003 г. Л. А. Левин предложил идею полной односторонней функции, основанной на комбинаторных соображениях. В настоящей статье представлены две новые полные односторонние функции, основанные на полусистемах Туэ, и полная односторонняя функция, основанная на варианте задачи соответствия Поста. Также формально представлены свойства, которыми должна обладать комбинаторная задача, чтобы на ее основе можно было построить полную одностороннюю функцию. Статья содержит новое доказательство результата Левина.

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

Англоязычная версия:
Problems of Information Transmission, 2009, 45:2, 168–183

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

УДК: 621.391.1+519.4
Поступила в редакцию: 19.05.2008
После переработки: 20.01.2009

Образец цитирования: А. А. Кожевников, С. И. Николенко, “О полных односторонних функциях”, Пробл. передачи информ., 45:2 (2009), 101–118; Problems Inform. Transmission, 45:2 (2009), 168–183

Цитирование в формате AMSBIB
\RBibitem{KojNik09}
\by А.~А.~Кожевников, С.~И.~Николенко
\paper О полных односторонних функциях
\jour Пробл. передачи информ.
\yr 2009
\vol 45
\issue 2
\pages 101--118
\mathnet{http://mi.mathnet.ru/ppi1982}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2554711}
\zmath{https://zbmath.org/?q=an:1181.68144}
\transl
\jour Problems Inform. Transmission
\yr 2009
\vol 45
\issue 2
\pages 168--183
\crossref{https://doi.org/10.1134/S0032946009020082}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000268246600008}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-67749127886}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ppi1982
  • http://mi.mathnet.ru/rus/ppi/v45/i2/p101

    ОТПРАВИТЬ: 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. А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 65–87  mathnet  mathscinet; 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  crossref
    2. С. Ю. Ерофеев, В. А. Романьков, “О построении возможно односторонних функций на основе алгоритмической неразрешимости проблемы эндоморфной сводимости в группах”, ПДМ, 2012, № 3(17), 13–24  mathnet
    3. С. И. Николенко, Д. С. Тугарёв, “Полная односторонняя функция, основанная на свободном $\mathbb Z\times\mathbb Z$-модуле конечного ранга”, Комбинаторика и теория графов. IV, Первый Российско-финский симпозиум по дискретной математике (специальный выпуск), Зап. научн. сем. ПОМИ, 402, ПОМИ, СПб., 2012, 91–107  mathnet  mathscinet; 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  crossref
    4. Ерофеев С.Ю., Романьков В.А., “О возможности построения односторонних функций на основе неразрешимости проблемы эндоморфной сводимости в группах”, Вестник омского университета, 2012, № 2, 53–56  mathscinet  elib
    5. 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
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:288
    Полный текст:69
    Литература:29
    Первая стр.:12
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020