Introduction to the qFALL Prototyping Library

by Marvin Beckmann, Phil Milewski, Sven Kilian Moog, Marcel Luca Schmidt, and Jan Niklas Siemer.

This book serves as a technical tutorial and reference guide for working with the qFALL Prototyping Library for Lattice Cryptography.

The library is written in Rust, leveraging its performance and memory safety guarantees. Therefore, we assume the reader has prior experience with the fundamental concepts of Rust. If you are new to the language, we highly recommend reading The Rust Programming Language book first. The qFALL libraries leverage a foreign function interface (FFI) to the highly-optimized C-library FLINT.

The qFALL library is architecturally designed into separate components that ensure modularity, usability, and performance. This documentation will guide you through the following structure:

How to use qFALL in Research

The qFALL prototyping libraries are explicitly designed to accelerate academic and industrial research into lattice-based cryptography. Our central objective is to provide an implementation environment that minimizes friction between theoretical work and practical code. This is achieved through research-close notation (using qFALL-maths’s mathematically intuitive types) and a well-defined collection of building blocks (in qFALL-schemes) that abstract complex primitives like trapdoors and samplers. This modular structure makes it easy to construct cryptographic schemes using high-level components and enables easy, one-by-one replacement of functions (e.g., swapping a reference Gaussian sampler for a highly optimized, constant-time version) without altering the surrounding scheme logic. This flexibility drastically speeds up the prototyping cycle, allowing researchers to rapidly test and benchmark different algorithmic components and parameter sets before fixing a specific optimized algorithm for the final implementation.

How to Use this Book

This book is just starting point, and not an entire reference. It helps you to get some familiarity with qFALL-math, but not with Rust (we advise Rust book for Rust basics).

Book Structure and Content

1. Installation and Setup:
   • A guide on how to install the required dependencies and add our libraries to your new or existing Rust project.
2. The Mathematical Foundation (qFALL-math):
   • This section details our lowest-level component. It includes all the arbitrary-precision mathematical features required for lattice-based cryptography, such as integer arithmetic, quotient rings (\(\mathbb{Z}_q\)), and polynomial ring operations. We cover its relationship with the underlying highly-optimized FLINT C library.
3. The Cryptographic Tools (qFALL-tools):
   • This component acts as the bridge between the foundational math and the schemes. It includes essential cryptographic primitives and interfaces, 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 (often referred to as the crypto-crate) provides an overview of the explicit, high-level cryptographic constructions available, such as signature schemes and encryption algorithms, built using the components from qFALL-math and qFALL-schemes.
5. Shared Features:
   • A guide to advanced utilities available across the entire library suite, including benchmarking facilities, serialization features, and external interoperability.

Contributing

License

Installation

To use this project, you need to have an installation of Rust. Since we are using flint-sys which itself uses gmp, we are currently restricted to usage on Mac, Linux and Linux subsystems under Windows. For a subsystem under Windows, you are additionally required to have installed m4 and a C-compiler like gcc. Furthermore, make sure to have make installed.

Command for installing m4, gcc, and make:

sudo apt-get install m4 gcc make

Integration

You can integrate our libraries via crates.io (not supported yet, as we have not published it here yet) or you can get the latest version directly 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-schemes = { git = "https://github.com/qfall/schemes", branch="dev" }
qfall-tools = { git = "https://github.com/qfall/tools", branch="dev" }

Be aware that the external libraries in our projects have to be compiled at the first installation, which may take about 10-30 minutes (depending on the used hardware and operating system). After the first installation, it should be working fine.

Documentation

You can find our documentations on crates.io (not supported yet, as we have not published it here yet) or you can build the latest documentation locally. Once you have integrated the desired library, you can build the project and open the documentation of the entire project. This includes our libraries for which you can then check the respective documentation.

cargo build
cargo doc --open

If you’re using WSL and your browser does not open, retry after installing wslu (this helped for us).

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 description 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, arbitrarily-precise 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 flint-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. (See Safety Guarantees for more details.)

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 maximum 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 memory management prevents memory leaks. The memory management of the underlying FLINT objects is abstracted away from the user and handled in a memory safe way. We have additional dedicated error handling that provides developers with more information when errors occur. These errors also differentiate different types of errors which should help while debugging.

Supported Mathematical Types

The qFALL-math library 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, Q and introduce some features and present some arithmetics.
2. Complex Structures: We present the more advanced types like MatZ, PolyZ, PolynomialRingZq and give some intuition on how they work, as all similar types also behave similarly, this allows you to figure out how to use the others.
3. NTT: We consider how values of PolynomialRingZq can be represented differently (using the NTT-transform) for more efficient multiplication.

Basic Types

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

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

qFALL-math works with arbitrarily large integers and the user can work with them without needing to consider potential overflows and execution failures.

Instantiate basic types

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));
    let q = Q::from((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.

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

fn instantiate_modulus() {
    let z = Z::from(42);
    let modulus = Modulus::from(&z);

    let modulus = Modulus::from(42);
}

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

use qfall_math::{
    integer::Z,
    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));
}

Each Modulus has a reference counter hidden behind them. Therefore, if a Modulus is cloned, this only allocates another pointer to the underlying object, making it efficient to store a Z and a Modulus together. Storing them together has 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 arithmetics

All types support basic arithmetics. Among them are multiplication, addition and subtraction. Opposed to what is typical Rust behavior, we natively support operations between different types, e.g., Z and Q, as there is a mathematical reasonable output of Q that can be expected, and as we are working with arbitrarily large values, no memory leaks or rounding can occur.

use qfall_math::integer::Z;
use qfall_math::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;

    let add: Q = &z_1 + Q::from((1, 2));
}

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}");

    // turn it into a string first
    let zq_string = zq.to_string();
    println!("{}", zq_string)
}

Error Handling

In our math crate, we have one file error.rs, containing all our 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 where errors are easily visible, like “division by zero” errors, we do not propagate the error but panic instead. That is to evade unnecessary uses of unwrap().

Complex Structures

Rather than saving Vec<Zq> or Vec<Vec<Zq>> to represent vectors/polynomials and matrices, qFALL-math has explicit struct with explicitly implemented functionalities that simplify prototyping.

Matrices

Each base type (Z, Q, Zq) has a matrix version (MatZ, MatQ, MatZq) that can be instantiated from strings or as the all 0 matrix.

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

fn matrix_instantiations() {
    // instantiations using new
    // the first number is the number of rows and the second one the number of columns
    let matz = MatZ::new(5, 10);
    let matzq = MatZq::new(5, 10, 13);
    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();

    // explicitly converting between different 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, … For ease of-usage, these functions also have 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();
}

We do not have explicit vector types like VecZ, VecZq and VecQ, but all matrices can serve as vectors if they have the correct dimensions. On vectors (e.g., a MatZ matrix with dimensions 1 x n) can be used as a normal vector, so you can for instance compute different norms and dot products.

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_sqrd();
}

Assuming matching dimensions, arithmetic operations between different types of matrices are well-defined and supported naturally. Beyond matrix-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 between different matrices.

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 is slightly different, as the string format is imported from FLINT reducing 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 have defined ModulusPolynomialRingZq, which can be shared among different instantiations.

use qfall_math::integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq};
use std::str::FromStr;

fn instantiate_moduli() {
    let polyzq = PolyOverZq::from_str("4  1 0 0 1 mod 17").unwrap();
    let modulus_poly = ModulusPolynomialRingZq::from(&polyzq);
}

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 is likely not fully understandable.

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 the NTT transform, 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 on the developer.

use crate::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 (like the one from ML-KEM) is desirable. Refer to the contribution details in case you want to extend the crates.

Random Sampling

An essential part of lattice-based cryptography are random values sampled according to specific distributions. qfall-math provides functions to sample from the following distributions efficiently and conveniently. The samplers themselves are implemented in utils::sample.

Uniform Distribution

Drawing uniform random samples 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 * s, c + 6 * s] \cap \mathbb{Z} \). center defines the value(s) with peak probability. The tailcut is chosen as 6 per convention and can be changed here: qfall_math::utils::sample::discrete_gauss::TAILCUT.

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 similar binomial distribution.

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.

Building Blocks

Building on top off 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.

G-Trapdoor

G-trapdoors are an important tool for creating trapdoors for lattices that are defined by uniformly looking matrices.

A G-trapdoor is a matrix \(T \in \mathbb{Z}^{m \times n \cdot k}\) for a matrix \(A \in \mathbb{Z}_q^{n \times m}\) such that \(A \cdot T = G\) where \(G\) is a gadget matrix. Such a matrix \(A\) and a trapdoor can be generated together:

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

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

G-trapdoors can be used for all sorts of constructions, such as signature schemes and identity-based encryptions, and are created using dedicated tags (here \(A \cdot T = H \cdot G\) where \(H\) is the invertible tag). For lattices, a useful trapdoor is given by a short basis. Given a G-trapdoor for a matrix \(A\), one can create a short base for \(\Lambda^\perp(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. G-trapdoors are also supported for rings. Feel free to check out the documentation of qFALL-crypto to see all supported functionality.

Preimage Sampleable Functions

Preimage sampleable functions are a cryptographic construction that can be used for cryptographic constructions such as signatures and identity-based encryptions. We have implemented a trait to mimic the functionality of a PSF. There are two explicit implementations of a PSF, one of which is constructed using G-trapdoors classically, and one is constructed using ring-variants. Check out qFALL-crypto to see the implementations and how we used them to create signature schemes and identity-based encryptions.

TODO: Add something about the perturbation sampling and more specific mentioning of the content. An example is probably also nice.

Features

We briefly present a list of implemented features in our crypto-crate. Afterwards, we provide a brief overview for each type of feature such that you can conveniently build upon them. A tutorial on how to use this crate in your own project can be found in chapter 1.

Full-fledged Cryptographic Features

• Public Key Encryption
  • LWE Encryption
  • Dual LWE Encryption
  • LPR Encryption
  • Ring-based LPR Encryption
• Identity Based Encryption
  • Dual LWE Encryption (Identity-Based)
• Signatures
  • Full-Domain Hash (FDH) / Probabilistic FDH (PFDH)
  • Ring-based FDH
• Hash Functions
  • SIS-Hash Function

TODO: list the new implementations

Encryption

Public Key Encryption

The implemented lattice-based public key encryption schemes can be found in the module qfall_crypto::constructions::pk_encryption. All of them implement the trait PKEncryption and thus the functions gen, enc, and dec for the key generation, encryption and decryption according to some public parameters, which are stored in the struct of each implemented scheme. Although not mandatory, currently all schemes provide functions to generate suitable public parameters via new_from_n(n) for some provided n, a default parameter set, and a static set of public parameters, which is 128-bit secure via secure128(). Nevertheless, you can also check your public parameters for provable security and correctness via check_security and check_correctness. Please note that these functions are not mandatory to implement. Hence, schemes added in the future might not provide this functionality.

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

use qfall_crypto::construction::pk_encryption::{PKEncryption, LPR};

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

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

Unfortunately, we can only encrypt one bit in the provided example. Thus, 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_crypto::construction::pk_encryption::{GenericMultiBitEncryption, PKEncryption, LPR};

// setup public parameters and generate key-pair
let scheme = LPR::default();
let (pk, sk) = scheme.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, can encrypt multiple bits at once, and is more efficient, as it is based on ideal lattices and with that polynomial rings. In this case, multiple bits can be encrypted at once with respect to the choice of n.

Signatures

The implemented lattice-based signature schemes can be found in the module qfall_crypto::constructions::signature. All of them implement the trait SignatureScheme and thus the functions gen, sign, and vfy for the key generation, signing and verification according to some public parameters, which are stored in the struct of each implemented scheme.

With the provided functionality, it is easy to setup a scheme, and sign and verify messages:

use qfall_schemes::signature::SignatureScheme;

fn signing_and_verifying() {
    // setup public parameters and generate key-pair
    let mut fdh = FDH::init_gpv(10, 512, 42);
    let (pk, sk) = fdh.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))
}

The signature schemes we have implemented are FDH and PFDH signature schemes that build upon any kind of PSF. We have implemented a general implementation of FDH and PFDH, such that instantiation with any valid PSF and correspondingly chosen parameters directly yields a valid signature scheme.

As the FDH signature scheme is stateful and requires storage, the signature scheme must also be serializable. As the combination of

• an implementation that is as general as possible
• an implementation that is serializable

is quite hard to do in code, you might see some types called PhantomData. This is only used for type-binding of the correspondingly used PSF and does not take any memory or appears in the serialization of the signature scheme.

A serialization looks as follows:

use qfall_math::{integer::MatZ, integer_mod_q::MatZq, rational::MatQ};
use qfall_tools::primitive::psf::PSFGPV;

fn serialize_and_deserialize() {
    // setup public parameters and generate key-pair
    let mut fdh = FDH::init_gpv(10, 1024, 42);
    let (pk, sk) = fdh.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: FDH<MatZq, (MatZ, MatQ), MatZ, MatZq, PSFGPV, HashMatZq> =
        serde_json::from_str(&fdh_string).unwrap();
}

The part FDH<MatZq, (MatZ, MatQ), MatZ, MatZq, PSFGPV, HashMatZq> might look a little irritating at first. Our implementation for a signature scheme is as general as possible, hence each implementation of an FDH signature scheme uses the same FDH struct, only with different parameters. The parameters <MatZq, (MatZ, MatQ), MatZ, MatZq, PSFGPV, HashMatZq> define the corresponding PSF and hash function used for the signature scheme. Looking at the documentation in the crypto crate this might become clearer FDH<A, Trapdoor, Domain, Range, T: PSF<A, Trapdoor, Domain, Range>, Hash: HashInto<Range>>. Each parameter determines the kind of signature scheme that is implemented. For the ring-based FDH signature scheme, we have FDH<MatPolynomialRingZq, (MatPolyOverZ, MatPolyOverZ), MatPolyOverZ, MatPolynomialRingZq, PSFGPVRing, HashMatPolynomialRingZq> which follows the same principle.

This idea was also applied to the PFDH signature scheme where the classical implementation follows the same pattern PFDH<MatZq, (MatZ, MatQ), MatZ, MatZq, PSFGPV, HashMatZq>.

Implementing Crypto

In the next section we provide a hands-on tutorial on how to implement a cryptographic scheme. 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 with which you can display the entire documentation. Press it to see the solution.

Private Key Encryption Scheme - Ring-LWE

We give the procedure of defining a private key encryption scheme based on ring-LWE.

Firstly, we look at the formal definition of the scheme we will implement:

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

• \(sk \leftarrow Gen(1^n): sk \leftarrow R_q\)
• \((a, b) \leftarrow Enc(sk, m): \text{ where } m \in R_{0,1}, a \leftarrow R_q, e \leftarrow \chi, b:= sk \cdot a + e + m\)
• \(m \leftarrow 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 from \(R_q\) and the modulus \(q\) is also chosen appropriately.

Finding the correct Trait

In order to implement a scheme, first identify the commonly shared functionality between each scheme of that category. Here, this is easy, as it is the formal definition of a private key encryption scheme:

• \(sk \leftarrow Gen(1^n)\) generate a private key for encryption
• \(c \leftarrow Enc(sk, m):\) encrypt the message
• \(m \leftarrow Dec(sk, c):\) decrypt the message

Now try to make a trait out of this:

// The trait is still missing the above described functionalities, try to add them
// manually

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

    /// Generates a secret key that can be used for encryption and decryption.
   fn 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

Now we want to implement the trait for our previously defined struct.

// The structure, now we only have to fill out each algorithm individually

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

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

    fn enc(&self, sk: &Self::SecretKey, message: &Z) -> Self::Cipher {
        let q_half = self.q.get_q().div_floor(2);

        // check for each coefficient whether it's closer to 0 or q/2
    fn compute_mu_half(&self, message: impl Into<Z>) -> PolynomialRingZq {
        // ensure mu has at most n bits

For the generation algorithm we have to implement

• \(sk \leftarrow Gen(1^n): sk \leftarrow R_q\) which corresponds to:

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

Now we have to implement the encryption. You might have realized that as input for the scheme we have chosen an integer rather than a value of \(R*{0,1}\), this was mainly due to practicability, but we need a way to transform an integer into an element in \(R*{0,1}\). Use the following function for the transformation:

        let message: Z = message.into().abs();
        let mu = message.modulo(Z::from(2).pow(&self.n).unwrap());
        // set mu_q_half to polynomial with n {0,1} coefficients
        let bits = mu.to_bits();
        let mut mu_q_half = PolynomialRingZq::from((PolyOverZ::default(), &self.q));
        let q_half = self.q.get_q().div_floor(2);
        for (i, bit) in bits.iter().enumerate() {
            if *bit {
                mu_q_half.set_coeff(i, &q_half).unwrap();
            }
        }

        mu_q_half
    }
}

impl PrivKRingLWE {
    pub fn secure128() -> Self {
        Self::new(512, 92897729, 0.000005)
    }

For the encryption algorithm we have to implement

• \((a, b) \leftarrow Enc(sk, m): \text{ where } m \in R_{0,1}, a \leftarrow R_q, e \leftarrow \chi, b:= sk \cdot a + e + m\) which corresponds to (note that for the error distribution you can sample from a discrete gauss):

    fn enc(&self, sk: &Self::SecretKey, message: &Z) -> Self::Cipher {
        let mu_q_half = self.compute_mu_half(message);
        let a = PolynomialRingZq::sample_uniform(&self.q);
        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)
    }
    fn dec(&self, sk: &Self::SecretKey, (a, b): &Self::Cipher) -> Z {

        let q_half = self.q.get_q().div_floor(2);

Now it only remains to decrypt the message. At this point this should probably be the easiest part, so we provide the solution directly:

        // check for each coefficient whether it's closer to 0 or q/2
        // if closer to q/2 -> add 2^i to result
        let mut vec = vec![];
        for i in 0..self.q.get_degree() {
            let coeff = Zq::from((result.get_coeff(i).unwrap(), self.q.get_q()));
            if coeff.distance(&q_half) < coeff.distance(Z::ZERO) {
                vec.push(true);
            } else {
                vec.push(false);
            }
        }

        Z::from_bits(&vec)
    }
}

impl PrivKRingLWE {
    /// Turns a [`Z`] instance into its bit representation, converts this bit representation
    /// into a [`PolynomialRingZq`] with entries q/2 for any 1-bit and 0 as coefficient for any 0-bit.

Choosing Parameters and using the Scheme

Now we only have to use a set of parameters and we can use our construction. This could look as follows:

    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 mut q = PolyOverZq::from((1, q));
        q.set_coeff(&n, 1).unwrap();
        let q = ModulusPolynomialRingZq::from(&q);

        let alpha: Q = alpha.into();

        Self { n, q, alpha }
    }
}

and can then be used to encrypt and decrypt messages:

    fn enc_and_dec() {
        let message = Z::from(17);
        let scheme = PrivKRingLWE::secure128();

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

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

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 (!Watch out for the criterion version, as of writing this, the book is not on the latest version!)

Commands

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

Flamegraphes provide insights into where execution time is spent.

Details can be found here:

• Flamegraph GitHub.

Installation

Installing Flamegraph in Linux and macOS is easy, since you only need to install flamegraph. But in WSL you need some more steps, since you need to install “perf” manually.

So after cargo install flamegraph, you need to update “apt” with sudo apt update and install “build-essential’s” by 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 ~ and install the linux kernel with
wget - https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.15.5.tar.xz (Adjust the version as needed).
After that you extract it with tar -xvf linux-5.15.5.tar.xz and move into “perf” with cd linux-5.15.5/tools/perf there you use make to compile it. The last step is to make “perf” visible by e.g. sudo cp ./perf /usr/local/bin/.

Command

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 the 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 the function you are looking for is to search for it with Ctrl + F. You have to 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 our qFALL-math supports serialization and deserialization using serde_json.

use qfall_math::integer::Z;

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

    let string = serde_json::to_string(&int).unwrap();
    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,
}

That allows for immediate serialization and deserialization of newly created constructions. Serialization is also implementable for more complicated structs. In qFALL-crypto we also utilized typetags that allow for easy serialization and deserialization of traits or, more precisely, the structs implementing the trait.