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.