Claw-free permutation

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

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

A pair of permutations f₀ and f₁ are said to be claw-free if there is no efficient algorithm for computing a claw.

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] (Note: Please verify this claim: the phrase claw-free appears in a 1984 publication by Goldwasser, Micali, and Rivest ^[2])

In his original work, Damgård constructed Collision Resistant Hash Functions from claw-free permutations. In subsequent work^[3], the existence of claw-free permutations with trapdoors was proven to imply secure digital signatures, for which existential forgery is not possible. This construction was later superseded by the construction of digital signatures from any one-way trapdoor permutation^[4]. The existence of trapdoor permutations does not by itself imply claw-free permutations exist^[5]; however, it has been shown that claw-free permutations do exist if factoring is hard.

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

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.

Constructions

Bit commitment

Given a pair of claw-free permutations f₀ and f₁ it is straightforward to create a commitment scheme. To commit to a bit b the sender chooses a random x, and calculates f_b(x). Since both f₀ and f₁ 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.

References

1. ^ Collision Free Hash Functions and Public Key Signature Schemes Ivan Damgard, EUROCRYPT '87
2. ^ A Paradoxical Solution to the Signature Problem, Shafi Goldwasser, Silvio Micali, Ronald L. Rivest, Proceedings of FOCS, pp. 441–448, 1984
3. ^ Takeshi Koshiba, Self-Definable Claw Free Functions, 1996.
4. ^ 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.
5. ^ On the Power of Claw-Free Permutations Yevgeniy Dodis, Leonid Reyzin, 2002
6. ^ How to sign given any trapdoor permutation Mihir Bellare, Silvio Micali.