The DOI matches its Crossref record; 52 of the 52 references it cites were found in a registry or an index.
Random Oracles in a Quantum World
Open accessAbstract
The interest in post-quantum cryptography -- classical systems that remain secure in the presence of a quantum adversary -- has generated elegant proposals for new cryptosystems. Some of these systems are set in the random oracle model and are proven secure relative to adversaries that have classical access to the random oracle. We argue that to prove post-quantum security one needs to prove security in the quantum-accessible random oracle model where the adversary can query the random oracle with quantum state. We begin by separating the classical and quantum-accessible random oracle models by presenting a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when the adversary can make quantum oracle queries. We then set out to develop generic conditions under which a classical random oracle proof implies security in the quantum-accessible random oracle model. We introduce the concept of a history-free reduction which is a category of classical random oracle reductions that basically determine oracle answers independently of the history of previous queries, and we prove that such reductions imply security in the quantum model. We then show that certain post-quantum proposals, including ones based on lattices, can be proven secure using history-free reductions and are therefore postquantum secure. We conclude with a rich set of open problems in this area.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
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
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
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
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
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
A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
Goldwasser, S., Micali, S., & Rivest, R. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217017 · Cited by 2,804
Cited by
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM
Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehle, D. (2018) · 2018 IEEE European Symposium on Security and Privacy (EuroS&P) · doi:10.1109/eurosp.2018.00032 · Cited by 1,192
A Modular Analysis of the Fujisaki-Okamoto Transformation
Hofheinz, D., Hövelmanns, K., & Kiltz, E. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-70500-2_12 · Cited by 451
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413 · Cited by 395
The SPHINCS + Signature Framework
Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., & Schwabe, P. (2019) · Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3319535.3363229 · Cited by 306
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413-upd1 · Cited by 301
Metadata
- Authors
- Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2011
- Pages
- 41-69
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W1480477462
- Cited by
- 449
- References
- 52
- FWCI
- 7.03
- Type
- conference paper
- Language
- en
- Open access
- green
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Random Oracles in a Quantum World. https://app.cochat.ai/papers/10.1007/978-3-642-25385-0_3
- The paper
- Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M. (2011). Random Oracles in a Quantum World. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-642-25385-0_3
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.