This library is a C implementation of SQIsign2DPush. It uses the base code of SQIsign-v2.0 and SQIsignHD-v1.0.
The main source directories and supporting files are organized as follows:
.
|-- CMakeLists.txt # Top-level build configuration
|-- .cmake/ # Compiler flags, dependencies, and build helpers
|-- include/ # Public API headers and symbol namespaces
|-- src/
| |-- common/ # Hashing, randomness, and shared utilities
| |-- ec/ # Elliptic-curve arithmetic, bases, and isogenies
| |-- gf/ # Finite-field arithmetic over Fp and Fp2
| | |-- ref/ # modarith-generated finite-field backend (default)
| | `-- fiat_crypto/ # Fiat-Crypto finite-field backend
| |-- hd/ # Theta structures and dimension-two isogenies
| |-- id2iso/ # Conversion from quaternion ideals to isogenies
| |-- intbig/ # Multiprecision integer arithmetic
| |-- klpt/ # KLPT routines and integer representation
| |-- precomp/ # Precomputed constants for each backend and level
| | |-- ref/ # Constants for the modarith-generated backend
| | `-- fiat_crypto/ # Constants for the Fiat-Crypto backend
| |-- quaternion/ # Quaternion algebra, ideals, and lattices
| |-- sqisign2dpush/ # SQIsign2DPush protocol implementation
| | `-- ref/
| | |-- include/ # Protocol types and internal interfaces
| | |-- lvl1/ # Level-1 build configuration
| | |-- lvl3/ # Level-3 build configuration
| | |-- lvl5/ # Level-5 build configuration
| | `-- lvlx/ # Shared keygen, signing, verification, and encoding
| | `-- test/ # Protocol tests and benchmarks
| `-- sqisign.c # Public API wrappers
|-- scripts/ # Code generation, precomputation, and validation
`-- docs/ # Implementation notes and benchmark results
Many modules use lvl1, lvl3, and lvl5 for parameter-specific files,
with shared code in directories such as lvlx, ecx, or generic.
Module tests are located in their respective test/ directories.
The src/ec-old/ and src/gf-old/ directories contain legacy code.
Local build directories such as build-ref/ and build-fiat-crypto/ are
generated by CMake and ignored by Git.
- CMake (version 3.13 or later)
- C99-compatible C compiler and an assembler
- GMP development files, unless building GMP with
-DENABLE_GMP_BUILD=ON - Make, or another build tool supported by the selected CMake generator
The finite-field implementation is selected at CMake configure time with
SQISIGN_BUILD_TYPE:
| Build type | Previous name | Finite-field source | Implementation |
|---|---|---|---|
ref (default) |
optimized |
src/gf/ref |
modarith-generated fp_backend.c |
fiat_crypto |
ref |
src/gf/fiat_crypto |
Fiat-Crypto-based fp_hd256.c, fp_hd384.c, and fp_hd512.c |
Each backend uses the matching constants under src/precomp/ref or
src/precomp/fiat_crypto. To keep using the former ref implementation,
configure with -DSQISIGN_BUILD_TYPE=fiat_crypto.
Use separate build directories when switching between backends because the choice is stored in the CMake cache.
Build the default ref backend:
cmake -S . -B build-ref -DSQISIGN_BUILD_TYPE=ref -DCMAKE_BUILD_TYPE=Release
cmake --build build-ref -j"$(nproc)"To build the Fiat-Crypto finite-field backend instead:
cmake -S . -B build-fiat-crypto -DSQISIGN_BUILD_TYPE=fiat_crypto -DCMAKE_BUILD_TYPE=Release
cmake --build build-fiat-crypto -j"$(nproc)"The SQIsign2DPush implementation and its protocol tests are shared by both configurations. To build one level only, run one of the following commands with the selected build directory:
cmake --build build-ref --target sqisign_test_sqisign2dpush_lvl1
cmake --build build-ref --target sqisign_test_sqisign2dpush_lvl3
cmake --build build-ref --target sqisign_test_sqisign2dpush_lvl5Here lvl1, lvl3, and lvl5 are the three parameter sets. Larger levels are
slower and correspond to stronger security parameters.
After building, run the matching test binary:
./build-ref/src/sqisign2dpush/ref/lvl1/test/sqisign_test_sqisign2dpush_lvl1
./build-ref/src/sqisign2dpush/ref/lvl3/test/sqisign_test_sqisign2dpush_lvl3
./build-ref/src/sqisign2dpush/ref/lvl5/test/sqisign_test_sqisign2dpush_lvl5The encoding round-trip test can also be run directly:
./build-ref/src/sqisign2dpush/ref/lvl1/test/sqisign_test_encoding_lvl1For the fiat_crypto configuration, use build-fiat-crypto as the build
directory in these commands. Protocol test binaries are still under
src/sqisign2dpush/ref within that build directory.
CMake build options can be specified with -D<BUILD_OPTION>=<VALUE>.
Selects the finite-field backend described in Backend selection.
The aliases optimized and opt are accepted by CMake and normalized to ref.
The former ref backend is now named fiat_crypto; use that value to retain
the previous Fiat-Crypto implementation.
The broadwell and arm64crypto values remain available for the platform-specific
backends supported by the base project.
Can be used to specify special build types. The options are:
Release: Builds with optimizations enabled and assertions disabled.Debug: Builds with debug symbols.ASAN: Builds with AddressSanitizer memory error detector.LSAN: Builds with LeakSanitizer for run-time memory leak detection.UBSAN: Builds with UndefinedBehaviorSanitizer for undefined behavior detection.
The default build type uses the flags -O3 -Wstrict-prototypes -Wno-error=strict-prototypes -fvisibility=hidden -Wno-error=implicit-function-declaration -Wno-error=attributes. (Notice that assertions remain enabled in this configuration, which harms performance.)
If set to OFF (by default), the gmp library on the system is dynamically linked.
If set to ON, a custom gmp library is linked, which is built as part of the overall build process.
In the latter case, the following further options are available:
ENABLE_GMP_STATIC: Does static linking against gmp. The default isOFF.GMP_BUILD_CONFIG_ARGS: Provides additional config arguments for the gmp build (for example--disable-assembly). By default, no config arguments are provided.
If set to OFF (by default), documentation targets are not configured. If set
to ON, Doxygen is required and the doc target is added:
cmake -S . -B build -DENABLE_DOCS=ON
cmake --build build --target docThe sqisign_bench_sqisign2dpush_lvl{1,3,5} binary accepts an optional
iteration count; the default is 3. It performs all key generations first,
then all signatures, and finally all verifications. For example:
cmake --build build-ref --target sqisign_bench_sqisign2dpush_lvl1
./build-ref/src/sqisign2dpush/ref/lvl1/test/sqisign_bench_sqisign2dpush_lvl1 100On x86/x86-64, cycle counts use rdtsc; other platforms use the clock
fallback. The benchmark reports average, standard deviation, median, minimum,
and maximum in MCycles, followed by average CPU time in milliseconds.
Each phase also reports four disjoint CPU-time categories:
isogeny: one- and two-dimensional isogeny computation, includingec_eval_*,isog_init_*, and theta-isogeny chains.elliptic-curve: elliptic-curve and basis work outside the isogeny category, such as basis changes, scalar multiplication, pairings, dlogs, kernel setup, and matrix application.ideal/quaternion: quaternion, ideal, lattice,represent_integer, andsample_responseprocessing.other: the residual CPU time, including hashing, setup, final checks, and bookkeeping.
The category percentages use the average CPU time of the corresponding phase
as the denominator. The other value is calculated as the total phase time
minus the first three categories, so small rounding residuals are expected.
The exact values depend on the CPU, compiler, build type, parameter level, and
iteration count. A representative level-1 output is:
keygen completed
sign completed
verify completed
SQIsign2DPush benchmark (1 iterations)
CPU cycles: rdtsc
keygen average 51.982, stddev 0.000, median 51.982, min 51.982, max 51.982 MCycles
sign average 462.545, stddev 0.000, median 462.545, min 462.545, max 462.545 MCycles
verify average 22.469, stddev 0.000, median 22.469, min 22.469, max 22.469 MCycles
average time: keygen 10.412 ms, sign 102.775 ms, verify 4.993 ms
breakdown averages [CPU ms (total percentage)]
other = unclassified time, hashing, management and measurement overhead
keygen isogeny 3.600 ms (34.6%), elliptic-curve 5.562 ms (53.4%), ideal/quaternion 1.213 ms (11.7%), other 0.037 ms (0.4%)
sign isogeny 35.253 ms (34.3%), elliptic-curve 30.481 ms (29.7%), ideal/quaternion 36.482 ms (35.5%), other 0.559 ms (0.5%)
verify isogeny 3.157 ms (63.2%), elliptic-curve 1.764 ms (35.3%), ideal/quaternion 0.000 ms (0.0%), other 0.072 ms (1.4%)
The finite-field test binaries accept either test <reps> for correctness
tests or bench <reps> for cycle-count benchmarks. For example, to benchmark
the level 1
cmake --build build-ref --target sqisign_test_gf_lvl1_fp
cmake --build build-ref --target sqisign_test_gf_lvl1_fp2
./build-ref/src/gf/ref/lvl1/test/sqisign_test_gf_lvl1_fp bench 100000
./build-ref/src/gf/ref/lvl1/test/sqisign_test_gf_lvl1_fp2 bench 100000The corresponding level 3 and level 5 binaries are:
./build-ref/src/gf/ref/lvl3/test/sqisign_test_gf_lvl3_fp bench 100000
./build-ref/src/gf/ref/lvl3/test/sqisign_test_gf_lvl3_fp2 bench 100000
./build-ref/src/gf/ref/lvl5/test/sqisign_test_gf_lvl5_fp bench 100000
./build-ref/src/gf/ref/lvl5/test/sqisign_test_gf_lvl5_fp2 bench 100000For a Fiat-Crypto build, replace build-ref/src/gf/ref with
build-fiat-crypto/src/gf/fiat_crypto.
In a fiat_crypto build, the basic Fp operations use fp_hd256.c for level 1,
fp_hd384.c for level 3, and fp_hd512.c for level 5. These files contain
Fiat-Crypto generated routines and
specialized multiplication and squaring routines. A ref build uses
the generated backend under src/gf/ref/lvl{1,3,5} instead.
Each level's fp_exp.c contains pre-generated schedules for the fixed
exponents (p-3)/4 and (p+1)/4. Inversion in fp.c uses the former;
square roots use the latter. Normal builds use the checked-in C files and
do not require Python. To regenerate or check the ref backend's arithmetic
primitives and fixed-exponent schedules:
python3 scripts/gen_fp_backend.py
python3 scripts/gen_fp_fixed.py
python3 scripts/gen_fp_backend.py --check
python3 scripts/gen_fp_fixed.py --checkThese scripts write to src/gf/ref/lvl{1,3,5}.
For representation details and benchmark results, see the v2-style representation, limb widths and benchmark results (Japanese).
The SQIsign v2.0 reference implementation also uses Michael Scott's
modarith to generate its finite-field
arithmetic (src/gf/ref), as documented in its
README acknowledgements.
This repository vendors modarith's monty.py from
commit dcdd51a3f49af0462d7a50f3bbdf63588c9f0cc0 and uses it through
scripts/gen_fp_backend.py to generate C code.
Signing and verification use the generated C code; they do not run the Python
generator. The vendored revision has not been verified to be identical to the
revision used to generate SQIsign v2.0's reference implementation.
The two backends expose the same field API and the same canonical byte encoding. Montgomery limbs and backend-specific internal layouts are never written directly to the public key, secret key, or signature encoding.
The encoded formats are defined by the mathematical object, not by the finite-field limb layout. The current sizes are:
| Level | Public key | Secret key | Signature |
|---|---|---|---|
| lvl1 | 66 bytes | 455 bytes | 151 bytes |
| lvl3 | 98 bytes | 679 bytes | 219 bytes |
| lvl5 | 130 bytes | 899 bytes | 295 bytes |
fp_encode writes a canonical little-endian field element and fp_decode
restores the backend's internal representation. The legacy hash path uses
fp_encode_legacy_hash explicitly so that the protocol hash input remains
compatible with the established format.
represent_integer follows the signed-coordinate search and small-prime
two-square solver in hiroshi-onuki/SQIsign2D-Push.
It preserves the requested norm and retries nonprimitive candidates within
a bounded search.
sample_response follows the public Julia implementation's
element_for_response search. After LLL reduction it enumerates the
short-vector candidates of the resulting positive-definite quadratic form,
reduces the coefficient vector by its gcd, and accepts a nonzero candidate
whose normalized norm is below 2^EXPONENT_TWO and coprime to 3. It does not
use the former random m=10 candidate box or a fixed inner attempt limit.
Protocol signing retries the outer response construction in the same way as
the Julia implementation when a response construction step fails.
SQIsign2DPush is licensed under Apache-2.0. See LICENSE and NOTICE in the root directory.
Most functionalities of this code are based on SQIsign-v2.0 and SQIsignHD-v1.0 under the license MIT: "Copyright (c) 2023 The SQIsign team".
Third party code is used in some test and common code files of this directory (Signature):
src/common/generic/aes_c.c; MIT: "Copyright (c) 2016 Thomas Pornin pornin@bolet.org"src/common/generic/fips202.c: Public Domainsrc/common/generic/randombytes_system.c: MIT: Copyright (c) 2017 Daan Sprenkels hello@dsprenkels.com