TY - GEN
T1 - On polynomial systems arising from a Weil descent
AU - Petit, Christophe
AU - Quisquater, Jean Jacques
PY - 2012
Y1 - 2012
N2 - In the last two decades, many computational problems arising in cryptography have been successfully reduced to various systems of polynomial equations. In this paper, we revisit a class of polynomial systems introduced by Faugère, Perret, Petit and Renault. Based on new experimental results and heuristic evidence, we conjecture that their degrees of regularity are only slightly larger than the original degrees of the equations, resulting in a very low complexity compared to generic systems. We then revisit the application of these systems to the elliptic curve discrete logarithm problem (ECDLP) for binary curves. Our heuristic analysis suggests that an index calculus variant due to Diem requires a subexponential number of bit operations O(2 c n2/3 log n) over the binary field double-struck F2n, where c is a constant smaller than 2. According to our estimations, generic discrete logarithm methods are outperformed for any n > N where N ≈ 2000, but elliptic curves of currently recommended key sizes (n ≈ 160) are not immediately threatened. The analysis can be easily generalized to other extension fields.
AB - In the last two decades, many computational problems arising in cryptography have been successfully reduced to various systems of polynomial equations. In this paper, we revisit a class of polynomial systems introduced by Faugère, Perret, Petit and Renault. Based on new experimental results and heuristic evidence, we conjecture that their degrees of regularity are only slightly larger than the original degrees of the equations, resulting in a very low complexity compared to generic systems. We then revisit the application of these systems to the elliptic curve discrete logarithm problem (ECDLP) for binary curves. Our heuristic analysis suggests that an index calculus variant due to Diem requires a subexponential number of bit operations O(2 c n2/3 log n) over the binary field double-struck F2n, where c is a constant smaller than 2. According to our estimations, generic discrete logarithm methods are outperformed for any n > N where N ≈ 2000, but elliptic curves of currently recommended key sizes (n ≈ 160) are not immediately threatened. The analysis can be easily generalized to other extension fields.
UR - http://www.scopus.com/inward/record.url?scp=84871537002&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-34961-4_28
DO - 10.1007/978-3-642-34961-4_28
M3 - Conference contribution
AN - SCOPUS:84871537002
SN - 9783642349607
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 451
EP - 466
BT - Advances in Cryptology, ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
T2 - 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012
Y2 - 2 December 2012 through 6 December 2012
ER -