Authentication schemes from actions on graphs, groups, or rings

Dima Grigoriev; Vladimir Shpilrain

Paper 2010/024

Authentication schemes from actions on graphs, groups, or rings

Dima Grigoriev and Vladimir Shpilrain

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: authentication one-way function NP-hard
Contact author(s): shpil @ groups sci ccny cuny edu
History: 2010-01-16: received
Short URL: https://ia.cr/2010/024
License: CC BY

BibTeX

@misc{cryptoeprint:2010/024,
      author = {Dima Grigoriev and Vladimir Shpilrain},
      title = {Authentication schemes from actions on graphs, groups, or rings},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/024},
      year = {2010},
      url = {https://eprint.iacr.org/2010/024}
}