Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. ElimLin Algorithm Revisited
 
conference paper

ElimLin Algorithm Revisited

Courtois, Nicolas
•
Sepehrdad, Pouyan  
•
Susil, Petr  
Show more
2012
Fast Software Encryption. FSE 2012
FSE

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 Grobner 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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-34047-5_18
Author(s)
Courtois, Nicolas
Sepehrdad, Pouyan  
Susil, Petr  
Vaudenay, Serge  
Date Issued

2012

Publisher

Springer

Published in
Fast Software Encryption. FSE 2012
Series title/Series vol.

Lecture Notes in Computer Science; 7549

Start page

306

End page

325

Subjects

block ciphers

•

algebraic cryptanalysis

•

systems of sparse polynomial equations of low degree

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LASEC  
Event nameEvent placeEvent date
FSE

Washington DC, USA

March 19-21, 2012

Available on Infoscience
April 19, 2012
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/79467
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés