Concatenation of pseudorandom binary sequences

In the applications it may occur that our initial pseudorandom binary sequence turns out to be not long enough, thus we have to take the concatenation or merging of it with other pseudorandom binary sequences. Here our goal is study when we can form the concatenation of several pseudorandom binary sequences belonging to a given family? We introduce and study new measures which can be used for answering this question.     

On finite pseudorandom sequences of k symbols

In earlier papers C. Mauduit and A. Sárközy have introduced and studied the measures of pseudorandomness for finite binary sequences. In [8] they extend this theory to sequences of k symbols: they give the definitions and also construct a “good” pseudorandom sequence of k symbols. In this paper these measures are studied for a “truely random” sequence.     

Logistic chaotic maps for binary numbers generations

Two pseudorandom binary sequence generators, based on logistic chaotic maps intended for stream cipher applications, are proposed. The first is based on a single one-dimensional logistic map which exhibits random, noise-like properties at given certain parameter values, and the second is based on a combination of two logistic maps. The encryption step proposed in both algorithms consists of a simple bitwise XOR operation of the plaintext binary sequence with the keystream binary sequence to produce the ciphertext binary sequence. A threshold function is applied to convert the floating-point iterates into binary form. Experimental results show that the produced sequences possess high linear complexity and very good statistical properties. The systems are put forward for security evaluation by the cryptographic committees.     

On Pseudorandomness in Families of Sequences Derived from the Legendre Symbol

We construct a family of finite binary sequences which has a remarkable uniformity with respect to specification of several terms and which also has the property that every sequence in the family has small measures of normality, well distribution in arithmetical progressions and multiple correlations. We also construct a pseudorandom bit generator whose output consists of members of the family.     

Collision and avalanche effect in families of pseudorandom binary sequences

Recently a constructive theory of pseudorandomness of binary sequences has been developed and many constructions for binary sequences with strong pseudorandom properties have been given. In the applications one usually needs large families of binary sequences of this type. In this paper we adapt the notions of collision and avalanche effect to study these pseudorandom properties of families of binary sequences. We test two of the most important constructions for these pseudorandom properties, and it turns out that one of the two constructions is ideal from this point of view as well, while the other construction does not possess these pseudorandom properties. Communicated by Attila Pethő     

On finite pseudorandom lattices of k symbols

In earlier papers Mauduit and Sárközy have introduced and studied the measures of pseudorandomness for finite binary sequences and sequences of k symbols. Later they (with further coauthors) extended the notation of binary sequences to binary lattices. In this paper measures of pseudorandom lattices of k symbols are introduced and studied for “truly random” lattices.     

Synthesis of cryptographic interleaved sequences by means of linear cellular automata

This work shows that a class of pseudorandom binary sequences, the so-called interleaved sequences, can be generated by means of linear multiplicative polynomial cellular automata. In fact, these linear automata generate all the solutions of a type of linear difference equations with binary coefficients. Interleaved sequences are just particular solutions of such equations. In this way, popular nonlinear sequence generators with cryptographic application can be linearized in terms of simple cellular automata.     

On the pseudorandomness of quaternary sequences derived from sequences over $$\mathbb F_4$$

In analogy to the corresponding measures of pseudorandomness for quaternary sequences introduced by Mauduit and Sárközy (for m-ary sequences) we introduce the well-distribution measure and correlation measure of order k for sequences over \(\mathbb F_4\). Using any fixed bijection from \(\mathbb F_4\) to the set of complex fourth roots of unity, we analyze the relation of these pseudorandomness measures for sequences over \(\mathbb F_4\) and for the corresponding quaternary sequences. More precisely, we show that they differ only by a multiplicative constant (depending only on k). We also apply the results for deriving new quaternary pseudorandom sequences from pseudorandom sequences over \(\mathbb F_4\) and vice versa.     

Extension of the notion of collision and avalanche effect to sequences of k symbols

In recent papers [14], [15] I studied collision and avalanche effect in families of finite pseudorandom binary sequences. Motivated by applications, Mauduit and Sárk?zy in [13] generalized and extended this theory from the binary case to k-ary sequences, i.e., to k symbols. They constructed a large family of k-ary sequences with strong pseudorandom properties. In this paper our goal is to extend the study of the pseudorandom properties mentioned above to k-ary sequences. The aim of this paper is twofold. First we will extend the definitions of collision and avalanche effect to k-ary sequences, and then we will study these related properties in a large family of pseudorandom k-ary sequences with ??small?? pseudorandom measures.     

合数模上的伪随机二进制数列

设m为"RSA"类型的模,即m为两个大小差不多的素数的乘积:m=pqp,q为素数,p相似文献   

Correlation measure,linear complexity and maximum order complexity for families of binary sequences

The correlation measure of order k is an important measure of pseudorandomness for binary sequences. This measure tries to look for dependence between several shifted versions of a sequence. We study the relation between the correlation measure of order k and two other pseudorandom measures: the Nth linear complexity and the Nth maximum order complexity. We simplify and improve several state-of-the-art lower bounds for these two measures using the Hamming bound as well as weaker bounds derived from it.     

Pseudo-randomness and complexity of binary sequences generated by the chaotic system

The pseudo-randomness and complexity of binary sequences generated by chaotic systems are investigated in this paper. These chaotic binary sequences can have the same pseudo-randomness and complexity as the chaotic real sequences that are transformed into them by the use of Kohda’s quantification algorithm. The statistical test, correlation function, spectral analysis, Lempel–Ziv complexity and approximate entropy are regarded as quantitative measures to characterize the pseudo-randomness and complexity of these binary sequences. The experimental results show the finite binary sequences generated by the chaotic systems have good properties with the pseudo-randomness and complexity of sequences. However, the pseudo-randomness and complexity of sequence are not added with the increase of sequence length. On the contrary, they steadily decrease with the increase of sequence length in the criterion of approximate entropy and statistical test. The constraint of computational precision is a fundamental reason resulting in the problem. So only the shorter binary sequences generated by the chaotic systems are suitable for modern cryptography without other way of adding sequence complexity in the existing computer system.     

Odd and even hamming spheres also have minimum boundary

Combinatorial problems with a geometric flavor arise if the set of all binary sequences of a fixed length n, is provided with the Hamming distance. The Hamming distance of any two binary sequences is the number of positions in which they differ. The (outer) boundary of a set A of binary sequences is the set of all sequences outside A that are at distance 1 from some sequence in A. Harper [6] proved that among all the sets of a prescribed volume, the ‘sphere’ has minimum boundary.We show that among all the sets in which no pair of sequences have distance 1, the set of all the sequences with an even (odd) number of 1's in a Hamming ‘sphere’ has the same minimizing property. Some related results are obtained. Sets with more general extremal properties of this kind yield good error-correcting codes for multi-terminal channels.     

Construction of large families of pseudorandom binary sequences

In a series of papers Mauduit and Sárközy (partly with coauthors) studied finite pseudorandom binary sequences. They showed that the Legendre symbol forms a “good” pseudorandom sequence, and they also tested other sequences for pseudorandomness, however, no large family of “good” pseudorandom sequences has been found yet.In this paper, a large family of this type is constructed by extending the earlier Legendre symbol construction.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.     

Asymptotic structural characteristics of fuzzy measure and their applications

In fuzzy measure theory, as Sugeno's fuzzy measures lose additivity in general, the concept ‘almost’, which is well known in classical measure theory, splits into two different concepts, ‘almost’ and ‘pseudo-almost’. In order to replace the additivity, it is quite necessary to investigate some asymptotic behaviors of a fuzzy measure at sequences of sets which are called ‘waxing’ and ‘waning’, and to introduce some new concepts, such as ‘autocontinuity’, ‘converse-autocontinuity’ and ‘pseudo-autocontinuity’. These concepts describe some asymptotic structural characteristics of a fuzzy measure.In this paper, by means of the asymptotic structural characteristics of fuzzy measure, we also give four forms of generalization for both Egoroff's theorem, Riesz's theorem and Lebesgue's theorem respectively, and prove the almost everywhere (pseudo-almost everywhere) convergence theorem, the convergence in measure (pseudo-in measure) theorem of the sequence of fuzzy integrals. In the last two theorems, the employed conditions are not only sufficient, but also necessary.     

On pseudorandom properties of some Dirichlet characters

In this paper, we try to generalize the Mauduit–Sárközy pseudorandom properties of the Legendre symbol to Dirichlet characters. We prove that in our construction the well-distribution and correlation measures are as “small” as in the case of the Legendre symbol. Furthermore we provide with sufficient conditions to ensure the coincidence of two binary sequences using the Legendre symbol.     

Construction of pseudorandom binary sequences using additive characters over GF(2<Superscript><Emphasis Type="Italic">k</Emphasis></Superscript>) II

In a series of papers Mauduit and Sárközy introduced measures of pseudorandomness and they constructed large families of sequences with strong pseudorandom properties. In later papers the structure of families of binary sequences was also studied. In these constructions fields with prime order were used. Throughout this paper the structure of a family of binary sequences based on GF(2 ^k ) will be studied.     

Measures of pseudorandomness of finite binary lattices,II. (The symmetry measures)

In an earlier paper Gyarmati introduced and studied the symmetry measure of pseudorandomness of binary sequences. The goal of this paper is to extend this definition to two dimensions, i.e., to binary lattices. Three different definitions are proposed to do this extension. The connection between these definitions is analyzed. It is shown that these new symmetry measures are independent of the other measures of pseudorandomness of binary lattices. A binary lattice is constructed for which both the pseudorandom measures of order ℓ (for every fixed ℓ) and the symmetry measures are small. Finally, the symmetry measures are estimated for truly random binary lattices.     

Modified constructions of binary sequences using multiplicative inverse

Two new families of finite binary sequences are constructed using multiplicative inverse. The sequences are shown to have strong pseudorandom properties by using some estimates of certain exponential sums over finite fields. The constructions can be implemented fast since multiplicative inverse over finite fields can be computed in polynomial time.