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 is NP-hard. Computationally hard problems that can be employed in these realizations include the Graph Colorability problem, the Diophantine problem, and many others