Information Technology Reference
In-Depth Information
Sequences, DFT and Resistance against Fast
Algebraic Attacks
(Invited Paper)
Guang Gong
Department of Electrical and Computer Engineering
University of Waterloo
Waterloo, Ontario N2L 3G1, Canada
ggong@calliope.uwaterloo.ca
Abstract.
The discrete Fourier transform (DFT) of a boolean function
yields a trace representation or equivalently, a polynomial representation,
of the boolean function, which is identical to the DFT of the sequence
associated with the boolean function. Using this tool, we investigate char-
acterizations of boolean functions for which the fast algebraic attack is
applicable. In order to apply the fast algebraic attack, the question that
needs to be answered is that: for a given boolean function f in n vari-
ables and a pair of positive integers ( d, e ), when there exists a function
g with degree at most d such that h = fg =0where h 's degree is at
most e . We give a sucient and necessary condition for the existence of
those multipliers of f . An algorithm for finding those multipliers is given
in terms of a polynomial basis of 2 n dimensional space over F 2 which is
established by an arbitrary m -sequence of period 2 n
1 together with
all its decimations and certain shifts. We then provide analysis for de-
generated cases and introduce a new concept of resistance against the
fast algebraic attack in terms of the DFT of sequences or boolean func-
tions. Some functions which made the fast algebraic attack inecient are
identified.
Keywords:
Discrete Fourier transform, fast algebraic attack, stream ci-
phers, LFSR, m -sequences, polynomials, bases, trace representations.
1
Introduction
Linear feedback shift register (LFSR) sequences are widely used as basic func-
tional blocks in key stream generators in stream cipher models due to their fast
implementation in hardware as well as in software in some cases. In LFSR based
stream ciphers, there are mainly two types of operations which operate on the
LFSRs: (a) outputs of one LFSR or multiple LFSRs are transformed by nonlin-
ear functions with or without memory states (including those by using mixed
finite field operations and integer modular operations); (b) change the clock of
the LFSRs to an irregular clock or by deleting some output bits of the LFSRs.
In theory, examples include filtering sequence generators (i.e., operate a boolean
 
Search WWH ::




Custom Search