In 1992, A. Hiltgen [1] 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 by a constant factor only (with the factor approaching 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 every honest participant by a constant factor of 25/22.
Original language | English |
---|---|
Title of host publication | Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings |
Pages | 129-142 |
Number of pages | 14 |
DOIs | |
State | Published - 29 Oct 2009 |
Externally published | Yes |
Event | 4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Russian Federation Duration: 18 Aug 2009 → 23 Aug 2009 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 5675 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 4th International Computer Science Symposium in Russia, CSR 2009 |
---|---|
Country/Territory | Russian Federation |
City | Novosibirsk |
Period | 18/08/09 → 23/08/09 |
ID: 49827838