The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Number-theoretic constructions of efficient pseudo-random functions
Abstract
We describe efficient constructions for various cryptographic primitives (both in private-key and in public-key cryptography). We show these constructions to be at least as secure as the decisional version of the Diffie-Hellman assumption or as the assumption that factoring is hard. Our major result is a new construction of pseudo-random functions such that computing their value at any given point involves two multiple products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in TC/sup 0/ (the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates) which has several interesting applications. The simple algebraic structure of the functions implies additional features. In particular, we show a zero-knowledge proof for statements of the form "y=f/sub s/(x)" and "y/spl ne/f(x)" given a commitment to a key s of a pseudo-random function f/sub 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
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 · cited 1×
“The most obvious application of the DDH-Assumption is to the Dif.e Hellman key-exchange protocol and to the related public-key cryptosystem [El Gamal 1985].”
MethodValiant, 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
Cited by
Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles
Boneh, D., & Boyen, X. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_14 · Cited by 1,766
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
On the (Im)possibility of Obfuscating Programs
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., & Yang, K. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_1 · Cited by 1,286
Cramer, R., & Shoup, V. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539702403773 · Cited by 978
The Decision Diffie-Hellman problem
Boneh, D. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054851 · Cited by 895
Practical Threshold Signatures
Shoup, V. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-45539-6_15 · Cited by 874
Micali, S., Rabin, M., & Vadhan, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814584 · Cited by 716
Secure Two-Party Computation Is Practical
Pinkas, B., Schneider, T., Smart, N. P., & Williams, S. C. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-10366-7_15 · Cited by 711
Traitor Tracing with Constant Transmission Rate
Kiayias, A., & Yung, M. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-46035-7_30 · Cited by 675
Oblivious transfer and polynomial evaluation
Naor, M., & Pinkas, B. (1999) · Proceedings of the thirty-first annual ACM symposium on Theory of Computing · doi:10.1145/301250.301312 · Cited by 629
Self-citationEfficient oblivious transfer protocols
Naor, M., & Benny Pinkas, B. (2001) · Symposium on Discrete Algorithms · doi:10.5555/365411.365502 · Cited by 614
Self-citationKey agreement in dynamic peer groups
Steiner, M., Tsudik, G., & Waidner, M. (2000) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.877936 · Cited by 601
On the (im)possibility of obfuscating programs
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., & Yang, K. (2012) · Journal of the ACM · doi:10.1145/2160158.2160159 · Cited by 595
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
The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES
Abdalla, M., Bellare, M., & Rogaway, P. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45353-9_12 · Cited by 445
Key-Privacy in Public-Key Encryption
Bellare, M., Boldyreva, A., Desai, A., & Pointcheval, D. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45682-1_33 · Cited by 442
Keyword Search and Oblivious Pseudorandom Functions
Freedman, M. J., Ishai, Y., Pinkas, B., & Reingold, O. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_17 · Cited by 441
Self-citationA Verifiable Random Function with Short Proofs and Keys
Dodis, Y., & Yampolskiy, A. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30580-4_28 · Cited by 428
Priced Oblivious Transfer: How to Sell Digital Goods
Aiello, B., Ishai, Y., & Reingold, O. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44987-6_8 · Cited by 400
Self-citationHow to Simulate It – A Tutorial on the Simulation Proof Technique
Lindell, Y. (2017) · Information Security and Cryptography · doi:10.1007/978-3-319-57048-8_6 · Cited by 381
Provably authenticated group Diffie-Hellman key exchange
Bresson, E., Chevassut, O., Pointcheval, D., & Quisquater, J.-J. (2001) · Proceedings of the 8th ACM conference on Computer and Communications Security · doi:10.1145/501983.502018 · Cited by 372
Number-theoretic constructions of efficient pseudo-random functions
Naor, M., & Reingold, O. (2004) · Journal of the ACM · doi:10.1145/972639.972643 · Cited by 368
Self-citationOn Cryptographic Assumptions and Challenges
Naor, M. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_6 · Cited by 360
Self-citationKey Homomorphic PRFs and Their Applications
Boneh, D., Lewi, K., Montgomery, H., & Raghunathan, A. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40041-4_23 · Cited by 321
Efficient Trace and Revoke Schemes
Naor, M., & Pinkas, B. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45472-1_1 · Cited by 298
Self-citationNon-interactive cryptocomputing for NC/sup 1/
Sander, T., Young, A., & Yung, M. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814630 · Cited by 279
Hazay, C., & Lindell, Y. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78524-8_10 · Cited by 267
MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity
Albrecht, M., Grassi, L., Rechberger, C., Roy, A., & Tiessen, T. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-53887-6_7 · Cited by 258
Metadata
- Authors
- Naor, M., & Reingold, O.
- Venue
- Proceedings 38th Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-22
- Pages
- 458-467
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2144560442
- Cited by
- 353
- References
- 46
- FWCI
- 12.78
- Type
- conference paper
- 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.