Jeudi 16 mai 2019 à 16h30 en salle C48
Monika Trimoska (Université de Picardie)
Titre : A SAT-based approach for index calculus on binary elliptic curves
Résumé :
Logical cryptanalysis 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 talk, we explain how cryptographic attacks can be transformed to Satisfiability problems and we present an original XOR-reasoning SAT solver, named WDSat. Additionally, we investigate solving the point decomposition step of the index calculus method for prime degree extension fields $\F_{2^n}$, using the WDSat solver. 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.