International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 11 April 2012

Emmanuel VOLTE, Jacques PATARIN, Valérie NACHEF
ePrint Report ePrint Report
Since the invention of the Rubik\'s cube by Ern\\\"o~Rubik in $1974$, similar puzzles have been produced, with various number of faces or stickers. We can use these toys to define several problems in computer science, such as go from one state of the puzzle to another one. In this paper, we will classify some of these problems based on the classic Rubik\'s cube or on generalized Rubik\'s Cube. And we will see how we can use them in Zero Knowledge Authentication with a public key in order to achieve a given complexity against the best known attacks (for example $2^{80}$ computations). The efficiency of these schemes, and their possible connection with

NP-complete problems will also be discussed.

Expand

Additional news items may be found on the IACR news page.