DOI

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.

Язык оригиналаанглийский
Название основной публикацииComputer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings
Страницы129-142
Число страниц14
DOI
СостояниеОпубликовано - 29 окт 2009
Опубликовано для внешнего пользованияДа
Событие4th International Computer Science Symposium in Russia, CSR 2009 - Novosibirsk, Российская Федерация
Продолжительность: 18 авг 200923 авг 2009

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том5675 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция4th International Computer Science Symposium in Russia, CSR 2009
Страна/TерриторияРоссийская Федерация
ГородNovosibirsk
Период18/08/0923/08/09

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49827838