A comprehensive review on collision-resistant hash functions on lattices

摘要

Hash functions have always attracted a lot of attention in modern cryptography because of their hard to invert nature. However, all previous constructions of cryptographic primitives face the threat of being broken by the recent advancements in quantum technology. The focus has thus shifted to developing cryptographic primitives on mathematical structures such as lattices that are intractable by quantum algorithms. We review the computational problems defined on lattices and their respective hardness and discuss constructions of hash function families based on both integer and ideal lattices whose security depends on these computational problems on lattices. We provide a comparative analysis of the theoretical security and concrete instantiations claimed by the different hash function families. Finally, we review techniques used in the reductions for the security proofs of constructions of different hash function families.