AsymptoticBounds

Code for the paper “Computing Asymptotic Bounds for Small Roots in Coppersmith’s Method via Sumset Theory".

Introduction

This repository contains the implementation of the algorithms described in the paper "Computing Asymptotic Bounds for Small Roots in Coppersmith’s Method via Sumset Theory." The main goal of this work is to develop the first provable algorithm for determining asymptotic bounds in Coppersmith’s method by introducing Sumset theory from Additive Combinatorics. This significantly streamlines manual calculations and provides a more efficient approach compared to previous heuristic methods.

Usage

Prerequisites

• SageMath: This code requires SageMath to be installed. You can download it from SageMath.

Running the Code

To run the code, use the following command in your terminal:

sage -python potato.py

Debug

You can enable debugging by setting logging.basicConfig(filename='attack.log', level=logging.DEBUG, format='%(asctime)s - %(levelname)s - %(message)s') in your code.

Files

• potato.py: The main implementation of the algorithm for computing asymptotic bounds using Sumset theory. This script provides the core functionality for determining the bounds in Coppersmith's method.
• Sarkar.py: An alternative implementation inspired by Sarkar's approach. This script offers a different perspective on solving the problem and can be used for comparison with the main implementation.
• variantI.py: Implementation of Variant I of the algorithm. This variant introduces additional shifts to the polynomials to further optimize the bounds.
• variantII.py: Implementation of Variant II of the algorithm. This variant explores another set of optimizations and improvements over the base algorithm.

Example

Here is an example of how to use the VariantII.py script:

# Example for variantII
import time
from variantII import main

# Define the polynomial ring and polynomials
pr = PolynomialRing(QQ, ['x3', 'x1', 'x2'], order="lex")
x3, x1, x2 = pr.gens()
p = 2
f1 = x1**2 + x1*x2**2 + x1*x2 + x1 + x2**2 + x2 + 1
f2 = x3**2 + x1**2*x3 + x1*x3 + x3 + x1**2 + x1 + 1
polys = [f1, f2]

# Run the main function
start_polytope = time.time()
N_f = main(pr, polys, p, shift=3)
end_polytope = time.time()
print("Time using polytope: ", end_polytope - start_polytope)

More examples can be found in example.ipynb.

Author

You can find more information on my personal website.

License

This script is released under the MIT License. See the LICENSE file for details.