Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleOn Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis
Author(s) Jiun-Ming Chen, Nicolas T. Courtois, Bo-Yin Yang
TextInformation and Communications Security: 6th International Conference, ICICS 2004, Malaga, Spain, October 27-29, 2004.
TypeBook, Chapter in Book, Conference Proceeding
Abstract"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.
KeywordsXL, Gröbner Bases, multivariate quadratics, algebraic cryptanalysis, asymptotic security estimates
URL DOI: 10.1007/b101042
JournalLecture Notes in Computer Science
PublisherSpringer-Verlag GmbH
EditorJ. Lopez, S. Qing, E. Okamoto
Translation No
Refereed No