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.