Cryptology ePrint Archive: Report 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.
Category / Keywords: Authentication, Coxeter groups, identification protocols, random spanning trees, word problem
Date: received 3 Sep 2010, last revised 27 Jan 2011
Contact author: gmorales at cs cinvestav mx
Available format(s): PDF | BibTeX Citation
Note: A flaw has been corrected. It is necessary to fix a threshold for the lengths of the responses to the challenges.
Version: 20110127:122818 (All versions of this report)
Short URL: ia.cr/2010/470
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]