|
Записки научных семинаров ПОМИ, 2012, том 399, страницы 65–87
(Mi znsl5221)
|
|
|
|
Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле
А. П. Давыдовa, С. И. Николенкоb a СПбАУ НОЦНТ РАН, Санкт-Петербург, Россия
b Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия
Аннотация:
Работа посвящена исследованиям в области схемной сложности в контексте доказуемо надёжных криптографических конструкций. Основываясь на идеях доказуемо надёжных функций с секретом, ранее разработанных в (Hirsch, Nikolenko, 2009; Melanich, 2009), мы представляем новую линейную конструкцию доказуемо надёжной функции с секретом, имеющую порядок надёжности $5/4$, а также проводим подробный общий анализ метода исключения гейтов (gate elimination) для случая линейных функций. В работе также приводится неконструктивное доказательство нелинейных нижних оценок схемной сложности на линейные булевы функции и верхние оценки на реализацию линейных булевых функций схемами с уточнёнными константами. Библ. – 53 назв.
Ключевые слова:
надёжность в слабом смысле, схемная сложность, функции с секретом, доказуемая надёжность.
Поступило: 31.01.2012
Образец цитирования:
А. П. Давыдов, С. И. Николенко, “Схемная сложность линейных функций: метод исключения гейтов и надежность в слабом смысле”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 65–87; J. Math. Sci. (N. Y.), 188:1 (2013), 35–46
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5221 https://www.mathnet.ru/rus/znsl/v399/p65
|
Статистика просмотров: |
Страница аннотации: | 672 | PDF полного текста: | 77 | Список литературы: | 52 |
|