The DOI matches its OpenAlex record; 18 of the 18 references it cites were found in a registry or an index.
Theory and application of trapdoor functions
Abstract
The purpose of this paper is to introduce a new information theory and explore its appplications. Using modern computational complexity, we study the notion of information that can be accessed through a feasible computation. In Part 1 of this paper, we lay the foundation of the theory and set up a framework for cryptography and pseudorandom number generation. In Part 2, we study the concept of trapdoor functions and examine applications of such functions in cryptography, pseudorandom number generation, and abstract complexity theory.
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 method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Communication Theory of Secrecy Systems
Shannon, C. E. (1949) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1949.tb00928.x · Cited by 9,440
Wyner, A. D. (1975) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1975.tb02040.x · Cited by 7,075
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
The definition of random sequences
Martin-Löf, P. (1966) · Information and Control · doi:10.1016/s0019-9958(66)80018-9 · Cited by 1,220
DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION
Rabin, M. O. (1979) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1,020
Probabilistic encryption & how to play mental poker keeping secret all partial information
Goldwasser, S., & Micali, S. (1982) · Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 · doi:10.1145/800070.802212 · Cited by 883
A Theory of Program Size Formally Identical to Information Theory
Chaitin, G. J. (1975) · Journal of the ACM · doi:10.1145/321892.321894 · Cited by 849
Random walks, universal traversal sequences, and the complexity of maze problems
Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., & Rackoff, C. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.34 · Cited by 692
Cited by
Random oracles are practical: a paradigm for designing efficient protocols
Bellare, M., & Rogaway, P. (1993) · Proceedings of the 1st ACM conference on Computer and communications security - CCS '93 · doi:10.1145/168588.168596 · Cited by 4,712
Practical Secure Aggregation for Privacy-Preserving Machine Learning
Bonawitz, K., Ivanov, V., Kreuter, B., Marcedone, A., McMahan, H. B., Patel, S., Ramage, D., Segal, A., & Seth, K. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3133982 · Cited by 3,956
How to generate and exchange secrets
Yao, A. C.-C. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.25 · Cited by 3,733
Self-citationGoldreich, O., Micali, S., & Wigderson, A. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28420 · Cited by 3,590
Universally composable security: a new paradigm for cryptographic protocols
Canetti, R. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959888 · Cited by 3,309
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
Entity Authentication and Key Distribution
Bellare, M., & Rogaway, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_21 · Cited by 1,752
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
How to time-stamp a digital document
Haber, S., & Stornetta, W. S. (1991) · Journal of Cryptology · doi:10.1007/bf00196791 · Cited by 1,483
Security and Composition of Multiparty Cryptographic Protocols
Canetti, R. (2000) · Journal of Cryptology · doi:10.1007/s001459910006 · Cited by 1,403
A practical scheme for non-interactive verifiable secret sharing
Feldman, P. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.4 · Cited by 1,125
Dolev, D., Dwork, C., & Naor, M. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103474 · Cited by 990
Universal one-way hash functions and their cryptographic applications
Naor, M., & Yung, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73011 · Cited by 959
A concrete security treatment of symmetric encryption
Bellare, M., Desai, A., Jokipii, E., & Rogaway, P. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646128 · Cited by 931
Bellare, M., & Rogaway, P. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053428 · Cited by 906
Non-interactive zero-knowledge and its applications
Blum, M., Feldman, P., & Micali, S. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62222 · Cited by 904
Nisan, N., & Wigderson, A. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80043-1 · Cited by 808
Bit commitment using pseudorandomness
Naor, M. (1991) · Journal of Cryptology · doi:10.1007/bf00196774 · Cited by 807
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Verifiable secret sharing and achieving simultaneity in the presence of faults
Chor, B., Goldwasser, S., Micali, S., & Awerbuch, B. (1985) · 26th Annual Symposium on Foundations of Computer Science (sfcs 1985) · doi:10.1109/sfcs.1985.64 · Cited by 771
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
Pseudo-random generation from one-way functions
Impagliazzo, R., Levin, L. A., & Luby, M. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73009 · Cited by 724
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
The random oracle methodology, revisited (preliminary version)
Canetti, R., Goldreich, O., & Halevi, S. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276741 · Cited by 715
The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs
Bellare, M., & Rogaway, P. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_25 · Cited by 672
Universally Composable Commitments
Canetti, R., & Fischlin, M. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44647-8_2 · Cited by 621
Definitions and properties of zero-knowledge proof systems
Goldreich, O., & Oren, Y. (1994) · Journal of Cryptology · doi:10.1007/bf00195207 · Cited by 614
Reconciling Two Views of Cryptography (The Computational Soundness of Formal Encryption)*
Abadi, M., & Rogaway, P. (2002) · Journal of Cryptology · doi:10.1007/s00145-001-0014-7 · Cited by 613
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
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
Goldreich, O., Micali, S., & Wigderson, A. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.47 · Cited by 549
P = BPP if E requires exponential circuits: derandomizing the XOR lemma
Impagliazzo, R., & Wigderson, A. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258590 · Cited by 534
Random sequence generation by cellular automata
Wolfram, S. (1986) · Advances in Applied Mathematics · doi:10.1016/0196-8858(86)90028-x · Cited by 494
Simultaneous Hardcore Bits and Cryptography against Memory Attacks
Akavia, A., Goldwasser, S., & Vaikuntanathan, V. (2009) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-00457-5_28 · Cited by 490
Public-key cryptosystems from lattice reduction problems
Goldreich, O., Goldwasser, S., & Halevi, S. (1997) · Lecture Notes in Computer Science · doi:10.1007/bfb0052231 · Cited by 482
Protecting data privacy in private information retrieval schemes
Gertner, Y., Ishai, Y., Kushilevitz, E., & Malkin, T. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276723 · Cited by 445
Damgård, I., Fitzi, M., Kiltz, E., Nielsen, J. B., & Toft, T. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_15 · Cited by 443
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
How to Time-Stamp a Digital Document
Haber, S., & Stornetta, W. S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-38424-3_32 · Cited by 404
Impagliazzo, R., & Zuckerman, D. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63486 · Cited by 387
Physically Observable Cryptography
Micali, S., & Reyzin, L. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24638-1_16 · Cited by 378
A model for asynchronous reactive systems and its application to secure message transmission
Pfitzmann, B., & Waidner, M. (2002) · Proceedings 2001 IEEE Symposium on Security and Privacy. S&P 2001 · doi:10.1109/secpri.2001.924298 · Cited by 349
Cryptographic Primitives Based on Hard Learning Problems
Blum, A., Furst, M., Kearns, M., & Lipton, R. J. (1994) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_24 · Cited by 332
On-line/off-line digital signatures
Even, S., Goldreich, O., & Micali, S. (1996) · Journal of Cryptology · doi:10.1007/bf02254791 · Cited by 318
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
Babai, L., Fortnow, L., Nisan, N., & Wigderson, A. (1993) · Computational Complexity · doi:10.1007/bf01275486 · Cited by 310
Coppersmith, D., Krawczyk, H., & Mansour, Y. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48329-2_3 · Cited by 306
A fair protocol for signing contracts
Ben-Or, M., Goldreich, O., Micali, S., & Rivest, R. L. (1990) · IEEE Transactions on Information Theory · doi:10.1109/18.50372 · Cited by 287
On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited
Naor, M., & Reingold, O. (1999) · Journal of Cryptology · doi:10.1007/pl00003817 · Cited by 285
Foundations of Secure Interactive Computing
Beaver, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_31 · Cited by 277
Composition and integrity preservation of secure reactive systems
Pfitzmann, B., & Waidner, M. (2000) · Proceedings of the 7th ACM conference on Computer and Communications Security · doi:10.1145/352600.352639 · Cited by 277
Forward-Security in Private-Key Cryptography
Bellare, M., & Yee, B. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36563-x_1 · Cited by 275
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
Klivans, A. R., & van Melkebeek, D. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700389652 · Cited by 270
Crytographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. G. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73049 · 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
One way functions and pseudorandom generators
Levin, L. A. (1987) · Combinatorica · doi:10.1007/bf02579323 · Cited by 257
Generating quasi-random sequences from semi-random sources
Santha, M., & Vazirani, U. V. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90044-9 · Cited by 256
Hard-core distributions for somewhat hard problems
Impagliazzo, R. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492584 · Cited by 254
Almost everywhere high nonuniform complexity
Lutz, J. H. (1992) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(92)90020-j · Cited by 254
Certifiable quantum dice: or, true random number generation secure against quantum adversaries
Vazirani, U., & Vidick, T. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213984 · Cited by 80
“It may also be worth emphasizing that the bits eventually produced, after application of an extractor, will be guaranteed to be statistically indistinguishable from uniform, a much stronger condition that the computational indistinguishability that is the criterion for cryptographic pseudorandom generators [26, 4, 30].”
BackgroundBlum, L., & Blum, M. (2022) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.2115934119 · Cited by 70
The ghost in the radiation: robust encodings of the black hole interior
Kim, I., Tang, E., & Preskill, J. (2020) · Journal of High Energy Physics · doi:10.1007/jhep06(2020)031 · Cited by 63
Metadata
- Authors
- Yao, A. C.-C.
- Published
- 1982-11-03
- Pages
- 80-91
- OpenAlex
- W2061106457
- Cited by
- 1,008
- References
- 18
- FWCI
- 14.04
- 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.