An infinitely-often one-way function based on an average-case assumption
HTML articles powered by AMS MathViewer
- by
E. A. Hirsch and D. M. Itsykson
Translated by: the authors - St. Petersburg Math. J. 21 (2010), 459-468
- DOI: https://doi.org/10.1090/S1061-0022-10-01103-9
- Published electronically: February 26, 2010
- PDF | Request permission
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
- Shai Ben-David, Benny Chor, Oded Goldreich, and Michel Luby, On the theory of average case complexity, J. Comput. System Sci. 44 (1992), no. 2, 193–219. MR 1160461, DOI 10.1016/0022-0000(92)90019-F
- Andrej Bogdanov and Luca Trevisan, Average-case complexity, Found. Trends Theor. Comput. Sci. 2 (2006), no. 1, 1–106. MR 2453146, DOI 10.1561/0400000004
- Oded Goldreich, Foundations of cryptography, Cambridge University Press, Cambridge, 2001. Basic tools. MR 1881185, DOI 10.1017/CBO9780511546891
- 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.
- 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.
- Leonid A. Levin, Average case complete problems, SIAM J. Comput. 15 (1986), no. 1, 285–286. MR 822205, DOI 10.1137/0215020
- L. A. Levin, One-way functions, Problemy Peredachi Informatsii 39 (2003), no. 1, 103–117 (Russian, with Russian summary); English transl., Probl. Inf. Transm. 39 (2003), no. 1, 92–103. MR 2101668, DOI 10.1023/A:1023634616182
Bibliographic 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
- 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.
- © Copyright 2010 American Mathematical Society
- Journal: St. Petersburg Math. J. 21 (2010), 459-468
- MSC (2000): Primary 68Q15
- DOI: https://doi.org/10.1090/S1061-0022-10-01103-9
- MathSciNet review: 2588765