bfvrnsB.h

// @file bfvrnsB.h -- Operations for the BEHZ variant of BFV.
// @author TPOC: contact@palisade-crypto.org
//
// @copyright Copyright (c) 2019, New Jersey Institute of Technology (NJIT)
// All rights reserved.
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 1. Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution. THIS SOFTWARE IS
// PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
// EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
// INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

/*
 *
 * This code implements the BEHZ variant of the Brakerski-Fan-Vercauteren (BFV)
 *homomorphic encryption scheme.  This scheme is also referred to as the FV
 *scheme.
 *
 * The BFV scheme is introduced in the following papers:
 *   - Zvika Brakerski (2012). Fully Homomorphic Encryption without Modulus
 *Switching from Classical GapSVP. Cryptology ePrint Archive, Report 2012/078.
 *(https://eprint.iacr.org/2012/078)
 *   - Junfeng Fan and Frederik Vercauteren (2012). Somewhat Practical Fully
 *Homomorphic Encryption.  Cryptology ePrint Archive, Report 2012/144.
 *(https://eprint.iacr.org/2012/144.pdf)
 *
 * Our implementation builds from the designs here:
 *   - Jean-Claude Bajard and Julien Eynard and Anwar Hasan and Vincent
 *Zucca (2016). A Full RNS Variant of FV like Somewhat Homomorphic Encryption
 *Schemes. Cryptology ePrint Archive, Report 2016/510.
 *(https://eprint.iacr.org/2016/510)
 *   - Lepoint T., Naehrig M. (2014) A Comparison of the Homomorphic Encryption
 *Schemes FV and YASHE. In: Pointcheval D., Vergnaud D. (eds) Progress in
 *Cryptology – AFRICACRYPT 2014. AFRICACRYPT 2014. Lecture Notes in Computer
 *Science, vol 8469. Springer, Cham. (https://eprint.iacr.org/2014/062.pdf)
 *   - Ahmad Al Badawi and Yuriy Polyakov and Khin Mi Mi Aung and Bharadwaj
 *Veeravalli and Kurt Rohloff (2018). Implementation and Performance Evaluation
 *of RNS Variants of the BFV Homomorphic Encryption Scheme. Cryptology ePrint
 *Archive, Report 2018/589. {https://eprint.iacr.org/2018/589}
 *
 */

#ifndef LBCRYPTO_CRYPTO_BFVRNS_B_H
#define LBCRYPTO_CRYPTO_BFVRNS_B_H

#include <memory>
#include <string>
#include <vector>

#include "palisade.h"

namespace lbcrypto {

template <class Element>
class LPCryptoParametersBFVrnsB : public LPCryptoParametersRLWE<Element> {
  using ParmType = typename Element::Params;
  using IntType = typename Element::Integer;
  using DugType = typename Element::DugType;
  using DggType = typename Element::DggType;
  using TugType = typename Element::TugType;

 public:
  LPCryptoParametersBFVrnsB();

  LPCryptoParametersBFVrnsB(const LPCryptoParametersBFVrnsB &rhs);
  LPCryptoParametersBFVrnsB(shared_ptr<typename Element::Params> params,
                            const PlaintextModulus &plaintextModulus,
                            float distributionParameter, float assuranceMeasure,
                            float securityLevel, usint relinWindow,
                            MODE mode = RLWE, int depth = 1, int maxDepth = 2);

  LPCryptoParametersBFVrnsB(shared_ptr<typename Element::Params> params,
                            EncodingParams encodingParams,
                            float distributionParameter, float assuranceMeasure,
                            float securityLevel, usint relinWindow,
                            MODE mode = RLWE, int depth = 1, int maxDepth = 2);

  LPCryptoParametersBFVrnsB(shared_ptr<typename Element::Params> params,
                            EncodingParams encodingParams,
                            float distributionParameter, float assuranceMeasure,
                            SecurityLevel securityLevel, usint relinWindow,
                            MODE mode = RLWE, int depth = 1, int maxDepth = 2);

  virtual ~LPCryptoParametersBFVrnsB() {}

  bool PrecomputeCRTTables();

  bool operator==(const LPCryptoParameters<Element> &rhs) const {
    const auto *el =
        dynamic_cast<const LPCryptoParametersBFVrnsB<Element> *>(&rhs);

    if (el == nullptr) return false;

    return LPCryptoParametersRLWE<Element>::operator==(rhs);
  }

  void PrintParameters(std::ostream &os) const {
    LPCryptoParametersRLWE<Element>::PrintParameters(os);
  }

  const shared_ptr<ILDCRTParams<BigInteger>> GetParamsBsk() const {
    return m_paramsBsk;
  }

  std::vector<NativeInteger> const &GetModuliQ() const { return m_moduliQ; }

  std::vector<DoubleNativeInt> const &GetModqBarrettMu() const {
    return m_modqBarrettMu;
  }

  std::vector<NativeInteger> const &GetModuliBsk() const { return m_moduliBsk; }

  std::vector<DoubleNativeInt> const &GetModbskBarrettMu() const {
    return m_modbskBarrettMu;
  }

  const std::vector<NativeInteger> &GetDelta() const { return m_QDivtModq; }

  std::vector<NativeInteger> const &GetmtildeQHatInvModq() const {
    return m_mtildeQHatInvModq;
  }

  std::vector<NativeInteger> const &GetmtildeQHatInvModqPrecon() const {
    return m_mtildeQHatInvModqPrecon;
  }

  std::vector<std::vector<NativeInteger>> const &GetQHatModbsk() const {
    return m_QHatModbsk;
  }

  std::vector<std::vector<NativeInteger>> const &GetqInvModbsk() const {
    return m_qInvModbsk;
  }

  std::vector<uint16_t> const &GetQHatModmtilde() const {
    return m_QHatModmtilde;
  }

  std::vector<NativeInteger> const &GetQModbsk() const { return m_QModbsk; }

  std::vector<NativeInteger> const &GetQModbskPrecon() const {
    return m_QModbskPrecon;
  }

  uint16_t const &GetNegQInvModmtilde() const { return m_negQInvModmtilde; }

  std::vector<NativeInteger> const &GetmtildeInvModbsk() const {
    return m_mtildeInvModbsk;
  }

  std::vector<NativeInteger> const &GetmtildeInvModbskPrecon() const {
    return m_mtildeInvModbskPrecon;
  }

  std::vector<NativeInteger> const &GetQHatInvModq() const {
    return m_QHatInvModq;
  }

  std::vector<NativeInteger> const &GettQHatInvModq() const {
    return m_tQHatInvModq;
  }

  std::vector<NativeInteger> const &GettQHatInvModqPrecon() const {
    return m_tQHatInvModqPrecon;
  }

  std::vector<NativeInteger> const &GettgammaQHatInvModq() const {
    return m_tgammaQHatInvModq;
  }

  std::vector<NativeInteger> const &GettgammaQHatInvModqPrecon() const {
    return m_tgammaQHatInvModqPrecon;
  }

  std::vector<NativeInteger> const &GettQInvModbsk() const {
    return m_tQInvModbsk;
  }

  std::vector<NativeInteger> const &GettQInvModbskPrecon() const {
    return m_tQInvModbskPrecon;
  }

  std::vector<NativeInteger> const &GetBHatInvModb() const {
    return m_BHatInvModb;
  }

  std::vector<NativeInteger> const &GetBHatInvModbPrecon() const {
    return m_BHatInvModbPrecon;
  }

  std::vector<NativeInteger> const &GetBHatModmsk() const {
    return m_BHatModmsk;
  }

  NativeInteger const &GetBInvModmsk() const { return m_BInvModmsk; }

  NativeInteger const &GetBInvModmskPrecon() const {
    return m_BInvModmskPrecon;
  }

  std::vector<std::vector<NativeInteger>> const &GetBHatModq() const {
    return m_BHatModq;
  }

  std::vector<NativeInteger> const &GetBModq() const { return m_BModq; }

  std::vector<NativeInteger> const &GetBModqPrecon() const {
    return m_BModqPrecon;
  }

  uint32_t const &Getgamma() const { return m_gamma; }

  // TODO: use 64 bit words in case NativeInteger uses smaller word size
  NativeInteger const &Gettgamma() const { return m_tgamma; }

  std::vector<NativeInteger> const &GetNegInvqModtgamma() const {
    return m_negInvqModtgamma;
  }

  std::vector<NativeInteger> const &GetNegInvqModtgammaPrecon() const {
    return m_negInvqModtgammaPrecon;
  }

  // NOTE that we do not serialize any of the members declared in this class.
  // they are all cached computations, and get recomputed in any
  // implementation that does a deserialization
  template <class Archive>
  void save(Archive &ar, std::uint32_t const version) const {
    ar(::cereal::base_class<LPCryptoParametersRLWE<Element>>(this));
  }

  template <class Archive>
  void load(Archive &ar, std::uint32_t const version) {
    if (version > SerializedVersion()) {
      PALISADE_THROW(deserialize_error,
                     "serialized object version " + std::to_string(version) +
                         " is from a later version of the library");
    }
    ar(::cereal::base_class<LPCryptoParametersRLWE<Element>>(this));
    if (SERIALIZE_PRECOMPUTE) {
      PrecomputeCRTTables();
    }
  }

  std::string SerializedObjectName() const { return "BFVrnsBSchemeParameters"; }
  static uint32_t SerializedVersion() { return 1; }

 private:
  // Stores a precomputed table of [\floor{Q/t}]_{q_i}
  std::vector<NativeInteger> m_QDivtModq;

  // Auxiliary CRT basis {Bsk} = {B U msk} = {{b_j} U msk}
  shared_ptr<ILDCRTParams<BigInteger>> m_paramsBsk;

  // number of moduli in the base {Q}
  uint32_t m_numq;

  // number of moduli in the auxilliary base {B}
  uint32_t m_numb;

  // mtilde = 2^16
  NativeInteger m_mtilde = NativeInteger((uint64_t)1 << 16);

  // Auxiliary modulus msk
  NativeInteger m_msk;

  // Stores q_i
  std::vector<NativeInteger> m_moduliQ;

  // Barrett modulo reduction precomputation for q_i
  std::vector<DoubleNativeInt> m_modqBarrettMu;

  // Stores auxilliary base moduli b_j
  std::vector<NativeInteger> m_moduliB;

  // Stores the roots of unity modulo bsk_j
  std::vector<NativeInteger> m_rootsBsk;

  // Stores moduli {bsk_i} = {{b_j} U msk}
  std::vector<NativeInteger> m_moduliBsk;

  // Barrett modulo reduction precomputation for bsk_j
  std::vector<DoubleNativeInt> m_modbskBarrettMu;

  // Stores [(Q/q_i)^{-1}]_{q_i}
  std::vector<NativeInteger> m_QHatInvModq;

  // Stores [t*(Q/q_i)^{-1}]_{q_i}
  std::vector<NativeInteger> m_tQHatInvModq;

  // Stores NTL precomputations for [t*(Q/q_i)^{-1}]_{q_i}
  std::vector<NativeInteger> m_tQHatInvModqPrecon;

  // Stores [Q/q_i]_{bsk_j}
  std::vector<std::vector<NativeInteger>> m_QHatModbsk;

  // Stores [(q_i)^{-1}]_{bsk_j}
  std::vector<std::vector<NativeInteger>> m_qInvModbsk;

  // Stores [Q/q_i]_{mtilde}
  std::vector<uint16_t> m_QHatModmtilde;

  // Stores [mtilde*(Q/q_i)^{-1}]_{q_i}
  std::vector<NativeInteger> m_mtildeQHatInvModq;

  // Stores NTL precomputations for [mtilde*(Q/q_i)^{-1}]_{q_i}
  std::vector<NativeInteger> m_mtildeQHatInvModqPrecon;

  // Stores [-Q^{-1}]_{mtilde}
  uint16_t m_negQInvModmtilde;

  // Stores [Q]_{bsk_j}
  std::vector<NativeInteger> m_QModbsk;
  // Stores NTL precomputations for [Q]_{bsk_j}
  std::vector<NativeInteger> m_QModbskPrecon;

  // Stores [mtilde^{-1}]_{bsk_j}
  std::vector<NativeInteger> m_mtildeInvModbsk;
  // Stores NTL precomputations for [mtilde^{-1}]_{bsk_j}
  std::vector<NativeInteger> m_mtildeInvModbskPrecon;

  // Stores [t/Q]_{bsk_j}
  std::vector<NativeInteger> m_tQInvModbsk;
  // Stores NTL precomputations for [t/Q]_{bsk_j}
  std::vector<NativeInteger> m_tQInvModbskPrecon;

  // Stores [(B/b_j)^{-1}]_{b_j}
  std::vector<NativeInteger> m_BHatInvModb;
  // Stores NTL precomputations for [(B/b_j)^{-1}]_{b_j}
  std::vector<NativeInteger> m_BHatInvModbPrecon;

  // Stores [B/b_j]_{q_i}
  std::vector<std::vector<NativeInteger>> m_BHatModq;

  // stores [B/b_j]_{msk}
  std::vector<NativeInteger> m_BHatModmsk;

  // Stores [B^{-1}]_msk
  NativeInteger m_BInvModmsk;
  // Stores NTL precomputations for [B^{-1}]_msk
  NativeInteger m_BInvModmskPrecon;

  // Stores [B]_{q_i}
  std::vector<NativeInteger> m_BModq;
  // Stores NTL precomputations for [B]_{q_i}
  std::vector<NativeInteger> m_BModqPrecon;

  // Stores gamma = 2^26;
  uint32_t m_gamma = 1 << 26;

  // TODO: use 64 bit words in case NativeInteger uses smaller word size
  // Stores t*gamma on a uint64_t word
  NativeInteger m_tgamma;

  // Stores [-(q_i)^{-1}]_{t*gamma}
  std::vector<NativeInteger> m_negInvqModtgamma;
  // Stores NTL precomputations for [-(q_i)^{-1}]_{t*gamma}
  std::vector<NativeInteger> m_negInvqModtgammaPrecon;

  // Stores [t*gamma*(Q/q_i)^(-1)]_{q_i}
  std::vector<NativeInteger> m_tgammaQHatInvModq;
  // Stores NTL precomputations for [t*gamma*(Q/q_i)^(-1)]_{q_i}
  std::vector<NativeInteger> m_tgammaQHatInvModqPrecon;
};

template <class Element>
class LPAlgorithmParamsGenBFVrnsB : public LPAlgorithmParamsGenBFV<Element> {
  using ParmType = typename Element::Params;
  using IntType = typename Element::Integer;
  using DugType = typename Element::DugType;
  using DggType = typename Element::DggType;
  using TugType = typename Element::TugType;

 public:
  LPAlgorithmParamsGenBFVrnsB() {}

  bool ParamsGen(shared_ptr<LPCryptoParameters<Element>> cryptoParams,
                 int32_t evalAddCount = 0, int32_t evalMultCount = 0,
                 int32_t keySwitchCount = 0, size_t dcrBits = 60,
                 uint32_t n = 0) const override;
};

template <class Element>
class LPAlgorithmBFVrnsB : public LPAlgorithmBFV<Element> {
  using ParmType = typename Element::Params;
  using IntType = typename Element::Integer;
  using DugType = typename Element::DugType;
  using DggType = typename Element::DggType;
  using TugType = typename Element::TugType;

 public:
  LPAlgorithmBFVrnsB() {}

  Ciphertext<Element> Encrypt(const LPPublicKey<Element> publicKey,
                              Element plaintext) const override;

  Ciphertext<Element> Encrypt(const LPPrivateKey<Element> privateKey,
                              Element plaintext) const override;

  DecryptResult Decrypt(const LPPrivateKey<Element> privateKey,
                        ConstCiphertext<Element> ciphertext,
                        NativePoly *plaintext) const override;
};

template <class Element>
class LPAlgorithmSHEBFVrnsB : public LPAlgorithmSHEBFV<Element> {
  using ParmType = typename Element::Params;
  using IntType = typename Element::Integer;
  using DugType = typename Element::DugType;
  using DggType = typename Element::DggType;
  using TugType = typename Element::TugType;

 public:
  LPAlgorithmSHEBFVrnsB() {}

  Ciphertext<Element> EvalAdd(ConstCiphertext<Element> ct,
                              ConstPlaintext pt) const override;

  Ciphertext<Element> EvalSub(ConstCiphertext<Element> ct,
                              ConstPlaintext pt) const override;

  Ciphertext<Element> EvalMult(ConstCiphertext<Element> ct1,
                               ConstCiphertext<Element> ct2) const override;

  LPEvalKey<Element> KeySwitchGen(
      const LPPrivateKey<Element> oldKey,
      const LPPrivateKey<Element> newKey) const override;

  void KeySwitchInPlace(const LPEvalKey<Element> keySwitchHint,
                        Ciphertext<Element>& ciphertext) const override;

  Ciphertext<Element> EvalMultAndRelinearize(
      ConstCiphertext<Element> ct1, ConstCiphertext<Element> ct2,
      const vector<LPEvalKey<Element>> &ek) const override;
};

template <class Element>
class LPAlgorithmPREBFVrnsB : public LPAlgorithmPREBFV<Element> {
  using ParmType = typename Element::Params;
  using IntType = typename Element::Integer;
  using DugType = typename Element::DugType;
  using DggType = typename Element::DggType;
  using TugType = typename Element::TugType;

 public:
  LPAlgorithmPREBFVrnsB() {}

  LPEvalKey<Element> ReKeyGen(
      const LPPublicKey<Element> newKey,
      const LPPrivateKey<Element> oldKey) const override;

  Ciphertext<Element> ReEncrypt(
      const LPEvalKey<Element> ek, ConstCiphertext<Element> ciphertext,
      const LPPublicKey<Element> publicKey = nullptr) const override;
};

template <class Element>
class LPAlgorithmMultipartyBFVrnsB : public LPAlgorithmMultipartyBFV<Element> {
  using ParmType = typename Element::Params;
  using IntType = typename Element::Integer;
  using DugType = typename Element::DugType;
  using DggType = typename Element::DggType;
  using TugType = typename Element::TugType;

 public:
  LPAlgorithmMultipartyBFVrnsB() {}

  DecryptResult MultipartyDecryptFusion(
      const vector<Ciphertext<Element>> &ciphertextVec,
      NativePoly *plaintext) const override;

  LPEvalKey<Element> MultiKeySwitchGen(
      const LPPrivateKey<Element> oldKey, const LPPrivateKey<Element> newKey,
      const LPEvalKey<Element> ek) const override;

  template <class Archive>
  void save(Archive &ar) const {
    ar(cereal::base_class<LPAlgorithmMultipartyBFV<Element>>(this));
  }

  template <class Archive>
  void load(Archive &ar) {
    ar(cereal::base_class<LPAlgorithmMultipartyBFV<Element>>(this));
  }

  std::string SerializedObjectName() const { return "BFVrnsBMultiparty"; }
};

template <class Element>
class LPPublicKeyEncryptionSchemeBFVrnsB
    : public LPPublicKeyEncryptionScheme<Element> {
  using ParmType = typename Element::Params;
  using IntType = typename Element::Integer;
  using DugType = typename Element::DugType;
  using DggType = typename Element::DggType;
  using TugType = typename Element::TugType;

 public:
  LPPublicKeyEncryptionSchemeBFVrnsB();

  bool operator==(
      const LPPublicKeyEncryptionScheme<Element> &sch) const override {
    return dynamic_cast<const LPPublicKeyEncryptionSchemeBFVrnsB<Element> *>(
               &sch) != nullptr;
  }

  void Enable(PKESchemeFeature feature) override;

  template <class Archive>
  void save(Archive &ar, std::uint32_t const version) const {
    ar(::cereal::base_class<LPPublicKeyEncryptionScheme<Element>>(this));
  }

  template <class Archive>
  void load(Archive &ar, std::uint32_t const version) {
    ar(::cereal::base_class<LPPublicKeyEncryptionScheme<Element>>(this));
  }

  std::string SerializedObjectName() const override { return "BFVrnsScheme"; }
};

}  // namespace lbcrypto

#endif