Paper 2017/688
Quantum Collision-Finding in Non-Uniform Random Functions
Marko Balogh, Edward Eaton, and Fang Song
Abstract
We give a complete characterization of quantum attacks for finding a collision in a non- uniform random function whose outputs are drawn according to a distribution of min-entropy k. This can be viewed as showing generic security of hash functions under relaxed assumptions in contrast to the standard heuristic of assuming uniformly random outputs. It also has ap- plications in analyzing quantum security of the Fujisaki-Okamoto transformation [TU TCC16B]. In particular, our results close a gap in the lower bound left open in [TTU PQCrypto16].
Specifically, let
Note: proofs largely updated for modularity; added discussion on preimage and second preimage resistance
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- collision resistancequantum securityhash functions
- Contact author(s)
- fsong @ pdx edu
- History
- 2017-11-26: revised
- 2017-07-18: received
- See all versions
- Short URL
- https://ia.cr/2017/688
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/688, author = {Marko Balogh and Edward Eaton and Fang Song}, title = {Quantum Collision-Finding in Non-Uniform Random Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/688}, year = {2017}, url = {https://eprint.iacr.org/2017/688} }