Information Technology Reference
In-Depth Information
from
F
2
and the boolean representation of the function. In this paper, we
use the polynomial representation, which have advantages in analysis of crypto-
graphical properties of functions. Another advantage is to prevent finding a low
degree multiplier probabilistically. In general, for a boolean representation, if
the number of monomial terms with high degrees are small, then one can easily
remove these terms for obtaining a low degree function for which the probabil-
ity that these two functions are equal is close to 1. However, if a function is
in a polynomial form, the degree of the function is governed by the Hamming
weights of exponents in monomial trace terms. Removing one or more monomial
trace terms from the expression may result in a large change of the distance
between the function and the resulting function, since it is equivalent to cal-
culate the distance of two codewords of a cyclic code. So, the probability that
these two functions are equal is not close to 1, possibly, close to 1
/
2. However,
boolean forms are easily used to analyze the correlation immunity/resiliency and
propagation property, and they can also be eciently implemented at hardware
level.
F
2
n
to
Acknowledgement
The work is supported by NSERC Discovery Grant. The author wishes to thank
the referee for his/her valuable comments.
References
1. Armknecht, F., Krause, M.: Algebraic attacks on combiners with memory. In:
Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 162-175. Springer, Hei-
delberg (2003)
2. Armknecht, F.: Improving fast algebraic attacks. In: Roy, B., Meier, W. (eds.) FSE
2004. LNCS, vol. 3017, pp. 65-82. Springer, Heidelberg (2004)
3. Armknecht, F., Ars, G.: Introducing a new variant of fast algebraic attacks and
minimizing their successive data complexity. In: Dawson, E., Vaudenay, S. (eds.)
Mycrypt 2005. LNCS, vol. 3715, pp. 16-32. Springer, Heidelberg (2005)
4. Bluetooth CIG, Specification of the Bluetooth system, Version 1.1 (February 22,
2001),
www.bluetooth.com
5. Canteaut, A., Carlet, C., Charpin, P., Fontaine, C.: On cryptographic properties
of the cosets of
R
(1
,m
). IEEE Trans. on Inform. Theory 47(4), 1491-1513 (2001)
6. Carlet, C.: On the higher order nonlinearities of algebraic immune functions. In:
Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 584-601. Springer, Heidel-
berg (2006)
7. Courtois, N.: Higher order correlation attacks, XL algorithm and cryptanalysis
of Toyocrypt. In: Lee, P.J., Lim, C.H. (eds.) ICISC 2002. LNCS, vol. 2587, pp.
549-564. Springer, Heidelberg (2003)
8. Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback.
In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345-359. Springer,
Heidelberg (2003)
