add benchmark params for packing 10 or 1000 lwes

keyswitch and lwe trace packing keyswitch

tfhe/benches/core_crypto/ks_bench.rs

@@ -9,6 +9,7 @@ use tfhe::core_crypto::prelude::*;
 use tfhe::keycache::NamedParam;
 use tfhe::shortint::parameters::{
     COMP_PARAM_MESSAGE_2_CARRY_2_KS_PBS_TUNIFORM_2M64,
+    MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_1000,
     PARAM_MESSAGE_1_CARRY_1_KS_PBS_GAUSSIAN_2M64, PARAM_MESSAGE_2_CARRY_2_KS_PBS_GAUSSIAN_2M64,
     PARAM_MESSAGE_2_CARRY_2_KS_PBS_TUNIFORM_2M64, PARAM_MESSAGE_3_CARRY_3_KS_PBS_GAUSSIAN_2M64,
 };
@@ -119,6 +120,13 @@ fn benchmark_compression_parameters() -> Vec<(String, CryptoParametersRecord<u64
     )]
 }
 
+fn benchmark_trace_packing_parameters() -> Vec<(String, CryptoParametersRecord<u64>)> {
+    vec![(
+        MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_1000.name(),
+        MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_1000.into(),
+    )]
+}
+
 fn keyswitch<Scalar: UnsignedTorus + CastInto<usize> + Serialize>(
     criterion: &mut Criterion,
     parameters: &[(String, CryptoParametersRecord<Scalar>)],
@@ -297,6 +305,109 @@ fn packing_keyswitch<Scalar, F>(
     }
 }
 
+fn trace_packing_keyswitch<Scalar: UnsignedTorus + CastInto<usize> + Serialize>(
+    criterion: &mut Criterion,
+    bench_name: &str,
+    parameters: &[(String, CryptoParametersRecord<Scalar>)],
+) {
+    let bench_name = format!("core_crypto::{bench_name}");
+    let mut bench_group = criterion.benchmark_group(&bench_name);
+
+    // Create the PRNG
+    let mut seeder = new_seeder();
+    let seeder = seeder.as_mut();
+    let mut encryption_generator =
+        EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
+    let mut secret_generator =
+        SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
+    
+    for (name, params) in parameters.iter() {
+        let lwe_dimension = params.lwe_dimension.unwrap();
+        let packing_ks_glwe_dimension = params.packing_ks_glwe_dimension.unwrap();
+        let packing_ks_polynomial_size = params.packing_ks_polynomial_size.unwrap();
+        let packing_ks_decomp_base_log = params.packing_ks_base_log.unwrap();
+        let packing_ks_decomp_level_count = params.packing_ks_level.unwrap();
+        let ciphertext_modulus = params.ciphertext_modulus.unwrap();
+        let count = params.lwe_per_glwe.unwrap();
+
+        let lwe_sk =
+            allocate_and_generate_new_binary_lwe_secret_key(lwe_dimension, &mut secret_generator);
+        
+        let mut glwe_sk = GlweSecretKey::new_empty_key(Scalar::ZERO, packing_ks_glwe_dimension, packing_ks_polynomial_size);
+
+        generate_tpksk_output_glwe_secret_key(
+            &lwe_sk,
+            &mut glwe_sk,
+            ciphertext_modulus,
+            &mut secret_generator,
+        );
+
+        let lwe_tpksk = allocate_and_generate_new_lwe_trace_packing_keyswitch_key(
+            lwe_dimension.to_lwe_size(),
+            &glwe_sk,
+            packing_ks_decomp_base_log,
+            packing_ks_decomp_level_count,
+            params.packing_ks_key_noise_distribution.unwrap(),
+            ciphertext_modulus,
+            &mut encryption_generator,
+        );
+
+        //let delta = (ciphertext_modulus.get_custom_modulus / params.message_modulus.unwrap() as u128).cast_into();
+        let lwe_plaintext_list = PlaintextList::new(Scalar::ZERO, PlaintextCount(count.0));
+        let mut lwe_list = LweCiphertextList::new(
+            Scalar::ZERO,
+            lwe_dimension.to_lwe_size(),
+            count,
+            ciphertext_modulus,
+        );
+        encrypt_lwe_ciphertext_list(
+            &lwe_sk,
+            &mut lwe_list,
+            &lwe_plaintext_list,
+            params.lwe_noise_distribution.unwrap(),
+            &mut encryption_generator,
+        );
+        
+        let mut output_glwe_ciphertext = GlweCiphertext::new(
+            Scalar::ZERO,
+            packing_ks_glwe_dimension.to_glwe_size(),
+            packing_ks_polynomial_size,
+            ciphertext_modulus,
+        );
+
+        let mut indices = vec![0usize; count.0];
+        for (index, item) in indices.iter_mut().enumerate() {
+            *item = index;
+        }
+
+        let id = format!("{bench_name}::{name}");
+        {
+            bench_group.bench_function(&id, |b| {
+                b.iter(|| {
+                    trace_packing_keyswitch_lwe_ciphertext_list_into_glwe_ciphertext(
+                        &lwe_tpksk,
+                        &mut output_glwe_ciphertext,
+                        &lwe_list,
+                        &indices,
+                    );
+                    black_box(&mut output_glwe_ciphertext);
+                })
+            });
+        }
+
+        let bit_size = (params.message_modulus.unwrap_or(2) as u64).ilog2();
+        write_to_json(
+            &id,
+            *params,
+            name,
+            "trace_packing_ks",
+            &OperatorType::Atomic,
+            bit_size,
+            vec![bit_size],
+        );
+    }
+}
+
 #[cfg(feature = "gpu")]
 mod cuda {
     use crate::benchmark_parameters_64bits;
@@ -553,7 +664,32 @@ pub fn packing_keyswitch_group() {
     );
 }
 
+pub fn trace_packing_keyswitch_group() {
+    let mut criterion: Criterion<_> = (Criterion::default()
+        .sample_size(10)
+        .measurement_time(std::time::Duration::from_secs(120)))
+    .configure_from_args();
+    trace_packing_keyswitch(
+        &mut criterion,
+        "trace_packing_keyswitch",
+        &benchmark_trace_packing_parameters(),
+    );
+}
+
+pub fn not_trace_packing_keyswitch_group() {
+    let mut criterion: Criterion<_> = (Criterion::default()
+        .sample_size(10)
+        .measurement_time(std::time::Duration::from_secs(120)))
+    .configure_from_args();
+    packing_keyswitch(
+        &mut criterion,
+        "not_trace_packing_keyswitch",
+        &benchmark_trace_packing_parameters(),
+        keyswitch_lwe_ciphertext_list_and_pack_in_glwe_ciphertext,
+    );
+}
+
 #[cfg(not(feature = "gpu"))]
-criterion_main!(keyswitch_group, packing_keyswitch_group);
+criterion_main!(keyswitch_group, packing_keyswitch_group, trace_packing_keyswitch_group, not_trace_packing_keyswitch_group);
 #[cfg(feature = "gpu")]
 criterion_main!(cuda_keyswitch_group);

tfhe/benches/utilities.rs

@@ -43,7 +43,7 @@ pub mod shortint_utils {
     #[cfg(not(feature = "gpu"))]
     use tfhe::shortint::parameters::PARAM_MULTI_BIT_GROUP_2_MESSAGE_2_CARRY_2_KS_PBS_GAUSSIAN_2M64;
     use tfhe::shortint::parameters::{
-        ShortintKeySwitchingParameters, PARAM_MESSAGE_2_CARRY_2_KS_PBS_TUNIFORM_2M64,
+        GlweMultParameters, ShortintKeySwitchingParameters, PARAM_MESSAGE_2_CARRY_2_KS_PBS_TUNIFORM_2M64
     };
     use tfhe::shortint::{ClassicPBSParameters, PBSParameters, ShortintParameterSet};
 
@@ -164,6 +164,25 @@ pub mod shortint_utils {
             }
         }
     }
+
+    impl From<GlweMultParameters> for CryptoParametersRecord<u64> {
+        fn from(glwe_mult_params: GlweMultParameters) -> Self {
+            CryptoParametersRecord {
+                lwe_dimension: Some(glwe_mult_params.lwe_dimension),
+                packing_ks_level: Some(glwe_mult_params.packing_ks_level),
+                packing_ks_base_log: Some(glwe_mult_params.packing_ks_base_log),
+                packing_ks_polynomial_size: Some(glwe_mult_params.packing_ks_polynomial_size),
+                packing_ks_glwe_dimension: Some(glwe_mult_params.packing_ks_glwe_dimension),
+                lwe_per_glwe: Some(glwe_mult_params.lwe_per_glwe),
+                packing_ks_key_noise_distribution: Some(glwe_mult_params.packing_ks_key_noise_distribution),
+                lwe_noise_distribution: Some(glwe_mult_params.lwe_noise_distribution),
+                ciphertext_modulus: Some(glwe_mult_params.ciphertext_modulus),
+                message_modulus: Some(glwe_mult_params.message_modulus.0),
+                carry_modulus: Some(glwe_mult_params.carry_modulus.0),
+                ..Default::default()
+            }
+        }
+    }
 }
 
 #[allow(unused_imports)]

tfhe/src/core_crypto/algorithms/glwe_keyswitch.rs

@@ -0,0 +1,304 @@
+//! Module containing primitives pertaining to [`GLWE ciphertext
+//! keyswitch`](`GlweKeyswitchKey#glwe-keyswitch`).
+
+use crate::core_crypto::algorithms::polynomial_algorithms::*;
+use crate::core_crypto::commons::math::decomposition::{
+    SignedDecomposer, SignedDecomposerNonNative,
+};
+use crate::core_crypto::commons::numeric::UnsignedInteger;
+use crate::core_crypto::commons::traits::*;
+use crate::core_crypto::entities::*;
+
+/// Keyswitch a [`GLWE ciphertext`](`GlweCiphertext`) encrypted under a
+/// [`GLWE secret key`](`GlweSecretKey`) to another [`GLWE secret key`](`GlweSecretKey`).
+///
+/// # Formal Definition
+///
+/// See [`GLWE keyswitch key`](`GlweKeyswitchKey#glwe-keyswitch`).
+///
+/// # Example
+///
+/// ```
+/// use tfhe::core_crypto::prelude::*;
+///
+/// // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
+/// // computations
+/// // Define parameters for GlweKeyswitchKey creation
+/// let input_glwe_dimension = GlweDimension(2);
+/// let poly_size = PolynomialSize(512);
+/// let glwe_noise_distribution = Gaussian::from_dispersion_parameter(
+///     StandardDev(0.00000000000000000000007069849454709433),
+///     0.0,
+/// );
+/// let output_glwe_dimension = GlweDimension(1);
+/// let decomp_base_log = DecompositionBaseLog(21);
+/// let decomp_level_count = DecompositionLevelCount(2);
+/// let ciphertext_modulus = CiphertextModulus::new_native();
+/// let delta = 1 << 59;
+///
+/// // Create the PRNG
+/// let mut seeder = new_seeder();
+/// let seeder = seeder.as_mut();
+/// let mut encryption_generator =
+///     EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
+/// let mut secret_generator =
+///     SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
+///
+/// // Create the LweSecretKey
+/// let input_glwe_secret_key = allocate_and_generate_new_binary_glwe_secret_key(
+///     input_glwe_dimension,
+///     poly_size,
+///     &mut secret_generator,
+/// );
+/// let output_glwe_secret_key = allocate_and_generate_new_binary_glwe_secret_key(
+///     output_glwe_dimension,
+///     poly_size,
+///     &mut secret_generator,
+/// );
+///
+/// let ksk = allocate_and_generate_new_glwe_keyswitch_key(
+///     &input_glwe_secret_key,
+///     &output_glwe_secret_key,
+///     decomp_base_log,
+///     decomp_level_count,
+///     glwe_noise_distribution,
+///     ciphertext_modulus,
+///     &mut encryption_generator,
+/// );
+///
+/// // Create the plaintext
+/// let msg = 3u64;
+/// let plaintext_list = PlaintextList::new(msg * delta, PlaintextCount(poly_size.0));
+///
+/// // Create a new GlweCiphertext
+/// let mut input_glwe = GlweCiphertext::new(
+///     0u64,
+///     input_glwe_dimension.to_glwe_size(),
+///     poly_size,
+///     ciphertext_modulus,
+/// );
+///
+/// encrypt_glwe_ciphertext(
+///     &input_glwe_secret_key,
+///     &mut input_glwe,
+///     &plaintext_list,
+///     glwe_noise_distribution,
+///     &mut encryption_generator,
+/// );
+///
+/// let mut output_glwe = GlweCiphertext::new(
+///     0u64,
+///     output_glwe_secret_key.glwe_dimension().to_glwe_size(),
+///     output_glwe_secret_key.polynomial_size(),
+///     ciphertext_modulus,
+/// );
+///
+/// keyswitch_glwe_ciphertext(&ksk, &input_glwe, &mut output_glwe);
+///
+/// // Round and remove encoding
+/// // First create a decomposer working on the high 5 bits corresponding to our encoding.
+/// let decomposer = SignedDecomposer::new(DecompositionBaseLog(5), DecompositionLevelCount(1));
+///
+/// let mut output_plaintext_list = PlaintextList::new(0u64, plaintext_list.plaintext_count());
+///
+/// decrypt_glwe_ciphertext(
+///     &output_glwe_secret_key,
+///     &output_glwe,
+///     &mut output_plaintext_list,
+/// );
+///
+/// // Get the raw vector
+/// let mut cleartext_list = output_plaintext_list.into_container();
+/// // Remove the encoding
+/// cleartext_list
+///     .iter_mut()
+///     .for_each(|elt| *elt = decomposer.decode_plaintext(*elt));
+/// // Get the list immutably
+/// let cleartext_list = cleartext_list;
+///
+/// // Check we recovered the original message for each plaintext we encrypted
+/// cleartext_list.iter().for_each(|&elt| assert_eq!(elt, msg));
+/// ```
+pub fn keyswitch_glwe_ciphertext<Scalar, KSKCont, InputCont, OutputCont>(
+    glwe_keyswitch_key: &GlweKeyswitchKey<KSKCont>,
+    input_glwe_ciphertext: &GlweCiphertext<InputCont>,
+    output_glwe_ciphertext: &mut GlweCiphertext<OutputCont>,
+) where
+    Scalar: UnsignedInteger,
+    KSKCont: Container<Element = Scalar>,
+    InputCont: Container<Element = Scalar>,
+    OutputCont: ContainerMut<Element = Scalar>,
+{
+    if glwe_keyswitch_key
+        .ciphertext_modulus()
+        .is_compatible_with_native_modulus()
+    {
+        keyswitch_glwe_ciphertext_native_mod_compatible(
+            glwe_keyswitch_key,
+            input_glwe_ciphertext,
+            output_glwe_ciphertext,
+        )
+    } else {
+        keyswitch_glwe_ciphertext_other_mod(
+            glwe_keyswitch_key,
+            input_glwe_ciphertext,
+            output_glwe_ciphertext,
+        )
+    }
+}
+
+pub fn keyswitch_glwe_ciphertext_native_mod_compatible<Scalar, KSKCont, InputCont, OutputCont>(
+    glwe_keyswitch_key: &GlweKeyswitchKey<KSKCont>,
+    input_glwe_ciphertext: &GlweCiphertext<InputCont>,
+    output_glwe_ciphertext: &mut GlweCiphertext<OutputCont>,
+) where
+    Scalar: UnsignedInteger,
+    KSKCont: Container<Element = Scalar>,
+    InputCont: Container<Element = Scalar>,
+    OutputCont: ContainerMut<Element = Scalar>,
+{
+    assert!(
+        glwe_keyswitch_key.input_key_glwe_dimension()
+            == input_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+        "Mismatched input GlweDimension. \
+        GlweKeyswitchKey input GlweDimension: {:?}, input GlweCiphertext GlweDimension {:?}.",
+        glwe_keyswitch_key.input_key_glwe_dimension(),
+        input_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+    );
+    assert!(
+        glwe_keyswitch_key.output_key_glwe_dimension()
+            == output_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+        "Mismatched output GlweDimension. \
+        GlweKeyswitchKey output GlweDimension: {:?}, output GlweCiphertext GlweDimension {:?}.",
+        glwe_keyswitch_key.output_key_glwe_dimension(),
+        output_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == input_glwe_ciphertext.polynomial_size(),
+        "Mismatched input PolynomialSize. \
+        GlweKeyswithcKey input PolynomialSize: {:?}, input GlweCiphertext PolynomialSize {:?}.",
+        glwe_keyswitch_key.polynomial_size(),
+        input_glwe_ciphertext.polynomial_size(),
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == output_glwe_ciphertext.polynomial_size(),
+        "Mismatched output PolynomialSize. \
+        GlweKeyswitchKey output PolynomialSize: {:?}, output GlweCiphertext PolynomialSize {:?}.",
+        glwe_keyswitch_key.polynomial_size(),
+        output_glwe_ciphertext.polynomial_size(),
+    );
+    assert!(glwe_keyswitch_key
+        .ciphertext_modulus()
+        .is_compatible_with_native_modulus());
+
+    // Clear the output ciphertext, as it will get updated gradually
+    output_glwe_ciphertext.as_mut().fill(Scalar::ZERO);
+
+    // Copy the input body to the output ciphertext
+    polynomial_wrapping_add_assign(
+        &mut output_glwe_ciphertext.get_mut_body().as_mut_polynomial(),
+        &input_glwe_ciphertext.get_body().as_polynomial(),
+    );
+
+    // We instantiate a decomposer
+    let decomposer = SignedDecomposer::new(
+        glwe_keyswitch_key.decomposition_base_log(),
+        glwe_keyswitch_key.decomposition_level_count(),
+    );
+
+    for (keyswitch_key_block, input_mask_element) in glwe_keyswitch_key
+        .iter()
+        .zip(input_glwe_ciphertext.get_mask().as_polynomial_list().iter())
+    {
+        let mut decomposition_iter = decomposer.decompose_slice(input_mask_element.as_ref());
+        // loop over the number of levels
+        for level_key_ciphertext in keyswitch_key_block.iter() {
+            let decomposed = decomposition_iter.next_term().unwrap();
+            polynomial_list_wrapping_sub_scalar_mul_assign(
+                &mut output_glwe_ciphertext.as_mut_polynomial_list(),
+                &level_key_ciphertext.as_polynomial_list(),
+                &Polynomial::from_container(decomposed.as_slice()),
+            );
+        }
+    }
+}
+
+pub fn keyswitch_glwe_ciphertext_other_mod<Scalar, KSKCont, InputCont, OutputCont>(
+    glwe_keyswitch_key: &GlweKeyswitchKey<KSKCont>,
+    input_glwe_ciphertext: &GlweCiphertext<InputCont>,
+    output_glwe_ciphertext: &mut GlweCiphertext<OutputCont>,
+) where
+    Scalar: UnsignedInteger,
+    KSKCont: Container<Element = Scalar>,
+    InputCont: Container<Element = Scalar>,
+    OutputCont: ContainerMut<Element = Scalar>,
+{
+    assert!(
+        glwe_keyswitch_key.input_key_glwe_dimension()
+            == input_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+        "Mismatched input GlweDimension. \
+        GlweKeyswitchKey input GlweDimension: {:?}, input GlweCiphertext GlweDimension {:?}.",
+        glwe_keyswitch_key.input_key_glwe_dimension(),
+        input_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+    );
+    assert!(
+        glwe_keyswitch_key.output_key_glwe_dimension()
+            == output_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+        "Mismatched output GlweDimension. \
+        GlweKeyswitchKey output GlweDimension: {:?}, output GlweCiphertext GlweDimension {:?}.",
+        glwe_keyswitch_key.output_key_glwe_dimension(),
+        output_glwe_ciphertext.glwe_size().to_glwe_dimension(),
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == input_glwe_ciphertext.polynomial_size(),
+        "Mismatched input PolynomialSize. \
+        GlweKeyswithcKey input PolynomialSize: {:?}, input GlweCiphertext PolynomialSize {:?}.",
+        glwe_keyswitch_key.polynomial_size(),
+        input_glwe_ciphertext.polynomial_size(),
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == output_glwe_ciphertext.polynomial_size(),
+        "Mismatched output PolynomialSize. \
+        GlweKeyswitchKey output PolynomialSize: {:?}, output GlweCiphertext PolynomialSize {:?}.",
+        glwe_keyswitch_key.polynomial_size(),
+        output_glwe_ciphertext.polynomial_size(),
+    );
+    let ciphertext_modulus = glwe_keyswitch_key.ciphertext_modulus();
+    assert!(!ciphertext_modulus.is_compatible_with_native_modulus());
+
+    // Clear the output ciphertext, as it will get updated gradually
+    output_glwe_ciphertext.as_mut().fill(Scalar::ZERO);
+
+    // Copy the input body to the output ciphertext (no need to use non native addition here)
+    polynomial_wrapping_add_assign(
+        &mut output_glwe_ciphertext.get_mut_body().as_mut_polynomial(),
+        &input_glwe_ciphertext.get_body().as_polynomial(),
+    );
+
+    // We instantiate a decomposer
+    let decomposer = SignedDecomposerNonNative::new(
+        glwe_keyswitch_key.decomposition_base_log(),
+        glwe_keyswitch_key.decomposition_level_count(),
+        ciphertext_modulus,
+    );
+
+    let mut scalar_poly = Polynomial::new(Scalar::ZERO, input_glwe_ciphertext.polynomial_size());
+
+    for (keyswitch_key_block, input_mask_element) in glwe_keyswitch_key
+        .iter()
+        .zip(input_glwe_ciphertext.get_mask().as_polynomial_list().iter())
+    {
+        let mut decomposition_iter = decomposer.decompose_slice(input_mask_element.as_ref());
+        // loop over the number of levels
+        for level_key_ciphertext in keyswitch_key_block.iter() {
+            let decomposed = decomposition_iter.next_term().unwrap();
+            decomposed.modular_value(scalar_poly.as_mut());
+            polynomial_list_wrapping_sub_scalar_mul_assign_custom_mod(
+                &mut output_glwe_ciphertext.as_mut_polynomial_list(),
+                &level_key_ciphertext.as_polynomial_list(),
+                &scalar_poly,
+                ciphertext_modulus.get_custom_modulus().cast_into(),
+            );
+        }
+    }
+}

tfhe/src/core_crypto/algorithms/glwe_keyswitch_key_generation.rs

@@ -0,0 +1,352 @@
+//! Module containing primitives pertaining to [`GLWE keyswitch key generation`](`GlweKeyswitchKey`)
+
+use crate::core_crypto::algorithms::slice_algorithms::slice_wrapping_scalar_div_assign;
+use crate::core_crypto::algorithms::*;
+use crate::core_crypto::commons::generators::EncryptionRandomGenerator;
+use crate::core_crypto::commons::math::decomposition::{
+    DecompositionLevel, DecompositionTermSlice, DecompositionTermSliceNonNative,
+};
+use crate::core_crypto::commons::math::random::{Distribution, Uniform};
+use crate::core_crypto::commons::parameters::*;
+use crate::core_crypto::commons::traits::*;
+use crate::core_crypto::entities::*;
+
+/// Fill a [`GLWE keyswitch key`](`GlweKeyswitchKey`) with an actual keyswitching key constructed
+/// from an input and an output key [`GLWE secret key`](`GlweSecretKey`).
+///
+/// ```
+/// use tfhe::core_crypto::prelude::*;
+///
+/// // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
+/// // computations
+/// // Define parameters for GlweKeyswitchKey creation
+/// let input_glwe_dimension = GlweDimension(2);
+/// let polynomial_size = PolynomialSize(1024);
+/// let glwe_noise_distribution =
+///     Gaussian::from_dispersion_parameter(StandardDev(0.000007069849454709433), 0.0);
+/// let output_glwe_dimension = GlweDimension(1);
+/// let decomp_base_log = DecompositionBaseLog(3);
+/// let decomp_level_count = DecompositionLevelCount(5);
+/// let ciphertext_modulus = CiphertextModulus::new_native();
+///
+/// // Create the PRNG
+/// let mut seeder = new_seeder();
+/// let seeder = seeder.as_mut();
+/// let mut encryption_generator =
+///     EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
+/// let mut secret_generator =
+///     SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
+///
+/// // Create the GlweSecretKey
+/// let input_glwe_secret_key = allocate_and_generate_new_binary_glwe_secret_key(
+///     input_glwe_dimension,
+///     polynomial_size,
+///     &mut secret_generator,
+/// );
+/// let output_glwe_secret_key = allocate_and_generate_new_binary_glwe_secret_key(
+///     output_glwe_dimension,
+///     polynomial_size,
+///     &mut secret_generator,
+/// );
+///
+/// let mut ksk = GlweKeyswitchKey::new(
+///     0u64,
+///     decomp_base_log,
+///     decomp_level_count,
+///     input_glwe_dimension,
+///     output_glwe_dimension,
+///     polynomial_size,
+///     ciphertext_modulus,
+/// );
+///
+/// generate_glwe_keyswitch_key(
+///     &input_glwe_secret_key,
+///     &output_glwe_secret_key,
+///     &mut ksk,
+///     glwe_noise_distribution,
+///     &mut encryption_generator,
+/// );
+///
+/// assert!(!ksk.as_ref().iter().all(|&x| x == 0));
+/// ```
+pub fn generate_glwe_keyswitch_key<
+    Scalar,
+    NoiseDistribution,
+    InputKeyCont,
+    OutputKeyCont,
+    KSKeyCont,
+    Gen,
+>(
+    input_glwe_sk: &GlweSecretKey<InputKeyCont>,
+    output_glwe_sk: &GlweSecretKey<OutputKeyCont>,
+    glwe_keyswitch_key: &mut GlweKeyswitchKey<KSKeyCont>,
+    noise_distribution: NoiseDistribution,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    InputKeyCont: Container<Element = Scalar>,
+    OutputKeyCont: Container<Element = Scalar>,
+    KSKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    let ciphertext_modulus = glwe_keyswitch_key.ciphertext_modulus();
+
+    if ciphertext_modulus.is_compatible_with_native_modulus() {
+        generate_glwe_keyswitch_key_native_mod_compatible(
+            input_glwe_sk,
+            output_glwe_sk,
+            glwe_keyswitch_key,
+            noise_distribution,
+            generator,
+        )
+    } else {
+        generate_glwe_keyswitch_key_other_mod(
+            input_glwe_sk,
+            output_glwe_sk,
+            glwe_keyswitch_key,
+            noise_distribution,
+            generator,
+        )
+    }
+}
+
+pub fn generate_glwe_keyswitch_key_native_mod_compatible<
+    Scalar,
+    NoiseDistribution,
+    InputKeyCont,
+    OutputKeyCont,
+    KSKeyCont,
+    Gen,
+>(
+    input_glwe_sk: &GlweSecretKey<InputKeyCont>,
+    output_glwe_sk: &GlweSecretKey<OutputKeyCont>,
+    glwe_keyswitch_key: &mut GlweKeyswitchKey<KSKeyCont>,
+    noise_distribution: NoiseDistribution,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    InputKeyCont: Container<Element = Scalar>,
+    OutputKeyCont: Container<Element = Scalar>,
+    KSKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    assert!(
+        glwe_keyswitch_key.input_key_glwe_dimension() == input_glwe_sk.glwe_dimension(),
+        "The destination GlweKeyswitchKey input GlweDimension is not equal \
+    to the input GlweSecretKey GlweDimension. Destination: {:?}, input: {:?}",
+        glwe_keyswitch_key.input_key_glwe_dimension(),
+        input_glwe_sk.glwe_dimension()
+    );
+    assert!(
+        glwe_keyswitch_key.output_key_glwe_dimension() == output_glwe_sk.glwe_dimension(),
+        "The destination GlweKeyswitchKey output GlweDimension is not equal \
+    to the output GlweSecretKey GlweDimension. Destination: {:?}, output: {:?}",
+        glwe_keyswitch_key.output_key_glwe_dimension(),
+        input_glwe_sk.glwe_dimension()
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == input_glwe_sk.polynomial_size(),
+        "The destination GlweKeyswitchKey input PolynomialSize is not equal \
+     to the input GlweSecretKey PolynomialSize. Destination: {:?}, input: {:?}",
+        glwe_keyswitch_key.polynomial_size(),
+        input_glwe_sk.polynomial_size(),
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == output_glwe_sk.polynomial_size(),
+        "The destination GlweKeyswitchKey output PolynomialSize is not equal \
+    to the output GlweSecretKey PolynomialSize. Destination: {:?}, output: {:?}",
+        glwe_keyswitch_key.polynomial_size(),
+        output_glwe_sk.polynomial_size(),
+    );
+
+    let decomp_base_log = glwe_keyswitch_key.decomposition_base_log();
+    let decomp_level_count = glwe_keyswitch_key.decomposition_level_count();
+    let ciphertext_modulus = glwe_keyswitch_key.ciphertext_modulus();
+    assert!(ciphertext_modulus.is_compatible_with_native_modulus());
+
+    // Iterate over the input key elements and the destination glwe_keyswitch_key memory
+    for (input_key_polynomial, mut keyswitch_key_block) in input_glwe_sk
+        .as_polynomial_list()
+        .iter()
+        .zip(glwe_keyswitch_key.iter_mut())
+    {
+        // The plaintexts used to encrypt a key element will be stored in this buffer
+        let mut decomposition_polynomials_buffer = PolynomialList::new(
+            Scalar::ZERO,
+            input_glwe_sk.polynomial_size(),
+            PolynomialCount(decomp_level_count.0),
+        );
+
+        // We fill the buffer with the powers of the key elmements
+        for (level, mut message_polynomial) in (1..=decomp_level_count.0)
+            .rev()
+            .map(DecompositionLevel)
+            .zip(decomposition_polynomials_buffer.as_mut_view().iter_mut())
+        {
+            let term =
+                DecompositionTermSlice::new(level, decomp_base_log, input_key_polynomial.as_ref());
+            term.fill_slice_with_recomposition_summand(message_polynomial.as_mut());
+            slice_wrapping_scalar_div_assign(
+                message_polynomial.as_mut(),
+                ciphertext_modulus.get_power_of_two_scaling_to_native_torus(),
+            );
+        }
+
+        let decomposition_plaintexts_buffer =
+            PlaintextList::from_container(decomposition_polynomials_buffer.into_container());
+
+        encrypt_glwe_ciphertext_list(
+            output_glwe_sk,
+            &mut keyswitch_key_block,
+            &decomposition_plaintexts_buffer,
+            noise_distribution,
+            generator,
+        );
+    }
+}
+
+pub fn generate_glwe_keyswitch_key_other_mod<
+    Scalar,
+    NoiseDistribution,
+    InputKeyCont,
+    OutputKeyCont,
+    KSKeyCont,
+    Gen,
+>(
+    input_glwe_sk: &GlweSecretKey<InputKeyCont>,
+    output_glwe_sk: &GlweSecretKey<OutputKeyCont>,
+    glwe_keyswitch_key: &mut GlweKeyswitchKey<KSKeyCont>,
+    noise_distribution: NoiseDistribution,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    InputKeyCont: Container<Element = Scalar>,
+    OutputKeyCont: Container<Element = Scalar>,
+    KSKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    assert!(
+        glwe_keyswitch_key.input_key_glwe_dimension() == input_glwe_sk.glwe_dimension(),
+        "The destination GlweKeyswitchKey input GlweDimension is not equal \
+    to the input GlweSecretKey GlweDimension. Destination: {:?}, input: {:?}",
+        glwe_keyswitch_key.input_key_glwe_dimension(),
+        input_glwe_sk.glwe_dimension()
+    );
+    assert!(
+        glwe_keyswitch_key.output_key_glwe_dimension() == output_glwe_sk.glwe_dimension(),
+        "The destination GlweKeyswitchKey output GlweDimension is not equal \
+    to the output GlweSecretKey GlweDimension. Destination: {:?}, output: {:?}",
+        glwe_keyswitch_key.output_key_glwe_dimension(),
+        input_glwe_sk.glwe_dimension()
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == input_glwe_sk.polynomial_size(),
+        "The destination GlweKeyswitchKey input PolynomialSize is not equal \
+     to the input GlweSecretKey PolynomialSize. Destination: {:?}, input: {:?}",
+        glwe_keyswitch_key.polynomial_size(),
+        input_glwe_sk.polynomial_size(),
+    );
+    assert!(
+        glwe_keyswitch_key.polynomial_size() == output_glwe_sk.polynomial_size(),
+        "The destination GlweKeyswitchKey output PolynomialSize is not equal \
+    to the output GlweSecretKey PolynomialSize. Destination: {:?}, output: {:?}",
+        glwe_keyswitch_key.polynomial_size(),
+        output_glwe_sk.polynomial_size(),
+    );
+
+    let decomp_base_log = glwe_keyswitch_key.decomposition_base_log();
+    let decomp_level_count = glwe_keyswitch_key.decomposition_level_count();
+    let ciphertext_modulus = glwe_keyswitch_key.ciphertext_modulus();
+    assert!(!ciphertext_modulus.is_compatible_with_native_modulus());
+
+    // Iterate over the input key elements and the destination glwe_keyswitch_key memory
+    for (input_key_polynomial, mut keyswitch_key_block) in input_glwe_sk
+        .as_polynomial_list()
+        .iter()
+        .zip(glwe_keyswitch_key.iter_mut())
+    {
+        // The plaintexts used to encrypt a key element will be stored in this buffer
+        let mut decomposition_polynomials_buffer = PolynomialList::new(
+            Scalar::ZERO,
+            input_glwe_sk.polynomial_size(),
+            PolynomialCount(decomp_level_count.0),
+        );
+
+        // We fill the buffer with the powers of the key elmements
+        for (level, mut message_polynomial) in (1..=decomp_level_count.0)
+            .rev()
+            .map(DecompositionLevel)
+            .zip(decomposition_polynomials_buffer.as_mut_view().iter_mut())
+        {
+            let term = DecompositionTermSliceNonNative::new(
+                level,
+                decomp_base_log,
+                input_key_polynomial.as_ref(),
+                ciphertext_modulus,
+            );
+            term.to_approximate_recomposition_summand(message_polynomial.as_mut());
+        }
+
+        let decomposition_plaintexts_buffer =
+            PlaintextList::from_container(decomposition_polynomials_buffer.into_container());
+
+        encrypt_glwe_ciphertext_list(
+            output_glwe_sk,
+            &mut keyswitch_key_block,
+            &decomposition_plaintexts_buffer,
+            noise_distribution,
+            generator,
+        );
+    }
+}
+
+/// Allocate a new [`GLWE keyswitch key`](`GlweKeyswitchKey`) and fill it with an actual
+/// keyswitching key constructed from an input and an output
+/// [`GLWE secret key`](`GlweSecretKey`).
+///
+/// See [`keyswitch_glwe_ciphertext`] for usage.
+pub fn allocate_and_generate_new_glwe_keyswitch_key<
+    Scalar,
+    NoiseDistribution,
+    InputKeyCont,
+    OutputKeyCont,
+    Gen,
+>(
+    input_glwe_sk: &GlweSecretKey<InputKeyCont>,
+    output_glwe_sk: &GlweSecretKey<OutputKeyCont>,
+    decomp_base_log: DecompositionBaseLog,
+    decomp_level_count: DecompositionLevelCount,
+    noise_distribution: NoiseDistribution,
+    ciphertext_modulus: CiphertextModulus<Scalar>,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) -> GlweKeyswitchKeyOwned<Scalar>
+where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    InputKeyCont: Container<Element = Scalar>,
+    OutputKeyCont: Container<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    let mut new_glwe_keyswitch_key = GlweKeyswitchKeyOwned::new(
+        Scalar::ZERO,
+        decomp_base_log,
+        decomp_level_count,
+        input_glwe_sk.glwe_dimension(),
+        output_glwe_sk.glwe_dimension(),
+        output_glwe_sk.polynomial_size(),
+        ciphertext_modulus,
+    );
+
+    generate_glwe_keyswitch_key(
+        input_glwe_sk,
+        output_glwe_sk,
+        &mut new_glwe_keyswitch_key,
+        noise_distribution,
+        generator,
+    );
+
+    new_glwe_keyswitch_key
+}

tfhe/src/core_crypto/algorithms/glwe_relinearization_key_generation.rs

@@ -0,0 +1,164 @@
+//! Module containing primitives pertaining to [`GLWE relinearization key
+//! generation`](`GlweRelinearizationKey`).
+
+use crate::core_crypto::algorithms::polynomial_algorithms::*;
+use crate::core_crypto::algorithms::*;
+use crate::core_crypto::commons::generators::EncryptionRandomGenerator;
+use crate::core_crypto::commons::math::random::{Distribution, Uniform};
+use crate::core_crypto::commons::parameters::*;
+use crate::core_crypto::commons::traits::*;
+use crate::core_crypto::entities::*;
+use crate::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount, PolynomialCount};
+
+/// Fill a [`GLWE Relinearization key`](`GlweRelinearizationKey`)
+/// with an actual key.
+///
+/// # Example
+///
+/// ```
+/// use tfhe::core_crypto::prelude::*;
+///
+/// // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
+/// // computations
+/// // Define parameters for GlweCiphertext creation
+/// let glwe_size = GlweSize(3);
+/// let polynomial_size = PolynomialSize(1024);
+/// let decomp_base_log = DecompositionBaseLog(3);
+/// let decomp_level_count = DecompositionLevelCount(7);
+/// let glwe_noise_distribution =
+///     Gaussian::from_dispersion_parameter(StandardDev(0.00000000000000029403601535432533), 0.0);
+/// let ciphertext_modulus = CiphertextModulus::new_native();
+///
+/// // Create the PRNG
+/// let mut seeder = new_seeder();
+/// let seeder = seeder.as_mut();
+/// let mut encryption_generator =
+///     EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
+/// let mut secret_generator =
+///     SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
+///
+/// // Create the GlweSecretKey
+/// let glwe_secret_key: GlweSecretKey<Vec<u64>> = allocate_and_generate_new_binary_glwe_secret_key(
+///     glwe_size.to_glwe_dimension(),
+///     polynomial_size,
+///     &mut secret_generator,
+/// );
+///
+/// let relin_key = allocate_and_generate_glwe_relinearization_key(
+///     &glwe_secret_key,
+///     decomp_base_log,
+///     decomp_level_count,
+///     glwe_noise_distribution,
+///     ciphertext_modulus,
+///     &mut encryption_generator,
+/// );
+///
+/// assert!(!relin_key.as_ref().iter().all(|&x| x == 0));
+/// ```
+pub fn generate_glwe_relinearization_key<
+    Scalar,
+    NoiseDistribution,
+    GlweKeyCont,
+    RelinKeyCont,
+    Gen,
+>(
+    glwe_secret_key: &GlweSecretKey<GlweKeyCont>,
+    glwe_relinearization_key: &mut GlweRelinearizationKey<RelinKeyCont>,
+    noise_distribution: NoiseDistribution,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    GlweKeyCont: Container<Element = Scalar>,
+    RelinKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    assert_eq!(
+        glwe_secret_key.glwe_dimension(),
+        glwe_relinearization_key.glwe_dimension()
+    );
+    assert_eq!(
+        glwe_secret_key.polynomial_size(),
+        glwe_relinearization_key.polynomial_size()
+    );
+
+    // We retrieve decomposition arguments
+    let glwe_dimension = glwe_relinearization_key.glwe_dimension();
+    let decomp_level_count = glwe_relinearization_key.decomposition_level_count();
+    let decomp_base_log = glwe_relinearization_key.decomposition_base_log();
+    let polynomial_size = glwe_relinearization_key.polynomial_size();
+    let ciphertext_modulus = glwe_relinearization_key.ciphertext_modulus();
+
+    // Construct the "glwe secret key" we want to keyswitch from, this is made up of the square
+    // and cross terms appearing when tensoring the glwe_secret_key with itself
+    let mut input_sk_poly_list = PolynomialList::new(
+        Scalar::ZERO,
+        polynomial_size,
+        PolynomialCount(glwe_dimension.0 * (glwe_dimension.0 + 1) / 2),
+    );
+    let mut input_sk_poly_list_iter = input_sk_poly_list.iter_mut();
+
+    // We compute the polynomial multiplication in the same way,
+    // regardless of the ciphertext modulus.
+    for i in 0..glwe_dimension.0 {
+        for j in 0..i + 1 {
+            let mut input_key_pol = input_sk_poly_list_iter.next().unwrap();
+            polynomial_wrapping_sub_mul_assign(
+                &mut input_key_pol,
+                &glwe_secret_key.as_polynomial_list().get(i),
+                &glwe_secret_key.as_polynomial_list().get(j),
+            );
+        }
+    }
+
+    let input_glwe_sk = GlweSecretKey::from_container(input_sk_poly_list.as_ref(), polynomial_size);
+
+    let mut glwe_ks_key = GlweKeyswitchKey::from_container(
+        glwe_relinearization_key.as_mut(),
+        decomp_base_log,
+        decomp_level_count,
+        glwe_dimension.to_glwe_size(),
+        polynomial_size,
+        ciphertext_modulus,
+    );
+
+    generate_glwe_keyswitch_key(
+        &input_glwe_sk,
+        glwe_secret_key,
+        &mut glwe_ks_key,
+        noise_distribution,
+        generator,
+    );
+}
+
+pub fn allocate_and_generate_glwe_relinearization_key<Scalar, NoiseDistribution, KeyCont, Gen>(
+    glwe_secret_key: &GlweSecretKey<KeyCont>,
+    decomp_base_log: DecompositionBaseLog,
+    decomp_level_count: DecompositionLevelCount,
+    noise_distribution: NoiseDistribution,
+    ciphertext_modulus: CiphertextModulus<Scalar>,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) -> GlweRelinearizationKeyOwned<Scalar>
+where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    KeyCont: Container<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    let mut glwe_relinearization_key = GlweRelinearizationKeyOwned::new(
+        Scalar::ZERO,
+        decomp_base_log,
+        decomp_level_count,
+        glwe_secret_key.glwe_dimension().to_glwe_size(),
+        glwe_secret_key.polynomial_size(),
+        ciphertext_modulus,
+    );
+    generate_glwe_relinearization_key(
+        glwe_secret_key,
+        &mut glwe_relinearization_key,
+        noise_distribution,
+        generator,
+    );
+
+    glwe_relinearization_key
+}

tfhe/src/core_crypto/algorithms/lwe_trace_packing_keyswitch_key_generation.rs

@@ -0,0 +1,419 @@
+//! Module containing primitives pertaining to [`LWE trace packing keyswitch key
+//! generation`](`LweTracePackingKeyswitchKey`).
+
+use crate::core_crypto::algorithms::*;
+use crate::core_crypto::commons::generators::{EncryptionRandomGenerator, SecretRandomGenerator};
+use crate::core_crypto::commons::math::random::{
+    Distribution, RandomGenerable, Uniform, UniformBinary,
+};
+use crate::core_crypto::commons::parameters::*;
+use crate::core_crypto::commons::traits::*;
+use crate::core_crypto::entities::*;
+use crate::core_crypto::prelude::polynomial_algorithms::apply_automorphism_wrapping_add_assign;
+use crate::core_crypto::prelude::CiphertextModulus;
+
+/// Fill a [`GLWE secret key`](`GlweSecretKey`) with an actual key derived from an
+/// [`LWE secret key`](`LweSecretKey`) for use in the [`LWE trace packing keyswitch key`]
+/// (`LweTracePackingKeyswitchKey`)
+pub fn generate_tpksk_output_glwe_secret_key<Scalar, InputKeyCont, OutputKeyCont, Gen>(
+    input_lwe_secret_key: &LweSecretKey<InputKeyCont>,
+    output_glwe_secret_key: &mut GlweSecretKey<OutputKeyCont>,
+    ciphertext_modulus: CiphertextModulus<Scalar>,
+    generator: &mut SecretRandomGenerator<Gen>,
+) where
+    Scalar: RandomGenerable<UniformBinary> + UnsignedInteger,
+    InputKeyCont: Container<Element = Scalar>,
+    OutputKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    let lwe_dimension = input_lwe_secret_key.lwe_dimension();
+    let glwe_dimension = output_glwe_secret_key.glwe_dimension();
+    let glwe_poly_size = output_glwe_secret_key.polynomial_size();
+
+    assert!(
+        lwe_dimension.0 <= glwe_dimension.0 * glwe_poly_size.0,
+        "Mismatched between input_lwe_secret_key dimension {:?} and number of coefficients of \
+        output_glwe_secret_key {:?}.",
+        lwe_dimension.0,
+        glwe_dimension.0 * glwe_poly_size.0
+    );
+
+    let glwe_key_container = output_glwe_secret_key.as_mut();
+
+    if lwe_dimension.0 < glwe_dimension.0 * glwe_poly_size.0 {
+        let additional_key_bits = LweSecretKey::generate_new_binary(
+            LweDimension(glwe_dimension.0 * glwe_poly_size.0 - lwe_dimension.0),
+            generator,
+        );
+        let extended_lwe_key_iter = input_lwe_secret_key
+            .as_ref()
+            .iter()
+            .chain(additional_key_bits.as_ref().iter());
+        for (index, lwe_key_bit) in extended_lwe_key_iter.enumerate() {
+            if index % glwe_poly_size.0 == 0 {
+                glwe_key_container[index] = *lwe_key_bit;
+            } else {
+                let rem = index % glwe_poly_size.0;
+                let quo = index / glwe_poly_size.0;
+                let new_index = (quo + 1) * glwe_poly_size.0 - rem;
+                if ciphertext_modulus.is_compatible_with_native_modulus() {
+                    glwe_key_container[new_index] = lwe_key_bit.wrapping_neg();
+                } else {
+                    glwe_key_container[new_index] = lwe_key_bit.wrapping_neg_custom_mod(
+                        ciphertext_modulus.get_custom_modulus().cast_into(),
+                    );
+                }
+            }
+        }
+    } else {
+        let extended_lwe_key_iter = input_lwe_secret_key.as_ref().iter();
+        for (index, lwe_key_bit) in extended_lwe_key_iter.enumerate() {
+            if index % glwe_poly_size.0 == 0 {
+                glwe_key_container[index] = *lwe_key_bit;
+            } else {
+                let rem = index % glwe_poly_size.0;
+                let quo = index / glwe_poly_size.0;
+                let new_index = (quo + 1) * glwe_poly_size.0 - rem;
+                if ciphertext_modulus.is_compatible_with_native_modulus() {
+                    glwe_key_container[new_index] = lwe_key_bit.wrapping_neg();
+                } else {
+                    glwe_key_container[new_index] = lwe_key_bit.wrapping_neg_custom_mod(
+                        ciphertext_modulus.get_custom_modulus().cast_into(),
+                    );
+                }
+            }
+        }
+    }
+}
+
+/// Fill an [`LWE trace packing keyswitch key`](`LweTracePackingKeyswitchKey`)
+/// with an actual key.
+///
+/// # Example
+///
+/// ```
+/// use tfhe::core_crypto::prelude::*;
+///
+/// // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
+/// // computations
+/// // Define parameters for GlweCiphertext creation
+/// let glwe_size = GlweSize(2);
+/// let polynomial_size = PolynomialSize(1024);
+/// let lwe_dimension = LweDimension(900);
+/// let noise_distribution =
+///     Gaussian::from_dispersion_parameter(StandardDev(0.00000000000000029403601535432533), 0.0);
+/// let ciphertext_modulus = CiphertextModulus::try_new((1 << 64) - (1 << 32) + 1).unwrap();
+///
+/// let mut seeder = new_seeder();
+/// let mut secret_generator =
+///     SecretRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed());
+/// let lwe_secret_key =
+///     allocate_and_generate_new_binary_lwe_secret_key(lwe_dimension, &mut secret_generator);
+///
+/// let mut glwe_secret_key =
+///     GlweSecretKey::new_empty_key(0u64, glwe_size.to_glwe_dimension(), polynomial_size);
+///
+/// generate_tpksk_output_glwe_secret_key(
+///     &lwe_secret_key,
+///     &mut glwe_secret_key,
+///     ciphertext_modulus,
+///     &mut secret_generator,
+/// );
+///
+/// let decomp_base_log = DecompositionBaseLog(2);
+/// let decomp_level_count = DecompositionLevelCount(8);
+/// let mut seeder = new_seeder();
+/// let seeder = seeder.as_mut();
+/// let mut encryption_generator =
+///     EncryptionRandomGenerator::<ActivatedRandomGenerator>::new(seeder.seed(), seeder);
+///
+/// let mut lwe_tpksk = LweTracePackingKeyswitchKey::new(
+///     0u64,
+///     decomp_base_log,
+///     decomp_level_count,
+///     lwe_dimension.to_lwe_size(),
+///     glwe_size,
+///     polynomial_size,
+///     ciphertext_modulus,
+/// );
+///
+/// generate_lwe_trace_packing_keyswitch_key(
+///     &glwe_secret_key,
+///     &mut lwe_tpksk,
+///     noise_distribution,
+///     &mut encryption_generator,
+/// );
+///
+/// assert!(!lwe_tpksk.as_ref().iter().all(|&x| x == 0));
+/// ```
+pub fn generate_lwe_trace_packing_keyswitch_key<
+    Scalar,
+    NoiseDistribution,
+    InputKeyCont,
+    KSKeyCont,
+    Gen,
+>(
+    input_glwe_secret_key: &GlweSecretKey<InputKeyCont>,
+    lwe_tpksk: &mut LweTracePackingKeyswitchKey<KSKeyCont>,
+    noise_distribution: NoiseDistribution,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    InputKeyCont: Container<Element = Scalar>,
+    KSKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    let ciphertext_modulus = lwe_tpksk.ciphertext_modulus();
+    if ciphertext_modulus.is_compatible_with_native_modulus() {
+        generate_lwe_trace_packing_keyswitch_key_native_mod_compatible(
+            input_glwe_secret_key,
+            lwe_tpksk,
+            noise_distribution,
+            generator,
+        )
+    } else {
+        generate_lwe_trace_packing_keyswitch_key_other_mod(
+            input_glwe_secret_key,
+            lwe_tpksk,
+            noise_distribution,
+            generator,
+        )
+    }
+}
+
+pub fn generate_lwe_trace_packing_keyswitch_key_native_mod_compatible<
+    Scalar,
+    NoiseDistribution,
+    InputKeyCont,
+    KSKeyCont,
+    Gen,
+>(
+    input_glwe_secret_key: &GlweSecretKey<InputKeyCont>,
+    lwe_tpksk: &mut LweTracePackingKeyswitchKey<KSKeyCont>,
+    noise_distribution: NoiseDistribution,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    InputKeyCont: Container<Element = Scalar>,
+    KSKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    assert_eq!(
+        input_glwe_secret_key.glwe_dimension(),
+        lwe_tpksk.output_glwe_key_dimension()
+    );
+    assert_eq!(
+        input_glwe_secret_key.polynomial_size(),
+        lwe_tpksk.polynomial_size()
+    );
+
+    let ciphertext_modulus = lwe_tpksk.ciphertext_modulus();
+    assert!(ciphertext_modulus.is_compatible_with_native_modulus());
+
+    // We retrieve decomposition arguments
+    let glwe_dimension = lwe_tpksk.output_glwe_key_dimension();
+    let decomp_level_count = lwe_tpksk.decomposition_level_count();
+    let decomp_base_log = lwe_tpksk.decomposition_base_log();
+    let polynomial_size = lwe_tpksk.polynomial_size();
+
+    let automorphism_index_iter = 1..=polynomial_size.log2().0;
+
+    //let gen_iter = generator
+    //    .try_fork_from_config(lwe_tpksk.encryption_fork_config(Uniform, noise_distribution))
+    //    .unwrap();
+
+    // loop over the before key blocks
+    //for ((auto_index, glwe_keyswitch_block), mut loop_generator) in automorphism_index_iter
+    for (auto_index, glwe_keyswitch_block) in automorphism_index_iter
+        .zip(lwe_tpksk.iter_mut())
+        //.zip(gen_iter)
+    {
+        let mut auto_glwe_sk_poly_list = PolynomialList::new(
+            Scalar::ZERO,
+            input_glwe_secret_key.polynomial_size(),
+            PolynomialCount(input_glwe_secret_key.glwe_dimension().0),
+        );
+        let input_key_poly_list = input_glwe_secret_key.as_polynomial_list();
+        let input_key_poly_iter = input_key_poly_list.iter();
+        let auto_key_poly_iter = auto_glwe_sk_poly_list.iter_mut();
+        for (mut auto_key_poly, input_key_poly) in auto_key_poly_iter.zip(input_key_poly_iter) {
+            apply_automorphism_wrapping_add_assign(
+                &mut auto_key_poly,
+                &input_key_poly,
+                2_usize.pow(auto_index as u32) + 1,
+            );
+        }
+        let mut glwe_ksk = GlweKeyswitchKey::from_container(
+            glwe_keyswitch_block.into_container(),
+            decomp_base_log,
+            decomp_level_count,
+            glwe_dimension.to_glwe_size(),
+            polynomial_size,
+            ciphertext_modulus,
+        );
+        let auto_glwe_sk =
+            GlweSecretKey::from_container(auto_glwe_sk_poly_list.into_container(), polynomial_size);
+        generate_glwe_keyswitch_key(
+            &auto_glwe_sk,
+            input_glwe_secret_key,
+            &mut glwe_ksk,
+            noise_distribution,
+            //&mut loop_generator,
+            generator,
+        );
+    }
+}
+
+pub fn generate_lwe_trace_packing_keyswitch_key_other_mod<
+    Scalar,
+    NoiseDistribution,
+    InputKeyCont,
+    KSKeyCont,
+    Gen,
+>(
+    input_glwe_secret_key: &GlweSecretKey<InputKeyCont>,
+    lwe_tpksk: &mut LweTracePackingKeyswitchKey<KSKeyCont>,
+    noise_distribution: NoiseDistribution,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    InputKeyCont: Container<Element = Scalar>,
+    KSKeyCont: ContainerMut<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    assert_eq!(
+        input_glwe_secret_key.glwe_dimension(),
+        lwe_tpksk.output_glwe_key_dimension()
+    );
+    assert_eq!(
+        input_glwe_secret_key.polynomial_size(),
+        lwe_tpksk.polynomial_size()
+    );
+
+    let ciphertext_modulus = lwe_tpksk.ciphertext_modulus();
+    assert!(!ciphertext_modulus.is_compatible_with_native_modulus());
+
+    // Convert the input glwe_ secret key to a polynomial list
+    // modulo the native modulus while keeping the sign
+    let mut native_glwe_secret_key_poly_list = PolynomialList::new(
+        Scalar::ZERO,
+        input_glwe_secret_key.polynomial_size(),
+        PolynomialCount(input_glwe_secret_key.glwe_dimension().0),
+    );
+    // Need to go from custom to native modulus while preserving the sign
+    let modulus_as_scalar: Scalar = ciphertext_modulus.get_custom_modulus().cast_into();
+    input_glwe_secret_key
+        .as_ref()
+        .iter()
+        .zip(native_glwe_secret_key_poly_list.as_mut().iter_mut())
+        .for_each(|(&src, dst)| {
+            if src > modulus_as_scalar / Scalar::TWO {
+                *dst = src.wrapping_sub(modulus_as_scalar)
+            } else {
+                *dst = src
+            }
+        });
+
+    // We retrieve decomposition arguments
+    let glwe_dimension = lwe_tpksk.output_glwe_key_dimension();
+    let decomp_level_count = lwe_tpksk.decomposition_level_count();
+    let decomp_base_log = lwe_tpksk.decomposition_base_log();
+    let polynomial_size = lwe_tpksk.polynomial_size();
+
+    let automorphism_index_iter = 1..=polynomial_size.log2().0;
+
+    let gen_iter = generator
+        .try_fork_from_config(lwe_tpksk.encryption_fork_config(Uniform, noise_distribution))
+        .unwrap();
+
+    // loop over the before key blocks
+    for ((auto_index, glwe_keyswitch_block), mut loop_generator) in automorphism_index_iter
+        .zip(lwe_tpksk.iter_mut())
+        .zip(gen_iter)
+    {
+        let mut auto_glwe_sk_poly_list = PolynomialList::new(
+            Scalar::ZERO,
+            input_glwe_secret_key.polynomial_size(),
+            PolynomialCount(input_glwe_secret_key.glwe_dimension().0),
+        );
+        let native_key_poly_iter = native_glwe_secret_key_poly_list.iter();
+        let auto_key_poly_iter = auto_glwe_sk_poly_list.iter_mut();
+        for (mut auto_key_poly, native_key_poly) in auto_key_poly_iter.zip(native_key_poly_iter) {
+            apply_automorphism_wrapping_add_assign(
+                &mut auto_key_poly,
+                &native_key_poly,
+                2_usize.pow(auto_index as u32) + 1,
+            );
+        }
+
+        let mut glwe_ksk = GlweKeyswitchKey::from_container(
+            glwe_keyswitch_block.into_container(),
+            decomp_base_log,
+            decomp_level_count,
+            glwe_dimension.to_glwe_size(),
+            polynomial_size,
+            ciphertext_modulus,
+        );
+        let auto_glwe_sk =
+            GlweSecretKey::from_container(auto_glwe_sk_poly_list.into_container(), polynomial_size);
+        generate_glwe_keyswitch_key(
+            &auto_glwe_sk,
+            input_glwe_secret_key,
+            &mut glwe_ksk,
+            noise_distribution,
+            &mut loop_generator,
+        );
+    }
+}
+
+/// Allocate a new [`LWE trace packing keyswitch key`](`LweTracePackingKeyswitchKey`) and fill it
+/// with an actual trace packing keyswitching key constructed from an associated input [`GLWE secret
+/// key`](`GlweSecretKey`).
+///
+/// See  [`generate_tpksk_output_glwe_secret_key`](`generate_tpksk_output_glwe_secret_key`)
+/// for more details.
+///
+/// See [`trace_packing_keyswitch_lwe_ciphertext_list_into_glwe_ciphertext`](`super::trace_packing_keyswitch_lwe_ciphertext_list_into_glwe_ciphertext`)
+/// for usage.
+pub fn allocate_and_generate_new_lwe_trace_packing_keyswitch_key<
+    Scalar,
+    NoiseDistribution,
+    KeyCont,
+    Gen,
+>(
+    lwe_size: LweSize,
+    glwe_secret_key: &GlweSecretKey<KeyCont>,
+    decomp_base_log: DecompositionBaseLog,
+    decomp_level_count: DecompositionLevelCount,
+    noise_distribution: NoiseDistribution,
+    ciphertext_modulus: CiphertextModulus<Scalar>,
+    generator: &mut EncryptionRandomGenerator<Gen>,
+) -> LweTracePackingKeyswitchKeyOwned<Scalar>
+where
+    Scalar: Encryptable<Uniform, NoiseDistribution>,
+    NoiseDistribution: Distribution,
+    KeyCont: Container<Element = Scalar>,
+    Gen: ByteRandomGenerator,
+{
+    let mut new_lwe_trace_packing_keyswitch_key = LweTracePackingKeyswitchKeyOwned::new(
+        Scalar::ZERO,
+        decomp_base_log,
+        decomp_level_count,
+        lwe_size,
+        glwe_secret_key.glwe_dimension().to_glwe_size(),
+        glwe_secret_key.polynomial_size(),
+        ciphertext_modulus,
+    );
+
+    generate_lwe_trace_packing_keyswitch_key(
+        glwe_secret_key,
+        &mut new_lwe_trace_packing_keyswitch_key,
+        noise_distribution,
+        generator,
+    );
+
+    new_lwe_trace_packing_keyswitch_key
+}

tfhe/src/core_crypto/algorithms/mod.rs

@@ -5,9 +5,13 @@
 pub mod ggsw_conversion;
 pub mod ggsw_encryption;
 pub mod glwe_encryption;
+pub mod glwe_keyswitch;
+pub mod glwe_keyswitch_key_generation;
 pub mod glwe_linear_algebra;
+pub mod glwe_relinearization_key_generation;
 pub mod glwe_sample_extraction;
 pub mod glwe_secret_key_generation;
+pub mod glwe_tensor_product;
 pub mod lwe_bootstrap_key_conversion;
 pub mod lwe_bootstrap_key_generation;
 pub mod lwe_compact_ciphertext_list_expansion;
@@ -26,6 +30,8 @@ pub mod lwe_private_functional_packing_keyswitch_key_generation;
 pub mod lwe_programmable_bootstrapping;
 pub mod lwe_public_key_generation;
 pub mod lwe_secret_key_generation;
+pub mod lwe_trace_packing_keyswitch;
+pub mod lwe_trace_packing_keyswitch_key_generation;
 pub mod lwe_wopbs;
 #[cfg(feature = "zk-pok")]
 pub mod lwe_zero_knowledge_verification;
@@ -53,9 +59,13 @@ pub(crate) mod test;
 pub use ggsw_conversion::*;
 pub use ggsw_encryption::*;
 pub use glwe_encryption::*;
+pub use glwe_keyswitch::*;
+pub use glwe_keyswitch_key_generation::*;
 pub use glwe_linear_algebra::*;
+pub use glwe_relinearization_key_generation::*;
 pub use glwe_sample_extraction::*;
 pub use glwe_secret_key_generation::*;
+pub use glwe_tensor_product::*;
 pub use lwe_bootstrap_key_conversion::*;
 pub use lwe_bootstrap_key_generation::*;
 pub use lwe_compact_ciphertext_list_expansion::*;
@@ -74,6 +84,8 @@ pub use lwe_private_functional_packing_keyswitch_key_generation::*;
 pub use lwe_programmable_bootstrapping::*;
 pub use lwe_public_key_generation::*;
 pub use lwe_secret_key_generation::*;
+pub use lwe_trace_packing_keyswitch::*;
+pub use lwe_trace_packing_keyswitch_key_generation::*;
 pub use lwe_wopbs::*;
 #[cfg(feature = "zk-pok")]
 pub use lwe_zero_knowledge_verification::*;

tfhe/src/core_crypto/algorithms/polynomial_algorithms.rs

@@ -334,6 +334,30 @@ pub fn polynomial_wrapping_add_mul_assign_custom_mod<Scalar, OutputCont, InputCo
     }
 }
 
+/// Multiply a polynomial by a scalar modulo a custom modulus.
+///
+/// # Example
+///
+/// ```
+/// use tfhe::core_crypto::algorithms::polynomial_algorithms::*;
+/// use tfhe::core_crypto::entities::*;
+/// let mut pol = Polynomial::from_container(vec![1u8, 2, 3, 4, 5, 6]);
+/// let scalar = 127u8;
+/// let custom_modulus = 249u8;
+/// polynomial_wrapping_scalar_mul_assign_custom_mod(&mut pol, scalar, custom_modulus);
+/// assert_eq!(pol.as_ref(), &[127u8, 5, 132, 10, 137, 15]);
+/// ```
+pub fn polynomial_wrapping_scalar_mul_assign_custom_mod<Scalar, PolyCont>(
+    output: &mut Polynomial<PolyCont>,
+    scalar: Scalar,
+    custom_modulus: Scalar,
+) where
+    Scalar: UnsignedInteger,
+    PolyCont: ContainerMut<Element = Scalar>,
+{
+    slice_wrapping_scalar_mul_assign_custom_mod(output.as_mut(), scalar, custom_modulus)
+}
+
 /// Divides (mod $(X^{N}+1)$), the output polynomial with a monic monomial of a given degree i.e.
 /// $X^{degree}$.
 ///
@@ -919,6 +943,224 @@ pub fn polynomial_wrapping_sub_mul_assign_custom_mod<Scalar, OutputCont, InputCo
     }
 }
 
+pub fn polynomial_list_wrapping_sub_scalar_mul_assign<Scalar, InputCont, OutputCont, PolyCont>(
+    output_poly_list: &mut PolynomialList<OutputCont>,
+    input_poly_list: &PolynomialList<InputCont>,
+    scalar_poly: &Polynomial<PolyCont>,
+) where
+    Scalar: UnsignedInteger,
+    OutputCont: ContainerMut<Element = Scalar>,
+    InputCont: Container<Element = Scalar>,
+    PolyCont: Container<Element = Scalar>,
+{
+    assert_eq!(
+        output_poly_list.polynomial_size(),
+        input_poly_list.polynomial_size()
+    );
+    assert_eq!(
+        output_poly_list.polynomial_count(),
+        input_poly_list.polynomial_count()
+    );
+    for (mut output_poly, input_poly) in output_poly_list.iter_mut().zip(input_poly_list.iter()) {
+        polynomial_wrapping_sub_mul_assign(&mut output_poly, &input_poly, scalar_poly)
+    }
+}
+
+pub fn polynomial_list_wrapping_sub_scalar_mul_assign_custom_mod<
+    Scalar,
+    InputCont,
+    OutputCont,
+    PolyCont,
+>(
+    output_poly_list: &mut PolynomialList<OutputCont>,
+    input_poly_list: &PolynomialList<InputCont>,
+    scalar_poly: &Polynomial<PolyCont>,
+    custom_modulus: Scalar,
+) where
+    Scalar: UnsignedInteger,
+    OutputCont: ContainerMut<Element = Scalar>,
+    InputCont: Container<Element = Scalar>,
+    PolyCont: Container<Element = Scalar>,
+{
+    assert_eq!(
+        output_poly_list.polynomial_size(),
+        input_poly_list.polynomial_size()
+    );
+    assert_eq!(
+        output_poly_list.polynomial_count(),
+        input_poly_list.polynomial_count()
+    );
+    for (mut output_poly, input_poly) in output_poly_list.iter_mut().zip(input_poly_list.iter()) {
+        polynomial_wrapping_sub_mul_assign_custom_mod(
+            &mut output_poly,
+            &input_poly,
+            scalar_poly,
+            custom_modulus,
+        )
+    }
+}
+
+/// Apply an automorphism to the input [`Polynomial`](`Polynomial`) and add
+/// the result to the output [`Polynomial`](`Polynomial`).
+///
+/// The automorphism is specified by the exponent to which the polynomial
+/// indeterminate is raised, namely the value e where X is mapped to X^e.
+/// The automorphism exponent needs to be odd as we assume we are working
+/// in a power of two cyclotomic ring.
+pub fn apply_automorphism_wrapping_add_assign<Scalar, OutputCont, PolyCont>(
+    output: &mut Polynomial<OutputCont>,
+    input: &Polynomial<PolyCont>,
+    automorphism_exponent: usize,
+) where
+    Scalar: UnsignedInteger,
+    OutputCont: ContainerMut<Element = Scalar>,
+    PolyCont: Container<Element = Scalar>,
+{
+    // check input and output polynomials have the same size
+    assert_eq!(input.polynomial_size(), output.polynomial_size());
+
+    // check dimensions are a power of 2
+    assert!(input.polynomial_size().0.is_power_of_two());
+
+    // check the automorphism exponent is odd so the function X -> X^automorphism_exponent is an
+    // automorphism (assumes polysize is a power of 2 which we just checked)
+    assert_eq!(automorphism_exponent % 2, 1);
+
+    let poly_size = input.polynomial_size().0;
+
+    for (index, coef) in input.iter().enumerate() {
+        let new_index = (index * automorphism_exponent) % poly_size;
+        if (index * automorphism_exponent) % (2 * poly_size) == new_index {
+            output[new_index] = output[new_index].wrapping_add(*coef);
+        } else {
+            output[new_index] = output[new_index].wrapping_sub(*coef);
+        }
+    }
+}
+
+/// Apply an automorphism to the input [`Polynomial`](`Polynomial`) and add
+/// the result to the output [`Polynomial`](`Polynomial`) modulo a custom modulus.
+///
+/// The automorphism is specified by the exponent to which the polynomial
+/// indeterminate is raised, namely the value e where X is mapped to X^e.
+/// The automorphism exponent needs to be odd as we assume we are working
+/// in a power of two cyclotomic ring.
+pub fn apply_automorphism_wrapping_add_assign_custom_mod<Scalar, OutputCont, PolyCont>(
+    output: &mut Polynomial<OutputCont>,
+    input: &Polynomial<PolyCont>,
+    automorphism_exponent: usize,
+    custom_modulus: Scalar,
+) where
+    Scalar: UnsignedInteger,
+    OutputCont: ContainerMut<Element = Scalar>,
+    PolyCont: Container<Element = Scalar>,
+{
+    // check input and output polynomials have the same size
+    assert_eq!(input.polynomial_size(), output.polynomial_size());
+
+    // check dimensions are a power of 2
+    assert!(input.polynomial_size().0.is_power_of_two());
+
+    // check the automorphism exponent is odd so the function X -> X^automorphism_exponent is an
+    // automorphism (assumes polysize is a power of 2 which we just checked)
+    assert_eq!(automorphism_exponent % 2, 1);
+
+    let poly_size = input.polynomial_size().0;
+
+    for (index, coef) in input.iter().enumerate() {
+        let new_index = (index * automorphism_exponent) % poly_size;
+        if (index * automorphism_exponent) % (2 * poly_size) == new_index {
+            output[new_index] = output[new_index].wrapping_add_custom_mod(*coef, custom_modulus);
+        } else {
+            output[new_index] = output[new_index].wrapping_sub_custom_mod(*coef, custom_modulus);
+        }
+    }
+}
+
+/// Apply an automorphism to the input [`Polynomial`](`Polynomial`).
+///
+/// The automorphism is specified by the exponent to which the polynomial
+/// indeterminate is raised, namely the value e where X is mapped to X^e.
+/// The automorphism exponent needs to be odd as we assume we are working
+/// in a power of two cyclotomic ring.
+///
+/// # Example
+///
+/// ```rust
+/// use tfhe::core_crypto::algorithms::polynomial_algorithms::*;
+/// use tfhe::core_crypto::commons::parameters::*;
+/// use tfhe::core_crypto::entities::*;
+/// let mut poly = Polynomial::new(1_u8, PolynomialSize(32));
+/// apply_automorphism_assign(&mut poly, 5);
+/// let expected = [
+///     1u8, 1, 1, 255, 255, 1, 1, 1, 255, 255, 1, 1, 1, 255, 255, 1, 1, 1, 255, 255, 1, 1, 1, 255,
+///     255, 1, 1, 1, 255, 255, 1, 1,
+/// ];
+///
+/// poly.as_ref()
+///     .iter()
+///     .zip(expected.iter())
+///     .for_each(|(&x, &y)| assert_eq!(x, y));
+/// ```
+pub fn apply_automorphism_assign<Scalar, PolyCont>(
+    input: &mut Polynomial<PolyCont>,
+    automorphism_exponent: usize,
+) where
+    Scalar: UnsignedInteger,
+    PolyCont: ContainerMut<Element = Scalar>,
+{
+    let mut temp = Polynomial::new(Scalar::ZERO, input.polynomial_size());
+    apply_automorphism_wrapping_add_assign(&mut temp, input, automorphism_exponent);
+    input.as_mut().fill(Scalar::ZERO);
+    polynomial_wrapping_add_assign(input, &temp);
+}
+
+/// Apply an automorphism to the input [`Polynomial`](`Polynomial`)
+/// modulo a custom modulus.
+///
+/// The automorphism is specified by the exponent to which the polynomial
+/// indeterminate is raised, namely the value e where X is mapped to X^e.
+/// The automorphism exponent needs to be odd as we assume we are working
+/// in a power of two cyclotomic ring.
+///
+/// # Example
+///
+/// ```rust
+/// use tfhe::core_crypto::algorithms::polynomial_algorithms::*;
+/// use tfhe::core_crypto::commons::parameters::*;
+/// use tfhe::core_crypto::entities::*;
+/// let mut poly = Polynomial::new(1_u8, PolynomialSize(32));
+/// let custom_modulus = 223u8;
+/// apply_automorphism_assign_custom_mod(&mut poly, 5, custom_modulus);
+/// let expected = [
+///     1u8, 1, 1, 222, 222, 1, 1, 1, 222, 222, 1, 1, 1, 222, 222, 1, 1, 1, 222, 222, 1, 1, 1, 222,
+///     222, 1, 1, 1, 222, 222, 1, 1,
+/// ];
+///
+/// poly.as_ref()
+///     .iter()
+///     .zip(expected.iter())
+///     .for_each(|(&x, &y)| assert_eq!(x, y));
+/// ```
+pub fn apply_automorphism_assign_custom_mod<Scalar, PolyCont>(
+    input: &mut Polynomial<PolyCont>,
+    automorphism_exponent: usize,
+    custom_modulus: Scalar,
+) where
+    Scalar: UnsignedInteger,
+    PolyCont: ContainerMut<Element = Scalar>,
+{
+    let mut temp = Polynomial::new(Scalar::ZERO, input.polynomial_size());
+    apply_automorphism_wrapping_add_assign_custom_mod(
+        &mut temp,
+        input,
+        automorphism_exponent,
+        custom_modulus,
+    );
+    input.as_mut().fill(Scalar::ZERO);
+    polynomial_wrapping_add_assign_custom_mod(input, &temp, custom_modulus);
+}
+
 /// Fill the output polynomial, with the result of the product of two polynomials, reduced modulo
 /// $(X^{N} + 1)$ with the schoolbook algorithm Complexity: $O(N^{2})$
 ///

tfhe/src/core_crypto/commons/math/decomposition/decomposer.rs

@@ -1,6 +1,7 @@
 use crate::core_crypto::commons::ciphertext_modulus::CiphertextModulus;
 use crate::core_crypto::commons::math::decomposition::{
-    SignedDecompositionIter, SignedDecompositionNonNativeIter, ValueSign,
+    SignedDecompositionIter, SignedDecompositionNonNativeIter, SliceSignedDecompositionIter,
+    SliceSignedDecompositionNonNativeIter, ValueSign,
 };
 use crate::core_crypto::commons::numeric::{CastInto, UnsignedInteger};
 use crate::core_crypto::commons::parameters::{DecompositionBaseLog, DecompositionLevelCount};
@@ -174,6 +175,56 @@ where
         res.wrapping_sub(need_balance << rep_bit_count)
     }
 
+    pub fn init_decomposer_state_slice(&self, input: &[Scalar], output: &mut [Scalar]) {
+        assert_eq!(input.len(), output.len());
+        let rep_bit_count = self.level_count * self.base_log;
+        let non_rep_bit_count: usize = Scalar::BITS - rep_bit_count;
+        let mod_mask = Scalar::MAX >> non_rep_bit_count;
+        input
+            .iter()
+            .zip(output.iter_mut())
+            .for_each(|(input, output)| {
+                *output = *input >> (non_rep_bit_count - 1);
+                let rounding_bit = *output & Scalar::ONE;
+                *output += Scalar::ONE;
+                *output >>= 1;
+                *output &= mod_mask;
+                let need_balance =
+                    balanced_rounding_condition_bit_trick(*output, rep_bit_count, rounding_bit);
+                *output = output.wrapping_sub(need_balance << rep_bit_count)
+            });
+    }
+
+    /// Decode a plaintext value using the decoder to compute the closest representable.
+    pub fn decode_plaintext(&self, input: Scalar) -> Scalar {
+        let shift = Scalar::BITS - self.level_count * self.base_log;
+        self.closest_representable(input) >> shift
+    }
+
+    /// Fills a mutable tensor-like objects with the closest representable values from another
+    /// tensor-like object.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposer;
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    ///
+    /// let input = vec![1_340_987_234_u32; 2];
+    /// let mut closest = vec![0u32; 2];
+    /// decomposer.fill_slice_with_closest_representable(&mut closest, &input);
+    /// assert!(closest.iter().all(|&x| x == 1_341_128_704_u32));
+    /// ```
+    pub fn fill_slice_with_closest_representable(&self, output: &mut [Scalar], input: &[Scalar]) {
+        assert_eq!(output.len(), input.len());
+        output
+            .iter_mut()
+            .zip(input.iter())
+            .for_each(|(dst, &src)| *dst = self.closest_representable(src));
+    }
+
     /// Generate an iterator over the terms of the decomposition of the input.
     ///
     /// # Warning
@@ -242,6 +293,89 @@ where
             None
         }
     }
+
+    /// Generates an iterator-like object over tensors of terms of the decomposition of the input
+    /// tensor.
+    ///
+    /// # Warning
+    ///
+    /// The returned iterator yields the terms $(\tilde{\theta}^{(a)}\_i)\_{a\in\mathbb{N}}$ in
+    /// order of decreasing $i$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposer;
+    /// use tfhe::core_crypto::commons::numeric::UnsignedInteger;
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let decomposable = vec![1_340_987_234_u32, 1_340_987_234_u32];
+    /// let mut decomp = decomposer.decompose_slice(&decomposable);
+    ///
+    /// let mut count = 0;
+    /// while let Some(term) = decomp.next_term() {
+    ///     assert!(1 <= term.level().0);
+    ///     assert!(term.level().0 <= 3);
+    ///     for elmt in term.as_slice().iter() {
+    ///         let signed_term = elmt.into_signed();
+    ///         let half_basis = 2i32.pow(4) / 2i32;
+    ///         assert!(-half_basis <= signed_term);
+    ///         assert!(signed_term < half_basis);
+    ///     }
+    ///     count += 1;
+    /// }
+    /// assert_eq!(count, 3);
+    /// ```
+    pub fn decompose_slice(&self, input: &[Scalar]) -> SliceSignedDecompositionIter<Scalar> {
+        // Note that there would be no sense of making the decomposition on an input which was
+        // not rounded to the closest representable first. We then perform it before decomposing.
+        let mut closest = vec![Scalar::ZERO; input.len()];
+        self.init_decomposer_state_slice(input, &mut closest);
+        SliceSignedDecompositionIter::new(
+            &closest,
+            DecompositionBaseLog(self.base_log),
+            DecompositionLevelCount(self.level_count),
+        )
+    }
+
+    /// Fills the output tensor with the recomposition of another tensor.
+    ///
+    /// Returns `Some(())` if the decomposition was fresh, and the output was filled with a
+    /// recomposition, and `None`, if not.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposer;
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let mut rounded = vec![0u32; 2];
+    /// decomposer.fill_slice_with_closest_representable(&mut rounded, &decomposable);
+    /// let decomp = decomposer.decompose_slice(&rounded);
+    /// let mut recomposition = vec![0u32; 2];
+    /// decomposer
+    ///     .fill_slice_with_recompose(decomp, &mut recomposition)
+    ///     .unwrap();
+    /// assert_eq!(recomposition, rounded);
+    /// ```
+    pub fn fill_slice_with_recompose(
+        &self,
+        decomp: SliceSignedDecompositionIter<Scalar>,
+        output: &mut [Scalar],
+    ) -> Option<()> {
+        let mut decomp = decomp;
+        if decomp.is_fresh() {
+            while let Some(term) = decomp.next_term() {
+                term.update_slice_with_recomposition_summand_wrapping_addition(output);
+            }
+            Some(())
+        } else {
+            None
+        }
+    }
 }
 
 /// A structure which allows to decompose unsigned integers into a set of smaller terms for moduli
@@ -437,6 +571,26 @@ where
         }
     }
 
+    /// Decode a plaintext value using the decoder modulo a custom modulus.
+    pub fn decode_plaintext(&self, input: Scalar) -> Scalar {
+        let ciphertext_modulus_as_scalar: Scalar =
+            self.ciphertext_modulus.get_custom_modulus().cast_into();
+        let mut negate_input = false;
+        let mut ptxt = input;
+        if input > ciphertext_modulus_as_scalar >> 1 {
+            negate_input = true;
+            ptxt = ptxt.wrapping_neg_custom_mod(ciphertext_modulus_as_scalar);
+        }
+        let number_of_message_bits = self.base_log().0 * self.level_count().0;
+        let delta = ciphertext_modulus_as_scalar >> number_of_message_bits;
+        let half_delta = delta >> 1;
+        let mut decoded = (ptxt + half_delta) / delta;
+        if negate_input {
+            decoded = decoded.wrapping_neg_custom_mod(ciphertext_modulus_as_scalar);
+        }
+        decoded
+    }
+
     #[inline(always)]
     pub fn init_decomposer_state(&self, input: Scalar) -> (Scalar, ValueSign) {
         let ciphertext_modulus_as_scalar: Scalar =
@@ -468,6 +622,36 @@ where
         (abs_closest_representable, input_sign)
     }
 
+    pub fn init_decomposer_state_slice(
+        &self,
+        input: &[Scalar],
+        output: &mut [Scalar],
+        signs: &mut [ValueSign],
+    ) {
+        assert_eq!(input.len(), output.len());
+        assert_eq!(input.len(), signs.len());
+        let ciphertext_modulus_as_scalar: Scalar =
+            self.ciphertext_modulus.get_custom_modulus().cast_into();
+        let shift_to_native = Scalar::BITS - self.ciphertext_modulus_bit_count() as usize;
+
+        input
+            .iter()
+            .zip(output.iter_mut())
+            .zip(signs.iter_mut())
+            .for_each(|((input, output), sign)| {
+                if *input < ciphertext_modulus_as_scalar.div_ceil(Scalar::TWO) {
+                    (*output, *sign) = (*input, ValueSign::Positive)
+                } else {
+                    (*output, *sign) = (ciphertext_modulus_as_scalar - *input, ValueSign::Negative)
+                };
+                *output = native_closest_representable(
+                    *output << shift_to_native,
+                    self.level_count,
+                    self.base_log,
+                ) >> shift_to_native
+            });
+    }
+
     /// Generate an iterator over the terms of the decomposition of the input.
     ///
     /// # Warning
@@ -565,6 +749,153 @@ where
             None
         }
     }
+
+    /// Fills a mutable tensor-like objects with the closest representable values from another
+    /// tensor-like object.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::{SignedDecomposerNonNative, ValueSign};
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    /// let decomposer = SignedDecomposerNonNative::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     CiphertextModulus::try_new((1 << 48) + 1).unwrap(),
+    /// );
+    ///
+    /// let input = vec![249280154129830u64; 2];
+    /// let mut closest = vec![0u64; 2];
+    /// let mut signs = vec![ValueSign::Positive; 2];
+    /// decomposer.init_decomposer_state_slice(&input, &mut closest, &mut signs);
+    /// assert!(closest.iter().all(|&x| x == 32160715112448u64));
+    /// decomposer.fill_slice_with_closest_representable(&mut closest, &input);
+    /// assert!(closest.iter().all(|&x| x == 249314261598209u64));
+    /// ```
+    pub fn fill_slice_with_closest_representable(&self, output: &mut [Scalar], input: &[Scalar]) {
+        assert_eq!(output.len(), input.len());
+        let mut signs = vec![ValueSign::Positive; input.len()];
+        self.init_decomposer_state_slice(input, output, &mut signs);
+
+        let modulus_as_scalar: Scalar = self.ciphertext_modulus.get_custom_modulus().cast_into();
+        output
+            .iter_mut()
+            .zip(signs.iter())
+            .for_each(|(output, sign)| match sign {
+                ValueSign::Positive => (),
+                ValueSign::Negative => *output = output.wrapping_neg_custom_mod(modulus_as_scalar),
+            });
+    }
+
+    /// Generates an iterator-like object over tensors of terms of the decomposition of the input
+    /// tensor.
+    ///
+    /// # Warning
+    ///
+    /// The returned iterator yields the terms $(\tilde{\theta}^{(a)}\_i)\_{a\in\mathbb{N}}$ in
+    /// order of decreasing $i$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposerNonNative;
+    /// use tfhe::core_crypto::commons::numeric::UnsignedInteger;
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    ///
+    /// let decomposition_base_log = DecompositionBaseLog(4);
+    /// let decomposition_level_count = DecompositionLevelCount(3);
+    /// let ciphertext_modulus = CiphertextModulus::try_new((1 << 64) - (1 << 32) + 1).unwrap();
+    ///
+    /// let decomposer = SignedDecomposerNonNative::new(
+    ///     decomposition_base_log,
+    ///     decomposition_level_count,
+    ///     ciphertext_modulus,
+    /// );
+    ///
+    /// let basis = 2i64.pow(decomposition_base_log.0.try_into().unwrap());
+    /// let half_basis = basis / 2;
+    ///
+    /// let decomposable = [9223372032559808513u64, 1u64 << 63];
+    /// let mut decomp = decomposer.decompose_slice(&decomposable);
+    ///
+    /// let mut count = 0;
+    /// while let Some(term) = decomp.next_term() {
+    ///     assert!(1 <= term.level().0);
+    ///     assert!(term.level().0 <= 3);
+    ///     for elmt in term.as_slice().iter() {
+    ///         let signed_term = elmt.into_signed();
+    ///         assert!(-half_basis <= signed_term);
+    ///         assert!(signed_term <= half_basis);
+    ///     }
+    ///     count += 1;
+    /// }
+    /// assert_eq!(count, 3);
+    /// ```
+    pub fn decompose_slice(
+        &self,
+        input: &[Scalar],
+    ) -> SliceSignedDecompositionNonNativeIter<Scalar> {
+        let mut abs_closest_representables = vec![Scalar::ZERO; input.len()];
+        let mut signs = vec![ValueSign::Positive; input.len()];
+        self.init_decomposer_state_slice(input, &mut abs_closest_representables, &mut signs);
+
+        SliceSignedDecompositionNonNativeIter::new(
+            &abs_closest_representables,
+            &signs,
+            DecompositionBaseLog(self.base_log),
+            DecompositionLevelCount(self.level_count),
+            self.ciphertext_modulus,
+        )
+    }
+
+    /// Fills the output tensor with the recomposition of another tensor.
+    ///
+    /// Returns `Some(())` if the decomposition was fresh, and the output was filled with a
+    /// recomposition, and `None`, if not.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposerNonNative;
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    ///
+    /// let ciphertext_modulus = CiphertextModulus::try_new((1 << 32) - (1 << 16) + 1).unwrap();
+    /// let decomposer = SignedDecomposerNonNative::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     ciphertext_modulus,
+    /// );
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let mut rounded = vec![0u32; 2];
+    /// decomposer.fill_slice_with_closest_representable(&mut rounded, &decomposable);
+    /// let decomp = decomposer.decompose_slice(&rounded);
+    /// let mut recomposition = vec![0u32; 2];
+    /// decomposer
+    ///     .fill_slice_with_recompose(decomp, &mut recomposition)
+    ///     .unwrap();
+    /// assert_eq!(recomposition, rounded);
+    /// ```
+    pub fn fill_slice_with_recompose(
+        &self,
+        decomp: SliceSignedDecompositionNonNativeIter<Scalar>,
+        output: &mut [Scalar],
+    ) -> Option<()> {
+        let mut decomp = decomp;
+        if decomp.is_fresh() {
+            while let Some(term) = decomp.next_term() {
+                term.update_slice_with_recomposition_summand_wrapping_addition(output);
+            }
+            Some(())
+        } else {
+            None
+        }
+    }
 }
 
 #[cfg(test)]

tfhe/src/core_crypto/commons/math/decomposition/iter.rs

@@ -1,6 +1,7 @@
 use crate::core_crypto::commons::ciphertext_modulus::CiphertextModulus;
 use crate::core_crypto::commons::math::decomposition::{
-    DecompositionLevel, DecompositionTerm, DecompositionTermNonNative, SignedDecomposerNonNative,
+    DecompositionLevel, DecompositionTerm, DecompositionTermNonNative, DecompositionTermSlice,
+    DecompositionTermSliceNonNative, SignedDecomposerNonNative,
 };
 use crate::core_crypto::commons::numeric::UnsignedInteger;
 use crate::core_crypto::commons::parameters::{DecompositionBaseLog, DecompositionLevelCount};
@@ -148,6 +149,149 @@ pub(crate) fn decompose_one_level<S: UnsignedInteger>(
     res.wrapping_sub(carry << base_log)
 }
 
+/// An iterator-like object that yields the terms of the signed decomposition of a tensor of values.
+///
+/// # Note
+///
+/// On each call to [`SliceSignedDecompositionIter::next_term`], this structure yields a new
+/// [`DecompositionTermSlice`], backed by a `Vec` owned by the structure. This vec is mutated at
+/// each call of the `next_term` method, and as such the term must be dropped before `next_term` is
+/// called again.
+///
+/// Such a pattern can not be implemented with iterators yet (without GATs), which is why this
+/// iterator must be explicitly called.
+///
+/// # Warning
+///
+/// This iterator yields the decomposition in reverse order. That means that the highest level
+/// will be yielded first.
+pub struct SliceSignedDecompositionIter<T>
+where
+    T: UnsignedInteger,
+{
+    // The base log of the decomposition
+    base_log: usize,
+    // The number of levels of the decomposition
+    level_count: usize,
+    // The current level
+    current_level: usize,
+    // A mask which allows to compute the mod B of a value. For B=2^4, this guy is of the form:
+    // ...0001111
+    mod_b_mask: T,
+    // The internal states of each decomposition
+    states: Vec<T>,
+    // In order to avoid allocating a new Vec every time we yield a decomposition term, we store
+    // a Vec inside the structure and yield slices pointing to it.
+    outputs: Vec<T>,
+    // A flag which stores whether the iterator is a fresh one (for the recompose method).
+    fresh: bool,
+}
+
+impl<T> SliceSignedDecompositionIter<T>
+where
+    T: UnsignedInteger,
+{
+    // Creates a new tensor decomposition iterator.
+    pub(crate) fn new(
+        input: &[T],
+        base_log: DecompositionBaseLog,
+        level: DecompositionLevelCount,
+    ) -> Self {
+        let len = input.len();
+        Self {
+            base_log: base_log.0,
+            level_count: level.0,
+            current_level: level.0,
+            mod_b_mask: (T::ONE << base_log.0) - T::ONE,
+            outputs: vec![T::ZERO; len],
+            states: input.to_vec(),
+            fresh: true,
+        }
+    }
+
+    pub(crate) fn is_fresh(&self) -> bool {
+        self.fresh
+    }
+
+    /// Returns the logarithm in base two of the base of this decomposition.
+    ///
+    /// If the decomposition uses a base $B=2^b$, this returns $b$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposer;
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let decomp = decomposer.decompose_slice(&decomposable);
+    /// assert_eq!(decomp.base_log(), DecompositionBaseLog(4));
+    /// ```
+    pub fn base_log(&self) -> DecompositionBaseLog {
+        DecompositionBaseLog(self.base_log)
+    }
+
+    /// Returns the number of levels of this decomposition.
+    ///
+    /// If the decomposition uses $l$ levels, this returns $l$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposer;
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let decomp = decomposer.decompose_slice(&decomposable);
+    /// assert_eq!(decomp.level_count(), DecompositionLevelCount(3));
+    /// ```
+    pub fn level_count(&self) -> DecompositionLevelCount {
+        DecompositionLevelCount(self.level_count)
+    }
+
+    /// Yield the next term of the decomposition, if any.
+    ///
+    /// # Note
+    ///
+    /// Because this function returns a borrowed tensor, owned by the iterator, the term must be
+    /// dropped before `next_term` is called again.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::{DecompositionLevel, SignedDecomposer};
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let mut decomp = decomposer.decompose_slice(&decomposable);
+    /// let term = decomp.next_term().unwrap();
+    /// assert_eq!(term.level(), DecompositionLevel(3));
+    /// assert_eq!(term.as_slice()[0], 4294967295);
+    /// ```
+    pub fn next_term(&mut self) -> Option<DecompositionTermSlice<'_, T>> {
+        // The iterator is not fresh anymore.
+        self.fresh = false;
+        // We check if the decomposition is over
+        if self.current_level == 0 {
+            return None;
+        }
+        // We iterate over the elements of the outputs and decompose
+        for (output_i, state_i) in self.outputs.iter_mut().zip(self.states.iter_mut()) {
+            *output_i = decompose_one_level(self.base_log, state_i, self.mod_b_mask);
+        }
+        self.current_level -= 1;
+        // We return the term tensor.
+        Some(DecompositionTermSlice::new(
+            DecompositionLevel(self.current_level + 1),
+            DecompositionBaseLog(self.base_log),
+            &self.outputs,
+        ))
+    }
+}
+
 /// An iterator that yields the terms of the signed decomposition of an integer.
 ///
 /// # Warning
@@ -293,6 +437,191 @@ where
     }
 }
 
+/// An iterator-like object that yields the terms of the signed decomposition of a tensor of values.
+///
+/// # Note
+///
+/// On each call to [`SliceSignedDecompositionNonNativeIter::next_term`], this structure yields a
+/// new
+/// [`DecompositionTermSlice`], backed by a `Vec` owned by the structure. This vec is mutated at
+/// each call of the `next_term` method, and as such the term must be dropped before `next_term` is
+/// called again.
+///
+/// Such a pattern can not be implemented with iterators yet (without GATs), which is why this
+/// iterator must be explicitly called.
+///
+/// # Warning
+///
+/// This iterator yields the decomposition in reverse order. That means that the highest level
+/// will be yielded first.
+pub struct SliceSignedDecompositionNonNativeIter<T>
+where
+    T: UnsignedInteger,
+{
+    // The base log of the decomposition
+    base_log: usize,
+    // The number of levels of the decomposition
+    level_count: usize,
+    // The current level
+    current_level: usize,
+    // A mask which allows to compute the mod B of a value. For B=2^4, this guy is of the form:
+    // ...0001111
+    mod_b_mask: T,
+    // Ciphertext modulus
+    ciphertext_modulus: CiphertextModulus<T>,
+    // The internal states of each decomposition
+    states: Vec<T>,
+    // In order to avoid allocating a new Vec every time we yield a decomposition term, we store
+    // a Vec inside the structure and yield slices pointing to it.
+    outputs: Vec<T>,
+    // A flag which stores whether the iterator is a fresh one (for the recompose method).
+    fresh: bool,
+    // The signs of the input values, for the algorithm we use, returned values require adaption
+    // depending on the sign of the input
+    signs: Vec<ValueSign>,
+}
+
+impl<T> SliceSignedDecompositionNonNativeIter<T>
+where
+    T: UnsignedInteger,
+{
+    // Creates a new tensor decomposition iterator.
+    pub(crate) fn new(
+        input: &[T],
+        input_signs: &[ValueSign],
+        base_log: DecompositionBaseLog,
+        level: DecompositionLevelCount,
+        ciphertext_modulus: CiphertextModulus<T>,
+    ) -> Self {
+        Self {
+            base_log: base_log.0,
+            level_count: level.0,
+            current_level: level.0,
+            mod_b_mask: (T::ONE << base_log.0) - T::ONE,
+            ciphertext_modulus,
+            outputs: vec![T::ZERO; input.len()],
+            states: input
+                .iter()
+                .map(|i| {
+                    *i >> (ciphertext_modulus.get_custom_modulus().ceil_ilog2() as usize
+                        - base_log.0 * level.0)
+                })
+                .collect(),
+            fresh: true,
+            signs: input_signs.to_vec(),
+        }
+    }
+
+    pub(crate) fn is_fresh(&self) -> bool {
+        self.fresh
+    }
+
+    /// Returns the logarithm in base two of the base of this decomposition.
+    ///
+    /// If the decomposition uses a base $B=2^b$, this returns $b$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposerNonNative;
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    /// let decomposer = SignedDecomposerNonNative::<u32>::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     CiphertextModulus::try_new((1 << 32) - (1 << 16) + 1).unwrap(),
+    /// );
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let decomp = decomposer.decompose_slice(&decomposable);
+    /// assert_eq!(decomp.base_log(), DecompositionBaseLog(4));
+    /// ```
+    pub fn base_log(&self) -> DecompositionBaseLog {
+        DecompositionBaseLog(self.base_log)
+    }
+
+    /// Returns the number of levels of this decomposition.
+    ///
+    /// If the decomposition uses $l$ levels, this returns $l$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposerNonNative;
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    /// let decomposer = SignedDecomposerNonNative::<u32>::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     CiphertextModulus::try_new((1 << 32) - (1 << 16) + 1).unwrap(),
+    /// );
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let decomp = decomposer.decompose_slice(&decomposable);
+    /// assert_eq!(decomp.level_count(), DecompositionLevelCount(3));
+    /// ```
+    pub fn level_count(&self) -> DecompositionLevelCount {
+        DecompositionLevelCount(self.level_count)
+    }
+
+    /// Yield the next term of the decomposition, if any.
+    ///
+    /// # Note
+    ///
+    /// Because this function returns a borrowed tensor, owned by the iterator, the term must be
+    /// dropped before `next_term` is called again.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::{
+    ///     DecompositionLevel, SignedDecomposerNonNative,
+    /// };
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    /// let decomposer = SignedDecomposerNonNative::<u32>::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     CiphertextModulus::try_new((1 << 32) - (1 << 16) + 1).unwrap(),
+    /// );
+    /// let decomposable = vec![1_340_987_234_u32; 2];
+    /// let mut decomp = decomposer.decompose_slice(&decomposable);
+    /// let term = decomp.next_term().unwrap();
+    /// assert_eq!(term.level(), DecompositionLevel(3));
+    /// assert_eq!(term.as_slice()[0], u32::MAX);
+    /// ```
+    pub fn next_term(&mut self) -> Option<DecompositionTermSliceNonNative<'_, T>> {
+        // The iterator is not fresh anymore.
+        self.fresh = false;
+        // We check if the decomposition is over
+        if self.current_level == 0 {
+            return None;
+        }
+        // We iterate over the elements of the outputs and decompose
+        for ((output_i, state_i), sign_i) in self
+            .outputs
+            .iter_mut()
+            .zip(self.states.iter_mut())
+            .zip(self.signs.iter())
+        {
+            *output_i = decompose_one_level(self.base_log, state_i, self.mod_b_mask);
+            *output_i = match sign_i {
+                ValueSign::Positive => *output_i,
+                ValueSign::Negative => output_i.wrapping_neg(),
+            };
+        }
+        self.current_level -= 1;
+        // We return the term tensor.
+        Some(DecompositionTermSliceNonNative::new(
+            DecompositionLevel(self.current_level + 1),
+            DecompositionBaseLog(self.base_log),
+            &self.outputs,
+            self.ciphertext_modulus,
+        ))
+    }
+}
+
 /// Specialized high performance implementation of a non native decomposer over a collection of
 /// elements, used notably in the PBS.
 pub struct TensorSignedDecompositionLendingIterNonNative<'buffers> {

tfhe/src/core_crypto/commons/math/decomposition/term.rs

@@ -223,3 +223,284 @@ where
         DecompositionLevel(self.level)
     }
 }
+
+/// A tensor whose elements are the terms of the decomposition of another tensor.
+///
+/// If we decompose each elements of a set of values $(\theta^{(a)})\_{a\in\mathbb{N}}$ as a set of
+/// sums $(\sum\_{i=1}^l\tilde{\theta}^{(a)}\_i\frac{q}{B^i})\_{a\in\mathbb{N}}$, this represents a
+/// set of $(\tilde{\theta}^{(a)}\_i)\_{a\in\mathbb{N}}$.
+#[derive(Debug, PartialEq, Eq, Clone)]
+pub struct DecompositionTermSlice<'a, T>
+where
+    T: UnsignedInteger,
+{
+    level: usize,
+    base_log: usize,
+    slice: &'a [T],
+}
+
+impl<'a, T> DecompositionTermSlice<'a, T>
+where
+    T: UnsignedInteger,
+{
+    // Creates a new tensor decomposition term.
+    pub(crate) fn new(
+        level: DecompositionLevel,
+        base_log: DecompositionBaseLog,
+        slice: &'a [T],
+    ) -> Self {
+        Self {
+            level: level.0,
+            base_log: base_log.0,
+            slice,
+        }
+    }
+
+    /// Fills the output tensor with the terms turned to summands.
+    ///
+    /// If our term tensor represents a set of $(\tilde{\theta}^{(a)}\_i)\_{a\in\mathbb{N}}$ of the
+    /// decomposition, this method fills the output tensor with a set of
+    /// $(\tilde{\theta}^{(a)}\_i\frac{q}{B^i})\_{a\in\mathbb{N}}$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposer;
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let input = vec![2u32.pow(19); 2];
+    /// let mut decomp = decomposer.decompose_slice(&input);
+    /// let term = decomp.next_term().unwrap();
+    /// let mut output = vec![0u32; 2];
+    /// term.fill_slice_with_recomposition_summand(&mut output);
+    /// assert!(output.iter().all(|&x| x == 1048576));
+    /// ```
+    pub fn fill_slice_with_recomposition_summand(&self, output: &mut [T]) {
+        assert_eq!(self.slice.len(), output.len());
+        output
+            .iter_mut()
+            .zip(self.slice.iter())
+            .for_each(|(dst, &value)| {
+                let shift: usize = <T as Numeric>::BITS - self.base_log * self.level;
+                *dst = value << shift
+            });
+    }
+
+    pub(crate) fn update_slice_with_recomposition_summand_wrapping_addition(
+        &self,
+        output: &mut [T],
+    ) {
+        assert_eq!(self.slice.len(), output.len());
+        let shift: usize = <T as Numeric>::BITS - self.base_log * self.level;
+        output
+            .iter_mut()
+            .zip(self.slice.iter())
+            .for_each(|(out, &value)| {
+                *out = (*out).wrapping_add(value << shift);
+            });
+    }
+
+    /// Returns a tensor with the values of term.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposer;
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let input = vec![2u32.pow(19); 2];
+    /// let mut decomp = decomposer.decompose_slice(&input);
+    /// let term = decomp.next_term().unwrap();
+    /// assert_eq!(term.as_slice()[0], 1);
+    /// ```
+    pub fn as_slice(&self) -> &'a [T] {
+        self.slice
+    }
+
+    /// Returns the level of this decomposition term tensor.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::{DecompositionLevel, SignedDecomposer};
+    /// use tfhe::core_crypto::prelude::{DecompositionBaseLog, DecompositionLevelCount};
+    /// let decomposer =
+    ///     SignedDecomposer::<u32>::new(DecompositionBaseLog(4), DecompositionLevelCount(3));
+    /// let input = vec![2u32.pow(19); 2];
+    /// let mut decomp = decomposer.decompose_slice(&input);
+    /// let term = decomp.next_term().unwrap();
+    /// assert_eq!(term.level(), DecompositionLevel(3));
+    /// ```
+    pub fn level(&self) -> DecompositionLevel {
+        DecompositionLevel(self.level)
+    }
+}
+
+/// A tensor whose elements are the terms of the decomposition of another tensor.
+///
+/// If we decompose each elements of a set of values $(\theta^{(a)})\_{a\in\mathbb{N}}$ as a set of
+/// sums $(\sum\_{i=1}^l\tilde{\theta}^{(a)}\_i\frac{q}{B^i})\_{a\in\mathbb{N}}$, this represents a
+/// set of $(\tilde{\theta}^{(a)}\_i)\_{a\in\mathbb{N}}$.
+#[derive(Debug, PartialEq, Eq, Clone)]
+pub struct DecompositionTermSliceNonNative<'a, T>
+where
+    T: UnsignedInteger,
+{
+    level: usize,
+    base_log: usize,
+    slice: &'a [T],
+    ciphertext_modulus: CiphertextModulus<T>,
+}
+
+impl<'a, T> DecompositionTermSliceNonNative<'a, T>
+where
+    T: UnsignedInteger,
+{
+    // Creates a new tensor decomposition term.
+    pub(crate) fn new(
+        level: DecompositionLevel,
+        base_log: DecompositionBaseLog,
+        slice: &'a [T],
+        ciphertext_modulus: CiphertextModulus<T>,
+    ) -> Self {
+        Self {
+            level: level.0,
+            base_log: base_log.0,
+            slice,
+            ciphertext_modulus,
+        }
+    }
+
+    /// Fills the output tensor with the terms turned to summands.
+    ///
+    /// If our term tensor represents a set of $(\tilde{\theta}^{(a)}\_i)\_{a\in\mathbb{N}}$ of the
+    /// decomposition, this method fills the output tensor with a set of
+    /// $(\tilde{\theta}^{(a)}\_i\frac{q}{B^i})\_{a\in\mathbb{N}}$.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposerNonNative;
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    /// let decomposer = SignedDecomposerNonNative::<u32>::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     CiphertextModulus::try_new((1 << 32) - 1).unwrap(),
+    /// );
+    /// let input = vec![2u32.pow(19); 2];
+    /// let mut decomp = decomposer.decompose_slice(&input);
+    /// let term = decomp.next_term().unwrap();
+    /// let mut output = vec![0; 2];
+    /// term.to_approximate_recomposition_summand(&mut output);
+    /// assert!(output.iter().all(|&x| x == 1048576));
+    /// ```
+    pub fn to_approximate_recomposition_summand(&self, output: &mut [T]) {
+        assert_eq!(self.slice.len(), output.len());
+        let modulus_as_t = T::cast_from(self.ciphertext_modulus.get_custom_modulus());
+        let ciphertext_modulus_bit_count: usize = modulus_as_t.ceil_ilog2().try_into().unwrap();
+        let shift: usize = ciphertext_modulus_bit_count - self.base_log * self.level;
+
+        output
+            .iter_mut()
+            .zip(self.slice.iter())
+            .for_each(|(dst, &value)| {
+                if value.into_signed() >= T::Signed::ZERO {
+                    *dst = value << shift
+                } else {
+                    *dst = modulus_as_t.wrapping_add(value << shift)
+                }
+            });
+    }
+
+    /// Compute the value of the term modulo the modulus given when building the
+    /// [`DecompositionTermSliceNonNative`]
+    pub fn modular_value(&self, output: &mut [T]) {
+        assert_eq!(self.slice.len(), output.len());
+        let modulus_as_t = T::cast_from(self.ciphertext_modulus.get_custom_modulus());
+        self.slice
+            .iter()
+            .zip(output.iter_mut())
+            .for_each(|(&value, output)| {
+                if value.into_signed() >= T::Signed::ZERO {
+                    *output = value
+                } else {
+                    *output = modulus_as_t.wrapping_add(value)
+                }
+            });
+    }
+
+    pub(crate) fn update_slice_with_recomposition_summand_wrapping_addition(
+        &self,
+        output: &mut [T],
+    ) {
+        assert_eq!(self.slice.len(), output.len());
+        let modulus_as_t = T::cast_from(self.ciphertext_modulus.get_custom_modulus());
+        let ciphertext_modulus_bit_count: usize = modulus_as_t.ceil_ilog2().try_into().unwrap();
+        let shift: usize = ciphertext_modulus_bit_count - self.base_log * self.level;
+        output
+            .iter_mut()
+            .zip(self.slice.iter())
+            .for_each(|(out, &value)| {
+                if value.into_signed() >= T::Signed::ZERO {
+                    *out = (*out).wrapping_add_custom_mod(value << shift, modulus_as_t)
+                } else {
+                    *out = (*out).wrapping_add_custom_mod(
+                        modulus_as_t.wrapping_add(value << shift),
+                        modulus_as_t,
+                    )
+                }
+            });
+    }
+
+    /// Returns a tensor with the values of term.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::SignedDecomposerNonNative;
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    /// let decomposer = SignedDecomposerNonNative::<u32>::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     CiphertextModulus::try_new((1 << 32) - 1).unwrap(),
+    /// );
+    /// let input = vec![2u32.pow(19); 2];
+    /// let mut decomp = decomposer.decompose_slice(&input);
+    /// let term = decomp.next_term().unwrap();
+    /// assert_eq!(term.as_slice()[0], 1);
+    /// ```
+    pub fn as_slice(&self) -> &'a [T] {
+        self.slice
+    }
+
+    /// Returns the level of this decomposition term tensor.
+    ///
+    /// # Example
+    ///
+    /// ```rust
+    /// use tfhe::core_crypto::commons::math::decomposition::{
+    ///     DecompositionLevel, SignedDecomposerNonNative,
+    /// };
+    /// use tfhe::core_crypto::prelude::{
+    ///     CiphertextModulus, DecompositionBaseLog, DecompositionLevelCount,
+    /// };
+    /// let decomposer = SignedDecomposerNonNative::<u32>::new(
+    ///     DecompositionBaseLog(4),
+    ///     DecompositionLevelCount(3),
+    ///     CiphertextModulus::try_new((1 << 32) - 1).unwrap(),
+    /// );
+    /// let input = vec![2u32.pow(19); 2];
+    /// let mut decomp = decomposer.decompose_slice(&input);
+    /// let term = decomp.next_term().unwrap();
+    /// assert_eq!(term.level(), DecompositionLevel(3));
+    /// ```
+    pub fn level(&self) -> DecompositionLevel {
+        DecompositionLevel(self.level)
+    }
+}

tfhe/src/core_crypto/entities/glwe_keyswitch_key.rs

@@ -0,0 +1,505 @@
+//! Module containing the definition of the [`GlweKeyswitchKey`].
+
+use crate::conformance::ParameterSetConformant;
+use crate::core_crypto::commons::parameters::*;
+use crate::core_crypto::commons::traits::*;
+use crate::core_crypto::entities::*;
+
+/// A [`GLWE keyswitch key`](`GlweKeyswitchKey`).
+///
+/// # Formal Definition
+///
+/// ## Key Switching Key
+///
+/// A key switching key is a vector of GLev ciphertexts (described on the bottom of
+/// [`this page`](`crate::core_crypto::entities::GgswCiphertext#Glev-ciphertext`)).
+/// It encrypts the coefficient of
+/// the [`GLWE secret key`](`crate::core_crypto::entities::GlweSecretKey`)
+/// $\vec{S}\_{\mathsf{in}}$ under the
+/// [`GLWE secret key`](`crate::core_crypto::entities::GlweSecretKey`)
+/// $\vec{S}\_{\mathsf{out}}$.
+///
+/// $$\mathsf{KSK}\_{\vec{S}\_{\mathsf{in}}\rightarrow \vec{S}\_{\mathsf{out}}} = \left(
+/// \overline{\mathsf{CT}\_0}, \cdots , \overline{\mathsf{CT}\_{k\_{\mathsf{in}}-1}}\right)
+/// \subseteq R\_q^{(k\_{\mathsf{out}}+1)\cdot k\_{\mathsf{in}}\cdot \ell}$$
+///
+/// where $\vec{S}\_{\mathsf{in}} = \left( S\_0 , \cdots , S\_{\mathsf{in}-1} \right)$ and for all
+/// $0\le i <k\_{\mathsf{in}}$ we have $\overline{\mathsf{CT}\_i} \in
+/// \mathsf{GLev}\_{\vec{S}\_{\mathsf{out}}}^{\beta, \ell}\left(S\_i\right)$.
+///
+/// ## GLWE Keyswitch
+///
+/// This homomorphic procedure transforms an input
+/// [`GLWE ciphertext`](`crate::core_crypto::entities::GlweCiphertext`)
+/// $\mathsf{CT}\_{\mathsf{in}} =
+/// \left( \vec{A}\_{\mathsf{in}} , B\_{\mathsf{in}}\right) \in \mathsf{GLWE}^{k\_{\mathsf{in}}}\_
+/// {\vec{S}\_{\mathsf{in}}}( \mathsf{PT} ) \subseteq R\_q^{(k\_{\mathsf{in}}+1)}$ into an
+/// output [`GLWE ciphertext`](`crate::core_crypto::entities::GlweCiphertext`)
+/// $\mathsf{CT}\_{\mathsf{out}} =
+/// \left( \vec{A}\_{\mathsf{out}} , B\_{\mathsf{out}}\right) \in
+/// \mathsf{GLWE}^{k\_{\mathsf{out}}}\_{\vec{S}\_{\mathsf{out}}}( \mathsf{PT} )\subseteq
+/// R\_q^{(k\_{\mathsf{out}}+1)}$ where $k\_{\mathsf{in}} = |\vec{S}\_{\mathsf{in}}|$ and
+/// $k\_{\mathsf{out}} = |\vec{S}\_{\mathsf{out}}|$. It requires a
+/// [`key switching key`](`crate::core_crypto::entities::GlweKeyswitchKey`).
+/// The input ciphertext is encrypted under the
+/// [`GLWE secret key`](`crate::core_crypto::entities::GlweSecretKey`)
+/// $\vec{S}\_{\mathsf{in}}$ and the output ciphertext is
+/// encrypted under the [`GLWE secret key`](`crate::core_crypto::entities::GlweSecretKey`)
+/// $\vec{S}\_{\mathsf{out}}$.
+///
+/// $$\mathsf{CT}\_{\mathsf{in}} \in \mathsf{GLWE}^{k\_{\mathsf{in}}}\_{\vec{S}\_{\mathsf{in}}}(
+/// \mathsf{PT} ) ~~~~~~~~~~\mathsf{KSK}\_{\vec{S}\_{\mathsf{in}}\rightarrow
+/// \vec{S}\_{\mathsf{out}}}$$ $$ \mathsf{keyswitch}\left(\mathsf{CT}\_{\mathsf{in}} , \mathsf{KSK}
+/// \right) \rightarrow \mathsf{CT}\_{\mathsf{out}} \in
+/// \mathsf{GLWE}^{k\_{\mathsf{out}}}\_{\vec{S}\_{\mathsf{out}}} \left( \mathsf{PT} \right)$$
+///
+/// ## Algorithm
+/// ###### inputs:
+/// - $\mathsf{CT}\_{\mathsf{in}} = \left( \vec{A}\_{\mathsf{in}} , B\_{\mathsf{in}}\right) \in
+///   \mathsf{GLWE}^{k\_{\mathsf{in}}}\_{\vec{S}\_{\mathsf{in}}}( \mathsf{PT} )$: a [`GLWE
+///   ciphertext`](`GlweCiphertext`) with $\vec{A}\_{\mathsf{in}}=\left(A\_0, \cdots
+///   A\_{k\_{\mathsf{in}}-1}\right)$
+/// - $\mathsf{KSK}\_{\vec{S}\_{\mathsf{in}}\rightarrow \vec{S}\_{\mathsf{out}}}$: a [`key switching
+///   key`](`crate::core_crypto::entities::GlweKeyswitchKey`)
+///
+/// ###### outputs:
+/// - $\mathsf{CT}\_{\mathsf{out}} \in \mathsf{GLWE}^{k\_{\mathsf{out}}}\_{\vec{S}\_{\mathsf{out}}}
+///   \left( \mathsf{PT} \right)$: a [`GLWE
+///   ciphertext`](`crate::core_crypto::entities::GlweCiphertext`)
+///
+/// ###### algorithm:
+/// 1. set $\mathsf{cCT}=\left( 0 , \cdots , 0 ,  B\_{\mathsf{in}} \right) \in
+///    R\_q^{(k\_{\mathsf{out}}+1)}$
+/// 2. compute $\mathsf{CT}\_{\mathsf{out}} = \mathsf{CT} - \sum\_{i=0}^{k\_{\mathsf{in}}-1}
+///    \mathsf{decompProduct}\left( A\_i , \overline{\mathsf{CT}\_i} \right)$
+/// 3. output $\mathsf{CT}\_{\mathsf{out}}$
+#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
+pub struct GlweKeyswitchKey<C: Container>
+where
+    C::Element: UnsignedInteger,
+{
+    data: C,
+    decomp_base_log: DecompositionBaseLog,
+    decomp_level_count: DecompositionLevelCount,
+    output_glwe_size: GlweSize,
+    poly_size: PolynomialSize,
+    ciphertext_modulus: CiphertextModulus<C::Element>,
+}
+
+impl<T: UnsignedInteger, C: Container<Element = T>> AsRef<[T]> for GlweKeyswitchKey<C> {
+    fn as_ref(&self) -> &[T] {
+        self.data.as_ref()
+    }
+}
+
+impl<T: UnsignedInteger, C: ContainerMut<Element = T>> AsMut<[T]> for GlweKeyswitchKey<C> {
+    fn as_mut(&mut self) -> &mut [T] {
+        self.data.as_mut()
+    }
+}
+
+/// Return the number of elements in an encryption of an input [`GlweSecretKey`] element for a
+/// [`GlweKeyswitchKey`] given a [`DecompositionLevelCount`] and output [`GlweSize`] and
+/// [`PolynomialSize`].
+pub fn glwe_keyswitch_key_input_key_element_encrypted_size(
+    decomp_level_count: DecompositionLevelCount,
+    output_glwe_size: GlweSize,
+    poly_size: PolynomialSize,
+) -> usize {
+    // One ciphertext per level encrypted under the output key
+    decomp_level_count.0 * output_glwe_size.0 * poly_size.0
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> GlweKeyswitchKey<C> {
+    /// Create an [`GlweKeyswitchKey`] from an existing container.
+    ///
+    /// # Note
+    ///
+    /// This function only wraps a container in the appropriate type. If you want to generate an
+    /// [`GlweKeyswitchKey`] you need to call
+    /// [`crate::core_crypto::algorithms::generate_glwe_keyswitch_key`] using this key as output.
+    ///
+    /// This docstring exhibits [`GlweKeyswitchKey`] primitives usage.
+    ///
+    /// ```
+    /// use tfhe::core_crypto::prelude::*;
+    ///
+    /// // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
+    /// // computations
+    /// // Define parameters for LweKeyswitchKey creation
+    /// let input_glwe_dimension = GlweDimension(1);
+    /// let output_glwe_dimension = GlweDimension(2);
+    /// let poly_size = PolynomialSize(1024);
+    /// let decomp_base_log = DecompositionBaseLog(4);
+    /// let decomp_level_count = DecompositionLevelCount(5);
+    /// let ciphertext_modulus = CiphertextModulus::new_native();
+    ///
+    /// // Create a new LweKeyswitchKey
+    /// let glwe_ksk = GlweKeyswitchKey::new(
+    ///     0u64,
+    ///     decomp_base_log,
+    ///     decomp_level_count,
+    ///     input_glwe_dimension,
+    ///     output_glwe_dimension,
+    ///     poly_size,
+    ///     ciphertext_modulus,
+    /// );
+    ///
+    /// assert_eq!(glwe_ksk.decomposition_base_log(), decomp_base_log);
+    /// assert_eq!(glwe_ksk.decomposition_level_count(), decomp_level_count);
+    /// assert_eq!(glwe_ksk.input_key_glwe_dimension(), input_glwe_dimension);
+    /// assert_eq!(glwe_ksk.output_key_glwe_dimension(), output_glwe_dimension);
+    /// assert_eq!(glwe_ksk.polynomial_size(), poly_size);
+    /// assert_eq!(
+    ///     glwe_ksk.output_glwe_size(),
+    ///     output_glwe_dimension.to_glwe_size()
+    /// );
+    /// assert_eq!(glwe_ksk.ciphertext_modulus(), ciphertext_modulus);
+    ///
+    /// // Demonstrate how to recover the allocated container
+    /// let underlying_container: Vec<u64> = glwe_ksk.into_container();
+    ///
+    /// // Recreate a keyswitch key using from_container
+    /// let glwe_ksk = GlweKeyswitchKey::from_container(
+    ///     underlying_container,
+    ///     decomp_base_log,
+    ///     decomp_level_count,
+    ///     output_glwe_dimension.to_glwe_size(),
+    ///     poly_size,
+    ///     ciphertext_modulus,
+    /// );
+    ///
+    /// assert_eq!(glwe_ksk.decomposition_base_log(), decomp_base_log);
+    /// assert_eq!(glwe_ksk.decomposition_level_count(), decomp_level_count);
+    /// assert_eq!(glwe_ksk.input_key_glwe_dimension(), input_glwe_dimension);
+    /// assert_eq!(glwe_ksk.output_key_glwe_dimension(), output_glwe_dimension);
+    /// assert_eq!(
+    ///     glwe_ksk.output_glwe_size(),
+    ///     output_glwe_dimension.to_glwe_size()
+    /// );
+    /// assert_eq!(glwe_ksk.ciphertext_modulus(), ciphertext_modulus);
+    /// ```
+    pub fn from_container(
+        container: C,
+        decomp_base_log: DecompositionBaseLog,
+        decomp_level_count: DecompositionLevelCount,
+        output_glwe_size: GlweSize,
+        poly_size: PolynomialSize,
+        ciphertext_modulus: CiphertextModulus<C::Element>,
+    ) -> Self {
+        assert!(
+            container.container_len() > 0,
+            "Got an empty container to create a GlweKeyswitchKey"
+        );
+        assert!(
+            container.container_len() % (decomp_level_count.0 * output_glwe_size.0 * poly_size.0)
+                == 0,
+            "The provided container length is not valid. \
+        It needs to be dividable by decomp_level_count * output_glwe_size * output_poly_size: {}. \
+        Got container length: {} and decomp_level_count: {decomp_level_count:?}, \
+        output_glwe_size: {output_glwe_size:?}, poly_size: {poly_size:?}.",
+            decomp_level_count.0 * output_glwe_size.0 * poly_size.0,
+            container.container_len()
+        );
+
+        Self {
+            data: container,
+            decomp_base_log,
+            decomp_level_count,
+            output_glwe_size,
+            poly_size,
+            ciphertext_modulus,
+        }
+    }
+
+    /// Return the [`DecompositionBaseLog`] of the [`LweKeyswitchKey`].
+    ///
+    /// See [`LweKeyswitchKey::from_container`] for usage.
+    pub fn decomposition_base_log(&self) -> DecompositionBaseLog {
+        self.decomp_base_log
+    }
+
+    /// Return the [`DecompositionLevelCount`] of the [`LweKeyswitchKey`].
+    ///
+    /// See [`LweKeyswitchKey::from_container`] for usage.
+    pub fn decomposition_level_count(&self) -> DecompositionLevelCount {
+        self.decomp_level_count
+    }
+
+    /// Return the input [`GlweDimension`] of the [`GlweKeyswitchKey`].
+    ///
+    /// See [`GlweKeyswitchKey::from_container`] for usage.
+    pub fn input_key_glwe_dimension(&self) -> GlweDimension {
+        GlweDimension(self.data.container_len() / self.input_key_element_encrypted_size())
+    }
+
+    /// Return the input [`PolynomialSize`] of the [`GlweKeyswitchKey`].
+    ///
+    /// See [`GlweKeyswitchKey::from_container`] for usage.
+    pub fn polynomial_size(&self) -> PolynomialSize {
+        self.poly_size
+    }
+
+    /// Return the output [`GlweDimension`] of the [`GlweKeyswitchKey`].
+    ///
+    /// See [`GlweKeyswitchKey::from_container`] for usage.
+    pub fn output_key_glwe_dimension(&self) -> GlweDimension {
+        self.output_glwe_size.to_glwe_dimension()
+    }
+
+    /// Return the output [`GlweSize`] of the [`GlweKeyswitchKey`].
+    ///
+    /// See [`GlweKeyswitchKey::from_container`] for usage.
+    pub fn output_glwe_size(&self) -> GlweSize {
+        self.output_glwe_size
+    }
+
+    /// Return the number of elements in an encryption of an input [`GlweSecretKey`] element of the
+    /// current [`GlweKeyswitchKey`].
+    pub fn input_key_element_encrypted_size(&self) -> usize {
+        glwe_keyswitch_key_input_key_element_encrypted_size(
+            self.decomp_level_count,
+            self.output_glwe_size,
+            self.poly_size,
+        )
+    }
+
+    /// Return a view of the [`GlweKeyswitchKey`]. This is useful if an algorithm takes a view by
+    /// value.
+    pub fn as_view(&self) -> GlweKeyswitchKey<&'_ [Scalar]> {
+        GlweKeyswitchKey::from_container(
+            self.as_ref(),
+            self.decomp_base_log,
+            self.decomp_level_count,
+            self.output_glwe_size,
+            self.poly_size,
+            self.ciphertext_modulus,
+        )
+    }
+
+    /// Consume the entity and return its underlying container.
+    ///
+    /// See [`GlweKeyswitchKey::from_container`] for usage.
+    pub fn into_container(self) -> C {
+        self.data
+    }
+
+    pub fn as_glwe_ciphertext_list(&self) -> GlweCiphertextListView<'_, Scalar> {
+        GlweCiphertextListView::from_container(
+            self.as_ref(),
+            self.output_glwe_size(),
+            self.polynomial_size(),
+            self.ciphertext_modulus(),
+        )
+    }
+
+    /// Return the [`CiphertextModulus`] of the [`GlweKeyswitchKey`].
+    ///
+    /// See [`GlweKeyswitchKey::from_container`] for usage.
+    pub fn ciphertext_modulus(&self) -> CiphertextModulus<C::Element> {
+        self.ciphertext_modulus
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: ContainerMut<Element = Scalar>> GlweKeyswitchKey<C> {
+    /// Mutable variant of [`GlweKeyswitchKey::as_view`].
+    pub fn as_mut_view(&mut self) -> GlweKeyswitchKey<&'_ mut [Scalar]> {
+        let decomp_base_log = self.decomp_base_log;
+        let decomp_level_count = self.decomp_level_count;
+        let output_glwe_size = self.output_glwe_size;
+        let poly_size = self.poly_size;
+        let ciphertext_modulus = self.ciphertext_modulus;
+        GlweKeyswitchKey::from_container(
+            self.as_mut(),
+            decomp_base_log,
+            decomp_level_count,
+            output_glwe_size,
+            poly_size,
+            ciphertext_modulus,
+        )
+    }
+
+    pub fn as_mut_glwe_ciphertext_list(&mut self) -> GlweCiphertextListMutView<'_, Scalar> {
+        let output_glwe_size = self.output_glwe_size();
+        let poly_size = self.polynomial_size();
+        let ciphertext_modulus = self.ciphertext_modulus();
+        GlweCiphertextListMutView::from_container(
+            self.as_mut(),
+            output_glwe_size,
+            poly_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+/// A [`GlweKeyswitchKey`] owning the memory for its own storage.
+pub type GlweKeyswitchKeyOwned<Scalar> = GlweKeyswitchKey<Vec<Scalar>>;
+/// A [`GlweKeyswitchKey`] immutably borrowing memory for its own storage.
+pub type GlweKeyswitchKeyView<'data, Scalar> = GlweKeyswitchKey<&'data [Scalar]>;
+/// A [`GlweKeyswitchKey`] mutably borrowing memory for its own storage.
+pub type GlweKeyswitchKeyMutView<'data, Scalar> = GlweKeyswitchKey<&'data mut [Scalar]>;
+
+impl<Scalar: UnsignedInteger> GlweKeyswitchKeyOwned<Scalar> {
+    /// Allocate memory and create a new owned [`GlweKeyswitchKey`].
+    ///
+    /// # Note
+    ///
+    /// This function allocates a vector of the appropriate size and wraps it in the appropriate
+    /// type. If you want to generate an [`GlweKeyswitchKey`] you need to call
+    /// [`crate::core_crypto::algorithms::generate_glwe_keyswitch_key`] using this key as output.
+    ///
+    /// See [`GlweKeyswitchKey::from_container`] for usage.
+    pub fn new(
+        fill_with: Scalar,
+        decomp_base_log: DecompositionBaseLog,
+        decomp_level_count: DecompositionLevelCount,
+        input_key_glwe_dimension: GlweDimension,
+        output_key_glwe_dimension: GlweDimension,
+        poly_size: PolynomialSize,
+        ciphertext_modulus: CiphertextModulus<Scalar>,
+    ) -> Self {
+        Self::from_container(
+            vec![
+                fill_with;
+                input_key_glwe_dimension.0
+                    * glwe_keyswitch_key_input_key_element_encrypted_size(
+                        decomp_level_count,
+                        output_key_glwe_dimension.to_glwe_size(),
+                        poly_size,
+                    )
+            ],
+            decomp_base_log,
+            decomp_level_count,
+            output_key_glwe_dimension.to_glwe_size(),
+            poly_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+#[derive(Clone, Copy)]
+pub struct GlweKeyswitchKeyCreationMetadata<Scalar: UnsignedInteger> {
+    pub decomp_base_log: DecompositionBaseLog,
+    pub decomp_level_count: DecompositionLevelCount,
+    pub output_glwe_size: GlweSize,
+    pub polynomial_size: PolynomialSize,
+    pub ciphertext_modulus: CiphertextModulus<Scalar>,
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> CreateFrom<C>
+    for GlweKeyswitchKey<C>
+{
+    type Metadata = GlweKeyswitchKeyCreationMetadata<Scalar>;
+
+    #[inline]
+    fn create_from(from: C, meta: Self::Metadata) -> Self {
+        let GlweKeyswitchKeyCreationMetadata {
+            decomp_base_log,
+            decomp_level_count,
+            output_glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        } = meta;
+        Self::from_container(
+            from,
+            decomp_base_log,
+            decomp_level_count,
+            output_glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> ContiguousEntityContainer
+    for GlweKeyswitchKey<C>
+{
+    type Element = C::Element;
+
+    type EntityViewMetadata = GlweCiphertextListCreationMetadata<Self::Element>;
+
+    type EntityView<'this>
+        = GlweCiphertextListView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    type SelfViewMetadata = GlweKeyswitchKeyCreationMetadata<Self::Element>;
+
+    type SelfView<'this>
+        = GlweKeyswitchKeyView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    fn get_entity_view_creation_metadata(&self) -> Self::EntityViewMetadata {
+        GlweCiphertextListCreationMetadata {
+            glwe_size: self.output_glwe_size(),
+            polynomial_size: self.polynomial_size(),
+            ciphertext_modulus: self.ciphertext_modulus(),
+        }
+    }
+
+    fn get_entity_view_pod_size(&self) -> usize {
+        self.input_key_element_encrypted_size()
+    }
+
+    fn get_self_view_creation_metadata(&self) -> Self::SelfViewMetadata {
+        GlweKeyswitchKeyCreationMetadata {
+            decomp_base_log: self.decomposition_base_log(),
+            decomp_level_count: self.decomposition_level_count(),
+            output_glwe_size: self.output_glwe_size(),
+            polynomial_size: self.polynomial_size(),
+            ciphertext_modulus: self.ciphertext_modulus(),
+        }
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: ContainerMut<Element = Scalar>> ContiguousEntityContainerMut
+    for GlweKeyswitchKey<C>
+{
+    type EntityMutView<'this>
+        = GlweCiphertextListMutView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    type SelfMutView<'this>
+        = GlweKeyswitchKeyMutView<'this, Self::Element>
+    where
+        Self: 'this;
+}
+
+pub struct GlweKeyswitchKeyConformanceParams {
+    pub decomp_base_log: DecompositionBaseLog,
+    pub decomp_level_count: DecompositionLevelCount,
+    pub output_glwe_size: GlweSize,
+    pub input_glwe_dimension: GlweDimension,
+    pub polynomial_size: PolynomialSize,
+    pub ciphertext_modulus: CiphertextModulus<u64>,
+}
+
+impl<C: Container<Element = u64>> ParameterSetConformant for GlweKeyswitchKey<C> {
+    type ParameterSet = GlweKeyswitchKeyConformanceParams;
+
+    fn is_conformant(&self, parameter_set: &Self::ParameterSet) -> bool {
+        let Self {
+            data,
+            decomp_base_log,
+            decomp_level_count,
+            output_glwe_size,
+            poly_size,
+            ciphertext_modulus,
+        } = self;
+
+        *ciphertext_modulus == parameter_set.ciphertext_modulus
+            && data.container_len()
+                == parameter_set.input_glwe_dimension.0
+                    * glwe_keyswitch_key_input_key_element_encrypted_size(
+                        parameter_set.decomp_level_count,
+                        parameter_set.output_glwe_size,
+                        parameter_set.polynomial_size,
+                    )
+            && *decomp_base_log == parameter_set.decomp_base_log
+            && *decomp_level_count == parameter_set.decomp_level_count
+            && *output_glwe_size == parameter_set.output_glwe_size
+            && *poly_size == parameter_set.polynomial_size
+    }
+}

tfhe/src/core_crypto/entities/glwe_relinearization_key.rs

@@ -0,0 +1,422 @@
+//! Module containing the definition of the [`GlweRelinearizationKey`].
+
+use crate::conformance::ParameterSetConformant;
+use crate::core_crypto::commons::parameters::*;
+use crate::core_crypto::commons::traits::*;
+use crate::core_crypto::entities::*;
+
+/// A [`GLWE relinearization key`](`GlweRelinearizationKey`).
+#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
+pub struct GlweRelinearizationKey<C: Container>
+where
+    C::Element: UnsignedInteger,
+{
+    data: C,
+    decomp_base_log: DecompositionBaseLog,
+    decomp_level_count: DecompositionLevelCount,
+    glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+    ciphertext_modulus: CiphertextModulus<C::Element>,
+}
+
+impl<T: UnsignedInteger, C: Container<Element = T>> AsRef<[T]> for GlweRelinearizationKey<C> {
+    fn as_ref(&self) -> &[T] {
+        self.data.as_ref()
+    }
+}
+
+impl<T: UnsignedInteger, C: ContainerMut<Element = T>> AsMut<[T]> for GlweRelinearizationKey<C> {
+    fn as_mut(&mut self) -> &mut [T] {
+        self.data.as_mut()
+    }
+}
+
+/// Return the number of elements in an encryption of an input [`GlweSecretKey`] element for a
+/// [`GlweRelinearizationKey`] given a [`DecompositionLevelCount`], [`GlweSize`] and
+/// [`PolynomialSize`].
+pub fn glwe_relinearization_key_input_key_element_encrypted_size(
+    decomp_level_count: DecompositionLevelCount,
+    glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+) -> usize {
+    // One ciphertext per level encrypted under the output key
+    decomp_level_count.0 * glwe_size.0 * polynomial_size.0
+}
+
+/// Return the number of elements in a [`GlweRelinearizationKey`] given a
+/// [`DecompositionLevelCount`], [`GlweSize`], and [`PolynomialSize`].
+pub fn glwe_relinearization_key_size(
+    decomp_level_count: DecompositionLevelCount,
+    glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+) -> usize {
+    (glwe_size.to_glwe_dimension().0 * (glwe_size.to_glwe_dimension().0 + 1)) / 2
+        * glwe_relinearization_key_input_key_element_encrypted_size(
+            decomp_level_count,
+            glwe_size,
+            polynomial_size,
+        )
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> GlweRelinearizationKey<C> {
+    /// Create a [`GlweRelinearizationKey`] from an existing container.
+    ///
+    /// # Note
+    ///
+    /// This function only wraps a container in the appropriate type. If you want to generate an
+    /// [`GlweRelinearizationKey`] you need to use
+    /// [`crate::core_crypto::algorithms::generate_glwe_relinearization_key`]
+    /// using this key as output.
+    ///
+    /// This docstring exhibits [`GlweRelinearizationKey`] primitives usage.
+    ///
+    /// ```
+    /// use tfhe::core_crypto::prelude::*;
+    ///
+    /// // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
+    /// // computations
+    /// // Define parameters for GlweRelinearizationKey creation
+    /// let glwe_size = GlweSize(3);
+    /// let polynomial_size = PolynomialSize(1024);
+    /// let decomp_base_log = DecompositionBaseLog(8);
+    /// let decomp_level_count = DecompositionLevelCount(3);
+    /// let ciphertext_modulus = CiphertextModulus::new_native();
+    ///
+    /// // Create a new GlweRelinearizationKey
+    /// let relin_key = GlweRelinearizationKey::new(
+    ///     0u64,
+    ///     decomp_base_log,
+    ///     decomp_level_count,
+    ///     glwe_size,
+    ///     polynomial_size,
+    ///     ciphertext_modulus,
+    /// );
+    ///
+    /// assert_eq!(relin_key.glwe_dimension(), glwe_size.to_glwe_dimension());
+    /// assert_eq!(relin_key.glwe_size(), glwe_size);
+    /// assert_eq!(relin_key.polynomial_size(), polynomial_size);
+    /// assert_eq!(relin_key.decomposition_base_log(), decomp_base_log);
+    /// assert_eq!(relin_key.decomposition_level_count(), decomp_level_count);
+    /// assert_eq!(relin_key.ciphertext_modulus(), ciphertext_modulus);
+    ///
+    /// // Demonstrate how to recover the allocated container
+    /// let underlying_container: Vec<u64> = relin_key.into_container();
+    ///
+    /// // Recreate a key using from_container
+    /// let relin_key = GlweRelinearizationKey::from_container(
+    ///     underlying_container,
+    ///     decomp_base_log,
+    ///     decomp_level_count,
+    ///     glwe_size,
+    ///     polynomial_size,
+    ///     ciphertext_modulus,
+    /// );
+    ///
+    /// assert_eq!(relin_key.glwe_dimension(), glwe_size.to_glwe_dimension());
+    /// assert_eq!(relin_key.glwe_size(), glwe_size);
+    /// assert_eq!(relin_key.polynomial_size(), polynomial_size);
+    /// assert_eq!(relin_key.decomposition_base_log(), decomp_base_log);
+    /// assert_eq!(relin_key.decomposition_level_count(), decomp_level_count);
+    /// assert_eq!(relin_key.ciphertext_modulus(), ciphertext_modulus);
+    /// ```
+    pub fn from_container(
+        container: C,
+        decomp_base_log: DecompositionBaseLog,
+        decomp_level_count: DecompositionLevelCount,
+        glwe_size: GlweSize,
+        polynomial_size: PolynomialSize,
+        ciphertext_modulus: CiphertextModulus<C::Element>,
+    ) -> Self {
+        assert!(
+            container.container_len() > 0,
+            "Got an empty container to create a GlweRelinearizationKey"
+        );
+        assert!(
+            container.container_len()
+                % glwe_relinearization_key_input_key_element_encrypted_size(
+                    decomp_level_count,
+                    glwe_size,
+                    polynomial_size
+                )
+                == 0,
+            "The provided container length is not valid. \
+        It needs to be divisible by decomp_level_count * glwe_size * polynomial_size:\
+         {}. Got container length: {} and decomp_level_count: {decomp_level_count:?}, \
+        glwe_size: {glwe_size:?}, polynomial_size: {polynomial_size:?}.",
+            glwe_relinearization_key_input_key_element_encrypted_size(
+                decomp_level_count,
+                glwe_size,
+                polynomial_size
+            ),
+            container.container_len()
+        );
+
+        Self {
+            data: container,
+            decomp_base_log,
+            decomp_level_count,
+            glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        }
+    }
+
+    /// Return the [`GlweDimension`] of the [`GlweRelinearizationKey`].
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn glwe_dimension(&self) -> GlweDimension {
+        self.glwe_size.to_glwe_dimension()
+    }
+
+    /// Return the [`GlweSize`] of the [`GlweRelinearizationKey`].
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn glwe_size(&self) -> GlweSize {
+        self.glwe_size
+    }
+
+    /// Return the output [`PolynomialSize`] of the [`GlweRelinearizationKey`].
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn polynomial_size(&self) -> PolynomialSize {
+        self.polynomial_size
+    }
+
+    /// Return the [`DecompositionLevelCount`] of the [`GlweRelinearizationKey`].
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn decomposition_level_count(&self) -> DecompositionLevelCount {
+        self.decomp_level_count
+    }
+
+    /// Return the [`DecompositionBaseLog`] of the [`GlweRelinearizationKey`].
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn decomposition_base_log(&self) -> DecompositionBaseLog {
+        self.decomp_base_log
+    }
+
+    /// Return the number of elements in an encryption of an input [`GlweSecretKey`] element of the
+    /// current [`GlweRelinearizationKey`].
+    pub fn input_key_element_encrypted_size(&self) -> usize {
+        glwe_relinearization_key_input_key_element_encrypted_size(
+            self.decomp_level_count,
+            self.glwe_size,
+            self.polynomial_size,
+        )
+    }
+
+    /// Return a view of the [`GlweRelinearizationKey`]. This is useful if an
+    /// algorithm takes a view by value.
+    pub fn as_view(&self) -> GlweRelinearizationKey<&'_ [Scalar]> {
+        GlweRelinearizationKey::from_container(
+            self.as_ref(),
+            self.decomp_base_log,
+            self.decomp_level_count,
+            self.glwe_size,
+            self.polynomial_size,
+            self.ciphertext_modulus,
+        )
+    }
+
+    /// Consume the entity and return its underlying container.
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn into_container(self) -> C {
+        self.data
+    }
+
+    /// Return the [`CiphertextModulus`] of the [`GlweRelinearizationKey`]
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn ciphertext_modulus(&self) -> CiphertextModulus<C::Element> {
+        self.ciphertext_modulus
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: ContainerMut<Element = Scalar>> GlweRelinearizationKey<C> {
+    /// Mutable variant of [`GlweRelinearizationKey::as_view`].
+    pub fn as_mut_view(&mut self) -> GlweRelinearizationKey<&'_ mut [Scalar]> {
+        let decomp_base_log = self.decomp_base_log;
+        let decomp_level_count = self.decomp_level_count;
+        let glwe_size = self.glwe_size;
+        let polynomial_size = self.polynomial_size;
+        let ciphertext_modulus = self.ciphertext_modulus;
+
+        GlweRelinearizationKey::from_container(
+            self.as_mut(),
+            decomp_base_log,
+            decomp_level_count,
+            glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+/// A [`GlweRelinearizationKey`] owning the memory for its own storage.
+pub type GlweRelinearizationKeyOwned<Scalar> = GlweRelinearizationKey<Vec<Scalar>>;
+/// A [`GlweRelinearizationKey`] immutably borrowing memory for its own storage.
+pub type GlweRelinearizationKeyView<'data, Scalar> = GlweRelinearizationKey<&'data [Scalar]>;
+/// A [`GlweRelinearizationKey`] mutably borrowing memory for its own storage.
+pub type GlweRelinearizationKeyMutView<'data, Scalar> = GlweRelinearizationKey<&'data mut [Scalar]>;
+
+impl<Scalar: UnsignedInteger> GlweRelinearizationKeyOwned<Scalar> {
+    /// Create a new [`GlweRelinearizationKey`].
+    ///
+    /// # Note
+    ///
+    /// This function allocates a vector of the appropriate size and wraps it in the appropriate
+    /// type. If you want to generate an [`GlweRelinearizationKey`] you need to use
+    /// [`crate::core_crypto::algorithms::generate_glwe_relinearization_key`]
+    /// using this key as output.
+    ///
+    /// See [`GlweRelinearizationKey::from_container`] for usage.
+    pub fn new(
+        fill_with: Scalar,
+        decomp_base_log: DecompositionBaseLog,
+        decomp_level_count: DecompositionLevelCount,
+        glwe_size: GlweSize,
+        polynomial_size: PolynomialSize,
+        ciphertext_modulus: CiphertextModulus<Scalar>,
+    ) -> Self {
+        Self::from_container(
+            vec![
+                fill_with;
+                glwe_relinearization_key_size(decomp_level_count, glwe_size, polynomial_size)
+            ],
+            decomp_base_log,
+            decomp_level_count,
+            glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+/// Metadata used in the [`CreateFrom`] implementation to create
+/// [`GlweRelinearizationKey`] entities.
+#[derive(Clone, Copy)]
+pub struct GlweRelinearizationKeyCreationMetadata<Scalar: UnsignedInteger> {
+    pub decomp_base_log: DecompositionBaseLog,
+    pub decomp_level_count: DecompositionLevelCount,
+    pub glwe_size: GlweSize,
+    pub polynomial_size: PolynomialSize,
+    pub ciphertext_modulus: CiphertextModulus<Scalar>,
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> CreateFrom<C>
+    for GlweRelinearizationKey<C>
+{
+    type Metadata = GlweRelinearizationKeyCreationMetadata<Scalar>;
+
+    #[inline]
+    fn create_from(from: C, meta: Self::Metadata) -> Self {
+        let GlweRelinearizationKeyCreationMetadata {
+            decomp_base_log,
+            decomp_level_count,
+            glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        } = meta;
+        Self::from_container(
+            from,
+            decomp_base_log,
+            decomp_level_count,
+            glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> ContiguousEntityContainer
+    for GlweRelinearizationKey<C>
+{
+    type Element = C::Element;
+
+    type EntityViewMetadata = GlweCiphertextListCreationMetadata<Self::Element>;
+
+    type EntityView<'this>
+        = GlweCiphertextListView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    type SelfViewMetadata = GlweRelinearizationKeyCreationMetadata<Self::Element>;
+
+    type SelfView<'this>
+        = GlweRelinearizationKeyView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    fn get_entity_view_creation_metadata(&self) -> Self::EntityViewMetadata {
+        GlweCiphertextListCreationMetadata {
+            glwe_size: self.glwe_size(),
+            polynomial_size: self.polynomial_size(),
+            ciphertext_modulus: self.ciphertext_modulus(),
+        }
+    }
+
+    fn get_entity_view_pod_size(&self) -> usize {
+        self.input_key_element_encrypted_size()
+    }
+
+    fn get_self_view_creation_metadata(&self) -> Self::SelfViewMetadata {
+        GlweRelinearizationKeyCreationMetadata {
+            decomp_base_log: self.decomposition_base_log(),
+            decomp_level_count: self.decomposition_level_count(),
+            glwe_size: self.glwe_size(),
+            polynomial_size: self.polynomial_size(),
+            ciphertext_modulus: self.ciphertext_modulus(),
+        }
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: ContainerMut<Element = Scalar>> ContiguousEntityContainerMut
+    for GlweRelinearizationKey<C>
+{
+    type EntityMutView<'this>
+        = GlweCiphertextListMutView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    type SelfMutView<'this>
+        = GlweRelinearizationKeyMutView<'this, Self::Element>
+    where
+        Self: 'this;
+}
+
+pub struct RelinearizationKeyConformanceParmas {
+    pub decomp_base_log: DecompositionBaseLog,
+    pub decomp_level_count: DecompositionLevelCount,
+    pub glwe_size: GlweSize,
+    pub polynomial_size: PolynomialSize,
+    pub ciphertext_modulus: CiphertextModulus<u64>,
+}
+
+impl<C: Container<Element = u64>> ParameterSetConformant for GlweRelinearizationKey<C> {
+    type ParameterSet = RelinearizationKeyConformanceParmas;
+
+    fn is_conformant(&self, parameter_set: &Self::ParameterSet) -> bool {
+        let Self {
+            data,
+            decomp_base_log,
+            decomp_level_count,
+            glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        } = self;
+
+        *ciphertext_modulus == parameter_set.ciphertext_modulus
+            && data.container_len()
+                == glwe_relinearization_key_size(
+                    parameter_set.decomp_level_count,
+                    parameter_set.glwe_size,
+                    parameter_set.polynomial_size,
+                )
+            && *decomp_base_log == parameter_set.decomp_base_log
+            && *decomp_level_count == parameter_set.decomp_level_count
+            && *glwe_size == parameter_set.glwe_size
+            && *polynomial_size == parameter_set.polynomial_size
+    }
+}

tfhe/src/core_crypto/entities/lwe_trace_packing_keyswitch_key.rs

@@ -0,0 +1,558 @@
+//! Module containing the definition of the [`LweTracePackingKeyswitchKey`].
+
+use crate::conformance::ParameterSetConformant;
+use crate::core_crypto::commons::generators::EncryptionRandomGeneratorForkConfig;
+use crate::core_crypto::commons::math::random::{Distribution, RandomGenerable};
+use crate::core_crypto::commons::parameters::*;
+use crate::core_crypto::commons::traits::*;
+use crate::core_crypto::entities::*;
+
+/// An [`LWE trace packing keyswitch key`](`LweTracePackingKeyswitchKey`).
+#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
+pub struct LweTracePackingKeyswitchKey<C: Container>
+where
+    C::Element: UnsignedInteger,
+{
+    data: C,
+    decomp_base_log: DecompositionBaseLog,
+    decomp_level_count: DecompositionLevelCount,
+    input_lwe_size: LweSize,
+    output_glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+    ciphertext_modulus: CiphertextModulus<C::Element>,
+}
+
+impl<T: UnsignedInteger, C: Container<Element = T>> AsRef<[T]> for LweTracePackingKeyswitchKey<C> {
+    fn as_ref(&self) -> &[T] {
+        self.data.as_ref()
+    }
+}
+
+impl<T: UnsignedInteger, C: ContainerMut<Element = T>> AsMut<[T]>
+    for LweTracePackingKeyswitchKey<C>
+{
+    fn as_mut(&mut self) -> &mut [T] {
+        self.data.as_mut()
+    }
+}
+
+/// Return the number of elements in an encryption of an input [`GlweSecretKey`] element for a
+/// [`LweTracePackingKeyswitchKey`] given a [`DecompositionLevelCount`] and output
+/// [`GlweSize`] and [`PolynomialSize`].
+pub fn lwe_tpksk_input_key_element_encrypted_size(
+    decomp_level_count: DecompositionLevelCount,
+    output_glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+) -> usize {
+    // One ciphertext per level encrypted under the output key
+    decomp_level_count.0 * output_glwe_size.0 * polynomial_size.0
+}
+
+/// Return the number of elements in an [`LweTracePackingKeyswitchKey`] given a
+/// [`DecompositionLevelCount`], output [`GlweSize`], and output [`PolynomialSize`].
+pub fn lwe_tpksk_size(
+    decomp_level_count: DecompositionLevelCount,
+    output_glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+) -> usize {
+    output_glwe_size.to_glwe_dimension().0
+        * polynomial_size.log2().0
+        * lwe_tpksk_input_key_element_encrypted_size(
+            decomp_level_count,
+            output_glwe_size,
+            polynomial_size,
+        )
+}
+
+pub fn tpksk_encryption_mask_sample_count(
+    glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+    decomp_level_count: DecompositionLevelCount,
+) -> EncryptionMaskSampleCount {
+    decomp_level_count.0
+        * glwe_size.to_glwe_dimension().0
+        * glwe_ciphertext_encryption_mask_sample_count(
+            glwe_size.to_glwe_dimension(),
+            polynomial_size,
+        )
+}
+
+pub fn tpksk_encryption_noise_sample_count(
+    polynomial_size: PolynomialSize,
+    decomp_level_count: DecompositionLevelCount,
+) -> EncryptionNoiseSampleCount {
+    decomp_level_count.0 * glwe_ciphertext_encryption_noise_sample_count(polynomial_size)
+}
+
+pub fn lwe_trace_packing_keyswitch_key_encryption_fork_config<
+    Scalar,
+    MaskDistribution,
+    NoiseDistribution,
+>(
+    glwe_size: GlweSize,
+    polynomial_size: PolynomialSize,
+    decomposition_level_count: DecompositionLevelCount,
+    mask_distribution: MaskDistribution,
+    noise_distribution: NoiseDistribution,
+    ciphertext_modulus: CiphertextModulus<Scalar>,
+) -> EncryptionRandomGeneratorForkConfig
+where
+    Scalar: UnsignedInteger
+        + RandomGenerable<MaskDistribution, CustomModulus = Scalar>
+        + RandomGenerable<NoiseDistribution, CustomModulus = Scalar>,
+    MaskDistribution: Distribution,
+    NoiseDistribution: Distribution,
+{
+    let tpksk_mask_sample_count =
+        tpksk_encryption_mask_sample_count(glwe_size, polynomial_size, decomposition_level_count);
+    let tpksk_noise_sample_count =
+        tpksk_encryption_noise_sample_count(polynomial_size, decomposition_level_count);
+
+    let modulus = ciphertext_modulus.get_custom_modulus_as_optional_scalar();
+
+    EncryptionRandomGeneratorForkConfig::new(
+        polynomial_size.log2().0,
+        tpksk_mask_sample_count,
+        mask_distribution,
+        tpksk_noise_sample_count,
+        noise_distribution,
+        modulus,
+    )
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> LweTracePackingKeyswitchKey<C> {
+    /// Create an [`LweTracePackingKeyswitchKey`] from an existing container.
+    ///
+    /// # Note
+    ///
+    /// This function only wraps a container in the appropriate type. If you want to generate an
+    /// [`LweTracePackingKeyswitchKey`] you need to use
+    /// [`crate::core_crypto::algorithms::generate_lwe_trace_packing_keyswitch_key`]
+    /// using this key as output.
+    ///
+    /// This docstring exhibits [`LweTracePackingKeyswitchKey`] primitives usage.
+    ///
+    /// ```
+    /// use tfhe::core_crypto::prelude::*;
+    ///
+    /// // DISCLAIMER: these toy example parameters are not guaranteed to be secure or yield correct
+    /// // computations
+    /// // Define parameters for LweTracePackingKeyswitchKey creation
+    /// let lwe_size = LweSize(1001);
+    /// let glwe_size = GlweSize(2);
+    /// let polynomial_size = PolynomialSize(1024);
+    /// let decomp_base_log = DecompositionBaseLog(8);
+    /// let decomp_level_count = DecompositionLevelCount(3);
+    /// let ciphertext_modulus = CiphertextModulus::new_native();
+    ///
+    /// // Create a new LweTracePackingKeyswitchKey
+    /// let tpksk = LweTracePackingKeyswitchKey::new(
+    ///     0u64,
+    ///     decomp_base_log,
+    ///     decomp_level_count,
+    ///     lwe_size,
+    ///     glwe_size,
+    ///     polynomial_size,
+    ///     ciphertext_modulus,
+    /// );
+    ///
+    /// assert_eq!(
+    ///     tpksk.output_glwe_key_dimension(),
+    ///     glwe_size.to_glwe_dimension()
+    /// );
+    /// assert_eq!(tpksk.output_glwe_size(), glwe_size);
+    /// assert_eq!(tpksk.polynomial_size(), polynomial_size);
+    /// assert_eq!(tpksk.decomposition_base_log(), decomp_base_log);
+    /// assert_eq!(tpksk.decomposition_level_count(), decomp_level_count);
+    /// assert_eq!(tpksk.ciphertext_modulus(), ciphertext_modulus);
+    ///
+    /// // Demonstrate how to recover the allocated container
+    /// let underlying_container: Vec<u64> = tpksk.into_container();
+    ///
+    /// // Recreate a key using from_container
+    /// let tpksk = LweTracePackingKeyswitchKey::from_container(
+    ///     underlying_container,
+    ///     decomp_base_log,
+    ///     decomp_level_count,
+    ///     lwe_size,
+    ///     glwe_size,
+    ///     polynomial_size,
+    ///     ciphertext_modulus,
+    /// );
+    ///
+    /// assert_eq!(
+    ///     tpksk.output_glwe_key_dimension(),
+    ///     glwe_size.to_glwe_dimension()
+    /// );
+    /// assert_eq!(tpksk.input_lwe_size(), lwe_size);
+    /// assert_eq!(tpksk.output_glwe_size(), glwe_size);
+    /// assert_eq!(tpksk.polynomial_size(), polynomial_size);
+    /// assert_eq!(tpksk.decomposition_base_log(), decomp_base_log);
+    /// assert_eq!(tpksk.decomposition_level_count(), decomp_level_count);
+    /// assert_eq!(tpksk.ciphertext_modulus(), ciphertext_modulus);
+    /// ```
+    pub fn from_container(
+        container: C,
+        decomp_base_log: DecompositionBaseLog,
+        decomp_level_count: DecompositionLevelCount,
+        input_lwe_size: LweSize,
+        output_glwe_size: GlweSize,
+        polynomial_size: PolynomialSize,
+        ciphertext_modulus: CiphertextModulus<C::Element>,
+    ) -> Self {
+        assert!(
+            container.container_len() > 0,
+            "Got an empty container to create a LweTracePackingKeyswitchKey"
+        );
+        assert!(
+            container.container_len()
+                % lwe_tpksk_input_key_element_encrypted_size(
+                    decomp_level_count,
+                    output_glwe_size,
+                    polynomial_size
+                )
+                == 0,
+            "The provided container length is not valid. \
+        It needs to be divisible by decomp_level_count * output_glwe_size * polynomial_size:\
+         {}. Got container length: {} and decomp_level_count: {decomp_level_count:?}, \
+        output_glwe_size: {output_glwe_size:?}, polynomial_size: \
+        {polynomial_size:?}.",
+            lwe_tpksk_input_key_element_encrypted_size(
+                decomp_level_count,
+                output_glwe_size,
+                polynomial_size
+            ),
+            container.container_len()
+        );
+
+        Self {
+            data: container,
+            decomp_base_log,
+            decomp_level_count,
+            input_lwe_size,
+            output_glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        }
+    }
+
+    /// Return the output key [`GlweDimension`] of the [`LweTracePackingKeyswitchKey`].
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn output_glwe_key_dimension(&self) -> GlweDimension {
+        self.output_glwe_size.to_glwe_dimension()
+    }
+
+    /// Return the output [`GlweSize`] of the [`LweTracePackingKeyswitchKey`].
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn output_glwe_size(&self) -> GlweSize {
+        self.output_glwe_size
+    }
+
+    /// Return the output [`PolynomialSize`] of the [`LweTracePackingKeyswitchKey`].
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn polynomial_size(&self) -> PolynomialSize {
+        self.polynomial_size
+    }
+
+    /// Return the input [`LweSize`] of the [`LweTracePackingKeyswitchKey`].
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn input_lwe_size(&self) -> LweSize {
+        self.input_lwe_size
+    }
+
+    /// Return the [`DecompositionLevelCount`] of the [`LweTracePackingKeyswitchKey`].
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn decomposition_level_count(&self) -> DecompositionLevelCount {
+        self.decomp_level_count
+    }
+
+    /// Return the [`DecompositionBaseLog`] of the [`LweTracePackingKeyswitchKey`].
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn decomposition_base_log(&self) -> DecompositionBaseLog {
+        self.decomp_base_log
+    }
+
+    /// Return the number of elements in an encryption of an input [`LweSecretKey`] element of the
+    /// current [`LweTracePackingKeyswitchKey`].
+    pub fn input_key_element_encrypted_size(&self) -> usize {
+        lwe_tpksk_input_key_element_encrypted_size(
+            self.decomp_level_count,
+            self.output_glwe_size,
+            self.polynomial_size,
+        )
+    }
+
+    /// Return a view of the [`LweTracePackingKeyswitchKey`]. This is useful if an
+    /// algorithm takes a view by value.
+    pub fn as_view(&self) -> LweTracePackingKeyswitchKey<&'_ [Scalar]> {
+        LweTracePackingKeyswitchKey::from_container(
+            self.as_ref(),
+            self.decomp_base_log,
+            self.decomp_level_count,
+            self.input_lwe_size,
+            self.output_glwe_size,
+            self.polynomial_size,
+            self.ciphertext_modulus,
+        )
+    }
+
+    /// Consume the entity and return its underlying container.
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn into_container(self) -> C {
+        self.data
+    }
+
+    pub fn as_glwe_ciphertext_list(&self) -> GlweCiphertextListView<'_, Scalar> {
+        GlweCiphertextListView::from_container(
+            self.as_ref(),
+            self.output_glwe_size(),
+            self.polynomial_size(),
+            self.ciphertext_modulus(),
+        )
+    }
+
+    /// Return the [`CiphertextModulus`] of the [`LweTracePackingKeyswitchKey`]
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn ciphertext_modulus(&self) -> CiphertextModulus<C::Element> {
+        self.ciphertext_modulus
+    }
+
+    pub fn encryption_fork_config<MaskDistribution, NoiseDistribution>(
+        &self,
+        mask_distribution: MaskDistribution,
+        noise_distribution: NoiseDistribution,
+    ) -> EncryptionRandomGeneratorForkConfig
+    where
+        MaskDistribution: Distribution,
+        NoiseDistribution: Distribution,
+        Scalar: RandomGenerable<MaskDistribution, CustomModulus = Scalar>
+            + RandomGenerable<NoiseDistribution, CustomModulus = Scalar>,
+    {
+        lwe_trace_packing_keyswitch_key_encryption_fork_config(
+            self.output_glwe_size(),
+            self.polynomial_size(),
+            self.decomposition_level_count(),
+            mask_distribution,
+            noise_distribution,
+            self.ciphertext_modulus(),
+        )
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: ContainerMut<Element = Scalar>> LweTracePackingKeyswitchKey<C> {
+    /// Mutable variant of [`LweTracePackingKeyswitchKey::as_view`].
+    pub fn as_mut_view(&mut self) -> LweTracePackingKeyswitchKey<&'_ mut [Scalar]> {
+        let decomp_base_log = self.decomp_base_log;
+        let decomp_level_count = self.decomp_level_count;
+        let input_lwe_size = self.input_lwe_size;
+        let output_glwe_size = self.output_glwe_size;
+        let polynomial_size = self.polynomial_size;
+        let ciphertext_modulus = self.ciphertext_modulus;
+        LweTracePackingKeyswitchKey::from_container(
+            self.as_mut(),
+            decomp_base_log,
+            decomp_level_count,
+            input_lwe_size,
+            output_glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        )
+    }
+
+    pub fn as_mut_glwe_ciphertext_list(&mut self) -> GlweCiphertextListMutView<'_, Scalar> {
+        let output_glwe_size = self.output_glwe_size();
+        let output_polynomial_size = self.polynomial_size();
+        let ciphertext_modulus = self.ciphertext_modulus();
+        GlweCiphertextListMutView::from_container(
+            self.as_mut(),
+            output_glwe_size,
+            output_polynomial_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+/// An [`LweTracePackingKeyswitchKey`] owning the memory for its own storage.
+pub type LweTracePackingKeyswitchKeyOwned<Scalar> = LweTracePackingKeyswitchKey<Vec<Scalar>>;
+/// An [`LweTracePackingKeyswitchKey`] immutably borrowing memory for its own storage.
+pub type LweTracePackingKeyswitchKeyView<'data, Scalar> =
+    LweTracePackingKeyswitchKey<&'data [Scalar]>;
+/// An [`LweTracePackingKeyswitchKey`] mutably borrowing memory for its own storage.
+pub type LweTracePackingKeyswitchKeyMutView<'data, Scalar> =
+    LweTracePackingKeyswitchKey<&'data mut [Scalar]>;
+
+impl<Scalar: UnsignedInteger> LweTracePackingKeyswitchKeyOwned<Scalar> {
+    /// Create an [`LweTracePackingKeyswitchKey`] from an existing container.
+    ///
+    /// # Note
+    ///
+    /// This function allocates a vector of the appropriate size and wraps it in the appropriate
+    /// type. If you want to generate an [`LweTracePackingKeyswitchKey`] you need to use
+    /// [`crate::core_crypto::algorithms::generate_lwe_trace_packing_keyswitch_key`]
+    /// using this key as output.
+    ///
+    /// See [`LweTracePackingKeyswitchKey::from_container`] for usage.
+    pub fn new(
+        fill_with: Scalar,
+        decomp_base_log: DecompositionBaseLog,
+        decomp_level_count: DecompositionLevelCount,
+        input_lwe_size: LweSize,
+        output_glwe_size: GlweSize,
+        poly_size: PolynomialSize,
+        ciphertext_modulus: CiphertextModulus<Scalar>,
+    ) -> Self {
+        Self::from_container(
+            vec![fill_with; lwe_tpksk_size(decomp_level_count, output_glwe_size, poly_size)],
+            decomp_base_log,
+            decomp_level_count,
+            input_lwe_size,
+            output_glwe_size,
+            poly_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+/// Metadata used in the [`CreateFrom`] implementation to create
+/// [`LweTracePackingKeyswitchKey`] entities.
+#[derive(Clone, Copy)]
+pub struct LweTracePackingKeyswitchKeyCreationMetadata<Scalar: UnsignedInteger> {
+    pub decomp_base_log: DecompositionBaseLog,
+    pub decomp_level_count: DecompositionLevelCount,
+    pub input_lwe_size: LweSize,
+    pub output_glwe_size: GlweSize,
+    pub polynomial_size: PolynomialSize,
+    pub ciphertext_modulus: CiphertextModulus<Scalar>,
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> CreateFrom<C>
+    for LweTracePackingKeyswitchKey<C>
+{
+    type Metadata = LweTracePackingKeyswitchKeyCreationMetadata<Scalar>;
+
+    #[inline]
+    fn create_from(from: C, meta: Self::Metadata) -> Self {
+        let LweTracePackingKeyswitchKeyCreationMetadata {
+            decomp_base_log,
+            decomp_level_count,
+            input_lwe_size,
+            output_glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        } = meta;
+        Self::from_container(
+            from,
+            decomp_base_log,
+            decomp_level_count,
+            input_lwe_size,
+            output_glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        )
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: Container<Element = Scalar>> ContiguousEntityContainer
+    for LweTracePackingKeyswitchKey<C>
+{
+    type Element = C::Element;
+
+    type EntityViewMetadata = GlweCiphertextListCreationMetadata<Scalar>;
+
+    type EntityView<'this>
+        = GlweCiphertextListView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    type SelfViewMetadata = LweTracePackingKeyswitchKeyCreationMetadata<Self::Element>;
+
+    type SelfView<'this>
+        = LweTracePackingKeyswitchKeyView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    fn get_entity_view_creation_metadata(&self) -> Self::EntityViewMetadata {
+        GlweCiphertextListCreationMetadata {
+            glwe_size: self.output_glwe_size(),
+            polynomial_size: self.polynomial_size(),
+            ciphertext_modulus: self.ciphertext_modulus(),
+        }
+    }
+
+    fn get_entity_view_pod_size(&self) -> usize {
+        self.input_key_element_encrypted_size() * self.output_glwe_size.to_glwe_dimension().0
+    }
+
+    /// Unimplemented for [`LweTracePackingKeyswitchKey`]. At the moment it does not
+    /// make sense to return "sub" packing keyswitch keys.
+    fn get_self_view_creation_metadata(&self) -> Self::SelfViewMetadata {
+        LweTracePackingKeyswitchKeyCreationMetadata {
+            decomp_base_log: self.decomposition_base_log(),
+            decomp_level_count: self.decomposition_level_count(),
+            input_lwe_size: self.input_lwe_size(),
+            output_glwe_size: self.output_glwe_size(),
+            polynomial_size: self.polynomial_size(),
+            ciphertext_modulus: self.ciphertext_modulus(),
+        }
+    }
+}
+
+impl<Scalar: UnsignedInteger, C: ContainerMut<Element = Scalar>> ContiguousEntityContainerMut
+    for LweTracePackingKeyswitchKey<C>
+{
+    type EntityMutView<'this>
+        = GlweCiphertextListMutView<'this, Self::Element>
+    where
+        Self: 'this;
+
+    type SelfMutView<'this>
+        = LweTracePackingKeyswitchKeyMutView<'this, Self::Element>
+    where
+        Self: 'this;
+}
+
+pub struct LweTracePackingKeyswitchKeyConformanceParams {
+    pub decomp_base_log: DecompositionBaseLog,
+    pub decomp_level_count: DecompositionLevelCount,
+    pub input_lwe_size: LweSize,
+    pub output_glwe_size: GlweSize,
+    pub polynomial_size: PolynomialSize,
+    pub ciphertext_modulus: CiphertextModulus<u64>,
+}
+
+impl<C: Container<Element = u64>> ParameterSetConformant for LweTracePackingKeyswitchKey<C> {
+    type ParameterSet = LweTracePackingKeyswitchKeyConformanceParams;
+
+    fn is_conformant(&self, parameter_set: &Self::ParameterSet) -> bool {
+        let Self {
+            data,
+            decomp_base_log,
+            decomp_level_count,
+            input_lwe_size,
+            output_glwe_size,
+            polynomial_size,
+            ciphertext_modulus,
+        } = self;
+
+        *ciphertext_modulus == parameter_set.ciphertext_modulus
+            && data.container_len()
+                == lwe_tpksk_size(
+                    parameter_set.decomp_level_count,
+                    parameter_set.output_glwe_size,
+                    parameter_set.polynomial_size,
+                )
+            && *decomp_base_log == parameter_set.decomp_base_log
+            && *decomp_level_count == parameter_set.decomp_level_count
+            && *input_lwe_size == parameter_set.input_lwe_size
+            && *output_glwe_size == parameter_set.output_glwe_size
+            && *polynomial_size == parameter_set.polynomial_size
+    }
+}

tfhe/src/core_crypto/entities/mod.rs

@@ -11,6 +11,8 @@ pub mod ggsw_ciphertext;
 pub mod ggsw_ciphertext_list;
 pub mod glwe_ciphertext;
 pub mod glwe_ciphertext_list;
+pub mod glwe_keyswitch_key;
+pub mod glwe_relinearization_key;
 pub mod glwe_secret_key;
 pub mod gsw_ciphertext;
 pub mod lwe_bootstrap_key;
@@ -25,6 +27,7 @@ pub mod lwe_private_functional_packing_keyswitch_key;
 pub mod lwe_private_functional_packing_keyswitch_key_list;
 pub mod lwe_public_key;
 pub mod lwe_secret_key;
+pub mod lwe_trace_packing_keyswitch_key;
 pub mod ntt_ggsw_ciphertext;
 pub mod ntt_ggsw_ciphertext_list;
 pub mod ntt_lwe_bootstrap_key;
@@ -68,6 +71,8 @@ pub use ggsw_ciphertext::*;
 pub use ggsw_ciphertext_list::*;
 pub use glwe_ciphertext::*;
 pub use glwe_ciphertext_list::*;
+pub use glwe_keyswitch_key::*;
+pub use glwe_relinearization_key::*;
 pub use glwe_secret_key::*;
 pub use gsw_ciphertext::*;
 pub use lwe_bootstrap_key::*;
@@ -82,6 +87,7 @@ pub use lwe_private_functional_packing_keyswitch_key::*;
 pub use lwe_private_functional_packing_keyswitch_key_list::*;
 pub use lwe_public_key::*;
 pub use lwe_secret_key::*;
+pub use lwe_trace_packing_keyswitch_key::*;
 pub use ntt_ggsw_ciphertext::*;
 pub use ntt_ggsw_ciphertext_list::*;
 pub use ntt_lwe_bootstrap_key::*;

tfhe/src/shortint/keycache.rs

@@ -268,6 +268,23 @@ impl NamedParam for CompressionParameters {
     }
 }
 
+impl NamedParam for GlweMultParameters {
+    fn name(&self) -> String {
+        named_params_impl!(expose MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_10);
+        named_params_impl!(
+            {
+                *self;
+                Self
+            } == (MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_10)
+        );
+
+        format!(
+            "MULT_PARAM_NOISE_DISTRIB_{}",
+            self.packing_ks_key_noise_distribution
+        )
+    }
+}
+
 impl From<PBSParameters> for (ClientKey, ServerKey) {
     fn from(param: PBSParameters) -> Self {
         let param_set = ShortintParameterSet::from(param);

tfhe/src/shortint/parameters/glwe_multiplication.rs

@@ -0,0 +1,62 @@
+use crate::core_crypto::prelude::*;
+use crate::shortint::parameters::{CarryModulus, MessageModulus};
+
+#[derive(Copy, Clone, Debug, PartialEq, serde::Serialize, serde::Deserialize)]
+pub struct GlweMultParameters {
+    pub message_modulus: MessageModulus,
+    pub carry_modulus: CarryModulus,
+    pub packing_ks_level: DecompositionLevelCount,
+    pub packing_ks_base_log: DecompositionBaseLog,
+    pub packing_ks_polynomial_size: PolynomialSize,
+    pub packing_ks_glwe_dimension: GlweDimension,
+    pub lwe_dimension: LweDimension,
+    pub lwe_per_glwe: LweCiphertextCount,
+    pub packing_ks_key_noise_distribution: DynamicDistribution<u64>,
+    pub lwe_noise_distribution: DynamicDistribution<u64>,
+    pub ciphertext_modulus: CiphertextModulus<u64>,
+}
+
+pub const MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_1000: GlweMultParameters =
+    GlweMultParameters {
+        message_modulus: MessageModulus(4),
+        carry_modulus: CarryModulus(4),
+        packing_ks_level: DecompositionLevelCount(2),
+        packing_ks_base_log: DecompositionBaseLog(14),
+        packing_ks_polynomial_size: PolynomialSize(1024),
+        packing_ks_glwe_dimension: GlweDimension(2),
+        lwe_dimension: LweDimension(2048),
+        lwe_per_glwe: LweCiphertextCount(1000),
+        packing_ks_key_noise_distribution: DynamicDistribution::new_t_uniform(17),
+        lwe_noise_distribution: DynamicDistribution::new_t_uniform(17),
+        ciphertext_modulus: CiphertextModulus::new_native(),
+    };
+
+pub const MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_100: GlweMultParameters =
+    GlweMultParameters {
+        message_modulus: MessageModulus(4),
+        carry_modulus: CarryModulus(4),
+        packing_ks_level: DecompositionLevelCount(1),
+        packing_ks_base_log: DecompositionBaseLog(28),
+        packing_ks_polynomial_size: PolynomialSize(512),
+        packing_ks_glwe_dimension: GlweDimension(5),
+        lwe_dimension: LweDimension(2048),
+        lwe_per_glwe: LweCiphertextCount(100),
+        packing_ks_key_noise_distribution: DynamicDistribution::new_t_uniform(5),
+        lwe_noise_distribution: DynamicDistribution::new_t_uniform(18),
+        ciphertext_modulus: CiphertextModulus::new_native(),
+    };
+
+pub const MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_10: GlweMultParameters =
+    GlweMultParameters {
+        message_modulus: MessageModulus(4),
+        carry_modulus: CarryModulus(4),
+        packing_ks_level: DecompositionLevelCount(1),
+        packing_ks_base_log: DecompositionBaseLog(29),
+        packing_ks_polynomial_size: PolynomialSize(512),
+        packing_ks_glwe_dimension: GlweDimension(5),
+        lwe_dimension: LweDimension(2048),
+        lwe_per_glwe: LweCiphertextCount(10),
+        packing_ks_key_noise_distribution: DynamicDistribution::new_t_uniform(4),
+        lwe_noise_distribution: DynamicDistribution::new_t_uniform(17),
+        ciphertext_modulus: CiphertextModulus::new_native(),
+    };

tfhe/src/shortint/parameters/mod.rs

@@ -25,6 +25,7 @@ pub mod classic;
 pub mod compact_public_key_only;
 #[cfg(tarpaulin)]
 pub mod coverage_parameters;
+pub mod glwe_multiplication;
 pub mod key_switching;
 pub mod list_compression;
 pub mod multi_bit;
@@ -45,6 +46,11 @@ pub use crate::shortint::parameters::classic::tuniform::p_fail_2_minus_64::pbs_k
 pub use crate::shortint::parameters::list_compression::{
     CompressionParameters, COMP_PARAM_MESSAGE_2_CARRY_2_KS_PBS_TUNIFORM_2M64,
 };
+pub use crate::shortint::parameters::glwe_multiplication::{
+    GlweMultParameters, MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_1000,
+    MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_100,
+    MULT_PARAM_MESSAGE_2_CARRY_2_TPKS_TUNIFORM_10,
+};
 pub use crate::shortint::parameters::multi_bit::gaussian::p_fail_2_minus_64::ks_pbs::*;
 pub use crate::shortint::parameters::multi_bit::gaussian::p_fail_2_minus_64::ks_pbs_gpu::*;
 pub use crate::shortint::parameters::multi_bit::tuniform::p_fail_2_minus_64::ks_pbs_gpu::*;