On constructing 1-1 one-way functions. (English) Zbl 1343.94056
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 13-25 (2011).
Summary: We show how to construct length-preserving 1-1 one-way functions based on popular intractability assumptions (e.g., RSA, DLP). Such 1-1 functions should not be confused with (infinite) families of (finite) one-way permutations. What we want and obtain is a single (infinite) 1-1 one-way function.
For the entire collection see [Zbl 1220.68005].
For the entire collection see [Zbl 1220.68005].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Agrawal, M., Kayal, N., Saxena, N.: Primes is in P. Annals of Mathematics 160(2), 781–793 (2004) · Zbl 1071.11070 · doi:10.4007/annals.2004.160.781 |
| [2] | Bach, E.: Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms (ACM Distinguished Dissertation 1984). MIT Press, Cambridge (1985) |
| [3] | Bach, E.: Realistic Analysis of some Randomized Algorithms. In: 19th STOC, pp. 453–461 (1987) · doi:10.1145/28395.28444 |
| [4] | Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM J. on Computing 13, 850–864 (1984) · Zbl 0547.68046 · doi:10.1137/0213053 |
| [5] | Goldreich, O.: Foundation of Cryptography: Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016 · doi:10.1017/CBO9780511546891 |
| [6] | Goldreich, O.: Foundation of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004) · Zbl 1068.94011 · doi:10.1017/CBO9780511721656 |
| [7] | Goldreich, O., Impagliazzo, R., Levin, L., Venkatesan, R., Zuckerman, D.: Security Preserving Amplification of Hardness. In: 31st FOCS, pp. 318–326 (1990) · doi:10.1109/FSCS.1990.89550 |
| [8] | Goldreich, O., Levin, L.: A Hard-Core Predicate for any One-way Function. In: 21st STOC, pp. 25–32 (1989) |
| [9] | Goldreich, O., Krawczyk, H., Luby, M.: On the Existence of Pseudorandom Generators. SIAM J. on Computing 22, 1163–1175 (1993) · Zbl 0795.94011 · doi:10.1137/0222069 |
| [10] | Haitner, I.: Implementing Oblivious Transfer Using Collection of Dense Trapdoor Permutations. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 394–409. Springer, Heidelberg (2004) · Zbl 1197.94189 · doi:10.1007/978-3-540-24638-1_22 |
| [11] | Haitner, I., Reingold, O., Vadhan, S.: Efficiency Improvements in Constructing Pseudorandom Generator from any One-way Function. In: 42nd STOC, pp. 437–446 (2010) · Zbl 1293.65006 |
| [12] | Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. SICOMP 28(4), 1364–1396 (1990); Combines papers of Impagliazzo, Levin, and Luby ( 21st STOC, 1989) and J. Håstad (22nd STOC, 1990) · Zbl 0940.68048 · doi:10.1137/S0097539793244708 |
| [13] | Miller, G.L.: Riemann’s Hypothesis and tests for primality. JCSS 13, 300–317 (1976) · Zbl 0349.68025 |
| [14] | Naor, M., Yung, M.: Universal Hash Functions and their Cryptographic Applications. In: 21st STOC, pp. 33–43 (1989) |
| [15] | Nisan, N., Zuckerman, D.: Randomness is Linear in Space. JCSS 52(1), 43–52 (1996); Preliminary version in 25th STOC (1993) · Zbl 0846.68041 |
| [16] | Rabin, M.O.: Digitalized Signatures and Public Key Functions as Intractable as Factoring. MIT/LCS/TR-212 (1979) |
| [17] | Rabin, M.O.: Probabilistic algorithm for testing primality. Jour. of Number Theory 12, 128–138 (1980) · Zbl 0426.10006 · doi:10.1016/0022-314X(80)90084-0 |
| [18] | Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public Key Cryptosystems. CACM 21, 120–126 (1978) · Zbl 0368.94005 · doi:10.1145/359340.359342 |
| [19] | Rompel, J.: One-way Functions are Necessary and Sufficient for Secure Signatures. In: 22nd STOC, pp. 387–394 (1990) · doi:10.1145/100216.100269 |
| [20] | Solovay, R., Strassen, V.: A fast Monte-Carlo test for primality. SIAM Jour. on Computing 6, 84–85 (1977) · Zbl 0345.10002 · doi:10.1137/0206006 |
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.
