Introduction to qFALL

qFALL is a project designed to accelerate the sustainable prototyping of lattice-based cryptography. Its central objective is to minimize the friction between theoretic contributions and practical implementations.

To achieve this, the project focuses on three core principles:

• Theory-Affine Interfaces: Researchers can implement constructions using notation that closely resembles academic pseudocode. This ensures prototypes are easily auditable, modifiable, and serve as a reusable resource for the scientific community.
• Incremental Optimization: The modular structure allows for the quick assembly of working prototypes to assess algorithmic trade-offs early. Users can then iteratively replace bottlenecks with optimized modules without rewriting the entire scheme.
• Performance & Safety: While focused on prototyping, qFALL ensures representative runtime performance by utilizing FLINT for underlying arithmetic and Rust for memory safety, alongside a streamlined benchmarking environment.

This book serves as a technical tutorial and reference guide for qFALL.

Structure of qFALL

The project is composed of three dedicated Rust crates, each serving a distinct layer of the cryptographic stack:

Crate	Links	Core Function	Example Content
qFALL-math		Mathematical Foundation	Arbitrary-precision arithmetic for integers, quotient rings, polynomial rings, and matrices over these rings.
qFALL-tools		Cryptographic Building Blocks	High-level primitives like gadget trapdoors, short basis generation, and fundamental primitives such as PSFs.
qFALL-schemes		Cryptographic Constructions	Prototypes of lattice-based constructions like signatures and public-key encryption schemes.

Prerequisites

To get the most out of this tutorial, we assume the following:

• Familiarity with Rust: All libraries that are part of qFALL leverage Rust’s performance and memory safety guarantees. If you are new to the language, we highly recommend reading The Rust Programming Language book first.
• Lattice Fundamentals: This guide focuses on implementation. We assume the reader has prior experience with the fundamental concepts of lattice-based cryptography. Several helpful resources on lattice-based cryptography are gathered on this website.

Intention and Structure of this Book

This tutorial is designed to be a hands-on guide to the qFALL ecosystem. It is not an exhaustive API reference; rather, it is designed to provide a starting point for new users.

1. Installation and Setup: How to install the required dependencies and add our libraries to your project.
2. The Mathematical Foundation (qFALL-math): This section details our most fundamental crate. It includes the arbitrary-precision mathematical features required for lattice-based cryptography, such as integer arithmetic, quotient rings (\(\mathbb{Z}_q\)), and polynomial ring operations.
3. Cryptographic Tools (qFALL-tools): This crate contains essential cryptographic primitives, algorithms, and shorthands, such as Gadget Trapdoors, algorithms for short basis generation, and the abstracted behavior of Preimage Sampleable Functions (PSFs).
4. Cryptographic Schemes (qFALL-schemes): This section (also refered to as crypto-crate) provides an overview of several implemented prototypes, such as signature schemes and encryption algorithms. Furthermore, it provides a step-by-step guide to implement a basic lattice-based encryption scheme using qFALL.
5. Shared Features: This section covers advanced utilities available across the entire library suite, including benchmarking facilities, serialization features, and external interoperability.

Contributing & License

qFALL is an open-source project distributed under the Mozilla Public License Version 2.0. We welcome all contributions such as bug fixes, algorithm optimizations, documentation improvements, and extensions. Please refer to our Contribution Guidelines for details.

Installation

To use this project, you need to have an installation of Rust version 1.88 or newer. As we use flint3-sys which itself depends on gmp, usage of qFALL is currently restricted to Mac, Linux and Windows Subsystem for Linux. To compile FLINT and gmp, it is required to have m4, make, and a C-compiler like gcc installed.

Command for installing m4, make, and gcc:

sudo apt-get install m4 gcc make

Integration

You can integrate our libraries via crates.io by running:

cargo add qfall-math qfall-tools qfall-schemes

Alternatively, you can get the latest version from GitHub. To get the latest version from GitHub, you can include a link to the dev branch in your Cargo.toml.

qfall-math = { git = "https://github.com/qfall/math", branch="dev" }
qfall-tools = { git = "https://github.com/qfall/tools", branch="dev" }
qfall-schemes = { git = "https://github.com/qfall/schemes", branch="dev" }

Be aware that the external libraries in our projects must be compiled once during the first build, which may take about 10-30 minutes (depending on the used hardware and operating system). After the first installation, you should be able to use qFALL.

Documentation

The official documentation is hosted on docs.rs.

• Documentation of qfall-math
• Documentation of qfall-tools
• Documentation of qfall-schemes

Alternatively, you can build it locally. Once you have integrated the desired library, running the command below will generate documentation for your entire project, including all integrated qFALL crates.

cargo doc --open

If you’re using WSL and your browser does not open, retry after installing wslu.

What can you expect from our documentation? Every public interface is provided with (1) an explanation of the behavior; (2) a description of all parameters; (3) a description of the output; (4) an example of the function; and (5) a list of potential errors and failures that can occur.

Introduction

qFALL-math provides the fundamental arithmetic backend for the entire qFALL suite. It is a dedicated Rust crate engineered for fast, arbitrary-precision number theory, specifically designed to meet the mathematical requirements of lattice-based cryptography.

Abstraction Layer

The primary purpose of qFALL-math is to function as a safe and idiomatic abstraction layer over the highly-optimized C-library, FLINT (Fast Library for Number Theory).

By utilizing the FFI crate flint3-sys, qFALL-math achieves two critical goals simultaneously:

1. Performance: Leveraging FLINT’s battle-tested and highly-efficient algorithms for large number arithmetic.
2. Safety & Usability: Taking over all responsibilities regarding manual memory management and unsafe C-calls, wrapping them in idiomatic Rust interfaces.

The core premise of this library is to provide a user-friendly interface that aligns closely with research notation, allowing for direct translation of cryptographic schemes while ensuring high efficiency and reliability. The underlying FFI can be updated or exchanged, if more up-to-date versions are desired.

Mathematical Scope

qFALL-math provides the required foundation for all subsequent cryptographic components in qFALL-tools and qFALL-schemes.

Its fundamentals include:

• Arbitrarily-Precise Integers: \(\mathbb{Z}\)
• Integers in the Quotient Ring: \(\mathbb{Z}_q\)
• Rationals: \(\mathbb{Q}\)
• Polynomial Rings over Quotients: \(\mathbb{Z}_q[X]/f(X)\)

These basic types are then extended to support more complex structures essential for lattice cryptography, such as polynomials, matrices, and matrices of polynomials.

In essence, qFALL-math black-boxes the complex, low-level behavior of FLINT and transforms it into a robust, memory-safe, and highly usable mathematical toolkit for the Rust ecosystem.

Safety Guarantees

In Rust, the ownership model enforced by the compiler prevents memory leaks. qFALL-math encapsulates the manual memory management required by the underlying FLINT structures, exposing only memory-safe interfaces.

Furthermore, the crate implements dedicated error handling. Instead of generic failures, we provide distinct error types that offer detailed context, supporting the debugging process.

Supported Mathematical Types

The qFALL-math crate provides types that align closely with mathematical notation, offering core domains and their extensions to matrices and polynomials.

How is this Section structured?

1. Basic Types: We show how to instantiate the three base types Z, Zq, and Q, introduce some features and present some arithmetic operations.
2. Complex Structures: We present more advanced types like MatZ, PolyOverZ, or PolynomialRingZq and give some intuition on working with them.
3. NTT: We consider how values of PolynomialRingZq can be represented differently (using the Number Theoretic Transform) for more efficient multiplication.

Basic Types

Rusts data types such as u64 and i64 do not capture arbitrarily big integers. For example, the following code causes an overflow:

let overflow: u64 = u64::MAX + 1;

qFALL-math works with arbitrarily big integers s.t. the user does not need to worry about potential overflows or execution failures.

Instantiation

qFALL-math’s basic types are integers (Z), integers in the quotient ring (Zq), and rationals (Q). Each can be instantiated from strings and Rust’s basic math types.

use qfall_math::{integer::Z, integer_mod_q::Zq, rational::Q};
use std::str::FromStr;

fn basic_instantiations() {
    // instantiations using rust types
    let z = Z::from(42);
    let zq = Zq::from((24, 42)); // instantiates 24 mod 42
    let q = Q::from((24, 42)); // instantiates 24 / 42

    // instantiations using strings
    let z = Z::from_str("42").unwrap();
    let zq = Zq::from_str("24 mod 42").unwrap();
    let q = Q::from_str("24/42").unwrap();
}

Zq and its Modulus

To identify an element in the quotient ring over the integers, we need a representative (a value in Z) and context information defining the quotient (Modulus). A modulus object is of type Modulus and can be instantiated from a Z greater or equal to two.

Then, a Zq value consists of a Z value and a Modulus. A modulus can be shared among different values:

use qfall_math::integer_mod_q::{Modulus, Zq};

fn shared_modulus() {
    let modulus = Modulus::from(42);

    let zq_1 = Zq::from((17, &modulus));
    let zq_2 = Zq::from((24, &modulus));
}

The Modulus struct utilizes a reference counter (Rc). Therefore, cloning a Modulus only creates another pointer to the underlying object, making it efficient to store a Z and a Modulus together. Storing only one instance also the following two advantages:

1. Mathematical soundness, i.e., no accidental modulus switching or operations between objects with different moduli can occur.
2. Easier use, as the developer does not have to carry the modulus manually.

Converting Types

All reasonable type conversions are possible, e.g. we can define a Q from a Z.

use qfall_math::{integer::Z, rational::Q};

fn q_from_z() {
    let z = Z::from(42);
    let q = Q::from(&z);
}

Basic Arithmetic Operations

All types support basic arithmetic operations. Among them are multiplication, addition and subtraction. Opposed to what is typical Rust behavior, we natively support operations between several distinct types, e.g., between Z and Q, as output of Q any arithmetic operation between these types results in a rational output Q. As we are working with arbitrarily large values, no memory leaks or rounding errors can occur.

use qfall_math::{integer::Z, rational::Q};

fn basic_arithmetics() {
    let z_1 = Z::from(42);
    let z_2 = Z::from(24);

    let add = &z_1 + &z_2;
    let sub = &z_1 - &z_2;
    let mul = &z_1 * &z_2;

    // arithmetic operations between different types, including native Rust types
    let add: Q = &z_1 + Q::from((1, 2));
    let mul: Q = 0.5 * &z_1;
}

The operations between types either hide optimized behavior or implicit type casts. Similarly, it is also to combine our types directly with Rust’s types, e.g., f64.

Printing your Results

You can print the values of operations using print!() or println!(), or convert them into strings with .to_string(). This naturally extends to more complex structs as well.

use qfall_math::integer_mod_q::Zq;

fn print() {
    let zq_1 = Zq::from((24, 42));
    let zq_2 = Zq::from((17, 42));

    let zq = zq_1 - zq_2;

    // print it directly
    println!("{zq}");

    // explicitly generate string
    println!("{}", zq.to_string())
}

Error Handling

In our math crate, the error.rs file contains all custom error types.
We use MathError as our error enum that holds all sorts of errors occurring in this crate and StringConversionError for all errors that are related to the conversion of strings. Errors are normally propagated through functions such that they can easily be handled or ignored with unwrap(). In cases of naive errors that are easy to spot like “division by zero” errors, we do not propagate the error but panic instead. This avoids unnecessary as well as reckless use of unwrap(), which would both defeat the purpose of proper error handling.

Complex Structures

Rather than saving Vec<Zq> or Vec<Vec<Zq>> to represent vectors/polynomials and matrices, qFALL-math provides explicit structs with dedicated functionalities that simplify prototyping.

Note that none of the following examples provides an extensive list of possibilities to instantiate structures. Please refer to Random Sampling to create random instances and browse the documentation of qFALL-math to find further options.

Matrices

Each base type (Z, Q, Zq) has a matrix version (MatZ, MatQ, MatZq) that can be instantiated from strings as well as a zero-matrix.

use qfall_math::{integer::MatZ, integer_mod_q::MatZq, rational::MatQ};
use std::str::FromStr;

fn matrix_instantiations() {
    // instantiation of zero matrices
    // the first two parameters define the dimensions (rows x columns)
    let matz = MatZ::new(5, 10);
    let matzq = MatZq::new(5, 10, 13); // the last parameter defines the modulus
    let matq = MatQ::new(5, 10);

    // instantiations using strings
    // the content of a matrix is written in square brackets and
    // one row of the matrix consists of numbers divided by commas in a square bracket
    let matz = MatZ::from_str("[[1,2],[3,4]]").unwrap();
    let matzq = MatZq::from_str("[[1,2],[3,4]] mod 5").unwrap();
    let matq = MatQ::from_str("[[1/2,2],[3/4,4]]").unwrap();

    // explicit conversions between different matrix types
    let matz = matzq.get_representative_least_absolute_residue();
    let matq = MatQ::from(&matz);
}

These matrices can then be modified in various ways, by redefining parts of the matrices, swapping entries, sorting by rows, etc. To enhance usability, these functions additionally provide some Python-like behavior, e.g., a row addressed with -1 refers to the last row of the matrix.

use qfall_math::{integer::MatZ, traits::*};
use std::str::FromStr;

fn manipulation() {
    let mut matz_1 = MatZ::from_str("[[1,2,3],[4,5,6]]").unwrap();
    let matz_2 = MatZ::from_str("[[5,2,7],[4,2,1]]").unwrap();

    // set the 3rd entry of the second row to value 8
    matz_1.set_entry(1, 2, 8).unwrap();
    // set the first row of matz_1 to the values of the second row of matz_2
    matz_1.set_row(0, &matz_2, 1).unwrap();
}

As vectors can be expressed as matrices, we do not implement explicit vector types. Instead, our matrix types provide several functions specific to vectors if they have appropriate dimensions (e.g., a MatZ matrix with dimensions 1 x n). For example, the compututation of several different norms and dot products is available for vectors of type MatZ.

use qfall_math::integer::MatZ;
use std::str::FromStr;

fn vectors() {
    let vecz = MatZ::from_str("[[1/2,2,3/4]]").unwrap();

    let is_vector = vecz.is_vector();

    let dot_product = vecz.dot_product(&vecz);
    let norm = vecz.norm_eucl();
}

Assuming matching dimensions, arithmetic operations between different types of matrices are well-defined and supported naturally. Beyond matrix multiplication, it is also possible to use scalars.

use qfall_math::{
    integer::MatZ,
    rational::{MatQ, Q},
};
use std::str::FromStr;

fn basic_arithmetics() {
    let matq = MatQ::from_str("[[1/2,2,3/4],[4,5/10,6]]").unwrap();
    let vecz = MatZ::from_str("[[1],[4]]").unwrap();
    let matz = MatZ::from_str("[[1,2,3],[4,5,6]]").unwrap();

    let add: MatQ = &matq + &matq;
    let sub: MatQ = &matq - &matz;
    let mul: MatQ = &matq * &vecz;
    let scalar: MatZ = 42 * &matz;
    let scalar: MatQ = Q::from((17, 42)) * &matz;
}

As with Zq, it is also possible to share a Modulus across several matrix instances.

use qfall_math::{
    integer::MatZ,
    integer_mod_q::{MatZq, Modulus, Zq},
};
use std::str::FromStr;

fn shared_moduli() {
    let modulus = Modulus::from(42);
    let matz_1 = MatZ::from_str("[[1,2,3],[4,5,6]]]").unwrap();
    let matz_2 = MatZ::from_str("[[17,42],[89, 100]]]").unwrap();

    let zq = Zq::from((17, &modulus));

    let matzq_1 = MatZq::from((&matz_1, &modulus));
    let matzq_2 = MatZq::from((&matz_2, &modulus));
}

Polynomials

Just like matrices, polynomials are also defined for all base types and the general behavior is comparable to that of vectors for our matrices. You can compute scalars, access/modify individual coefficients and compute various functions. The instantiation from strings is slightly different, as the string format is imported from FLINT to reduce the preprocessing workload.

use qfall_math::{
    integer::PolyOverZ,
    integer_mod_q::{Modulus, PolyOverZq},
    rational::PolyOverQ,
};
use std::str::FromStr;

fn polynomial_instantiations() {
    // instantiations using strings
    // the first number is the number of coefficients in the polynomial,
    // which is followed by the coefficients in ascending order
    let polyz = PolyOverZ::from_str("4  0 1 2 3").unwrap();
    let polyzq = PolyOverZq::from_str("4  0 1 -2 3 mod 42").unwrap();
    let polyq = PolyOverQ::from_str("5  0 1/3 2/10 -3/2 1").unwrap();

    // instantiations using components
    let modulus = Modulus::from_str("100").unwrap();

    let polyzq = PolyOverZq::from(&modulus);
    let polyzq = PolyOverZq::from((&polyz, &modulus));

    let polyq = PolyOverQ::from(&polyz);
}

For polynomials, we support quotient rings of polynomials, where the context/modulus object itself is a PolyOverZq. We treat the modulus in the same fashion as Modulus and defined ModulusPolynomialRingZq, which can be shared among different instantiations.

use qfall_math::{integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq}, traits::*};

fn instantiate_moduli() {
    let mut polyzq = PolyOverZq::from((1, 17)); // 1 mod 17
    polyzq.set_coeff(4, 1); // becomes X^4 + 1 mod 17
    let modulus_poly = ModulusPolynomialRingZq::from(&polyzq);
}

To instantiate common ModulusPolynomialRingZq, please take a look at qFALL-tools::utils::common_moduli.

A PolynomialRingZq can be instantiated from strings or its components.

use qfall_math::integer::PolyOverZ;
use qfall_math::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
use std::str::FromStr;

fn ring_instantiations() {
    // instantiations using components
    let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
    let poly = PolyOverZ::from_str("4  -1 0 1 1").unwrap();

    let poly_ring = PolynomialRingZq::from((&poly, &modulus));
}

Number Theoretic Transform (NTT)

The NTT for quotient rings of polynomials often finds specific application in lattice-based cryptography. We do not give a complete introduction here, so for those unfamiliar with the NTT transform, this section might not be fully understandable. We recommend this paper as a beginner guide for NTT.

Full NTT transform

Given a ring \(\mathbb{Z}_q[X]/f(X)\) (assuming that \(f\) can be represented as a product of polynomials of degree at most 1 over \(\mathbb{Z}_q\)), there exists an isomorphism (implemented with the NTT) to \(\mathbb{Z}_q^{deg(f)}\). The transform is homomorphic, and addition in the NTT representation remains coefficient-wise. However, the multiplication is also coefficient-wise in NTT representation, reducing the cost of naïve multiplication from \(deg(f)^2\) to \(deg(f)\) operations.

Instantiation

The NTT algorithm is context dependent, i.e., for a fixed ring, many values can be precomputed using the shared modulus. For instantiation, a fixed root of unity needs to be provided, and its powers are precomputed and stored in the context object. We fix these precomputed values with a reference counter in the context modulus object.

use qfall_math::integer_mod_q::ModulusPolynomialRingZq;
use qfall_math::integer_mod_q::PolyOverZq;
use qfall_math::traits::SetCoefficient;

/// Using the ring from Dilithium
pub fn instantiate_ntt_modulus() -> ModulusPolynomialRingZq {
    let n = 256;
    let modulus = 2_i64.pow(23) - 2_i64.pow(13) + 1;

    let mut mod_poly = PolyOverZq::from(modulus);
    mod_poly.set_coeff(0, 1).unwrap();
    mod_poly.set_coeff(n, 1).unwrap();

    // X^{256} + 1 mod 8384017
    let mut polynomial_modulus = ModulusPolynomialRingZq::from(&mod_poly);

    // 2nth root of unity
    polynomial_modulus.set_ntt_unchecked(1753);
    polynomial_modulus
}

A Dedicated Type

Coefficient-wise arithmetic, especially for matrices over PolynomialRingZq can be tedious to self-implement, so we provide a separate datatype that stores values in the NTT-transform and allows for very basic arithmetic operations. This makes the current state of the program very explicit, and reduces the implementation workload of the developer.

use crate::math_foundation::ntt_modulus_instantiation::instantiate_ntt_modulus;
use qfall_math::integer_mod_q::{NTTPolynomialRingZq, PolynomialRingZq};

fn ntt_arithmetic() {
    let modulus = instantiate_ntt_modulus();

    let poly1 = PolynomialRingZq::sample_uniform(&modulus);
    let poly2 = PolynomialRingZq::sample_uniform(&modulus);

    let ntt_poly1: NTTPolynomialRingZq = poly1.ntt();
    let ntt_poly2: NTTPolynomialRingZq = poly1.ntt();

    // normal multiplication
    let normal_mul = poly1 * poly2;

    // ntt multiplication
    let ntt_mul = ntt_poly1 * ntt_poly2;

    assert_eq!(normal_mul, ntt_mul.inv_ntt())
}

Unsupported NTTs

Currently, we only support a full split of positive/negative-wrapped convolutions. Adding other splits (e.g., as specified in ML-KEM) is desirable as well as optimizing the current implementation. Please refer to contribution guidelines in case you want to optimize or extend this feature.

Random Sampling

Randomly sampled values are an essential part of (lattice-based) cryptography. qfall-math provides functions to sample from the following distributions efficiently and conveniently. The samplers themselves are implemented in qfall_math::utils::sample.

Uniform Distribution

Sampling values uniformly is an inevitable part of modern and post-quantum cryptography. Thus, qFALL provides uniform samplers for all reasonable data types.

    let uniform_sample_z = Z::sample_uniform(-5, 5)?;
    let uniform_sample_zq = Zq::sample_uniform(257);

For Z, the first parameter specifies the inclusive lower bound of the interval, from which is sampled. The second parameter specifies the exclusive upper bound. Hence, the first line samples a random integer from the interval \( [-5, 4] \). The function returns an error if the specified interval is invalid. For Zq, the function samples uniformly from \( [0, \text{modulus}-1] \).

A similar API instantiates polynomials and matrices with each entry sampled from any implemented distribution. In these cases, the first parameters specify the dimensions of the new matrix or the maximum degree of the freshly instantiated polynomial. All subsequent parameters are specific to the distribution to sample from.

    let uniform_matz = MatZ::sample_uniform(2, 2, -5, 5)?;
    let uniform_polyoverz = PolyOverZ::sample_uniform(256, -5, 5)?;
    let uniform_matzq = MatZq::sample_uniform(2, 2, 257);
    let uniform_matpolynomialringzq = MatPolynomialRingZq::sample_uniform(2, 2, &modulus);

Discrete Gaussian Distribution

Discrete Gaussians are often required to instantiate lattice-based problems like Learning with Errors. Thus, we support the instantiation of integer and residue class data type sampled according to the discrete Gaussian distribution.

    let discrete_gauss_z = Z::sample_discrete_gauss(center, s)?;
    let discrete_gauss_zq = Zq::sample_discrete_gauss(modulus, center, s)?;

The discrete Gaussian distribution is implemented via rejection sampling from GPV08. This algorithm takes a center and the Gaussian parameter s to sample a value \( x \) according to the discrete Gaussian distribution over the interval \( [c - 6 \cdot s, c + 6 \cdot s] \cap \mathbb{Z} \). center defines the value(s) with peak probability. The tailcut is set to 6 per convention s.t. it satisfies \( \omega(\sqrt{\log n}) \) for relevant parameter sizes. However, the value can be changed using an unsafe setter for qfall_math::utils::sample::discrete_gauss::TAILCUT if needed.

Furthermore, qfall-math supports sampling discrete Gaussian over arbitrary lattices by implementing SampleD from GPV08. It outputs a discrete Gaussian distributed point of the lattice centered around center, which is the \( 0 \)-vector in our example. The lattice is specified by a basis and the specified center does not have to be a lattice point.

    let basis = MatZ::from_str("[[7,3],[7,0]]")?;
    let center = MatQ::new(2, 1);
    let s = 8.0;

    let discrete_gauss_over_lattice = MatZ::sample_d(&basis, &center, s)?;

Binomial Distribution

As discrete Gaussian sampling is computationally expensive and hard to implement in constant time, several schemes replace it by sampling from a binomial distribution that resembles the required discrete Gaussian closely.

    let binomial_z = Z::sample_binomial(5, 0.5)?;
    let binomial_zq = Zq::sample_binomial(3, 5, 0.5)?;

The last two parameters denote the number of experiments n and probability p with which each Bernulli-experiment succeeds. Any parameters preceding these, are specific to their type, i.e. the modulus in case of Zq. To sample centered binomial distributions, qfall-math offers the function sample_binomial_with_offset for each type.

Further Information

The presented samplers are available for all types of integers and residue classes including polynomials and matrices over these types. For rationals, there are fewer and other samplers available. Please, refer to the documentation to find specifics.

All presented samplers use random bits generated by ThreadRng from the rand-crate. This sampler is considered to be cryptographically secure by building on ChaCha with 12 rounds.

Seeded Sampling

Every sampling function has a variant with suffix _seeded, which takes a 256-bit seed [u8; 32] as its last parameter. It draws its random bits from a StdRng seeded with this seed, which also builds on ChaCha with 12 rounds. The same seed and parameters always yield the same sample, which makes experiments and tests reproducible and enables Known Answer Tests (KATs).

    let seed = [42; 32];

    let matzq_0 = MatZq::sample_uniform_seeded(2, 2, 257, seed);
    let matzq_1 = MatZq::sample_uniform_seeded(2, 2, 257, seed);
    assert_eq!(matzq_0, matzq_1);

    let discrete_gauss_z = Z::sample_discrete_gauss_seeded(0, 8.0, seed)?;

Building Blocks

Building on top of qFALL-math, qFALL-tools provides building blocks and helper functions for lattice-based implementations. The crate is designed to be extended by researchers while implementing with the qFALL library suite. Nevertheless, we provide some basic features that can be found in existing literature.

We show how we implemented a building block: Gadget-Trapdoors; and how it can be used to define a preimage sampleable function (PSF).

G-Trapdoor

\(\mathbf{G}\)-trapdoors are an important tool for creating trapdoors for lattices that are defined by uniformly looking matrices. We consider a modulus \(q = 2^k\) that is a power of two for simplicity. The gadget vector is then defined as \(\mathbf{g}^t = \begin{pmatrix}1 & 2 & 4 & 8 & \ldots & 2^k\end{pmatrix}\). Given any target \(u \in \mathbb{Z}_q\), its binary decomposition \(\mathbf{x}^t = \begin{pmatrix}u_0 & u_1 & \ldots & u_k\end{pmatrix}\) can be used as a solution for a linear equation \(\mathbf{g}^t \mathbf{x} = u\). This can be naturally extended to gadget matrices \(\mathbf{G} = \mathbf{I}_n \otimes \mathbf{g}^t\) and targets that are vectors.

A gadget matrix now becomes useful if a public matrix \(A \in \mathbb{Z}_q^{n \times m}\) has a \(\mathbf{G}\)-trapdoor matrix \(\mathbf{T} \in \mathbb{Z}^{m \times n \cdot k}\) such that \(\mathbf{A} \cdot \mathbf{T} = \mathbf{G}\).

For a linear equation of the form \(\mathbf{A x} = \mathbf{t}\), we can find a solution for \(\mathbf{Gy} = \mathbf{t}\) first. This solution implies that \(\mathbf{Ty}\) is a valid solution \(\mathbf{x}\) for the first equation.

How they could be implemented

We give a brief idea showing how a simple version of \(\mathbf{G}\)-trapdoor can be implemented using our libraries (our actual implementation is more general than the example here). A \(\mathbf{G}\)-trapdoor can be implemented by sampling a uniform matrix \(\mathbf{\bar{A}}\) and a short trapdoor matrix \(\mathbf{R}\) from, e.g., the binomial distribution with \(p=0.5\) and two trials and centered around \(0\). The first step in the process of generating a gadget trapdoor is the generation of the gadget matrix itself:

use qfall_math::{
    integer::{MatZ, Z},
    traits::{MatrixDimensions, MatrixSetEntry, Tensor},
};

fn gen_gadget_mat(n: i64, k: i64, base: &Z) -> MatZ {
    // get g^t
    let gadget_vec = gen_gadget_vec(k, base).transpose();
    // instantiate I_n
    let identity_mat = MatZ::identity(n, n);
    // return G = I_n ⊗ g^t
    identity_mat.tensor_product(&gadget_vec)
}

fn gen_gadget_vec(k: i64, base: &Z) -> MatZ {
    let mut entry = Z::ONE;
    let mut out = MatZ::new(k, 1);
    for i in 0..out.get_num_rows() {
        out.set_entry(i, 0, &entry).unwrap();
        entry *= base
    }
    out
}

Next, sample a uniform matrix \(\mathbf{\bar{A}}\) and a trapdoor \(\mathbf{R}\). The matrix \(\begin{bmatrix}\mathbf{\bar{A}} & \mathbf{G} - \mathbf{\bar{A} R}\end{bmatrix}\) now has a gadget trapdoor: \(\begin{bmatrix}\mathbf{R}^t & \mathbf{I}\end{bmatrix}^t\).

use qfall_math::traits::{Concatenate, Tensor};
use qfall_math::{
    error::MathError,
    integer::{MatZ, Z},
    integer_mod_q::MatZq,
    traits::Pow,
};
use qfall_tools::sample::g_trapdoor::gadget_classical::gen_gadget_vec;

fn gen_trapdoor(n: u32, m: u32, k: u32) -> Result<(MatZq, MatZ), MathError> {
    let base = Z::from(2);
    let q = base.pow(k)?;

    let a_bar = MatZq::sample_uniform(n, m, q);
    let g_t = gen_gadget_vec(k, &base).transpose();
    let identity_n = MatZ::identity(n, n);
    // G = I \otimes g^t
    let g_mat = identity_n.tensor_product(&g_t);
    let r = MatZ::sample_binomial_with_offset(n, m, -1, 2, 0.5)?;

    // set A = [A_bar | G - A_bar R]
    let a = a_bar.concat_horizontal(&(g_mat - (&a_bar * &r)))?;
    Ok((a, r))
}

Our Implementation

We abstracted these implementation steps for you by providing a more general implementation of the above. It can be found in qfall_tools::sample::g_trapdoor using the following API. A matrix and a trapdoor can be generated together with some default parameters as:

use qfall_tools::sample::g_trapdoor::gadget_default::gen_trapdoor_default;

fn generate_trapdoor() {
    let (a, t) = gen_trapdoor_default(128, u32::MAX);
}

\(\mathbf{G}\)-trapdoors can be used for all sorts of constructions, such as signature and identity-based encryption schemes. These often utilize so-called tags, denoted by an invertible matrix \(\mathbf{H}\) to satisfy the slightly altered equation \(\mathbf{A} \cdot \mathbf{T} = \mathbf{H} \cdot \mathbf{G}\). Thus, our implementation also enables the use of tags with \(\mathbf{G}\)-trapdoors.

Another useful trapdoor for lattices is given by a short basis of that lattice. Given a \(\mathbf{G}\)-trapdoor for a matrix \(\mathbf{A}\), one can create a short base for \(\Lambda_q^\perp(\mathbf{A})\):

use qfall_math::integer_mod_q::MatZq;
use qfall_tools::sample::g_trapdoor::{
    gadget_classical::gen_trapdoor, gadget_parameters::GadgetParameters,
    short_basis_classical::gen_short_basis_for_trapdoor,
};

fn generate_short_base() {
    let params = GadgetParameters::init_default(128, u32::MAX);

    let a_bar = MatZq::sample_uniform(&params.n, &params.m_bar, &params.q);
    let tag = 17 * MatZq::identity(&params.n, &params.n, &params.q);
    let (a, t) = gen_trapdoor(&params, &a_bar, &tag).unwrap();

    let b = gen_short_basis_for_trapdoor(&params, &tag, &a, &t);
}

This base can then be used to implement cryptographic constructions. \(\mathbf{G}\)-trapdoor are also supported for rings. Please refer to the documentation of qFALL-tools to find all details.

Preimage Sampleable Functions

Preimage sampleable functions are a primitive that is utilized in cryptographic constructions such as signature or identity-based encryption schemes. It is first, and foremost a trapdoored function \(f_a :D \to R\), that, with access to a trapdoor \(td\) generated as \((a, td) \gets Gen(1^\lambda)\) allows to sample preimages for \(r \in R\) under \(f_a\). Additionally, there exists an algorithm \(SampleD\), that samples elements in \(D\) with specific properties related to the presampling and \(f_a\). For more details, refer to the definition in the original paper GPV08.

We provide a trait that interfaces the functionality of a PSF. qFALL-tools also has explicit implementations of the trait that can be used in constructions.

The PSF Trait

The PSF trait consists of five algorithms trap_gen, samp_d, samp_p, check_domain, f_a. Here, f_a is the function evaluation and check_domain checks if an element is in the domain \(D\).

A PSF trait can be implemented for a specific struct as follows:

use qfall_tools::primitive::psf::PSF;
pub type Placeholder = bool;

pub struct ExamplePSF;

impl PSF for ExamplePSF {
    type A = Placeholder;
    type Trapdoor = Placeholder;
    type Domain = Placeholder;
    type Range = Placeholder;

    fn trap_gen(&self) -> (Self::A, Self::Trapdoor) {
        todo!()
    }

    fn samp_d(&self) -> Self::Domain {
        todo!()
    }

    fn samp_p(&self, a: &Self::A, r: &Self::Trapdoor, u: &Self::Range) -> Self::Domain {
        todo!()
    }

    fn f_a(&self, a: &Self::A, sigma: &Self::Domain) -> Self::Range {
        todo!()
    }

    fn check_domain(&self, sigma: &Self::Domain) -> bool {
        todo!()
    }
}

Using the PSF Trait

The PSF trait can be used to implement full-domain hash signatures very easily and generically.

use crate::crypto_tools::psf_definition::ExamplePSF;
use crate::crypto_tools::psf_definition::Placeholder;
use qfall_tools::primitive::psf::PSF;

pub struct ExampleUsingPSF {
    example_psf: ExamplePSF,
}

impl ExampleUsingPSF {
    fn kgen(&self) -> (Placeholder, Placeholder) {
        self.example_psf.trap_gen()
    }

    fn sign(&self, a: Placeholder, td: Placeholder, m: &str) -> Placeholder {
        // hash message into domain
        let t = todo!("Hash(m)");
        self.example_psf.samp_p(&a, &td, t)
    }

    fn verify(&self, a: Placeholder, m: &str, sig: Placeholder) -> bool {
        // hash message into domain
        let t: Placeholder = todo!("Hash(m)");
        self.example_psf.check_domain(&sig) && self.example_psf.f_a(&a, &sig) == t
    }
}

Originally, we had a completely generic implementation, where the signature uses a generic PSF. However, the type handling became too complicated, so we decided on an implementation, where the developer needs to provide the explicit types for the fixed implementations. However, the abstraction of the PSF behavior is still something we consider desirable for consistency.

Common Utility Functions

The qfall-tools crate includes a suite of standard algorithms and shorthands designed to streamline prototyping. We document them here to ensure you don’t reinvent the wheel – utilizing these reviewed and tested implementations allows you to focus on high-level prototyping rather than boilerplate code.

You can find these utilities in the qfall_tools::utils module:

• common_encodings: Encodes any integer into a PolynomialRingZq s.t. each coefficient encodes at most one value in \([0,p)\), which is spread by a factor of \(q/p\). Thus, this function mimics the behavior of \(\lfloor \frac{q}{p} \cdot \mu \rfloor\) for an encoded message \(\mu \in \mathcal{R}_p\), which is often used in lattice-based public-key encryption schemes.
• common_moduli: Provides helper functions new_cyclic and new_anticyclic to create ModulusPolynomialRingZq instances for \( X^n - 1 \bmod q \) and \( X^n + 1 \bmod q \) respectively.
• rotation_matrix: Contains functions to generate rotation matrices that can serve as bases for structured lattices (specifically for anti-cyclic lattices).

Note: This list is not frequently updated. So, please check qfall_tools::utils for updates and further details.

Cryptographic Schemes and Prototypes

We have seen that qFALL-math provides the basic types and functions while qFALL-tools provides common building block for cryptographic schemes.

qFALL-schemes is a collection of prototype implementations of lattice-based cryptography. This chapter gives an overview of the already implemented schemes and gives a hands-on tutorial on how to create your own prototype.

Implemented Prototypes

We will give some explicit examples, but here is a short (non-exhaustive) list of features that qFALL-schemes currently provides.

• Public-Key Encryption
  • LWE Encryption
  • Dual LWE Encryption
  • LPR Encryption
  • Ring-based LPR Encryption
  • CCA-secure Encryption
  • K-PKE
• Identity-Based Encryption
  • IBE from Dual LWE Encryption
• Signatures
  • Full-Domain Hash (FDH) / Probabilistic FDH (PFDH)
  • Ring-based FDH
  • ML-DSA (prototype, not FIPS 204 compliant)
• Hash Functions
  • SIS-Hash Function
  • SHA256

Note: This list is neither exhaustive nor frequently updated. So, please check qfall_schemes for updates and further details.

Encryption

Public-Key Encryption

A public-key encryption scheme consists of three algorithms: key_gen, enc and dec.

• key_gen(): outputs a tuple (pk, sk) of public key and secret key,
• enc(pk, m): takes in a message m and a public key pk, and outputs a ciphertext c,
• dec(sk, c): takes in a ciphertext c and a secret key sk, and outputs a message m.

This general behavior is captured by the PKEncryptionScheme trait. Any explicit implementation fixes the domains of the public key, secret key, message and ciphertext. When implementing the trait for a struct, then that struct can hold additional public parameters such as the security parameter.

With the provided functionality, it is easy to setup a scheme to encrypt and decrypt a bit:

use qfall_schemes::pk_encryption::{LPR, PKEncryptionScheme};

fn example_lpr() {
    // setup public parameters and generate key-pair
    let lpr = LPR::default();
    let (pk, sk) = lpr.key_gen();

    // encrypt and decrypt one bit
    let cipher = lpr.enc(&pk, 1);
    let m = lpr.dec(&sk, &cipher);
}

We implemented a generic trait to enable multi-bit encryption and decryption for schemes like LWE, Dual LWE, and LPR Encryption, which are in the implemented variant just capable of encrypting one bit.

use qfall_schemes::pk_encryption::{GenericMultiBitEncryption, LPR, PKEncryptionScheme};

fn example_lpr_multi_bit() {
    // setup public parameters and generate key-pair
    let scheme = LPR::default();
    let (pk, sk) = scheme.key_gen();

    // encrypt and decrypt multiple bits
    let cipher = scheme.enc_multiple_bits(&pk, 15);
    let message = scheme.dec_multiple_bits(&sk, &cipher);
}

The ring-based variant of LPR does not have this issue. It can encrypt multiple bits at once, and is more efficient, as it is based on ideal lattices and thus, based on polynomial rings. In this case, multiple bits can be encrypted at once with respect to the choice of n.

The implemented public-key encryption schemes can be found in qfall_schemes::pk_encryption. Although not mandatory, several schemes provide functions to generate suitable public parameters via new_from_n(n) for some provided n, and a default parameter set.

Signatures

A signature scheme consists of three algorithms: key_gen, sign and vfy.

• key_gen(): outputs a tuple (pk, sk) of public key and secret key,
• sign(sk, m): takes in a secret key sk and a message m , and outputs a signature sig,
• vfy(pk, m, sig): takes in a public key pk, a message m and a signature sig, and outputs true or false.

This general behavior is captured by the SignatureScheme trait. Similar to public-key encryption schemes, it is easy to setup a scheme to sign and verify messages once an implementation of the trait is given.

use qfall_schemes::signature::{SignatureScheme, fdh::FDHGPV};

fn signing_and_verifying() {
    // setup public parameters and generate key-pair
    let mut fdh = FDHGPV::setup(10, 512, 42);
    let (pk, sk) = fdh.key_gen();

    // sign and verify a message
    let sigma = fdh.sign("Hello World!".to_owned(), &sk, &pk);
    assert!(fdh.vfy("Hello World!".to_owned(), &sigma, &pk))
}

Among the implemented signature schemes are Full-Domain Hash (FDH) and Probabilistic FDH (PFDH) signature schemes that build upon a PSF. After several iterations, we decided to remove our initially completely generic implementation as it was not properly maintainable and too complicated to extend or build upon it. The current implementations fix the domains themselves rather than defining them via generics.

As the FDH signature scheme is stateful and requires storage, the signature scheme must also be serializable. A serialization looks as follows:

use qfall_math::{integer::MatZ, integer_mod_q::MatZq, rational::MatQ};
use qfall_schemes::signature::{SignatureScheme, fdh::FDHGPV};
use qfall_tools::primitive::psf::PSFGPV;

fn serialize_and_deserialize() {
    // setup public parameters and generate key-pair
    let mut fdh = FDHGPV::setup(10, 1024, 42);
    let (pk, sk) = fdh.key_gen();

    // sign one message
    let _ = fdh.sign("Hello World!".to_owned(), &sk, &pk);

    // serialize the signature scheme
    let fdh_string = serde_json::to_string(&fdh).unwrap();

    // deserialize the signature scheme together with the storage
    let fdh_deserialized: FDHGPV = serde_json::from_str(&fdh_string).unwrap();
}

The implemented lattice-based signature schemes can be found in the module qfall_schemes::signature.

Prototype your own Scheme

In this section, we provide a hands-on tutorial on how to implement a private-key encryption scheme based on ring-LWE.

Note: This section is a step-by-step tutorial and as such code-blocks only display the outline of the code. In the top right corner of every code field, there is an eye, which allows you to display the entire documentation. Press it to see the solution.

Private-Key Encryption Scheme - Ring-LWE

First, we look at the formal definition of the scheme that we want to implement.

Let \( {R} = \mathbb{Z}[X]/(X^n + 1) \), then we define the ring-based LWE private-key encryption scheme as follows:

• \(sk \leftarrow \text{KGen}(1^n): sk \leftarrow {R}_q\)
• \((a, b) \leftarrow \text{Enc}(sk, m): a \leftarrow {R}_q, e \leftarrow \chi, b:= sk \cdot a + e + \lfloor q/2 \rfloor \cdot m \text{, where } m \in {R}_2\)
• \(m \leftarrow \text{Dec}(sk, (a,b)): d:= b - a\cdot sk\) and each coefficient of \(d\) is mapped to \(0\) if it is closer to \(0\) than to \(q/2\) and to \(1\) otherwise.

The error distribution \(\chi\) samples an element of \({R}_q\) with small coefficients and the modulus \(q\) is also chosen appropriately. Scaling \(m\) by \(\lfloor q/2 \rfloor\) is what makes decryption work: \(d = e + \lfloor q/2 \rfloor \cdot m\), i.e. every coefficient of \(d\) is close to \(0\) for a \(0\)-bit and close to \(q/2\) for a \(1\)-bit, as long as the coefficients of \(e\) are smaller than \(q/4\).

Defining the correct Trait

In order to implement a scheme, first define the common functionality of its primitive. In our case, the formal definition of a private-key encryption scheme provides all required information for this task:

• \(sk \leftarrow \text{KGen}(1^n):\) generates a private key for encryption
• \(c \leftarrow \text{Enc}(sk, m):\) encrypts the message
• \(m \leftarrow \text{Dec}(sk, c):\) decrypts the message

Create a trait according to the specification above.

// Add the corresponding function signatures to this trait

pub trait PrivKeyEncryption {
    type SecretKey;
    type Message;
    type Cipher;

    /// Generates a secret key that can be used for encryption and decryption.
    fn key_gen(&self) -> Self::SecretKey;
    /// Encrypts a message using the secret key.
    fn enc(&self, sk: &Self::SecretKey, message: &Self::Message) -> Self::Cipher;
    /// Decrypts a ciphertext using the secret key.
    fn dec(&self, sk: &Self::SecretKey, cipher: &Self::Cipher) -> Self::Message;
}

Determining Public Parameters and Defining a corresponding Struct

Traits are implemented for structs. The actual implementation of our scheme corresponds to an implementation of the trait for a struct. This struct holds the public parameters needed for the computation:

// The struct is still missing the public parameters, try to identify them

pub struct PrivKRingLWE {
    // the security parameter
    n: Z,
    // the modulus
    q: ModulusPolynomialRingZq,
    // the parameter for the error distribution
    alpha: Q,
}

Implementing the Scheme

The next step is to implement the trait for our previously defined struct.

// This defines the structure
// We have to implement each algorithm individually

impl PrivKeyEncryption for PrivKRingLWE {
    type SecretKey = PolynomialRingZq;
    type Message = Z;
    type Cipher = (PolynomialRingZq, PolynomialRingZq);

    fn key_gen(&self) -> Self::SecretKey {
    }

    fn enc(&self, sk: &Self::SecretKey, message: &Z) -> Self::Cipher {
    }

    fn dec(&self, sk: &Self::SecretKey, (a, b): &Self::Cipher) -> Z {
    }
}

For the generation algorithm we have to implement

• \(sk \leftarrow \text{KGen}(1^n): sk \leftarrow {R}_q\) which corresponds to:

    fn key_gen(&self) -> Self::SecretKey {
        PolynomialRingZq::sample_uniform(&self.q)
    }

Now we have to implement the encryption. As it was more practical, we have as input an integer rather than a value of \( {R}_2 \). However, we need a way to transform an integer into \(\lfloor q/2 \rfloor \cdot m\) with \(m \in {R}_{2}\) and back. Fortunately, qFALL-tools provides this functionality for arbitrary \({R}_{p}\), i.e. \(\lfloor q/p \rfloor \cdot m\) with \(m \in {R}_{p}\), with the functions encode_value_in_polynomialringzq and decode_value_from_polynomialringzq.

For the encryption algorithm we have to implement the following.

• \((a, b) \leftarrow \text{Enc}(sk, m): a \leftarrow {R}_q, e \leftarrow \chi, b:= sk \cdot a + e + \lfloor q/2 \rfloor \cdot m \text{, where } m \in {R}_2\)

The algorithmic description given above corresponds to the following implementation.

    fn enc(&self, sk: &Self::SecretKey, message: &Z) -> Self::Cipher {
        let mu_q_half = encode_value_in_polynomialringzq(message, 2, &self.q).unwrap();

        // a <- R_q
        let a = PolynomialRingZq::sample_uniform(&self.q);
        // e <- χ
        let e = PolynomialRingZq::sample_discrete_gauss(&self.q, 0, &self.alpha * &self.q.get_q())
            .unwrap();

        let b = sk * &a + e + mu_q_half;

        (a, b)
    }

Note that we use a discrete Gaussian error distribution with Gaussian parameter \(s = \alpha \cdot q\).

The last function left to implement is decryption. At this point, it should be quite easy to finalize the implementation. So, we provide the solution directly:

    fn dec(&self, sk: &Self::SecretKey, (a, b): &Self::Cipher) -> Z {
        let result = b - sk * a;

        decode_value_from_polynomialringzq(&result, 2).unwrap()
    }

Choosing Parameters and Testing the Scheme

Finally, we introduce a set of parameters to test our construction. This can be done in the following way.

    pub fn parameter_set() -> Self {
        Self::new(512, 92897729, 0.000005)
    }

    pub fn new(n: impl Into<Z>, q: impl Into<Modulus>, alpha: impl Into<Q>) -> Self {
        let n: Z = n.into();

        // mod = (X^n + 1) mod q
        let q = new_anticyclic(&n, q).unwrap();

        let alpha: Q = alpha.into();

        Self { n, q, alpha }
    }

The previously defined set of parameters can then be used to test whether encrypting and decrypting messages works.

    #[test]
    fn enc_and_dec() {
        let message = Z::from(17);
        let scheme = PrivKRingLWE::parameter_set();

        let sk = scheme.key_gen();
        let c = scheme.enc(&sk, &message);

        assert_eq!(message, scheme.dec(&sk, &c));
    }

Shared Features

qFALL-math, qFALL-tools and qFall-schemes share several common features. In this section, we mainly want to highlight and explain their benchmarking capabilities by example. Furthermore, every struct in qFALL enables serialization and deserialization using json-format s.t. storing and recovering data is quick and easy to do.

Benchmarking and Profiling

Benchmarking is the process of measuring the performance of a program. It can be used to compare the execution time of two different algorithms. Profiling can be used to analyze where time is spent during the evaluation of an algorithm. We suggest to use criterion for benchmarking and flamegraph for profiling.

Benchmarking with Criterion

criterion supports statistical analysis of the runtime of your program. A plotting library has to be installed to generate graphs. You can find more information and help here:

• Criterion-rs GitHub
• Cargo-criterion GitHub
• Criterion Book (!Check your criterion version. As of writing this, the criterion book is not up-to-date.)

Commands for Criterion

a) cargo criterion <benchmark name regex>
Has to be installed with cargo install cargo-criterion.
Pros:

• You can remove features = ["html_reports"] from the Cargo.toml, leading to (slightly) faster compile times.
• criterion aims to move to just using cargo criterion
• The large Probability Density Function graph shows the samples and marks the outlier categorization borders.
• can use either gnuplot or plotters

b) cargo bench <benchmark name regex>
Pros:

• Can visualize the change in performance compared to the previous run or other baseline

Cons:

• can only use gnuplot

Profiling with Flamegraph

Flamegraphs provide insights into where execution time is spent. Thus, they enable efficient identification of bottlenecks in your code.

Details can be found here:

• Flamegraph GitHub.

Installation

Installing flamegraph in Linux and macOS is usually done by simply installing flamegraph using the following command.

cargo install flamegraph

In WSL you need some more steps, since you need to install a dependency called perf manually.

After running cargo install flamegraph, ensure your list of packages is up-to-date using sudo apt update and install several packages among build-essentials by running

sudo apt install -y build-essential libelf-dev libnuma-dev flex bison libdw-dev libunwind-dev libaudit-dev libslang2-dev libperl-dev python3-dev binutils-dev liblzma-dev libiberty-dev

Then you go into the home directory with cd ~, find the current kernel you’re running by executing uname -r, and download the appropriate linux kernel with an adjusted version of the following link.

wget - https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.15.5.tar.xz

Next, you extract the downloaded file with tar -xvf linux-5.15.5.tar.xz and move into perf with cd linux-5.15.5/tools/perf. In this directory, run make to compile it. The last step is to make perf visible / add it to your path, e.g., by running sudo cp ./perf /usr/local/bin/.

Command for Flamegraph

cargo flamegraph --freq 63300 --bench benchmarks -- --bench --profile-time 5 <benchmark name regex>
Generates a flamegraph that allows us to approximate how long each function executes. The accuracy of the approximation is better the more samples are produced. That can be improved by

• increasing the sampling frequency (--freq 63300). This frequency is throttled to the highest possible frequency, which depends on the CPU, CPU-temperature, power settings and much more…
• increasing profile-time (in seconds). That is how long the benchmark code will be executed. This parameter also disables the statistical analysis of criterion which prevents it from showing up in the graph. This parameter is optional but suggested.

The flamegraph can be overwhelming since it exposes a lot of internal workings of Rust, criterion, and more. The easiest way to find a specific function is to search with Ctrl + F. Simply enter a part of the Rust function name or regex (not the benchmark name).

Serialization

The most common format for serialization and deserialization is JSON. Each type in qFALL-math supports serialization and deserialization using serde_json.

use qfall_math::integer::Z;

fn serialize_and_deserialize_z() {
    let int = Z::from(17);

    // Serialization of a Number
    let string = serde_json::to_string(&int).unwrap();

    // Deserialization of a String into a Number
    let string_int = "{\"value\":\"17\"}";
    let z_deserialized: Z = serde_json::from_str(string_int).unwrap();
}

This principle can be applied to all types but is especially useful if we want to create new structs which correspond to cryptographic constructions. If all parts of a struct are serializable, then the struct can be derived as serializable and no new implementation is needed:

use qfall_math::{integer::Z, rational::Q};
use serde::{Deserialize, Serialize};

#[derive(Serialize, Deserialize)]
struct SerializableStruct {
    integer: Z,
    rational: Q,
}

This allows for immediate serialization and deserialization of newly created constructions.

Versioning and Updates

This part of the tutorial documents how the qFALL crates evolve between minor releases. For every release that requires action on your side, it lists what is new, which bugs were fixed, and how to move your code to the new version.

Semantic Versioning

All qFALL crates follow Semantic Versioning. As long as the crates are not stable yet, i.e. before version 1.0.0, the following rules apply:

• Minor version updates, e.g. 0.1.x → 0.2.0, may introduce API-breaking changes.
• Patch version updates, e.g. 0.2.0 → 0.2.1, are backwards compatible and only contain bug fixes, documentation, or non-breaking additions.

Hence, we recommend to fix the minor version in your Cargo.toml, which is also what cargo add does by default.

[dependencies]
qfall-math = "0.2"
qfall-tools = "0.2"
qfall-schemes = "0.2"

With this requirement, cargo update pulls in patch releases automatically, but never moves you to the next minor version without you editing your Cargo.toml.

Released Versions

✅ available on crates.io, ❌ yanked, – not released

We aimed for maximal compatibility and allowed any 0.x version of several dependencies. Breaking changes in these dependencies, e.g. rand 0.10 and sha2 0.11, broke the 0.1 releases. Hence, we yanked them.

Using 0.1 Releases Today

The following combinations still build, if the listed dependencies are fixed in your Cargo.lock.

Compatible Versions Across Crates

The three crates build on each other: qfall-tools depends on qfall-math, and qfall-schemes depends on both. Always update them together and use the same minor version for all qFALL crates in your project.

The 0.1 and 0.2 releases cannot be mixed in one project. Both FLINT bindings, flint-sys and flint3-sys, link the native library flint, and Cargo allows only one crate per native library in a dependency tree. Hence, if any dependency of your project still requires a 0.1 release, Cargo fails to resolve the dependencies with an error mentioning links = "flint". In this case, update that dependency as well.

How to Update

1. Read the update notes of the target version, in particular its How to Transition chapter.
2. Ensure your Rust toolchain is recent enough, e.g. via rustup update and rustc --version.
3. Update all qFALL crates at once, e.g. via

   cargo add qfall-math@0.2 qfall-tools@0.2 qfall-schemes@0.2
   

4. Run cargo clean, cargo build and work through the compiler errors with the help of the transition guide.
5. Run your tests. Some changes, which are listed in the chapter on bug fixes, change the output of functions without changing their signature.

If you encounter problems that are not covered here, please open an issue in the GitHub repository of the respective crate.

Updating to 0.2

Version 0.2 is the first breaking release of qFALL since its publication on crates.io. Its most important change is invisible in most code: qfall-math moved from FLINT 2.8 to FLINT 3.6. Beyond that, the release adds reproducible (seeded) sampling, several convenience functions, a prototype of ML-DSA, and fixes a few bugs.

The following chapters cover the release in detail:

• New Features lists everything that was added to qfall-math, qfall-tools, and qfall-schemes.
• Bug Fixes lists the fixed bugs, including fixes that change the output of existing functions.
• How to Transition explains step by step how to move your project from version 0.1 to 0.2.

Main Novelties

• FLINT 3.6 via flint3-sys replaces FLINT 2.8 via flint-sys.
• Seeded sampling: every sampling function has a _seeded variant that takes a 256-bit seed and produces reproducible output.
• Negation via the unary - operator for all integer, rational, and residue class types.
• New functions: hamming_weight, norm_eucl for polynomials, get_representative_least_absolute_residue for all residue class types, and change_modulus/change_q to switch the modulus of an existing value.
• ML-DSA: a prototype of the signature scheme behind FIPS 204 in qfall-schemes.

Do I Need to Change My Code?

Most projects that only use the safe API of qFALL need nothing but a version bump, a call to cargo clean, and a newer Rust toolchain. The table below tells you which parts of the transition guide are relevant for you.

New Features in 0.2

qFALL-math

Seeded Sampling

Every sampling function in qfall-math now comes in two variants: the previously existing un-seeded sampler and a sampler that takes a seed on input to enable Known-Answer-Tests (KATs), i.e. experiments, tests, and benchmarks can be made reproducible via seeding.

use qfall_math::{integer::Z, integer_mod_q::MatZq};

let seed = [42; 32];

let mat_0 = MatZq::sample_uniform_seeded(3, 3, 17, seed);
let mat_1 = MatZq::sample_uniform_seeded(3, 3, 17, seed);
assert_eq!(mat_0, mat_1);

let e = Z::sample_discrete_gauss_seeded(0, 8, [7; 32]).unwrap();

The samplers in qfall_math::utils::sample, i.e. UniformIntegerSampler, DiscreteGaussianIntegerSampler, and BinomialSampler, accept an optional seed in their init functions. Inputting None selects a randomly chosen seed.

use qfall_math::{integer::Z, utils::sample::uniform::UniformIntegerSampler};

let mut sampler_0 = UniformIntegerSampler::init(&Z::from(256), Some([1; 32])).unwrap();
let mut sampler_1 = UniformIntegerSampler::init(&Z::from(256), Some([1; 32])).unwrap();
assert_eq!(sampler_0.sample(), sampler_1.sample());

// unseeded
let mut sampler = UniformIntegerSampler::init(&Z::from(256), None).unwrap();
let sample = sampler.sample();

Negation

The Neg trait is now implemented for owned values and references across all relevant datatypes. Hence, you can write -x instead of -1 * x.

use qfall_math::{integer::Z, integer_mod_q::MatZq};
use std::str::FromStr;

let a = Z::from(5);
assert_eq!(Z::from(-5), -&a);

let mat = MatZq::from_str("[[1, 2],[3, 0]] mod 7").unwrap();
assert_eq!(MatZq::from_str("[[6, 5],[4, 0]] mod 7").unwrap(), -mat);

Hamming Weight

All polynomial and matrix types provide hamming_weight, which returns the number of non-zero coefficients or entries.

use qfall_math::integer::{MatZ, PolyOverZ};
use std::str::FromStr;

let mat = MatZ::from_str("[[2, 3],[2, 0]]").unwrap();
assert_eq!(3, mat.hamming_weight());

let poly = PolyOverZ::from_str("4  0 -1 0 1").unwrap();
assert_eq!(2, poly.hamming_weight());

Least Absolute Residues for All Residue Class Types

get_representative_least_absolute_residue is now also implemented for PolyOverZq, PolynomialRingZq, and MatPolynomialRingZq. It returns the representative of each coefficient in [-⌊q/2⌋, ⌊q/2⌋] as an integer type, i.e. Z, MatZ, PolyOverZ, or MatPolyOverZ.

use qfall_math::{
    integer::{PolyOverZ, Z},
    integer_mod_q::{PolyOverZq, Zq},
};
use std::str::FromStr;

let value = Zq::from((15, 17));
assert_eq!(Z::from(-2), value.get_representative_least_absolute_residue());

let poly = PolyOverZq::from_str("3  1 16 9 mod 17").unwrap();
assert_eq!(
    PolyOverZ::from_str("3  1 -1 -8").unwrap(),
    poly.get_representative_least_absolute_residue()
);

Note that the behavior of Zq::get_representative_least_absolute_residue changed in this release, see Bug Fixes.

Changing the Modulus

The new functions change_modulus and change_q replace the modulus of an existing value in place. They take the representative of each coefficient in [0, q) and reduce it by the new modulus.

use qfall_math::integer_mod_q::{MatZq, PolynomialRingZq};
use std::str::FromStr;

let mut mat = MatZq::from_str("[[1, 15]] mod 17").unwrap();
mat.change_modulus(7);
assert_eq!(MatZq::from_str("[[1, 1]] mod 7").unwrap(), mat);

let mut poly = PolynomialRingZq::from_str("3  12 2 13 / 4  1 0 0 1 mod 17").unwrap();
poly.change_q(12);
assert_eq!("3  0 2 1 / 4  1 0 0 1 mod 12", poly.to_string());

This is handy for modulus switching and for compression techniques.

Further Additions

• norm_eucl returns the Euclidean norm as a Q for PolyOverZ, PolyOverZq, and PolynomialRingZq, complementing norm_eucl_sqrd.
• Factorization implements Debug.
• Debug is derived for Zq, PolynomialRingZq, MatPolynomialRingZq, ModulusPolynomialRingZq, and the NTT types now, which changes their Debug output, see How to Transition.
• All computations are performed by FLINT 3.6, which received several years of improvements and bug fixes since FLINT 2.8, see the FLINT history.

qFALL-tools

qfall-tools 0.2 contains no new features. It was updated to qfall-math 0.2 and flint3-sys, and it pins the minor versions of all its dependencies, see Bug Fixes.

qFALL-schemes

ML-DSA

qfall-schemes now contains MLDSA, a prototype of the module-lattice-based signature scheme standardized in FIPS 204, which is also known as Dilithium. It implements the SignatureScheme trait and comes with the three parameter sets of the standard.

use qfall_schemes::signature::{MLDSA, SignatureScheme};

// choose among MLDSA::ml_dsa_44(), MLDSA::ml_dsa_65() and MLDSA::ml_dsa_87()
let mut ml_dsa = MLDSA::ml_dsa_44();

let (pk, sk) = ml_dsa.key_gen();

let msg = String::from("Hello world!");
let signature = ml_dsa.sign(msg.clone(), &sk, &pk);

assert!(ml_dsa.vfy(msg, &signature, &pk));

The building blocks of ML-DSA are public as well, so that you can experiment with them in isolation or reuse them in your own prototypes: power2round, decompose, make_hint, use_hint (each also as a _coeff variant for a single coefficient), and modified_sample_in_ball.

Note that MLDSA is not supposed to be an implementation up to the specification of FIPS 204. It is implemented with certain levels of freedom and provides significantly more free variables to experiment with the prototype.

Bug Fixes in 0.2

This chapter lists all bugs of the 0.1 releases that are fixed in 0.2. Fixes marked with behavior change change the output of a function without changing its signature. The compiler will not point you to them, so check your code for these functions.

qFALL-math

• Behavior change: Zq::get_representative_least_absolute_residue returned the absolute value of the least absolute residue instead of the residue itself. For example, 15 mod 17 was mapped to 2 instead of -2. The function now returns values in [-⌊q/2⌋, ⌊q/2⌋] as documented.
• Behavior change: MatZq::sample_discrete_gauss, MatZq::sample_binomial, and MatZq::sample_binomial_with_offset did not reduce the sampled values modulo q before storing them. For example, MatZq::sample_discrete_gauss(1, 1, 3, 0, 15.0) could return [[-1]] mod 3 or [[5]] mod 3. Such matrices printed, compared, and computed with values outside of [0, q), which could lead to wrong results in subsequent operations. All entries are now reduced to [0, q).
• MatZq::clone leaked the memory of the entries of the freshly allocated matrix, as the clone re-initialized them instead of overwriting them. This issue is fixed by clearing the allocated memory before cloning the entries.
• PolyOverZq::clone converted the polynomial into a string and parsed it again. Now, it copies the FLINT structure directly and avoids this costly detour.
• qfall-math 0.1.0 failed to compile once rand 0.10 was released, as it required rand = "0". qfall-math 0.1.1 adapted to the breaking changes of rand 0.10, and 0.2 requires specific minor versions of all its dependencies due to further breaks of SemVer rules from dependencies.

qFALL-tools

• qfall-tools 0.1.0 required qfall-math = "0", sha2 = "0", and typetag = "0", i.e. any 0.x version. New releases of these dependencies with breaking changes could therefore break the build. qfall-tools 0.2 requires qfall-math = "0.2", sha2 = "0.11", and typetag = "0.2" to protect against breaking changes of these crates.

qFALL-schemes

• qfall-schemes 0.1.0 failed to build with recent releases of sha2, as the computed hash no longer implemented hexadecimal formatting via {:x}. The SHA-256 based hash functions in qfall_schemes::hash assemble the hex string manually since 0.1.1. The output is unchanged.
• Like qfall-tools, the crate pins the minor versions of all its dependencies since 0.2.

How to Transition from 0.1 to 0.2

This chapter guides you step by step from version 0.1 to 0.2. Most of it covers the switch from FLINT 2.8 (flint-sys) to FLINT 3.6 (flint3-sys). If you only use the safe API of qFALL, the FLINT switch affects your build, but not your code, and you can skip Migrating Direct FLINT Usage.

Updating Dependencies

Rust Toolchain

qfall-tools 0.2 and qfall-schemes 0.2 require Rust 1.88 or newer, mostly due to their dependency on sha2 0.11.

rustup update stable
rustc --version

Cargo.toml

Update all qFALL crates at once.

[dependencies]
qfall-math = "0.2"
qfall-tools = "0.2"
qfall-schemes = "0.2"

To avoid build issues, run cargo clean and cargo update. If Cargo reports a conflict regarding links = "flint", some dependency still requires a 0.1 release of qFALL, see Versioning and Updates.

Building FLINT 3

What Changed

qfall-math is a memory-safe wrapper around the C-library FLINT. Until 0.1, it accessed FLINT through the crate flint-sys 0.7, which bundles the sources of FLINT 2.8.5. Since 0.2, it uses flint3-sys 3.6, which bundles the sources of FLINT 3.6 and generates its bindings with bindgen. qfall-math enables the feature gmp-mpfr-sys of flint3-sys, i.e. FLINT is built against the GMP and MPFR libraries provided by the crate gmp-mpfr-sys, as before.

We switched for the following reasons.

• FLINT 2.8 is outdated. FLINT 3 merged the libraries Arb, Antic, and Calcium into FLINT and received several years of performance improvements and bug fixes.
• flint3-sys follows the versioning of FLINT and generates its bindings from the FLINT headers. This enables an easier support of new FLINT releases.
• flint3-sys offers better cross-platform support of the build process.

What This Means for Your Build

The build requirements are unchanged: you need m4, make, and a C-compiler like gcc, see Installation.

• The first build recompiles FLINT. Artifacts of flint-sys in your target directory or CI caches cannot be reused. Depending on your hardware, the first build takes several minutes up to half an hour. Subsequent builds reuse the compiled FLINT version as before.
• Clean up old artifacts. The compiled FLINT version 2.8 remains in your target directory until you run cargo clean. This frees up about 80 MB per build profile and stale build.
• Invalidate CI caches. If your CI caches the target directory or ~/.cargo, the cache key should include Cargo.lock, so that it is rebuilt once after the update.
• Workarounds for gmp-mpfr-sys still apply. As FLINT is still built against gmp-mpfr-sys, the troubleshooting steps in Installation for compilation errors in gmp-mpfr-sys remain relevant.

Migrating Direct FLINT Usage

This section applies to you if you

• use unsafe getters and setters of qFALL to access the underlying FLINT structures, e.g. Z::get_fmpz, MatZ::get_fmpz_mat_struct, MatZq::get_fmpz_mod_mat_struct, or Modulus::get_fmpz_mod_ctx, or
• call FLINT functions via flint-sys in your own code, e.g. to use FLINT functionality that qFALL does not cover yet.

The names of all unsafe getters and setters of qFALL are unchanged, but they return and accept the types of flint3-sys now. Hence, your code has to move from flint-sys to flint3-sys as well.

Step 1: Replace the Dependency

[dependencies]
flint3-sys = "3.6"

The version requirement must be compatible with the one of qfall-math, i.e. 3.6. Otherwise, Cargo compiles two copies of FLINT, and the types of your copy do not match the types returned by qFALL.

Step 2: Flatten Your Imports

flint-sys organized its bindings in one module per FLINT header, e.g. flint_sys::fmpz or flint_sys::fmpz_mat. flint3-sys exports all bindings at the crate root. Rename the crate from flint_sys to flint3_sys and drop the module from each path.

Step 3: fmpz Is a Plain Integer Now

In flint-sys, fmpz was a tuple struct pub struct fmpz(pub slong). In flint3-sys, it is a type alias pub type fmpz = slong, i.e. an i64 on 64-bit platforms, which matches its definition in C. Wherever you constructed or destructured an fmpz, remove the wrapper.

The same applies to all structs that contain an fmpz, e.g. the fields num and den of fmpq. Keep in mind that the value of an fmpz is only the integer itself if it is smaller than 2^{62}. Large integers are stored as a tagged pointer, in FLINT 2.8 and in FLINT 3.6. Therefore, never interpret the raw value directly. Use FLINT functions like fmpz_get_si, or convert it into a Z. As fmpz is a plain i64 now, the compiler no longer prevents you from mixing it up with ordinary integers.

The following example writes an entry of a MatZ via FLINT and reads a small Z.

Step 4: Pass the Modulus Context Explicitly

FLINT 3 redesigned the fmpz_mod_* types around the modulus context fmpz_mod_ctx. This affects the internals of MatZq the most.

• For example, fmpz_mod_mat_struct is a type alias of fmpz_mat_struct now. It no longer has the fields mat and mod_, i.e. it does not store its modulus. Replace matrix.mat[0] by matrix, and obtain the modulus via MatZq::get_fmpz_mod_ctx.
• Almost all fmpz_mod_mat_* functions take a *const fmpz_mod_ctx_struct as additional last parameter. For example, fmpz_mod_mat_init(mat, rows, cols, n) took the modulus n as *const fmpz and now takes the context instead, and fmpz_mod_mat_set_entry(mat, i, j, val) became fmpz_mod_mat_set_entry(mat, i, j, val, ctx).

Some function signatures include minor differences between flint-sys and flint3-sys. However, most of them are self-explanatory to resolve.

Changed Signatures

Besides the FLINT types, the signatures of the following functions changed.

Initialization of Samplers

The init functions of the samplers in qfall_math::utils::sample take an additional last parameter seed: Option<[u8; 32]>. Pass None to keep the previous behavior.

use qfall_math::utils::sample::{
    binomial::BinomialSampler,
    discrete_gauss::{DiscreteGaussianIntegerSampler, LookupTableSetting},
    uniform::UniformIntegerSampler,
};
use qfall_math::integer::Z;

let mut uniform = UniformIntegerSampler::init(&Z::from(256), None).unwrap();

let mut binomial = BinomialSampler::init(4, 0.5, None).unwrap();

let mut gaussian =
    DiscreteGaussianIntegerSampler::init(0, 3, 6, LookupTableSetting::FillOnTheFly, None).unwrap();

The sampling functions of the data types, e.g. MatZq::sample_uniform, keep their signatures. Their seeded counterparts are new functions with the suffix _seeded.

MatZq::gaussian_elimination_prime

gaussian_elimination_prime borrows self instead of consuming it.

Behavior Changes

The following changes do not cause compiler errors. Search your code for the affected functions.

Zq::get_representative_least_absolute_residue

The function returned the absolute value of the least absolute residue in 0.1, e.g. 2 for 15 mod 17. It now returns the residue itself, i.e. -2, see Bug Fixes. If your code computes the distance of a value to 0, e.g. to decode an LWE ciphertext, add .abs() to preserve the previous result.

Reduced Samples of MatZq

MatZq::sample_discrete_gauss, MatZq::sample_binomial, and MatZq::sample_binomial_with_offset return entries in [0, q) now. If your code worked around this bug, e.g. by reducing the matrix explicitly, multiplying with another matrix, or by mapping negative entries, the workaround is no longer needed.

Debug Output

Zq, PolynomialRingZq, MatPolynomialRingZq, ModulusPolynomialRingZq, and the NTT types derive Debug now. Their Debug output is formatted differently and includes the internal FLINT structures of the modulus. Don’t compare Debug strings in tests. Use to_string(), which is unchanged, or compare the values directly.

Getting Help

If your project does not compile after following this guide, or you observe different results that are not explained here, please open an issue in the repository of the respective crate: qfall-math, qfall-tools, or qfall-schemes.