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

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 2(37) operations where a brute force approach requires 2(72) 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 O(n/2 . 2(n/2)) operations and using O(2(n/2)) units of memory rather than O(2(n)) trials of the equation system.