Article

Free access

A hard-core predicate for all one-way functions

Authors:

L. A. LevinAuthors Info & Claims

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

Pages 25 - 32

https://doi.org/10.1145/73007.73010

Published: 01 February 1989 Publication History

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

[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.

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.

Digital 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.

Digital Library

[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]

O. Goldreich, S. Goldwasser, and S. Miali, "How to Construct Random Functions,'' J. of A CM, 33(4)'792-807, 1986.

Digital Library

[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]

L.A. Levin, "One-Way Function and Pseudorandom Generators," Combinatorica, 7(4):357-363, 1987. Also STOC 1985.

Digital Library

[13]

L. A. Levin, "Homogeneous Measures and Polynomial Time Invariants," Proc. FOGS, 1988, pp. 36-41.

[14]

D.L. Long and A. Wigderson, "How Discreet is Discrete Log?," Proc. STOC, 1983, pp. 413-420.

Digital Library

[15]

M. Luby and C. Rackoff, "How to Construct Pseudorandom Permutations From Pseudorandom Functions," SiAM J. Comput., 17-373-386, 1988.

Digital Library

[16]

M.O. Rabin, "Digitalized Signatures and Public Key Functions as Intractable as Factoring, "MIT/LCS/TR-212 1979.

Digital Library

[17]

A. Renyi, Probability Theory, North Holland Publ. Co., 1970.

[18]

R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public Key Cryptosystems," Comm. ACM, 21'120-126, 1978.

Digital Library

[19]

A. Shamir, ~On the Generation of Cryptographically Strong Pseudorandom Sequences,'' A UJli Trans. on Corap. Sys., 1(1):38-44, 1983.

Digital Library

[20]

U. V. Vazirani, "Efficiency Considerations in Using Semi-random Sources," Proc. A CM Syrup. on Theory of Computing, 1987, pp. 160-168.

Digital 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.

[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

Lee K(2024)Bit Security as Cost to Demonstrate AdvantageIACR Communications in Cryptology10.62056/an5txol7Online publication date: 9-Apr-2024
https://doi.org/10.62056/an5txol7
Bruhns IBerndt SSander JEisenbarth T(2024)Slalom at the Carnival: Privacy-preserving Inference with Masks from Public KnowledgeIACR Communications in Cryptology10.62056/akp-49qgxqOnline publication date: 7-Oct-2024
https://doi.org/10.62056/akp-49qgxq
Bock EBrzuska CLai R(2024)Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom GeneratorsIACR Communications in Cryptology10.62056/aevur-10kOnline publication date: 8-Jul-2024
https://doi.org/10.62056/aevur-10k
Show More Cited By

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 2023
Abstract
In this work we give the first non-adaptive construction of universal one-way hash functions (UOWHFs) from arbitrary one-way functions. Our construction uses $O (n^{9})$ calls to the one-way function, has a key of length $O (n^{10})$ , 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 Computing
We 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 Cryptography

In 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

February 1989

600 pages

ISBN:0897913078

DOI:10.1145/73007

Editor:
D. S. Johnson

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC89

Sponsor:

SIGACT

STOC89: 21st Annual ACM Symposium on the Theory of Computing

May 14 - 17, 1989

Washington, Seattle, USA

Acceptance Rates

STOC '89 Paper Acceptance Rate 56 of 196 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

774
Total Citations
View Citations
3,498
Total Downloads

Downloads (Last 12 months)532
Downloads (Last 6 weeks)87

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee K(2024)Bit Security as Cost to Demonstrate AdvantageIACR Communications in Cryptology10.62056/an5txol7Online publication date: 9-Apr-2024
https://doi.org/10.62056/an5txol7
Bruhns IBerndt SSander JEisenbarth T(2024)Slalom at the Carnival: Privacy-preserving Inference with Masks from Public KnowledgeIACR Communications in Cryptology10.62056/akp-49qgxqOnline publication date: 7-Oct-2024
https://doi.org/10.62056/akp-49qgxq
Bock EBrzuska CLai R(2024)Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom GeneratorsIACR Communications in Cryptology10.62056/aevur-10kOnline publication date: 8-Jul-2024
https://doi.org/10.62056/aevur-10k
Xagawa K(2024)On the Efficiency of Generic, Quantum Cryptographic ConstructionsIACR Communications in Cryptology10.62056/a66c0l5vtOnline publication date: 9-Apr-2024
https://doi.org/10.62056/a66c0l5vt
Zhang HHuang TZhang FWei BDu Y(2024)Self-Bilinear Map from One Way Encoding System and i𝒪Information10.3390/info1501005415:1(54)Online publication date: 17-Jan-2024
https://doi.org/10.3390/info15010054
Liu FZheng ZGong ZTian KZhang YHu ZLi JXu Q(2024)A survey on lattice-based digital signatureCybersecurity10.1186/s42400-023-00198-17:1Online publication date: 1-Apr-2024
https://doi.org/10.1186/s42400-023-00198-1
Gur TJahanara MKhodabandeh MRajgopal NSalamatian BShinkar IMohar BShinkar IO'Donnell R(2024)On the Power of Interactive Proofs for LearningProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649784(1063-1070)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649784
Amireddy PBehera AParaashar MSrinivasan SSudan MMohar BShinkar IO'Donnell R(2024)Local Correction of Linear Functions over the Boolean CubeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649746(764-775)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649746
Khurana DTomer KMohar BShinkar IO'Donnell R(2024)Commitments from Quantum One-WaynessProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649654(968-978)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649654
Chen YLi JMohar BShinkar IO'Donnell R(2024)Hardness of Range Avoidance and Remote Point for Restricted Circuits via CryptographyProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649602(620-629)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649602
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents