Class KeySwitchBV

• Defined in File keyswitch-bv.h

Inheritance Relationships

Base Type

• public lbcrypto::KeySwitchRNS (Class KeySwitchRNS)

Class Documentation

class lbcrypto::KeySwitchBV : public lbcrypto::KeySwitchRNS

Inheritence diagram for lbcrypto::KeySwitchBV:

Collaboration diagram for lbcrypto::KeySwitchBV:

RNS variant of the Brakerski-Vaikuntanathan (BV) key switching method.

The method was introduced in Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages; see Appendix B of https://eprint.iacr.org/2021/204 for the RNS description used here.

The element to be switched is decomposed digit by digit and the digits are multiplied by encryptions of the corresponding multiples of the old secret key, so that the noise added by the key switching is proportional to the size of a digit instead of the size of the ciphertext modulus. In RNS the digits are the CRT residues of the element (one digit per RNS limb q_i of the current modulus Ql), and the key holds one (b_i, a_i) pair per limb of Q, where b_i encrypts the i-th CRT component of the old key under the new key. Following https://eprint.iacr.org/2018/117, the factors (Q/q_i)^{-1} mod q_i of the decomposition are folded into the key, so the digits are obtained for free. When the crypto parameters set a digit size, every residue is further decomposed in radix base 2^digitSize, which reduces the noise at the cost of more key components and more NTTs.

Key switching runs entirely in the basis Ql (no auxiliary modulus P), so it does not reduce the usable ciphertext modulus, but it costs a quadratic number of NTTs in the number of limbs, which makes it slower than hybrid key switching for large parameters. The extended-basis operations (KeySwitchExt, KeySwitchDown, EvalFastKeySwitchCoreExt) are not supported.

Public Functions

KeySwitchBV() = default

Default constructor.

virtual ~KeySwitchBV() = default

Virtual destructor.

virtual EvalKey<DCRTPoly> KeySwitchGenInternal(const PrivateKey<DCRTPoly> oldPrivateKey, const PrivateKey<DCRTPoly> newPrivateKey) const override

Generates a BV key switching key from oldPrivateKey to newPrivateKey. The key has one (b_i, a_i) pair per RNS limb of the old key (or per radix digit of every limb when a digit size is set), with a_i uniformly random and b_i = -a_i * sB + noiseScale * e_i + [sA]_{q_i} placed in limb i.

Parameters

• oldPrivateKey – private key the ciphertexts to be switched are encrypted under

• newPrivateKey – private key the switched ciphertexts should decrypt under

Returns

the key switching key

virtual EvalKey<DCRTPoly> KeySwitchGenInternal(const PrivateKey<DCRTPoly> oldPrivateKey, const PrivateKey<DCRTPoly> newPrivateKey, const EvalKey<DCRTPoly> evalKey) const override

Generates a BV key switching key from oldPrivateKey to newPrivateKey reusing the “a” components of evalKey (threshold FHE); see KeySwitchBase::KeySwitchGenInternal.

Parameters

• oldPrivateKey – private key the ciphertexts to be switched are encrypted under

• newPrivateKey – private key the switched ciphertexts should decrypt under

• evalKey – key switching key whose “a” components are reused; if null, fresh components are sampled

Returns

the key switching key

virtual EvalKey<DCRTPoly> KeySwitchGenInternal(const PrivateKey<DCRTPoly> oldPrivateKey, const PublicKey<DCRTPoly> newPublicKey) const override

Generates a BV key switching key from oldPrivateKey to the secret key of newPublicKey by encrypting every CRT component of the old key with the public key (proxy re-encryption).

Parameters

• oldPrivateKey – private key the ciphertexts to be switched are encrypted under

• newPublicKey – public key of the party the switched ciphertexts should decrypt for

Returns

the key switching key

virtual void KeySwitchInPlace(Ciphertext<DCRTPoly> &ciphertext, const EvalKey<DCRTPoly> evalKey) const override

Key switches a ciphertext in place; see KeySwitchBase::KeySwitchInPlace.

Parameters

• ciphertext – ciphertext to be key switched; holds the result

• evalKey – key switching key

virtual std::vector<DCRTPoly> KeySwitchCore(const DCRTPoly &a, const EvalKey<DCRTPoly> evalKey) const override

Key switches a single ring element: digit decomposition followed by EvalFastKeySwitchCore.

Parameters

• a – ring element to be key switched, in basis Ql

• evalKey – key switching key

Returns

the pair (b’, a’) in basis Ql such that b’ + a’ * sB = a * sA + noise

virtual std::shared_ptr<std::vector<DCRTPoly>> EvalKeySwitchPrecomputeCore(const DCRTPoly &c, std::shared_ptr<CryptoParametersBase<DCRTPoly>> cryptoParamsBase) const override

Computes the BV digits of a ring element: its CRT decomposition (one digit per RNS limb, each extended to the whole basis Ql), further split in radix base 2^digitSize when the crypto parameters set a digit size.

Parameters

• c – ring element to be decomposed, in basis Ql

• cryptoParamsBase – crypto parameters (used for the digit size)

Returns

the digits of c

std::vector<DCRTPoly> EvalFastKeySwitchCore(const std::shared_ptr<std::vector<DCRTPoly>> digits, const EvalKey<DCRTPoly> evalKey, const std::shared_ptr<ParmType> paramsQl) const override

Computes the inner products of the digits with the two component vectors of the key switching key, limb by limb in the basis Ql. Only the key components that correspond to the limbs of Ql are used.

Parameters

• digits – digits of the element computed by EvalKeySwitchPrecomputeCore

• evalKey – key switching key

• paramsQl – parameters of the basis Ql of the element (its current level)

Returns

the pair (b’, a’) in basis Ql such that b’ + a’ * sB = a * sA + noise

template<class Archive>
inline void save(Archive &ar) const

Serializes the object (no state of its own beyond the base class).

Parameters

ar – archive to write to

template<class Archive>
inline void load(Archive &ar)

Deserializes the object.

Parameters

ar – archive to read from

inline virtual std::string SerializedObjectName() const override

Name used to identify the class in serialized objects.

Returns

the name of the class