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 http://www.ucl.ac.uk/finance/research/post_award/post_award_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
ElimLin Algorithm Revisited
  • Publication Type:
  • Authors:
    Courtois N, Sepherdad P, Susil P, Vaudenay S
  • Publisher:
  • Publication date:
  • Pagination:
    306, 325
  • Published proceedings:
    FSE 2012, Fast Software Encryption - 19th International Workshop
  • Volume:
  • Series:
    Lecture Notes In Computer Science
  • Editors:
    Canteaut A
  • ISBN-13:
  • Status:
  • Name of conference:
    FSE 2012 (Fast Software Encryption)
  • Conference place:
    Washington, DC, USA
  • Conference start date:
  • Conference finish date:
  • Language:
  • Keywords:
    block ciphers, algebraic cryptanalysis, systems of sparse polynomial equations of low degree.
ElimLin is a simple algorithm for solving polynomial systems of multivariate equations over small finite fields. It was initially proposed as a single tool by Courtois to attack DES. It can reveal some hidden linear equations existing in the ideal generated by the system. We report a number of key theorems on ElimLin. Our main result is to characterize ElimLin in terms of a sequence of intersections of vector spaces. It implies that the linear space generated by ElimLin is invariant with respect to any variable ordering during elimination and substitution. This can be seen as surprising given the fact that it eliminates variables. On the contrary, monomial ordering is a crucial factor in Gröbner basis algorithms such as F4. Moreover, we prove that the result of ElimLin is invariant with respect to any affine bijective variable change. Analyzing an overdefined dense system of equations, we argue that to obtain more linear equations in the succeeding iteration in ElimLin some restrictions should be satisfied. Finally, we compare the security of LBlock and MIBS block ciphers with respect to algebraic attacks and propose several attacks on Courtois Toy Cipher version 2 (CTC2) with distinct parameters using ElimLin.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
UCL Researchers
Dept of Computer Science
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by