Linear Complexity Profiles: Hausdorff Dimensions for Almost Perfect Profiles and Measures for General Profiles

✍ Scribed by Harald Niederreiter; Michael Vielhaber

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 252 KB
• Volume: 13
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.1997.0451

✦ Synopsis

Stream ciphers usually employ some sort of pseudorandomly generated bit strings to be added to the plaintext. The cryptographic properties of such a sequence a can be stated in terms of the so-called linear complexity profile (l.c.p.), ), it is called (almost) perfect. This paper examines first those subsets

q where for fixed d ∈ the l.c.p. satisfies |2 • L a (t) -t| ≤ d for all t ∈ . It turns out that (after suitably mapping A (q)

where ϕ (q) d is the largest real root of x d = (q -1) • d-1 i=0 x i . The second part deals with nondecreasing bounds d: → . Since d(t) → ∞ as t → ∞ always leads to a Hausdorff dimension 1, here we consider the measure of the set A (q)

d .