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

Hüseyin DEMİRCİ

Article Details

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

Authors:

Hüseyin DEMİRCİ

Publisher:

TUBITAK

Journal:

Turkish Journal of Electrical Engineering and Computer Science 2013 Vol.21 Issue 1, pp.186-197

Document Type:

Article

Publication Date:

12/2012

Document Language:

Turkish

Document ID (Org No.):

2000743393

Frequency:

Bimonthly

eISSN:

1303-6203

pISSN:

1300-0632

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 O(n/2.   2n/2) operations and using O(2n/2) units of memory rather than  O(2n) trials of the equation system.

 

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 O(n/2.   2n/2) operations and using O(2n/2) units of memory rather than  O(2n) trials of the equation system.

Article Details

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

Authors: Hüseyin DEMİRCİ

Publisher: TUBITAK

Journal: Turkish Journal of Electrical Engineering and Computer Science 2013 Vol.21 Issue 1, pp.186-197

Document Type: Article

Publication Date: 12/2012

Document Language: Turkish

Document ID (Org No.): 2000743393

Frequency: Bimonthly

eISSN: 1303-6203

pISSN: 1300-0632

Issues

Authors:

Hüseyin DEMİRCİ

Publisher:

TUBITAK

Journal:

Turkish Journal of Electrical Engineering and Computer Science 2013 Vol.21 Issue 1, pp.186-197

Document Type:

Article

Publication Date:

12/2012

Document Language:

Turkish

Document ID (Org No.):

2000743393

Frequency:

Bimonthly

eISSN:

1303-6203

pISSN:

1300-0632