In the 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<sub>0</sub> and f<sub>1</sub> if
A pair of permutations f<sub>0</sub> and f<sub>1</sub> are said to be claw-free if there is no efficient algorithm for computing a claw.
The terminology claw free was introduced by Goldwasser, Micali, and Rivest in their 1984 paper, "A Paradoxical Solution to the Signature Problem" (and later in a more complete journal paper), where they showed that the existence of claw-free pairs of trapdoor permutations implies the existence of digital signature schemes secure against adaptive chosen-message attack. This construction was later superseded by the construction of digital signatures from any one-way trapdoor permutation. 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.
The general notion of claw-free permutation (not necessarily trapdoor) was further studied by Ivan DamgÃÂ¥rd in his PhD thesis The Application of Claw Free Functions in Cryptography (Aarhus University, 1988), where he showed how to construct Collision Resistant Hash Functions from claw-free permutations. The notion of claw-freeness is closely related to that of collision resistance in hash functions. The distinction is that claw-free permutations are pairs of functions in which it is hard to create a collision between them, while a collision-resistant hash function is a single function in which it's hard to find a collision, i.e. a function H is collision resistant if it's hard to find a pair of distinct values x,y such that
In the hash function literature, this is commonly termed a hash collision. A hash function where collisions are difficult to find is said to have collision resistance.
Given a pair of claw-free permutations f<sub>0</sub> and f<sub>1</sub> it is straightforward to create a commitment scheme. To commit to a bit b the sender chooses a random x, and calculates f<sub>b</sub>(x). Since both f<sub>0</sub> and f<sub>1</sub> share the same domain (and range), the bit b is statistically hidden from the receiver. To open the commitment, the sender simply sends the randomness x to the receiver. The sender is bound to his bit because opening a commitment to 1 − b is exactly equivalent to finding a claw. Notice that like the construction of Collision Resistant Hash functions, this construction does not require that the claw-free functions have a trapdoor.