Number-theoretic constructions of efficient pseudo-random functions
The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
Abstract
We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that factoring (Blum integers) is hard while the other construction is pseudo-random if the decisional version of the Diffie--Hellman assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC 0 (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form " y = f s ( x )" and " y ≠ f s ( x )" given a commitment to a key s of a pseudo-random function f s .
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
Goldwasser, S., & Micali, S. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90070-9 · Cited by 2,603
How to construct random functions
Goldreich, O., Goldwasser, S., & Micali, S. (1986) · Journal of the ACM · doi:10.1145/6490.6503 · Cited by 2,115
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack
Cramer, R., & Shoup, V. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055717 · Cited by 1,437
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,322
Lower Bounds for Discrete Logarithms and Related Problems
Shoup, V. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-69053-0_18 · Cited by 1,229
A hard-core predicate for all one-way functions
Goldreich, O., & Levin, L. A. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73010 · Cited by 1,193
A Simple Unpredictable Pseudo-Random Number Generator
Blum, L., Blum, M., & Shub, M. (1986) · SIAM Journal on Computing · doi:10.1137/0215025 · Cited by 1,036
How to Construct Pseudorandom Permutations from Pseudorandom Functions
Luby, M., & Rackoff, C. (1988) · SIAM Journal on Computing · doi:10.1137/0217022 · Cited by 938
The Decision Diffie-Hellman problem
Boneh, D. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054851 · Cited by 895
Cryptographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. (1994) · Journal of the ACM · doi:10.1145/174644.174647 · Cited by 733
Chaum, D., & van Antwerpen, H. (1990) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_20 · Cited by 605
Constant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1993) · Journal of the ACM · doi:10.1145/174130.174138 · Cited by 572
Publicly Verifiable Secret Sharing
Stadler, M. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68339-9_17 · Cited by 531
Razborov, A. A., & Rudich, S. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1494 · Cited by 479
Chor, B., Fiat, A., & Naor, M. (1994) · International Cryptology Conference · Cited by 468
Self-citationPseudorandomness and Cryptographic Applications
Luby, M. (1996) · Princeton University Press eBooks · doi:10.1515/9780691206844 · Cited by 374
Towards realizing random oracles: Hash functions that hide all partial information
Canetti, R. (1997) · Lecture Notes in Computer Science · doi:10.1007/bfb0052255 · Cited by 365
Number-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646134 · Cited by 353
Self-citationHow to share a function securely
De Santis, A., Desmedt, Y., Frankel, Y., & Yung, M. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195405 · Cited by 328
Non-Interactive Oblivious Transfer and Applications
Bellare, M., & Micali, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_48 · Cited by 297
Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
Boneh, D., & Venkatesan, R. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_11 · Cited by 266
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information
Blum, M., & Goldwasser, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39568-7_23 · Cited by 262
Log Depth Circuits for Division and Related Problems
Beame, P. W., Cook, S. A., & Hoover, H. J. (1986) · SIAM Journal on Computing · doi:10.1137/0215070 · Cited by 242
Fast Exponentiation with Precomputation
Brickell, E. F., Gordon, D. M., McCurley, K. S., & Wilson, D. B. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47555-9_18 · Cited by 236
Proceedings on Advances in cryptology---CRYPTO '86
Odlyzko, A. M. (1987) · Cited by 215
Oblivious Transfer with Adaptive Queries
Naor, M., & Pinkas, B. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48405-1_36 · Cited by 214
Self-citationDistributed Pseudo-random Functions and KDCs
Naor, M., Pinkas, B., & Reingold, O. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_23 · Cited by 209
Self-citationChecking the correctness of memories
Blum, M., Evans, W., Gemmell, P., Kannan, S., & Naor, M. (1994) · Algorithmica · doi:10.1007/bf01185212 · Cited by 201
Self-citationWhen won't membership queries help?
Angluin, D., & Kharitonov, M. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103420 · Cited by 190
A key distribution system equivalent to factoring
McCurley, K. S. (1988) · Journal of Cryptology · doi:10.1007/bf02351718 · Cited by 176
Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms
Maurer, U. M. (1994) · Lecture notes in computer science · Cited by 174
Synthesizers and Their Application to the Parallel Construction of Pseudo-Random Functions
Naor, M., & Reingold, O. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1618 · Cited by 168
Self-citationAlgorithms for Black-Box Fields and their Application to Cryptography
Boneh, D., & Lipton, R. J. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_22 · Cited by 167
The Relationship Between Breaking the Diffie--Hellman Protocol and Computing Discrete Logarithms
Maurer, U. M., & Wolf, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539796302749 · Cited by 154
Separating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups.
Joux, A., & Nguyen, K. T. (2001) · Cited by 143
Two Remarks Concerning the Goldwasser-Micali-Rivest Signature Scheme
Goldreich, O. (2007) · Springer eBooks · doi:10.1007/3-540-47721-7_8 · Cited by 129
On Threshold Circuits and Polynomial Computation
Reif, J. H., & Tate, S. R. (1992) · SIAM Journal on Computing · doi:10.1137/0221053 · Cited by 102
Depth efficient neural networks for division and related problems
Siu, K.-Y. S., Bruck, J., Kailath, T., & Hofmeister, T. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.256501 · Cited by 99
When Won′t Membership Queries Help?
Angluin, D., & Kharitonov, M. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1026 · Cited by 97
Joint Encryption and Message-Efficient Secure Computation
Franklin, M., & Haber, S. (1996) · Journal of Cryptology · doi:10.1007/bf00189261 · Cited by 83
On Threshold Circuits and Polynomial Computation
Reif, J. H. (1987) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/psct.1987.10319260 · Cited by 56
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
Applebaum, B., Cash, D., Peikert, C., & Sahai, A. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-03356-8_35 · Cited by 562
Public-Key Encryption in a Multi-user Setting: Security Proofs and Improvements
Bellare, M., Boldyreva, A., & Micali, S. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45539-6_18 · Cited by 519
A Decade of Lattice Cryptography
Peikert, C. (2016) · Foundations and TrendsŴ in Theoretical Computer Science · doi:10.1561/0400000074 · Cited by 504
Pseudorandom Functions and Lattices
Banerjee, A., Peikert, C., & Rosen, A. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_42 · Cited by 459
Camenisch, J., Hohenberger, S., & Lysyanskaya, A. (2005) · Lecture Notes in Computer Science · doi:10.1007/11426639_18 · Cited by 431
Metadata
- Authors
- Naor, M., & Reingold, O.
- Venue
- Journal of the ACM
- Published
- 2004-03
- Volume
- 51
- Issue
- 2
- Pages
- 231-262
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2124218043
- Cited by
- 368
- References
- 49
- FWCI
- 9.49
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.