Solving Systems of Differential Equations of Addition
(Extended Abstract)
详细信息 查看全文
- 作者：Souradyuti Paul ; Bart Preneel
- 刊名：Lecture Notes in Computer Science
- 出版年：2005
- 出版时间：2005
- 年：2005
- 卷：3574
- 期：1
- 页码：p.75
- 全文大小：260 KB
文摘
Mixing addition modulo 2n (+) and exclusive-or (⊕) 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)⊕((x⊕α)+(y⊕β))=γ. 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.