Joint linear complexity of multisequences consisting of linear recurring sequences

Date

2009-04-01

Author

Fu, Fang-Wei
Niederreiter, Harald
Özbudak, Ferruh

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

224
views

0
downloads

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. In this paper, we study the joint linear complexity of multisequences consisting of linear recurring sequences. The expectation and variance of the joint linear complexity of random multisequences consisting of linear recurring sequences are determined. These results extend the corresponding results on the expectation and variance of the joint linear complexity of random periodic multisequences. Then we enumerate the multisequences consisting of linear recurring sequences with fixed joint linear complexity. A general formula for the appropriate counting function is derived. Some convenient closed-form expressions for the counting function are determined in special cases. Furthermore, we derive tight upper and lower bounds on the counting function in general. Some interesting relationships among the counting functions of certain cases are established. The generating polynomial for the distribution of joint linear complexities is determined. The proofs use new methods that enable us to obtain results of great generality.

Subject Keywords

Computer Networks and Communications, Computational Theory and Mathematics, Applied Mathematics

URI

https://hdl.handle.net/11511/44140

Journal

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES

DOI

https://doi.org/10.1007/s12095-007-0001-4

Collections

Department of Mathematics, Article

Suggestions

OpenMETU
Core

Generalized nonbinary sequences with perfect autocorrelation, flexible alphabets and new periods BOZTAŞ, Serdar; Özbudak, Ferruh; TEKİN, Eda (Springer Science and Business Media LLC, 2018-05-01) We extend the parameters and generalize existing constructions of perfect autocorrelation sequences over complex alphabets. In particular, we address the PSK+ constellation (Boztas and Udaya 2010) and present an extended number theoretic criterion which is sufficient for the existence of the new sequences with perfect autocorrelation. These sequences are shown to exist for nonprime alphabets and more general lengths in comparison to existing designs. The new perfect autocorrelation sequences provide novel a...
R-2 composition tests: a family of statistical randomness tests for a collection of binary sequences Uğuz, Muhiddin; Doğanaksoy, Ali (Springer Science and Business Media LLC, 2019-09-01) In this article a family of statistical randomness tests for binary strings are introduced, based on Golomb's pseudorandomness postulate R-2 on the number of runs. The basic idea is to construct recursive formulae with computationally tenable probability distribution functions. The technique is illustrated on testing strings of 2(7), 2(8), 2(10) and 2(12) bits. Furthermore, the expected value of the number of runs with a specific length is obtained. Finally the tests are applied to several collections of st...
Results on symmetric S-boxes constructed by concatenation of RSSBs KAVUT, SELÇUK; Baloglu, Sevdenur (Springer Science and Business Media LLC, 2019-07-01) In this paper, we first present an efficient exhaustive search algorithm to enumerate 6 x 6 bijective S-boxes with the best-known nonlinearity 24 in a class of S-boxes that are symmetric under the permutation (x) = (x(0), x(2), x(3), x(4), x(5), x(1)), where x = (x(0), x1,...,x5)?26. Since any S-box S:?26?26 in this class has the property that S((x)) = (S(x)) for every x, it can be considered as a construction obtained by the concatenation of 5 x 5 rotation-symmetric S-boxes (RSSBs). The size of the search ...
Constructions of bent functions Sulak, Fatih; Doğanaksoy, Ali; Department of Cryptography (2006) In cryptography especially in block cipher design, Boolean functions are the basic elements. A cryptographic function should have high nonlinearity as it can be attacked by linear attack. In this thesis the highest possible nonlinear boolean functions in the even dimension, that is bent functions, basic properties and construction methods of bent functions are studied. Also normal bent functions and generalized bent functions are presented.
WEIGHTED MATRIX ORDERING AND PARALLEL BANDED PRECONDITIONERS FOR ITERATIVE LINEAR SYSTEM SOLVERS Manguoğlu, Murat; Sameh, Ahmed H.; Grama, Ananth (Society for Industrial & Applied Mathematics (SIAM), 2010-01-01) The emergence of multicore architectures and highly scalable platforms motivates the development of novel algorithms and techniques that emphasize concurrency and are tolerant of deep memory hierarchies, as opposed to minimizing raw FLOP counts. While direct solvers are reliable, they are often slow and memory-intensive for large problems. Iterative solvers, on the other hand, are more efficient but, in the absence of robust preconditioners, lack reliability. While preconditioners based on incomplete factor...

Citation Formats

F.-W. Fu, H. Niederreiter, and F. Özbudak, “Joint linear complexity of multisequences consisting of linear recurring sequences,” CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, pp. 3–29, 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/44140.