Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / authentication, one-way function, NP-hard

Date: received 15 Jan 2010

Contact author: shpil at groups sci ccny cuny edu

Available formats: PDF | BibTeX Citation

Version: 20100116:062629 (All versions of this report)

Discussion forum: Show discussion | Start new discussion