You are looking at a specific version 20110127:122818 of this paper. See the latest version.

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
AuthenticationCoxeter groupsidentification protocolsrandom spanning treesword 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.