O. Goldreich
L. A. Levin
ABSTRACT
A central tool in constructing pseudorandom generators, secure encryption functions, and in other areas are “hard-core” predicates b of functions (permutations) ƒ, discovered in [Blum Micali 82]. Such b(x) cannot be efficiently guessed (substantially better than 50-50) given only ƒ(x). Both b, ƒ are computable in polynomial time.
[Yao 82] transforms any one-way function ƒ into a more complicated one, ƒ*, which has a hard-core predicate. The construction applies the original ƒ to many small pieces of the input to ƒ* just to get one “hard-core” bit. The security of this bit may be smaller than any constant positive power of the security of ƒ. In fact, for inputs (to ƒ*) of practical size, the pieces effected by ƒ are so small that ƒ can be inverted (and the “hard-core” bit computed) by exhaustive search.
In this paper we show that every one-way function, padded to the form ƒ(p, x) = (p, g(x)), ‖‖p‖‖ = ‖x‖, has by itself a hard-core predicate of the same (within a polynomial) security. Namely, we prove a conjecture of [Levin 87, sec. 5.6.2] that the scalar product of Boolean vectors p, x is a hard-core of every one-way function ƒ(p, x) = (p, g(x)). The result extends to multiple (up to the logarithm of security) such bits and to any distribution on the x's for which ƒ is hard to invert.
- 1.W. Alexi, B. Chor, O. Goldreich and C.P. Schnorr, RSA and Rabin Functions- Certain Parts Are As Hard As the Whole, SIAM J. Comput., 17'194- 209, 1988; also FOCS~ 1984. Google Scholar
Digital Library
- 2.L. Blum, M. Blum and M. Shub, A Simple Secure Unpredictable Pseudo- Random Number Generator, SIAM J. Comput., 15'364-383, 1986. Google ScholarDigital Library
- 3.M. Blum and S. Micali, "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits," SIAM J. Comput., 13'850-864, 1984; ~lso FOGS, 1982. Google ScholarDigital Library
- 4.W. Diffie, and M.E. Hellman, "New Directions in Cryptography," iEEE trans. on Info. Theory, IT-22'644-654, 1976.Google Scholar
- 5.P.Elias, Personal communication with L.Levin, 1985. Also in "Error-correcting Codes for List Decoding," 1989, Technical Memo TM-381, Laboratory for Computer Science, MIT.Google Scholar
- 6.O. Goldreich, S. Goldwasser, and S. Miali, "How to Construct Random Functions,'' J. of A CM, 33(4)'792-807, 1986. Google ScholarDigital Library
- 7.O. Goldreich, H. Krawcyzk, and M. Luby, "On the Existence of Pseudorandom Generators~" Proc. FOG'S, 1988~ pp. 12-24.Google Scholar
- 8.S. Goldwasser and S. MicMi, "Probbilistic Encryption," JC$S, 28(2)'270- 299~ 1984; also STOC, 1982.Google Scholar
- 9.B.S. KMiski, Jr., "Elliptic Curves and Cryptography' A Pseudorandom Bit Generator and Other Tools" PhD Diss, LCS, MIT, 1988.Google Scholar
- 10.A.N. Kolmogorov, Three Approaches to the Concept of the Amount of Information, Probl. Inf. Tvansm., 1(1), 1965.Google Scholar
- 11.A.N. Kolmogorov and V.A. Uspenskii, Algorithms and Randomness, Teoriya Veroyatnostey iee Primeneniya (= Theory of Probability and its Applications), 32(3)'389-412, 1987.Google Scholar
- 12.L.A. Levin, "One-Way Function and Pseudorandom Generators," Combinatorica, 7(4):357-363, 1987. Also STOC 1985. Google ScholarDigital Library
- 13.L. A. Levin, "Homogeneous Measures and Polynomial Time Invariants," Proc. FOGS, 1988, pp. 36-41.Google Scholar
- 14.D.L. Long and A. Wigderson, "How Discreet is Discrete Log?," Proc. STOC, 1983, pp. 413-420. Google ScholarDigital Library
- 15.M. Luby and C. Rackoff, "How to Construct Pseudorandom Permutations From Pseudorandom Functions," SiAM J. Comput., 17-373-386, 1988. Google ScholarDigital Library
- 16.M.O. Rabin, "Digitalized Signatures and Public Key Functions as Intractable as Factoring, "MIT/LCS/TR-212 1979. Google ScholarDigital Library
- 17.A. Renyi, Probability Theory, North Holland Publ. Co., 1970.Google Scholar
- 18.R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems," Comm. ACM, 21'120-126, 1978. Google ScholarDigital Library
- 19.A. Shamir, ~On the Generation of Cryptographically Strong Pseudorandom Sequences,'' A UJli Trans. on Corap. Sys., 1(1):38-44, 1983. Google ScholarDigital Library
- 20.U. V. Vazirani, "Efficiency Considerations in Using Semi-random Sources," Proc. A CM Syrup. on Theory of Computing, 1987, pp. 160-168. Google ScholarDigital Library
- 21.U.V. Vazirani, and V.V. Vazirani, "Efficient and Secure Pseudo-Random Number Generations' Proc. IEEE Syrup. on Foundations of Computer Science, 1984, pp. 458-463.Google Scholar
- 22.A.C. Yao, "Theory and Applications of Trapdoor Functions," Proc. of IEEE Syrup. on Foundations of Computer Science, 1982, pp. 80-91.Google Scholar
Index Terms
- A hard-core predicate for all one-way functions
Recommendations
Non-adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions
Advances in Cryptology – EUROCRYPT 2023AbstractIn this work we give the first non-adaptive construction of universal one-way hash functions (UOWHFs) from arbitrary one-way functions. Our construction uses calls to the one-way function, has a key of length , and can be implemented ...
On basing one-way functions on NP-hardness
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingWe consider the possibility of basing one-way functions on NP-Hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a polynomial-time computable function f. Our main findings are the ...
Pseudorandom generators from one-way functions: a simple construction for any hardness
TCC'06: Proceedings of the Third conference on Theory of CryptographyIn a seminal paper, Håstad, Impagliazzo, Levin, and Luby showed that pseudorandom generators exist if and only if one-way functions exist. The construction they propose to obtain a pseudorandom generator from an n-bit one-way function uses $\mathcal{O}(...
Comments