About: 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 [Formula: see text], 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 symmetry breaking technique and optimizing the time complexity of the point decomposition step by a factor of m! for the [Formula: see text](th) 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 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 symmetry breaking technique is up to 300 times faster than Magma’s F4 implementation, and this factor grows with l and n.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • 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 [Formula: see text], 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 symmetry breaking technique and optimizing the time complexity of the point decomposition step by a factor of m! for the [Formula: see text](th) 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 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 symmetry breaking technique is up to 300 times faster than Magma’s F4 implementation, and this factor grows with l and n.
Subject
  • Commercial-free television networks
  • Proprietary commercial software for Linux
  • Banking technology
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software