Struct DigitExtract

pub struct DigitExtract { /* private fields */ }

The digit extraction operation, as required in BFV bootstrapping.

Concretely, this encapsulates an efficient implementation of the per-slot digit extraction function

  Z/p^eZ -> Z/p^rZ x Z/p^eZ,  x -> (x - (x mod p^v) / p^v, x mod p^v)

for v = e - r. Here x mod p^v refers to the smallest positive element of Z/p^eZ that is congruent to x modulo p^v.

This function can also be applied to values in a ring Z/p^e'Z for e' > e, in which case the results are only specified modulo p^e, i.e. may be perturbed by an arbitrary value p^e a.

Implementations

impl DigitExtract

pub fn new_precomputed_p_is_2(p: i64, e: usize, r: usize) -> Self

Creates a DigitExtract for a scalar ring Z/2^eZ.

Uses the precomputed table of best digit extraction circuits for e <= 23.

pub fn new_default<const LOG: bool>(p: i64, e: usize, r: usize) -> Self

Creates a DigitExtract for a scalar ring Z/p^eZ.

Uses the Chen-Han digit retain polynomials [https://ia.cr/2018/067] together with a heuristic method to compile them into an arithmetic circuit, based on the Paterson-Stockmeyer method.

pub fn new_with( p: i64, e: usize, r: usize, extraction_circuits: Vec<(Vec<usize>, ArithCircuit)>, ) -> Self

Creates a new DigitExtract from the given circuits.

This functions expects the list of circuits to contain tuples (digits, C), where the circuit C takes a single input and computes digits.len() outputs, such that the i-th output is congruent to lift(input mod p) modulo p^digits[i].

If you want to use the default choice of circuits, consider using DigitExtract::new_default().

pub fn r(&self) -> usize

pub fn e(&self) -> usize

pub fn v(&self) -> usize

pub fn p(&self) -> i64

pub fn evaluate<R>(&self, ring: R, input: El<R>) -> (El<R>, El<R>)

where R: RingStore + Copy, R::Type: CanHomFrom<StaticRingBase<i64>> + DivisibilityRing,

Computes the function directly on a ring. Mainly designed for testing.

To avoid requiring many rings, this actually computes a slight variant of the digit extraction function on only one ring, namely

  Z/p^eZ -> Z/p^eZ x Z/p^eZ,  x -> (x - (x mod p^v), x mod p^v)

In particular, the first returned value is divisible by p^v.

pub fn evaluate_homomorphic<'a, Params, const LOG: bool>( &self, P_base: &PlaintextRing<Params>, P_bootstrap: &[PlaintextRing<Params>], C: &CiphertextRing<Params>, C_mul: &CiphertextRing<Params>, ct: Ciphertext<Params>, rk: &RelinKey<'a, Params>, debug_sk: Option<&SecretKey<Params>>, ) -> (Ciphertext<Params>, Ciphertext<Params>)

where Params: 'a + BFVParams,