Template Class DCRTPolyImpl

Defined in File dcrtpoly.h

Page Contents

Inheritance Relationships
- Base Type
Template Parameter Order
Class Documentation

Inheritance Relationships

Base Type

public lbcrypto::DCRTPolyInterface< DCRTPolyImpl< VecType >, VecType, NativeVector, PolyImpl > (Template Class DCRTPolyInterface)

Template Parameter Order

typename VecType

Class Documentation

template<typename VecType> class lbcrypto::DCRTPolyImpl : public lbcrypto::DCRTPolyInterface<DCRTPolyImpl<VecType>, VecType, NativeVector, PolyImpl>

Inheritence diagram for lbcrypto::DCRTPolyImpl:

digraph {
graph [bgcolor="#00000000"]
node [shape=rectangle style=filled fillcolor="#FFFFFF" font=Helvetica padding=2]
edge [color="#1414CE"]
"1" [label="lbcrypto::DCRTPolyImpl< VecType >" tooltip="lbcrypto::DCRTPolyImpl< VecType >" fillcolor="#BFBFBF"]
"2" [label="lbcrypto::DCRTPolyInterface< DCRTPolyImpl< VecType >, VecType, NativeVector, PolyImpl >" tooltip="lbcrypto::DCRTPolyInterface< DCRTPolyImpl< VecType >, VecType, NativeVector, PolyImpl >"]
"4" [label="lbcrypto::Serializable" tooltip="lbcrypto::Serializable"]
"3" [label="lbcrypto::ILElement< DCRTPolyImpl< VecType >, VecType >" tooltip="lbcrypto::ILElement< DCRTPolyImpl< VecType >, VecType >"]
"1" -> "2" [dir=forward tooltip="public-inheritance"]
"2" -> "3" [dir=forward tooltip="public-inheritance"]
"3" -> "4" [dir=forward tooltip="public-inheritance"]
}

Collaboration diagram for lbcrypto::DCRTPolyImpl:

Default double-CRT polynomial: an element of the cyclotomic ring modulo a composite modulus Q = q_1 * … * q_l stored as one native polynomial (tower) per CRT modulus q_i, all towers in the same format.

Template Parameters: VecType – the big-integer vector type of the interpolated single-modulus polynomial, e.g. BigVector.

Public Types

using Vector = VecType 

using Integer = typename VecType::Integer

using Params = ILDCRTParams<Integer>

using PolyType = PolyImpl<NativeVector>

using PolyLargeType = PolyImpl<VecType>

using DCRTPolyType = DCRTPolyImpl<VecType>

using DCRTPolyInterfaceType = DCRTPolyInterface<DCRTPolyImpl<VecType>, VecType, NativeVector, PolyImpl>

using Precomputations = typename DCRTPolyInterfaceType::CRTBasisExtensionPrecomputations

using DggType = typename DCRTPolyInterfaceType::DggType

using DugType = typename DCRTPolyInterfaceType::DugType

using TugType = typename DCRTPolyInterfaceType::TugType

using BugType = typename DCRTPolyInterfaceType::BugType

Public Functions

DCRTPolyImpl() = default

inline DCRTPolyImpl(const DCRTPolyType &e) noexcept

inline virtual DCRTPolyType &operator=(const DCRTPolyType &rhs) noexcept override

Assignment Operator.

Parameters: rhs – the copied element.
Returns: the resulting element.

DCRTPolyImpl(const PolyLargeType &e, const std::shared_ptr<Params> &params) noexcept

Constructs the double-CRT representation of a big-integer polynomial: every coefficient of e is reduced modulo each tower modulus of params; the format of e is kept.

Parameters

e – the polynomial with coefficients modulo the composite modulus.
params – the double-CRT parameters defining the towers.

DCRTPolyType &operator=(const PolyLargeType &rhs) noexcept

Assigns a big-integer polynomial: the towers are rebuilt from this element’s parameters and every coefficient of rhs is reduced modulo each tower modulus; this element’s format is kept. Reduction preserves the polynomial only for coefficients, so rhs and this element must both be in COEFFICIENT format.

Parameters: rhs – the polynomial with coefficients modulo the composite modulus.
Returns: the resulting element.

DCRTPolyImpl(const PolyType &e, const std::shared_ptr<Params> &params) noexcept

Constructs an element whose first tower is the native polynomial e and whose other towers are copies of e switched (centered) to the remaining tower moduli of params; if e is empty, all towers are empty. The switch preserves the polynomial only for coefficients, so e must be in COEFFICIENT format.

Parameters

e – the native polynomial, with the modulus of the first tower.
params – the double-CRT parameters defining the towers.

DCRTPolyType &operator=(const PolyType &rhs) noexcept

Assigns a native polynomial: rhs becomes the first tower and copies of it switched (centered) to each remaining tower modulus become the other towers; if rhs is empty, all towers are empty. The element takes the format of rhs, which must be COEFFICIENT because the switch preserves the polynomial only for coefficients.

Parameters: rhs – the native polynomial, with the modulus of the first tower.
Returns: the resulting element.

inline DCRTPolyImpl(DCRTPolyType &&e) noexcept

inline virtual DCRTPolyType &operator=(DCRTPolyType &&rhs) noexcept override

Move Assignment Operator.

Parameters: rhs – the copied element.
Returns: the resulting element.

explicit DCRTPolyImpl(const std::vector<PolyType> &elements)

Constructs an element from its towers; the parameters (cyclotomic order and the tower moduli) and the format are taken from the towers, which must all have the same cyclotomic order.

Parameters: elements – the towers, one native polynomial per CRT modulus.

inline DCRTPolyImpl(const std::shared_ptr<Params> &params, Format format = Format::EVALUATION, bool initializeElementToZero = false) noexcept

Constructs an element with one tower per modulus of params, in the given format.

Parameters

params – the double-CRT parameters defining the towers.
format – the format of the element (COEFFICIENT or EVALUATION).
initializeElementToZero – if true, the towers are allocated and set to zero; otherwise their values are left unallocated.

DCRTPolyImpl(const DggType &dgg, const std::shared_ptr<Params> &p, Format f = Format::EVALUATION)

Constructs an element with coefficients sampled from a discrete Gaussian distribution: one integer vector is sampled and reduced modulo each tower modulus, then the towers are converted to the requested format.

Parameters

dgg – the discrete Gaussian generator.
p – the double-CRT parameters defining the towers.
f – the format of the resulting element.

DCRTPolyImpl(const BugType &bug, const std::shared_ptr<Params> &p, Format f = Format::EVALUATION)

Constructs an element with binary uniform coefficients: one polynomial is sampled with the first tower’s parameters and switched to the modulus of every other tower, then the towers are converted to the requested format.

Parameters

bug – the binary uniform generator.
p – the double-CRT parameters defining the towers.
f – the format of the resulting element.

DCRTPolyImpl(const TugType &tug, const std::shared_ptr<Params> &p, Format f = Format::EVALUATION, uint32_t h = 0)

Constructs an element with ternary uniform coefficients: one integer vector with entries in {-1, 0, 1} is sampled and reduced modulo each tower modulus, then the towers are converted to the requested format.

Parameters

tug – the ternary uniform generator.
p – the double-CRT parameters defining the towers.
f – the format of the resulting element.
h – the Hamming weight (number of nonzero coefficients) for the sparse distribution; 0 samples every coefficient uniformly.

DCRTPolyImpl(DugType &dug, const std::shared_ptr<Params> &p, Format f = Format::EVALUATION)

Constructs an element with uniformly random coefficients: each tower is sampled independently and uniformly modulo its own modulus and is recorded as already being in the requested format (no transform).

Parameters

dug – the discrete uniform generator.
p – the double-CRT parameters defining the towers.
f – the format recorded for the resulting element.

virtual DCRTPolyType &operator=(std::initializer_list<uint64_t> rhs) noexcept override

Initalizer list.

Parameters: rhs – the list to initalized the element.
Returns: the resulting element.

DCRTPolyType &operator=(uint64_t val) noexcept

Assigns the constant val to every entry of every tower; the element and each tower become EVALUATION, as in PolyImpl::operator=(uint64_t).

Parameters: val – the value to assign.
Returns: the resulting element.

DCRTPolyType &operator=(const std::vector<int64_t> &rhs) noexcept

Assigns signed coefficients (used for trapdoor sampling): every tower receives the coefficients reduced modulo its own modulus, missing trailing coefficients are zero and the format becomes COEFFICIENT.

Parameters: rhs – the signed coefficients.
Returns: the resulting element.

DCRTPolyType &operator=(const std::vector<int32_t> &rhs) noexcept

Assigns signed coefficients (used for trapdoor sampling): every tower receives the coefficients reduced modulo its own modulus, missing trailing coefficients are zero and the format becomes COEFFICIENT.

Parameters: rhs – the signed coefficients.
Returns: the resulting element.

DCRTPolyType &operator=(std::initializer_list<std::string> rhs) noexcept

Assigns coefficients given as decimal strings to every tower, as given (without modular reduction); missing trailing coefficients are zero. Towers with unallocated values are allocated first.

Parameters: rhs – the coefficients as decimal strings.
Returns: the resulting element.

virtual DCRTPolyType CloneWithNoise(const DiscreteGaussianGeneratorImpl<VecType> &dgg, Format format) const override

Clone with noise. This method creates a new DCRTPoly and clones the params. The tower values will be filled up with noise based on the discrete gaussian.

Parameters

dgg – the input discrete Gaussian generator. The dgg will be the seed to populate the towers of the DCRTPoly with random numbers.
format – the format of the resulting element; the noise is sampled as coefficients and then converted to this format.

Returns

the new element.

DCRTPolyType CloneTowers(uint32_t startTower, uint32_t endTower) const

Makes a copy holding only the towers startTower to endTower (inclusive), with parameters restricted to those moduli and the same format.

Parameters

startTower – the index of the first tower to copy.
endTower – the index of the last tower to copy.

Returns

the new element.

virtual bool operator==(const DCRTPolyType &rhs) const override

Equality operator.

Parameters: rhs – is the specified element to be compared with this element.
Returns: true if this element represents the same values as the specified element, false otherwise.

virtual DCRTPolyType &operator+=(const DCRTPolyType &rhs) override

Performs an entry-wise addition over all elements of each tower with the towers of the element on the right hand side.

Parameters: rhs – is the element to add with.
Returns: is the result of the addition.

virtual DCRTPolyType &operator+=(const Integer &rhs) override

Performs += operation with a BigInteger and returns the result.

Parameters: element – is the element to add
Returns: is the result of the addition.

DCRTPolyType &operator+=(const NativeInteger &rhs) override

Adds a native integer to every tower in place: to the first coefficient of each tower in COEFFICIENT format, or to all entries of each tower in EVALUATION format.

Parameters: rhs – the native integer to add.
Returns: the resulting element.

virtual DCRTPolyType &operator-=(const DCRTPolyType &rhs) override

Performs an entry-wise subtraction over all elements of each tower with the towers of the element on the right hand side.

Parameters: rhs – is the element to subtract.
Returns: is the result of the subtraction.

virtual DCRTPolyType &operator-=(const Integer &rhs) override

Performs -= operation with a BigInteger and returns the result.

Parameters: element – is the element to subtract
Returns: is the result of the subtraction.

DCRTPolyType &operator-=(const NativeInteger &rhs) override

Subtracts a native integer from all entries of every tower in place.

Parameters: rhs – the native integer to subtract.
Returns: the resulting element.

inline virtual DCRTPolyType &operator*=(const DCRTPolyType &rhs) override

Performs a multiplication operation and returns the result.

Parameters: rhs – is the element to multiply with.
Returns: is the result of the multiplication.

virtual DCRTPolyType &operator*=(const Integer &rhs) override

Performs *= operation with a BigInteger and returns the result.

Parameters: element – is the element to multiply by
Returns: is the result of the multiplication.

DCRTPolyType &operator*=(const NativeInteger &rhs) override

Multiplies all entries of every tower by a native integer in place.

Parameters: rhs – the native integer to multiply by.
Returns: the resulting element.

virtual DCRTPolyType Negate() const override

Performs a negation operation and returns the result.

Returns: is the result of the negation.

virtual DCRTPolyType operator-() const override

Unary minus on a element.

Returns: additive inverse of the an element.

virtual std::vector<DCRTPolyType> BaseDecompose(uint32_t baseBits, bool evalModeAnswer) const override

Write the element as $\sum\limits{i=0}^{\lfloor {\log q/base} \rfloor} {(base^i u_i)}$ and return the vector of $\left\{u_0, u_1,...,u_{\lfloor {\log q/base} \rfloor} \right\} \in R_{{base}^{\lceil {\log q/base} \rceil}}$ ; This is used as a subroutine in the relinearization procedure.

Warning

not efficient and not fast, uses multiprecision arithmetic and will be removed in future. Use

Parameters: baseBits – is the number of bits in the base, i.e., $base = 2^{baseBits}$ .
Returns: is the pointer where the base decomposition vector is stored

std::vector<DCRTPolyType> CRTDecompose(uint32_t baseBits) const

Decomposes the element for key switching: element i of the result holds the residue of this element modulo q_i, as an integer in [0, q_i), represented in every tower; when baseBits > 0 each residue is further split into digits of baseBits bits, one element per digit. The result is in EVALUATION format.

Parameters: baseBits – the number of bits of the digit base for the additional decomposition; 0 for none.
Returns: the vector of decomposed elements.

virtual DCRTPolyType AutomorphismTransform(uint32_t i) const override

Permutes coefficients in a polynomial. Moves the ith index to the first one, it only supports odd indices.

Parameters: i – is the automorphism index (an odd integer) to apply.
Returns: is the result of the automorphism transform.

virtual DCRTPolyType AutomorphismTransform(uint32_t i, const std::vector<uint32_t> &vec) const override

Performs an automorphism transform operation using precomputed bit reversal indices.

Parameters

i – is the automorphism index (an odd integer) to apply.
vec – a vector with precomputed indices

Returns

is the result of the automorphism transform.

virtual DCRTPolyType Plus(const Integer &rhs) const override

Scalar addition - add an integer to the first index only in COEFFICIENT format, or to all entries in EVALUATION format.

Parameters: element – is the integer to add.
Returns: is the return of the addition operation.

DCRTPolyType Plus(const std::vector<Integer> &rhs) const

Adds an integer given in CRT form (one value per tower, converted to a native integer) to each tower: to the first coefficient in COEFFICIENT format, or to all entries in EVALUATION format.

Parameters: rhs – the CRT representation of the integer to add, in tower order.
Returns: the result of the addition.

inline virtual DCRTPolyType Plus(const DCRTPolyType &rhs) const override

Performs an addition operation and returns the result.

Parameters: rhs – is the element to add with.
Returns: is the result of the addition.

virtual DCRTPolyType Minus(const DCRTPolyType &rhs) const override

Performs a subtraction operation and returns the result.

Parameters: rhs – is the element to subtract.
Returns: is the result of the subtraction.

virtual DCRTPolyType Minus(const Integer &rhs) const override

Scalar subtraction - subtract an element from all entries.

Parameters: element – is the element to subtract entry-wise.
Returns: is the return value of the minus operation.

DCRTPolyType Minus(const std::vector<Integer> &rhs) const

Subtracts an integer given in CRT form (one value per tower, converted to a native integer) from all entries of each tower.

Parameters: rhs – the CRT representation of the integer to subtract, in tower order.
Returns: the result of the subtraction.

inline virtual DCRTPolyType Times(const DCRTPolyType &rhs) const override

Performs a multiplication operation and returns the result.

Parameters: rhs – is the element to multiply with.
Returns: is the result of the multiplication.

virtual DCRTPolyType Times(const Integer &rhs) const override

Scalar multiplication - multiply all entries.

Parameters: element – is the element to multiply entry-wise.
Returns: is the return value of the times operation.

DCRTPolyType Times(const std::vector<Integer> &rhs) const

Multiplies all entries of each tower by an integer given in CRT form (one value per tower, converted to a native integer).

Parameters: rhs – the CRT representation of the integer to multiply by, in tower order.
Returns: the result of the multiplication.

virtual DCRTPolyType Times(NativeInteger::SignedNativeInt rhs) const override

Scalar multiplication - multiply by a signed integer.

Parameters: rhs – is the element to multiply entry-wise.
Returns: is the return value of the times operation.

inline DCRTPolyType Times(int64_t rhs) const

Scalar multiplication by a 64-bit signed integer, forwarded to Times(NativeInteger::SignedNativeInt); provided for builds with 128-bit native integers.

Parameters: rhs – the signed integer to multiply by.
Returns: the result of the multiplication.

DCRTPolyType Times(const std::vector<NativeInteger> &rhs) const

Multiplies tower i by rhs[i]; throws if the number of towers differs from the size of rhs.

Parameters: rhs – the CRT representation of the integer to multiply by, in tower order.
Returns: the result of the multiplication.

DCRTPolyType TimesNoCheck(const std::vector<NativeInteger> &rhs) const

Multiplies tower i by rhs[i] for the first min(number of towers, rhs.size()) towers without a size check; any remaining towers of the result are left unallocated.

Parameters: rhs – the CRT representation of the integer to multiply by, in tower order.
Returns: the result of the multiplication.

inline DCRTPolyType &MultAccEqNoCheck(const DCRTPolyType &a, const DCRTPolyType &b)

Fused multiply-accumulate: *this += a * b (mod each tower modulus), without parameter validation. All three operands must hold reduced values (see the NativeVectorT overload). Saves the full-element temporary of *this += a * b.

Parameters

a – the element to multiply.
b – the element to multiply a by.

Returns

the resulting element.

virtual DCRTPolyType MultiplicativeInverse() const override

Performs a multiplicative inverse operation and returns the result.

Returns: is the result of the multiplicative inverse.

virtual bool InverseExists() const override

Determines if inverse exists.

Returns: is the Boolean representation of the existence of multiplicative inverse.

virtual bool IsEmpty() const override

Returns true if ALL the tower(s) are empty.

Returns: true if all towers are empty

virtual void SetValuesToZero() override: Sets all values of element to zero.

virtual void AddILElementOne() override: Adds “1” to every entry in every tower.

virtual void DropLastElement() override: Drops the last element in the double-CRT representation. The resulting DCRTPoly element will have one less tower.

virtual void DropLastElements(size_t i) override

Drops the last i elements in the double-CRT representation.

Parameters: i – the number of towers to drop.

virtual void DropLastElementAndScale(const std::vector<NativeInteger> &qlInvModq) override

Drops the last element in the double-CRT representation and scales down by the last CRT modulus, computing round(x/q_l) as (x - [x]_{q_l}) * [q_l^{-1}]_{q_i}. The resulting DCRTPoly element will have one less tower and is always in EVALUATION format.

Parameters: qlInvModq – precomputed values for [q_l^{-1}]_{q_i}

virtual void ModReduce(const NativeInteger &t, const std::vector<NativeInteger> &tModqPrecon, const NativeInteger &negtInvModq, const NativeInteger &negtInvModqPrecon, const std::vector<NativeInteger> &qlInvModq, const std::vector<NativeInteger> &qlInvModqPrecon) override

Used for BGVrns modulus switching This function performs ModReduce on ciphertext element and private key element. The algorithm computes ct’ <- round( ct/qt ).

Modulus reduction reduces a ciphertext from modulus q to a smaller modulus q/qt where qt is generally the last moduli of the tower. ModReduce is written for DCRTPolyImpl and it drops the last tower while updating the necessary parameters.

The rounding is actually computed as a flooring by computing delta such that delta = -ct mod qt and delta = 0 [t]

The steps taken here are as follows:

compute delta <- -ct/ptm mod qt
compute delta <- ptm*delta in Z. E.g., all of delta’s integer coefficients can be in the range [-ptm*qt/2, ptm*qt/2).
let d’ = c + delta mod q/qt. By construction, d’ is divisible by qt and congruent to 0 mod ptm.
output (d’/q’) in R(q/q’).

Parameters

t – the plaintext modulus.
tModqPrecon – NTL-specific precomputations for [t]_{q_i}; not used by this implementation.
negtInvModq – precomputed value for [-t^{-1}]_{q_l}.
negtInvModqPrecon – NTL-specific precomputation for negtInvModq; not used by this implementation.
qlInvModq – precomputed values for [q_l^{-1}]_{q_i}.
qlInvModqPrecon – NTL-specific precomputations for qlInvModq; not used by this implementation.

virtual PolyLargeType CRTInterpolate() const override

Interpolates the DCRTPoly to a Poly based on the Chinese Remainder Transform Interpolation. and then returns a Poly with that single element.

Returns: the interpolated ring element as a Poly object.

virtual PolyType DecryptionCRTInterpolate(PlaintextModulus ptm) const override

Interpolates the towers to a single polynomial modulo the composite modulus Q, maps each coefficient from the centered range [-Q/2, Q/2) to [0, ptm) and returns the result as a native polynomial with modulus ptm; this produces the plaintext polynomial at decryption.

Parameters: ptm – the plaintext modulus.
Returns: the native polynomial of the reduced coefficients, in this element’s format.

virtual PolyType ToNativePoly() const override

If the values are small enough this is used for efficiency.

Warning

This will be replaced with a non-member utility function.

Returns: NativePoly

virtual PolyLargeType CRTInterpolateIndex(uint32_t i) const override

Interpolates the DCRTPoly to a Poly based on the Chinese Remainder Transform Interpolation, only at element index i, all other elements are zero. and then returns a Poly with that single element.

Parameters: i – the coefficient index to interpolate.
Returns: the interpolated ring element as a Poly object.

virtual Integer GetWorkingModulus() const override

Computes and returns the product of primes in the current moduli chain. Compared to GetModulus, which always returns the product of all primes in the crypto parameters, this method will return a different modulus, based on the towers/moduli that are currently in the chain (some towers are dropped along the way).

Returns: the product of moduli in the current towers.

virtual void SetValuesModSwitch(const DCRTPolyType &element, const NativeInteger &modulus) override

Sets values with a different modulus: the single tower of element is scaled from its modulus to the given modulus (with rounding) and stored in this element.

Parameters

element – the single-tower source element whose values are switched.
modulus – the new modulus.

std::shared_ptr<Params> GetExtendedCRTBasis(const std::shared_ptr<Params> &paramsP) const override

Builds the parameters of the extended basis {Q, P}: the moduli and roots of unity of this element’s current towers followed by those of paramsP, with this element’s cyclotomic order.

Parameters: paramsP – element parameters for the moduli to append to the current towers.
Returns: element parameters of the extended basis.

void TimesQovert(const std::shared_ptr<Params> &paramsQ, const std::vector<NativeInteger> &tInvModq, const NativeInteger &t, const NativeInteger &NegQModt, const NativeInteger &NegQModtPrecon) override

Scales the element by Q/t in place (BFV plaintext encoding); see DCRTPolyInterface::TimesQovert. Every coefficient m of tower i becomes [[m*(-Q)]_t * t^{-1}]_{q_i}.

Parameters

paramsQ – element parameters of the basis Q; not used, the current towers define the basis.
tInvModq – precomputed values for [t^{-1}]_{q_i}; throws if fewer than the number of towers.
t – the plaintext modulus.
NegQModt – precomputed value for [-Q]_t.
NegQModtPrecon – NTL-specific precomputation for NegQModt.

DCRTPolyType ApproxSwitchCRTBasis(const std::shared_ptr<Params> &paramsQ, const std::shared_ptr<Params> &paramsP, const std::vector<NativeInteger> &QHatInvModq, const std::vector<NativeInteger> &QHatInvModqPrecon, const std::vector<std::vector<NativeInteger>> &QHatModp, const std::vector<DoubleNativeInt> &modpBarrettMu) const override

Approximate CRT basis switching {X}_Q -> {X + alpha*Q}_P for a small alpha; see DCRTPolyInterface::ApproxSwitchCRTBasis for the algorithm.

Parameters

paramsQ – parameters for the CRT basis {q_1,…,q_l}.
paramsP – parameters for the CRT basis {p_1,…,p_k}.
QHatInvModq – precomputed values for [(Q/q_i)^{-1}]_{q_i}.
QHatInvModqPrecon – NTL-specific precomputations for QHatInvModq.
QHatModp – precomputed values for [Q/q_i]_{p_j}.
modpBarrettMu – 128-bit Barrett reduction precomputed values for p_j.

Returns

the representation of X + alpha*Q in the basis P.

void ApproxModUp(const std::shared_ptr<Params> &paramsQ, const std::shared_ptr<Params> &paramsP, const std::shared_ptr<Params> &paramsQP, const std::vector<NativeInteger> &QHatInvModq, const std::vector<NativeInteger> &QHatInvModqPrecon, const std::vector<std::vector<NativeInteger>> &QHatModp, const std::vector<DoubleNativeInt> &modpBarrettMu) override

Approximate modulus raising in place, {X}_Q -> {X + alpha*Q}_{Q,P}: the P towers are computed with ApproxSwitchCRTBasis and appended; see DCRTPolyInterface::ApproxModUp.

Parameters

paramsQ – parameters for the CRT basis {q_1,…,q_l}.
paramsP – parameters for the CRT basis {p_1,…,p_k}.
paramsQP – parameters for the CRT basis {q_1,…,q_l,p_1,…,p_k}.
QHatInvModq – precomputed values for [(Q/q_i)^{-1}]_{q_i}.
QHatInvModqPrecon – NTL-specific precomputations for QHatInvModq.
QHatModp – precomputed values for [Q/q_i]_{p_j}.
modpBarrettMu – 128-bit Barrett reduction precomputed values for p_j.

DCRTPolyType ApproxModDown(const std::shared_ptr<Params> &paramsQ, const std::shared_ptr<Params> &paramsP, const std::vector<NativeInteger> &PInvModq, const std::vector<NativeInteger> &PInvModqPrecon, const std::vector<NativeInteger> &PHatInvModp, const std::vector<NativeInteger> &PHatInvModpPrecon, const std::vector<std::vector<NativeInteger>> &PHatModq, const std::vector<DoubleNativeInt> &modqBarrettMu, const std::vector<NativeInteger> &tInvModp, const std::vector<NativeInteger> &tInvModpPrecon, const NativeInteger &t, const std::vector<NativeInteger> &tModqPrecon) const override

Approximate modulus reduction {X}_{Q,P} -> {approximately X/P}_Q (with the multiplication by t used by BGV); see DCRTPolyInterface::ApproxModDown for the algorithm.

Parameters

paramsQ – parameters for the CRT basis {q_1,…,q_l}.
paramsP – parameters for the CRT basis {p_1,…,p_k}.
PInvModq – precomputed values for [P^{-1}]_{q_i}.
PInvModqPrecon – NTL-specific precomputations for PInvModq.
PHatInvModp – precomputed values for [(P/p_j)^{-1}]_{p_j}.
PHatInvModpPrecon – NTL-specific precomputations for PHatInvModp.
PHatModq – precomputed values for [P/p_j]_{q_i}.
modqBarrettMu – 128-bit Barrett reduction precomputed values for q_i.
tInvModp – precomputed values for [t^{-1}]_{p_j} (BGV only).
tInvModpPrecon – NTL-specific precomputations for tInvModp.
t – the plaintext modulus (BGV only).
tModqPrecon – NTL-specific precomputations for t modulo q_i.

Returns

the representation of approximately X/P in the basis Q.

DCRTPolyType SwitchCRTBasis(const std::shared_ptr<Params> &paramsP, const std::vector<NativeInteger> &QHatInvModq, const std::vector<NativeInteger> &QHatInvModqPrecon, const std::vector<std::vector<NativeInteger>> &QHatModp, const std::vector<std::vector<NativeInteger>> &alphaQModp, const std::vector<DoubleNativeInt> &modpBarrettMu, const std::vector<double> &qInv) const override

Exact CRT basis switching {X}_Q -> {X}_P; see DCRTPolyInterface::SwitchCRTBasis for the algorithm.

Parameters

paramsP – parameters for the CRT basis {p_1,…,p_k}.
QHatInvModq – precomputed values for [(Q/q_i)^{-1}]_{q_i}.
QHatInvModqPrecon – NTL-specific precomputations for QHatInvModq.
QHatModp – precomputed values for [Q/q_i]_{p_j}.
alphaQModp – precomputed values for [alpha*Q]_{p_j}.
modpBarrettMu – 128-bit Barrett reduction precomputed values for p_j.
qInv – precomputed values for 1/q_i.

Returns

the representation of X in the basis P.

void ExpandCRTBasis(const std::shared_ptr<Params> &paramsQP, const std::shared_ptr<Params> &paramsP, const std::vector<NativeInteger> &QHatInvModq, const std::vector<NativeInteger> &QHatInvModqPrecon, const std::vector<std::vector<NativeInteger>> &QHatModp, const std::vector<std::vector<NativeInteger>> &alphaQModp, const std::vector<DoubleNativeInt> &modpBarrettMu, const std::vector<double> &qInv, Format resultFormat) override

Exact modulus raising in place, {X}_Q -> {X}_{Q,P}: the P towers are computed with SwitchCRTBasis and appended; see DCRTPolyInterface::ExpandCRTBasis.

Parameters

paramsQP – parameters for the CRT basis {q_1,…,q_l,p_1,…,p_k}.
paramsP – parameters for the CRT basis {p_1,…,p_k}.
QHatInvModq – precomputed values for [(Q/q_i)^{-1}]_{q_i}.
QHatInvModqPrecon – NTL-specific precomputations for QHatInvModq.
QHatModp – precomputed values for [Q/q_i]_{p_j}.
alphaQModp – precomputed values for [alpha*Q]_{p_j}.
modpBarrettMu – 128-bit Barrett reduction precomputed values for p_j.
qInv – precomputed values for 1/q_i.
resultFormat – the format of the resulting element.

void ExpandCRTBasisReverseOrder(const std::shared_ptr<Params> &paramsQP, const std::shared_ptr<Params> &paramsP, const std::vector<NativeInteger> &QHatInvModq, const std::vector<NativeInteger> &QHatInvModqPrecon, const std::vector<std::vector<NativeInteger>> &QHatModp, const std::vector<std::vector<NativeInteger>> &alphaQModp, const std::vector<DoubleNativeInt> &modpBarrettMu, const std::vector<double> &qInv, Format resultFormat) override

Exact modulus raising in place with the new towers first, {X}_Q -> {X}_{P,Q}; see DCRTPolyInterface::ExpandCRTBasisReverseOrder.

Parameters

paramsQP – parameters for the CRT basis {p_1,…,p_k,q_1,…,q_l}.
paramsP – parameters for the CRT basis {p_1,…,p_k}.
QHatInvModq – precomputed values for [(Q/q_i)^{-1}]_{q_i}.
QHatInvModqPrecon – NTL-specific precomputations for QHatInvModq.
QHatModp – precomputed values for [Q/q_i]_{p_j}.
alphaQModp – precomputed values for [alpha*Q]_{p_j}.
modpBarrettMu – 128-bit Barrett reduction precomputed values for p_j.
qInv – precomputed values for 1/q_i.
resultFormat – the format of the resulting element.

void FastExpandCRTBasisPloverQ(const Precomputations &precomputed) override

Scales the element by P_l/Q and expands it to the basis {Q_l, P_l} in place: ApproxSwitchCRTBasis to P_l with the folded constants, then SwitchCRTBasis back to Q_l; see DCRTPolyInterface::FastExpandCRTBasisPloverQ.

Parameters: precomputed – the precomputed constants for the bases Q, Q_l and P_l.

void ExpandCRTBasisQlHat(const std::shared_ptr<Params> &paramsQ, const std::vector<NativeInteger> &QlHatModq, const std::vector<NativeInteger> &QlHatModqPrecon, const uint32_t sizeQ) override

Multiplies the element by Q/Q_l and expands it from the basis Q_l to the full basis Q in place; the towers for the moduli not in Q_l are zero. See DCRTPolyInterface::ExpandCRTBasisQlHat.

Parameters

paramsQ – element parameters of the full basis Q.
QlHatModq – precomputed values for [Q/Q_l]_{q_i} for the towers in Q_l.
QlHatModqPrecon – NTL-specific precomputations for QlHatModq.
sizeQ – the number of towers in the full basis Q.

virtual PolyType ScaleAndRound(const NativeInteger &t, const std::vector<NativeInteger> &tQHatInvModqDivqModt, const std::vector<NativeInteger> &tQHatInvModqDivqModtPrecon, const std::vector<NativeInteger> &tQHatInvModqBDivqModt, const std::vector<NativeInteger> &tQHatInvModqBDivqModtPrecon, const std::vector<double> &tQHatInvModqDivqFrac, const std::vector<double> &tQHatInvModqBDivqFrac) const override

Performs scale and round: {X}_{Q} -> {round(t/Q*X)}_t {Q} = {q_1,…,q_l} {P} = {p_1,…,p_k}.

Brief algorithm: [sum over i of x_i*[t*QHatInv_i/q_i]_t + Round(sum over i of x_i*{t*QHatInv_i/q_i})]_t

Source: Halevi S., Polyakov Y., and Shoup V. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. Cryptology ePrint Archive, Report 2018/117. (https://eprint.iacr.org/2018/117)

Parameters

t – often corresponds to the plaintext modulus
tQHatInvModqDivqModt – precomputed values for [Floor{t*QHatInv_i/q_i}]_t
tQHatInvModqDivqModtPrecon – NTL-specific precomputations
tQHatInvModqBDivqModt – precomputed values for [Floor{t*QHatInv_i*B/q_i}]_t used when CRT moduli are 45..60 bits long
tQHatInvModqBDivqModtPrecon – NTL-specific precomputations used when CRT moduli are 45..60 bits long
tQHatInvModqDivqFrac – precomputed values for Frac{t*QHatInv_i/q_i}
tQHatInvModqBDivqFrac – precomputed values for Frac{t*QHatInv_i*B/q_i} used when CRT moduli are 45..60 bits long

Returns

the result of computation as a polynomial with native 64-bit coefficients

DCRTPolyType ApproxScaleAndRound(const std::shared_ptr<Params> &paramsP, const std::vector<std::vector<NativeInteger>> &tPSHatInvModsDivsModp, const std::vector<DoubleNativeInt> &modpBarretMu) const override

Approximate scale and round {X}_{Q,P} -> {approximately t/Q * X}_P; see DCRTPolyInterface::ApproxScaleAndRound for the algorithm.

Parameters

paramsP – parameters for the CRT basis {p_1,…,p_k}.
tPSHatInvModsDivsModp – precomputed values for [floor(t*P*[(S/s_k)^{-1}]_{s_k}/s_k)]_{p_j}, S = {Q,P}.
modpBarretMu – 128-bit Barrett reduction precomputed values for p_j.

Returns

the representation of approximately t/Q * X in the basis P.

DCRTPolyType ScaleAndRound(const std::shared_ptr<Params> &paramsOutput, const std::vector<std::vector<NativeInteger>> &tOSHatInvModsDivsModo, const std::vector<double> &tOSHatInvModsDivsFrac, const std::vector<DoubleNativeInt> &modoBarretMu) const override

Exact scale and round {X}_{I,O} -> {round(t/I * X)}_O, where O is the output basis (P or Q) and I is the other one; see DCRTPolyInterface::ScaleAndRound for the algorithm.

Parameters

paramsOutput – parameters for the output CRT basis {o_1,…,o_k}.
tOSHatInvModsDivsModo – precomputed values for [floor(t*O*[(S/s_k)^{-1}]_{s_k}/s_k)]_{o_j}, S = {I,O}.
tOSHatInvModsDivsFrac – precomputed fractional parts of t*O*[(S/s_k)^{-1}]_{s_k}/s_k.
modoBarretMu – 128-bit Barrett reduction precomputed values for o_j.

Returns

the representation of round(t/I * X) in the basis O.

virtual PolyType ScaleAndRound(const std::vector<NativeInteger> &moduliQ, const NativeInteger &t, const NativeInteger &tgamma, const std::vector<NativeInteger> &tgammaQHatModq, const std::vector<NativeInteger> &tgammaQHatModqPrecon, const std::vector<NativeInteger> &negInvqModtgamma, const std::vector<NativeInteger> &negInvqModtgammaPrecon) const override

Computes scale and round for fast rounding: {X}_{Q} -> {round(t/Q * X)}_t {Q} = {q_1,…,q_l}.

Brief algorithm:

Source: Jean-Claude Bajard and Julien Eynard and Anwar Hasan and Vincent Zucca. A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes. Cryptology ePrint Archive: Report 2016/510. (https://eprint.iacr.org/2016/510)

Parameters

moduliQ – moduli {q_1,…,q_l}
t – often corresponds to the plaintext modulus
tgamma – t * gamma : t * 2^26 reduction
tgammaQHatModq – [t*gamma*(Q/q_i)]_{q_i}
tgammaQHatModqPrecon – NTL-specific precomputations
negInvqModtgamma – [-q^{-1}]_{t*gamma}
negInvqModtgammaPrecon – NTL-specific precomputations

Returns

the result of computation as a polynomial with native 64-bit coefficients

void ScaleAndRoundPOverQ(const std::shared_ptr<Params> &paramsQ, const std::vector<NativeInteger> &pInvModq) override

Computes round(X/p) in place for an element in the basis {Q, p} (BFV EXTENDED encryption): the last tower, modulo p, is switched (centered) to each q_i and subtracted, the difference is multiplied by [p^{-1}]_{q_i}, the p tower is dropped and the parameters become paramsQ.

Parameters

paramsQ – parameters for the CRT basis {q_1,…,q_l}.
pInvModq – precomputed values for [p^{-1}]_{q_i}.

void FastBaseConvqToBskMontgomery(const std::shared_ptr<Params> &paramsQBsk, const std::vector<NativeInteger> &moduliQ, const std::vector<NativeInteger> &moduliBsk, const std::vector<DoubleNativeInt> &modbskBarrettMu, const std::vector<NativeInteger> &mtildeQHatInvModq, const std::vector<NativeInteger> &mtildeQHatInvModqPrecon, const std::vector<std::vector<NativeInteger>> &QHatModbsk, const std::vector<uint64_t> &QHatModmtilde, const std::vector<NativeInteger> &QModbsk, const std::vector<NativeInteger> &QModbskPrecon, uint64_t negQInvModmtilde, const std::vector<NativeInteger> &mtildeInvModbsk, const std::vector<NativeInteger> &mtildeInvModbskPrecon) override

Expands the element from the basis Q to {Q, Bsk, mtilde} in place using the Montgomery-style fast base conversion of the BEHZ BFV variant; see DCRTPolyInterface::FastBaseConvqToBskMontgomery.

Parameters

paramsQBsk – parameters for the CRT basis {Q, Bsk}.
moduliQ – the moduli {q_1,…,q_l}.
moduliBsk – the moduli {bsk_1,…,bsk_k} of the auxiliary basis.
modbskBarrettMu – 128-bit Barrett reduction precomputed values for bsk_j.
mtildeQHatInvModq – precomputed values for [mtilde*(Q/q_i)^{-1}]_{q_i}.
mtildeQHatInvModqPrecon – NTL-specific precomputations for mtildeQHatInvModq.
QHatModbsk – precomputed values for [Q/q_i]_{bsk_j}.
QHatModmtilde – precomputed values for [Q/q_i]_{mtilde}.
QModbsk – precomputed values for [Q]_{bsk_j}.
QModbskPrecon – NTL-specific precomputations for QModbsk.
negQInvModmtilde – precomputed value for [-Q^{-1}]_{mtilde}.
mtildeInvModbsk – precomputed values for [mtilde^{-1}]_{bsk_j}.
mtildeInvModbskPrecon – NTL-specific precomputations for mtildeInvModbsk.

virtual void FastRNSFloorq(const NativeInteger &t, const std::vector<NativeInteger> &moduliQ, const std::vector<NativeInteger> &moduliBsk, const std::vector<DoubleNativeInt> &modbskBarrettMu, const std::vector<NativeInteger> &tQHatInvModq, const std::vector<NativeInteger> &tQHatInvModqPrecon, const std::vector<std::vector<NativeInteger>> &QHatModbsk, const std::vector<std::vector<NativeInteger>> &qInvModbsk, const std::vector<NativeInteger> &tQInvModbsk, const std::vector<NativeInteger> &tQInvModbskPrecon) override

Computes scale and floor: {X}_{Q,Bsk} -> {floor(t/Q * X)}_{Bsk} {Q} = {q_1,…,q_l} {Bsk} = {bsk_1,…,bsk_k} Outputs the resulting polynomial in CRT/RNS.

Source: Jean-Claude Bajard and Julien Eynard and Anwar Hasan and Vincent Zucca. A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes. Cryptology ePrint Archive: Report 2016/510. (https://eprint.iacr.org/2016/510)

Parameters

t – plaintext modulus
moduliQ – {Q} = {q_1,…,q_l}
moduliBsk – {Bsk} = {bsk_1,…,bsk_k}
modbskBarrettMu – 128-bit Barrett reduction precomputed values for bsk_j
tQHatInvModq – [(Q/q_i)^{-1}]_{q_i}
tQHatInvModqPrecon – NTL-specific precomputations
QHatModbsk – [Q/q_i]_{bsk_i}
qInvModbsk – [(q_i)^{-1}]_{bsk_j}
tQInvModbsk – [t*Q^{-1}]_{bsk_j}
tQInvModbskPrecon – NTL-specific precomputations

void FastBaseConvSK(const std::shared_ptr<Params> &paramsQ, const std::vector<DoubleNativeInt> &modqBarrettMu, const std::vector<NativeInteger> &moduliBsk, const std::vector<DoubleNativeInt> &modbskBarrettMu, const std::vector<NativeInteger> &BHatInvModb, const std::vector<NativeInteger> &BHatInvModbPrecon, const std::vector<NativeInteger> &BHatModmsk, const NativeInteger &BInvModmsk, const NativeInteger &BInvModmskPrecon, const std::vector<std::vector<NativeInteger>> &BHatModq, const std::vector<NativeInteger> &BModq, const std::vector<NativeInteger> &BModqPrecon) override

Converts the element from the basis {Q, Bsk} back to Q in place with the Shenoy-Kumaresan method: the Q towers are recomputed from the Bsk towers, which are then dropped; see DCRTPolyInterface::FastBaseConvSK.

Parameters

paramsQ – parameters for the CRT basis Q.
modqBarrettMu – 128-bit Barrett reduction precomputed values for q_i.
moduliBsk – the moduli {bsk_1,…,bsk_k} of the auxiliary basis.
modbskBarrettMu – 128-bit Barrett reduction precomputed values for bsk_j.
BHatInvModb – precomputed values for [(B/b_j)^{-1}]_{b_j}.
BHatInvModbPrecon – NTL-specific precomputations for BHatInvModb.
BHatModmsk – precomputed values for [B/b_j]_{msk}.
BInvModmsk – precomputed value for [B^{-1}]_{msk}.
BInvModmskPrecon – NTL-specific precomputation for BInvModmsk.
BHatModq – precomputed values for [B/b_j]_{q_i}.
BModq – precomputed values for [B]_{q_i}.
BModqPrecon – NTL-specific precomputations for BModq.

virtual void SwitchFormat(uint32_t thread_limit = 0) override

Convert from Coefficient to CRT or vice versa; calls FFT and inverse FFT.