Abstract

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 languageEnglish
Title of host publicationComputer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings
Pages129-142
Number of pages14
DOIs
Publication statusPublished - 29 Oct 2009
Event4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk
Duration: 18 Aug 200923 Aug 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5675 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Computer Science Symposium in Russia, CSR 2009
CountryRussian Federation
CityNovosibirsk
Period18/08/0923/08/09

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A feebly secure trapdoor function'. Together they form a unique fingerprint.

  • Cite this

    Hirsch, E. A., & Nikolenko, S. I. (2009). A feebly secure trapdoor function. In Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings (pp. 129-142). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5675 LNCS). https://doi.org/10.1007/978-3-642-03351-3_14