// SPDX-License-Identifier: AGPL-3.0-or-later
// FHE Key Switching Shader
//
// **Purpose**: Decompose ciphertext for key switching
//
// **Algorithm**: Base-B digit decomposition
// ```
// For coefficient c and base B:
// d₀ = c mod B
// d₁ = (c / B) mod B
// d₂ = (c / B²) mod B
// ...
// dₗ = (c / B^L) mod B
// ```
//
// **Performance**: O(L·n) where L is decomposition levels
@group(0) @binding(0) var<storage, read> input: array<u32>; // u64 as 2xu32
@group(0) @binding(1) var<storage, read_write> output: array<u32>;
struct Params {
degree: u32,
decomp_base: u32,
decomp_levels: u32,
modulus_lo: u32,
modulus_hi: u32,
_padding: vec3<u32>,
}
@group(0) @binding(2) var<uniform> params: Params;
// ============================================================================
// U64 Helpers
// ============================================================================
struct U64 {
lo: u32,
hi: u32,
}
fn load_u64(idx: u32) -> U64 {
return U64(input[idx * 2u], input[idx * 2u + 1u]);
}
fn store_u64(idx: u32, val: U64) {
output[idx * 2u] = val.lo;
output[idx * 2u + 1u] = val.hi;
}
fn u64_from_parts(lo: u32, hi: u32) -> U64 {
return U64(lo, hi);
}
// Divide u64 by u32
fn u64_div_u32(a: U64, b: u32) -> U64 {
let a_val = (u64(a.hi) << 32u) | u64(a.lo);
let quotient = a_val / u64(b);
return U64(u32(quotient & 0xFFFFFFFFu), u32(quotient >> 32u));
}
// Modulo u64 by u32
fn u64_mod_u32(a: U64, b: u32) -> u32 {
let a_val = (u64(a.hi) << 32u) | u64(a.lo);
return u32(a_val % u64(b));
}
// ============================================================================
// Base-B Decomposition
// ============================================================================
/// Decompose coefficient into base-B digits
///
/// Returns the k-th digit: (coeff / B^k) mod B
fn decompose_digit(coeff: U64, base: u32, level: u32) -> u32 {
var current = coeff;
// Divide by B^level
for (var i = 0u; i < level; i = i + 1u) {
current = u64_div_u32(current, base);
}
// Take modulo B
return u64_mod_u32(current, base);
}
// ============================================================================
// Main Compute Kernels
// ============================================================================
/// Decompose ciphertext component into base-B representation
@compute @workgroup_size(256)
fn decompose_base_b(
@builtin(global_invocation_id) global_id: vec3<u32>,
) {
let coeff_idx = global_id.x;
if (coeff_idx >= params.degree) {
return;
}
// Load coefficient to decompose
let coeff = load_u64(coeff_idx);
// For simplified version, just copy input to output
// Full implementation would store L digits per coefficient
// in a (degree * L) output buffer
// Decompose into base-B digits (demonstration)
// In production: store all digits for multiplication with switching keys
let digit_0 = decompose_digit(coeff, params.decomp_base, 0u);
// For now, store first digit (full version stores all L digits)
// This demonstrates the decomposition algorithm
store_u64(coeff_idx, U64(digit_0, 0u));
}
/// Accumulate switched ciphertext components
///
/// Phase 3 requirement: Full key switching accumulation needs:
/// 1. Switching key storage buffers (L × degree × 2 polynomials)
/// 2. NTT-domain multiplication (via fhe_ntt.wgsl)
/// 3. Multi-level accumulation across all L decomposition digits
///
/// Current: Identity pass-through (decompose kernel outputs digit[0]).
/// The decomposition + pass-through structure is correct and tested.
/// Full accumulation will be wired when the FHE key infrastructure
/// (key generation, serialization, NTT-domain key storage) is implemented.
@compute @workgroup_size(256)
fn accumulate_switched(
@builtin(global_invocation_id) global_id: vec3<u32>,
) {
let coeff_idx = global_id.x;
if (coeff_idx >= params.degree) {
return;
}
// Load decomposed digit
let digit = load_u64(coeff_idx);
// Identity pass-through: preserves the decomposed coefficient.
// When switching keys are available, this becomes:
// var acc = u64_from_u32(0u);
// for level 0..L:
// acc = u64_add(acc, u64_mul_mod(digit[level], switch_key[level][coeff_idx], m, mu));
// store_u64(coeff_idx, acc);
store_u64(coeff_idx, digit);
}