Two identification protocols based on Cayley graphs of Coxeter groups

Feliú Sagols; Guillermo Morales-Luna

Paper 2010/470

Two identification protocols based on Cayley graphs of Coxeter groups

Feliú Sagols and Guillermo Morales-Luna

Abstract

A challenge-response identification protocol is introduced, based on the intractability of the word problem in some Coxeter groups. A Prover builds his public key as the set of leaves of a tree in the Cayley graph of a Coxeter group, and the tree itself is his private keys. Any challenge posed by a Verifier consists of a subset of the public key, and the Prover shows his knowledge of the private key by providing a subtree having as set of leaves the challenge set. Any third party aiming to impersonate the Prover faces a form of the word problem in the Coxeter group. Although this protocol maintains the secrecy of the whole private key, it is disclosing some parts of it. A second protocol is introduced which is indeed a transcription of the already classical zero-knowledge protocol to recognize pairs of isomorphic graphs.

Note: A flaw has been corrected. It is necessary to fix a threshold for the lengths of the responses to the challenges.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Authentication Coxeter groups identification protocols random spanning trees word problem
Contact author(s): gmorales @ cs cinvestav mx
History: 2011-01-27: revised; 2010-09-08: received; See all versions
Short URL: https://ia.cr/2010/470
License: CC BY

BibTeX

@misc{cryptoeprint:2010/470,
      author = {Feliú Sagols and Guillermo Morales-Luna},
      title = {Two identification protocols based on Cayley graphs of Coxeter groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/470},
      year = {2010},
      url = {https://eprint.iacr.org/2010/470}
}