Английская Википедия:Claw finding problem
The claw finding problem is a classical problem in complexity theory, with several applications in cryptography. In short, given two functions f, g, viewed as oracles, the problem is to find x and y such as f(x) = g(y). The pair (x, y) is then called a claw. Some problems, especially in cryptography, are best solved when viewed as a claw finding problem, hence any algorithmic improvement to solving the claw finding problem provides a better attack on cryptographic primitives such as hash functions.
Definition
Let <math>A, B, C</math> be finite sets, and <math>f: A \to C</math>, <math>g: B \to C</math> two functions. A pair <math>(x,y) \in A \times B</math> is called a claw if <math>f(x) = g(y)</math>. The claw finding problem is defined as to find such a claw, given that one exists.
If we view <math>f, g</math> as random functions, we expect a claw to exist iff <math>|A| \cdot |B| \geq |C|</math>. More accurately, there are exactly <math>|A| \cdot |B|</math> pairs of the form <math>(x,y)</math> with <math>x \in A, y \in B</math>; the probability that such a pair is a claw is <math>1/|C|</math>. So if <math>|A| \cdot |B| \geq |C|</math>, the expected number of claws is at least 1.
Algorithms
If classical computers are used, the best algorithm is similar to a Meet-in-the-middle attack, first described by Diffie and Hellman.[1] The algorithm works as follows: assume <math>|A| \leq |B|</math>. For every <math>x \in A</math>, save the pair <math>(f(x),x)</math> in a hash table indexed by <math>f(x)</math>. Then, for every <math>y \in B</math>, look up the table at <math>g(y)</math>. If such an index exists, we found a claw. This approach takes time <math>O(|A| + |B|)</math> and memory <math>O(|A|)</math>.
If quantum computers are used, Seiichiro Tani showed that a claw can be found in complexity
<math>\sqrt[3]{|A|\cdot|B|}</math> if <math>|A|\le|B|<|A|^2</math> and
<math>\sqrt{|B|}</math> if <math>|B|\ge|A|^2</math>.[2]
Shengyu Zhang showed that asymptotically these algorithms are the most efficient possible.[3]
Applications
As noted, most applications of the claw finding problem appear in cryptography. Examples include:
- Collision finding on cryptographic hash functions.
- Meet-in-the-middle attacks: using this technique, k bits of round keys can be found in time roughly 2k/2+1. Here f is encrypting halfway through and g is decrypting halfway through. This is why Triple DES applies DES three times and not just two.
References
