Paper 2021/1016

Quantum collision finding for homomorphic hash functions

Juan Carlos Garcia-Escartin, Vicent Gimeno, and Julio José Moyano-Fernández

Abstract

Hash functions are a basic cryptographic primitive. Certain hash functions try to prove security against collision and preimage attacks by reductions to known hard problems. These hash functions usually have some additional properties that allow for that reduction. Hash functions which are additive or multiplicative are vulnerable to a quantum attack using the hidden subgroup problem algorithm for quantum computers. Using a quantum oracle to the hash, we can reconstruct the kernel of the hash function, which is enough to find collisions and second preimages. When the hash functions are additive with respect to the group operation in an Abelian group, there is always an efficient implementation of this attack. We present concrete attack examples to provable hash functions, including a preimage attack to $\oplus$-linear hash functions and for certain multiplicative homomorphic hash schemes.

Note: Comments welcome. Example without quantum advantage removed.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
hash functionsquantum attackscollisionshidden subgroup problem
Contact author(s)
juagar @ tel uva es
History
2021-08-09: last of 3 revisions
2021-08-06: received
See all versions
Short URL
https://ia.cr/2021/1016
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1016,
      author = {Juan Carlos Garcia-Escartin and Vicent Gimeno and Julio José Moyano-Fernández},
      title = {Quantum collision finding for homomorphic hash functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1016},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1016}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.