BooleanSolveFXL-only for evaluating the complexity of Hashimoto's algorithm

[maxostuzzi]

In estimating the bit complexity of Hashimoto's algorithm, only BooleanSolveFXL is considered, while it should be considered the MQ solving algorithm with the smallest bit complexity available. This causes an overestimation of the complexity for some parameters.

[Javierverbel]

Dear @maxostuzzi,
You are absolutely right. The simplified approach used to estimate Hashimoto’s complexity may indeed lead to overestimations for certain parameter regimes.
The main reasons for considering only BooleanSolveFXL as the initial internal solver in our implementation of Hashimoto’s estimator are the following:
In the original paper, Hashimoto’s algorithm is evaluated exclusively using BooleanSolveFXL as the internal solver.
For most cryptographic schemes where Hashimoto’s algorithm represents the best known attack, BooleanSolveFXL is also the only solver considered. A an example of this is the MAYO scheme.
We consider it important to design the estimator so that most relevant results from the literature can be reproduced directly using the library, provided that the appropriate configuration is specified.
Thanks to your comment, we are now considering the possibility of adding an additional parameter to the Hashimoto estimator to define the set of internal algorithms to be used. For instance, something like:

internal_mq_solvers = [BooleanSolveFXL]                # default
internal_mq_solvers = [BooleanSolveFXL, AdditionalAlgorithm1, AdditionalAlgorithm2]
internal_mq_solvers = ["All"]                          # consider all available MQ solvers

By default, we prefer not to include all solvers in order to keep the estimation process efficient. In addition, using only BooleanSolveFXL should remain a good approximation for most practically relevant cases.