**Authentication code**

In a military system, authentication should be secure unconditionally. Note that we studied digital signatures and message authentication code in the crypto week. However, these schemes are generally conditionally secure. That is, it is only secure if the underlying assumption holds. For example, an RSA signature is secure against forgery attacks only if factorization is hard (which is only an assumption). Imagine then that a country uses the RSA digital signature authentication scheme to issue military commands and some other country has a secret method of forging RSA signatures. The result, obviously, would be disastrous. Thus for military usage, we need an unconditionally secure authentication method. In another words, we need an authentication method that is secure in the sense of information theory. A simple unconditionally secure authentication scheme can be constructed as follows. (Note that unconditionally secure authentication schemes are always symmetric).

Assume that Alice and Bob share two elements a and b from a finite field, e.g. from the set {1, 2, …, p-1} where p is a large prime. In order for Alice to send an authenticated message m to Bob (we assume that m is also an element from the same finite field), Alice could send the pair (m, am+b) to Bob. After receiving a message pair (m,c) from Alice, Bob checks whether c=am+b. If the equation holds, then Bob is assured that the message came from Alice, otherwise, Bob regards m as a forged message. A simple mathematical calculation shows that Carol, who knows nothing about the secret key (a,b), cannot forge any authenticated message no matter how much computation power she has. We should also note that one key pair (a,b) could only be used to authenticate one message, since if it is used twice, then Carol, who saw the two messages and their authenticators, could recover the secret key (a,b). You should also be aware that this kind of authentication method does not provide all properties such as those provided by the public key authentication method (e.g. digital signatures). However, for many military command systems, this authentication method is good enough.

**Shared control schemes**

Secret sharing schemes are widely used both in military and civilian systems. For example, control of nuclear weapons in Russia involves a two-out-of-three access mechanism. The three parties involved are the President, the Defense Minister, and the Defense Ministry. Threshold schemes like this one involve a special type of secret sharing. Formally, let t < n be positive integers, a t-out-of-n-threshold scheme is a method of sharing a key K among a set of n participants in such a way that any t participants can compute the value of K, but no group of t-1 participants can do so. Another commonly used shared control scheme is the Shamir secret sharing scheme that we describe here. Let P(x) be a random polynomial of degree t-1 in which the constant term is the secret key K.

Every participant Pi obtains a point (xi, yi) on this polynomial (that is, yi=P(xi)). Let us look at how a subset B of t participants can reconstruct the key. This is basically accomplished by means of polynomial interpolation.

Suppose that participant P1, P2, P3, …, and Pt want to determine K, they know that yi=P(xi)

for all 1 ≤ i ≤ t. Since P(x) has degree of t-1, P(x) can be written as P(x)=K+a1x+…+ at-1xt-1

where the coefficients K, a1, …, at-1 are unknown elements. Since yi=P(xi), we can obtain t linear equations in the t unknowns a1, …, at-1, where all arithmetic is done in the default field. If the equations are linearly independent, there will be a unique solution, and K will be revealed from these unknowns. Due to the Vandermonde property, these equations are linearly independent if these xi are chosen to be different.

**Example**. Suppose that t = 3, n = 5, and all the mathematical operations are carried out mod p = 17. Now assume that P1, P3, and P5 want to recover the secret key K and pool their shares, which are (1,8), (3,10), and (5,11) respectively. Writing the polynomial P(x) as

P(x)=K+a1x+ a2x2

And computing P(1), P(3), and P(5), the following three linear equations in Z17 are obtained:

K+ a1 + a2 = 8

K+3a1+ 9a2=10

K+5a1+ 8a2=11

This system does have a unique solution in Z17: K = 13, a1=10, a2=2. The key is therefore

K = 13.

A more general situation is to specify exactly which subsets of participants should be able to determine the key and which should not. We will not go into details here of these generalized access structures.

**Permissive action links (PAL)**

A ’Permissive Action Link’ is the box which is supposed to prevent unauthorized use of a nuclear weapon. For a detailed description of the history of PAL, types of PAL, cryptography and PAL, PAL and key management, and why PAL is classified, please see Bellovin’s paper.

Author : Yongge Wang