Accompanying repository to the manuscript titled “Let us walk on the 3-isogeny graph: efficient, fast, and simple”.
Table of contents
- Introduction
- Setup Process
- Reproducing the Manuscript Results
- Source-Code Technical Documentation: Doxygen
- Integrated CI/CD: Build, Test and Benchmarking
- Additional Resources' Build Process
- Authors
1. Introduction
Our paper reached several important results:
- This work centers on improving HASH functions (CGL Function), KEMs (QFESTA) and NIKEs (CTIDH).
- Our results help to propose friendly parameters for QFESTA, along with the first efficient implementation in C of the radical 3-isogenies.
- Our results speedup the dCTIDH-2048 by a 4x factor, without any considerable change in the parameter sets and allowing a straightforward integration (just replacing small isogenies of degree 3,5,7,11 and 13 by the aforementioned radical 3-isogenies).
A video summarizing our ideas and contribution (in a general-reader level) is shown below:
The YouTube link of our video is shown here: Let us walk on the 3-isogeny graph: efficient, fast, and simple.
A general tree description of the source code of our project is shown below.
In the following sections, we will cover in detail:
- How to build, test, and benchmark,
- How to replicate the results reported in the manuscript,
- How to generate the source code technical documentation using Doxygen, and
- A real-life production CI/CD pipeline integration.
2. Setup Process
In this section we present a setup process that can be run in any Linux terminal. In case a specialized IDE like CLion is desired, please refer to Let us walk on the 3-isogeny graph: CLion Setup.
2.1. Build
System requirements
Our project works in any out-of-the-box Linux-based environment with some basic software requirements:
- Cmake
- Python3 (numpy and matplotlib)
To check if your system counts with the required software, simply run
If all the requirements are met, the terminal should return installed versions like the ones below. 
To build our project, in the root directory pqc-engineering-ssec-23, simply run
This will create the cmake-build-release folder with all the tests for all the supported primes: p254, p255, p381, p383, p398, p511, p575, p592, p765, and p783. A list of the generated tests is shown below.
A demo of the whole process of setup and build process is shown below.
2.2. Testing
In this section, we show how to perform the testing of our source code. For a detailed explanation of each testing mode, please refer to our additional documentation: Let us walk on the 3-isogeny graph: (Detailed) Build, Test and Benchmarking Framework Documentation.
After building as shown in the previous section, inside the c-code/cmake-build-release folder, locate all the possible tests with
To execute any particular test, simply select one of the following
For example, the execution of ./tests/tests-ssec-p254 is shown below.
To run ALL the tests in verbose mode, simply run
A demo of all the tests running in verbose mode is shown below.
2.3. Benchmarking
In this section, we show how to perform the benchmarking of our source code. For an explanation of how to perform the benchmarks in a detailed mode (and more insights about the used CPU benchmarking method), please refer to our additional documentation: Let us walk on the 3-isogeny graph: (Detailed) Build, Test and Benchmarking Framework Documentation.
For benchmarking, the correct commands must be used when doing the first cmake. Inside the root directory pqc-engineering-ssec-23, simply run
followed by
NOTE: Benchmarking does not work for
In case you run the benchmarking in either one of these two build modes (without the -DBENCHMARKING and the -DARCHITECTURE flags), you will get the following error:
To execute any particular benchmarking, inside the cmake-build-release-cycles-x8664 folder, simply select one of the following
A demo of successful benchmarkings is shown below.
3. Reproducing the Manuscript Results
In our manuscript, several statistical figures are shown. In this section, we cover how to replicate the obtained graphs. In order to reproduce some of the figures in the manuscript, we provide with easy-to-use scripts that wrap all the required executions of the benchmarking tests, and by using numpy and matplotlib, generate the manuscript graphs.
The related code to reproduce our results is shown in the tree below.
3.1. Figure 3: Benchmarks for the 2-isogenies vs. 3-isogenies walks
Inside the reproduce_results/manuscript_figure_03 folder, it is necessary to give execution permissions to the script, via
Then, just simply execute it
This will automatically build with the -DBENCHMARKING=CYCLES -DARCHITECTURE=x8664 flags, and perform all the statistics. At the end, a bar graph is automatically generated.
A demo of how to obtain the manuscript's Figure 03 is shown below.
where the original Figure 3 presented in the manuscript is shown below.
3.2. Figure 4: Benchmarks for the 3-isogenies walks (Our solution vs. QFESTA)
Similar to the previous figure, inside the reproduce_results/manuscript_figure_04 folder, it is necessary to give execution permissions to the script, via
Then, just simply execute it
This will automatically build with the -DBENCHMARKING=CYCLES -DARCHITECTURE=x8664 flags, and perform all the statistics. At the end, a bar graph is automatically generated.
A demo of how to obtain the manuscript's Figure 03 is shown below.
where the original Figure 4 presented in the manuscript is shown below.
4. Source-Code Technical Documentation: Doxygen
Our project supports automatic technical documentation generation via Doxygen. To generate the Doxygen documentation, inside the docs folder, simply run
This will generate an HTML site with interactive diagrams, and plenty of technical documentation. A demo of the generated documentation is shown below.
A link to a public-hosted version of our source-code documentation is shown here: Let us walk on the 3-isogeny graph: Technical Documentation
5. Integrated CI/CD: Build, Test and Benchmarking
To prove that this project can be integrated in an industrial environment where Continuous Integration (CI) and Continuous Delivery (CD), we follow a classic CI/CD workflow of (1) Build, (2) Test and (3) Benchmark approach.
To provide CI/CD related capabilities, in our source code we provide a cmake-multi-platform.yml file that uses Docker images to build, test and benchmark our solution. This is done to prove that our code and contribution can be integrated in a pipeline and be delivered as a part of a cryptographic solution in an industrial scenario.
6. Additional Resources' Build Process
As mentioned before, for a detailed explanation of our testing and benchmarking frameworks (with insights of the CPU benchmarking approach), please refer to our additional documentation: Let us walk on the 3-isogeny graph: (Detailed) Build, Test and Benchmarking Framework Documentation.
As part of our experiments, we used the a modified version of dCTIDH. To build the modified dCTIDH, please refer to Let us walk on the 3-isogeny graph: dCTIDH modified version.
7. Authors
For further information, please feel free to contact any of the authors:
Jesús-Javier Chi-Domínguez, Eduardo Ochoa-Jiménez, Ricardo-Neftalí Pontaza-Rodas.
