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

edit

Let   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   with  ; the probability that such a pair is a claw is  . So if  , the expected number of claws is at least 1.

Algorithms

edit

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  . For every  , save the pair   in a hash table indexed by  . Then, for every  , 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

  if   and

  if  .[2]

Shengyu Zhang showed that asymptotically these algorithms are the most efficient possible.[3]

Applications

edit

As noted, most applications of the claw finding problem appear in cryptography. Examples include:

References

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