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

ПРЕПРИНТ 12/2009

НЕЛИНЕЙНЫЕ НАДЕЖНЫЕ В СЛАБОМ СМЫСЛЕ КРИПТОГРАФИЧЕСКИЕ ПРИМИТИВЫ

This preprint was accepted December 18, 2009

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

  В 1992 году Ален Хильтген построил функцию, обратить которую вдвое
сложнее, чем вычислить. 
В 2009 году Э. А. Гирш и С. И. Николенко предложили конструкцию надежной
в слабом смысле функции с секретом, основанную на функции Хильтгена. Обе
вышеупомянутые конструкции линейны, что мало перспективно (сложность
взломщика не может быть более чем квадратом сложности честных участников
протокола). Автор продолжает исследования Хильтгена, Гирша и Николенко и
конструирует первые нелинейные надежные в слабом смысле криптографические
примитивы: одностороннюю в слабом смысле функцию и основанную на ней
функцию с секретом.

Ключевые слова: функции, односторонние в слабом смысле, надежные в слабом смысле функции
с секретом, схемная сложность, нижние оценки

  O. Yu. Melanich  ``NONLINEAR FEEBLY SECURE CRYPTOGRAPHIK PRIMITIVES'' 


In traditional cryptography, one-way functions are the basic primitive of private-key and
digital signature schemes and trapdoor functions serve as a basis for public-key
cryptosystems. As everybody knows, it is not proved that one or another function
(synthetically constructed or in practical use) is one-way function or trapdoor function.
However there exist constructions of feebly one-way functions and feebly secure trapdoor
functions, which are provably harder to invert then to compute, but still only by a
constant factor.

In 1992, Alain Hiltgen provided a function that is twice harder to invert then to compute.
In 2009, Edward Hirsch and Sergey Nikolenko provided a construction of a feebly secure
trapdoor function, based on Hiltgen's function. Both of above-mentioned constructions are
linear, which is not promising (the complexity of the adversary can't be greater than
squared complexity of the honest participants). The author continues investigations of
Hiltgen, Hirsch and Nikolenko and provides the first examples of nonlinear feebly secure
cryptographic primitives: a feebly one-way function and a feebly secure trapdoor function.


 Key words: feebly one-way functions, feebly secure trapdoor functions, circuit complexity,
lower bounds


[Full text:
Preprint in Russian (.pdf.gz)



Back to all preprints


Back to the Steklov
Institute of Mathematics at St.Petersburg