### 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
AuthenticationCoxeter groupsidentification protocolsrandom spanning treesword problem
Contact author(s)
gmorales @ cs cinvestav mx
History
2011-01-27: revised
See all versions
Short URL
https://ia.cr/2010/470

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},
note = {\url{https://eprint.iacr.org/2010/470}},
url = {https://eprint.iacr.org/2010/470}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.