use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha20Rng;
use spiral_rs::poly::{
automorph_alloc, from_ntt_alloc, to_ntt_alloc, PolyMatrix, PolyMatrixNTT, PolyMatrixRaw,
};
use std::collections::HashMap;
use crate::params::RlweParams;
pub const G: u64 = 5;
#[must_use]
pub const fn h(d: usize) -> u64 {
(2 * d as u64) - 1
}
#[must_use]
pub fn tau_g_pow(j: usize, d: usize) -> u64 {
let modulus = 2 * d as u64;
let mut acc = 1_u64;
let mut base = G % modulus;
let mut exp = j;
while exp > 0 {
if exp & 1 == 1 {
acc = (u128::from(acc) * u128::from(base) % u128::from(modulus)) as u64;
}
base = (u128::from(base) * u128::from(base) % u128::from(modulus)) as u64;
exp >>= 1;
}
acc
}
pub fn tau_raw<'a>(a: &PolyMatrixRaw<'a>, t: u64) -> PolyMatrixRaw<'a> {
automorph_alloc(a, t as usize)
}
#[derive(Clone)]
pub struct NttAutomorphTable {
exponent: u64,
indices: Box<[u32]>,
}
impl NttAutomorphTable {
pub(crate) fn from_prepared(exponent: u64, indices: Box<[u32]>, d: usize) -> Option<Self> {
let table = Self { exponent, indices };
table.validate_permutation(d).then_some(table)
}
#[must_use]
pub fn exponent(&self) -> u64 {
self.exponent
}
#[must_use]
pub fn indices(&self) -> &[u32] {
&self.indices
}
#[must_use]
fn new_checked(exponent: u64, indices: Box<[u32]>, d: usize) -> Self {
let table = Self { exponent, indices };
assert!(
table.validate_permutation(d),
"NTT automorphism table for exponent {exponent} is not a permutation of 0..{d}; \
the packing hot loop's index masking depends on this invariant"
);
table
}
pub fn validate_permutation(&self, d: usize) -> bool {
if self.indices.len() != d {
return false;
}
let mut seen = vec![false; d];
for &index in self.indices.iter() {
let index = index as usize;
if index >= d || seen[index] {
return false;
}
seen[index] = true;
}
true
}
}
#[must_use]
pub fn ntt_automorph_table(params: &RlweParams, exponent: u64) -> NttAutomorphTable {
let two_d = 2 * params.d as u64;
let exponent = exponent % two_d;
assert!(
exponent % 2 == 1,
"automorphism exponent must be odd modulo 2d"
);
for attempt in 0..16_u64 {
let mut rng = ChaCha20Rng::seed_from_u64(0xA770_0000 + attempt);
let probe_a = PolyMatrixRaw::random_rng(¶ms.spiral, 1, 1, &mut rng);
let probe_b = PolyMatrixRaw::random_rng(¶ms.spiral, 1, 1, &mut rng);
let probe_a_ntt = to_ntt_alloc(&probe_a);
let probe_b_ntt = to_ntt_alloc(&probe_b);
let auto_a_ntt = to_ntt_alloc(&tau_raw(&probe_a, exponent));
let auto_b_ntt = to_ntt_alloc(&tau_raw(&probe_b, exponent));
if let Some(indices) =
match_probe_slots(params, &probe_a_ntt, &probe_b_ntt, &auto_a_ntt, &auto_b_ntt)
{
return NttAutomorphTable::new_checked(exponent, indices, params.d);
}
}
panic!("failed to build collision-free NTT automorphism table");
}
#[must_use]
pub fn tau_g_power_tables(
params: &RlweParams,
count: usize,
) -> (Vec<NttAutomorphTable>, Vec<NttAutomorphTable>) {
let two_d = 2 * params.d as u64;
let g_table = ntt_automorph_table(params, G % two_d);
let h_table = ntt_automorph_table(params, h(params.d));
let mut current = identity_table(params);
let mut left = Vec::with_capacity(count);
let mut right = Vec::with_capacity(count);
for _ in 0..count {
left.push(current.clone());
right.push(compose_tables(
params,
¤t,
&h_table,
(current.exponent * h_table.exponent) % two_d,
));
current = compose_tables(
params,
¤t,
&g_table,
(current.exponent * g_table.exponent) % two_d,
);
}
(left, right)
}
pub fn apply_tau_ntt_into<'a>(
out: &mut PolyMatrixNTT<'a>,
input: &PolyMatrixNTT<'a>,
table: &NttAutomorphTable,
) {
assert_eq!(out.rows, input.rows);
assert_eq!(out.cols, input.cols);
assert_eq!(out.params.poly_len, input.params.poly_len);
assert_eq!(table.indices.len(), input.params.poly_len);
let d = input.params.poly_len;
for row in 0..input.rows {
for col in 0..input.cols {
let input_poly = input.get_poly(row, col);
let out_poly = out.get_poly_mut(row, col);
for (input_chunk, out_chunk) in
input_poly.chunks_exact(d).zip(out_poly.chunks_exact_mut(d))
{
for (dst_idx, src_idx) in table.indices.iter().enumerate() {
out_chunk[dst_idx] = input_chunk[*src_idx as usize];
}
}
}
}
}
#[must_use]
pub fn apply_tau_ntt_alloc<'a>(
input: &PolyMatrixNTT<'a>,
table: &NttAutomorphTable,
) -> PolyMatrixNTT<'a> {
let mut out = PolyMatrixNTT::zero(input.params, input.rows, input.cols);
apply_tau_ntt_into(&mut out, input, table);
out
}
pub fn apply_tau_ntt_double_into<'a>(
out_left: &mut PolyMatrixNTT<'a>,
out_right: &mut PolyMatrixNTT<'a>,
input: &PolyMatrixNTT<'a>,
left_table: &NttAutomorphTable,
right_table: &NttAutomorphTable,
) {
assert_eq!(out_left.rows, input.rows);
assert_eq!(out_left.cols, input.cols);
assert_eq!(out_right.rows, input.rows);
assert_eq!(out_right.cols, input.cols);
assert_eq!(left_table.indices.len(), input.params.poly_len);
assert_eq!(right_table.indices.len(), input.params.poly_len);
let d = input.params.poly_len;
for row in 0..input.rows {
for col in 0..input.cols {
let input_poly = input.get_poly(row, col);
let left_poly = out_left.get_poly_mut(row, col);
let right_poly = out_right.get_poly_mut(row, col);
for ((input_chunk, left_chunk), right_chunk) in input_poly
.chunks_exact(d)
.zip(left_poly.chunks_exact_mut(d))
.zip(right_poly.chunks_exact_mut(d))
{
for dst_idx in 0..d {
left_chunk[dst_idx] = input_chunk[left_table.indices[dst_idx] as usize];
right_chunk[dst_idx] = input_chunk[right_table.indices[dst_idx] as usize];
}
}
}
}
}
pub fn tau_ntt<'a>(a: &PolyMatrixNTT<'a>, t: u64) -> PolyMatrixNTT<'a> {
to_ntt_alloc(&tau_raw(&from_ntt_alloc(a), t))
}
pub fn trace<'a>(p: &PolyMatrixRaw<'a>) -> PolyMatrixRaw<'a> {
let d = p.params.poly_len;
let two_d = 2 * d as u64;
let h_d = h(d);
let mut out = PolyMatrixRaw::zero(p.params, p.rows, p.cols);
for j in 0..(d / 2) {
let gj = tau_g_pow(j, d);
let left = tau_raw(p, gj);
let right = tau_raw(p, (gj * h_d) % two_d);
add_assign_raw_mod(&mut out, &left);
add_assign_raw_mod(&mut out, &right);
}
out
}
fn add_assign_raw_mod(out: &mut PolyMatrixRaw<'_>, rhs: &PolyMatrixRaw<'_>) {
debug_assert_eq!(out.rows, rhs.rows);
debug_assert_eq!(out.cols, rhs.cols);
let q = out.params.modulus;
for row in 0..out.rows {
for col in 0..out.cols {
let out_poly = out.get_poly_mut(row, col);
let rhs_poly = rhs.get_poly(row, col);
for (out_coeff, rhs_coeff) in out_poly.iter_mut().zip(rhs_poly) {
*out_coeff = (*out_coeff + *rhs_coeff) % q;
}
}
}
}
fn identity_table(params: &RlweParams) -> NttAutomorphTable {
NttAutomorphTable::new_checked(
1,
(0..params.d as u32).collect::<Vec<_>>().into_boxed_slice(),
params.d,
)
}
fn compose_tables(
params: &RlweParams,
first: &NttAutomorphTable,
second: &NttAutomorphTable,
exponent: u64,
) -> NttAutomorphTable {
debug_assert_eq!(first.indices.len(), params.d);
debug_assert_eq!(second.indices.len(), params.d);
let indices = (0..params.d)
.map(|idx| first.indices[second.indices[idx] as usize])
.collect::<Vec<_>>()
.into_boxed_slice();
NttAutomorphTable::new_checked(exponent, indices, params.d)
}
fn match_probe_slots(
params: &RlweParams,
probe_a: &PolyMatrixNTT<'_>,
probe_b: &PolyMatrixNTT<'_>,
auto_a: &PolyMatrixNTT<'_>,
auto_b: &PolyMatrixNTT<'_>,
) -> Option<Box<[u32]>> {
let mut positions = HashMap::with_capacity(params.d);
let a = probe_a.get_poly(0, 0);
let b = probe_b.get_poly(0, 0);
for idx in 0..params.d {
if positions.insert((a[idx], b[idx]), idx as u32).is_some() {
return None;
}
}
let auto_a = auto_a.get_poly(0, 0);
let auto_b = auto_b.get_poly(0, 0);
let mut indices = Vec::with_capacity(params.d);
for idx in 0..params.d {
let src = positions.get(&(auto_a[idx], auto_b[idx]))?;
indices.push(*src);
}
Some(indices.into_boxed_slice())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::params::{GadgetParams, RlweParams};
fn params() -> RlweParams {
RlweParams::new(
8,
12289,
4,
3.2,
GadgetParams {
bits_per: 3,
ell: 5,
},
)
.expect("valid params")
}
fn raw_from_coeffs<'a>(params: &'a RlweParams, coeffs: &[u64]) -> PolyMatrixRaw<'a> {
let mut poly = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
poly.get_poly_mut(0, 0).copy_from_slice(coeffs);
poly
}
fn raw_matrix<'a>(params: &'a RlweParams, rows: usize, cols: usize) -> PolyMatrixRaw<'a> {
let mut matrix = PolyMatrixRaw::zero(¶ms.spiral, rows, cols);
for row in 0..rows {
for col in 0..cols {
for coeff in 0..params.d {
matrix.get_poly_mut(row, col)[coeff] =
(1 + row * 100 + col * 10 + coeff) as u64;
}
}
}
matrix
}
fn coeffs(poly: &PolyMatrixRaw<'_>) -> Vec<u64> {
poly.get_poly(0, 0).to_vec()
}
fn ntt_coeffs(poly: &PolyMatrixNTT<'_>) -> Vec<u64> {
coeffs(&from_ntt_alloc(poly))
}
#[test]
fn h_returns_negation_exponent() {
assert_eq!(h(8), 15);
assert_eq!(h(16), 31);
}
#[test]
fn tau_g_pow_returns_powers_mod_2d() {
assert_eq!(tau_g_pow(0, 8), 1);
assert_eq!(tau_g_pow(1, 8), 5);
assert_eq!(tau_g_pow(2, 8), 9);
assert_eq!(tau_g_pow(3, 8), 13);
assert_eq!(tau_g_pow(4, 8), 1);
}
#[test]
fn tau_raw_applies_negacyclic_automorphism() {
let params = params();
let poly = raw_from_coeffs(¶ms, &[1, 2, 3, 4, 5, 6, 7, 8]);
assert_eq!(
coeffs(&tau_raw(&poly, h(params.d))),
vec![1, 12281, 12282, 12283, 12284, 12285, 12286, 12287]
);
}
#[test]
fn tau_ntt_matches_tau_raw_after_round_trip() {
let params = params();
let poly = raw_from_coeffs(¶ms, &[9, 8, 7, 6, 5, 4, 3, 2]);
let exponent = tau_g_pow(2, params.d);
assert_eq!(
ntt_coeffs(&tau_ntt(&to_ntt_alloc(&poly), exponent)),
coeffs(&tau_raw(&poly, exponent))
);
}
#[test]
fn ntt_table_automorphism_matches_round_trip_for_all_odd_exponents() {
let params = params();
let poly = raw_from_coeffs(¶ms, &[9, 8, 7, 6, 5, 4, 3, 2]);
let input_ntt = to_ntt_alloc(&poly);
for exponent in (1..2 * params.d as u64).step_by(2) {
let table = ntt_automorph_table(¶ms, exponent);
let actual = apply_tau_ntt_alloc(&input_ntt, &table);
let expected = to_ntt_alloc(&tau_raw(&poly, exponent));
assert_eq!(
actual.as_slice(),
expected.as_slice(),
"exponent {exponent}"
);
}
}
#[test]
fn ntt_table_automorphism_handles_multi_polynomial_matrices() {
let params = params();
let matrix = raw_matrix(¶ms, 2, 3);
let input_ntt = to_ntt_alloc(&matrix);
let exponent = tau_g_pow(2, params.d);
let table = ntt_automorph_table(¶ms, exponent);
let mut actual = PolyMatrixNTT::zero(¶ms.spiral, 2, 3);
apply_tau_ntt_into(&mut actual, &input_ntt, &table);
let expected = to_ntt_alloc(&tau_raw(&matrix, exponent));
assert_eq!(actual.as_slice(), expected.as_slice());
}
#[test]
fn double_ntt_automorphism_matches_independent_applications() {
let params = params();
let matrix = raw_matrix(¶ms, 1, 2);
let input_ntt = to_ntt_alloc(&matrix);
let left_exp = tau_g_pow(1, params.d);
let right_exp = (left_exp * h(params.d)) % (2 * params.d as u64);
let left_table = ntt_automorph_table(¶ms, left_exp);
let right_table = ntt_automorph_table(¶ms, right_exp);
let mut actual_left = PolyMatrixNTT::zero(¶ms.spiral, 1, 2);
let mut actual_right = PolyMatrixNTT::zero(¶ms.spiral, 1, 2);
apply_tau_ntt_double_into(
&mut actual_left,
&mut actual_right,
&input_ntt,
&left_table,
&right_table,
);
let expected_left = to_ntt_alloc(&tau_raw(&matrix, left_exp));
let expected_right = to_ntt_alloc(&tau_raw(&matrix, right_exp));
assert_eq!(actual_left.as_slice(), expected_left.as_slice());
assert_eq!(actual_right.as_slice(), expected_right.as_slice());
}
#[test]
fn tau_g_power_tables_match_left_and_right_exponents() {
let params = params();
let poly = raw_from_coeffs(¶ms, &[2, 7, 1, 8, 2, 8, 1, 8]);
let input_ntt = to_ntt_alloc(&poly);
let two_d = 2 * params.d as u64;
let h_d = h(params.d);
let (left, right) = tau_g_power_tables(¶ms, params.d / 2 - 1);
for i in 0..(params.d / 2 - 1) {
let left_exp = tau_g_pow(i, params.d);
let right_exp = (left_exp * h_d) % two_d;
assert_eq!(left[i].exponent(), left_exp);
assert_eq!(right[i].exponent(), right_exp);
let actual_left = apply_tau_ntt_alloc(&input_ntt, &left[i]);
let actual_right = apply_tau_ntt_alloc(&input_ntt, &right[i]);
let expected_left = to_ntt_alloc(&tau_raw(&poly, left_exp));
let expected_right = to_ntt_alloc(&tau_raw(&poly, right_exp));
assert_eq!(actual_left.as_slice(), expected_left.as_slice());
assert_eq!(actual_right.as_slice(), expected_right.as_slice());
}
}
#[test]
fn trace_keeps_only_d_times_constant_coefficient() {
let params = params();
let poly = raw_from_coeffs(¶ms, &[42, 1, 9, 2, 6, 5, 3, 8]);
assert_eq!(
coeffs(&trace(&poly)),
vec![(params.d as u64 * 42) % params.q, 0, 0, 0, 0, 0, 0, 0]
);
}
}