Remote Access 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
DOI: https://doi.org/10.1090/S1061-0022-10-01103-9
Published electronically: February 26, 2010
MathSciNet review: 2588765
Full-text PDF Free Access

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?)

  • 1. Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby, On the theory of average case complexity, J. Comput. System Sci. 44 (1992), no. 2, 193-219; https://doi.org/10.1016/0022-0000(92)90019-F. MR 1160461 (93d:68020)
  • 2. A. Bogdanov and L. Trevisan, Average-case complexity, Found. Trends Theor. Comput. Sci. 2 (2006), no. 1, 1-106. MR 2453146
  • 3. O. Goldreich, Foundations of cryptography. Basic tools, Cambridge Univ. Press, Cambridge, 2001. MR 1881185 (2004a:94042)
  • 4. R. Impagliazzo, A personal view of average-case complexity, 10th Annual Conference. Structure in Complexity Theory (SCT'95) (Minneapolis, Minnesota, 1995), IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, pp. 134-147.
  • 5. R. Impagliazzo and L. Levin, No better ways to generate hard NP instances than picking uniformly at random, 31st Annual Symposium on Foundations of Computer Science, Vol. II (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 812-821.
  • 6. L. Levin, Average case complete problems, SIAM J. Comput. 15 (1986), no. 1, 285-286. MR 0822205 (87b:68053)
  • 7. -, One-way functions, Probl. Peredachi Inf. 39 (2003), no. 1, 103-117; English transl., Probl. Inf. Transm. 39 (2003), no. 1, 92-103. DOI 10.1023/A:1023634616182. MR 2101668 (2005g:94080)

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: https://doi.org/10.1090/S1061-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

American Mathematical Society