CTLLL-SQIsign

Constant-time lattice reduction for SQIsign

This is the code and data for our paper on the same topic.

We will first explain how to use the present code, then we will detail the structure of the codebase.

---

Origins of the code

Many parts of this code are adapted from the NIST submission of SQIsign.

In particular the file src/lll/lll.c is directly taken from that implementation. Furthermore, almost all quaternion-related functions in src/ct_helpers/ct_helpers.c, src/test_helpers/nct_helpers.c and src/test_helpers/test_helpers.c are taken over from SQIsign, and the src/nct_intbig module is obtained from SQIsign's intbig module by just renaming the functions to add the nct_ prefix. Similarly, src/nct_lll/lll.c is an adaptation of SQIsign's lll.c file to use the nct_ibz functions. The constant-time gcd is implemented using Bernstein and Yang's constant-time xgcd from 2019.

The code in src/bkz, as well as most test code at the root of the src folder and all code outside of the src folder was newly written for this project.

---

Structure of this repository

This folder contains several subfolders. Most of these contain a separate README with details their content and use.

• src: This folder contains all C source code for the project.
  This includes in particular the BKZ2 implementation, but also integer arithmetic, test and benchmark code and the LLL implementation from SQIsign used for comparison.
  A dedicated README in src explains its inner structure.

• build: This folder is empty and meant to be used only for compilation.

• sage: This folder contains some additional sage scripts used for early testing, explained by a README in the folder.

There are three folders with data and scripts from our experiments. Each of them contains a README giving more detail on its content.

• RTLF-data: This contains the data, benchmarks, input files, raw outputs and plots from our experiments with RTLF, as well as a README explaining how to use them.

• quality-tests: This contains input data and scripts for our quality test, as well as a README explaining how to use them.

• benchmark-inputs: This provides input data for our benchmarks comparing LLL with BKZ, as well as a README explaining how to use them.

The root folder contains, besides the above folders:

• This README and the license
• The Makefile of the project
• A toy input data file p335_nl_11_1_small with 9 lattices, used as default
• Scripts create_ideals.sage and parse_output.py for generating alternative inputs, as described at the end of this README.
• Other scripts and example data used by the two above. Details on them can be found in the README in the src folder.

---

Prerequisites and first step

Prerequisites

• Strictly required: A 64-bit little-endian architecture, gcc, the GNU multiprecision library GMP (version at least 6.2.0).
• Required for generation scripts: Python and a recent version of sage (9.5 should work)
• For the scripts in the sage folder: sage, the python library fpylll (version at least 0.6.2) and its dependency fplll
• Required for ctgrind/valgrind: Not an ARM processor (intel/AMD work)
• For generating figures using the scripts in RTLF-data, the python library matplotlib is required

First steps

Type make test. Wait a few seconds, and check if the tests pass.

---

Build and execute

First, create a directory called build in this folder if it does not yet exist.

There are 4 main executables which can be built and run:

Small_tests

Runs some fixed and not randomized tests on submodules

Build and run it with make small_test.

This is the only executable which can be run without using inputs.h, but it does require setting LIMBNUM and the scratch space in limbnum.h, and the constants in lll_constants.c.

Test

Runs tests ensuring that BKZ reduces all lattices in the inputs.h file.

The tests verify that the bound from Minkowski's second theorem and the bound on the shortest vector are respected. Furthermore, it is verified that the output is a basis of the same lattice then the input.

Compile and run it with make test

Requires inputs.h (with corresponding inputs.cor datafile), bkz_constants.h, lll_constants.c and limbnum.hto be generated correctly and consistently.

If DATA_FILE and LATTICE_DATA_NUMBER are defined in inputs.h, it the script will be compiled so that it uses these. The lattices in the data file are assumed to be integral ideals of the given quaternion algebra. If one of these macros is undefined, the compiler will check if LATTICE_NUMBER is defined and use the lattices from LATTICE_LIST. To be run on LLL instead or in addition to BKZ, the BKZ_TEST and LLL_TEST can be used as described above.

Benchmark

Runs benchmarks on BKZ and LLL, with a fixed number of iterations on each lattice from input.h.

Compile and run it with make bench

Requires inputs.h (with corresponding inputs.cor datafile), bkz_constants.h (with BENCHMARK_ITERATIONS), lll_constants.c and limbnum.hto be generated correctly and consistently.

If DATA_FILE and LATTICE_DATA_NUMBER are defined in inputs.h, it the script will be compiled so that it uses these, otherwise it will check if LATTICE_NUMBER is defined and use the lattices from LATTICE_LIST. To be run on LLL instead or in addition to BKZ, the BKZ_BENCH and LLL_BENCH can be used as described above.

Run

Runs BKZ once on each lattice in input.h. This should always run in the same time independently of the lattices in inputs.h, as long as the variables QUATALG_P, LATTICE_NUMBER and LIMBNUM are unchanged.

Compile and run it with make run. You can also compile it using make and run it using ./build/run.

Requires inputs.h (with corresponding inputs.cor datafile), bkz_constants.h and limbnum.h to be generated correctly and consistently.

If DATA_FILE and LATTICE_DATA_NUMBER are defined in inputs.h, it the script will be compiled so that it uses these. Reading from the file is however not guaranteed to run in file-content-independent time. Otherwise it will check if LATTICE_NUMBER is defined and use the lattices from LATTICE_LIST.

Clean

To remove all compilation files, use make clean.

---

Additional make targets for our measures

For the measures reported in the paper, some additional targets can be build and run.

Test, benchmark, write to file

This is only available if DATA_FILE and LATTICE_DATA_NUMBER are defined in inputs.h. It runs tests on NTESTS lattices in the file, where NTESTScan be defined in inputs.h and otherwise defaults to 7. After this, benchmarks are run on LATTICE_DATA_NUMBER lattices in the datafile, and the results for each lattice are written to a file named like the datafile prefixed with bench_. Our post-processing script post_processor.py can be run on this output and the datafile to produce a .csv file for RLFT.

Compile and run it with make bench_stats.

In case the LLL implementation from SQIsign's NIST submission and not our BKZ should be benchmarked, run make bench_stats_lll instead.

Quality test: Test with verbous output

make quality_test compiles and runs the tests for Minkowski reduction and for the length of the shortest vector. It does not only report the result, but also prints both sides of the inequalities it tests. This is used in out quality tests.

In order to get this verbous output from noral tests, it is sufficient to compile them with the additional flag -DPRINT_FLAG=1.

ctgrind

make bench_ctgrind will compile and run BKZ-2 on the first lattice in the used datafile while using ctgind (that is, valgrind with the input lattice declared as uninitialized memory). Be aware that this requires to have Valgrind installed, which is not possible on ARM Macs.

bench_nct_lll

make bench_nct_lll will compile and run benchmarks for the LLL implementation in nct_intbig_lll.

---

Different inputs for the tests

Use inputs from the data folders

The folders RTLF-data, quality-tests and benchmark-inputs provide the inputs we used in our tests for running respectively RTLF, our tests on BKZ quality for low iteration counts, and the benchmarks. Their use is described in the READMEs of these subfolders.

Automatic input generation using sage

We provide a sage script create_ideals.sage to generate (lattices representing) random ideals of a specific order (called O0 in all papers on SQIsign), with norm in a given range. The given basis is the HNF also used in the SQIsign round 1 NIST submission.
To get help on the inputs it requires, use the -h argument. To generate a data file instead of a lattice list in the inputs.c file, run the script with an additional argument -data. The name of the datafile can be set by using datafile=<name> as last argument, it is data_file by default.

A few notes on some of the arguments (in order here):

• p: Prime defining the quaternion algebra (and therefore the norm of an element of coordinates (a,b,c,d) in the standard basis as a^2+b^2+pc^2+pd^2). It must be 3 modulo 4 as otherwise the order used to generate the ideals might not be an order.
• ni and nu: Lower and upper bound of the bitsize of the norms of the ideals to be generated. nu should be larger than 2sqrt(p) to guarantee such ideals exist.
• ln: The number of ideals to be generated.
• nl: The size of the integers to be used by the C code, in 64-bit words. For example, nl=2 means that integers of 128 bits will be used for the computation of LLL- and BKZ- reductions in the C code. It is important this number is large enough to allow the algorithm you want to run (LLL or BKZ) to operate on the given input. Formulas to compute this size can be found in lemma 2 of our paper, and in the sage/clll.sage file. A too large nl will slow down the computation, while a too small one will lead to arithmetic exceptions, overflows and potentially even segfaults.
• bt and lt: The iteration numbers for the outer loop of the BKZ algorithm and the constant-time Lagrange reduction algorithm respectively. Should be larger than 0.
• bi (optional, default 1). Number of iterations on each lattice for benchmarking. Not used if not benchmarking.

The toy example in the datafile p335_nl11_1_small used by the default src/inputs.h was obtained by running sage create_ideals.sage 33506587778976371636384290201141387 12890707586852862 187181532229268607942 9 11 10 6 -data datafile=p335_nl11_1_small.

Automatic input from SQIsign prints

The script parse_output.py (not requiring sage, only python3) allows to obtain input lattices from outputs printed by a run of the SQIsign round 1 reference implementation (which must be slightly modified to obtain these printouts). How to obtain a suitable printout is explained in the comments at the beginning of parse_output.py. The proposed modification to the NIST 1 SQIsign submission code will print all lattices encountered in keygen and one signing run.
An example of such a trace is given with the file sqisign_lvl1_lll_calls_trace. The default are BKZ and Lagrange tour counts of 30 and 10, these can however be adjusted in the script. Similar printouts (calling the same print functions at the beginning of the respective LLL implementation) can be used to achieve the same result on most other SQIsign C implementations (SQIsignHD, SQIsign2d-West and the round 2 NIST submission for example).

Once this output file is obtained, the script parse_output.py can be called. It requires the following inputs (in this order):

• filename the name of the trace file containing the printouts from the C code.
• limbnum must be a number of words so that integers of bitsize 64limbnum are large enough to allow the algorithm you want to run (LLL or BKZ) to operate on the given input. Formulas to compute this size can be found in lemma 2 of our paper, and in the sage/clll.sage file. For the given sqisign_lvl1_lll_calls_trace, 100 can be used. A too large limbnum will slow down the computation, while a too small one will lead to arithmetic exceptions, overflows and potentially even segfaults.
• bkz_tours the number of outer iterations in the BKZ algorithm
• lagrange_tours the number of iterations used in the constant-time Lagrange reduction algorithm
• benchmark_iterations the number of times the same lattice should be reduced during benchmarking. 1 is a reasonable default.

If less arguments (1, 2 or 4) are given, these are taken as the first (1, 2 or 4) of the above arguments, and defaults defined in the first 5 lines of the script are used for the others. These defaults are acceptable for the NIST round 1 implementation at level 1, even though the iteration counts are neither minimal nor above the proven bounds.

If one wants to generate and use a datafile instead of a lattice list in a C file (this is required for some of the make targets), run the script with an additional argument -data. The name of the datafile can be set by using datafile=<name> as last argument, it is data_file by default.

The script will then take care of setting the relevant constants in the src folder accordingly, so that recompiling using make will yield executables using the given list of lattices as input.

Input generation by hand or using parts of our scripts

If further customization of the inputs is needed, please check the README of the src folder.