Cryptology ePrint Archive: Report 2019/313

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

Monika Trimoska and 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 propose an original XOR-reasoning SAT solver, named WDSat, dedicated to this specific problem. While asymptotically solving the point decomposition problem with our method has exponential worst time complexity in the dimension $l$ of the vector space defining the factor base, experimental running times show that our solver is significantly faster than current algebraic methods based on Gröbner basis computation. For the values $l$ and $n$ considered in the experiments, WDSat was up to 300 times faster then MAGMA's F4 implementation, and this factor grows with $l$ and $n$. Our solver outperforms as well current best state-of-the-art SAT solvers for this specific problem.

Category / Keywords: public-key cryptography / discrete logarithm, index calculus, elliptic curves, point decomposition, symmetry, satisfiability, DPLL algorithm

Date: received 20 Mar 2019, last revised 15 May 2019

Contact author: monika trimoska at u-picardie fr,sorina ionica@u-picardie fr,gilles dequen@u-picardie fr

Available format(s): PDF | BibTeX Citation

Version: 20190515:132738 (All versions of this report)

Short URL: ia.cr/2019/313


[ Cryptology ePrint archive ]