A time--memory trade-off approach for the solution of nonlinear equation systems

Authors : Hüseyin DEMİRCİ

Pages : 186-197

Doi:10.3906/elk-1103-42

View : 19 | Download : 8

Publication Date : 0000-00-00

Article Type : Research Paper

Abstract :We propose a memory-based method for the solution of a specific type of nonlinear equation systems. We observe that when the equations in a system can be separated into 2 parts, where each subset contains fewer parameters than the whole set of equations, the system can be solved faster with a preprocessing phase. We show that reduced rounds of AES produce such a system under a chosen plaintext scenario. This observation enables us to solve that system within a practically applicable complexity of 237 operations where a brute force approach requires 272 trials. The method can be used for the solution of other equation systems of the same structure. In the optimal case where we can divide the equations into 2, a problem that contains n binary variables can be solved at time Oinsert ignore into journalissuearticles values(n/2. 2n/2); operations and using Oinsert ignore into journalissuearticles values(2n/2); units of memory rather than Oinsert ignore into journalissuearticles values(2n); trials of the equation system.
Keywords : Key words Time memory trade off, solution of nonlinear equations, AES, cryptanalysis