Claw-free permutation

From Wikipedia, the free encyclopedia

In mathematical and computer science field of cryptography, a group of three numbers (x,y,z) is said to be a claw of two permutations f₀ and f₁ if and only if

f₀(x) = f₁(y) = z.

The terminology claw free was introduced by Ivan Damgård in his PhD thesis The Application of Claw Free Functions in Cryptography, Aarhus University, 1988.^[1]

The existence of claw-free permutations has been proven to imply secure digital signatures, for which existential forgery is not possible.^[2] The existence of trapdoor permutations does not by itself imply claw-free permutations exist; however, it has been shown that claw-free permutations do exist if factoring is hard.

It is also often cryptographically important for a hash function to be claw-free, in the sense that it is difficult to create a pair (x,y) such that

H(x) = H(y).

In the hash function literature, this is commonly termed a hash collision. A hash function where collisions are difficult to educe is said to have collision resistance.

[edit] References

^ Takeshi Koshiba, Self-Definable Claw Free Functions, 1996.
^ S. Goldwasser, S. Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing, 17(2):281-308, April 1988.