A meta-complexity characterization of quantum cryptography

DOI10.1007/978-3-031-91098-2_4MaRDI QIDQ6891197zbMATH OpenFDO

Authors Bruno Pasqualotto Cavalar, Eli Goldin, Matthew J. Gray, Peter J. Hall

Publication date 2 December 2025

Full work available at URL https://doi.org/10.1007/978-3-031-91098-2_4

zbMATH Keywords

meta-complexityone-way puzzlesquantum cryptographic primitive

Mathematics Subject Classification ID

Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Cites work

• A duality between one-way functions and average-case symmetry of information
• A method for obtaining digital signatures and public-key cryptosystems
• A Pseudorandom Generator from any One-way Function
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES
• An introduction to Kolmogorov complexity and its applications
• Average-Case Complexity
• Average-case hardness of NP from exponential worst-case hardness assumptions
• Beyond natural proofs: hardness magnification and locality
• Capturing one-way functions via NP-hardness of meta-complexity
• Characterizing pseudoentropy and simplifying pseudorandom generator constructions
• Complexity limitations on quantum computation
• Cryptography from pseudorandom quantum states
• Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
• Erratum for: ``On basing one-way functions on NP-hardness
• General properties of quantum bit commitments (extended abstract)
• scientific article; zbMATH DE number 1024063 (Why is no real title available?)
• scientific article; zbMATH DE number 1497858 (Why is no real title available?)
• scientific article; zbMATH DE number 7650416 (Why is no real title available?)
• scientific article; zbMATH DE number 7829279 (Why is no real title available?)
• scientific article; zbMATH DE number 7701522 (Why is no real title available?)
• Kolmogorov comes to cryptomania: on interactive Kolmogorov complexity and key-agreement
• Learning algorithms from natural proofs
• On basing size-verifiable one-way functions on NP-hardness
• On central primitives for quantum cryptography with classical communication
• On one-way functions and Kolmogorov complexity
• One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions
• Pseudorandom quantum states
• Quantum advantage from one-way functions
• Quantum commitments and signatures without one-way functions
• Quantum Complexity Theory
• Quantum cryptography in Algorithmica
• Quantum Kolmogorov complexity
• Zero knowledge and circuit minimization

This page was built for publication: A meta-complexity characterization of quantum cryptography

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6891197)