On quantum query complexities of collision-finding in non-uniform random functions

DOI10.1007/978-981-95-5125-5_7MaRDI QIDQ7232833zbMATH OpenFDO

Authors Tianci Peng, Shujiao Cao, Rui Xue

Publication date 23 April 2026

Full work available at URL https://doi.org/10.1007/978-981-95-5125-5_7

zbMATH Keywords

collision-finding algorithmscompressed oracle techniquequantum query complexity

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Cites work

• 4-round Luby-Rackoff construction is a qPRP
• A method for obtaining digital signatures and public-key cryptosystems
• A new pseudorandom generator from collision-resistant hash functions
• Breaking symmetric cryptosystems using quantum period finding
• How to construct quantum random functions
• How to record quantum queries, and applications to quantum indifferentiability
• scientific article; zbMATH DE number 6492476 (Why is no real title available?)
• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• Improved quantum algorithm for triangle finding via combinatorial arguments
• Lattice Sieving via Quantum Random Walks
• Multi-collision resistant hash functions and their applications
• Nested Quantum Walks with Quantum Data Structures
• New directions in cryptography
• On finding quantum multi-collisions
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Post-Quantum Security of the Fujisaki-Okamoto and OAEP Transforms
• Quantum attacks on classical proof systems: the hardness of quantum rewinding
• Quantum attacks on some Feistel block ciphers
• Quantum collision-finding in non-uniform random functions
• Quantum collision-resistance of non-uniformly distributed functions
• Quantum lower bound for the collision problem with small range
• Quantum lower bounds by quantum arguments
• Quantum lower bounds for the collision and the element distinctness problems
• Quantum security proofs using semi-classical oracles
• Search via Quantum Walk
• Secure integration of asymmetric and symmetric encryption schemes
• Security-Amplifying Combiners for Collision-Resistant Hash Functions
• When Are Fuzzy Extractors Possible?

This page was built for publication: On quantum query complexities of collision-finding in non-uniform random functions

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