Quantum advantage from one-way functions

DOI10.1007/978-3-031-68388-6_13MaRDI QIDQ6652974FDOQ6652974

Authors: Tomoyuki Morimae, Takashi Yamakawa 

Publication date: 13 December 2024

Recommendations

• Statistical zero knowledge and quantum one-way functions
• scientific article; zbMATH DE number 7651035
• One-way functions imply secure computation in a quantum world
• Quantum commitments and signatures without one-way functions

Mathematics Subject Classification ID

Cryptography (94A60) Quantum computation (81P68)

Cites Work

• Computational Complexity
• Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function
• The random oracle methodology, revisited.
• Practical and provably-secure commitment schemes from collision-free hashing
• Foundations of Cryptography
• Foundations of Cryptography
• Advances in Cryptology - CRYPTO 2003
• The computational complexity of linear optics
• NP is as easy as detecting unique solutions
• On the randomness complexity of efficient sampling
• The need for structure in quantum speedups
• Quantum advantage with shallow circuits
• Separating succinct non-interactive arguments from all falsifiable assumptions
• BQP and the polynomial hierarchy
• Theory of Cryptography
• An Equivalence Between Zero Knowledge and Commitments
• Cryptography from pseudorandom quantum states
• Multi-collision resistant hash functions and their applications
• Collision resistant hashing for paranoids: dealing with multiple collisions
• Title not available (Why is that?)
• The equivalence of sampling and searching
• Pseudorandom quantum states
• On the relationship between statistical zero-knowledge and statistical randomized encodings
• Title not available (Why is that?)
• Forrelation: a problem that optimally separates quantum from classical computing
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
• On distributional collision resistant hashing
• Title not available (Why is that?)
• Complexity-theoretic foundations of quantum supremacy experiments
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Quantum commitments and signatures without one-way functions
• Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
• Distributional collision resistance beyond one-way functions
• A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
• Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond
• Pseudorandom (function-Like) quantum state generators: new definitions and applications
• Title not available (Why is that?)
• On the computational hardness needed for quantum cryptography
• Proofs of quantumness from trapdoor permutations

Cited In (1)

• Exponential quantum one-wayness and EFI pairs

This page was built for publication: Quantum advantage from one-way functions

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