Reducing the Number of Qubits in Quantum Discrete Logarithms on Elliptic Curves

This repository contains the code of the paper Reducing the Number of Qubits in Quantum Discrete Logarithms on Elliptic Curves by Clémence Chevignard, Pierre-Alain Fouque and André Schrottenloher.

We provide implementations for the main components of the algorithm presented in the paper, up to the RNS binary tree. We do not provide an implementation of the full algorithm, which would be out of reach for the framework used at the moment (and difficult to simulate / test). A handful of scripts allow to recompute the resource estimates and re-obtain the main tables of the paper.

Structure

Most of the code can be found in /ecdlp. Files named *_test.py are unit test files. Outside /ecdlp the following scripts are provided:

• legendre_symbol.py: performs experiments with our Legendre / Jacobi symbol algorithm (Section 4.2 & 4.3 in the paper)

• parameters.py: displays the RNS parameters (Table 2 in the paper)

• pebbling_tree.py: prints the counts of operations for the spooky pebbling of the binary tree, for different numbers of leaves (Table 3 in the paper)

• rns_addition_tree_cost.py: constructs the whole RNS tree circuit (Section 5 & 6 in the paper)

• rns_addition_tree_run.py: runs the whole RNS tree circuit and checks that it indeed outputs the RNS residue.

• full_cost.py: displays Table 5 and 8

• rns_size_experimental.py: estimates experimentally the bit-size of the integers that need to be represented in the RNS.

Installation

The code requires the python library Qarton, which is available here and requires Python 3.12. You need the release 0.2.0. Please note that older python versions than 3.12 will likely fail, while never python versions will likely work. We provide two methods to install and run the code.

With a Python virtual environment

For this method, you need to have curl, unzip and python3-venv installed. Run the install.sh script:

chmod +x install.sh
./install.sh

After installation, you can activate the virtual environment using:

source .venv-qarton/bin/activate

With Docker

Alternatively, we provide a Dockerfile. To build the Docker image:

docker build -t ecdlp .

Afterwards, to run the Docker image:

docker run -it --rm ecdlp

After installation

Whether you are in the python virtual environment or in the Docker image, you can run the tests and execute the scripts using the commands given below.

Note that for many tests and scripts, running the code for the first time will take longer, as there are lots of precomputations which are tabulated and stored into JSON files locally.

Testing

Run:

cd ecdlp
pytest .

To run all available unit tests. Running all the tests from scratch may take a few minutes, as the curve_params_test.py needs precomputations for the P224 parameters, whose results are later stored in the precomputations sub-folder. The tests will appear stuck on curve_params_test.py until it finally completes.

Reproducing the results

The scripts are intended to reproduce the results of the paper. Here is a suggested order:

1. Use legendre_symbol.py to reproduce the statistics on the parameters of our Jacobi symbol algorithm which are given in Section 4.2 and 4.3. Running:

python legendre_symbol.py iterations -n 100

Produces a number of figures showing the different statistics. These figures are stored locally as PDF files named:

• number_iterations_{n}_{nb_trials}.pdf
• number_garbage_bits_{n}_{nb_trials}.pdf
• p_padding_{n}_{nb_trials}.pdf
• garbage_padding_{n}_{nb_trials}.pdf

Where {n} is the bit-size of the inputs and {nb_trials} is the number of random inputs that we used for the statistics.

These histograms were not included in the paper for the sake of brevity, but they correspond to the statistics used in Section 4.2 and Section 4.3 as follows:

• number_iterations_{n}_{nb_trials}.pdf displays a histogram of the number of iterations that the Legendre symbol algorithm takes. We observe that this number of iterations follows a normal law with average 1.413n and standard deviation 0.6 sqrt(n). Taking three standard deviations, we obtain that 1.413n + 1.8 sqrt(n) is an upper bound for the number of iterations in the algorithm, valid with probability 0.99: this gives us Heuristic 3 in Section 4.2.

• number_garbage_bits_{n}_{nb_trials}.pdf displays a histogram of the number of garbage bits produced during the execution of the reversible algorithm. Indeed, some iterations produce 1 garbage bit, but others produce 2, so there is a variation. We observe that the number of garbage bits follows a normal law with average 1.413 * 1.5n = 2.12n and standard deviation 0.53 sqrt(n). Taking three standard deviations, we obtain that 2.12n + 1.6 sqrt(n) is an upper bound for the number of garbage bits in the algorithm, valid with probability 0.99: this gives us Heuristic 4 in Section 4.3.

• p_padding_{n}_{nb_trials}.pdf displays a histogram of the maximal number of 'padding' bits required for the register for p (the other one having a symmetrical behavior). This is the difference between the actual length of p and its expected length, given at iteration i by the formula n - 0.708 i. We display on this figure a vertical line at 1.5 sqrt(n) to observe that the bits of padding are smaller than this quantity with a large probability.

• garbage_padding_{n}_{nb_trials}.pdf displays a similar histogram for the maximal number of padding bits for the garbage register, which is how much its size deviates, at each iteration i, from the expected 1.5 i. We display on this figure a vertical line at 2 sqrt(n) to observe that, with high probability, the number of bits of garbage is always smaller than 1.5 i + 2 sqrt(n). Note that some versions of the paper say 1.5 i + sqrt(n) instead, this is a typo.

2. Use legendre_symbol.py to construct and test the circuit for a small input bit size n. Running:

python legendre_symbol.py circuit -n 100

Will construct the circuit for n = 100 and run on 32 random inputs.

3. Use legendre_symbol.py to output Table 7 in the paper:

python legendre_symbol.py qubits

i.e., a table giving the number of qubits of the Legendre / Jacobi symbol circuit.

4. Use parameters.py to output Table 2 (Section 6.1) in the paper, with parameters and sizes for the RNS for all curves given as examples.

python parameters.py

5. Use pebbling_tree.py to output Table 3 (Section 6.2) in the paper, with counts of the number of leaf / node circuit in the spooky pebbling of the binary tree.

python pebbling_tree.py

6. Use rns_addition_tree_cost.py to output Table 5 (Section 6.4) in the paper, with total Toffoli counts for the RNS tree (computing (XZ) mod q). Note that in this script, random RNS primes are chosen before constructing the circuits, so there will be a small variation on the cost of point additions (in the first or second decimal of the exponent). This variation propagates to the entire table. The displayed table also includes the total number of qubits, which in the paper is given in Table 6.

   Running this script will take some time, and use some disk space (less than 2GB), because there is a precomputation of the windows in the tree. The results of this precomputation are stored as JSON files in the sub-folder precomputations.

python rns_addition_tree_cost.py

7. Use full_cost.py to display Table 5 and Table 8 in the paper. Some of the quantities in these tables are hard-coded (which is why we obtain exactly Table 5, and not a small variation of it).

python full_cost.py

Note that there will be a slight difference in Table 8 on the "Toffoli count" line with some versions of the paper, this is a typo from the paper (not the code).

8. Use rns_addition_tree_run.py to test the tree circuit. We run the Qarton simulator to check that the output of the tree, on random inputs, matches the result of the non-RNS integer formulas for addition. This is not a full RNS reconstruction though, which would take much more time.

python rns_addition_tree_run.py