Tutorial to Use qFALL Libraries

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

This tutorial shall give you a brief introduction on how to work with the software developed by qFALL. qFALL is a group of students developing a prototyping library for lattice cryptography organized by the Codes and Cryptography research group in Paderborn.

Our libraries are written in Rust, as well as the following examples. Thus, we require some experience with Rust and its concepts to properly understand the following sections. Otherwise, we recommend starting with some hands-on experience with Rust by reading the Rust book.

First, we start with a guide on how to install and add our libraries to your project.
Afterward, we briefly describe the central concepts of our two co-developed libraries.

The first one is our math-crate, which contains all the mathematical features required to implement lattice-based cryptography and more.
The second library, called crypto-crate, includes an overview of the cryptographic schemes and specific mathematical primitives for lattice-based cryptography available so far.
At the end, we present some more advanced features like benchmarking and serialization features, which are available in both crates.

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

Documentation

Since our projects documentation isn't yet published, there is no option to find it on Rust's library collection on crates.io. But you can see our documentation of the libraries if you have installed them. and run the following command in your command line:

To install one of our libraries, clone qfall/math and/or qfall/crypto from GitHub. To build the library, run the following command:

cargo build

To generate and open the documentation of the installed library, run this command:

cargo doc --open

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

Integration

If you want to include the math library in your own Rust project, you can include a link to our version on the dev branch in your Cargo.toml.

qfall-math = { git = "https://github.com/qfall/math", 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.

Furthermore, we provide several lattice-based constructions and mathematical primitives for convenient usage in our crypto library. These can be used in your project after adding the following text in your Cargo.toml.

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

A description and short list of features can be found in chapter 6.

Introduction

Welcome to the section Getting Started with qFALL-math. qFALL-math is a rust crate for fast number theory with arbitrarily large numbers. It builds upon FLINT and uses the FFI flint-sys to call methods from FLINT. This crate acts as an abstraction layer and takes over all worries regarding memory management. Additionally it provides an easy-to-use interface with easy-to-understand notation and a wide range of operations possible with the related data types.

The crate is a work in progress and will be expanded. If you are missing a feature, an operation or a datatype, feel free to open an issue so we can work on your request.

What does qFALL-math offer?

qFALL-math gives the mathematical foundation to build on. It does not implement cryptographic schemes. It offers several different number types, over which we give a basic overview in the following.

We divide all types into three categories integer, integer_mod_q and rational. Within these categories, we have defined several types:

• integer
  • integers \(\mathbb Z\) are called Z
  • matrices over integers \(\mathbb Z^{n\times m}\) are called MatZ
  • polynomials over integers \(\mathbb Z[X]\) are called PolyOverZ
  • matrices over polynomials over integers \(\mathbb Z[X]^{n \times m}\) are called MatPolyOverZ
• integer_mod_q
  • integers modulo a natural number \(\mathbb Z_q\) are called Zq
  • matrices over integers modulo a natural number \(\mathbb Z_q^{n\times m}\) are called MatZq
  • polynomials over integers modulo a natural number \(\mathbb Z_q[X]\) are called PolyOverZq
  • elements of a polynomial ring over integers modulo a natural number \(\mathbb Z_q[X]/\Phi(X)\) are called PolynomialRingZq, where \(\Phi(X)\) is a polynomial over X
  • matrices with elements of a polynomial ring over integers modulo a natural number \(\mathbb Z_q[X]/\Phi(X)^{n \times m}\) are called MatPolynomialRingZq
• rational
  • rationals \(\mathbb Q\) are called Q
  • matrices over rationals \(\mathbb Q^{n\times m}\) are called MatQ
  • polynomials over integers \(\mathbb Q[X]\) are called PolyOverQ

As this list may be extended and is already relatively long, we will not be able to cover all types in this tutorial. Anyway, our documentation provides examples for every function and should therefore make it easily applicable.

Who is this Section for

Anyone trying to implement code founded on basic number theoretic types. Anyone who wants to implement relatively fast code with reliable memory management.

How to Use this Section

Use this book as a starting point, not as an entire reference. It helps you to get familiar with qFALL-math, but not with Rust. If you are not familiar with Rust, we highly advise you to have a look into the Rust book to get to know the basics.

How is this Section structured?

1. qFALL-math basics: We show how to instantiate the three base types Z, Zq, Q and introduce some features and present some arithmetics.
2. qFALL-math advanced types: We present the more advanced types 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. qFALL-math beyond types: We implement some additional features we want to showcase, such as sampling elements from a certain type.
4. using qFALL-math: We show how qFALL-math can be used as a building block. Therefore, we implement some cryptographic schemes in a step-by-step tutorial.

qFALL-math basics

Rusts datatypes such as u64 and i64 are limited in the representable integers. For example, the following code causes an overflow:

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

The library allows it to work with arbitrarily large integers without having to worry about overflows and memory allocation. The most basic types are Z, Zq and Q. All can be instantiated from rust types, as well as from strings and also support all common arithmetic operations among other functionalities.

Instantiate basic types

Z, Zq and Q can be instantiated both from strings, as well as 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

A special role can be assigned to Zq, as it does not only contain a value but also a context object represented by its 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 modulus can be shared among different values and, if shared, reduces runtime and reduces storage usage.

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

Converting types

All reasonable types can be converted between one another, 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.

use qfall_math::integer::Z;

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

Printing your Results

You can print the values of operations using print! or println!, or convert them into strings with .tostring().

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().

qFALL-math advanced types

For all basic types Z, Zq and Q, there exists a matrix MatZ, MatZq and MatQ. They can be instantiated from strings or as zero matrices with their entries set manually with the functions set_entry(), set_row and set_column. There also exist polynomials like PolyZ, PolyZq and PolyQ, which can be instantiated from strings or as zero polynomials with their coefficients set manually with the function set_coeff(). Furthermore, we provide ring elements like PolynomialRingZq, which can be instantiated from strings or their components. Matrices, polynomials and rings support all common arithmetic operations, among other functionalities.

These three advanced types and their functionalities are presented in the following sections with examples of how to use them.

Instantiate advanced types

MatZ, MatZq and MatQ can be instantiated from strings or as 0 matrices.

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

    // instantiations using components
    let matz = MatZ::from(&matzq);
    let matq = MatQ::from(&matz);
}

PolyZ, PolyZq and PolyQ can be instantiated from strings and their components.

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

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

Manipulation of advanced types

Entries from matrices can be set manually with the functions set_entry(), set_row() and set_column(). Their entries/rows/columns can be swapped with the functions swap_entries()/swap_row()/swap_column(). Rows/Columns of matrices can be reversed with the functions reverse_rows()/reverse_columns() and sorted with the functions sort_by_rows()/sort_by_columns().

Coefficients of polynomials and ring elements can be set manually with the function set_coeff().

use qfall_math::{
    integer::{MatZ, PolyOverZ},
    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();
    let mut polyz = PolyOverZ::from_str("4  -1 0 1 1").unwrap();

    matz_1.set_entry(1, 2, 8).unwrap();
    matz_1.set_row(0, &matz_2, 1).unwrap();

    polyz.set_coeff(2, 6).unwrap();
}

Note that for all set_*() functions, there is a corresponding get_*() function.

MatZq, PolyZq, PolynomialRingZq and their Moduli

Just like Zq, the advanced types MatZq, PolyZq and PolynomialRingZq have special roles since they do not only contain a value but also a context object represented by their moduli. A modulus object is of type Modulus or in the case of a PolynomialRingZq of type ModulusPolynomialRingZq.

The modulus Modulus can be instantiated from a Z greater or equal to two, and the modulus ModulusPolynomialRingZq can be instantiated from a PolyZq.

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

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

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

Both moduli can be shared among different values and, if shared, reduce runtime and reduce storage usage, since only the reference counter goes up, and the modulus is not cloned.

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_1 = Zq::from((17, 42));
    let zq_2 = Zq::from((24, 42));

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

Matrices as Vectors

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. So a MatZ matrix with dimensions 1 x n is a row vector and a matrix with dimensions n x 1 a column vector. This property can be checked with the function is_vector().

use qfall_math::{
    integer::{MatPolyOverZ, MatZ},
    integer_mod_q::{MatPolynomialRingZq, ModulusPolynomialRingZq},
};
use std::str::FromStr;

fn vectors() {
    let vecz = MatZ::from_str("[[1/2,2,3/4]]").unwrap();
    let poly_vec = MatPolyOverZ::from_str("[[4  -1 0 1 1],[2  12 4]]").unwrap();
    let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 42").unwrap();
    let poly_ring_vec =
        MatPolynomialRingZq::from_poly_over_z_modulus_polynomial_ring_zq(&poly_vec, &modulus);

    let is_vector = vecz.is_vector();
    let is_vector = poly_vec.is_vector();
    let is_vector = poly_ring_vec.is_vector();

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

Note that matrices with dimensions 1 x 1 are seen as both row and column vectors.

Converting types

All reasonable types can be converted between one another, e.g. we can define a MatQ from a MatZ or a PolyQ from a PolyZ.

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

fn conversions() {
    let matz = MatZ::from_str("[[1,2],[3,4]]").unwrap();
    let matq = MatQ::from(&matz);

    let polyz = PolyOverZ::from_str("4  1 2 3 4").unwrap();
    let polyq = PolyOverQ::from(&polyz);
}

Arithmetics

All advanced types (except moduli) support basic arithmetics. Among these are multiplication, addition and subtraction.

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

fn basic_arithmetics() {
    let matq = MatQ::from_str("[[1/2,2,3/4],[4,5/10,6]]").unwrap();
    let polyz = PolyOverZ::from_str("4  -1 0 1 1").unwrap();
    let polyz_2 = PolyOverZ::from_str("4  -1 0 1 2").unwrap();
    let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 42").unwrap();
    let poly_ring = PolynomialRingZq::from((&polyz, &modulus));

    let add = &matq + &matq;
    let sub = &polyz_2 - &polyz;
    let mul = &poly_ring * &poly_ring;
}

Printing your Results

You can print the values of all advanced types with the print! or println! command or convert them into strings with .to_string().

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

fn print() {
    let matq = MatQ::from_str("[[1/2,2,3/4],[4,5/10,6]]").unwrap();
    let polyz = PolyOverZ::from_str("4  -1 0 1 1").unwrap();
    let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 42").unwrap();
    let poly_ring = PolynomialRingZq::from((&polyz, &modulus));

    // print them directly
    println!("{matq}");
    println!("{polyz}");
    println!("{modulus}");
    println!("{poly_ring}");

    // turn them into a string first
    let matq_string = matq.to_string();
    let polyz_string = polyz.to_string();
    let modulus_string = modulus.to_string();
    let poly_ring_string = poly_ring.to_string();

    println!("{}", matq_string);
    println!("{}", polyz_string);
    println!("{}", modulus_string);
    println!("{}", poly_ring_string);
}

qFALL-math beyond types

This chapter includes the presentation of some helpful additional features, which we believe will be helpful for a more complex use of qFALL-math.

Random Sampling

... according to the uniform distribution

Drawing uniform random samples is an inevitable part of modern and post-quantum cryptography. Thus, we provide this feature with cryptographically secure randomness.

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

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, uniform_sample_z is uniformly random sampled over the interval \( [-5, 4] \). The function returns an error if the specified interval does not include at least two integer values.

The sampling for Zq is a little easier to instantiate as sample_uniform samples uniformly over the interval \( [0, \text{modulus}-1] \) for the given modulus parameter.

Furthermore, it is possible to instantiate matrices uniformly at random. In these cases, the first two parameters specify the dimensions of the newly created matrix. All subsequent parameters determine - as is the case for the integer data types - the size of the interval over which sampling takes place.

let uniform_matz = MatZ::sample_uniform(2, 2, -5, 5)?;
let uniform_matzq = MatZq::sample_uniform(2, 2, 7);

All sampling is also available for all our polynomial (matrix) data types except PolyOverQ. Their instantiation looks similar to the ones presented above. Please, refer to the documentation to find specifics.

The random number generator used for instantiation of uniformly random bits is ThreadRng from Rust's rand-crate and considered to be cryptographically secure.

... according to the discrete Gaussian distribution

Discrete Gaussians are often required to instantiate lattice-based problems like Learning with Errors. Hence, we also support the instantiation of integer data types sampled according to the discrete Gaussian distribution.

let n = 1024;
let center = 0;
let s = 1;

let discrete_gauss_sample_z = Z::sample_discrete_gauss(&n, &center, &s)?;

let modulus = 7;
let discrete_gauss_sample_zq = Zq::sample_discrete_gauss(&modulus, &n, &center, &s)?;

The discrete Gaussian distribution is implemented via a rejection sampling algorithm called SampleZ from GPV08. This algorithm takes the security parameter n, a center, and the Gaussian parameter s to sample a value \( x \) according to the discrete Gaussian distribution over the interval \( [c - s \log n, c + s \log n] \cap \mathbb{Z} \). center defines the value with peak probability.

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 a center vector, which is \( 0 \) in our example. This center does not have to be a lattice point. The lattice to sample from must be specified via a basis.

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

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

... according to the binomial distribution

As discrete Gaussian sampling is expensive and usually not done in constant time, several schemes replace it by a similar binomial distribution. Thus, we offer binomial sampling for all of our data types as well.

let binomial_sample_z = Z::sample_binomial(5, 0.5)?;
let binomial_sample_zq = Zq::sample_binomial(3, 5, 0.5)?;

The last first two parameters denote the number of experiments n and probability p with which these experiments succeed. Any parameters preceding these, are specific to their type. For sampling with the center around a specific value like 0, qFALL offers sample_binomial_with_offset.

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

Building Blocks and Primitives

• Preimage Samplable Functions (PSF)
• Trapdoors
  • G-trapdoor incl. short basis
  • Ring-based G-trapdoor incl. short basis

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_crypto::construction::signature::{SignatureScheme, FDH};

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_crypto::construction::{
    hash::sha256::HashMatZq,
    signature::{SignatureScheme, FDH},
};
use qfall_crypto::primitive::psf::PSFGPV;
use qfall_math::{integer::MatZ, integer_mod_q::MatZq, rational::MatQ};

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>.

Building Blocks

An essential part of our library are building blocks. If you look at the construction of our signature schemes, they are built upon PSFs. These PSFs themselves can be used in various cases, e.g. for Identity-Based Encryptions. In this part, we will present some of our most important building blocks, namely G-trapdoors and PSFs and explain how they can be used to build cryptographic constructions.

G-trapdoors

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_crypto::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_crypto::sample::g_trapdoor::{
    gadget_classical::gen_trapdoor, gadget_parameters::GadgetParameters,
    short_basis_classical::gen_short_basis_for_trapdoor,
};
use qfall_math::integer_mod_q::MatZq;

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 Samplable Functions

Preimage samplable 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.

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 {
    }

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

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:

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.
    fn compute_mu_half(&self, message: impl Into<Z>) -> PolynomialRingZq {
        // ensure mu has at most n bits
        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
    }
}

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,
            &self.n,
            0,
            &self.alpha * &self.q.get_q(),
        )
        .unwrap();
        let b = sk * &a + e + mu_q_half;
        (a, b)
    }

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

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

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

        // 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)
    }

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:

impl PrivKRingLWE {
    pub fn secure128() -> 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 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.