We continue the study of the properties of Boolean functions as reflected in The properties of a recently defined transform. For each non-constant Boolean function q, the q-transform of a Boolean function f is related to the Hamming distances from f to the functions obtainable from q by nonsingular linear change of basis. Many properties that can be characterized by the Walsh-Hadamard transform have (for each q) analogues that can be characterized by the q-transform. In this paper, we study one such property, bentness. We show that if q is balanced and not affine, then there is no function that is both bent and q-bent.

We introduce a new transform on Boolean functions generalizing the Walsh–Hadamard transform. For Boolean functions$q$and$f$, the$q$-transform of$f$measures the proximity of$f$to the set of functions obtained from$q$by change of basis. This has implications for security against certain algebraic attacks. In this paper, we derive the expected value and second moment (Parseval’s equation) of the$q$-transform, leading to a notion of$q$-bentness. We also develop a Poisson summation formula, which leads to a proof that the$q$-transform is invertible.

In this paper, the authors continue a program to find arithmetic, or “with-carry,” analogs of polynomial-based phenomena that appear in the design and analysis of cryptosystems and other branches of digital computation and communications. They construct arithmetic analogs of the Walsh-Hadamard transform and correlation functions of Boolean functions. These play central roles in the cryptographic analysis of block ciphers and stream ciphers. After making basic definitions and constructing various algebraic tools they: 1) show how to realize arithmetic correlations as cardinalities of intersections of hypersurfaces; 2) show that the arithmetic Walsh spectrum characterizes a Boolean function; 3) study the average behavior of arithmetic Walsh transforms; and 4) find the arithmetic Walsh transforms of linear and affine functions.

Various measures of security of stream ciphers have been studied that are based on the problem of finding a minimum size generator for the keystream in some special class of generators. These include linear and p-adic spans, as well as π-adic span, which is based on a choice of an element π in a finite extension of the integers. The corresponding sequence generators are known as linear feedback shift registers, feedback with carry shift registers, and the more general algebraic feedback shift registers, respectively. In this paper, the average behavior of such security measures when πd= p ≫ 0 or π2= -p ≪ 0 is studied. In these cases, if Z [π] is the ring of integers in its fraction field and is a UFD, it is shown that the average π-adic span is n - O(log(n)) for sequences with period n.

The m-covering radii of codes are natural generalizations of the covering radii of codes. In this paper we analyze the 2-covering radii of double error correcting BCH code

Over the past half century, various statistical properties of pseudorandom sequences have played important roles in a variety of applications. Among these properties are Golomb's randomness conditions: (R1) balance, (R2) run property, and (R3) ideal autocorrelations, as well as the closely related properties (R4) shift and add, and (R5) de Bruin (uniform distribution of subblocks). The purpose of this paper is to describe the relationships among these conditions, and to introduce a new method for generating sequences with all these properties, using algebraic feedback shift registers.

This paper describes the new construction of nonbinary pseudonoise sequences or m-sequences. These sequences have random properties: uniform distribution of subsequences, expected distribution of runs, and ideal autocorrelations. The polynomial pseudonoise sequences based on algebraic feedback shift register sequences are discussed.

Maximal length feedback with carry shift register sequences have several remarkable statistical properties. Among them is the property that the arithmetic correlations between any two cyclically distinct decimations are precisely zero. It is open, however, whether all such pairs of decimations are indeed cyclically distinct. In this paper we show that the set of distinct decimations is large and, in some cases, all decimations are distinct.

The multicovering radii of a code are natural generalizations of the covering radius in which the goal is to cover all m-tuples of vectors for some m as cheaply as possible. In this correspondence, we describe several techniques for obtaining lower bounds on the sizes of codes achieving a given multicovering radius. Our main method is a generalization of the method of linear inequalities based on refined weight distributions of the code. We also obtain a linear upper bound on the 2-covering radius. We further study bounds on the sizes of codes with a given multicovering radius that are subcodes of a fixed code. We find, for example, constraints on parity checks for codes with small ordinary covering radius.

Families of sequences with low pairwise shifted cross correlations are desirable for applications such as code-division multiple-access (CDMA) communications. Often such sequences must have additional properties for specific applications. Several ad hoc constructions of such families exist in the literature, but there are few systematic approaches to such sequence design. We introduce a general method of constructing new families of sequences with bounded pairwise shifted cross correlations from old families of such sequences. The bounds are obtained in terms of the maximum cross correlation in the old family and the Walsh transform of certain functions.

The multicovering radii of a code are recently introduced natural generalizations of the covering radius measuring the smallest radius of balls around codewords that cover all m-tuples of vectors. In this paper we prove a new identity relating the multicovering radii of a code to a relativized notion of ordinary covering radius. This identity is used to prove new bounds on the multicovering radii of particular codes.

A feedback-with-carry shift register (FCSR) with "Fibonacci" architecture is a shift register provided with a small amount of memory which is used in the feedback algorithm. Like the linear feedback shift register (LFSR), the FCSR provides a simple and predictable method for the fast generation of pseudorandom sequences with good statistical properties and large periods. In this paper, we describe and analyze an alternative architecture for the FCSR which is similar to the "Galois" architecture for the LFSR. The Galois architecture is more efficient than the Fibonacci architecture because the feedback computations are performed in parallel. We also describe the output sequences generated by the d-FCSR, a slight modification of the (Fibonacci) FCSR architecture in which the feedback bit is delayed for d clock cycles before being returned to the first cell of the shift register. We explain how these devices may be configured so as to generate sequences with large periods. We show that the d-FCSR also admits a more efficient "Galois" architecture.

In this correspondence, we study families of generalized geometric sequences formed bp applying a feedforward function to certain sums of decimated m-sequences with elements in a finite field. We compute their correlation functions, which for certain families turn out to be close to the square root of the period. The size of these families equals their period. We also show that in the binary case, the linear complexities of these sequences are much larger than those of cascaded geometric sequences, although in these cases the maximum correlations are larger.

An arithmetic or with-carry analog of Blahut's (1979) theorem is presented. This relates the length of the smallest feedback with-carry shift register to the number of nonzero classical Fourier coefficients of a periodic binary sequence.

The m-covering radius of a code is a generalization of the covering radius of a code. It is the smallest t such that every m-tuple of vectors is contained in a ball of Hamming radius t centered at some codeword. We derive new lower bounds for the size of the smallest code that has a given length and m-covering radius.

An arithmetic version of the crosscorrelation of two sequences is defined, generalizing Mandelbaum's (1967) arithmetic autocorrelations. Large families of sequences are constructed with ideal (vanishing) arithmetic crosscorrelations. These sequences are decimations of the 2-adic expansions of rational numbers p/q such that 2 is a primitive root module q.

The covering radius of a code is the least r such that the set of balls of radius r around codewords covers the entire ambient space. We introduce a generalization of the notion of covering radius. The m-covering radius of a code is the least radius such that the set of balls of that radius covers all m-tuples of elements in the ambient space. We investigate basic properties of m-covering radii. We investigate whether codes exist with given m-covering radii (not always). We derive bounds on the size of the smallest code with a given m-covering radius, based on generalizations of the sphere bound and the method of counting excesses.

The expectations and variances of partial period crosscorrelations for certain geometric sequences are estimated. The expectations of the partial period crosscorrelations are shown to be proportional to the periodic crosscorrelations. Bounds are found for the variance that show that with high probability the partial period crosscorrelations are small if the sequences are balanced.

In order to build spread-spectrum communication systems based on the CDMA paradigm, it is necessary to have large families of binary sequences with low pairwise correlation values. For these systems to have resistance to certain cryptanalytic attacks and resistance to jamming, the sequences must have large linear span. We describe certain families of sequences that have these desirable properties. The sequences are based on families of quadratic forms over finite fields.

Large families of binary sequences with low correlation values and large linear span are critical for spread-spectrum communication systems. The author describes a method for constructing such families from families of homogeneous functions over finite fields, satisfying certain properties. He then uses this general method to construct specific families of sequences with optimal correlations and exponentially better linear span than No sequences (No. 1988).>

For a binary pseudorandom sequence {S/sub i/} with period N, the partial period autocorrelation function A/sub S/(/spl tau/,k,D) is defined by correlating the portion of the sequence within a window of size D, and start position k, with the portion in another window of the same size but starting /spl tau/ steps later in the sequence. A distribution of possible partial period autocorrelation values is obtained by allowing the start position K to vary over all possible values O/spl les/k>

Pseudorandom binary sequences with high linear complexity and low correlation function values are sought in many applications of modern communication systems. A new family of pseudorandom binary sequences, cascaded GMW sequences, is constructed. These sequences are shown to share many desirable correlation properties with the GMW sequences of B. Gordon, W.A. Mills, and L.R. Welch (1962)-for example, high-shifted autocorrelation values and, in many cases, three-valued cross-correlation values with m-sequences. It is shown, moreover, that in many cases the linear complexities of cascaded GMW sequences are far greater than those of GMW sequences.>

Sequences generated by arbitrary feedback registers (not necessarily feedback shift registers) with arbitrary feedforward functions are studied. The definition of linear complexity of a sequence is generalized to the notions of strong and weak linear complexity of feedback registers. A technique for finding upper bounds for the strong linear complexities of such registers is developed. This technique is applied to several classes of registers. It is shown that a feedback shift register in which the feedback function is of the form x/sub 1/+h(x/sub 2/, . . . , x/sub n/) can generate long periodic sequences with high linear complexities only if its linear and quadratic terms have certain specific forms.>