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

ПРЕПРИНТ 16/2008

НАДЕЖНАЯ В СЛАБОМ СМЫСЛЕ ФУНКЦИЯ С СЕКРЕТОМ

 АННОТАЦИЯ:
 В 1992 году А. Хильтген построил первые конструкции доказуемо
 надежных криптографических примитивов, а именно функций, односторонних в слабом
смысле.
 Такие функции доказуемо сложнее обратить, чем вычислить, но сложность при этом
 (рассматриваемая как схемная сложность над схемами с произвольными бинарными гейтами)
 увеличивается лишь в константное число раз (в работах Хильтгена эта константа
приближается к 2).

 В классической криптографии односторонние функции являются базовыми примитивами
для протоколов
 согласования ключа и цифровой подписи, в то время как криптосистемы с открытым
ключом конструируются
 на базе функций с секретом. Мы продолжаем исследования Хильтгена и строим надежную
в слабом смысле
 функцию с секретом; в нашей конструкции противник гарантированно потратит больше
времени на обращение
 функции, чем честные участники протокола (также в константное число раз).

E.  Hirsch, S. Nikolenko. A  FEEBLY SECURE TRAPDOOR FUNCTION


 In 1992, A. Hiltgen provided the first constructions of provably
 (slightly) secure cryptographic primitives, namely \emph{feebly one-way functions}.
 These functions are provably harder to invert than to compute,
 but the complexity (viewed as circuit complexity over circuits
 with arbitrary binary gates) is amplified only by a constant factor
 (in Hiltgen's works, the factor approaches 2).

 In traditional cryptography,
 one-way functions are the basic primitive of private-key and digital signature
schemes,
 while public-key cryptosystems are constructed with trapdoor functions.
 We continue Hiltgen's work by providing an example
 of a feebly   trapdoor function where the adversary is guaranteed to spend more time
 than the honest participants (also by a constant factor).