International Association for Cryptologic Research

International Association
for Cryptologic Research

EUROCRYPT 2024

AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field Signing


README

AprèsSQI

This repository contains the code related to the SQIsign signature scheme, using extension-fields in signing. This is code accompanying the paper AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field Signing by Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer and Krijn Reijnders.

All code in this repository was written in Python and SageMath, and is made publicly available under the MIT license. The dependencies are:

Instructions for Reproducing Results

To reproduce ... from AprèsSQI: Extra Fast Verification for SQIsign Using Extension-Field Signing, do the following:

cd ApresSQI-Sage/
sage benchmark.py

cd BenchmarkVerification/Apres/
python benchmark.py All 100 True

and for benchmarking NIST/LWXZ, run

cd BenchmarkVerification/NISTandLWXZ/
python benchmark.py All 100 True

The results can then be found as

cat results_specific_version_[version].txt

where the output is of the form [(e, cost)], where e represents the 2-valuation of p+1.

Contents

This repository contains two main directories:

We now describe the files in each of these directories and how to run their contents.

ApresSQI-Sage

The directory ApresSQI-Sage provides a proof of concept implementation of the SQIsign signature algorithm, using field extensions when signing, allowing for lightning fast verification.

The files contained in the main directory are as follows:

sage benchmark.py

The directory ApresSQI-Sage also contains two sub-directories:

We give the precomputed parameters in Precomputed and private keys in Privkeys for the following primes:

If other primes are found in these sub-directories, they have been requested and added for other applications (beyond AprèsSQI).

Example usage

from ApresSQI import SQIsign

# Signer
msg = "Kani came in like a wrecking ball"
signer = SQIsign()
pk = signer.KeyGen()
signer.sk.export('priv.key')

sigma = signer.Sign(msg)

# Verifier
verifier = SQIsign()
verified = verifier.verify(msg, sigma, pk)
print('Signature was ' + ('CORRECT' if verified else 'WRONG'))

Or, if you just want to test a ready-made example, you can run

sage example.py param seeds compressed

which allows for signing with any of the four parameters by setting param = toy, NIST, 7-block, 4-block, signing both with and without seeds by setting seeds = True or False (respectively), as well as using compressed or uncompressed signatures by setting compressed = True or False (respectively).

By default, running

sage example.py

will use the toy parameter, signing with seeds and using compressed signatures.

Acknowledgements

The code in this directory is based on the documentation from the NIST submission of SQIsign. Further, it uses many ideas introduced in Deuring for the People, and some code found here is also taken from the code, made by Jonathan Komada Eriksen, Lorenz Panny, Jana Sotáková and Mattia Veroni. Some other code (specifically, lattice enumeration) is also taken from the code accompanying the project Learning to SQI, made by Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer and Giacomo Pope. Finally, the implementation of sqrt_velu in xonly_velusqrt.py is from the SageMath source code, adapted to work with our custom xPoint class (doing x-only arithmetic).

Benchmark Verification

The directory BenchmarkVerification allows us to (re)run benchmarking found in Section 7 of the paper. It contains two subdirectories:

AprèsSQI directory

The files in the Apres sub-directory are as follows:

To benchmark ApresSQI variants of SQIsign go into the sub-directory Apres and run

python benchmark.py version N

where

NOTE: Throughout, by python we mean python3 if your terminal requires this (e.g., some MacOS versions may require this.) Furthermore, if you want to output plots, uncomment the line import matplotlib.pyplot as plt.

If you want to run the benchmarks for a specific prime, add the prime to the array SpecificPrimes on line 343, and then run

python benchmark.py version N True

where version and N as above.

NIST and LWXZ directory

The files contained in this directory have identical descriptions barring the following differences:

To benchmark NIST and LWXZ variants of SQIsign go into the sub-directory NISTandLWXZ and run

python benchmark.py version N

where

If you want to run the benchmarks for a specific prime, add the prime to the array SpecificPrimes on line 162, and then run

python benchmark.py version N True

where version and N as above.

Example usage

For example, to benchmark the NIST version of SQIsign with 100 runs per prime, navigate to the NISTandLWXZ subdirectory and run:

python benchmark.py NIST 100

Licenses

The code in this repository is published under the MIT license, except for in the following files where the code is published under the GNU General Public License v3.0:

In this repository, we have included third party code. Follow the links below to read their licenses in detail: