Security of cryptographic hash functions: Difference between revisions

Revision as of 21:48, 21 September 2018

Revision as of 18:37, 9 January 2019

Line 62:

* [[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_{2p+1}</math>.

* [[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 rely on the arithmetic of the group of matrices [[Special linear group|SL2]]. 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}</math>. This beat by far the birthday bound and ideal pre-image complexities which are <math>2^{3n/2}</math> and <math>2^{3n}</math> for the Zémor-Tillich hash function. As the attacks include a birthday search in a reduced set of size <math>2n</math> they indeed do not destroy the idea of provable security ofor invalidate the scheme but rather suggest that the initial parameters were too small.<ref>{{Citation

| last1 = Petit | first1 = C.

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