Tight quantum time-space tradeoffs for function inversion

DOI10.1109/FOCS46700.2020.00068MaRDI QIDQ6943988zbMATH OpenFDO

Authors Luowen Qian, Kai-Min Chung, Siyao Guo, Qipeng Liu

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00068

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(15)

• Time-space tradeoffs for finding multi-collisions in Merkle-Damgård hash functions
• On the power of adaptivity for function inversion
• Time-space tradeoffs for sponge hashing: attacks and limitations for short collisions
• A new approach to generic lower bounds. Classical/quantum MDL, quantum factoring, and more
• The space-time cost of purifying quantum computations
• Classical vs quantum advice and proofs under classically-accessible oracle
• Quantum lower bounds by sample-to-query lifting
• Hide-and-seek and the non-resignability of the BUFF transform
• Improved quantum lifting by coherent measure-and-reprogram
• Verifiable quantum advantage without structure
• Seedless condensers for efficiently samplable sources
• NISQ security and complexity via simple classical reasoning
• Tight quantum time-space tradeoffs for permutation inversion
• On the efficiency of generic, quantum cryptographic constructions
• On the two-sided permutation inversion problem

This page was built for publication: Tight quantum time-space tradeoffs for function inversion

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