My work that is being recognized by the 2015 ACM A. M. Turing Award is in cybersecurity, while my primary interest for the last thirty-five years is concerned with reducing the risk that nuclear deterrence will fail and destroy civilization. This Turing Lecture draws connections between those seemingly disparate areas as well as Alan Turing's elegant proof that the computable real numbers, while denumerable, are not effectively denumerable.

It is demonstrated that usual time-memory trade-offs offer no asymptotic advantage over exhaustive search. Instead, trade-offs between time, memory, and parallel processing are proposed. Using this approach it is shown that most searching problems allow a trade-off between C/sub s/, the cost per solution, and C/sub m/, the cost of the machine: doubling C/sub m/ increases the solution rate by a factor of four, halving C/sub s/. The machine which achieves this has an unusual architecture, with a number of processors sharing a large memory through a sorting/switching network. The implications of cryptanalysis, the knapsack problem, and multiple encryption are discussed.>

A "secret sharing system" permits a secret to be shared amongntrustees in such a way that anykof them can recover the secret, but anyk-1have complete uncertainty about it. A linear coding scheme for secret sharing is exhibited which subsumes the polynomial interpolation method proposed by Shamir and can also be viewed as a deterministic version of Blakley's probabilistic method. Bounds on the maximum value ofnfor a givenkand secret size are derived for any system, linear or nonlinear. The proposed scheme achieves the lower bound which, for practical purposes, differs insignificantly from the upper bound. The scheme may be extended to protect several secrets. Methods to protect against deliberate tampering by any of the trustees are also presented.

It is shown that the longest super-increasing sequence which can be constructed from a set ofnindependent uniformly distributed random variables is almost surely asymptotic to\log_{2}n. Some extensions of this result, as well as the implications for the security of knapsack-based cryptographic systems, are discussed.

In “New Directions in Cryptography”, Diffie and Hellman propose a public key distribution (PKD) system based on exponentiation in a discrete arithmetic system. The security of this technique is crucially dependent on the difficulty of computing discrete logarithms (the inverse of the discrete exponential function). Until recently, the best known method for computing discrete logs required running time which grew exponentially in the word size. However, Adleman has recently observed that certain fast algorithms for factoring integers are also applicable to computing discrete logs over GF(q), the Galois field with q elements (q denotes a prime number). He also noted that the running time for the modified algorithm should be of the same form as for factoring, namely

A probabilistic method is presented which cryptanalyzes anyNkey cryptosystem inN^{2/3}operational withN^{2/3}words of memory (average values) after a precomputation which requiresNoperations. If the precomputation can be performed in a reasonable time period (e.g, several years), the additional computation required to recover each key compares very favorably with theNoperations required by an exhaustive search and theNwords of memory required by table lookup. When applied to the Data Encryption Standard (DES) used in block mode, it indicates that solutions should cost between1 and100 each. The method works in a chosen plaintext attack and, if cipher block chaining is not used, can also be used in a ciphertext-only attack.

The wiretap channel introduced by Wyner is studied for the special case when the main channel is a noiseless binary channel and the wiretap channel is a binary symmetric channel. With a rate-one convolutional encoder, the steady-state uncertainty of the wiretapper is shown to depend only on the constraint lengthvof the code, not on the specific taps, and is complete on k successive bits providedk\leq v. During the initial transient period, the rate of growth of uncertainty does depend on the tap connections of the shift register.

Wyner's results for discrete memoryless wire-tap channels are extended to the Gaussian wire-tap channel. It is shown that the secrecy capacity Cs is the difference between the capacities of the main and wire.tap channels. It is further shown that Rd= Cs is the upper boundary of the achievable rate-equivocation region.

The knapsack problem is an NP-complete combinatorial problem that is strongly believed to be computationally difficult to solve in general. Specific instances of this problem that appear very difficult to solve unless one possesses "trapdoor information" used in the design of the problem are demonstrated. Because only the designer can easily solve problems, others can send him information hidden in the solution to the problems without fear that an eavesdropper will be able to extract the information. This approach differs from usual cryptographic systems in that a secret key is not needed. Conversely, only the designer can generate signatures for messages, but anyone can easily check their authenticity.

A cryptographic system is described which is secure if and only if computing logarithms overGF(p)is infeasible. Previously published algorithms for computing this function requireO(p^{1/2})complexity in both time and space. An improved algorithm is derived which requiresO =(\log^{2} p)complexity ifp - 1has only small prime factors. Such values ofpmust be avoided in the cryptosystem. Constructive uses for the new algorithm are also described.

Wyner recently introduced the concept of a wiretap channel and showed that by transmitting at a rate less than capacity on the main link it was possible to keep the wiretapper's information about the entire message equal to zero. It is shown that it is possible to send at capacity on the main link and still keep the wiretapper's information equal to zero on many, large, arbitrary portions of the message.

Shannon's information-theoretic approach to cryptography is reviewed and extended. It is shown that Shannon's random cipher model is conservative in that a randomly chosen cipher is essentially the worst possible. This is in contrast with error-correcting codes where a randomly chosen code is essentially the best possible. The concepts of matching a cipher to a language and of the trade-off between local and global uncertainty are also developed.

Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.

In the past, it has generally been assumed that the probability of undetected error for an(n,k)block code, used solely for error detection on a binary symmetric channel, is upperbounded by2^{-(n-k)}. In this correspondence, it is shown that Hamming codes do indeed obey this bound, but that the bound is violated by some more general codes. Examples of linear, cyclic, and Bose-Chaudhuri-Hocquenghem (BCH) codes which do not obey the bound are given.

Packet switching has found widespread application in computer communications because of its ability to efficiently handle high ratios of peak-to-average data rate. Packet radio is the application of packet switching techniques to radio channels. The resultant multiple-access problem requires novel approaches. Such approaches have been developed by others and have primarily been analyzed in steady-state behavior. This paper demonstrates and analyzes an important aspect of the dynamic characteristics of packet radio, namely, that of bistable behavior. That is, the system possesses two statistically stable equilibrium points, one in a desirable low-delay region, and the other in an undesirable high-delay region. Since the stability is only statistical in nature, the system oscillates between these two points. Even if the resultant steady-state behavior is very poor, this dynamic analysis frequently shows that system performance will be acceptable. This is due to quiet periods (such as at night) which allow the system to recover.

Cyclic codes are very attractive for error detection because of their low cost encoding and decoding circuits, and because of their high guaranteed minimum distance, but they suffer from very poor protection when word frame synchronization is lost. This note suggests starting the encoder and decoder circuits in an essentially random state, instead of the usual all-zero state. Under this condition of operation it is shown that the undetected error rate against synchronization loss is2^{-p}wherepis the number of parity check bits.

This paper reexamines Jelinek's proof that tree codes can be used to approach the rate-distortion bound. It is shown that the branching process used in Jelinek's proof is not a (strict-sense) branching process (SSBP) when the source is asymmetric. Branching processes with random environments (BPWRE) are introduced and used to extend the proof to general discrete-time memoryless sources. The theory developed indicates why a particular metric used in experiments performed better than another suggested by the original proof.

In certain communications problems, such as remote telemetry, it is important that any operations performed at the transmitter be of a simple nature, while operations performed at the receiver can frequently be orders of magnitude more complex. Channel coding is well matched to such situations while conventional source coding is not. To overcome this difficulty of usual source coding, we propose using a convolutional encoder for joint source and channel encoding. When the channel is noiseless this scheme reduces to a convolutional source code that is simpler to encode than any other optimal noiseless source code known to date. In either case, decoding can be a minor variation on sequential decoding.

In this paper we develop a simple encoder/decoder pair which utilizes the natural redundancy of a source for error detection. It does so with no loss in rate of transmission and with only minimal hardware cost.

Let\{X_n\}_{n=1}^{\infty}be independent random variables, each having a\mathcal{N}(\mu, \sigma^2)distribution. If we try to estimate\muwith anm-state learning algorithm, then the minimum mean-squared error is bounded below by that obtained by the bestm-level quantizer (which requires knowledge of\mu). Here we show that this lower bound is tight. The results are easily extended to a number of other problems, such as estimating the mean\thetaof a uniform distribution.

The hypothesis-testing problem has recently been studied under a finite-memory constraint. However, most work has been concerned with the large-sample theory. Here we study the small-sample theory for binary-valued observations.

This paper is concerned with the differences between deterministic and randomized finite-memory decision rules. It is shown that for any hypothesis-testing problem there exists ab < \inftysuch that, for anyB, the optimal deterministic rule withB + bbits in memory has a lower error probability than the optimal randomized rule withBbits in memory. Suboptimal deterministic rules with this property are demonstrated. These deterministic rules lose at mostbbits. Thus for large memories the fraction of memory, measured in bits, lost by deterministic rules is negligible.

A confidence model for finite-memory learning systems is advanced in this correspondence. The primary difference between this and the previously used probability-of-error model is that a measure of confidence is associated with each decision and any incorrect decisions are weighted according to their confidence measure in figuring total loss. The optimal rule for this model is deterministic, whereas the previous model required randomized rules to achieve minimum error probability.

This paper solves the classical two-armed-bandit problem under the finite-memory constraint described below. Given are probability densitiesp_0andp_1, and two experimentsAandB. It is not known which density is associated with which experiment. Thus the experimental outcomeYof experimentAis as likely to be distributed according top_0as it is to be distributed according top_1. It is desired to sequentially choose an experiment to be performed on the basis of past observations according to the algorithmT_n = f(T_{n-1}, e_n, Y_n), e_n = e(T_{n-1}), whereT_n \in \{1, 2, \cdots, m\}is the state of memory at timen, e_n \in \{A, B\}is the choice of experiment, andY_n, is the random variable observation. The goal is to maximize the asymptotic proportionrof uses of the experiment associated with densityp_0. Letl(y) = p_0 (y) / p_1 (y), and let\bar{l}and\bar{\bar{l}}denote the almost everywhere greatest lower bound and least upper bound onl(y). Let1 = \max {\bar{\bar{l}}, 1/\bar{l}}. Then the optimal value ofr, over allm-state algorithms(f, e), will be shown to bel^{m-1} / (l^{m-1} + 1). Ane-optimal family ofm-state algorithms will be demonstrated. In general, optimal algorithms do not exist, ande-optimal algorithms require artificial randomization.

Relationships between the probability of error, the equivocation, and the Chernoff bound are examined for the two-hypothesis decision problem. The effect of rejections on these bounds is derived. Finally, the results are extended to the case of any finite number of hypotheses.