G-Trapdoor

\(\mathbf{G}\)-trapdoors are an important tool for creating trapdoors for lattices that are defined by uniformly looking matrices. We consider a modulus \(q = 2^k\) that is a power of two for simplicity. The gadget vector is then defined as \(\mathbf{g}^t = \begin{pmatrix}1 & 2 & 4 & 8 & \ldots & 2^k\end{pmatrix}\). Given any target \(u \in \mathbb{Z}_q\), its binary decomposition \(\mathbf{x}^t = \begin{pmatrix}u_0 & u_1 & \ldots & u_k\end{pmatrix}\) can be used as a solution for a linear equation \(\mathbf{g}^t \mathbf{x} = u\). This can be naturally extended to gadget matrices \(\mathbf{G} = \mathbf{I}_n \otimes \mathbf{g}^t\) and targets that are vectors.

A gadget matrix now becomes useful if a public matrix \(A \in \mathbb{Z}_q^{n \times m}\) has a \(\mathbf{G}\)-trapdoor matrix \(\mathbf{T} \in \mathbb{Z}^{m \times n \cdot k}\) such that \(\mathbf{A} \cdot \mathbf{T} = \mathbf{G}\).

For a linear equation of the form \(\mathbf{A x} = \mathbf{t}\), we can find a solution for \(\mathbf{Gy} = \mathbf{t}\) first. This solution implies that \(\mathbf{Ty}\) is a valid solution \(\mathbf{x}\) for the first equation.

How they could be implemented

We give a brief idea showing how a simple version of \(\mathbf{G}\)-trapdoor can be implemented using our libraries (our actual implementation is more general than the example here). A \(\mathbf{G}\)-trapdoor can be implemented by sampling a uniform matrix \(\mathbf{\bar{A}}\) and a short trapdoor matrix \(\mathbf{R}\) from, e.g., the binomial distribution with \(p=0.5\) and two trials and centered around \(0\). The first step in the process of generating a gadget trapdoor is the generation of the gadget matrix itself:

use qfall_math::{
    integer::{MatZ, Z},
    traits::{MatrixDimensions, MatrixSetEntry, Tensor},
};

fn gen_gadget_mat(n: i64, k: i64, base: &Z) -> MatZ {
    // get g^t
    let gadget_vec = gen_gadget_vec(k, base).transpose();
    // instantiate I_n
    let identity_mat = MatZ::identity(n, n);
    // return G = I_n ⊗ g^t
    identity_mat.tensor_product(&gadget_vec)
}

fn gen_gadget_vec(k: i64, base: &Z) -> MatZ {
    let mut entry = Z::ONE;
    let mut out = MatZ::new(k, 1);
    for i in 0..out.get_num_rows() {
        out.set_entry(i, 0, &entry).unwrap();
        entry *= base
    }
    out
}

Next, sample a uniform matrix \(\mathbf{\bar{A}}\) and a trapdoor \(\mathbf{R}\). The matrix \(\begin{bmatrix}\mathbf{\bar{A}} & \mathbf{G} - \mathbf{\bar{A} R}\end{bmatrix}\) now has a gadget trapdoor: \(\begin{bmatrix}\mathbf{R}^t & \mathbf{I}\end{bmatrix}^t\).

use qfall_math::traits::{Concatenate, Tensor};
use qfall_math::{
    error::MathError,
    integer::{MatZ, Z},
    integer_mod_q::MatZq,
    traits::Pow,
};
use qfall_tools::sample::g_trapdoor::gadget_classical::gen_gadget_vec;

fn gen_trapdoor(n: u32, m: u32, k: u32) -> Result<(MatZq, MatZ), MathError> {
    let base = Z::from(2);
    let q = base.pow(k)?;

    let a_bar = MatZq::sample_uniform(n, m, q);
    let g_t = gen_gadget_vec(k, &base).transpose();
    let identity_n = MatZ::identity(n, n);
    // G = I \otimes g^t
    let g_mat = identity_n.tensor_product(&g_t);
    let r = MatZ::sample_binomial_with_offset(n, m, -1, 2, 0.5)?;

    // set A = [A_bar | G - A_bar R]
    let a = a_bar.concat_horizontal(&(g_mat - (&a_bar * &r)))?;
    Ok((a, r))
}

Our Implementation

We abstracted these implementation steps for you by providing a more general implementation of the above. It can be found in qfall_tools::sample::g_trapdoor using the following API. A matrix and a trapdoor can be generated together with some default parameters as:

use qfall_tools::sample::g_trapdoor::gadget_default::gen_trapdoor_default;

fn generate_trapdoor() {
    let (a, t) = gen_trapdoor_default(128, u32::MAX);
}

\(\mathbf{G}\)-trapdoors can be used for all sorts of constructions, such as signature and identity-based encryption schemes. These often utilize so-called tags, denoted by an invertible matrix \(\mathbf{H}\) to satisfy the slightly altered equation \(\mathbf{A} \cdot \mathbf{T} = \mathbf{H} \cdot \mathbf{G}\). Thus, our implementation also enables the use of tags with \(\mathbf{G}\)-trapdoors.

Another useful trapdoor for lattices is given by a short basis of that lattice. Given a \(\mathbf{G}\)-trapdoor for a matrix \(\mathbf{A}\), one can create a short base for \(\Lambda_q^\perp(\mathbf{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. \(\mathbf{G}\)-trapdoor are also supported for rings. Please refer to the documentation of qFALL-tools to find all details.