2009 | OriginalPaper | Buchkapitel
Almost Fully Optimized Infinite Classes of Boolean Functions Resistant to (Fast) Algebraic Cryptanalysis
verfasst von : Enes Pasalic
Erschienen in: Information Security and Cryptology – ICISC 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper the possibilities of an iterative concatenation method towards construction of Boolean functions resistant to algebraic cryptanalysis are investigated. The notion of
$\mathcal{AAR}$
(Algebraic Attack Resistant) function is introduced as a unified measure of protection against classical algebraic attacks as well as fast algebraic attacks. Then, it is shown that functions that posses the highest resistance to fast algebraic attacks are necessarily of maximum
$\mathcal{AI}$
(Algebraic Immunity ), the notion introduced in [20] defined as a minimum degree of functions that annihilate either
f
or 1 +
f
. More precisely, if for any non-annihilating function
g
of degree
e
an optimum degree relation
e
+
d
≥
n
is satisfied in the product
fg
=
h
(denoting
deg
(
h
) =
d
), then the function
f
in
n
variables must have maximum
$\mathcal{AI}$
, i.e. for nonzero function
g
the relation
fg
= 0 or (1 +
f
)
g
= 0 implies
$deg(g)\geq \frac{n}{2}$
. The presented theoretical framework allows us to iteratively construct functions with maximum
$\mathcal{AI}$
satisfying
e
+
d
≥
n
− 1, thus almost optimized resistance to fast algebraic cryptanalysis. This infinite class for the first time, apart from almost optimal resistance to algebraic cryptanalysis, in addition generates the functions that possess high nonlinearity (superior to previous constructions) and maximum algebraic degree, thus unifying most of the relevant cryptographic criteria.