Analysis of the compression techniques and memory bit effects on compression for pseudo-random generation

Abstract

Compression of sequence is one of the most useful tools for strengthening the pseudo-random generators used in stream ciphers. Using compression components can prevent algebraic attacks against LFSR-based stream ciphers. Some of the proposed compression algorithms are bit-search generator (BSG), ABSG (modified version of BSG), Self-Shrinking Generator (SSG), Shrinking Generator (SG). In this thesis, we analyze the compression of pseudo-random generation and determine the optimum compression algorithm among existing ones that has the optimal trade-off between output rate and resistance against general attacks. We also aim to investigate the memory bit effect on compression for pseudo-random generation. We present the algorithm EBSG which is similar to ABSG. EBSG uses memory bit and after each output bit generation, it inserts the bit stored in memory to the input sequence. We show that EBSG increases output rate while providing good linear complexities and randomness.