The study of collision and avalanche effect in a family of pseudorandom binary sequences
- PDF / 110,495 Bytes
- 8 Pages / 594.96 x 842.04 pts (A4) Page_size
- 67 Downloads / 171 Views
THE STUDY OF COLLISION AND AVALANCHE EFFECT IN A FAMILY OF PSEUDORANDOM BINARY SEQUENCES ´ ria To ´ th Vikto [Communicated by Attila Peth˝ o] Department of Algebra and Number Theory, Department of Computer Algebra E¨ otv¨ os Lor´ and University, P´ azm´ any P´eter s´et´ any 1/C, H-1117 Budapest, Hungary E-mail: [email protected] (Received February 1, 2008; Accepted April 23, 2009)
Abstract In an earlier paper we studied collisions and avalanche effect in two of the most important constructions given for large families of binary sequences possessing strong pseudorandom properties. It turned out that one of the two constructions (which is based on the use of the Legendre symbol) is ideal from this point of view, while the other construction (which is based on the size of the modulo p residue of f (n) for some polynomial f (x) ∈ Fp [x]) is not satisfactory since there are “many” collisions in it. Here it is shown that this weakness of the second construction can be corrected: one can take a subfamily of the given family which is just slightly smaller and collision free.
1. Introduction Pseudorandom binary sequences play a crucial role in modern cryptography. The notion of pseudorandomness is usually characterized by using the tools of computational complexity. However, this approach has certain weaknesses which restrict its applicability. Thus recently a more constructive theory of pseudorandomness of binary sequences has been initiated by Mauduit and S´ark¨ozy [9]. They introduced the following notations and definitions: Consider a binary sequence EN = (e1 , . . . , eN ) ∈ {−1, 1}N . Then the well-distribution measure of EN is defined as t−1 X ea+jb , W (EN ) = max a,b,t
j=0
Mathematics subject classification number : 11K45. Key words and phrases: pseudorandom, binary sequence, collision, avalanche effect. 0031-5303/2009/$20.00
c Akad´emiai Kiad´o, Budapest
Akad´ emiai Kiad´ o, Budapest Springer, Dordrecht
2
´ V. TOTH
where the maximum is taken over all a, b, t with a, b, t ∈ N, 1 ≤ a + b ≤ a + tb ≤ N . The correlation measure of order k of EN is M X en+d1 en+d2 · · · en+dk , Ck (EN ) = max M,D
n=1
where the maximum is taken over all D = (d1 , . . . , dk ) (d1 < · · · < dk are nonnegative integers) and M ∈ N with M + dk ≤ N . Then EN is considered as a “good” pseudorandom sequence if both W (EN ) and Ck (EN ) (at least for “small” k) are “small” in terms of N . Indeed, later, Cassaigne, Mauduit and S´ ark¨ozy [2] showed that this terminology is justified since for almost all EN ∈ {−1, 1}N , both W (EN ) and Ck (EN ) are less than N 1/2 (log N )c . In an earlier paper [10] we introduced and studied the following definitions and notions: Assume that N ∈ N, S is a given set (e.g., a set of certain polynomials or the set of all binary sequences of a given length much less than N ). To each s ∈ S we assign a unique binary sequence EN = EN (s) = (e1 , . . . , eN ) ∈ {−1, 1}N and let F = F(S) denote the family of binary sequences obtained in this way: F = F(S) = {EN (s) : s ∈ S}.
(1)
Definition 1. If s ∈ S, s′ ∈
Data Loading...
