CryptoDB
Improved Agreeing-Gluing Algorithm
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2010-23041,
title={Improved Agreeing-Gluing Algorithm},
booktitle={IACR Eprint archive},
keywords={},
url={http://eprint.iacr.org/2010/140},
note={ igor@ii.uib.no 14681 received 13 Mar 2010},
author={Igor Semaev},
year=2010
}