Claw finding problem

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

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

${\displaystyle {\sqrt[{3}]{|A|\cdot |B|}}}$ if ${\displaystyle |A|\leq |B|<|A|^{2}}$ and

${\displaystyle {\sqrt {|B|}}}$ if ${\displaystyle |B|\geq |A|^{2}}$.^[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:

• 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.