Trait concrete_core::specification::engines::LweCiphertextDiscardingBootstrapEngine

source · [−]
pub trait LweCiphertextDiscardingBootstrapEngine<BootstrapKey, Accumulator, InputCiphertext, OutputCiphertext>: AbstractEnginewhere
    BootstrapKey: LweBootstrapKeyEntity,
    Accumulator: GlweCiphertextEntity,
    InputCiphertext: LweCiphertextEntity,
    OutputCiphertext: LweCiphertextEntity,{
    fn discard_bootstrap_lwe_ciphertext(
        &mut self,
        output: &mut OutputCiphertext,
        input: &InputCiphertext,
        acc: &Accumulator,
        bsk: &BootstrapKey
    ) -> Result<(), LweCiphertextDiscardingBootstrapError<Self::EngineError>>;
    unsafe fn discard_bootstrap_lwe_ciphertext_unchecked(
        &mut self,
        output: &mut OutputCiphertext,
        input: &InputCiphertext,
        acc: &Accumulator,
        bsk: &BootstrapKey
    );
}
Expand description

A trait for engines bootstrapping (discarding) LWE ciphertexts.

Semantics

This discarding operation fills the output LWE ciphertext with the bootstrap of the input LWE ciphertext, using the acc accumulator as lookup-table, and the bsk bootstrap key.

Formal Definition

Programmable Bootstrapping

This homomorphic procedure allows to both reduce the noise of a ciphertext and to evaluate a Look-Up Table (LUT) on the encrypted plaintext at the same time, i.e., it transforms an input LWE ciphertext $\mathsf{ct}_{\mathsf{in}} = \left( \vec{a}_{\mathsf{in}} , b_{\mathsf{in}}\right) \in \mathsf{LWE}^{n_{\mathsf{in}}}_{\vec{s}_{\mathsf{in}}}( \mathsf{pt} ) \subseteq \mathbb{Z}_q^{(n_{\mathsf{in}}+1)}$ into an output LWE ciphertext $\mathsf{ct}_{\mathsf{out}} = \left( \vec{a}_{\mathsf{out}} , b_{\mathsf{out}}\right) \in \mathsf{LWE}^{n_{\mathsf{out}}}_{\vec{s}_{\mathsf{out}}}( \mathsf{LUT(pt)} )\subseteq \mathbb{Z}_q^{(n_{\mathsf{out}}+1)}$ where $n_{\mathsf{in}} = |\vec{s}_{\mathsf{in}}|$ and $n_{\mathsf{out}} = |\vec{s}_{\mathsf{out}}|$, such that the noise in this latter is set to a fixed (reduced) amount. It requires a bootstrapping key.

The input ciphertext is encrypted under the LWE secret key $\vec{s}_{\mathsf{in}}$ and the output ciphertext is encrypted under the LWE secret key $\vec{s}_{\mathsf{out}}$.

$$\mathsf{ct}_{\mathsf{in}} \in \mathsf{LWE}^{n_{\mathsf{in}}}_{\vec{s}_{\mathsf{in}}}( \mathsf{pt} ) ~~~~~~~~~~\mathsf{BSK}_{\vec{s}_{\mathsf{in}}\rightarrow \vec{S}_{\mathsf{out}}}$$ $$ \mathsf{PBS}\left(\mathsf{ct}_{\mathsf{in}} , \mathsf{BSK} \right) \rightarrow \mathsf{ct}_{\mathsf{out}} \in \mathsf{LWE}^{n_{\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{LWE}^{n_{\mathsf{in}}}_{\vec{s}_{\mathsf{in}}}( \mathsf{pt} )$: an LWE ciphertext with $\vec{a}_{\mathsf{in}}=\left(a_0, \cdots a_{n_{\mathsf{in}}-1}\right)$
  • $\mathsf{BSK}_{\vec{s}_{\mathsf{in}}\rightarrow \vec{S}_{\mathsf{out}}}$: a bootstrapping key as defined above
  • $\mathsf{LUT} \in \mathcal{R}_q$: a LUT represented as a polynomial _with redundancy_
outputs:
  • $\mathsf{ct}_{\mathsf{out}} \in \mathsf{LWE}^{n_{\mathsf{out}}}_{\vec{s}_{\mathsf{out}}} \left( \mathsf{LUT(pt)} \right)$: an LWE ciphertext
algorithm:
  1. Compute $\tilde{a}_i \in \mathbb{Z}_{2N_{\mathsf{out}}} \leftarrow \lfloor \frac{2 N_{\mathsf{out}} \cdot a_i}{q} \rceil$, for $i= 0, 1, \ldots, n_{\mathsf{in}-1}$ 2. Compute $\tilde{b}_\mathsf{in} \in \mathbb{Z}_{2N_{\mathsf{out}}} \leftarrow \lfloor \frac{2 N_{\mathsf{out}} \cdot b_\mathsf{in}}{q} \rceil$ 3. Set $\mathsf{ACC} = (0, \ldots, 0, \mathsf{LUT} \cdot X^{-\tilde{b}_\mathsf{in}})$ 4. Compute $\mathsf{ACC} = \mathsf{CMux}(\overline{\overline{\mathsf{CT}_i}}, \mathsf{ACC} \cdot X^{\tilde{a}_i}, \mathsf{ACC})$, for $i= 0, 1, \ldots, n_{\mathsf{in}-1}$ 5. Output $\mathsf{ct}_{\mathsf{out}} \leftarrow \mathsf{SampleExtract}(\mathsf{ACC})$

Required Methods

Bootstrap an LWE ciphertext .

Unsafely bootstrap an LWE ciphertext .

Safety

For the general safety concerns regarding this operation, refer to the different variants of LweCiphertextDiscardingBootstrapError. For safety concerns specific to an engine, refer to the implementer safety section.

Implementors