Claw finding problem explained

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

A, B, C be finite sets, and f: A \to C , g: B \to C two functions. A pair (x,y) \in A x B is called a claw if f(x) = g(y) . The claw finding problem is defined as to find such a claw, given that one exists.

If we view

f, g as random functions, we expect a claw to exist iff |A| ⋅ |B| \geq |C| . More accurately, there are exactly |A| ⋅ |B| pairs of the form (x,y) with x \in A, y \in B ; the probability that such a pair is a claw is 1 /|C| . So if |A| ⋅ |B| \geq |C| , 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

|A| \leq |B| . For every x \in A , save the pair (f(x),x) in a hash table indexed by f(x) . Then, for every y \in B , look up the table at g(y) . If such an index exists, we found a claw. This approach takes time O(|A| + |B|) and memory O(|A|) .

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

\sqrt[ 3 ]{|A| ⋅ |B|} if |A|\le|B|<|A| ^{2} and \sqrt{|B|} if |B|\ge|A| ^{2} .^[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 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.

Notes and References

1. Diffie. Whitfield. Hellman. Martin E.. June 1977. Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Computer. 10. 6. 74–84. 10.1109/C-M.1977.217750.
2. Tani . Seiichiro . Claw Finding Algorithms Using Quantum Walk . Theoretical Computer Science . 410 . 50 . 5285–5297 . 10.1016/j.tcs.2009.08.030 . November 2009. 0708.2584 .
3. Book: Zhang . Shengyu . Computing and Combinatorics . 3595 . Promised and Distributed Quantum Search . Springer Berlin Heidelberg . 430–439 . en . 10.1007/11533719_44 . 2005. Lecture Notes in Computer Science . 978-3-540-28061-3 .