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

ПРЕПРИНТ 16/2008


Э. А. Гирш, С. И. Николенко

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

С.-Петербургское отделение Математического института им. В.А.Стеклова РАН, Фонтанка 27, 191023, С.-Петербург, Россия
hirsch@pdmi.ras.ru
sergey@logic.pdmi.ras.ru, snikolenko@gmail.ru
This preprint was accepted September 12, 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).

[Full text: Preprint in Russian (.ps.gz) Preprint in English (.ps.gz)]
Back to all preprints
Back to the Steklov Institute of Mathematics at St.Petersburg