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 $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.[1] 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}]{|A|\cdot |B|}}$ .[2]

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

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.
Currently best known attack against supersingular isogeny key exchange is finding a claw on the isogeny graph.[4]

References

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.
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.
Zhang, Shengyu (2005). "Promised and Distributed Quantum Search". Computing and Combinatorics. Lecture Notes in Computer Science. 3595. Springer Berlin Heidelberg. pp. 430–439. doi:10.1007/11533719_44. ISBN 978-3-540-28061-3.
De Feo, Luca; Jao, Plut (2011). "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" (PDF). PQCrypto 2011. Lecture Notes in Computer Science. Springer. 7071: 19–34. CiteSeerX 10.1.1.359.5262. doi:10.1007/978-3-642-25405-5_2. ISBN 978-3-642-25404-8. Retrieved 15 Dec 2019.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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. 3595. Springer Berlin Heidelberg. pp. 430–439. doi:10.1007/11533719_44. ISBN 978-3-540-28061-3.

[4] De Feo, Luca; Jao, Plut (2011). "Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" (PDF). PQCrypto 2011. Lecture Notes in Computer Science. Springer. 7071: 19–34. CiteSeerX 10.1.1.359.5262. doi:10.1007/978-3-642-25405-5_2. ISBN 978-3-642-25404-8. Retrieved 15 Dec 2019.