Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
St. Petersburg Mathematical Journal
St. Petersburg Mathematical Journal
ISSN 1547-7371(online) ISSN 1061-0022(print)

 

An infinitely-often one-way function based on an average-case assumption


Authors: E. A. Hirsch and D. M. Itsykson
Translated by: the authors
Original publication: Algebra i Analiz, tom 21 (2009), nomer 3.
Journal: St. Petersburg Math. J. 21 (2010), 459-468
MSC (2000): Primary 68Q15
Published electronically: February 26, 2010
MathSciNet review: 2588765
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We assume the existence of a function $ f$ that is computable in polynomial time but cannot be inverted by a randomized average-case polynomial algorithm. The cryptographic setting is, however, different: even for a weak one-way function, a successful adversary should fail on a polynomial fraction of inputs. Nevertheless, we show how to construct an infinitely-often one-way function based on $ f$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in St. Petersburg Mathematical Journal with MSC (2000): 68Q15

Retrieve articles in all journals with MSC (2000): 68Q15


Additional Information

E. A. Hirsch
Affiliation: St. Petersburg Branch, Steklov Institute of Mathematics, 27 Fontanka, St. Petersburg 191023, Russia
Email: hirsch@pdmi.ras.ru

D. M. Itsykson
Affiliation: St. Petersburg Branch, Steklov Institute of Mathematics, 27 Fontanka, St. Petersburg 191023, Russia
Email: dmitrits@pdmi.ras.ru

DOI: http://dx.doi.org/10.1090/S1061-0022-10-01103-9
PII: S 1061-0022(10)01103-9
Keywords: One-way function, average-case complexity
Received by editor(s): May 29, 2008
Published electronically: February 26, 2010
Additional Notes: Partially supported by RFBR grant 08-01-00640 and the President of Russian Federation grant for support of leading scientific schools NSh-4392.2008. The first author was also supported by the Dynasty Foundation Fellowship, and the second author was also supported by the Russian Science Support Foundation.
Article copyright: © Copyright 2010 American Mathematical Society