UCL  IRIS
Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at https://www.ucl.ac.uk/finance/research/rs-contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis
  • Publication Type:
    Conference
  • Authors:
    Yang BY, Chen JM, Courtois NT
  • Publisher:
    Springer-Verlag
  • Publication date:
    2004
  • Place of publication:
    Berlin / Heidelberg, Germany
  • Pagination:
    401, 413
  • Published proceedings:
    Information and Communications Security: 6th International Conference, ICICS 2004, Malaga, Spain, October 27-29, 2004: Proceedings
  • Volume:
    3269
  • Series:
    Lecture Notes in Computer Science
  • Editors:
    Lopez J,Qing S,Okamoto E
  • ISBN-10:
    3540235639
  • Status:
    Published
  • Language:
    English
  • Keywords:
    Grobner bases, XL algorithm and variants, Sflash signature scheme
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.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
There are no UCL People associated with this publication
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by