Lecture Notes in Computer Science vol:3797 pages:90-103
INDOCRYPT 2005 date:December 10-12, 2005
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.