Computer Science – Cryptography and Security
Scientific paper
2007-02-16
Computer Science
Cryptography and Security
20 pages, 2 figures and submitted to IEEE Transactions on Information Theory
Scientific paper
We investigate the bit-search type irregular decimation algorithms that are used within LFSR-based stream ciphers. In particular, we concentrate on BSG and ABSG, and consider two different setups for the analysis. In the first case, the input is assumed to be a m-sequence; we show 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, we prove that the cardinality of each of these sets is equal to the period of one of its elements and subsequently derive the first known bounds on the expected output period (assuming that no subperiods exist). In the second setup, we work in a probabilistic framework and assume that the input sequence is evenly distributed (i.e., independent identically distributed Bernoulli process with probability 1/2). Under these assumptions, we derive closed-form expressions 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.
Altug Yucel
Anarim Emin
Ayerden Polat N.
Mihcak Kivanc M.
No associations
LandOfFree
A Note on the Periodicity and the Output Rate of Bit Search Type Generators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Note on the Periodicity and the Output Rate of Bit Search Type Generators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on the Periodicity and the Output Rate of Bit Search Type Generators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-196305