A hard-core predicate for all one-way functions
Published 1 January 1989
Oded Goldreich, Leonid A. Levin
Citations1,196
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper proves a conjecture of [Levin 87, sec. 5.6.2] that the scalar product of Boolean vectors p, g, x is a hard-core of every one-way function ƒ, and extends to multiple (up to the logarithm of security) such bits and to any distribution on the x.
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.
Keywords
Computer Science
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,142 Citations1983Ronald L. Rivest, Adi Shamir +1 more
Journal of the ACMHow to construct random functions
2,111 Citations1986Oded Goldreich, Shafi Goldwasser +1 more
A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented that has applications in cryptography, random constructions, and complexity theory.
SIAM Journal on ComputingHow to Generate Cryptographically Strong Sequences of Pseudorandom Bits
1,323 Citations1984Manuel Blum, Silvio Micali
SIAM Journal on ComputingA Simple Unpredictable Pseudo-Random Number Generator
1,036 Citations1986Lenore Blum, Manuel Blum +1 more
Two closely-related pseudo-random sequence generators are presented: the ${1 / P} generator, with input P a prime, and the $x^2 \bmod N$generator, which outputs the quotient digits obtained on dividing 1 by P.
DSpace@MIT (Massachusetts Institute of Technology)DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION
1,024 Citations1979M. O. Rabin
It is proved that for any given n, if the authors can invert the function y = E (x1) for even a small percentage of the values y then they can factor n, which seems to be the first proved result of this kind.
SIAM Journal on ComputingHow to Construct Pseudorandom Permutations from Pseudorandom Functions
935 Citations1988Michael Luby, Charles Rackoff
SIAM Journal on ComputingRSA and Rabin Functions: Certain Parts are as Hard as the Whole
340 Citations1988Werner Alexi, Benny Chor +2 more
The RSA and Rabin encryption functions are computationally equivalent, which implies that an adversary, given the RSA/Rabin ciphertext, cannot have a non-negligible advantage in guessing the least-significant bit of the plaintext, unless he can invert RSA/factor N.
ACM Transactions on Computer SystemsOn the generation of cryptographically strong pseudorandom sequences
266 Citations1983Adi Shamir
This paper shows how to generate from a short random seed S a long sequence of pseudo-random numbers Ri in which the problem of computing one more Ri value given an arbitrarily large subset of the other values is provably equivalent to the cryptanalysis of the associated Rivest-Shamir-Adleman encryption function.
COMBINATORICAOne way functions and pseudorandom generators
261 Citations1987Leonid A. Levin
A weaker assumption about one-way functions is proposed, which is not only sufficient, but also necessary for the existence of pseudorandom generators.
IEEE Transactions on Information TheoryError-correcting codes for list decoding
190 Citations1991Peter Eliaš
The authors show that a jammer who can change a fixed fraction p > indicates that the maximum rate of (n,e,L) codes, which correct all sets of e or fewer errors in a block of n bits under list-of-L decoding, is limited.
Efficient And Secure Pseudo-Random Number Generation
84 Citations2005Umesh Vazirani, Vijay V. Vazirani
The security of the x/sup 2/ mod N generator, which being a Trapdoor Generator, has several applications, is strengthened by proving it as hard as Factoring.
On the existence of pseudorandom generators
63 Citations1988Oded Goldreich, Hugo Krawczyk +1 more
It is shown that if aRegular functions in which every image of a k-bit string has the same number of preimages of length k are considered, then pseudorandom generators do exist, and assuming the intractability of general factoring, it can be proved that they do exist.
Efficiency considerations in using semi-random sources
55 Citations1987Umesh Vazirani
Randomness is an important computational resource, and has found application in such diverse computational tasks as combinatorial algorithms, synchronization and deadlock resolution protocols, encrypting data and cryptographic protocols, and so on.
DSpace@MIT (Massachusetts Institute of Technology)Elliptic curves and cryptography : a pseudorandom bit generator and other tools
33 Citations1988Burton S. Kaliski
How discreet is the discrete log?
19 Citations1983Douglas L. Long, Avi Wigderson
This paper shows how to hide c•loglog p bits for any constant c, where p is the modulus, using the discrete logarithm function.
Homogeneous measures and polynomial time invariants
12 Citations1988Leonid A. Levin
The formalization of this statement is given and shown to distinguish a class of homogeneous probability measures suggesting various applications that could explain why the average case NP-completeness results are so measure-independent and could lead to their generalization to this wider and more invariant class of measures.