Paper 2012/174

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

Emmanuel VOLTE, 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.

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

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero-knowledgeRubik's cubeauthenticationsymmetric groupcryptographic protocolfactorization
Contact author(s)
emmanuel volte @ u-cergy fr
valerie nachef @ u-cergy fr
History
2012-12-09: revised
2012-04-11: received
See all versions
Short URL
https://ia.cr/2012/174
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/174,
      author = {Emmanuel VOLTE and Jacques PATARIN and Valérie NACHEF},
      title = {Zero Knowledge with  Rubik's Cubes and Non-Abelian Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2012/174},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/174}},
      url = {https://eprint.iacr.org/2012/174}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.