Conference Proceedings

Testing Stream Ciphers by Finding the Longest Substring of a Given Density

Serdar Boztas, Simon J Puglisi, Andrew Turpin, C Boyd (ed.), JG Nieto (ed.)

Proceedings of 14th Australasian Conference on Information Security and Privacy (ACISP2009) | SPRINGER-VERLAG BERLIN | Published : 2009


Given a string x[1..n] drawn from the alphabet {0,1}, and a rational density parameter 0 ≤ θ ≤ 1, this paper considers algorithms for finding the longest substring of x with density θ. That is, if the length of the substring is m, the number of one-bits in the substring is exactly θ×m. It is surprisingly difficult to devise an algorithm that has worst case time less than the obvious brute-force algorithm's O(n 2). We present three new approaches to reducing the running time, and an algorithm that solves the problem in O(nlogn) expected time. We then apply the new algorithm, as well as an empirical estimate of the lim-sup and the lim-inf of a centred statistic which is expected to obey a law ..

View full abstract

University of Melbourne Researchers


Funding Acknowledgements

This work is supported by the Australian Research Council.