qFALL-math

qFALL is a prototyping library for lattice-based constructions. This math-crate is a memory-safe wrapper of FLINT in Rust, which provides several additional features often used in lattice-based cryptography. This crate is the foundation of the qFALL project containing further crates for prototyping of lattice-based cryptography.

Quick-Start

First, ensure that you use a Unix-like distribution (Linux or MacOS). Setup WSL if you're using Windows. This is required due to this crate's dependency on FLINT. Then, make sure your rustc --version is 1.85 or newer.

Furthermore, it's required that m4, a C-compiler such as gcc, and make are installed.

sudo apt-get install m4 gcc make

Then, add you can add this crate to your project by executing the following command.

cargo add qfall-math

• Find further information on our website. Also check out qfall-tools and qfall-schemes.
• Read the documentation of this crate.
• We recommend our tutorial to start working with qFALL.

What does qFALL-math offer?

We would like to point out a few supported features which are specifically important for lattice-based cryptography.

• Uniform, discrete Gaussian, and binomial sampling
• Support of several norms
• Solving systems of linear equations
• Support of the Number-Theoretic Transform (NTT)

Furthermore, this crate simplifies the implementation of your prototype by supporting a wide range of functions such as tensor multiplication, serialisation, matrix concatenations and many more. Arithmetic operations, comparisons, and conversions are supported across several types. You can find all supported data-types below.

Integers

• Z: Represents $\mathbb Z$.
• MatZ: Represents matrices over $\mathbb Z$.
• PolyOverZ: Represents polynomials with coefficients over $\mathbb Z$.
• MatPolyOverZ: Represents matrices of polynomials with coefficients over $\mathbb Z$.

Integers mod q

• Zq: Represents $\mathbb Z_q$.
• MatZq: Represents matrices over $\mathbb Z_q$.
• PolyOverZq: Represents polynomials with coefficients over $\mathbb Z_q$.
• PolynomialRingZq: Represents quotient rings $\mathbb Z_q[X]/f(X)$.
• MatPolynomialRingZq: Represents matrices over quotient rings $\mathbb Z_q[X]/f(X)$.
• NTTPolynomialRingZq: Represents quotient rings $\mathbb Z_q[X]/f(X)$ in NTT form.
• MatNTTPolynomialRingZq: Represents matrices over quotient rings $\mathbb Z_q[X]/f(X)$ in NTT form.

Rationals

• Q: Represents $\mathbb Q$.
• MatQ: Represents matrices over $\mathbb Q$.
• PolyOverQ: Represents polynomials with coefficients over $\mathbb Q$.

Quick Example

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

let (n, m, q) = (256, 1024, 3329);
let (center, sigma) = (0.0, 8.0);

let mat_a = MatZq::sample_uniform(n, m, q);
let vec_s = MatZ::sample_uniform(n, 1, 0, 2).unwrap();
let vec_e = MatZ::sample_discrete_gauss(m, 1, center, sigma).unwrap();

// SIS-Instance: t = A * e mod q
let vec_t = &mat_a * &vec_e;

// LWE-Instance: b^T = s^T * A + e^T mod q
let vec_b = vec_s.transpose() * mat_a + vec_e.transpose();

Bugs

Please report bugs through the GitHub issue tracker.

Contributions

Contributors are:

• Marvin Beckmann
• Phil Milewski
• Sven Moog
• Marcel Luca Schmidt
• Jan Niklas Siemer

See Contributing for details on how to contribute.

Citing

Please use the following bibtex entry to cite qFALL.

TODO: Update to eprint

Dependencies

This project uses the C-based, optimized math-library FLINT. We tested our use of FLINT extensively to ensure that you can not introduce memory-leaks by using our library. If you need a function supported by FLINT that is not supported by this crate, we have created an unsafe passthrough to access and operate on FLINT's structs directly.

Furthermore, we utilized serde and serde_json to (de-)serialize objects to and from JSON. Last, but not least, our sampling algorithms use the rand-crate to generate uniformly random bits. An extensive list can be found in our Cargo.toml file.

License

This library is distributed under the Mozilla Public License Version 2.0. Permissions of this weak copyleft license are conditioned on making the source code of licensed files and modifications of those files available under the same license (or in certain cases, under one of the GNU licenses). Copyright and license notices must be preserved. Contributors provide an express grant of patent rights. However, a larger work using the licensed work may be distributed under different terms and without source code for files added to the larger work.