Struct DigitExtract

pub struct DigitExtract<R: ?Sized + RingBase = StaticRingBase<i64>> { /* private fields */ }

The digit extraction operation, as required during BFV and BGV 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, i.e. it will then have the signature

  Z/p^e'Z -> Z/p^(e' - e + r)Z x Z/p^e'Z

In this case, the results are only specified modulo p^r resp. p^e, i.e. may be perturbed by an arbitrary value p^r a resp. p^e a'.

Implementations

impl DigitExtract

pub fn evaluate_bfv<'a, Params: BFVCiphertextParams>( &self, P_base: &PlaintextRing<Params>, P: &[PlaintextRing<Params>], C: &CiphertextRing<Params>, Cmul: &CiphertextRing<Params>, input: Ciphertext<Params>, rk: &RelinKey<'a, Params>, ) -> (Ciphertext<Params>, Ciphertext<Params>)

Evaluates the digit extraction function on a BFV-encrypted input.

For details on how the digit extraction function looks like, see DigitExtract and DigitExtract::evaluate_generic().

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(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.

impl<R: ?Sized + RingBase> DigitExtract<R>

pub fn new_with<S: Copy + RingStore<Type = R>>( p: i64, e: usize, r: usize, ring: S, extraction_circuits: Vec<(Vec<usize>, PlaintextCircuit<R>)>, ) -> 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_generic<T, EvalCircuit, ChangeSpace>( &self, input: T, eval_circuit: EvalCircuit, change_space: ChangeSpace, ) -> (T, T)

where EvalCircuit: FnMut(usize, &[T], &PlaintextCircuit<R>) -> Vec<T>, ChangeSpace: FnMut(usize, usize, T) -> T,

Evaluates the digit extraction function over any representation of elements of Z/p^iZ, which supports the evaluation of PlaintextCircuits. Since digit extraction requires computations in all the rings Z/p^(r - 1)Z, ...., Z/p^eZ, we also require a change_space function, with the following properties:

  change_space(e, e', .): Z/p^eZ -> Z/p^e' Z
  change_space(e, e', x mod p^e) = x p^(e' - e) mod p^e'      if e' > e
  change_space(e, e', x mod p^e) = x / p^(e - e') mod p^e'    if e' < e and p^(e - e') | x

If the passed functions behave as specified, change_space(e, e', x) will never be called for e' < e and an x which is not divisible by p^(e - e').

Furthermore, the eval_circuit is given the exponent of the current ring we work in as the first parameter. The result of DigitExtract::evaluate_generic() is then the tuple (quo, rem) with quo in Z/p^rZ and rem in Z/p^eZ such that x = p^(e - r) * quo + rem and rem < p^(e - r).

If DigitExtract is used on elements of Z/p^e'Z with e' > e (as mentioned at the end of the doc of DigitExtract), the moduli passed to eval_circuit() and change_space() remain nevertheless unchanged - after all, evaluate_generic() does not know that we are in a larger ring. If necessary, you have to manually offset all exponents passed to eval_circuit and change_space by e' - e.

pub fn evaluate<H, S>( &self, input: S::Element, hom: H, ) -> (S::Element, S::Element)

where H: Homomorphism<R, S>, S: ?Sized + RingBase + DivisibilityRing,

Computes (quo, rem) with input = quo * p^(e - r) + rem and rem < p^(e - r). Note that both quo and rem are returned as elements of Z/p^eZ, which means that quo is defined only up to a multiple of p^r.

This function is designed to test digit extraction, since quo and rem will be computed exactly in the same way as in a homomorphic setting. Note also that performing euclidean division can be done much easier with feanor_math::pid::EuclideanRing::euclidean_div_rem() when you have access to the ring elements.

This function does not perform any checks on the underlying ring, in particular, you can call it on an input in Z/p^e'Z with e' > e or an input in Z. Of course, in any case, the output will only be correct modulo p^r resp. p^e.

impl DigitExtract

pub fn evaluate_bgv<'a, Params: BGVCiphertextParams, Strategy: BGVModswitchStrategy<Params>, const LOG: bool>( &self, modswitch_strategy: &Strategy, P_base: &PlaintextRing<Params>, P: &[PlaintextRing<Params>], C_master: &CiphertextRing<Params>, input: ModulusAwareCiphertext<Params, Strategy>, rk: &RelinKey<'a, Params>, key_switches: &mut usize, debug_sk: Option<&SecretKey<Params>>, ) -> (ModulusAwareCiphertext<Params, Strategy>, ModulusAwareCiphertext<Params, Strategy>)