Helger Lipmaa's publications

Efficient Algorithms for Computing Differential Properties of Addition

Helger Lipmaa and Shiho Moriai. Efficient Algorithms for Computing Differential Properties of Addition. In Mitsuru Matsui, editor, Fast Software Encryption: 8th International Workshop, FSE 2001, volume 2355 of Lecture Notes in Computer Science, pages 336--350, Yokohama, Japan, April 2--4, 2001. Springer, Heidelberg. ISBN 3-540-43869-6.

File: [.ps.bz2 (66 KB), .pdf (168 KB)] ps recommended.


In this paper we systematically study the differential properties of addition modulo 2n. We derive Θ(log n)-time algorithms for most of the properties, including differential probability of addition. We also present log-time algorithms for finding good differentials. Despite the apparent simplicity of modular addition, the best known algorithms required naive exhaustive computation. Our results represent a significant improvement over them. In the most extreme case, we present a complexity reduction from Ω(24n) to Θ(log n).

Keywords: NA.


More information: CiteSeer.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.