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

Том 399, стр. 32-64

Э. А. Гирш, О. Ю. Меланич, Николенко С. И.

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

hirsch@pdmi.ras.ru, tushkanchik239@mail.ru, sergey@logic.pdmi.ras.ru

Аннотация:В 1992 г. А. Хильтген построил первые конструкции доказуемо (слабо) надёжных криптографических примитивов, а именно односторонних функций. Эти функции доказуемо сложнее обратить, чем вычислить, но сложность (схемная сложность в базисе из произвольных бинарных гейтов) увеличивается лишь в константное число раз (в конструкциях Хильтгена этот показатель приближается к 2). В традиционной криптографии, односторонние функции являются основными примитивами для схем с секретным ключом, а схемы с открытым ключом конструируются на основе функций с секретом. Мы развиваем идеи работ Хильтгена и строим примеры функций с секретом, доказуемо надёжных в слабом смысле, в которых схема противника гарантированно больше, чем схемы честных участников (тоже в константное число раз). Мы строим примеры как (более простых) линейных, так и (более надёжных) нелинейных конструкций. Библ. -- 25 назв.
Ключевые слова: надёжность в слабом смысле, схемная сложность, теоретическая криптография [Feeble security, circuit complexity, trapdoor functions, provable security]

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