This item still needs to be validated !
ITEM METADATA RECORD
Title: Solving Systems of Differential Equations of Addition and Cryptanalysis of the Helix Cipher
Authors: Paul, Souradyuti
Preneel, Bart
Issue Date: 2005
Publisher: Springer-Verlag
Host Document: Lecture Notes in Computer Science vol:3574 pages:75-88
Conference: ACISP 2005 date:July 04-06, 2005
Abstract: Mixing addition modulo 2(n) (+) and exclusive-or (E)) have a host of applications in symmetric cryptography as the operations are fast and nonlinear over GF(2). We deal with a frequently encountered equation (x + y) circle plus ((x circle plus alpha) + (y circle plus beta)) = gamma. The difficulty of solving an arbitrary system of such equations - named differential equations of addition (DEA) - is an important consideration in the evaluation of the security of many ciphers against differential attacks. This paper shows that the satisfiability of an arbitrary set of DEA - which has so far been assumed hard for large n - is in the complexity class P. We also design an efficient algorithm to obtain all solutions to an arbitrary system of DEA with running time linear in the number of solutions. Our second contribution is solving DEA in an adaptive query model where an equation is formed by a query (alpha, beta) and oracle output gamma. The challenge is to optimize the number of queries to solve (x + y) circle plus ((x circle plus alpha) + (y circle plus beta)) = gamma. Our algorithm solves this equation with only 3 queries in the worst case. Another algorithm solves the equation (x+y) circle plus (x + (y circle plus beta)) = gamma with (n - t - 1) queries in the worst case (t is the position of the least significant '1' of x), and thus, outperforms the previous best known algorithm by Muller - presented at FSE '04 - which required 3(n - 1) queries. Most importantly, we show that the upper bounds, for our algorithms, on the number of queries match worst case lower bounds. This, essentially, closes further research in this direction as our lower bounds are optimal. Finally we describe applications of our results in differential cryptanalysis.
URI: 
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Electrical Engineering - miscellaneous
ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics

Files in This Item:
File Status SizeFormat
article-566.pdf Published 462KbAdobe PDFView/Open

 


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science