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.85 or newer. As we use flint-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 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 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.

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
• 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 + 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 from \({R}_q\) and the modulus \(q\) is also chosen appropriately.

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 an element in \({R}_{2}\) and back. Fortunately, qFALL-tools provides this functionality for arbitrary \({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 + 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.

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.