Essentially s-fold secure authentication systems of level l

In this paper we introduce the notion of essentially s-fold secure authentication systems of level l (2 ≤ l ≤s). These are authentication systems in which the Bad Guy’schances to cheat after observing l messages are only O(1/K1/s+1)where K is the number of keys, and after s messages areonly O(1/K1/c(s+1)) for a suitable constant c. We construct a suitable class of essentially s-fold secure authentication systems of level l; these systems are defined by using algebraic varieties in finite projective spaces.