This item still needs to be validated !
ITEM METADATA RECORD
Title: Near Optimal Algorithms for Solving Differential Equations of Addition with Batch Queries
Authors: Paul, Souradyuti
Preneel, Bart
Issue Date: 2005
Publisher: Springer-Verlag
Host Document: Lecture Notes in Computer Science vol:3797 pages:90-103
Conference: INDOCRYPT 2005 date:December 10-12, 2005
Abstract: Combination of modular addition (+) and exclusive-or (0) is one of the widely used symmetric cipher components. The paper investigates the strength of modular addition against differential cryptanalysis (DC) where the differences of inputs and outputs are expressed as XOR. In particular, we solve two very frequently used equations (1) (x+y)circle plus(x+(y circle plus beta)) = gamma and (2) (x+y)circle plus((x circle plus alpha) + (y circle plus beta)) = gamma, known as the differential equations of addition (DEA), with a set of batch queries. In a companion paper, presented at ACISP'05, we improved the algorithm by Muller (at FSE'04) to design optimal algorithms to solve the equations with adaptive queries. However, a nontrivial solution with batch queries has remained open. The major contributions of this paper are (i) determination of lower bounds on the required number of batch queries to solve the equations and (ii) design of two algorithms which solve them with queries close to optimal. Our algorithms require 2(n-2) and 6 queries to solve (1) and (2) where the lower bounds are 3/4(.)2(n-2) (theoretically proved) and 4 (based on extensive experiments) respectively (n is the bit-length of x, y, alpha,beta,gamma). This exponential lower bound is an important theoretical benchmark which certifies (1) as strong against DC. On the other hand, the constant number of batch queries to solve (2) discovers a major weakness of modular addition against DC.
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-587.pdf Published 242KbAdobe PDFView/Open

 


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

© Web of science