This paper develops analytical models for the avalanche characteristics of a class of block ciphers usually referred to as substitution-permutation encryption networks or SPNs. An SPN is considered to display good avalanche characteristics if a one bit change in the plaintext input is expected to result in close to half the ciphertext output bits changing. Good avalanche characteristics are important to ensure that a cipher is not susceptible to statistical attacks and the strength of an SPN's avalanche characteristics may be considered as a measure of the randomness of the ciphertext. The results presented in this paper demonstrate that the avalanche behavior of encryption networks can be improved by using larger S-boxes. As well, it is shown that increasing the diffusion properties of the S-boxes or replacing the permutations by diffusive linear transformations is effective in improving the network avalanche characteristics.>

In this paper we examine a class of product ciphers referred to as substitution-permutation networks. We investigate the resistance of these cryptographic networks to two important attacks: differential cryptanalysis and linear cryptanalysis. In particular, we develop upper bounds on the differential characteristic probability and on the probability of a linear approximation as a function of the number of rounds of substitutions. Further, it is shown that using large S-boxes with good diffusion characteristics and replacing the permutation between rounds by an appropriate linear transformation is effective in improving the cipher security in relation to these two attacks.

This paper presents some results on the cryptographic strength of Boolean functions from the information theoretic point of view. It is argued that a Boolean function is resistant to statistical analysis if there is no significant static and dynamic information leakage between its inputs and its output(s). In particular we relate information leakage to nonlinearity, higher order SAC, correlation immunity and resilient functions. It is shown that reducing information leakage increases resistance to the differential attack and the linear attack. We note that some conventional cryptographic criteria require zero static or dynamic information leakage in only one domain. Such a requirement can result in a large information leakage in another domain. To avoid this weakness, it is better to jointly constrain all kinds of information leakage in the function. In fact, we claim that information leakage can be used as a fundamental measure of the strength of a cryptographic algorithm.

Previously proposed error detection algorithms for the residue number system require a complete recombination. A weighted approximation via the Chinese remainder theorem is shown to be sufficient to detect 100% of single errors. This makes real-time single-error diagnosis possible, which involves up to N+2 iterations of detection (N is the number of nonredundant channels). One approach uses a scaled range of L+1+log/sub 2/ (N+1) bits for detection in contrast with full decoding of approximately=L(N+1) bits, where L is the number of bits in the largest modulus. A second method forms a redundant residue number representation of the overflow multiplier A(x), although A(x) does not need to be carried through processing operations. This permits real-time single-error diagnosis and correction with a parallel array of approximately=(N+2)/sup 2/ tables.>

Two general classes of binary bent sequences, bent-based and linear-based, are introduced. Algorithms that allow easy generation of bent sequences from either class are given. Based on some simple computation and a computer search, the authors conjecture a lower bound on the total number of binary bent sequences of a given order. This lower bound is exact for bent sequences of order 16; a list is included from which all such sequences can be derived.>

Several VLSI architectures for performing exponentiation in GF(2/sup m/) are presented. Two approaches to the architecture design are taken. In the first, all intermediate products of the exponentiation are computed in a sequential fashion to minimize the silicon area. In the second approach, all values of raised to the 2/sup ei/ power, O>

Multiplication in the finite fieldGF(2^{m}) has particular computational advantages in data encryption systems. This paper presents a new algorithm for performing fast multiplication inGF(2^{m}), which isO(m)in computation time and implementation area. The bit-slice architecture of a serial-in-serial-out modulo multiplier is described and the circuit details given. The design is highly regular, modular, and well-suited for VLSI implementation. The resulting multiplier will have application in algorithms based on arithmetic in large finite fields of characteristic 2, and which require high throughput.

A computer search has been made to determine the true minimum distancedfor all binary cyclic codes having odd lengthsnin the range69\leq n\leq 99. Using an algorithm originally developed by C. L. Chen, the generator matrixGof each(n,k)binary cyclic code was put in systematic form. All possible codewords obtained from sums ofirows ofG, fori= 1,2, \cdots,\upsilon, were examined, and the minimum distanced_{\upsilon}of this set was recorded. Thend=d_{\upsilon}whenever\upsilon >\{(d_{\upsilon}-l)k/n\}-l. Known equivalences among cyclic codes were taken into account, and only one code from each equivalence class was listed. Letg(x)dividex^{n}-1, wherex - 1is not a factor ofg(x). Then the minimum distances of the codes generated byg(x),(x - l)g(x)and their duals are listed together. For each such set of codes, the value of\upsilonfor which a codeword of minimum weight first appeared is listed. The codes found were compared with the list of best codes tabulated by Sloane [5]. Many good cyclic codes have been found. Among the best(n,k,d)cyclic codes found are the following: (73, 27, 20), (73, 36, 16), (85, 12, 34), (85, 20, 28), (87, 31, 22), (89, 56, 11), (91, 51, 14), (93, 20, 32), (93, 23, 29), (93, 31, 24), (93, 33, 22).

The weight distribution of some "best"(3m,2m)rate 2/3 binary quasi-cyclic codes of length up to 54 is discussed. The approach taken was to compute the weight distribution of the corresponding(3m,m)rate 1/3 dual code, and then take advantage of the MacWilliams' identities to derive the weight distribution of the(3m,2m)code.

LetV\primebe a binary(n,k)majority-logic decodable code withg\prime (X)as its generator polynomial and odd minimum distanced. LetVbe the(n, k - 1)subset code generated byg\prime (X)(1 + X). This correspondence shows thatVis majority-logic deeodable withd + 1orthogonal estimates. This fact is useful in the simultaneous correction of random errors and erasures.

Some optimal rate-\frac{1}{2}quasi-cyclic codes found by Chert et aL [3] are grouped into a small set of equivalence classes with the assistance of a computer. The weight distribution of a selection of these rate-\frac{1}{2}codes is tabulated. In addition, a list of new optimal rate-\frac{2}{3}quasi-cyclic codes of lengths up to 54 is presented.

It is shown that certain coset codes derived from binary cyclic codes can determine the magnitude of a synchronization error, as well as its direction by examining only the syndrome of the receivedntuple. For such coset codes, therefore, the need for a search procedure to recover synchronism is eliminated. In addition, the range of slip that can be detected and corrected for noisy channels is extended.

Stone^1found that multiple-error-correcting codes inherently have the ability to correct multiple bursts. Using his methods, somewhat stronger theorems are derived here, and a decoding procedure is given.

The problem of detecting and correcting loss of synchronization for binary cyclic codes is examined. The method used is to form a coset code from tho given(n, k)cyclic code by adding a suitablenvector to each cyclic code word before transmission. Unlike some other techniques, the length of the code wordnis not altered. A code word may be represented in at least two ways: 1) as a vector and 2) as a polynomial. Depending on the problem at hand, one approach may offer more insight or supply a shorter proof for a theorem than the other. Throughout this paper, we use the binaryn-vector representation. Using this approach, we give new proofs to some known results, and derive some now theorems dealing with the simultaneous occurrence of loss of synchronization and additive errors. Specifically, it is shown that there exist coset codes that can correct both additive error and synchronization error even when they occur simultaneously.