BooleanSolve doctest failing with Python

[Dioprz]

@fmerino21 had shared with me some days ago that one of the UOVEstimator doctest was failing when running with Python instead of Sage.

The failing doctest is this one:

CryptographicEstimators/cryptographic_estimators/UOVEstimator/uov_estimator.py

Lines 130 to 141 in 9637e57

	sage: A = UOVEstimator(n=184, m=72, q=256, theta=None)
	sage: A.table(show_all_parameters=1) # long time
	+--------------------+--------------+-----------------------------------------------+
	| | | estimate |
	+--------------------+--------------+-------+--------+------------------------------+
	| algorithm | attack_type | time | memory | parameters |
	+--------------------+--------------+-------+--------+------------------------------+
	| DirectAttack | forgery | 217.9 | 87.0 | {} |
	| KipnisShamir | key-recovery | 348.2 | 24.2 | {} |
	| CollisionAttack | forgery | 301.6 | 293.3 | {'X': 292.034, 'Y': 282.331} |
	| IntersectionAttack | key-recovery | 249.9 | 117.9 | {'k': 2} |
	+--------------------+--------------+-------+--------+------------------------------+

Steps to reproduce

1. make docker-run

2. In a python3 REPL, run:

   from cryptographic_estimators.UOVEstimator import UOVEstimator
   A = UOVEstimator(n=184, m=72, q=256, theta=None)
   A.table(show_all_parameters=1) # long time

   You will get:

   ...
   File "/home/cryptographic_estimators/cryptographic_estimators/MQEstimator/MQAlgorithms/booleansolve_fxl.py", line 184, in _compute_time_complexity
     time_complexity = q**k * m * binomial(n - k + wit_deg, wit_deg) ** w
   OverflowError: int too large to convert to float

3. If you run the same in a sage REPL, everything works normally (this will take some minutes).

Solution:

The error comes from the file cryptographic_estimators/MQEstimator/MQAlgorithms/booleansolve_fxl.py, specifically from this lines of the _compute_time_complexity method:

CryptographicEstimators/cryptographic_estimators/MQEstimator/MQAlgorithms/booleansolve_fxl.py

Lines 169 to 189 in 9637e57

	k = parameters["k"]
	variant = parameters[MQ_VARIANT]
	n, m, q = self.get_reduced_parameters()
	w = self.linear_algebra_constant()
	wit_deg = witness_degree.quadratic_system(n=n - k, m=m, q=q)
	if variant == MQ_LAS_VEGAS:
	time_complexity = (
	3
	* binomial(n - k + 2, 2)
	* q**k
	* binomial(n - k + wit_deg, wit_deg) ** 2
	)
	elif variant == MQ_DETERMINISTIC:
	time_complexity = q**k * m * binomial(n - k + wit_deg, wit_deg) ** w
	else:
	raise ValueError("variant must either be las_vegas or deterministic")
	h = self._h
	return log2(time_complexity) + h * log2(q)

Specifically, from the expression q**k * m * binomial(n - k + wit_deg, wit_deg) ** w

The issue can likely be solved by integrating the log2 directly into the if/elif blocks, so logarithms properties help us lowering the powers.

Did you agree? Could any of you help me ensuring this will not break anything (or implementing the patch) please? @Memphisd @Javierverbel @FloydZ

[Javierverbel]

@Dioprz I pushed a fix for this here