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.

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 \times 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| \cdot |B| \geq |C| . More accurately, there are exactly |A| \cdot |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| \cdot |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. 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] if |A|\le|B| and \sqrt if |B|\ge|A|^2 . 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. ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1156919373 under CC BY-SA 4.0; modifications have been made.