A SAT-based approach for index calculus on binary elliptic curves

Monika Trimoska, Sorina Ionica, and Gilles Dequen

Abstract

Logical cryptanalysis, first introduced by Massacci in 2000, is a viable alternative to common algebraic cryptanalysis techniques over boolean fields. With XOR operations being at the core of many cryptographic problems, recent research in this area has focused on handling XOR clauses efficiently. In this paper, we investigate solving the point decomposition step of the index calculus method for prime degree extension fields $\mathbb{F}_{2^n}$, using SAT solving methods. We experimented with different SAT solvers and decided on using WDSat, a solver dedicated to this specific problem. We extend this solver by adding a novel breaking symmetry technique and optimizing the time complexity of the point decomposition step by a factor of $m!$ for the $(m+1)$\textsuperscript{th} Semaev's summation polynomial. While asymptotically solving the point decomposition problem with this method has exponential worst time complexity in the dimension $l$ of the vector space defining the factor base, experimental running times show that the the presented SAT solving technique is significantly faster than current algebraic methods based on Gröbner basis computation. For the values $l$ and $n$ considered in the experiments, the WDSat solver coupled with our breaking symmetry technique is up to 300 times faster then MAGMA's F4 implementation, and this factor grows with $l$ and $n$.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Progress in Cryptology - AFRICACRYPT 2020
DOI
10.1007/978-3-030-51938-4_11
Keywords
discrete logarithmindex calculuselliptic curvespoint decompositionsymmetrysatisfiabilityDPLL algorithm
Contact author(s)
monika trimoska @ u-picardie fr
sorina ionica @ u-picardie fr
gilles dequen @ u-picardie fr
History
2020-12-18: last of 6 revisions
See all versions
Short URL
https://ia.cr/2019/313

CC BY

BibTeX

@misc{cryptoeprint:2019/313,
author = {Monika Trimoska and Sorina Ionica and Gilles Dequen},
title = {A SAT-based approach for index calculus on binary elliptic curves},
howpublished = {Cryptology ePrint Archive, Paper 2019/313},
year = {2019},
doi = {10.1007/978-3-030-51938-4_11},
note = {\url{https://eprint.iacr.org/2019/313}},
url = {https://eprint.iacr.org/2019/313}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.