**Zero Knowledge with Rubik's Cubes and Non-Abelian Groups**

*Emmanuel VOLTE and Jacques PATARIN and Valérie NACHEF*

**Abstract: **The factorization problem in non-abelian groups is still an open and a difficult problem. The Rubik's cube is a famous group that illustrates the hardness of the problem. We will define a public key identification scheme based on this problem, in the case of the Rubik's cube, when the number of moves is fixed to a given value. Our scheme consists of an interactive protocol which is zero-knowledge argument of knowledge under the assumption of the existence of a commitment scheme. We will see that our scheme works with any non-abelian groups with a set of authorized moves that has a specific property. Then we will generalize the scheme for larger Rubik's cubes and for any groups.

**Category / Keywords: **zero-knowledge, Rubik's cube, authentication, symmetric group, cryptographic protocol, factorization

**Date: **received 2 Apr 2012, last revised 9 Dec 2012

**Contact author: **emmanuel volte at u-cergy fr, valerie nachef@u-cergy fr

**Available format(s): **PDF | BibTeX Citation

**Note: **The scheme has been simplified, there are more references to other existing papers, and the scheme has been extended to non-abelian groups.

**Version: **20121209:164808 (All versions of this report)

**Short URL: **ia.cr/2012/174

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]