A FEEBLY TRAPDOOR FUNCTION
Edward Alekseevich Hirsch, Sergey Nikolenko · 2008
In 1992, A. Hiltgen [Hil92] provided the first constructions of provably (slightly) secure cryptographic primitives, namely 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).