000176270 001__ 176270
000176270 005__ 20180317093341.0
000176270 037__ $$aCONF
000176270 245__ $$aElimLin Algorithm Revisited
000176270 269__ $$a2012
000176270 260__ $$bSpringer$$c2012
000176270 336__ $$aConference Papers
000176270 490__ $$aLNCS
000176270 520__ $$aElimLin 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.
000176270 6531_ $$ablock ciphers
000176270 6531_ $$aalgebraic cryptanalysis
000176270 6531_ $$asystems of sparse polynomial equations of low degree
000176270 700__ $$aCourtois, Nicolas
000176270 700__ $$0243334$$aSepehrdad, Pouyan$$g186617
000176270 700__ $$0244132$$aSusil, Petr$$g190647
000176270 700__ $$0241950$$aVaudenay, Serge$$g131602
000176270 7112_ $$aFSE$$cWashington DC, USA$$dMarch 19-21, 2012
000176270 773__ $$tProceedings of Fast Software Encryption
000176270 8564_ $$s409193$$uhttps://infoscience.epfl.ch/record/176270/files/ElimLin_full_version.pdf$$yn/a$$zn/a
000176270 909CO $$ooai:infoscience.tind.io:176270$$pIC$$pconf
000176270 909C0 $$0252183$$pLASEC$$xU10433
000176270 917Z8 $$x186617
000176270 937__ $$aEPFL-CONF-176270
000176270 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000176270 980__ $$aCONF