Paper 2011/638

Rubik's for cryptographers

Christophe Petit and Jean-Jacques Quisquater


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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
christophe petit @ uclouvain be
2011-11-26: received
Short URL
Creative Commons Attribution


      author = {Christophe Petit and Jean-Jacques Quisquater},
      title = {Rubik's for cryptographers},
      howpublished = {Cryptology ePrint Archive, Paper 2011/638},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.