2004 | OriginalPaper | Buchkapitel
On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis
verfasst von : Bo-Yin Yang, Jiun-Ming Chen, Nicolas T. Courtois
Erschienen in: Information and Communications Security
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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
“Algebraic Cryptanalysis” against a cryptosystem often comprises finding enough relations that are generally or probabilistically valid, then solving the resultant system. The security of many schemes (most important being AES) thus depends on the difficulty of solving multivariate polynomial equations. Generically, this is NP-hard.The related methods of XL (eXtended Linearization), Gröbner Bases, and their variants (of which a large number has been proposed) form a unified approach to solving equations and thus affect our assessment and understanding of many cryptosystems.Building on prior theory, we analyze these XL variants and derive asymptotic formulas giving better security estimates under XL-related algebraic attacks; through this examination we have hopefully improved our understanding of such variants. In particular, guessing a portion of variables is a good idea for both XL and Gröbner Bases methods.