# Worst-Case Lattice Sampler with Truncated Gadgets and Applications

This artifact contains the code by Corentin Jeudy for the paper Worst-Case Lattice Sampler with Truncated Gadgets and Applications by Corentin Jeudy and Olivier Sanders. The paper was accepted at Asiacrypt 2025 and is also available on the IACR ePrint Archive here. Part of the code was taken from the implementation of lattice anonymous credentials (by Sven Argo, Corentin Jeudy and Olivier Sanders) and lattice blind signature (by Corentin Jeudy).

The artifact contains

• the parameter selection and security estimation scripts in python, and
• the implementation in C

Parameter Scripts

In the /scripts subdirectory, we provide a parameter estimation script which depends on the lattice-estimator.

You can then run the python scripts:

• parameters_standard_model_signature.py: Parameter selection script for the standard model signature from [AGJLRS24] (optimized for standalone signature) and the one from Section 5.1 using our truncated sampler.
• parameters_group_signature.py: Parameter selection script for the group signature from [LNPS21,LNP22] and the one from Section 5.2.1 using our truncated sampler (and/or the tricks from [AGJLRS24]).
• parameters_anonymous_credentials_AGJLRS24_bimodal.py: Parameter selection script for the anonymous credentials from [AGJLRS24] (with or without the zero-knowledge optimizations of [LNP22,LN22]).
• parameters_anonymous_credentials.py: Parameter selection script for the anonymous credentials with our truncated sampler (with or without the zero-knowledge optimizations of [LNP22,LN22]).
• parameters_blind_signature.py: Parameter selection script for the blind signature from [JS24] and the one from Section 5.2.3 using our truncated sampler.

References

[AGJLRS24] Argo, Güneysu, Jeudy, Land, Roux-Langlois, Sanders. Practical Post-Quantum Signatures for Privacy. CCS 2024
[JS24] Jeudy, Sanders. Improved Lattice Blind Signatures from Recycled Entropy. IACR ePrint 2024/1289
[LN22] Lyubashevsky, Nguyen. BLOOM: Bimodal Lattice One-Out-of-Many Proofs and Applications. ASIACRYPT 2022
[LNP22] Lyubashevsky, Nguyen, Plançon. Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. CRYPTO 2022
[LNPS21] Lyubashevsky, Nguyen, Plançon, Seiler. Shorter Lattice-Based Group Signatures via ``Almost Free'' Encryption and Other Optimizations. ASIACRYPT 2021

C Implementations

The artifact contains two C implementations:

• signature_full folder contains the full implementation of the standard model signature from [AGJLRS24], with slightly optimized parameters for the standalone signature use-case.
• signature_truncated folder contains the full implementation of the standard model signature from Section 5.1 using our truncated sampler.

Organization of the source code

Each signature folder contains a code folder where the source code and dependencies are provided. The directory is organized as follows:

• code/bench contains the source and header files for the benchmarks of the different functionalities. One can change the code/bench/main.c file to skip certain benchmarks or change the number of iterations.
• code/include contains the header files of the implementation
• code/libs contains the external dependencies the implementation relies on, i.e., Flint 3.2.0-dev, GMP 6.2.1, and MPFR 4.2.2. Instructions on how to build these external dependencies are provided below.
• code/src contains the source code of the implementation and is written in C.
• code/test contains the source code for the unit tests.
• code/CMakeLists.txt is the cmake file for building the implementation.

Building Manually

Both our implementations have their own README and Dockerfile. We nevertheless provide all the build instructions here for each signature. In the instructions, X must be replaced by either full or truncated depending on which implementation is built. The implementations rely on FLINT, which itself depends on GMP and MPFR. All these dependencies are included in the libs folder of each implementation. When building each library, the make check can take a long time.

To install GMP, run the following commands (from top-level directory which contains this README file). It only needs to be installed once.

cd signature_X/code/libs/gmp-6.2.1
./configure
make -j
make check
make install

To install MPFR, run the following commands (from top-level directory which contains this README file). It only needs to be installed once.

cd signature_X/code/libs/mpfr-4.2.2
./configure
make -j
make check
make install

To install FLINT, run the following commands (from top-level directory which contains this README file). It only needs to be installed once.

cd signature_X/code/libs/flint-3.2.0-dev
./bootstrap.sh 
./configure --enable-avx2 --disable-pthread CFLAGS="-O3 -Wall -march=native" CC="gcc-11"
make -j
make check
make install

To build our implementation, run the following commands (from top-level directory which contains this README file).

cd signature_X/code
mkdir _build
cd _build
cmake ..
make -j

Then, running ./test or ./bench runs the tests or the benchmarks, respectively. Each change of the source code requires to run the last command (make or make -j).

Building with Docker

We provide a Dockerfile to build a docker image corresponding to each implementation (either using our truncated sampler /signature_truncated or the full sampler /signature_full). We give the instructions to run our implementations with Docker, recalling that X should be replaced either by full or truncated depending on which implementation is built.
For information on how to install docker on your system visit the docker docs.
Depending on your setup, you may need to prefix the following commands with sudo.

1. Build the docker image

Navigate to the top-level directory which contains this README file. Then run (notice the trailing dot for the second command!)

cd signature_X
docker build -t X-docker .

This takes some time as docker needs to pull the base-image for Ubuntu and then builds all dependencies
(i.e. GMP, MPFR and FLINT) as well as the test and benchmark executables from scratch.
In particular the make check instructions are very time consuming.

The libraries are built with standard options and fine-tuning is possible by adjusting the corresponding
make and configure commands in the Dockerfile. However, installation paths must not be changed.

Note that this step needs to be repeated for any changes in the code base or Dockerfile but not
for subsequent runs of the code.

2. Run the docker image

Issue the following command to start the docker container, where YYY is either ./test or ./bench to select
the tests or benchmarks respectively.

docker run -t X-docker YYY

You should now see the output of either the test or the benchmarking executables.

3. Stopping the running docker image

To get a list of running docker containers use docker ps. Then you can use docker stop <container_id> to stop
the execution. For more information see the docker docs.

4. Cleaning up

To remove all stopped docker containers use docker container prune.
To remove docker images use docker images to get a list of all images and then docker rm <image_id> to remove
the image in question.