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.
Let
,
{\displaystyle A,B,C}
be finite sets, and
two functions.
A pair
is called a claw if
The claw finding problem is defined as to find such a claw, given that one exists.
If we view
as random functions, we expect a claw to exist iff
More accurately, there are exactly
pairs of the form
; the probability that such a pair is a claw is
, the expected number of claws is at least 1.
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
, save the pair
in a hash table indexed by
, look up the table at
If such an index exists, we found a claw.
This approach takes time
and memory
If quantum computers are used, Seiichiro Tani showed that a claw can be found in complexity
[2] Shengyu Zhang showed that asymptotically these algorithms are the most efficient possible.
[3] As noted, most applications of the claw finding problem appear in cryptography.
Examples include: