In the mathematical and

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

field of

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

, 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

Goldwasser Goldwasser ("Gold water from Gdańsk"), pol. Wódka Gdańska, with Goldwasser as the registered tradename, is a strong (40% ABV) root and herbal liqueur which was produced from 1598 to 2009 in Gdańsk. Production now takes place in Germany. Th ...

, Micali, and

Rivest Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Intell ...

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 A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents. A valid digital signature, where the prerequisites are satisfied, gives a recipient very high confidence that the message was created b ...

. This construction was later superseded by the construction of digital signatures from any one-way trapdoor permutation. The existence of

trapdoor permutation In theoretical computer science and cryptography, a trapdoor function is a function that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) without special information, called the "tra ...

s 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 Ivan Bjerre Damgård (born 1956) is a Danish cryptographer and currently a professor at the Department of Computer Science, Aarhus University, Denmark. Academic background In 1983, he obtained a master's degree in mathematics (with minors in ...

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 :''H''(''x'') = ''H''(''y''). In the hash function literature, this is commonly termed a

hash collision In computer science, a hash collision or hash clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Al ...

. A hash function where collisions are difficult to find is said to have

collision resistance In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ '' ...

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.

Bit commitment

References

Further reading