On the correlation of binary sequences

In a series of papers Mauduit and Sárközy (partly with further coauthors) studied finite pseudorandom binary sequences. In particular, one of the most important applications of pseudorandomness is cryptography. If, e.g., we want to use a binary sequence E_N{-1,+1}^N (after transforming it into a bit sequence) as a key stream in the standard Vernam cipher [A. Menezes, P. van Oorschot, R. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1997], then E_N must possess certain pseudorandom properties. Does E_N need to possess both small well-distribution measure and, for any fixed small k, small correlation measure of order k? In other words, if W(E_N) is large, resp. C_k(E_N) is large for some fixed small k, then can the enemy utilize this fact to break the code? The most natural line of attack is the exhaustive search: the attacker may try all the binary sequences E_N{-1,+1}^N with large W(E_N), resp. large C_k(E_N), as a potential key stream. Clearly, this attack is really threatening only if the number of sequences E_N{-1,+1}^N with

(i) large W(E_N), resp.

(ii) large C_k(E_N)

is “much less” than the total number 2^N of sequences in {-1,+1}^N, besides one needs a fast algorithm to generate the sequences of type (i), resp. (ii).The case (i) is easy, thus, for the sake of completeness, here we just present an estimate for the number of sequences E_N with large W(E_N).The case (ii), i.e., the case of large correlation is much more interesting: this case will be studied in Section 2.In Section 3 we will sharpen the results of Section 2 in the special case when the order of the correlation is 2.Finally, in Section 4 we will study a lemma, which plays a crucial role in the estimation of the correlation in some of the most important constructions of pseudorandom binary sequences.     

Measures of pseudorandomness for binary sequences constructed using finite fields

We extend the results of Goubin, Mauduit and Sárközy on the well-distribution measure and the correlation measure of order k of the sequence of Legendre sequences with polynomial argument in several ways. We analyze sequences of quadratic characters of finite fields of prime power order and consider in each case two, in general, different definitions of well-distribution measure and correlation measure of order k, respectively.     

A trace representation of binary Jacobi sequences

We determine the trace function representation, or equivalently, the Fourier spectral sequences of binary Jacobi sequences of period pq, where p and q are two distinct odd primes. This includes the twin-prime sequences of period p(p+2) whenever both p and p+2 are primes, corresponding to cyclic Hadamard difference sets.     

Construction of large families of pseudorandom binary sequences

Oon constructed large families of finite binary sequences with strong pseudorandom properties by using Dirichlet characters of large order. In this paper Oon’s construction is generalized and extended. We prove that in our construction the well-distribution and correlation measures are as “small” as in the case of the Legendre symbol.      

On the mean and extreme distances between failures in Markovian binary sequences

This paper is concerned with the mean, minimum and maximum distances between two successive failures in a binary sequence consisting of Markov dependent elements. These random variables are potentially useful for the analysis of the frequency of critical events occurring in certain stochastic processes. Exact distributions of these random variables are derived via combinatorial techniques and illustrative numerical results are presented.     

More constructions of pseudorandom sequences of k symbols

We present some new constructions of families of pseudorandom sequences of k symbols, which generalize several previous constructions for the binary case.     

2-Adic complexity of binary sequences with interleaved structure

In this paper, 2-adic complexity of some binary sequences with interleaved structure is investigated. Firstly, 2-adic complexity of low correlation zone (LCZ) sequences constructed by Zhou et al. [23] is completely determined. We show that their 2-adic complexity could attain the maximum if suitable parameters are chosen. Secondly, we also determine 2-adic complexity of optimal autocorrelation sequences constructed by Tang and Ding [16]. Results show that they have the maximum 2-adic complexity.     

A geometric averaging procedure for constructing supertransitive approximation to binary comparison matrices

The usefulness of encoding the fuzzy evaluations of alternatives and the importance weights of criteria, in a multiple objective decision problem through binary comparison matrices (or pairwise judgment matrices) is receiving considerable attention. The methodology for identifying the best alternative in a given decision problem involves the computation of the principal eigenvectors of the binary comparison matrices. The eigenvectors transform the fuzzy evaluations of the importance of the criteria and the ratings of the alternatives into a ratio scale. A difficulty that is often experienced in using this approach in practice, is the inconsistency of the binary evaluations. This paper proposes a simple averaging procedure to construct a supertransitive approximation to a binary comparison matrix, where inconsistency is a problem. It is further suggested that such an adjustment might be necessary to more closely reflect the inherent fuzziness of the evaluations contained in a binary comparison matrix. The procedure is illustrated by means of examples.     

Linear complexity profile of binary sequences with small correlation measure

Summary A high linear complexity profile is a desirable feature of sequences used for cryptographical purposes. For a given binary sequence we estimate its linear complexity profile in terms of the correlation measure, which was introduced by Mauduit and Sárk?zy. We apply this result to certain periodic sequences including Legendre sequences, Sidelnikov sequences and other sequences related to the discrete logarithm.     

A meta-control algorithm for generating approximate solutions to binary integer programming problems

Binary integer program problems, which are known to be difficult to solve, have long been an important research area. We use a new approach with continualization techniques to find approximate solutions to binary integer programming problems. The algorithm constructs a sequence of approximations to a solution using a meta-control approach that has low polynomial time complexity. The algorithm is illustrated with a BIP example.     

A generic construction of low correlation zone sequences based on interleaved technique

Low correlation zone (LCZ) sequences are useful in quasi-synchronous code-division multiple access (QS-CDMA) communication systems. In this paper, a generic construction of LCZ sequences based on inter-leaved technique is investigated. Firstly, the shift sequence is shown to correspond to two-tuple balanced d-form function essentially, which results in new shift sequence. Secondly, an optimal design of p2-ary sequences over the integer residue class ring Zp2 is proposed, which improves the previous construction when p is an odd prime.     

On the index of minimal zero-sum sequences over finite cyclic groups

Let G be a cyclic group of order n?2 and a sequence over G. We say that S is a zero-sum sequence if and that S is a minimal zero-sum sequence if S is a zero-sum sequence and S contains no proper zero-sum sequence.The notion of the index of a minimal zero-sum sequence (see Definition 1.1) in G has been recently addressed in the mathematical literature. Let l(G) be the smallest integer t∈N such that every minimal zero-sum sequence S over G with length |S|?t satisfies index(S)=1. In this paper, we first prove that for n?8. Secondly, we obtain a new result about the multiplicity and the order of elements in long zero-sumfree sequences.     

A simplified completely positive reformulation for binary quadratic programs

In this paper, we propose a simplified completely positive programming reformulation for binary quadratic programs. The linear equality constraints associated with the binary constraints in the original problem can be aggregated into a single linear equality constraint without changing the feasible set of the classic completely positive reformulation proposed in the literature. We also show that the dual of the proposed simplified formulation is strictly feasible under a mild assumption.     

A discrete logarithm-based approach to compute low-weight multiples of binary polynomials

Being able to compute efficiently a low-weight multiple of a given binary polynomial is often a key ingredient of correlation attacks to LFSR-based stream ciphers. The best known general purpose algorithm is based on the generalized birthday problem. We describe an alternative approach which is based on discrete logarithms and can take advantage of the structure of the polynomial. In some cases it has much lower memory complexity requirements with a comparable time complexity.     

Equivalent measures of dependence

The maximal correlation between a pair of σ-fields $\text{A}$ and $\text{B}$ becomes arbitrarily small as sup{|P(A ? B) ? P(A) P(B)|/[P(A) P(B)]^1/2, A ∈ $\text{A}$, B ∈ $\text{B}$, P(A) > 0, P(B) > 0} becomes sufficiently small.     

A combinatorial approach to height sequences in finite partially ordered sets

Fix an element x of a finite partially ordered set P on n elements. Then let h_i(x) be the number of linear extensions of P in which x is in position i, counting from the bottom. The sequence {h_i(x):1≤i≤n} is the height sequence of x in P. In 1982, Stanley used the Alexandrov–Fenchel inequalities for mixed volumes to prove that this sequence is log-concave, i.e., for 1≤i≤n−2. However, Stanley’s elegant proof does not seem to shed any light on the error term when the inequality is not tight; as a result, researchers have been unable to answer some challenging questions involving height sequences in posets. In this paper, we provide a purely combinatorial proof of two important special cases of Stanley’s theorem by applying Daykin’s inequality to an appropriately defined distributive lattice. As an end result, we prove a somewhat stronger result, one for which it may be possible to analyze the error terms when the log-concavity bound is not tight.     

A chain theorem for internally 4-connected binary matroids

Let M be a matroid. When M is 3-connected, Tutte's Wheels-and-Whirls Theorem proves that M has a 3-connected proper minor N with |E(M)−E(N)|=1 unless M is a wheel or a whirl. This paper establishes a corresponding result for internally 4-connected binary matroids. In particular, we prove that if M is such a matroid, then M has an internally 4-connected proper minor N with |E(M)−E(N)|?3 unless M or its dual is the cycle matroid of a planar or Möbius quartic ladder, or a 16-element variant of such a planar ladder.     

On the lifetime of a random binary sequence

Consider a system with m elements which is used to fulfill tasks. Each task is sent to one element which fulfills a task and the outcome is either fulfillment of the task (“1”) or the failure of the element (“0”). Initially, m tasks are sent to the system. At the second step, a complex of length m₁ is formed and sent to the system, where m₁ is the number of tasks fulfilled at the first step, and so on. The process continues until all elements fail and the corresponding waiting time defines the lifetime of the binary sequence which consists of “1” or “0”. We obtain a recursive equation for the expected value of this waiting time random variable.     

MAXIMUM TREES OF FINITE SEQUENCES

ＭＡＸＩＭＵＭＴＲＥＥＳＯＦＦＩＮＩＴＥＳＥＱＵＥＮＣＥＳ￥ＷＵＳＨＩＱＵＡＮＡｂｓｔｒａｃｔ：Ｌｅｔｎ，ｓ１，ｓ２，．．．，ｓｎｂｅｎｏｎ－ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓａｎｄＭ（ｓ１，ｓ２，．．．，ｓｎ）＝｛（ａ１，ａ２，．．．，ａ．）｜ａｉｉ...