Quantum algorithm for the multicollision problem

DOI10.1016/j.tcs.2020.07.039zbMath1455.68067arXiv1911.02822OpenAlexW3047009386MaRDI QIDQ2006780

Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, Keita Xagawa

Publication date: 12 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.02822

zbMATH Keywords

quantum algorithmpost-quantum cryptographymulticollisionmulticlaw

Mathematics Subject Classification ID

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

Related Items (1)

Finding many collisions via reusable quantum walks. Application to lattice sieving

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Claw finding algorithms using quantum walk
• Multi-collision resistant hash functions and their applications
• Collision resistant hashing for paranoids: dealing with multiple collisions
• Quantum multicollision-finding algorithm
• On finding quantum multi-collisions
• Improved quantum multicollision-finding algorithm
• Concentration of the hypergeometric distribution
• Improved Indifferentiable Security Analysis of PHOTON
• Beyond 2 c/2 Security in Sponge-Based Authenticated Encryption Modes
• Cryptanalysis of Iterated Even-Mansour Schemes with Two Keys
• Cryptanalysis of Round-Reduced $$\mathtt{LED}$$
• A New Algorithm for the Unbalanced Meet-in-the-Middle Problem
• A Lightweight 256-Bit Hash Function for Hardware and Low-End Devices: Lesamnta-LW
• Quantum Random Access Memory
• Generic State-Recovery and Forgery Attacks on ChopMD-MAC and on NMAC/HMAC
• Quantum lower bounds for the collision and the element distinctness problems
• Improved Indifferentiability Security Analysis of chopMD Hash Function
• Cryptanalysis of MDC-2
• Improved Generic Algorithms for 3-Collisions
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• Multi-collision resistance: a paradigm for keyless hash functions
• Quantum Algorithms for Element Distinctness
• Time-Efficient Quantum Walks for 3-Distinctness
• Birthday Paradox for Multi-collisions
• Span programs for functions with constant-sized 1-certificates
• Quantum Walk Algorithm for Element Distinctness
• Nondeterministic Algorithms
• Quantum cryptanalysis of hash and claw-free functions

This page was built for publication: Quantum algorithm for the multicollision problem