use rand_chacha::rand_core::SeedableRng;
use rand_chacha::ChaCha20Rng;
use rayon::prelude::*;
use spiral_rs::arith::barrett_reduction_u128;
use spiral_rs::gadget::build_gadget;
use spiral_rs::ntt::ntt_forward;
use spiral_rs::params::Params as SpiralParams;
use spiral_rs::poly::{
add_into, from_ntt_alloc, multiply, stack_ntt, to_ntt_alloc, PolyMatrix, PolyMatrixNTT,
PolyMatrixRaw,
};
use crate::automorph::{apply_tau_ntt_alloc, h, tau_g_pow, tau_g_power_tables, NttAutomorphTable};
use crate::collapse::{collapse_one_with_digits, precompute_collapse_affine, CollapseState};
use crate::error::InspiringError;
use crate::key_switching::{
automorphic_image_with_table, ks_digits_ntt_from_c1, KeySwitchingMatrix,
};
use crate::pack::RlweCiphertext;
use crate::params::RlweParams;
pub const REFERENCE_W_SEED: [u8; 32] = [7; 32];
pub const REFERENCE_V_SEED: [u8; 32] = [
8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
];
pub struct PackPublicPreprocessed<'a> {
pub params: &'a RlweParams,
pub a_agg: Vec<PolyMatrixNTT<'a>>,
}
pub struct PackPreprocessed<'a> {
pub params: &'a RlweParams,
pub collapse_a_final_ntt: PolyMatrixNTT<'a>,
pub collapse_b_offset_ntt: PolyMatrixNTT<'a>,
}
pub struct PackingKeys<'a> {
pub kg_body: PolyMatrixNTT<'a>,
pub kh_body: PolyMatrixNTT<'a>,
}
pub struct TopKeyImages<'a> {
pub kg_top_left: Vec<PolyMatrixNTT<'a>>,
pub kg_top_right: Vec<PolyMatrixNTT<'a>>,
pub kh_top: PolyMatrixNTT<'a>,
pub kg_body_left_tables: Vec<NttAutomorphTable>,
pub kg_body_right_tables: Vec<NttAutomorphTable>,
}
pub struct QueryPackPreprocessed<'a> {
pub params: &'a RlweParams,
pub collapse_a_final_ntt: PolyMatrixNTT<'a>,
pub digits_ntt: Vec<PolyMatrixNTT<'a>>,
}
struct QueryReferencePrecomputed<'a> {
collapse_a_final_ntt: PolyMatrixNTT<'a>,
digits_ntt: Vec<PolyMatrixNTT<'a>>,
}
impl<'a> PackPreprocessed<'a> {
pub fn build(
params: &'a RlweParams,
crs: &PolyMatrixNTT<'a>,
kg: &KeySwitchingMatrix<'a>,
kh: &KeySwitchingMatrix<'a>,
) -> Result<Self, InspiringError> {
PackPublicPreprocessed::build(params, crs)?.bind_keys(kg, kh)
}
}
impl<'a> PackPublicPreprocessed<'a> {
pub fn build(params: &'a RlweParams, crs: &PolyMatrixNTT<'a>) -> Result<Self, InspiringError> {
if crs.rows != params.d || crs.cols != 1 {
return Err(InspiringError::PreprocessMismatch(format!(
"expected CRS shape {}x1, got {}x{}",
params.d, crs.rows, crs.cols
)));
}
let crs_raw = from_ntt_alloc(crs);
let a_tildes: Vec<_> = (0..params.d)
.map(|row| a_tilde_coeffs(params, crs_raw.get_poly(row, 0)))
.collect();
let a_agg = build_a_agg(params, &a_tildes);
Ok(Self { params, a_agg })
}
pub fn bind_keys(
&self,
kg: &KeySwitchingMatrix<'a>,
kh: &KeySwitchingMatrix<'a>,
) -> Result<PackPreprocessed<'a>, InspiringError> {
let params = self.params;
if kg.mat.rows != 2 || kg.mat.cols != params.gadget.ell {
return Err(InspiringError::PreprocessMismatch(format!(
"K_g must have shape 2x{}, got {}x{}",
params.gadget.ell, kg.mat.rows, kg.mat.cols
)));
}
if kh.mat.rows != 2 || kh.mat.cols != params.gadget.ell {
return Err(InspiringError::PreprocessMismatch(format!(
"K_h must have shape 2x{}, got {}x{}",
params.gadget.ell, kh.mat.rows, kh.mat.cols
)));
}
let (left_tables, right_tables) = tau_g_power_tables(params, params.d / 2 - 1);
let kg_images_left: Vec<_> = left_tables
.iter()
.map(|table| automorphic_image_with_table(kg, table))
.collect();
let kg_images_right: Vec<_> = right_tables
.iter()
.map(|table| automorphic_image_with_table(kg, table))
.collect();
let collapse_affine = precompute_collapse_affine(
params,
self.a_agg.clone(),
&kg_images_left,
&kg_images_right,
kh,
);
Ok(PackPreprocessed {
params,
collapse_a_final_ntt: collapse_affine.a_final_ntt,
collapse_b_offset_ntt: collapse_affine.b_offset_ntt,
})
}
}
impl<'a> PackingKeys<'a> {
pub fn generate_full(
params: &'a RlweParams,
secret_ntt: &PolyMatrixNTT<'a>,
rng: &mut ChaCha20Rng,
) -> Self {
let kg_body = generate_reference_body(
params,
secret_ntt,
tau_g_pow(1, params.d),
REFERENCE_W_SEED,
rng,
);
let kh_body =
generate_reference_body(params, secret_ntt, h(params.d), REFERENCE_V_SEED, rng);
Self { kg_body, kh_body }
}
pub fn to_key_pair(
&self,
params: &'a RlweParams,
) -> Result<(KeySwitchingMatrix<'a>, KeySwitchingMatrix<'a>), InspiringError> {
self.validate(params)?;
let y_top = reference_mask_top(params, REFERENCE_W_SEED);
let z_top = reference_mask_top(params, REFERENCE_V_SEED);
Ok((
KeySwitchingMatrix {
mat: stack_ntt(&y_top, &self.kg_body),
params,
},
KeySwitchingMatrix {
mat: stack_ntt(&z_top, &self.kh_body),
params,
},
))
}
pub fn validate(&self, params: &RlweParams) -> Result<(), InspiringError> {
validate_reference_body(params, &self.kg_body, "reference K_g body")?;
validate_reference_body(params, &self.kh_body, "reference K_h body")?;
Ok(())
}
}
impl<'a> QueryPackPreprocessed<'a> {
pub fn build_with_top(
params: &'a RlweParams,
crs: &PolyMatrixNTT<'a>,
top: &TopKeyImages<'a>,
) -> Result<Self, InspiringError> {
crate::preprocess_reuse::build(params, crs, top)
}
pub fn build(params: &'a RlweParams, crs: &PolyMatrixNTT<'a>) -> Result<Self, InspiringError> {
let public = PackPublicPreprocessed::build(params, crs)?;
let reference = precompute_reference_trace(params, public.a_agg);
Ok(Self {
params,
collapse_a_final_ntt: reference.collapse_a_final_ntt,
digits_ntt: reference.digits_ntt,
})
}
pub fn pack_b(
&self,
b_scalars: &[u64],
keys: &PackingKeys<'a>,
top_images: &TopKeyImages<'a>,
) -> Result<RlweCiphertext<'a>, InspiringError> {
keys.validate(self.params)?;
top_images.validate(self.params)?;
self.pack_b_prevalidated(b_scalars, keys, top_images)
}
pub fn pack_b_prevalidated(
&self,
b_scalars: &[u64],
keys: &PackingKeys<'a>,
top_images: &TopKeyImages<'a>,
) -> Result<RlweCiphertext<'a>, InspiringError> {
if b_scalars.len() != self.params.d {
return Err(InspiringError::LweShape(format!(
"expected {} LWE b scalars, got {}",
self.params.d,
b_scalars.len()
)));
}
let mut b_tilde = PolyMatrixRaw::zero(&self.params.spiral, 1, 1);
for (idx, b) in b_scalars.iter().copied().enumerate() {
b_tilde.get_poly_mut(0, 0)[idx] = b % self.params.q;
}
let b_final = collapse_uploaded_body_b(
self.params,
to_ntt_alloc(&b_tilde),
&keys.kg_body,
&keys.kh_body,
top_images,
&self.digits_ntt,
);
Ok(RlweCiphertext {
inner: stack_ntt(&self.collapse_a_final_ntt, &b_final),
})
}
pub fn pack_b_batched_prevalidated(
&self,
b_scalars: &[&[u64]],
keys: &[&PackingKeys<'a>],
top_images: &TopKeyImages<'a>,
) -> Result<Vec<RlweCiphertext<'a>>, InspiringError> {
if b_scalars.len() != keys.len() {
return Err(InspiringError::LweShape(format!(
"expected one key set per query, got {} b blocks and {} key sets",
b_scalars.len(),
keys.len()
)));
}
if b_scalars.is_empty() {
return Ok(Vec::new());
}
let mut b_tildes = Vec::with_capacity(b_scalars.len());
for block in b_scalars {
if block.len() != self.params.d {
return Err(InspiringError::LweShape(format!(
"expected {} LWE b scalars, got {}",
self.params.d,
block.len()
)));
}
let mut b_tilde = PolyMatrixRaw::zero(&self.params.spiral, 1, 1);
for (idx, b) in block.iter().copied().enumerate() {
b_tilde.get_poly_mut(0, 0)[idx] = b % self.params.q;
}
b_tildes.push(to_ntt_alloc(&b_tilde));
}
let bodies: Vec<(&PolyMatrixNTT<'a>, &PolyMatrixNTT<'a>)> =
keys.iter().map(|k| (&k.kg_body, &k.kh_body)).collect();
let finals = collapse_uploaded_body_b_batched(
self.params,
b_tildes,
&bodies,
top_images,
&self.digits_ntt,
);
Ok(finals
.iter()
.map(|b_final| RlweCiphertext {
inner: stack_ntt(&self.collapse_a_final_ntt, b_final),
})
.collect())
}
}
impl<'a> TopKeyImages<'a> {
pub fn build(params: &'a RlweParams) -> Self {
let kg_top = reference_mask_top(params, REFERENCE_W_SEED);
let kh_top = reference_mask_top(params, REFERENCE_V_SEED);
let (kg_body_left_tables, kg_body_right_tables) =
tau_g_power_tables(params, params.d / 2 - 1);
let kg_top_left = kg_body_left_tables
.iter()
.map(|table| apply_tau_ntt_alloc(&kg_top, table))
.collect();
let kg_top_right = kg_body_right_tables
.iter()
.map(|table| apply_tau_ntt_alloc(&kg_top, table))
.collect();
Self {
kg_top_left,
kg_top_right,
kh_top,
kg_body_left_tables,
kg_body_right_tables,
}
}
pub fn validate(&self, params: &RlweParams) -> Result<(), InspiringError> {
let expected = params.d / 2 - 1;
if self.kg_top_left.len() != expected {
return Err(InspiringError::PreprocessMismatch(format!(
"expected {expected} left fixed K_g top images, got {}",
self.kg_top_left.len()
)));
}
if self.kg_top_right.len() != expected {
return Err(InspiringError::PreprocessMismatch(format!(
"expected {expected} right fixed K_g top images, got {}",
self.kg_top_right.len()
)));
}
if self.kg_body_left_tables.len() != expected {
return Err(InspiringError::PreprocessMismatch(format!(
"expected {expected} left K_g body tables, got {}",
self.kg_body_left_tables.len()
)));
}
if self.kg_body_right_tables.len() != expected {
return Err(InspiringError::PreprocessMismatch(format!(
"expected {expected} right K_g body tables, got {}",
self.kg_body_right_tables.len()
)));
}
validate_reference_body(params, &self.kh_top, "reference kh top")?;
for (idx, top) in self.kg_top_left.iter().enumerate() {
validate_reference_body(params, top, "reference left kg top").map_err(|err| {
InspiringError::PreprocessMismatch(format!("left K_g top image {idx}: {err}"))
})?;
if self.kg_body_left_tables[idx].indices().len() != params.d {
return Err(InspiringError::PreprocessMismatch(format!(
"left K_g body table {idx} has length {}, expected {}",
self.kg_body_left_tables[idx].indices().len(),
params.d
)));
}
}
for (idx, top) in self.kg_top_right.iter().enumerate() {
validate_reference_body(params, top, "reference right kg top").map_err(|err| {
InspiringError::PreprocessMismatch(format!("right K_g top image {idx}: {err}"))
})?;
if self.kg_body_right_tables[idx].indices().len() != params.d {
return Err(InspiringError::PreprocessMismatch(format!(
"right K_g body table {idx} has length {}, expected {}",
self.kg_body_right_tables[idx].indices().len(),
params.d
)));
}
}
Ok(())
}
}
fn precompute_reference_trace<'a>(
params: &'a RlweParams,
a_agg: Vec<PolyMatrixNTT<'a>>,
) -> QueryReferencePrecomputed<'a> {
let kg = fixed_reference_key(params, REFERENCE_W_SEED);
let kh = fixed_reference_key(params, REFERENCE_V_SEED);
let (left_tables, right_tables) = tau_g_power_tables(params, params.d / 2 - 1);
let kg_images_left: Vec<_> = left_tables
.iter()
.map(|table| automorphic_image_with_table(&kg, table))
.collect();
let kg_images_right: Vec<_> = right_tables
.iter()
.map(|table| automorphic_image_with_table(&kg, table))
.collect();
let mut digits_ntt = Vec::with_capacity(params.d - 1);
let mut slots = a_agg;
let right = slots.split_off(params.d / 2);
let left = slots;
let b = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
let mut left_state = CollapseState { a: left, b };
collect_half_digits(&mut left_state, &kg_images_left, &mut digits_ntt);
let left_a = left_state
.a
.pop()
.expect("collapse_half leaves one left component");
let mut right_state = CollapseState {
a: right,
b: left_state.b,
};
collect_half_digits(&mut right_state, &kg_images_right, &mut digits_ntt);
let right_a = right_state
.a
.pop()
.expect("collapse_half leaves one right component");
let mut final_state = CollapseState {
a: vec![left_a, right_a],
b: right_state.b,
};
let final_digits = ks_digits_ntt_from_c1(params, &final_state.a[1]);
collapse_one_with_digits(&mut final_state, &kh, &final_digits);
digits_ntt.push(final_digits);
debug_assert_eq!(digits_ntt.len(), params.d - 1);
let collapse_a_final_ntt = final_state
.a
.pop()
.expect("final reference collapse leaves one component");
QueryReferencePrecomputed {
collapse_a_final_ntt,
digits_ntt,
}
}
fn collect_half_digits<'a>(
state: &mut CollapseState<'a>,
kg_images: &[KeySwitchingMatrix<'a>],
digits_ntt: &mut Vec<PolyMatrixNTT<'a>>,
) {
while state.a.len() > 1 {
let image_idx = state.a.len() - 2;
let digits = ks_digits_ntt_from_c1(kg_images[image_idx].params, &state.a[image_idx + 1]);
collapse_one_with_digits(state, &kg_images[image_idx], &digits);
digits_ntt.push(digits);
}
}
fn generate_reference_body<'a>(
params: &'a RlweParams,
secret_ntt: &PolyMatrixNTT<'a>,
secret_from_exponent: u64,
mask_seed: [u8; 32],
rng: &mut ChaCha20Rng,
) -> PolyMatrixNTT<'a> {
let spiral = ¶ms.spiral;
let ell = params.gadget.ell;
let mask_raw = reference_mask_raw(params, mask_seed);
let mask_ntt = to_ntt_alloc(&mask_raw);
let secret_from = crate::automorph::tau_ntt(secret_ntt, secret_from_exponent);
let gadget = build_gadget(spiral, 1, ell);
let scaled = spiral_rs::poly::scalar_multiply_alloc(&secret_from, &to_ntt_alloc(&gadget));
let dg = crate::gaussian::discrete_gaussian(params.sigma_chi);
let error = PolyMatrixRaw::noise(spiral, 1, ell, &dg, rng);
let mut body = PolyMatrixNTT::zero(spiral, 1, ell);
multiply(&mut body, secret_ntt, &mask_ntt);
add_into(&mut body, &to_ntt_alloc(&error));
add_into(&mut body, &scaled);
body
}
fn fixed_reference_key<'a>(params: &'a RlweParams, mask_seed: [u8; 32]) -> KeySwitchingMatrix<'a> {
let top = reference_mask_top(params, mask_seed);
let body = PolyMatrixNTT::zero(¶ms.spiral, 1, params.gadget.ell);
KeySwitchingMatrix {
mat: stack_ntt(&top, &body),
params,
}
}
fn collapse_uploaded_body_b<'a>(
params: &'a RlweParams,
b: PolyMatrixNTT<'a>,
kg_body: &PolyMatrixNTT<'a>,
kh_body: &PolyMatrixNTT<'a>,
top_images: &TopKeyImages<'a>,
digits_ntt: &[PolyMatrixNTT<'a>],
) -> PolyMatrixNTT<'a> {
assert_eq!(
digits_ntt.len(),
params.d - 1,
"preprocess::collapse_uploaded_body_b expects d - 1 digit blocks"
);
if !fused_accumulator_fits(params, kg_body.cols) {
return collapse_uploaded_body_b_stepwise(
params, b, kg_body, kh_body, top_images, digits_ntt,
);
}
let left = &top_images.kg_body_left_tables;
let right = &top_images.kg_body_right_tables;
assert_eq!(left.len(), params.d / 2 - 1);
assert_eq!(right.len(), params.d / 2 - 1);
let mut schedule: Vec<CollapseTerm<'_, 'a>> = Vec::with_capacity(params.d - 1);
for (digit_idx, image_idx) in (0..left.len()).rev().enumerate() {
schedule.push(CollapseTerm {
body: kg_body,
table: Some(&left[image_idx]),
digits: (&digits_ntt[digit_idx]).into(),
});
}
let right_base = left.len();
for (digit_idx, image_idx) in (0..right.len()).rev().enumerate() {
schedule.push(CollapseTerm {
body: kg_body,
table: Some(&right[image_idx]),
digits: (&digits_ntt[right_base + digit_idx]).into(),
});
}
schedule.push(CollapseTerm {
body: kh_body,
table: None,
digits: (&digits_ntt[params.d - 2]).into(),
});
debug_assert_eq!(schedule.len(), params.d - 1);
collapse_terms(params, b, &schedule)
}
thread_local! {
static PACKING_SCRATCH: std::cell::RefCell<Vec<Vec<u128>>> = const { std::cell::RefCell::new(Vec::new()) };
}
struct PackingScratch(Vec<u128>);
impl PackingScratch {
fn new(lanes: usize) -> Self {
let mut data = PACKING_SCRATCH
.with(|p| p.borrow_mut().pop())
.unwrap_or_default();
data.resize(lanes, 0);
data.fill(0);
Self(data)
}
}
impl std::ops::Deref for PackingScratch {
type Target = [u128];
fn deref(&self) -> &[u128] {
&self.0
}
}
impl std::ops::DerefMut for PackingScratch {
fn deref_mut(&mut self) -> &mut [u128] {
&mut self.0
}
}
impl Drop for PackingScratch {
fn drop(&mut self) {
self.0.fill(0);
let data = std::mem::take(&mut self.0);
PACKING_SCRATCH.with(|p| {
let mut pool = p.borrow_mut();
if pool.len() < 4 && data.capacity() <= 16384 {
pool.push(data);
}
});
}
}
fn collapse_terms<'a>(
params: &'a RlweParams,
b: PolyMatrixNTT<'a>,
schedule: &[CollapseTerm<'_, 'a>],
) -> PolyMatrixNTT<'a> {
let spiral = ¶ms.spiral;
let d = spiral.poly_len;
let lanes = d * spiral.crt_count;
let partials = schedule
.par_chunks(collapse_steps_per_task(schedule.len()))
.map(|chunk| {
let mut acc = PackingScratch::new(lanes);
for term in chunk {
accumulate_collapse_term(spiral, term, &mut acc);
}
acc
})
.reduce(
|| PackingScratch::new(lanes),
|mut lhs, rhs| {
for (slot, add) in lhs.iter_mut().zip(rhs.iter()) {
*slot += *add;
}
lhs
},
);
let mut out = b;
let out_poly = out.get_poly_mut(0, 0);
for crt_idx in 0..spiral.crt_count {
let modulus = spiral.moduli[crt_idx];
let offset = crt_idx * d;
for lane in 0..d {
let acc = partials[offset + lane];
debug_assert!(
acc <= u128::MAX - u128::from(modulus),
"fused collapse accumulator overflowed its proven bound"
);
let reduced = barrett_reduction_u128(spiral, acc);
let sum = out_poly[offset + lane] + reduced;
out_poly[offset + lane] = if sum >= modulus { sum - modulus } else { sum };
}
}
out
}
pub(crate) fn pack_mapped_block<'a>(
params: &'a RlweParams,
b_scalars: &[u64],
keys: &PackingKeys<'a>,
left: &[NttAutomorphTable],
right: &[NttAutomorphTable],
digits: &[DigitView<'_>],
a_final: &[u64],
) -> RlweCiphertext<'a> {
assert!(fused_accumulator_fits(params, keys.kg_body.cols));
let mut raw = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
raw.as_mut_slice().copy_from_slice(b_scalars);
let mut schedule = Vec::with_capacity(params.d - 1);
for (idx, table) in left.iter().rev().chain(right.iter().rev()).enumerate() {
schedule.push(CollapseTerm {
body: &keys.kg_body,
table: Some(table),
digits: digits[idx],
});
}
schedule.push(CollapseTerm {
body: &keys.kh_body,
table: None,
digits: digits[params.d - 2],
});
let b = collapse_terms(params, to_ntt_alloc(&raw), &schedule);
let mut out = PolyMatrixNTT::zero(¶ms.spiral, 2, 1);
let lanes = params.d * params.spiral.crt_count;
out.as_mut_slice()[..lanes].copy_from_slice(a_final);
out.as_mut_slice()[lanes..].copy_from_slice(b.as_slice());
RlweCiphertext { inner: out }
}
pub(crate) fn mapped_accumulator_supported(params: &RlweParams) -> bool {
fused_accumulator_fits(params, params.gadget.ell)
}
fn collapse_uploaded_body_b_batched<'a>(
params: &'a RlweParams,
b: Vec<PolyMatrixNTT<'a>>,
bodies: &[(&PolyMatrixNTT<'a>, &PolyMatrixNTT<'a>)],
top_images: &TopKeyImages<'a>,
digits_ntt: &[PolyMatrixNTT<'a>],
) -> Vec<PolyMatrixNTT<'a>> {
assert_eq!(
digits_ntt.len(),
params.d - 1,
"preprocess::collapse_uploaded_body_b_batched expects d - 1 digit blocks"
);
assert_eq!(b.len(), bodies.len(), "one b per key-body pair");
let fits = bodies
.iter()
.all(|(kg, _)| fused_accumulator_fits(params, kg.cols));
if !fits {
return b
.into_iter()
.zip(bodies.iter())
.map(|(b_one, (kg, kh))| {
collapse_uploaded_body_b_stepwise(params, b_one, kg, kh, top_images, digits_ntt)
})
.collect();
}
let left = &top_images.kg_body_left_tables;
let right = &top_images.kg_body_right_tables;
assert_eq!(left.len(), params.d / 2 - 1);
assert_eq!(right.len(), params.d / 2 - 1);
struct BatchedTerm<'t> {
table: Option<&'t NttAutomorphTable>,
digits: DigitView<'t>,
use_kh: bool,
}
let mut schedule: Vec<BatchedTerm<'_>> = Vec::with_capacity(params.d - 1);
for (digit_idx, image_idx) in (0..left.len()).rev().enumerate() {
schedule.push(BatchedTerm {
table: Some(&left[image_idx]),
digits: (&digits_ntt[digit_idx]).into(),
use_kh: false,
});
}
let right_base = left.len();
for (digit_idx, image_idx) in (0..right.len()).rev().enumerate() {
schedule.push(BatchedTerm {
table: Some(&right[image_idx]),
digits: (&digits_ntt[right_base + digit_idx]).into(),
use_kh: false,
});
}
schedule.push(BatchedTerm {
table: None,
digits: (&digits_ntt[params.d - 2]).into(),
use_kh: true,
});
debug_assert_eq!(schedule.len(), params.d - 1);
let spiral = ¶ms.spiral;
let d = spiral.poly_len;
let lanes = d * spiral.crt_count;
let k = bodies.len();
let partials = schedule
.par_chunks(collapse_steps_per_task(schedule.len()))
.map(|chunk| {
let mut acc = vec![0_u128; k * lanes];
for term in chunk {
for (query_idx, (kg, kh)) in bodies.iter().enumerate() {
let body = if term.use_kh { *kh } else { *kg };
let slot = &mut acc[query_idx * lanes..(query_idx + 1) * lanes];
accumulate_collapse_term(
spiral,
&CollapseTerm {
body,
table: term.table,
digits: term.digits,
},
slot,
);
}
}
acc
})
.reduce(
|| vec![0_u128; k * lanes],
|mut lhs, rhs| {
for (slot, add) in lhs.iter_mut().zip(rhs.iter()) {
*slot += *add;
}
lhs
},
);
b.into_iter()
.enumerate()
.map(|(query_idx, mut out)| {
let acc = &partials[query_idx * lanes..(query_idx + 1) * lanes];
let out_poly = out.get_poly_mut(0, 0);
for crt_idx in 0..spiral.crt_count {
let modulus = spiral.moduli[crt_idx];
let offset = crt_idx * d;
for lane in 0..d {
let value = acc[offset + lane];
debug_assert!(
value <= u128::MAX - u128::from(modulus),
"batched collapse accumulator overflowed its proven bound"
);
let reduced = barrett_reduction_u128(spiral, value);
let sum = out_poly[offset + lane] + reduced;
out_poly[offset + lane] = if sum >= modulus { sum - modulus } else { sum };
}
}
out
})
.collect()
}
#[derive(Clone, Copy)]
pub(crate) struct DigitView<'a> {
data: &'a [u64],
rows: usize,
cols: usize,
lanes: usize,
}
impl<'a> DigitView<'a> {
pub(crate) fn new(data: &'a [u64], rows: usize, lanes: usize) -> Self {
assert_eq!(data.len(), rows * lanes);
Self {
data,
rows,
cols: 1,
lanes,
}
}
fn get_poly(&self, row: usize, col: usize) -> &'a [u64] {
assert_eq!(col, 0);
&self.data[row * self.lanes..(row + 1) * self.lanes]
}
}
impl<'a> From<&'a PolyMatrixNTT<'_>> for DigitView<'a> {
fn from(m: &'a PolyMatrixNTT<'_>) -> Self {
assert_eq!(m.cols, 1);
Self::new(m.as_slice(), m.rows, m.params.poly_len * m.params.crt_count)
}
}
struct CollapseTerm<'t, 'a> {
body: &'t PolyMatrixNTT<'a>,
table: Option<&'t NttAutomorphTable>,
digits: DigitView<'t>,
}
fn fused_accumulator_fits(params: &RlweParams, ell: usize) -> bool {
let terms = ((params.d - 1) * ell) as u128;
let max_product = u128::from(params.q - 1).saturating_mul(u128::from(params.q - 1));
max_product.checked_mul(terms).is_some()
}
fn collapse_steps_per_task(steps: usize) -> usize {
let tasks = rayon::current_num_threads().max(1) * 4;
steps.div_ceil(tasks).max(1)
}
fn accumulate_collapse_term(spiral: &SpiralParams, term: &CollapseTerm<'_, '_>, acc: &mut [u128]) {
let d = spiral.poly_len;
let ell = term.body.cols;
debug_assert_eq!(term.digits.rows, ell);
debug_assert_eq!(term.digits.cols, 1);
if ell == 3 && spiral.crt_count == 1 {
let b0 = &term.body.get_poly(0, 0)[..d];
let b1 = &term.body.get_poly(0, 1)[..d];
let b2 = &term.body.get_poly(0, 2)[..d];
let g0 = &term.digits.get_poly(0, 0)[..d];
let g1 = &term.digits.get_poly(1, 0)[..d];
let g2 = &term.digits.get_poly(2, 0)[..d];
let acc = &mut acc[..d];
let mask = d - 1;
match term.table {
Some(table) => {
let indices = &table.indices()[..d];
for dst in 0..d {
let src = indices[dst] as usize & mask;
debug_assert!((indices[dst] as usize) < d, "table index out of range");
acc[dst] += u128::from(b0[src]) * u128::from(g0[dst])
+ u128::from(b1[src]) * u128::from(g1[dst])
+ u128::from(b2[src]) * u128::from(g2[dst]);
}
}
None => {
for dst in 0..d {
acc[dst] += u128::from(b0[dst]) * u128::from(g0[dst])
+ u128::from(b1[dst]) * u128::from(g1[dst])
+ u128::from(b2[dst]) * u128::from(g2[dst]);
}
}
}
return;
}
if ell > MAX_INLINE_ELL {
accumulate_collapse_term_digit_outer(spiral, term, acc);
return;
}
let mut bodies: [&[u64]; MAX_INLINE_ELL] = [&[]; MAX_INLINE_ELL];
let mut digits: [&[u64]; MAX_INLINE_ELL] = [&[]; MAX_INLINE_ELL];
for crt_idx in 0..spiral.crt_count {
let offset = crt_idx * d;
for digit_idx in 0..ell {
bodies[digit_idx] = &term.body.get_poly(0, digit_idx)[offset..offset + d];
digits[digit_idx] = &term.digits.get_poly(digit_idx, 0)[offset..offset + d];
}
let acc_chunk = &mut acc[offset..offset + d];
match term.table {
Some(table) => {
let indices = table.indices();
debug_assert_eq!(indices.len(), d);
for (dst, slot) in acc_chunk.iter_mut().enumerate() {
let src = indices[dst] as usize;
let mut sum = 0_u128;
for digit_idx in 0..ell {
sum +=
u128::from(bodies[digit_idx][src]) * u128::from(digits[digit_idx][dst]);
}
*slot += sum;
}
}
None => {
for (dst, slot) in acc_chunk.iter_mut().enumerate() {
let mut sum = 0_u128;
for digit_idx in 0..ell {
sum +=
u128::from(bodies[digit_idx][dst]) * u128::from(digits[digit_idx][dst]);
}
*slot += sum;
}
}
}
}
}
const MAX_INLINE_ELL: usize = 8;
fn accumulate_collapse_term_digit_outer(
spiral: &SpiralParams,
term: &CollapseTerm<'_, '_>,
acc: &mut [u128],
) {
let d = spiral.poly_len;
let ell = term.body.cols;
for crt_idx in 0..spiral.crt_count {
let offset = crt_idx * d;
let acc_chunk = &mut acc[offset..offset + d];
for digit_idx in 0..ell {
let body_chunk = &term.body.get_poly(0, digit_idx)[offset..offset + d];
let digit_chunk = &term.digits.get_poly(digit_idx, 0)[offset..offset + d];
match term.table {
Some(table) => {
let indices = table.indices();
debug_assert_eq!(indices.len(), d);
for (dst, (slot, digit)) in
acc_chunk.iter_mut().zip(digit_chunk.iter()).enumerate()
{
let src = indices[dst] as usize;
*slot += u128::from(body_chunk[src]) * u128::from(*digit);
}
}
None => {
for ((slot, body), digit) in acc_chunk
.iter_mut()
.zip(body_chunk.iter())
.zip(digit_chunk.iter())
{
*slot += u128::from(*body) * u128::from(*digit);
}
}
}
}
}
}
fn collapse_uploaded_body_b_stepwise<'a>(
params: &'a RlweParams,
mut b: PolyMatrixNTT<'a>,
kg_body: &PolyMatrixNTT<'a>,
kh_body: &PolyMatrixNTT<'a>,
top_images: &TopKeyImages<'a>,
digits_ntt: &[PolyMatrixNTT<'a>],
) -> PolyMatrixNTT<'a> {
let mut digit_idx = 0;
b = collapse_uploaded_body_half(
b,
kg_body,
&top_images.kg_body_left_tables,
digits_ntt,
&mut digit_idx,
);
b = collapse_uploaded_body_half(
b,
kg_body,
&top_images.kg_body_right_tables,
digits_ntt,
&mut digit_idx,
);
let mut final_b = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
multiply(&mut final_b, kh_body, &digits_ntt[digit_idx]);
add_into(&mut final_b, &b);
digit_idx += 1;
assert_eq!(digit_idx, digits_ntt.len());
final_b
}
fn collapse_uploaded_body_half<'a>(
mut b: PolyMatrixNTT<'a>,
kg_body: &PolyMatrixNTT<'a>,
body_tables: &[NttAutomorphTable],
digits_ntt: &[PolyMatrixNTT<'a>],
digit_idx: &mut usize,
) -> PolyMatrixNTT<'a> {
for image_idx in (0..body_tables.len()).rev() {
let mut next_b = multiply_permuted_body_by_digits(
kg_body,
&body_tables[image_idx],
&digits_ntt[*digit_idx],
);
add_into(&mut next_b, &b);
b = next_b;
*digit_idx += 1;
}
b
}
#[cfg(test)]
fn switch_with_permuted_body<'a>(
top_row: &PolyMatrixNTT<'a>,
body_row: &PolyMatrixNTT<'a>,
body_table: &NttAutomorphTable,
digits_ntt: &PolyMatrixNTT<'a>,
c2: &PolyMatrixNTT<'a>,
) -> (PolyMatrixNTT<'a>, PolyMatrixNTT<'a>) {
validate_key_parts(top_row, body_row, digits_ntt, c2);
assert_eq!(body_table.indices().len(), top_row.params.poly_len);
let mut delta_a = PolyMatrixNTT::zero(top_row.params, 1, 1);
multiply(&mut delta_a, top_row, digits_ntt);
let mut delta_b = multiply_permuted_body_by_digits(body_row, body_table, digits_ntt);
add_into(&mut delta_b, c2);
(delta_a, delta_b)
}
#[cfg(test)]
fn switch_with_body<'a>(
top_row: &PolyMatrixNTT<'a>,
body_row: &PolyMatrixNTT<'a>,
digits_ntt: &PolyMatrixNTT<'a>,
c2: &PolyMatrixNTT<'a>,
) -> (PolyMatrixNTT<'a>, PolyMatrixNTT<'a>) {
validate_key_parts(top_row, body_row, digits_ntt, c2);
let mut delta_a = PolyMatrixNTT::zero(top_row.params, 1, 1);
multiply(&mut delta_a, top_row, digits_ntt);
let mut delta_b = PolyMatrixNTT::zero(top_row.params, 1, 1);
multiply(&mut delta_b, body_row, digits_ntt);
add_into(&mut delta_b, c2);
(delta_a, delta_b)
}
#[cfg(test)]
fn validate_key_parts(
top_row: &PolyMatrixNTT<'_>,
body_row: &PolyMatrixNTT<'_>,
digits_ntt: &PolyMatrixNTT<'_>,
c2: &PolyMatrixNTT<'_>,
) {
assert_eq!(top_row.rows, 1);
assert_eq!(top_row.cols, body_row.cols);
assert_eq!(body_row.rows, 1);
assert_eq!(digits_ntt.rows, top_row.cols);
assert_eq!(digits_ntt.cols, 1);
assert_eq!(c2.rows, 1);
assert_eq!(c2.cols, 1);
}
fn multiply_permuted_body_by_digits<'a>(
body_row: &PolyMatrixNTT<'a>,
body_table: &NttAutomorphTable,
digits_ntt: &PolyMatrixNTT<'a>,
) -> PolyMatrixNTT<'a> {
assert_eq!(body_row.rows, 1);
assert_eq!(digits_ntt.cols, 1);
assert_eq!(body_row.cols, digits_ntt.rows);
let spiral = body_row.params;
let d = spiral.poly_len;
let body_indices = body_table.indices();
let mut out = PolyMatrixNTT::zero(spiral, 1, 1);
let out_poly = out.get_poly_mut(0, 0);
for crt_idx in 0..spiral.crt_count {
let modulus = u128::from(spiral.moduli[crt_idx]);
let max_product = (modulus - 1) * (modulus - 1);
let can_reduce_once = max_product.checked_mul(body_row.cols as u128).is_some();
let offset = crt_idx * d;
let out_chunk = &mut out_poly[offset..offset + d];
for dst_idx in 0..d {
let src_idx = body_indices[dst_idx] as usize;
let mut acc = 0_u128;
for digit_idx in 0..body_row.cols {
let body_poly = body_row.get_poly(0, digit_idx);
let digit_poly = digits_ntt.get_poly(digit_idx, 0);
let body_chunk = &body_poly[offset..offset + d];
let digit_chunk = &digit_poly[offset..offset + d];
let product = u128::from(body_chunk[src_idx]) * u128::from(digit_chunk[dst_idx]);
acc = if can_reduce_once {
acc + product
} else {
(acc + product) % modulus
};
}
out_chunk[dst_idx] = (acc % modulus) as u64;
}
}
out
}
fn reference_mask_top<'a>(params: &'a RlweParams, mask_seed: [u8; 32]) -> PolyMatrixNTT<'a> {
(-&reference_mask_raw(params, mask_seed)).ntt()
}
#[must_use]
pub fn reference_mask_coeffs(params: &RlweParams, mask_seed: [u8; 32]) -> Vec<Vec<u64>> {
let raw = reference_mask_raw(params, mask_seed);
(0..params.gadget.ell)
.map(|col| raw.get_poly(0, col).to_vec())
.collect()
}
fn reference_mask_raw<'a>(params: &'a RlweParams, mask_seed: [u8; 32]) -> PolyMatrixRaw<'a> {
PolyMatrixRaw::random_rng(
¶ms.spiral,
1,
params.gadget.ell,
&mut ChaCha20Rng::from_seed(mask_seed),
)
}
fn validate_reference_body(
params: &RlweParams,
body: &PolyMatrixNTT<'_>,
label: &'static str,
) -> Result<(), InspiringError> {
if body.rows != 1 || body.cols != params.gadget.ell {
return Err(InspiringError::PreprocessMismatch(format!(
"{label} must have shape 1x{}, got {}x{}",
params.gadget.ell, body.rows, body.cols
)));
}
Ok(())
}
fn build_a_agg<'a>(params: &'a RlweParams, a_tildes: &[Vec<u64>]) -> Vec<PolyMatrixNTT<'a>> {
let spiral = ¶ms.spiral;
let d = params.d;
assert_eq!(a_tildes.len(), d, "preprocess::build_a_agg expects d rows");
if spiral.crt_count != 1 {
return build_a_agg_direct(params, a_tildes);
}
let mut a_hat = vec![0_u64; d * d];
a_hat
.par_chunks_mut(d)
.zip(a_tildes.par_iter())
.for_each(|(dst, src)| {
debug_assert!(src.iter().all(|coeff| *coeff < params.q));
dst.copy_from_slice(src);
ntt_forward(spiral, dst);
});
let mut e_table = vec![0_u64; d * d];
transpose_square(&a_hat, &mut e_table, d);
drop(a_hat);
e_table
.par_chunks_mut(d)
.for_each(|row| ntt_forward(spiral, row));
let mut e_by_slot = vec![0_u64; d * d];
transpose_square(&e_table, &mut e_by_slot, d);
drop(e_table);
let (left_tables, right_tables) = tau_g_power_tables(params, d / 2);
let mut out: Vec<PolyMatrixNTT<'a>> =
(0..d).map(|_| PolyMatrixNTT::zero(spiral, 1, 1)).collect();
out.par_chunks_mut(A_AGG_SLOT_BLOCK)
.enumerate()
.for_each(|(block_idx, out_block)| {
let base = block_idx * A_AGG_SLOT_BLOCK;
for s_start in (0..d).step_by(A_AGG_COEFF_BLOCK) {
let s_end = (s_start + A_AGG_COEFF_BLOCK).min(d);
for (offset, out_poly) in out_block.iter_mut().enumerate() {
let slot = base + offset;
let table = if slot < d / 2 {
&left_tables[slot]
} else {
&right_tables[slot - d / 2]
};
let indices = table.indices();
let dst = out_poly.get_poly_mut(0, 0);
for s in s_start..s_end {
let value = e_by_slot[s * d + indices[s] as usize];
dst[s] = ((u128::from(value) * u128::from(params.d_inv))
% u128::from(params.q)) as u64;
}
}
}
});
out
}
const A_AGG_SLOT_BLOCK: usize = 64;
const A_AGG_COEFF_BLOCK: usize = 32;
fn transpose_square(src: &[u64], dst: &mut [u64], d: usize) {
const TILE: usize = 32;
debug_assert_eq!(src.len(), d * d);
debug_assert_eq!(dst.len(), d * d);
dst.par_chunks_mut(TILE * d)
.enumerate()
.for_each(|(tile_idx, dst_rows)| {
let row_start = tile_idx * TILE;
let rows = dst_rows.len() / d;
for col_start in (0..d).step_by(TILE) {
let col_end = (col_start + TILE).min(d);
for (local_row, row) in (row_start..row_start + rows).enumerate() {
let dst_row = &mut dst_rows[local_row * d..local_row * d + d];
for col in col_start..col_end {
dst_row[col] = src[col * d + row];
}
}
}
});
}
fn build_a_agg_direct<'a>(params: &'a RlweParams, a_tildes: &[Vec<u64>]) -> Vec<PolyMatrixNTT<'a>> {
(0..params.d)
.into_par_iter()
.map(|slot| aggregate_slot(params, a_tildes, slot))
.collect()
}
fn aggregate_slot<'a>(
params: &'a RlweParams,
a_tildes: &[Vec<u64>],
slot: usize,
) -> PolyMatrixNTT<'a> {
let mut out = vec![0_u64; params.d];
let exponent = if slot < params.d / 2 {
tau_g_pow(slot, params.d)
} else {
let two_d = 2 * params.d as u64;
(tau_g_pow(slot - params.d / 2, params.d) * h(params.d)) % two_d
};
for (shift, a_tilde) in a_tildes.iter().enumerate() {
add_shifted_tau(&mut out, a_tilde, exponent, shift, params.q);
}
for coeff in &mut out {
*coeff = (u128::from(*coeff) * u128::from(params.d_inv) % u128::from(params.q)) as u64;
}
let mut raw = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
raw.get_poly_mut(0, 0).copy_from_slice(&out);
to_ntt_alloc(&raw)
}
fn a_tilde_coeffs(params: &RlweParams, a: &[u64]) -> Vec<u64> {
assert_eq!(
a.len(),
params.d,
"preprocess::a_tilde_coeffs expects an LWE vector of length d"
);
let mut out = vec![0_u64; params.d];
out[0] = a[0] % params.q;
for (i, coeff) in a.iter().enumerate().skip(1) {
let reduced = coeff % params.q;
out[params.d - i] = if reduced == 0 { 0 } else { params.q - reduced };
}
out
}
fn add_shifted_tau(out: &mut [u64], poly: &[u64], exponent: u64, shift: usize, q: u64) {
let d = out.len();
debug_assert!(
d.is_power_of_two(),
"add_shifted_tau requires power-of-two d"
);
debug_assert!(
poly.iter().all(|coeff| *coeff < q),
"add_shifted_tau expects a_tilde coefficients already reduced mod q"
);
let d_u64 = d as u64;
let two_d_mask = 2 * d_u64 - 1;
for (source_idx, coeff) in poly.iter().enumerate() {
let reduced = *coeff;
if reduced == 0 {
continue;
}
let exp = (source_idx as u64 * exponent) & two_d_mask;
let mut idx = if exp < d_u64 {
exp as usize
} else {
(exp - d_u64) as usize
};
let mut negate = exp >= d_u64;
idx += shift;
if idx >= d {
idx -= d;
negate = !negate;
}
let term = if negate { q - reduced } else { reduced };
let sum = out[idx] + term;
out[idx] = if sum >= q { sum - q } else { sum };
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::params::GadgetParams;
use spiral_rs::poly::{to_ntt_alloc, PolyMatrixRaw};
fn params() -> RlweParams {
RlweParams::new(
8,
12289,
4,
3.2,
GadgetParams {
bits_per: 3,
ell: 5,
},
)
.expect("valid params")
}
fn zero_ks<'a>(params: &'a RlweParams) -> KeySwitchingMatrix<'a> {
KeySwitchingMatrix {
mat: PolyMatrixNTT::zero(¶ms.spiral, 2, params.gadget.ell),
params,
}
}
fn crs<'a>(params: &'a RlweParams) -> PolyMatrixNTT<'a> {
let mut raw = PolyMatrixRaw::zero(¶ms.spiral, params.d, 1);
for row in 0..params.d {
for col in 0..params.d {
raw.get_poly_mut(row, 0)[col] = (row * params.d + col + 1) as u64;
}
}
to_ntt_alloc(&raw)
}
fn b_scalars(params: &RlweParams) -> Vec<u64> {
(0..params.d)
.map(|idx| (idx as u64 * 17 + 3) % params.q)
.collect()
}
fn ntt_matrix<'a>(
params: &'a RlweParams,
rows: usize,
cols: usize,
seed: u64,
) -> PolyMatrixNTT<'a> {
let mut matrix = PolyMatrixNTT::zero(¶ms.spiral, rows, cols);
for (idx, coeff) in matrix.as_mut_slice().iter_mut().enumerate() {
*coeff = (seed + idx as u64 * 19 + (idx / params.d) as u64 * 7) % params.q;
}
matrix
}
fn packing_keys<'a>(params: &'a RlweParams, seed: u64) -> PackingKeys<'a> {
PackingKeys {
kg_body: ntt_matrix(params, 1, params.gadget.ell, seed),
kh_body: ntt_matrix(
params,
1,
params.gadget.ell,
seed.wrapping_mul(31).wrapping_add(7),
),
}
}
fn params_ell3() -> RlweParams {
RlweParams::new(
8,
12289,
4,
3.2,
GadgetParams {
bits_per: 5,
ell: 3,
},
)
.expect("valid ell=3 params")
}
#[test]
fn accumulate_collapse_term_ell3_specialization_matches_generic() {
let params = params_ell3();
let d = params.d;
let ell = params.gadget.ell;
assert_eq!(ell, 3, "this test must drive the specialized path");
assert_eq!(params.spiral.crt_count, 1);
let images = TopKeyImages::build(¶ms);
let body = ntt_matrix(¶ms, 1, ell, params.q - 5);
let digits = ntt_matrix(¶ms, ell, 1, params.q - 17);
for table in [
Some(&images.kg_body_left_tables[0]),
Some(&images.kg_body_right_tables[0]),
None,
] {
if let Some(table) = table {
assert!(
table.validate_permutation(d),
"hot-path masking requires a genuine permutation of 0..d"
);
}
let term = CollapseTerm {
body: &body,
table,
digits: (&digits).into(),
};
let mut fast = vec![0_u128; d];
let mut reference = vec![0_u128; d];
for _ in 0..2 {
accumulate_collapse_term(¶ms.spiral, &term, &mut fast);
accumulate_collapse_term_digit_outer(¶ms.spiral, &term, &mut reference);
}
assert_eq!(
fast,
reference,
"ell=3 specialization disagrees with the generic path (table: {})",
table.is_some()
);
assert!(fast.iter().any(|v| *v != 0), "all-zero accumulator");
}
}
#[test]
fn cached_automorphism_tables_are_permutations() {
for params in [params(), params_ell3()] {
let images = TopKeyImages::build(¶ms);
for table in images
.kg_body_left_tables
.iter()
.chain(images.kg_body_right_tables.iter())
{
assert!(
table.validate_permutation(params.d),
"cached table is not a permutation of 0..{}",
params.d
);
}
}
}
#[test]
fn accumulate_collapse_term_orderings_agree() {
let params = params();
let d = params.d;
let ell = params.gadget.ell;
let images = TopKeyImages::build(¶ms);
let body = ntt_matrix(¶ms, 1, ell, params.q - 3);
let digits = ntt_matrix(¶ms, ell, 1, params.q - 11);
for table in [Some(&images.kg_body_left_tables[0]), None] {
let term = CollapseTerm {
body: &body,
table,
digits: (&digits).into(),
};
let mut fast = vec![0_u128; d * params.spiral.crt_count];
let mut reference = vec![0_u128; d * params.spiral.crt_count];
for _ in 0..2 {
accumulate_collapse_term(¶ms.spiral, &term, &mut fast);
accumulate_collapse_term_digit_outer(¶ms.spiral, &term, &mut reference);
}
assert_eq!(
fast,
reference,
"slot-outer and digit-outer accumulation disagree (table: {})",
table.is_some()
);
assert!(
fast.iter().any(|v| *v != 0),
"test inputs produced an all-zero accumulator"
);
}
}
#[test]
fn batched_pack_matches_sequential() {
for params in [params(), params_ell3()] {
batched_pack_matches_sequential_at(¶ms);
}
}
fn batched_pack_matches_sequential_at(params: &RlweParams) {
let crs = crs(params);
let pre = QueryPackPreprocessed::build(params, &crs).expect("valid preprocessing");
let top = TopKeyImages::build(params);
for k in [1_usize, 2, 3, 5] {
let keys: Vec<PackingKeys<'_>> = (0..k)
.map(|idx| packing_keys(params, 1_000 + idx as u64 * 977))
.collect();
let blocks: Vec<Vec<u64>> = (0..k)
.map(|idx| {
(0..params.d)
.map(|c| ((c as u64 + 1) * (idx as u64 * 13 + 5) + idx as u64) % params.q)
.collect()
})
.collect();
let expected: Vec<RlweCiphertext<'_>> = blocks
.iter()
.zip(keys.iter())
.map(|(b, key)| {
pre.pack_b_prevalidated(b, key, &top)
.expect("sequential pack succeeds")
})
.collect();
let block_refs: Vec<&[u64]> = blocks.iter().map(|b| b.as_slice()).collect();
let key_refs: Vec<&PackingKeys<'_>> = keys.iter().collect();
let batched = pre
.pack_b_batched_prevalidated(&block_refs, &key_refs, &top)
.expect("batched pack succeeds");
assert_eq!(batched.len(), k, "batch returns one ciphertext per query");
for (idx, (got, want)) in batched.iter().zip(expected.iter()).enumerate() {
assert_eq!(
got.inner.as_slice(),
want.inner.as_slice(),
"batched query {idx} of {k} differs from the sequential result"
);
}
}
}
#[test]
fn batched_pack_rejects_mismatched_lengths() {
let params = params();
let crs = crs(¶ms);
let pre = QueryPackPreprocessed::build(¶ms, &crs).expect("valid preprocessing");
let top = TopKeyImages::build(¶ms);
let key = packing_keys(¶ms, 5);
let block = b_scalars(¶ms);
assert!(matches!(
pre.pack_b_batched_prevalidated(&[block.as_slice()], &[], &top),
Err(InspiringError::LweShape(_))
));
assert!(pre
.pack_b_batched_prevalidated(&[], &[], &top)
.expect("empty batch is not an error")
.is_empty());
let short = vec![0_u64; params.d - 1];
assert!(matches!(
pre.pack_b_batched_prevalidated(&[short.as_slice()], &[&key], &top),
Err(InspiringError::LweShape(_))
));
}
#[test]
fn build_precomputes_affine_collapse_cache() {
let params = params();
let crs = crs(¶ms);
let kg = zero_ks(¶ms);
let kh = zero_ks(¶ms);
let pre = PackPreprocessed::build(¶ms, &crs, &kg, &kh).expect("valid preprocessing");
assert_eq!(pre.collapse_a_final_ntt.rows, 1);
assert_eq!(pre.collapse_a_final_ntt.cols, 1);
assert_eq!(pre.collapse_b_offset_ntt.rows, 1);
assert_eq!(pre.collapse_b_offset_ntt.cols, 1);
}
#[test]
fn build_rejects_wrong_crs_shape() {
let params = params();
let wrong = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
let kg = zero_ks(¶ms);
let kh = zero_ks(¶ms);
assert!(matches!(
PackPreprocessed::build(¶ms, &wrong, &kg, &kh),
Err(InspiringError::PreprocessMismatch(_))
));
}
#[test]
fn top_key_images_cache_matching_body_automorphism_tables() {
let params = params();
let kg_top = reference_mask_top(¶ms, REFERENCE_W_SEED);
let images = TopKeyImages::build(¶ms);
let two_d = 2 * params.d as u64;
let h_d = h(params.d);
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;
let expected_left = crate::automorph::tau_ntt(&kg_top, left_exp);
let expected_right = crate::automorph::tau_ntt(&kg_top, right_exp);
assert_eq!(images.kg_body_left_tables[i].exponent(), left_exp);
assert_eq!(images.kg_body_right_tables[i].exponent(), right_exp);
assert_eq!(images.kg_top_left[i].as_slice(), expected_left.as_slice());
assert_eq!(images.kg_top_right[i].as_slice(), expected_right.as_slice());
}
}
#[test]
fn permuted_body_multiply_matches_materialized_body_image() {
let params = params();
let images = TopKeyImages::build(¶ms);
let body = ntt_matrix(¶ms, 1, params.gadget.ell, 11);
let digits = ntt_matrix(¶ms, params.gadget.ell, 1, 29);
let table = &images.kg_body_right_tables[1];
let materialized_body = apply_tau_ntt_alloc(&body, table);
let mut expected = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
multiply(&mut expected, &materialized_body, &digits);
let actual = multiply_permuted_body_by_digits(&body, table, &digits);
assert_eq!(actual.as_slice(), expected.as_slice());
}
#[test]
fn switch_with_permuted_body_matches_materialized_key_product() {
let params = params();
let images = TopKeyImages::build(¶ms);
let top = ntt_matrix(¶ms, 1, params.gadget.ell, 5);
let body = ntt_matrix(¶ms, 1, params.gadget.ell, 13);
let digits = ntt_matrix(¶ms, params.gadget.ell, 1, 31);
let c2 = ntt_matrix(¶ms, 1, 1, 43);
let table = &images.kg_body_left_tables[2];
let (actual_a, actual_b) = switch_with_permuted_body(&top, &body, table, &digits, &c2);
let materialized_body = apply_tau_ntt_alloc(&body, table);
let mut expected_a = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
multiply(&mut expected_a, &top, &digits);
let mut expected_b = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
multiply(&mut expected_b, &materialized_body, &digits);
add_into(&mut expected_b, &c2);
assert_eq!(actual_a.as_slice(), expected_a.as_slice());
assert_eq!(actual_b.as_slice(), expected_b.as_slice());
}
#[test]
fn switch_with_body_matches_materialized_key_product() {
let params = params();
let top = ntt_matrix(¶ms, 1, params.gadget.ell, 5);
let body = ntt_matrix(¶ms, 1, params.gadget.ell, 13);
let digits = ntt_matrix(¶ms, params.gadget.ell, 1, 31);
let c2 = ntt_matrix(¶ms, 1, 1, 43);
let (actual_a, actual_b) = switch_with_body(&top, &body, &digits, &c2);
let mut expected_a = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
multiply(&mut expected_a, &top, &digits);
let mut expected_b = PolyMatrixNTT::zero(¶ms.spiral, 1, 1);
multiply(&mut expected_b, &body, &digits);
add_into(&mut expected_b, &c2);
assert_eq!(actual_a.as_slice(), expected_a.as_slice());
assert_eq!(actual_b.as_slice(), expected_b.as_slice());
}
fn uploaded_key_fixture() -> (
&'static RlweParams,
QueryPackPreprocessed<'static>,
PackPublicPreprocessed<'static>,
PackingKeys<'static>,
TopKeyImages<'static>,
) {
let params = Box::leak(Box::new(params()));
let crs = crs(params);
let public = PackPublicPreprocessed::build(params, &crs).expect("public preprocess");
let pre = QueryPackPreprocessed::build(params, &crs).expect("preprocess");
let secret_raw = {
let mut raw = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
raw.get_poly_mut(0, 0)[0] = 1;
raw.get_poly_mut(0, 0)[2] = params.q - 1;
raw
};
let secret_ntt = to_ntt_alloc(&secret_raw);
let mut rng = ChaCha20Rng::from_seed([42; 32]);
let keys = PackingKeys::generate_full(params, &secret_ntt, &mut rng);
let top_images = TopKeyImages::build(params);
(params, pre, public, keys, top_images)
}
#[test]
fn pack_b_prevalidated_matches_pack_b() {
let (params, pre, _public, keys, top_images) = uploaded_key_fixture();
let b_scalars = b_scalars(params);
let checked = pre.pack_b(&b_scalars, &keys, &top_images).expect("pack b");
keys.validate(pre.params).expect("keys validate");
top_images
.validate(pre.params)
.expect("top images validate");
let prevalidated = pre
.pack_b_prevalidated(&b_scalars, &keys, &top_images)
.expect("pack b prevalidated");
assert_eq!(prevalidated.inner.as_slice(), checked.inner.as_slice());
}
#[test]
fn query_preprocess_stores_fixed_c1_trace() {
let (params, pre, public, _keys, _top_images) = uploaded_key_fixture();
let expected = precompute_reference_trace(params, public.a_agg);
assert_eq!(pre.collapse_a_final_ntt.rows, 1);
assert_eq!(pre.collapse_a_final_ntt.cols, 1);
assert_eq!(pre.digits_ntt.len(), pre.params.d - 1);
assert_eq!(
pre.collapse_a_final_ntt.as_slice(),
expected.collapse_a_final_ntt.as_slice()
);
assert_eq!(pre.digits_ntt.len(), expected.digits_ntt.len());
for (actual, expected) in pre.digits_ntt.iter().zip(expected.digits_ntt.iter()) {
assert_eq!(actual.as_slice(), expected.as_slice());
}
}
#[test]
fn pack_with_uploaded_key_bodies_returns_rlwe_ciphertext() {
let (params, pre, _public, keys, top_images) = uploaded_key_fixture();
let b_scalars = b_scalars(params);
let ct = pre.pack_b(&b_scalars, &keys, &top_images).expect("pack b");
let mut b_tilde = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
for (idx, b) in b_scalars.iter().copied().enumerate() {
b_tilde.get_poly_mut(0, 0)[idx] = b;
}
let expected_b = collapse_uploaded_body_b(
params,
to_ntt_alloc(&b_tilde),
&keys.kg_body,
&keys.kh_body,
&top_images,
&pre.digits_ntt,
);
let expected = RlweCiphertext {
inner: stack_ntt(&pre.collapse_a_final_ntt, &expected_b),
};
assert_eq!(ct.inner.rows, 2);
assert_eq!(ct.inner.cols, 1);
assert_eq!(ct.inner.as_slice(), expected.inner.as_slice());
}
fn production_like_params() -> RlweParams {
RlweParams::new(
128,
72_057_594_037_641_217,
1 << 14,
6.4,
GadgetParams {
bits_per: 19,
ell: 3,
},
)
.expect("valid production-like params")
}
fn random_crs<'a>(params: &'a RlweParams, seed: u64) -> PolyMatrixNTT<'a> {
let mut rng = ChaCha20Rng::seed_from_u64(seed);
let mut raw = PolyMatrixRaw::zero(¶ms.spiral, params.d, 1);
for coeff in raw.as_mut_slice().iter_mut() {
*coeff = rand_chacha::rand_core::RngCore::next_u64(&mut rng) % params.q;
}
to_ntt_alloc(&raw)
}
#[test]
fn fused_collapse_matches_stepwise_cascade() {
let params = production_like_params();
assert!(
fused_accumulator_fits(¶ms, params.gadget.ell),
"the fused path must be the one under test here"
);
let crs = random_crs(¶ms, 0x_C0_11_AB_5E);
let pre = QueryPackPreprocessed::build(¶ms, &crs).expect("preprocess");
let top_images = TopKeyImages::build(¶ms);
let mut rng = ChaCha20Rng::from_seed([7; 32]);
let secret_ntt = to_ntt_alloc(&PolyMatrixRaw::random_rng(¶ms.spiral, 1, 1, &mut rng));
let keys = PackingKeys::generate_full(¶ms, &secret_ntt, &mut rng);
let mut b_tilde = PolyMatrixRaw::zero(¶ms.spiral, 1, 1);
for coeff in b_tilde.get_poly_mut(0, 0).iter_mut() {
*coeff = rand_chacha::rand_core::RngCore::next_u64(&mut rng) % params.q;
}
let b_ntt = to_ntt_alloc(&b_tilde);
let fused = collapse_uploaded_body_b(
¶ms,
b_ntt.clone(),
&keys.kg_body,
&keys.kh_body,
&top_images,
&pre.digits_ntt,
);
let stepwise = collapse_uploaded_body_b_stepwise(
¶ms,
b_ntt,
&keys.kg_body,
&keys.kh_body,
&top_images,
&pre.digits_ntt,
);
assert_eq!(fused.as_slice(), stepwise.as_slice());
}
#[test]
fn fused_accumulator_bound_gates_on_q_and_ell() {
let production = production_like_params();
assert!(fused_accumulator_fits(&production, 3));
let wide = RlweParams {
q: (1 << 63) - 25,
..production
};
assert!(!fused_accumulator_fits(&wide, 3));
}
#[test]
fn build_a_agg_matches_direct_transform() {
for params in [params(), production_like_params()] {
let mut rng = ChaCha20Rng::seed_from_u64(0x_A6_6E_60);
let a_tildes: Vec<Vec<u64>> = (0..params.d)
.map(|_| {
(0..params.d)
.map(|_| rand_chacha::rand_core::RngCore::next_u64(&mut rng) % params.q)
.collect()
})
.collect();
let fast = build_a_agg(¶ms, &a_tildes);
let direct = build_a_agg_direct(¶ms, &a_tildes);
assert_eq!(fast.len(), direct.len());
for (slot, (fast, direct)) in fast.iter().zip(direct.iter()).enumerate() {
assert_eq!(
fast.as_slice(),
direct.as_slice(),
"aggregate slot {slot} differs at d={}",
params.d
);
}
}
}
#[test]
fn transpose_square_moves_every_element() {
let d = 64;
let src: Vec<u64> = (0..(d * d) as u64).collect();
let mut dst = vec![0_u64; d * d];
transpose_square(&src, &mut dst, d);
for row in 0..d {
for col in 0..d {
assert_eq!(dst[row * d + col], src[col * d + row]);
}
}
}
}