ABSTRACT
We study authentication schemes with three participants in this chapter. When we say authentication schemes, we always mean the schemes with three participants in this chapter. The successful probability Pr of optimal spoofing attack of order r was introduced in Section 2.1. The information-theoretic lower bound of Pr and the necessary and sufficient conditions for achieving this bound will be given in Section 3.2 of this chapter. In order to discuss the information-theoretic bound, the important concept of information theory, entropy, is introduced in Section 3.1; some often used properties of entropy are proven. One important aim in constructing authentication schemes is to make Pr as small as possible. This aim is achieved at the expense of the use of a very large number of encoding rules. We also hope that the number of encoding rules can be as small as possible when we require Pr as small as possible. When Pr, 0 ≤ r < t achieve their information-theoretic bounds, the schemes are called t-fold key-entropy minimal, and when the number of encoding rules achieves its lower bound, the schemes are called (t-fold) perfect. It is proved in Section 3.3 that each perfect authentication scheme is always a key-entropy minimal and it corresponds to a strong partially balanced design (SPBD will be defined in Section 3.3), and vice versa, each SPBD can be used to construct a perfect authentication scheme. Thus, to construct perfect authentication schemes reduces to finding SPBD. We will construct a new family of SPBD, in order to construct a new family of perfect authentication schemes in Chapter 5.
