Content deleted Content added
Various corrections |
The Zémor-Tillich hash function attack |
||
Line 60:
* [[Chaum, van Heijst, Pfitzmann hash function]] - A compression function where finding collisions is as hard as finding a [[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]]. 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 preimage 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 distroy the idea of provable security of invalidate the scheme but rather suggest that the initial parameters were too small. <ref>{{Citation
| last1 = Petit | first1 = C.
| last2 = Quisquater | first2 = J.-J.
| last3 = Tillich | first3 = J.-P.
| contribution = Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security
| contribution-url = http://www-rocq.inria.fr/secret/Jean-Pierre.Tillich/publications/CTRSA.pdf }}</ref>
* [[Hash functions from Sigma Protocols]] - there exists a general way of constructing a provably secure hash, specifically from a any (suitable) [[The Sigma Protocol|sigma protocol]]. A faster version of [[Very smooth hash|VSH]] (called VSH*) could be obtained in this way.
* [[Hash functions from Sigma Protocols]] - there exists a general way of constructing a provably secure hash, specifically from a any (suitable) [[The Sigma Protocol|sigma protocol]]. A faster version of [[Very smooth hash|VSH]] (called VSH*) could be obtained in this way.
==References==
{{Reflist}}
{{Crypto navbox | hash}}
| |||