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:
- 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§
sourcefn discard_bootstrap_lwe_ciphertext(
&mut self,
output: &mut OutputCiphertext,
input: &InputCiphertext,
acc: &Accumulator,
bsk: &BootstrapKey
) -> Result<(), LweCiphertextDiscardingBootstrapError<Self::EngineError>>
fn discard_bootstrap_lwe_ciphertext(
&mut self,
output: &mut OutputCiphertext,
input: &InputCiphertext,
acc: &Accumulator,
bsk: &BootstrapKey
) -> Result<(), LweCiphertextDiscardingBootstrapError<Self::EngineError>>
Bootstrap an LWE ciphertext .
sourceunsafe fn discard_bootstrap_lwe_ciphertext_unchecked(
&mut self,
output: &mut OutputCiphertext,
input: &InputCiphertext,
acc: &Accumulator,
bsk: &BootstrapKey
)
unsafe fn discard_bootstrap_lwe_ciphertext_unchecked(
&mut self,
output: &mut OutputCiphertext,
input: &InputCiphertext,
acc: &Accumulator,
bsk: &BootstrapKey
)
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§
impl LweCiphertextDiscardingBootstrapEngine<FftFourierLweBootstrapKey32, GlweCiphertext32, LweCiphertext32, LweCiphertext32> for FftEngine
Description
Implementation of LweCiphertextDiscardingBootstrapEngine
for FftEngine
that operates
on 32 bit integers.
impl LweCiphertextDiscardingBootstrapEngine<FftFourierLweBootstrapKey32, GlweCiphertextView32<'_>, LweCiphertextView32<'_>, LweCiphertextMutView32<'_>> for FftEngine
Description
Implementation of LweCiphertextDiscardingBootstrapEngine
for FftEngine
that operates
on 32 bit integers.
impl LweCiphertextDiscardingBootstrapEngine<FftFourierLweBootstrapKey64, GlweCiphertext64, LweCiphertext64, LweCiphertext64> for FftEngine
Description
Implementation of LweCiphertextDiscardingBootstrapEngine
for FftEngine
that operates
on 64 bit integers.
impl LweCiphertextDiscardingBootstrapEngine<FftFourierLweBootstrapKey64, GlweCiphertextView64<'_>, LweCiphertextView64<'_>, LweCiphertextMutView64<'_>> for FftEngine
Description
Implementation of LweCiphertextDiscardingBootstrapEngine
for FftEngine
that operates
on 64 bit integers.