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

ПРЕПРИНТ 12/2009


О. Ю. Меланич

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

С.-Петербургское отделение Математического института им. В. А.Стеклова РАН, Фонтанка, 27, 191023 С.-Петербург, Россия
http://logic.pdmi.ras.ru/~melanich
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