On Finding Quantum Multi-collisions

Liu, Qipeng; Zhandry, Mark

On Finding Quantum Multi-collisions

Author(s): Liu, Qipeng; Zhandry, Mark

Download

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr16g2x

Full metadata record

DC Field	Value	Language
dc.contributor.author	Liu, Qipeng	-
dc.contributor.author	Zhandry, Mark	-
dc.date.accessioned	2021-10-08T19:48:16Z	-
dc.date.available	2021-10-08T19:48:16Z	-
dc.date.issued	2019	en_US
dc.identifier.citation	Liu, Qipeng, and Mark Zhandry. "On Finding Quantum Multi-collisions." In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2019): pp. 189-218. doi:10.1007/978-3-030-17659-4_7	en_US
dc.identifier.issn	0302-9743	-
dc.identifier.uri	https://arxiv.org/pdf/1811.05385v1.pdf	-
dc.identifier.uri	http://arks.princeton.edu/ark:/88435/pr16g2x	-
dc.description.abstract	A k-collision for a compressing hash function H is a set of k distinct inputs that all map to the same output. In this work, we show that for any constant k, 𝛩(𝑁12(1−12𝑘−1)) quantum queries are both necessary and sufficient to achieve a k-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.	en_US
dc.format.extent	189 - 218	en_US
dc.language.iso	en_US	en_US
dc.relation.ispartof	Annual International Conference on the Theory and Applications of Cryptographic Techniques	en_US
dc.rights	Author's manuscript	en_US
dc.title	On Finding Quantum Multi-collisions	en_US
dc.type	Conference Article	en_US
dc.identifier.doi	10.1007/978-3-030-17659-4_7	-
dc.identifier.eissn	1611-3349	-
pu.type.symplectic	http://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceeding	en_US

Files in This Item:

File	Description	Size	Format
FindingQuantumMultiCollisions.pdf		283.12 kB	Adobe PDF	View/Download

Show Simple Item Record