On hardness of one-way functions. (English) Zbl 0635.68037
Summary: We investigate hardness of one-way functions (i.e., difficulty of computing inverse of one-way functions). Here, the notion of polynomial lowness [U. Schöning, J. Comput. Syst. Sci. 27, 14-28 (1983; Zbl 0515.68046)] is used to measure the difficulty of a given problem. We show that, for any one-way function f, the hardness of f is similar to the complexity of dom(f) and rang(f).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 03D60 | Computability and recursion theory on ordinals, admissible sets, etc. |
| 03F20 | Complexity of proofs |
Citations:
Zbl 0515.68046References:
| [1] | Allender, E., Invertible Functions, Ph.D. Dissertation (1985), Georgia Institute of Technology |
| [2] | Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. Comput., 1, 305-322 (1977) · Zbl 0356.68059 |
| [3] | Brassard, G., A note on the complexity of cryptography, IEEE Trans. Inform. Theory, IT-25, 232-233 (1979) · Zbl 0393.68052 |
| [4] | Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039 |
| [5] | Grollmann, J.; Selman, A., Complexity measures for public-key cryptosystems, Proc. 25th IEEE Symp. on Foundations of Computer Science, 495-503 (1984) |
| [6] | Hartmanis, J., Feasible Computations and Provable Complexity Properties (1978), SIAM: SIAM Philadelphia · Zbl 0383.68043 |
| [7] | Ko, K., On some natural complete operators, Theoret. Comput. Sci., 37, 1-30 (1985) · Zbl 0576.68033 |
| [8] | Pratt, V., Every prime has a succinct certificate, SIAM J. Comput., 4, 120-126 (1975) · Zbl 0316.68031 |
| [9] | Schöning, U., A low and high hierarchy within NP, J. Comput. System Sci., 27, 14-28 (1983) · Zbl 0515.68046 |
| [10] | Schöning, U., Complexity and Structure, Lecture Notes in Computer Science, Vol. 211 (1985), Springer: Springer Berlin |
| [11] | Schöning, U., Graph isomorphism in the low hierarchy, (Proc. 4th Symp. on Theoretical Aspects of Computer Science, Vol. 247 (1987), Springer: Springer Berlin), 114-124, Lecture Notes in Computer Science · Zbl 0621.68034 |
| [12] | Stockmeyer, L., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024 |
| [13] | Valiant, L., Relative complexity of checking and evaluating, Inform. Process. Lett., 5, 1, 20-23 (1976) · Zbl 0342.68028 |
| [14] | O. Watanabe, How hard could one-way functions be?, Math. Syst. Theory, Submitted for publication.; O. Watanabe, How hard could one-way functions be?, Math. Syst. Theory, Submitted for publication. |
| [15] | Wrathall, C., Complete sets and the polynomial-time hierarchy, Theoret. Comput. Sci., 3, 23-33 (1976) · Zbl 0366.02031 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
