Sebery J.Cryptography.An introduction to computer security.1989

other third observation breaks the A-code and allows Oscar to determine the encoding rule used.

8.4.2 A-codes and Orthogonal Arrays

Orthogonal arrays (OA) are combinatorial designs that are ideally suited for the design of A-codes without secrecy (Cartesian A-codes). There is also a strong relation between orthogonal arrays and projective spaces. Indeed, one of the general methods used to construct orthogonal arrays applies projective spaces.

De nition 24. An orthogonal array OA (t; n; k) is a kt n array of k symbols such that for any t columns of the array, every one of the possible kt ordered t-tuples of symbols occurs in exactly rows.

Assume we assign elements of an A-code to components of OA as follows:

{An encoding rule identi es the unique row.

{A message (source state) labels the unique column.

{A tag is a symbol.

Clearly, we can conclude that for every OA there is the corresponding Cartesian A-code.

Theorem 36. (Stinson [496]) Given an orthogonal array OA (t; n; k), then there is a Cartesian A-code hS; M; Ei such that E = kt, S = n, T = k, M = nk, and the probabilities of deception pi = T 1 = k 1 for i = 0; 1; : : : ; t 1.

Consider OA1(2; 4; 3). It can be used to design an A-code of the form given in Table 8.4. If Oscar observes the cryptogram (s3; 2), he can deduce that the applied encoding rule e 2 fe3; e5; e7g. His chances of success are no better than random selection of a tag from the set f0; 1; 2g for any fraudulent cryptogram. Any other second observation breaks the A-code.

Theorem (36) asserts that any orthogonal array corresponds to an A-code. In many practical, situations we would like to know whether a given A-code can be obtained from an orthogonal array. More precisely, we know the set of source states S and require the deception probabilities to be smaller than " (pi " for i = 0;1; : : : ; r). We are looking for an OA which produces an A-code whose construction is in a sense \minimal," i.e. contains the smallest possible collection of tags and encoding rules and satis es the imposed conditions. This problem can be translated into the language of combinatorics. Given the parameter n

322 8 AUTHENTICATION

EnM s1 s2 s3 s4

e1 0 0 0 0

e2 0 1 1 2

e3 0 2 2 1

e4 1 0 1 1

e5 1 1 2 0

e6 1 2 0 2

e7 2 0 2 2

e8 2 1 0 1

e9 2 2 1 0

Table 8.4. The authentication matrix of an A-code based on OA1 (2; 4; 3)

and conditions t r + 1, and k " 1, what is the \smallest" OA (t; n; k)? A discussion of this problem can be found in [497].

8.4.3 A-codes Based on Error Correcting Codes

Error correcting codes (E-codes) were invented to detect and hopefully correct errors that occurred during the transmission of messages via a noisy channel [318].

Given a vector space Vn over GF (q). A vector v = (v1; : : : ; vn) 2 Vn contains n coordinates from GF (q) (vi 2 GF (q) for i = 1; : : : ; n). The Hamming distance between two vectors x; y 2 Vn is the number of coordinates in which the two vectors di er. The number is denoted by d(x; y).

An (n; `; d) E-code is a set of ` vectors from Vn such that the Hamming distance between any two vectors is at least d. The set of all codewords is denoted C. Clearly j C j= `.

Johansson, Smeets, and Kabatianskii [263] investigated the relation between A-codes and E-codes. Their observations are summarized in the following two theorems. The rst theorem indicates how A-codes with the requested probability of substitution p1 can be implemented using E-codes.

Theorem 37. Given an hS; M; Ei A-code with uniform selection of both messages and encoding rules and with the probabilities p0 = T 1 and p1 = ". Then there exists a corresponding (n; `; d) E-code with the parameters n = E,

` = q(q 1)S + q and d = E(1 ").

The next theorem identi es a class of E-codes which corresponds to A-codes with protection against substitution.

Theorem 38. Assume there is an E-code C over GF (q) with parameters (n; `; d) such that if c 2 C then c + 1 2 C for all 2 GF (q). Then there exists a cor-

responding Cartesian A-code hS; M; Ei with parameters S = `q 1, E = nq and probabilities p0 = q 1, p1 = 1 nd .

In contrast to combinatorial designs, E-codes o er an relatively eÆcient implementation tool for A-codes that are perfect under substitution.

8.5 General A-codes

If we drop the restriction on the set of cryptograms, then the general A-code is a collection hS;M;Ei with M S. As previously, the active opponent Oscar has access to the communication channel. Alice sends to Bob a pair consisting of a message s and the corresponding cryptogram m. After receiving the pair (s0; m0) from the channel and knowing the secret encoding rule, Bob recovers the message from the cryptogram m0 and compares it with the message s0. If they are equal, he accepts the pair as genuine. Oscar may try impersonation, substitution, or spoo ng attacks. General A-codes can also be analyzed using the game model. As previously, the spoo ng game (which covers also impersonation and substitution) is played between communicants (Alice and Bob) and the opponent (Oscar). Oscar knows the A-code (the authentication matrix is public) and observes r pairs of (message, cryptogram).

An A-code is r-fold secure against spoo ng if the values of the games pi (or probabilities of deception) are

pi = S i M i

for i = 0; : : : ; r. Readers interested in details of game model are referred to [472, 473, 476]. The combinatorial nature of A-codes is studied in [444, 492, 493, 494]. Bounds for probabilities of deception are investigated in [31, 262, 261, 434, 482, 518]. A-codes and their resistance against spoo ng are examined in [442, 443, 509].

324 8 AUTHENTICATION

EnS s1 s2 s3

e1 1 2 3

e2 2 3 1

e3 3 1 2

e4 1 3 2

e5 3 2 1

e6 2 1 3

Table 8.5. Authentication matrix

Table 8.6. Incidence matrix

8.6 Problems and Exercises

1.Given an A-code in the form of its authentication matrix shown in Table 8.5, determine

the set of encoding rules E, the set of tags T , the set of source states S and the set of cryptograms M. Assume that the communicants have agreed to use the encoding rule e3. What are cryptograms for all possible messages? Is the cryptogram (s1; 2) valid?

2.Write an incidence matrix for the A-code given in Table 8.5.

3.Consider again the code in Table 8.5. Suppose that an attacker, Oscar knows that communicants use the strategy

= ( e1 ; : : : ; e6 ) = ( 121 ; 123 ; 121 ; 124 ; 122 ; 121 )

What are conditional probabilities payo (mi) for all possible cryptograms mi? What are conditional probabilities payo (mi) when Alice and Bob select encoding rules with

uniform probabilities (so = (16 ; 16 ; 16 ; 16 ; 16 ; 16 ))? Discuss the results in the context of impersonation attack.

4.Table 8.2 shows an A-code with four cryptograms and four encoding rules. Analyze

the code under the substitution attack. In particular, compute conditional probabilities payo (m; m0) for the two following strategies: = ( 18 ; 18 ; 28 ; 48 ) and = ( 14 ; 14 ; 14 ; 14 ). Discuss possible strategies for Oscar.

5.The incidence matrix in Table 8.6 shows an A-code with fourteen encoding rules and six cryptograms. Analyze the code under the spoo ng attack of order 2. Compute conditional

its properties in the context of impersonation, substitution and spoo ng attacks.

9 SECRET SHARING

Secret sharing becomes indispensable whenever secret information needs to be kept collectively by a group of participants in such a way that only a quali ed subgroup is able to reconstruct the secret. An example of such scheme is a (t; n) threshold secret sharing in which there are n participants holding their shares of the secret and every t (t n) participants can collectively recreate the secret while any (t 1) participants cannot get any information about the secret. The need for secret sharing arises if the storage system is not reliable so that there is a high likelihood that some pieces of information will be lost. Secret sharing is also useful if the owner of the secret does not trust any single person. Instead, the owner can deposit the secret with a group so that only a suÆciently large subgroup of members can reconstruct the secret. Threshold schemes were independently proposed by Blakley [41] and Shamir [465].

9.1 Threshold Secret Sharing

A (t; n) threshold secret sharing scheme distributes a secret among n participants in such a way that any t of them can recreate the secret, but any t 1 or fewer members gain no information about it. The piece held by a single participant is called a share of the secret. Secret sharing schemes are normally set up by a trusted authority who computes all shares and distributes them to participants via secure channels. The trusted authority who sets up the scheme is called a dealer. The participants hold their shares until some of them decide to pool their shares and recreate the secret. The recovery of the secret is done by the so-called combiner who on behalf of the cooperating group computes the secret. The combiner is successful only if the cooperating group has at least t members. The combiner can be collective, i.e. all active participants show to each other their shares so that any active participant can calculate the secret.

328 9 SECRET SHARING

The combiner can also be a mutually trusted participant who collects all shares, calculates the secret, and distributes it secretly to the active participants.

Assume that secrets belong to the set K and shares are from the set S. Let Si be the set from which the dealer draws shares for the participant Pi; i = 1; : : : ; n. The set of all participants P = fP1; : : : ; Png.

De nition 25. A (t; n) threshold scheme is a collection of two algorithms. Therst algorithm called the dealer

D : K ! S1 S2 Sn

assigns shares to the participants for a secret k 2 K. The share si 2 Si is communicated via a secure channel to the participant Pi. If all share sets Si are equal we simply say that si 2 S.

The second algorithm (the combiner)

C : Si1 Si2 Sij ! K

takes an arbitrary collection of shares and attempts to compute the secret. The combiner recovers the secret successfully only if the number j of di erent shares is greater or equal to t (j t). It fails if the number j of shares is smaller than t (j < t).

A (t; n) threshold scheme is perfect if any (t 1) shares provide no information about the secret. Note that secret sharing schemes are normally intended to be used one time only. Once the secret has been recreated the scheme is e ectively no longer in existence.

9.1.1 (t; t) Threshold Schemes

Karnin, Greene, and Hellman [269] studied (t; t) threshold sharing. The secret can be recovered only when all participants cooperate. The implementation of (t; t) schemes can be done as follows.

Let the secret integer k be given. The dealer chooses a modulus p that can be any integer bigger than k. Its value determines the security parameter. Next

i=1

Obviously, any (t 1) or fewer shares provide no information about the secret k.

9.1.2 Shamir Scheme

Shamir [465] used Lagrange polynomial interpolation to design (t; n) threshold schemes. All calculations are done in GF (p) where the prime p is a big enough integer (so the secret is always smaller than p).

A (t; n) Shamir scheme is constructed by the dealer Don. First Don chooses n di erent points xi 2 GF (p) for i = 1; : : : ; n. These points are public. Next

Don selects at random coeÆcients a0; : : : ; at 1 from GF (p). The polynomial f(x) = a0 + a1x + : : : + at 1xt 1 is of degree at most (t 1). The shares are si = f(xi) for i = 1; : : : ; n, and the secret is k = f(0). The share si is distributed to the participant Pi 2 P via a secure channel and is kept secret.

When t participants agree to cooperate, the combiner Clara takes their shares and tries to recover the secret polynomial f(x). She knows t points on the curve f(x)

(xij ; f(xij )) = (xij ; sij ) for j = 1; : : : ; t:

These points produce the following system of equations:

330 9 SECRET SHARING

is a Vandermonde determinant di erent from zero. The Lagrange interpolation formula allows to determine the polynomial f(x) of degree (t 1) from the t di erent points (xij ; sij ), thus

The secret k = f(0), therefore we obtain

If Clara knows (t 1) shares, she cannot nd the unique solution for k = a0 as the system (9.2) contains (t 1) equations with t unknowns. The security is discussed later.

Consider a simple (3; 6) Shamir scheme over GF (7). The dealer selects six public numbers, say xi = i for i = 1; : : : ; 6, and a random polynomial of degree at most 2. Let it be f(x) = 5 + 3x + 2x2. Shares are

s1 = f(x1) = 3; s2 = f (x2) = 5; s3 = f(x3) = 4; s4 = f (x4) = 0; s5 = f(x5) = 0; s6 = f (x6) = 4:

The shares are sent to the corresponding participants in a secure way. Assume that three participants P1, P3 and P6 cooperate and have revealed

their shares to the combiner. Clara solves the following system of equations: 3 = a0 + a1 + a2

4= a0 + 3a1 + 2a2

4= a0 + 6a1 + a2

According to the Lagrange interpolation formula, the coeÆcients b1 = 6, b2 = 6, and b3 = 3 and the secret k = a0 = b1s1 + b2s3 + b3s6 = 5.