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]\displaystyle{ A, B, C }[/math] be finite sets, and [math]\displaystyle{ f: A \to C }[/math], [math]\displaystyle{ g: B \to C }[/math] two functions. A pair [math]\displaystyle{ (x,y) \in A \times B }[/math] is called a claw if [math]\displaystyle{ 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]\displaystyle{ f, g }[/math] as random functions, we expect a claw to exist iff [math]\displaystyle{ |A| \cdot |B| \geq |C| }[/math]. More accurately, there are exactly [math]\displaystyle{ |A| \cdot |B| }[/math] pairs of the form [math]\displaystyle{ (x,y) }[/math] with [math]\displaystyle{ x \in A, y \in B }[/math]; the probability that such a pair is a claw is [math]\displaystyle{ 1/|C| }[/math]. So if [math]\displaystyle{ |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. The algorithm works as follows: assume [math]\displaystyle{ |A| \leq |B| }[/math]. For every [math]\displaystyle{ x \in A }[/math], save the pair [math]\displaystyle{ (f(x),x) }[/math] in a hash table indexed by [math]\displaystyle{ f(x) }[/math]. Then, for every [math]\displaystyle{ y \in B }[/math], look up the table at [math]\displaystyle{ g(y) }[/math]. If such an index exists, we found a claw. This approach takes time [math]\displaystyle{ O(|A| + |B|) }[/math] and memory [math]\displaystyle{ O(|A|) }[/math].

If quantum computers are used, Seiichiro Tani showed that a claw can be found in complexity

[math]\displaystyle{ \sqrt[3]{|A|\cdot|B|} }[/math] if [math]\displaystyle{ |A|\le|B|\lt |A|^2 }[/math] and

[math]\displaystyle{ \sqrt{|B|} }[/math] if [math]\displaystyle{ |B|\ge|A|^2 }[/math].

Shengyu Zhang showed that asymptotically these algorithms are the most efficient possible.

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 2^k/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.