Security of cryptographic hash functions: Difference between revisions

Revision as of 02:02, 24 August 2024

Revision as of 20:15, 26 August 2024

Line 68:

* [[Fast Syndrome Based Hash|FSB]]—[[Fast Syndrome Based Hash|Fast Syndrome-Based hash function]]—it can be proven that breaking FSB is at least as difficult as solving ''regular syndrome decoding'', which is known to be NP-complete.

* [[SWIFFT]]—SWIFFT is based on the [[fast Fourier transform]] and is provably collision resistant, under a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/[[Ideal lattice cryptography|ideal lattices]].

* [[Chaum, van Heijst, Pfitzmann hash function]]—a compression function where finding collisions is as hard as solving the [[discrete logarithm|discrete logarithm problem]] in a finite group {{Math|''F''_2''p''+1}}.

* [[Knapsack-based hash functions]]—a family of hash functions based on the [[knapsack problem]].

* [[The Zémor-Tillich hash function]]—a family of hash functions that relies on the arithmetic of the group of matrices [[Special linear group|SL₂]]. Finding collisions is at least as difficult as finding factorization of certain elements in this group. This is supposed to be hard, at least [[PSPACE-complete]].{{Dubious|PSPACE-complete?!|date=January 2019}} For this hash, an attack was eventually discovered with a time complexity close to {{Math|2^''n''/2}}. This beat by far the birthday bound and ideal pre-image complexities, which are {{Math|2^3''n''/2}} and {{Math|2^3''n''}} for the Zémor-Tillich hash function. As the attacks include a birthday search in a reduced set of size {{Math|2''n''}}, they indeed do not destroy the idea of provable security or invalidate the scheme but rather suggest that the initial parameters were too small.<ref>{{Citation

| last1 = Petit | first1 = C.

| last2 = Quisquater | first2 = J.-J.