"Записки научных семинаров ПОМИ"

Том 399, стр. 65-87

А. П. Давыдов, В. О. Николаенко

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

СПбАУ НОЦНТ РАН, ул. Хлопина, д. 8, корпус 3, Санкт-Петербург 194021, Россия

adavydow@gmail.com, sergey@logic.pdmi.ras.ru

Аннотация: Работа посвящена исследованиям в области схемной сложности в контексте доказуемо надёжных криптографических конструкций. Основываясь на идеях доказуемо надёжных функций с секретом, ранее разработанных в (Hirsch, Nikolenko, 2009; Melanich, 2009), мы представляем новую линейную конструкцию доказуемо надёжной функции с секретом, имеющую порядок надёжности 5/4, а также проводим подробный общий анализ метода исключения гейтов (gate elimination) для случая линейных функций. В работе также приводится неконструктивное доказательство нелинейных нижних оценок схемной сложности на линейные булевы функции и верхние оценки на реализацию линейных булевых функций схемами с уточнёнными константами. Библ. -- 53 назв.
Ключевые слова: надёжность в слабом смысле, схемная сложность, функции с секретом, доказуемая надёжность [feeble security, circuit complexity, trapdoor functions, provable security]

Полный текст(.pdf)