Laboratory of Mathematical Logic at PDMI

Пятница, 8 февраля, комната 106. Начало в 16:45.

Докладчик: Э. Гирш.

Тема: Feebly trapdoor functions.

Abstract

(Joint work with S.Nikolenko)

One-way functions are the basic primitive of private-key cryptography. However, no provably one-way functions (the ones that can be computed more than polynomially faster than inverted) are known. A natural question is to construct a function that would be at least a little bit (provably!) harder to compute than to invert (call it feebly secure one-way function). Alain Hiltgen (1992) answered this question affirmatively by constructing a function that can be computed by n+O(1)-size circuits but can be inverted only by 2n-size circuits. However, similar constructions of other cryptographic primitives remained unknown.

Trapdoor functions are the basic primitive of public-key cryptography. In this work we construct a family of feebly secure trapdoor functions.