  We propose a general way of constructing zero-knowledge 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
zero-knowledge authentication schemes where forgery (a.k.a. impersonation) is
NP-hard. Computationally hard problems that can be employed in these
realizations include (Sub)graph Isomorphism, Graph Colorability, Diophantine
Problem, and many others.
