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.

Abstract:

In this paper we systematically study the differential properties of addition modulo 2ⁿ. 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 Ω(2⁴ⁿ) to Θ(log n).

Keywords: NA.

Slides:

• conference slides

More information: CiteSeer.

• Helger Lipmaa
• Shiho Moriai

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