DocumentCode :
3807119
Title :
A Note on the Periodicity and the Output Rate of Bit Search Type Generators
Author :
Y?cel Altug;N. Polat Ayerden;M. Kivan? Mihcak;Emin Anarim
Author_Institution :
Bogazici Univ., Istanbul
Volume :
54
Issue :
2
fYear :
2008
Firstpage :
666
Lastpage :
679
Abstract :
In this paper, the bit-search type irregular decimation algorithms, that are used within linear-feedback shift register (LFSR)-based stream ciphers, are investigated. In particular, bit-search generator (BSG) and and its variant ABSG are concentrated on and two different setups are considered for the analysis. In the first case, the input is assumed to be an m-sequence; it is shown that all possible output sequences can be classified into two sets, each of which is characterized by the equivalence of their elements up to shifts. Furthermore, it is proved that the cardinality of each of these sets is equal to the period of one of its elements and subsequently the (upper and lower) bounds on the expected output period (assuming that no subperiods exist) are derived. In the second setup, we work in a probabilistic framework and assume that the input sequence is evenly distributed (i.e., independent and identically distributed (i.i.d.) Bernoulli process with probability 1/2). Under these assumptions, closed-form expressions are derived for the distribution of the output length and the output rate, which is shown to be asymptotically Gaussian-distributed and concentrated around the mean with exponential tightness.
Keywords :
"Shift registers","Cryptography","Security","Closed-form solution","Gaussian distribution","Polynomials","Linearity","Engineering profession","Hardware"
Journal_Title :
IEEE Transactions on Information Theory
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2007.913503
Filename :
4439830
Link To Document :
بازگشت