A new authentication scheme based on latin squares

✍ Scribed by J. Dénes; A.D. Keedwell

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 293 KB
• Volume: 106-107
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90543-o

✦ Synopsis

We propose a simple and flexible authentication scheme applicable for use with both binary and nonbinary messages and we show that, among the set of all possible messages of assigned length, all possible signatures occur with equal probability: that is, equally often. Additionally, our scheme allows calculation of the digits of the signature to be carried out in parallel.

1. The scheme outlined

The scheme proposed here may be used for both binary and nonbinary messages but, for the purposes of exposition, it is simplest to consider the nonbinary case first.

Let ala2 +-. a,, be a message over a q-ary alphabet Q which is required to be authenticated by means of a signature of s additional q-ary digits bI, bz, , . . , b,.

Let n = SC. We separate the message into s mutually disjoint subsets Si, i=l,2,..., s, of c not-necessarily-consecutive digits each. Each of these s subsets of message digits is used to calculate one of the digits bi. For the calculation, we make use of a latin square of order q.