International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Authentication schemes from actions on graphs, groups, or rings

Authors:
Dima Grigoriev
Vladimir Shpilrain
Download:
URL: http://eprint.iacr.org/2010/024
Search ePrint
Search Google
Abstract: We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include Graph Colorability, Diophantine Problem, and many others.
BibTeX
@misc{eprint-2010-22925,
  title={Authentication schemes from actions on graphs, groups, or rings},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / authentication, one-way function, NP-hard},
  url={http://eprint.iacr.org/2010/024},
  note={ shpil@groups.sci.ccny.cuny.edu 14624 received 15 Jan 2010},
  author={Dima Grigoriev and Vladimir Shpilrain},
  year=2010
}