New Features in 0.2

qFALL-math

Seeded Sampling

Every sampling function in qfall-math now comes in two variants: the previously existing un-seeded sampler and a sampler that takes a seed on input to enable Known-Answer-Tests (KATs), i.e. experiments, tests, and benchmarks can be made reproducible via seeding.

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

let seed = [42; 32];

let mat_0 = MatZq::sample_uniform_seeded(3, 3, 17, seed);
let mat_1 = MatZq::sample_uniform_seeded(3, 3, 17, seed);
assert_eq!(mat_0, mat_1);

let e = Z::sample_discrete_gauss_seeded(0, 8, [7; 32]).unwrap();

The samplers in qfall_math::utils::sample, i.e. UniformIntegerSampler, DiscreteGaussianIntegerSampler, and BinomialSampler, accept an optional seed in their init functions. Inputting None selects a randomly chosen seed.

use qfall_math::{integer::Z, utils::sample::uniform::UniformIntegerSampler};

let mut sampler_0 = UniformIntegerSampler::init(&Z::from(256), Some([1; 32])).unwrap();
let mut sampler_1 = UniformIntegerSampler::init(&Z::from(256), Some([1; 32])).unwrap();
assert_eq!(sampler_0.sample(), sampler_1.sample());

// unseeded
let mut sampler = UniformIntegerSampler::init(&Z::from(256), None).unwrap();
let sample = sampler.sample();

Negation

The Neg trait is now implemented for owned values and references across all relevant datatypes. Hence, you can write -x instead of -1 * x.

use qfall_math::{integer::Z, integer_mod_q::MatZq};
use std::str::FromStr;

let a = Z::from(5);
assert_eq!(Z::from(-5), -&a);

let mat = MatZq::from_str("[[1, 2],[3, 0]] mod 7").unwrap();
assert_eq!(MatZq::from_str("[[6, 5],[4, 0]] mod 7").unwrap(), -mat);

Hamming Weight

All polynomial and matrix types provide hamming_weight, which returns the number of non-zero coefficients or entries.

use qfall_math::integer::{MatZ, PolyOverZ};
use std::str::FromStr;

let mat = MatZ::from_str("[[2, 3],[2, 0]]").unwrap();
assert_eq!(3, mat.hamming_weight());

let poly = PolyOverZ::from_str("4  0 -1 0 1").unwrap();
assert_eq!(2, poly.hamming_weight());

Least Absolute Residues for All Residue Class Types

get_representative_least_absolute_residue is now also implemented for PolyOverZq, PolynomialRingZq, and MatPolynomialRingZq. It returns the representative of each coefficient in [-⌊q/2⌋, ⌊q/2⌋] as an integer type, i.e. Z, MatZ, PolyOverZ, or MatPolyOverZ.

use qfall_math::{
    integer::{PolyOverZ, Z},
    integer_mod_q::{PolyOverZq, Zq},
};
use std::str::FromStr;

let value = Zq::from((15, 17));
assert_eq!(Z::from(-2), value.get_representative_least_absolute_residue());

let poly = PolyOverZq::from_str("3  1 16 9 mod 17").unwrap();
assert_eq!(
    PolyOverZ::from_str("3  1 -1 -8").unwrap(),
    poly.get_representative_least_absolute_residue()
);

Note that the behavior of Zq::get_representative_least_absolute_residue changed in this release, see Bug Fixes.

Changing the Modulus

The new functions change_modulus and change_q replace the modulus of an existing value in place. They take the representative of each coefficient in [0, q) and reduce it by the new modulus.

use qfall_math::integer_mod_q::{MatZq, PolynomialRingZq};
use std::str::FromStr;

let mut mat = MatZq::from_str("[[1, 15]] mod 17").unwrap();
mat.change_modulus(7);
assert_eq!(MatZq::from_str("[[1, 1]] mod 7").unwrap(), mat);

let mut poly = PolynomialRingZq::from_str("3  12 2 13 / 4  1 0 0 1 mod 17").unwrap();
poly.change_q(12);
assert_eq!("3  0 2 1 / 4  1 0 0 1 mod 12", poly.to_string());

This is handy for modulus switching and for compression techniques.

Further Additions

• norm_eucl returns the Euclidean norm as a Q for PolyOverZ, PolyOverZq, and PolynomialRingZq, complementing norm_eucl_sqrd.
• Factorization implements Debug.
• Debug is derived for Zq, PolynomialRingZq, MatPolynomialRingZq, ModulusPolynomialRingZq, and the NTT types now, which changes their Debug output, see How to Transition.
• All computations are performed by FLINT 3.6, which received several years of improvements and bug fixes since FLINT 2.8, see the FLINT history.

qFALL-tools

qfall-tools 0.2 contains no new features. It was updated to qfall-math 0.2 and flint3-sys, and it pins the minor versions of all its dependencies, see Bug Fixes.

qFALL-schemes

ML-DSA

qfall-schemes now contains MLDSA, a prototype of the module-lattice-based signature scheme standardized in FIPS 204, which is also known as Dilithium. It implements the SignatureScheme trait and comes with the three parameter sets of the standard.

use qfall_schemes::signature::{MLDSA, SignatureScheme};

// choose among MLDSA::ml_dsa_44(), MLDSA::ml_dsa_65() and MLDSA::ml_dsa_87()
let mut ml_dsa = MLDSA::ml_dsa_44();

let (pk, sk) = ml_dsa.key_gen();

let msg = String::from("Hello world!");
let signature = ml_dsa.sign(msg.clone(), &sk, &pk);

assert!(ml_dsa.vfy(msg, &signature, &pk));

The building blocks of ML-DSA are public as well, so that you can experiment with them in isolation or reuse them in your own prototypes: power2round, decompose, make_hint, use_hint (each also as a _coeff variant for a single coefficient), and modified_sample_in_ball.

Note that MLDSA is not supposed to be an implementation up to the specification of FIPS 204. It is implemented with certain levels of freedom and provides significantly more free variables to experiment with the prototype.