Cryptology ePrint Archive: Report 2010/140

Improved Agreeing-Gluing Algorithm

Igor Semaev

Abstract: A system of algebraic equations over a finite field is called sparse if each equation depends on a low number of variables. Finding efficiently solutions to the system is an underlying hard problem in the cryptanalysis of modern ciphers. In this paper a deterministic Improved Agreeing-Gluing Algorithm is introduced. The expected running time of the new 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 [10, 11]. In sparse Boolean equations a gap between the worst case and the average time complexity of the problem has significantly increased.

Category / Keywords:

Date: received 13 Mar 2010

Contact author: igor at ii uib no

Available formats: PDF | BibTeX Citation

Version: 20100314:160838 (All versions of this report)

Discussion forum: Show discussion | Start new discussion