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 formula_1 be finite sets, and formula_2, formula_3 two functions. A pair formula_4 is called a "claw" if formula_5. The claw finding problem is defined as to find such a claw, given that one exists.
If we view formula_6 as random functions, we expect a claw to exist iff formula_7. More accurately, there are exactly formula_8 pairs of the form formula_9 with formula_10; the probability that such a pair is a claw is formula_11. So if formula_7, 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 formula_13. For every formula_14, save the pair formula_15 in a hash table indexed by formula_16. Then, for every formula_17, look up the table at formula_18. If such an index exists, we found a claw. This approach takes time formula_19 and memory formula_20.
If quantum computers are used, Seiichiro Tani showed that a claw can be found in complexity formula_21.
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: