CWI Cryptology Group

Abstract: In this talk I will compare two alternative complexity concepts: first I present the linear complexity with the help of Linear Feedback Shift Registers, and the Berlekamp-Massey algorithm for computing this measure. Then I introduce the so-called f-complexity, suggested by R. Ahlswede, L. Khachatrian, C. Mauduit and A. Sarkozy. The f-complexity turned out to be a useful concept: there are some recently created constructions that aim for a better constructability and computability, and whose high complexity could easily be proven using this new measure. But the linear complexity of these f-complex constructions has never been studied. It seems to be a hopelessly difficult task to verify that these constructions have high linear complexity with any chosen parameters. Here I will show that for some randomly chosen parameters the binary sequence generated by such a construction has a high linear complexity. Finally I will discuss the possible theoretical relationship of the two complexity concepts.