Lester Hill’s “The checking of the accuracy …”, part 14

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the 15th section of his paper. I hope to post more later. (Part 14 is here.)


 

Lemma concerning reference matrices

The general reference matrix of Section 3 was:

Q =   \left(  \begin{array}{cccc}  k_{11} & k_{12} &  \dots & k_{1n} \\  k_{21} & k_{22} &  \dots & k_{2n} \\  \vdots & & & \vdots \\  k_{q1} & k_{q2} &  \dots & k_{qn} \\  \end{array}  \right)
the k_{ij} being elements of any given finite algebraic field F, and q being less than or equal to n.

This matrix contains determinants of order r with r=1,2,\dots, q — determinants of first order (r=1) being single elements of the matrix.

We recall that if f_1, f_2, \dots, f_{s} is an s element operand
sequence in F, a t-element check based upon the matrix Q is:

c_j = \sum_{i=1}^{s} k_{ji} f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).
it being understood that s\leq n, t\leq q.

Let Q contain no vanishing determinant of any order: Let c_1, c_2, \dots, c_{t} be a t-element check, t\leq q, on the operand sequence f_1, f_2, \dots, $f_{s}$, $s\leq n$. Let v be a positive integer less than or equal to s+t. If, in the transmittal of the sequence

f_1, f_2, \dots, f_{s}, c_1, c_2, \dots, c_{t},
errors occur in v of its s+t elements, whatever the distribution of the errors, the presence of error will certainly be disclosed, or will enjoy only a 1-in-(\Gamma-1)^t chance of escaping disclosure, according as $v$ is, or is not, less than t+1. In this statement, \Gamma denotes the total number of elements in the field F.

proof:
Case 1:
Let all v errors fall among the c_1, c_2, \dots, c_{t}. The presence of error is evidently certain to be disclosed.

Case 2:
Let all v errors fall among the $f_1, f_2, \dots, f_{s}$.

(2.1): Let v\leq t. There is no loss of generality of we assume [This assumption implies v\leq s. – wdj] the $v$ errors are \epsilon_1, \epsilon_2, \dots, \epsilon_v, affecting f_1, f_2, \dots, f_{v}. The errors cannot escape disclosure. For, to do so, they would have to satisfy the system of homogeneous linear equations:

\sum_{i=1}^{v} k_{ji} \epsilon_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).
in which the matrix of coefficients k_{ji} contains no vanishing determinant of any order, and which, therefore admits no solution other than \epsilon_i=0 (i = 1, 2, \dots, v).

For this treatment of the errors, compare Sections 4, 5.

Case 3:
Let z errors fall among the f_i and w=v-z errors fall among the c_j. Without loss in generality, we may assume that the errors are \epsilon_1, \epsilon_2, \dots, \epsilon_z, affecting f_1, f_2, \dots, f_{z}, and \delta_{j_1}, \delta_{j_2}, \dots, \delta_{j_w}, affecting c_{j_1}, c_{j_2}, \dots, c_{j_w}.

(3.1): Let z+w\leq t. Writing t=v+h=z+w+h, where h denotes a non-negative integer which may or may not be zero, we have t-w = z+h. Hence z+h of the c_j are transmitted without error.

If the presence of error is to escape disclosure, we see, therefore, that the z errors $\epsilon_i$ must satisfy the system of at least z homogeneous linear equations:

\sum_{i=1}^{z} k_{r_m,i} \epsilon_i,\ \ \ \ \ \ \ (m = 1, 2, \dots, z+h),
where the indices r_m denote a set of z+h integers selected from 1, 2, \dots, t. But the matrix of coefficients in this system contains no vanishing determinant, so that the only solution would be \epsilon_i=0 (i = 1, 2, \dots, z).

For details in this treatment of errors, see Section \ref{sec:5}.

(3.2): Let z+w> t. Then w = t-(z-h), where $h$ denotes a positive integer. Assuming that the presence of error is to escape detection, we see, therefore, that the v errors must satisfy t linear equations as follows:

(\alpha) a system of z-h equations involving only the errors \epsilon_i, (i = 1, 2, \dots, z), and homogeneous in these $z$ errors;

(\beta) a system of w equations involving all v errors.

Since the matrix of the coefficients in the system (\alpha) contains no vanishing determinant, we can solve this system for $z-h$ of the $\epsilon_i$ as rational functions of the remaining h of the \epsilon_i.

The system (\beta) determines all errors affecting the c_j — that is, all the errors \delta_{j_i} — as polynomial functions of the \epsilon_i, (i = 1, 2, \dots, z).

Hence, all told, (z-h)+w errors are determined as rational functions of the remaining h errors. In other words, v-t errors determine the other $t$ errors.

An accidental error can assume any one of $\Gamma -1$ values, there being \Gamma elements in the finite field F. Hence the chance that the errors will check up, and thus escape disclosure, is only 1-in-(\Gamma-1)^t.
QED

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s