SavedAdd your journal

Journals / Turkish Journal of Electrical Engineering and Computer Science / 2013 / Cilt: 21 - Sayı: 1

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

Hüseyin DEMİRCİ
Pages
186–197
Publication Date
2013-01-01
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

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.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:We propose a memory-based method for the solution of a specific type of nonlinear equation systems.
📊
Key Findings & Data: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.
💡
Conclusion & Impact: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.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Key words: Time-memory trade-off · solution of nonlinear equations · AES

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.

Özet

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.

🔖

Cite This Article

DEMİRCİ, H. (2013). A time--memory trade-off approach for the solution of nonlinear equation systems. Turkish Journal of Electrical Engineering and Computer Science, Cilt: 21 - Sayı: 1, 186–197. https://ajindex.com/articles/188632

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (21)

  1. A. Kipnis, A. Shamir, “Cryptanalysis of the HFE public key crypto system by relinearization”, In CRYPTO 99, LNCS, Vol. 1666, pp. 19–30, Springer-Verlag, 1999.
  2. N. Courtois, A. Klimov, J. Patarin, A. Shamir, “Efficient algorithms for solving overdefined systems of multivariate polynomial equations”, In EUROCRYPT 2000,
  3. LNCS, Vol. 1807, pp. 392–407, Springer-Verlag, 2000.
  4. N.T. Courtois, J. Pieprzyk, “Cryptanalysis of block ciphers with overdefined systems of equations”, In ASIACRYPT 2002,
  5. LNCS, Vol. 2501, pp. 267–287, Springer-Verlag, 2002. M.H. Hellman, “A cryptanalytic time-memory trade-off”, IEEE Transactions in Information Theory, Vol. IT-26, pp. 401–406, 1980.
  6. A. Biryukov, A. Shamir, “Cryptanalytic time/memory/data trade-offs for stream ciphers”, In ASIACRYPT 2000,
  7. LNCS, Vol. 1976, pp. 1–13, Springer-Verlag, 2000.
  8. A. Biryukov, A. Shamir, D. Wagner, “Real time cryptanalysis of A5/1 on a PC”, In FSE 2000,
  9. LNCS, Vol. 1978, pp. 37–44, Springer-Verlag, 2001. P. Oechslin, “Making a faster cryptanalytic time-memory trade-off”, In CRYPTO 2003,
  10. LNCS, Vol. 2729, pp. 617–630, Springer-Verlag, 2003. S.H. Babbage, “Improved exhaustive search attacks on stream ciphers”, In European Convention on Security and Detection, IEE Conference publication, Vol. 408, pp. 161–166, IEE, 1995. J.Dj. Goli´ c, “Cryptanalysis of alleged A5 stream cipher”, In EUROCRYPT 97, LNCS, Vol. 1233, pp. 239–255, Springer-Verlag, 1997.
  11. D.E. Denning, In Cryptography and Data Security, page 100, Addison-Wesley, 1982. W. Diffie, M.E. Hellman, “Exhaustive cryptanalysis of the NBS data encryption standard”, Computer, Vol. 10, 74–84, 1977.
  12. H. Morita, K. Ohta, K. Miyaguchi, “A switching closure test to analyze cryptosystems”, In CRYPTO 1991,
  13. LNCS, Vol. 576, pp. 183–193, Springer-Verlag, 1992.
  14. M. Matsui, A. Yamagishi, “A new method for known plaintext attack of FEAL cipher”, In EUROCRYPT 1992,
  15. LNCS, Vol. 658, pp. 81–91, Springer-Verlag, 1993.
  16. D. Khovratovich, I. Nikoli´ c, R.P. Weinmann, “Meet-in-the-middle attacks on SHA-3 candidates”, In FSE 2009,
  17. LNCS, Vol. 5665, pp. 228–245, Springer-Verlag, 2009.
  18. H. Gilbert, M. Minier, “A collision attack on 7 rounds of Rijndael”, In The Third AES Candidate Conference, 2000.
  19. H. Demirci, A.A. Sel¸cuk, “A meet in the middle attack on 8-round AES”, In FSE 2008,
  20. LNCS, Vol. 5086, pp. 116–126, Springer-Verlag, 2008.
  21. K. Nyberg, L.R. Knudsen, “Provable security against a differential attack”, Journal of Cryptology, Vol. 8(1), pp. 27–38, 1995. “Fips-197: Advanced Encryption Standard”,