The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Limits on the provable consequences of one-way permutations
Abstract
We present strong evidence that the implication, “if one-way permutations exist, then secure secret key agreement is possible”, is not provable by standard techniques. Since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. We consider a world where all parties have access to a black box for a randomly selected permutation. Being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. We show that, if P = N P, no protocol for secret key agreement is secure in such a setting. Thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving P ≠ N P. We also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. Thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. Our results present a general framework for proving statements of the form, “Cryptographic application X is not likely possible based solely on complexity assumption Y.”
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
Goldreich, 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
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
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
Zero-knowledge proofs of identity
Feige, U., Fiat, A., & Shamir, A. (1988) · Journal of Cryptology · doi:10.1007/bf02351717 · Cited by 1,029
Random generation of combinatorial structures from a uniform distribution
Jerrum, M. R., Valiant, L. G., & Vazirani, V. V. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90174-x · Cited by 985
Theory and application of trapdoor functions
Yao, A. C. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.45 · Cited by 968
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
Minimum disclosure proofs of knowledge
Brassard, G., Chaum, D., & Crépeau, C. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90005-0 · Cited by 959
Secure communications over insecure channels
Merkle, R. C. (1978) · Communications of the ACM · doi:10.1145/359460.359473 · Cited by 757
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
Efficient Private Matching and Set Intersection
Freedman, M. J., Nissim, K., & Pinkas, B. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24676-3_1 · Cited by 1,266
Perfectly-Secure Key Distribution for Dynamic Conferences
Blundo, C., De Santis, A., Herzberg, A., Kutten, S., Vaccaro, U., & Yung, M. (1993) · Lecture Notes in Computer Science · doi:10.1007/3-540-48071-4_33 · Cited by 1,030
The random oracle methodology, revisited
Canetti, R., Goldreich, O., & Halevi, S. (2004) · Journal of the ACM · doi:10.1145/1008731.1008734 · Cited by 978
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
Replication is not needed: single database, computationally-private information retrieval
Kushilevitz, E., & Ostrovsky, R. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646125 · Cited by 932
Privacy preserving auctions and mechanism design
Naor, M., Pinkas, B., & Sumner, R. (1999) · Proceedings of the 1st ACM conference on Electronic commerce · doi:10.1145/336992.337028 · Cited by 753
Unconditionally Secure Quantum Bit Commitment is Impossible
Mayers, D. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.3414 · Cited by 748
Extending Oblivious Transfers Efficiently
Ishai, Y., Kilian, J., Nissim, K., & Petrank, E. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_9 · Cited by 746
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
Self-citationSecret-Sharing Schemes: A Survey
Beimel, A. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20901-7_2 · Cited by 652
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
Efficient oblivious transfer protocols
Naor, M., & Benny Pinkas, B. (2001) · Symposium on Discrete Algorithms · doi:10.5555/365411.365502 · Cited by 614
Separating succinct non-interactive arguments from all falsifiable assumptions
Gentry, C., & Wichs, D. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993651 · Cited by 456
Zero-knowledge from secure multiparty computation
Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250794 · Cited by 412
On Cryptographic Assumptions and Challenges
Naor, M. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_6 · Cited by 360
Witness encryption and its applications
Garg, S., Gentry, C., Sahai, A., & Waters, B. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488667 · Cited by 333
Extractors and pseudorandom generators
(2001) · Journal of the ACM · doi:10.1145/502090.502099 · Cited by 324
Public-key cryptography and password protocols
Halevi, S., & Krawczyk, H. (1999) · ACM Transactions on Information and System Security · doi:10.1145/322510.322514 · Cited by 314
Formal certification of code-based cryptographic proofs
Barthe, G., Grégoire, B., & Zanella Béguelin, S. (2009) · Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages · doi:10.1145/1480881.1480894 · Cited by 268
Modern Cryptography, Probabilistic Proofs and Pseudorandomness
Goldreich, O. (1999) · Algorithms and Combinatorics · doi:10.1007/978-3-662-12521-2 · Cited by 265
Yang, Q., Liu, Y., Cheng, Y., Kang, Y., Chen, T., & Yu, H. (2019) · Synthesis lectures on artificial intelligence and machine learning · doi:10.2200/s00960ed2v01y201910aim043 · Cited by 261
The Relationship Between Password-Authenticated Key Exchange and Other Cryptographic Primitives
Nguyen, M.-H. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_25 · Cited by 7
“Hence, unlike the GL definition, the BPR definition does not imply semihonest OT for dictionaries of exponential size under black-box reductions ([15, 9]).”
BackgroundMethodInfluentialOn the (im)possibility of perennial message recognition protocols without public-key cryptography
González Muñiz, M., & Laud, P. (2011) · Proceedings of the 2011 ACM Symposium on Applied Computing · doi:10.1145/1982185.1982508 · Cited by 5
Metadata
- Authors
- Impagliazzo, R., & Rudich, S.
- Venue
- Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89
- Publisher
- ACM Press
- Published
- 1989
- Pages
- 44-61
- OpenAlex
- W2004881597
- Cited by
- 575
- References
- 21
- FWCI
- 3.07
- 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.