Improved Agreeing-Gluing Algorithm

Igor Semaev

Paper 2010/140

Improved Agreeing-Gluing Algorithm

Igor Semaev

Abstract

In this paper we study the asymptotical complexity of solving a system of sparse algebraic equations over finite fields. An equation is called sparse if it depends on a bounded number of variables. Finding efficiently solutions to the system of such equations is an underlying hard problem in the cryptanalysis of modern ciphers. New deterministic Improved Agreeing-Gluing Algorithm is introduced. The expected running time of the Algorithm on uniformly random instances of the problem is rigorously estimated. The estimate is at present the best theoretical bound on the complexity of solving average instances of the problem. In particular, this is a significant improvement over those in our earlier papers [20,21]. In sparse Boolean equations a gap between the present worst case and the average time complexity of the problem has significantly increased. Also we formulate Average Time Complexity Conjecture. If proved that will have far-reaching consequences in the field of cryptanalysis and in computing in general.

Note: Full paper, new sections were added

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Extended Abstract in SCC2010
Contact author(s): hiding @ example com
History: 2012-06-11: revised; 2010-03-14: received; See all versions
Short URL: https://ia.cr/2010/140
License: CC BY

BibTeX

@misc{cryptoeprint:2010/140,
      author = {Igor Semaev},
      title = {Improved Agreeing-Gluing Algorithm},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/140},
      year = {2010},
      url = {https://eprint.iacr.org/2010/140}
}