|
Warning: The download time has expired please click on the item to try again.
 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.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
|
| |
3
|
|
| |
4
|
W. Diffie, and M.E. Hellman, "New Directions in Cryptography," iEEE trans. on Info. Theory, IT-22'644-654, 1976.
|
| |
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.
|
 |
6
|
|
| |
7
|
O. Goldreich, H. Krawcyzk, and M. Luby, "On the Existence of Pseudorandom Generators~" Proc. FOG'S, 1988~ pp. 12-24.
|
| |
8
|
S. Goldwasser and S. MicMi, "Probbilistic Encryption," JC$S, 28(2)'270- 299~ 1984; also STOC, 1982.
|
| |
9
|
B.S. KMiski, Jr., "Elliptic Curves and Cryptography' A Pseudorandom Bit Generator and Other Tools" PhD Diss, LCS, MIT, 1988.
|
| |
10
|
A.N. Kolmogorov, Three Approaches to the Concept of the Amount of Information, Probl. Inf. Tvansm., 1(1), 1965.
|
| |
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.
|
| |
12
|
|
| |
13
|
L. A. Levin, "Homogeneous Measures and Polynomial Time Invariants," Proc. FOGS, 1988, pp. 36-41.
|
| |
14
|
|
| |
15
|
|
| |
16
|
|
| |
17
|
A. Renyi, Probability Theory, North Holland Publ. Co., 1970.
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
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.
|
| |
22
|
A.C. Yao, "Theory and Applications of Trapdoor Functions," Proc. of IEEE Syrup. on Foundations of Computer Science, 1982, pp. 80-91.
|
CITED BY 87
|
|
Nader H. Bshouty , Jeffrey C. Jackson , Christino Tamon, More efficient PAC-learning of DNF with membership queries under the uniform distribution, Proceedings of the twelfth annual conference on Computational learning theory, p.286-295, July 07-09, 1999, Santa Cruz, California, United States
|
|
|
|
|
|
|
|
|
William Aiello , Sivaramakrishnan Rajagopalan , Ramarathnam Venkatesan, Design of practical and provably good random number generators, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.1-9, January 22-24, 1995, San Francisco, California, United States
|
|
|
|
|
|
Moni Naor , Omer Reingold , Alon Rosen, Pseudo-random functions and factoring (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.11-20, May 21-23, 2000, Portland, Oregon, United States
|
|
|
|
|
|
|
|
|
|
|
|
Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States
|
|
|
|
|
|
Ran Canetti , Oded Goldreich , Shafi Goldwasser , Silvio Micali, Resettable zero-knowledge (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.235-244, May 21-23, 2000, Portland, Oregon, United States
|
|
|
Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States
|
|
|
Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jin-Yi Cai , Ajay Nerurkar , D. Sivakumar, Hardness and hierarchy theorems for probabilistic quasi-polynomial time, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.726-735, May 01-04, 1999, Atlanta, Georgia, United States
|
|
|
Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ran Canetti , Daniele Micciancio , Omer Reingold, Perfectly one-way probabilistic hash functions (preliminary version), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.131-140, May 24-26, 1998, Dallas, Texas, United States
|
|
|
R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States
|
|
|
Danny Harnik , Moni Naor , Omer Reingold , Alon Rosen, Completeness in two-party secure computation: a computational view, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Irit Dinur , Elena Grigorescu , Swastik Kopparty , Madhu Sudan, Decodability of group homomorphisms beyond the johnson bound, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Peter Honeyman , Andy Adamson , Kevin Coffman , Janani Janakiraman , Rob Jerdonek , Jim Rees, Secure videoconferencing, Proceedings of the 7th conference on USENIX Security Symposium, 1998, p.9-9, January 26-29, 1998, San Antonio, Texas
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Russell Impagliazzo , Ragesh Jaiswal , Valentine Kabanets , Avi Wigderson, Uniform direct product theorems: simplified, optimized, and derandomized, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Côme Berbain , Olivier Billet , Jonathan Etrog , Henri Gilbert, An efficient forward private RFID protocol, Proceedings of the 16th ACM conference on Computer and communications security, November 09-13, 2009, Chicago, Illinois, USA
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.4