use rand_chacha::ChaCha20Rng;
use spiral_rs::gadget::build_gadget;
use spiral_rs::poly::{
add_into, from_ntt_alloc, multiply, scalar_multiply_alloc, stack_ntt, to_ntt_alloc, PolyMatrix,
PolyMatrixNTT, PolyMatrixRaw,
};
use crate::automorph::{apply_tau_ntt_alloc, tau_ntt, NttAutomorphTable};
use crate::params::RlweParams;
pub struct KeySwitchingMatrix<'a> {
pub mat: PolyMatrixNTT<'a>,
pub params: &'a RlweParams,
}
pub fn ks_setup<'a>(
params: &'a RlweParams,
s_from_ntt: &PolyMatrixNTT<'a>,
s_to_ntt: &PolyMatrixNTT<'a>,
rng: &mut ChaCha20Rng,
) -> KeySwitchingMatrix<'a> {
assert_eq!(s_from_ntt.rows, 1);
assert_eq!(s_from_ntt.cols, 1);
assert_eq!(s_to_ntt.rows, 1);
assert_eq!(s_to_ntt.cols, 1);
let spiral = ¶ms.spiral;
let ell = params.gadget.ell;
let gadget = build_gadget(spiral, 1, ell);
let scaled = scalar_multiply_alloc(s_from_ntt, &to_ntt_alloc(&gadget));
let dg = crate::gaussian::discrete_gaussian(params.sigma_chi);
let a = PolyMatrixRaw::random_rng(spiral, 1, ell, rng);
let e = PolyMatrixRaw::noise(spiral, 1, ell, &dg, rng);
let a_ntt = to_ntt_alloc(&a);
let w = (-&a).ntt();
let mut y = PolyMatrixNTT::zero(spiral, 1, ell);
multiply(&mut y, s_to_ntt, &a_ntt);
add_into(&mut y, &to_ntt_alloc(&e));
add_into(&mut y, &scaled);
KeySwitchingMatrix {
mat: stack_ntt(&w, &y),
params,
}
}
pub fn ks_switch<'a>(
k: &KeySwitchingMatrix<'a>,
c1: &PolyMatrixNTT<'a>,
c2: &PolyMatrixNTT<'a>,
) -> (PolyMatrixNTT<'a>, PolyMatrixNTT<'a>) {
let params = k.params;
assert_eq!(k.mat.rows, 2, "KS matrix must have 2 rows ([w; y])");
assert_eq!(
k.mat.cols, params.gadget.ell,
"KS matrix width must match the gadget length ℓ",
);
assert_eq!(c1.rows, 1);
assert_eq!(c1.cols, 1);
assert_eq!(c2.rows, 1);
assert_eq!(c2.cols, 1);
let digits_ntt = ks_digits_ntt_from_c1(params, c1);
ks_switch_with_digits_ntt(k, &digits_ntt, c2)
}
pub(crate) fn ks_digits_ntt_from_c1<'a>(
params: &'a RlweParams,
c1: &PolyMatrixNTT<'a>,
) -> PolyMatrixNTT<'a> {
assert_eq!(c1.rows, 1);
assert_eq!(c1.cols, 1);
let digits_raw = signed_gadget_invert_alloc(params, &from_ntt_alloc(c1));
to_ntt_alloc(&digits_raw)
}
pub(crate) fn ks_switch_with_digits_ntt<'a>(
k: &KeySwitchingMatrix<'a>,
digits_ntt: &PolyMatrixNTT<'a>,
c2: &PolyMatrixNTT<'a>,
) -> (PolyMatrixNTT<'a>, PolyMatrixNTT<'a>) {
ks_call_count::inc();
let params = k.params;
assert_eq!(k.mat.rows, 2, "KS matrix must have 2 rows ([w; y])");
assert_eq!(
k.mat.cols, params.gadget.ell,
"KS matrix width must match the gadget length ℓ",
);
assert_eq!(digits_ntt.rows, params.gadget.ell);
assert_eq!(digits_ntt.cols, 1);
assert_eq!(c2.rows, 1);
assert_eq!(c2.cols, 1);
let mut switched = PolyMatrixNTT::zero(¶ms.spiral, 2, 1);
multiply(&mut switched, &k.mat, digits_ntt);
let delta_a = switched.submatrix(0, 0, 1, 1);
let mut delta_b = switched.submatrix(1, 0, 1, 1);
add_into(&mut delta_b, c2);
(delta_a, delta_b)
}
fn signed_gadget_invert_alloc<'a>(
params: &'a RlweParams,
input: &PolyMatrixRaw<'a>,
) -> PolyMatrixRaw<'a> {
assert_eq!(input.rows, 1);
assert_eq!(input.cols, 1);
let mut out = PolyMatrixRaw::zero(¶ms.spiral, params.gadget.ell, 1);
let z = params.gadget.z();
let half = z / 2;
let shift = params.gadget.bits_per;
let mask = z - 1;
assert!(
half <= params.q,
"signed digits must be representable modulo q"
);
for coeff_idx in 0..params.d {
let mut x = input.get_poly(0, 0)[coeff_idx];
if x >= params.q {
x %= params.q;
}
for digit_idx in 0..params.gadget.ell - 1 {
let low = x & mask;
x >>= shift;
let digit = if low >= half {
x += 1;
params.q - (z - low)
} else {
low
};
out.get_poly_mut(digit_idx, 0)[coeff_idx] = digit;
}
debug_assert!(x <= z);
let top = if x >= params.q { x % params.q } else { x };
out.get_poly_mut(params.gadget.ell - 1, 0)[coeff_idx] = top;
}
out
}
#[must_use]
pub fn automorphic_image<'a>(k: &KeySwitchingMatrix<'a>, t: u64) -> KeySwitchingMatrix<'a> {
KeySwitchingMatrix {
mat: tau_ntt(&k.mat, t),
params: k.params,
}
}
#[must_use]
pub fn automorphic_image_with_table<'a>(
k: &KeySwitchingMatrix<'a>,
table: &NttAutomorphTable,
) -> KeySwitchingMatrix<'a> {
KeySwitchingMatrix {
mat: apply_tau_ntt_alloc(&k.mat, table),
params: k.params,
}
}
#[doc(hidden)]
pub mod ks_call_count {
use std::cell::Cell;
thread_local! {
static COUNTER: Cell<u64> = const { Cell::new(0) };
}
pub fn reset() {
COUNTER.with(|c| c.set(0));
}
pub fn inc() {
COUNTER.with(|c| c.set(c.get() + 1));
}
#[must_use]
pub fn get() -> u64 {
COUNTER.with(Cell::get)
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::automorph::tau_g_pow;
use crate::params::GadgetParams;
use rand_chacha::rand_core::SeedableRng;
use spiral_rs::gadget::gadget_invert_alloc;
use spiral_rs::poly::PolyMatrix;
fn params() -> RlweParams {
RlweParams::new(
8,
12289,
4,
0.1,
GadgetParams {
bits_per: 3,
ell: 5,
},
)
.expect("valid params")
}
fn raw_from_coeffs<'a>(params: &'a RlweParams, coeffs: &[u64]) -> PolyMatrixRaw<'a> {
let mut raw = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
raw.get_poly_mut(0, 0).copy_from_slice(coeffs);
raw
}
fn ntt_from_coeffs<'a>(params: &'a RlweParams, coeffs: &[u64]) -> PolyMatrixNTT<'a> {
to_ntt_alloc(&raw_from_coeffs(params, coeffs))
}
fn tau_coeffs(poly: &[u64], exponent: u64, q: u64) -> Vec<u64> {
let d = poly.len();
let mut out = vec![0; d];
for (i, coeff) in poly.iter().enumerate() {
let exp = (i as u64 * exponent) % (2 * d as u64);
let reduced = coeff % q;
let (idx, value) = if exp < d as u64 {
(exp as usize, reduced)
} else {
(
(exp - d as u64) as usize,
if reduced == 0 { 0 } else { q - reduced },
)
};
out[idx] = (out[idx] + value) % q;
}
out
}
fn negacyclic_mul(lhs: &[u64], rhs: &[u64], q: u64) -> Vec<u64> {
let d = lhs.len();
let mut out = vec![0; d];
for (i, l) in lhs.iter().enumerate() {
for (j, r) in rhs.iter().enumerate() {
let product = (u128::from(*l) * u128::from(*r) % u128::from(q)) as u64;
let degree = i + j;
if degree < d {
out[degree] = (out[degree] + product) % q;
} else if product != 0 {
out[degree - d] = (out[degree - d] + q - product) % q;
}
}
}
out
}
fn add_poly(lhs: &[u64], rhs: &[u64], q: u64) -> Vec<u64> {
lhs.iter().zip(rhs).map(|(x, y)| (x + y) % q).collect()
}
fn sub_poly(lhs: &[u64], rhs: &[u64], q: u64) -> Vec<u64> {
lhs.iter().zip(rhs).map(|(x, y)| (q + x - y) % q).collect()
}
fn decrypt(params: &RlweParams, c1: &[u64], c2: &[u64], s: &[u64]) -> Vec<u64> {
let inner = add_poly(c2, &negacyclic_mul(c1, s, params.q), params.q);
inner
.iter()
.map(|coeff| ((coeff + params.delta / 2) / params.delta) % params.p)
.collect()
}
#[test]
fn spiral_matrix_multiply_accumulates_along_inner_dim() {
let params = params();
let mut a = PolyMatrixNTT::zero(¶ms.spiral, 1, 3);
let mut b = PolyMatrixNTT::zero(¶ms.spiral, 3, 1);
let inputs: [[u64; 8]; 3] = [
[3, 1, 4, 1, 5, 9, 2, 6],
[2, 7, 1, 8, 2, 8, 1, 8],
[1, 6, 1, 8, 0, 3, 3, 9],
];
let factors: [[u64; 8]; 3] = [
[11, 13, 17, 19, 23, 29, 31, 37],
[41, 43, 47, 53, 59, 61, 67, 71],
[73, 79, 83, 89, 97, 101, 103, 107],
];
for k in 0..3 {
let a_ntt = to_ntt_alloc(&raw_from_coeffs(¶ms, &inputs[k]));
a.get_poly_mut(0, k).copy_from_slice(a_ntt.get_poly(0, 0));
let b_ntt = to_ntt_alloc(&raw_from_coeffs(¶ms, &factors[k]));
b.get_poly_mut(k, 0).copy_from_slice(b_ntt.get_poly(0, 0));
}
let mut prod = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
multiply(&mut prod, &a, &b);
let prod_raw = from_ntt_alloc(&prod);
let mut expected = vec![0_u64; params.d];
for k in 0..3 {
expected = add_poly(
&expected,
&negacyclic_mul(&inputs[k], &factors[k], params.q),
params.q,
);
}
assert_eq!(
prod_raw.get_poly(0, 0).to_vec(),
expected,
"spiral-rs multiply lost the accumulator; see docs/spiral-rs-mapping.md §1"
);
}
#[test]
fn spiral_gadget_invert_reconstructs_each_coefficient_mod_q() {
let params = params();
let mut input = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
input
.get_poly_mut(0, 0)
.copy_from_slice(&[0, 1, 7, 8, 63, 64, params.q - 1, params.q - 4]);
let digits = gadget_invert_alloc(params.gadget.ell, &input);
let z = u128::from(params.gadget.z());
let q = u128::from(params.q);
for coeff_idx in 0..params.d {
let mut acc = 0u128;
for digit_row in 0..params.gadget.ell {
acc +=
u128::from(digits.get_poly(digit_row, 0)[coeff_idx]) * z.pow(digit_row as u32);
}
assert_eq!(
input.get_poly(0, 0)[coeff_idx],
(acc % q) as u64,
"coefficient index {coeff_idx}"
);
}
}
#[test]
fn signed_gadget_invert_uses_balanced_digits_and_reconstructs() {
let params = params();
let input = raw_from_coeffs(¶ms, &[0, 1, 4, 7, 8, 63, 64, params.q - 1]);
let digits = signed_gadget_invert_alloc(¶ms, &input);
let z = u128::from(params.gadget.z());
let q = u128::from(params.q);
for coeff_idx in 0..params.d {
let mut acc = 0_u128;
for digit_row in 0..params.gadget.ell {
acc +=
u128::from(digits.get_poly(digit_row, 0)[coeff_idx]) * z.pow(digit_row as u32);
}
assert_eq!(
input.get_poly(0, 0)[coeff_idx],
(acc % q) as u64,
"coefficient index {coeff_idx}"
);
}
assert_eq!(digits.get_poly(0, 0)[2], params.q - 4);
assert_eq!(digits.get_poly(0, 0)[3], params.q - 1);
}
#[test]
fn signed_gadget_invert_retains_top_carry() {
for gadget in [
GadgetParams {
bits_per: 1,
ell: 14,
},
GadgetParams {
bits_per: 3,
ell: 5,
},
] {
let params = RlweParams::new(8, 12289, 4, 3.2, gadget).unwrap();
let values = [
0,
1,
gadget.z() / 2,
gadget.z() / 2 + 1,
params.q / 2,
params.q - 2,
params.q - 1,
params.q,
];
let digits = signed_gadget_invert_alloc(¶ms, &raw_from_coeffs(¶ms, &values));
for (coeff_idx, value) in values.into_iter().enumerate() {
let mut reconstructed = 0_u128;
let mut power = 1_u128;
for digit_idx in 0..gadget.ell {
reconstructed = (reconstructed
+ u128::from(digits.get_poly(digit_idx, 0)[coeff_idx]) * power)
% u128::from(params.q);
power = power * u128::from(gadget.z()) % u128::from(params.q);
}
assert_eq!(reconstructed as u64, value % params.q);
}
}
let params = RlweParams::new(
8,
12289,
4,
3.2,
GadgetParams {
bits_per: 1,
ell: 14,
},
)
.unwrap();
let digits =
signed_gadget_invert_alloc(¶ms, &raw_from_coeffs(¶ms, &[params.q - 2; 8]));
assert_eq!(digits.get_poly(13, 0)[0], 2);
}
#[test]
fn high_carry_key_switch_preserves_zero_phase() {
let params = RlweParams::new(
8,
12289,
4,
3.2,
GadgetParams {
bits_per: 1,
ell: 14,
},
)
.unwrap();
let gadget = build_gadget(¶ms.spiral, 1, params.gadget.ell);
let zero = PolyMatrixRaw::zero(¶ms.spiral, 1, params.gadget.ell);
let k = KeySwitchingMatrix {
mat: stack_ntt(&to_ntt_alloc(&zero), &to_ntt_alloc(&gadget)),
params: ¶ms,
};
let c1 = ntt_from_coeffs(¶ms, &[params.q - 1, 0, 0, 0, 0, 0, 0, 0]);
let c2 = ntt_from_coeffs(¶ms, &[1, 0, 0, 0, 0, 0, 0, 0]);
let digits = ks_digits_ntt_from_c1(¶ms, &c1);
let (a_direct, b_direct) = ks_switch(&k, &c1, &c2);
let (a_cached, b_cached) = ks_switch_with_digits_ntt(&k, &digits, &c2);
assert_eq!(a_direct.as_slice(), a_cached.as_slice());
assert_eq!(b_direct.as_slice(), b_cached.as_slice());
assert_eq!(from_ntt_alloc(&b_direct).get_poly(0, 0)[0], 0);
assert_eq!(
decrypt(
¶ms,
from_ntt_alloc(&a_direct).get_poly(0, 0),
from_ntt_alloc(&b_direct).get_poly(0, 0),
&[0; 8]
),
vec![0; 8]
);
}
#[test]
fn ks_switch_with_precomputed_digits_matches_full_switch() {
let params = params();
let mut rng = rand_chacha::ChaCha20Rng::seed_from_u64(0xD161_7A11);
let k = ks_setup(
¶ms,
&ntt_from_coeffs(¶ms, &[1, 2, 3, 4, 5, 6, 7, 8]),
&ntt_from_coeffs(¶ms, &[8, 7, 6, 5, 4, 3, 2, 1]),
&mut rng,
);
let c1 = ntt_from_coeffs(¶ms, &[3, 1, 4, 1, 5, 9, 2, 6]);
let c2_values = [
[0, 0, 0, 0, 0, 0, 0, 0],
[9, 2, 6, 5, 3, 5, 8, 9],
[
params.q - 1,
1,
params.q - 2,
2,
params.q - 3,
3,
params.q - 4,
4,
],
];
let digits = ks_digits_ntt_from_c1(¶ms, &c1);
for c2_coeffs in c2_values {
let c2 = ntt_from_coeffs(¶ms, &c2_coeffs);
let (expected_a, expected_b) = ks_switch(&k, &c1, &c2);
let (actual_a, actual_b) = ks_switch_with_digits_ntt(&k, &digits, &c2);
assert_eq!(actual_a.as_slice(), expected_a.as_slice());
assert_eq!(actual_b.as_slice(), expected_b.as_slice());
}
}
#[test]
fn ks_setup_then_ks_switch_recovers_plaintext_under_target_secret() {
let params = params();
let s_from = vec![3, 1, 4, 1, 5, 9, 2, 6];
let s_to = vec![1, 0, params.q - 1, 1, 0, 1, params.q - 1, 0];
let messages = vec![0_u64, 1, 2, 3, 3, 2, 1, 0];
let c1 = vec![5_u64, 7, 11, 13, 17, 19, 23, 29];
let encoded: Vec<_> = messages
.iter()
.map(|m| (params.delta * m) % params.q)
.collect();
let c2 = sub_poly(&encoded, &negacyclic_mul(&c1, &s_from, params.q), params.q);
let mut rng = rand_chacha::ChaCha20Rng::seed_from_u64(0xC0DE_C0DE);
let k = ks_setup(
¶ms,
&ntt_from_coeffs(¶ms, &s_from),
&ntt_from_coeffs(¶ms, &s_to),
&mut rng,
);
let (c1_new, c2_new) = ks_switch(
&k,
&ntt_from_coeffs(¶ms, &c1),
&ntt_from_coeffs(¶ms, &c2),
);
let c1_new_raw = from_ntt_alloc(&c1_new);
let c2_new_raw = from_ntt_alloc(&c2_new);
assert_eq!(
decrypt(
¶ms,
c1_new_raw.get_poly(0, 0),
c2_new_raw.get_poly(0, 0),
&s_to
),
messages,
);
}
#[test]
fn automorphic_image_yields_ks_for_rotated_secret_pair() {
let params = params();
let s_from = vec![3, 1, 4, 1, 5, 9, 2, 6];
let s_to = vec![1, 0, params.q - 1, 1, 0, 1, params.q - 1, 0];
let messages = vec![0_u64, 1, 2, 3, 3, 2, 1, 0];
let c1 = vec![5_u64, 7, 11, 13, 17, 19, 23, 29];
let mut rng = rand_chacha::ChaCha20Rng::seed_from_u64(0xA70_A0E);
let k = ks_setup(
¶ms,
&ntt_from_coeffs(¶ms, &s_from),
&ntt_from_coeffs(¶ms, &s_to),
&mut rng,
);
let t = tau_g_pow(2, params.d);
let s_from_rot = tau_coeffs(&s_from, t, params.q);
let s_to_rot = tau_coeffs(&s_to, t, params.q);
let k_image = automorphic_image(&k, t);
let encoded: Vec<_> = messages
.iter()
.map(|m| (params.delta * m) % params.q)
.collect();
let c2 = sub_poly(
&encoded,
&negacyclic_mul(&c1, &s_from_rot, params.q),
params.q,
);
let (c1_new, c2_new) = ks_switch(
&k_image,
&ntt_from_coeffs(¶ms, &c1),
&ntt_from_coeffs(¶ms, &c2),
);
let c1_new_raw = from_ntt_alloc(&c1_new);
let c2_new_raw = from_ntt_alloc(&c2_new);
assert_eq!(
decrypt(
¶ms,
c1_new_raw.get_poly(0, 0),
c2_new_raw.get_poly(0, 0),
&s_to_rot
),
messages,
"ks_switch through automorphic_image(K, t) must decrypt under τ_t(s_to)",
);
}
#[test]
fn ks_call_count_increments_once_per_ks_switch() {
let params = params();
let mut rng = rand_chacha::ChaCha20Rng::seed_from_u64(0xCA11);
let k = ks_setup(
¶ms,
&ntt_from_coeffs(¶ms, &[1, 2, 3, 4, 5, 6, 7, 8]),
&ntt_from_coeffs(¶ms, &[8, 7, 6, 5, 4, 3, 2, 1]),
&mut rng,
);
let c1 = ntt_from_coeffs(¶ms, &[1, 0, 0, 0, 0, 0, 0, 0]);
let c2 = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
ks_call_count::reset();
let _ = ks_switch(&k, &c1, &c2);
let _ = ks_switch(&k, &c1, &c2);
let _ = ks_switch(&k, &c1, &c2);
assert_eq!(ks_call_count::get(), 3);
}
}