Welcome to the resource topic for 2011/638
Title:
Rubik’s for cryptographers
Authors: Christophe Petit, Jean-Jacques Quisquater
Abstract:Hard mathematical problems are at the core of security arguments in cryptography. In this paper, we study mathematical generalizations of the famous Rubik’s cube puzzle, namely the factorization, representation and balance problems in non-Abelian groups. These problems arise naturally when describing the security of Cayley hash functions, a class of cryptographic hash functions with very interesting properties. The factorization problem is also strongly related to a famous long-standing conjecture of Babai, at the intersection of group theory and graph theory. A constructive proof of Babai’s conjecture would make all Cayley hash functions insecure, but on the other hand it would have many positive applications in graph theory and computer science. In this paper, we classify existing attacks against Cayley hash functions and we review known results on Babai’s conjecture. Despite recent cryptanalytic progress on particular instances, we show that the factorization, representation and balance problems presumably remain good sources of cryptographic hard problems. Our study demonstrates that Cayley hash functions deserve further interest by the cryptography community.
ePrint: https://eprint.iacr.org/2011/638
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .