Groups -- Complexity -- Cryptology 01 (2009), No. 2, 231--259
Copyright Heldermann Verlag 2009
Algebraic Attacks Galore!
Martin Kreuzer
Fakultät für Informatik und Mathematik, Universität Passau, 94030 Passau, Germany
Martin.Kreuzer@uni-passau.de
This is the first in a two-part survey of current techniques in algebraic cryptanalysis. After introducing the basic setup of algebraic attacks and discussing several attack scenarios for symmetric cryptosystems, public key cryptosystems, and stream ciphers, we discuss a number of individual methods. The XL, XSL, and MutantXL attacks are based on linearization techniques for multivariate polynomial systems. Then we look at Gröbner basis and border bases methods. In the last section we introduce attacks based on integer programming techniques and try them in some concrete cases.
Keywords: Cryptosystem, algebraic attack, polynomial system solving.
MSC: 11T71; 13P10, 94A60
[ Fulltext-pdf (236 KB)] for subscribers only.