G-Trapdoor

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_tools::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_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. G-trapdoors are also supported for rings. Feel free to check out the documentation of qFALL-crypto to see all supported functionality.