Claw-free permutation
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 f0 and f1 if
A pair of permutations f0 and f1 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. (Note: Please verify this claim: the phrase claw-free appears in a 1984 publication by Goldwasser, Micali, and Rivest )
In his original work, Damgård constructed Collision Resistant Hash Functions
from claw-free permutations. In subsequent work, 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. 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 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 educe is said to have collision resistance
.
. To commit to a bit b the sender chooses a random x, and calculates fb(x). Since both f0 and f1 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
field of cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a group of three numbers (x,y,z) is said to be a claw of two permutations f0 and f1 if
- f0(x) = f1(y) = z.
A pair of permutations f0 and f1 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
Ivan Damgård
Ivan Bjerre Damgård is a Danish cryptographer and currently a professor at the Department of Computer Science , Aarhus University, Denmark....
in his PhD thesis The Application of Claw Free Functions in Cryptography, Aarhus University, 1988. (Note: Please verify this claim: the phrase claw-free appears in a 1984 publication by Goldwasser, Micali, and Rivest )
In his original work, Damgård constructed Collision Resistant Hash Functions
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
from claw-free permutations. In subsequent work, 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. 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 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
Hash collision
Not to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest....
. A hash function where collisions are difficult to educe is said to have collision resistance
Collision resistance
Collision resistance is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H = H, and a ≠ b.Every hash function with more inputs than outputs will necessarily have...
.
Bit commitment
Given a pair of claw-free permutations f0 and f1 it is straightforward to create a commitment schemeCommitment scheme
In cryptography, a commitment scheme allows one to commit to a value while keeping it hidden, with the ability to reveal the committed value later. Commitments are used to bind a party to a value so that they cannot adapt to other messages in order to gain some kind of inappropriate advantage...
. To commit to a bit b the sender chooses a random x, and calculates fb(x). Since both f0 and f1 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.