Cryptology ePrint Archive: Report 2010/140
Improved Agreeing-Gluing Algorithm
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.
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.
Category / Keywords:
Date: received 13 Mar 2010, last revised 11 Jun 2012
Contact author: Extended Abstract in SCC2010
Available format(s): PDF | BibTeX Citation
Note: Full paper, new sections were added
Version: 20120611:194723 (All versions of this report)
Short URL: ia.cr/2010/140
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]