|
Записки научных семинаров ПОМИ, 2012, том 399, страницы 32–64
(Mi znsl5220)
|
|
|
|
Feebly secure cryptographic primitives
[Крипотографические примитивы, доказуемо надёжные в слабом смысле]
E. A. Hirsch, O. Melanich, S. I. Nikolenko St. Petersburg Department of the Steklov Mathematical
Institute, St. Petersburg, Russia
Аннотация:
В 1992 г. А. Хильтген построил первые конструкции доказуемо (слабо) надёжных криптографических примитивов, а именно односторонних функций. Эти функции доказуемо сложнее обратить, чем вычислить, но сложность (схемная сложность в базисе из произвольных бинарных гейтов) увеличивается лишь в константное число раз (в конструкциях Хильтгена этот показатель приближается к $2$). В традиционной криптографии, односторонние функции являются основными примитивами для схем с секретным ключом, а схемы с открытым ключом конструируются на основе функций с секретом. Мы развиваем идеи работ Хильтгена и строим примеры функций с секретом, доказуемо надёжных в слабом смысле, в которых схема противника гарантированно больше, чем схемы честных участников (тоже в константное число раз). Мы строим примеры как (более простых) линейных, так и (более надёжных) нелинейных конструкций. Библ. – 25 назв.
Ключевые слова:
надёжность в слабом смысле, схемная сложность, теоретическая криптография.
Поступило: 15.01.2012
Образец цитирования:
E. A. Hirsch, O. Melanich, S. I. Nikolenko, “Feebly secure cryptographic primitives”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 32–64; J. Math. Sci. (N. Y.), 188:1 (2013), 17–34
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5220 https://www.mathnet.ru/rus/znsl/v399/p32
|
Статистика просмотров: |
Страница аннотации: | 555 | PDF полного текста: | 36 | Список литературы: | 35 |
|