In cryptography output sequences of stream ciphers are binary valued (or more generally finite field valued). However mathematically sequences over real and complex variables can also be generated by stream ciphers utilising feedback shift registers. We can also convert a binary output sequence $w(k)$ of a stream cipher to real interval $[-1,1]$ by defining the sequence $z(k)=(-1)^{w(k)}$. I don't find literature on linear complexity theory of real and complex sequences in my searches. Why is such a theory not useful or interesting?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Generally speaking, the finite field theory is cleaner, being based on exact arithmetic. Since we require exact arithmetic in cryptography (otherwise things like uniform distribution are either impossible or very hard to prove and we need finite processes to actually implement cryptography) the theory over finite fields suffices.
A few notes:
- One can define the theory of linear complexity over an arbitrary infinite fields, such as $\mathbb{C}$ or $\mathbb{R}.$ For example linear recurrences over the reals are taught/used in undergraduate math and engineering classes. From a crypto point of view this linear complexity will be very unstable [if you have a small error in the value of the terms it will fluctuate wildly]
- There is a related question and answer about codes over complex fields where the issue of berlekamp massey over such fields is addressed at the link here.
- There is a theory of sequence complexity over $p-$adic fields, which represent feedback shift registers with carry, pioneered by Klapper and Goresky. See Wikipedia here.
- Finally if you perform the map $s_t=(-1)^{u_t}$ for a binary sequence you directly obtain a multiplicative recurrence for $s_t$ corresponding to the linear recurrence for $u_t$ such as $$ u_{t+3}=u_{t+1}\oplus u_{t} \Longleftrightarrow s_{t+3}=s_{t+1}s_{t} $$
-
$\begingroup$ Thanks Kodlu for your comments. Point 1 is interesting and I have been thinking on existence of stable minimal polynomials of real matrices and sequences. One thought arises from the multiplicative recurrence. Clearly s_t will have analogous multiplicative recurrence, as stable as additive rec of u_t. What can be said about relationship of additive linear rec of s_t with the sequence u_t? $\endgroup$ Aug 12, 2022 at 0:02
-
$\begingroup$ I am not sure how much one can say beyond the fact that they are the same recurrence (one multiplicative one additive) in the absence of errors. $\endgroup$– kodluAug 12, 2022 at 2:36
$\begingroup$
$\endgroup$
Such transformations are quite common in linear cryptanalysis, the process turns additive combinations of bits into multiplicative combinations of characters under the Hadamard transform. Calculations on the transform can then be informative about the input bits essentially using what is Fourier analysis in characteristic 2. The expected value of the transform is sometimes referred to as the bulge.
An example of the use of this transform is in the piling-up lemma in its expected value form. For a more modern usage see for example the proof of Theorem 6 of Cryptanalysis of stream ciphers with linear masking by Coppersmith et al