bfvrns.h

// @file bfvrns.h -- Operations for the HPS RNS variant of the BFV cryptoscheme.
// @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 a RNS 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:
 *   - 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)
 *   - 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)
 *   - 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)
 *   - 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_H
#define LBCRYPTO_CRYPTO_BFVRNS_H

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

#include "palisade.h"

namespace lbcrypto {

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

 public:
  LPCryptoParametersBFVrns();

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

  LPCryptoParametersBFVrns(shared_ptr<ParmType> params,
                           EncodingParams encodingParams,
                           float distributionParameter, float assuranceMeasure,
                           float securityLevel, usint relinWindow,
                           MODE mode = RLWE, int depth = 1, int maxDepth = 2);

  LPCryptoParametersBFVrns(shared_ptr<ParmType> params,
                           EncodingParams encodingParams,
                           float distributionParameter, float assuranceMeasure,
                           SecurityLevel securityLevel, usint relinWindow,
                           MODE mode = RLWE, int depth = 1, int maxDepth = 2);

  virtual ~LPCryptoParametersBFVrns() {}

  bool PrecomputeCRTTables();

  const shared_ptr<ILDCRTParams<BigInteger>> GetParamsP() const {
    return m_paramsP;
  }

  const shared_ptr<ILDCRTParams<BigInteger>> GetParamsQP() const {
    return m_paramsQP;
  }

  std::vector<double> const& GetqInv() const { return m_qInv; }

  std::vector<double> const& GetpInv() const { return m_pInv; }

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

  std::vector<DoubleNativeInt> const& GetModpBarrettMu() const {
    return m_modpBarrettMu;
  }

  const std::vector<double>& GettQHatInvModqDivqFrac() const {
    return m_tQHatInvModqDivqFrac;
  }

  const std::vector<double>& GettQHatInvModqBDivqFrac() const {
    return m_tQHatInvModqBDivqFrac;
  }

  const std::vector<NativeInteger>& GettQHatInvModqDivqModt() const {
    return m_tQHatInvModqDivqModt;
  }

  const std::vector<NativeInteger>& GettQHatInvModqDivqModtPrecon() const {
    return m_tQHatInvModqDivqModtPrecon;
  }

  const std::vector<NativeInteger>& GettQHatInvModqBDivqModt() const {
    return m_tQHatInvModqBDivqModt;
  }

  const std::vector<NativeInteger>& GettQHatInvModqBDivqModtPrecon() const {
    return m_tQHatInvModqBDivqModtPrecon;
  }

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

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

  const std::vector<NativeInteger>& GetQHatInvModqPrecon() const {
    return m_QHatInvModqPrecon;
  }

  const std::vector<std::vector<NativeInteger>>& GetQHatModp() const {
    return m_QHatModp;
  }

  const std::vector<std::vector<NativeInteger>>& GetalphaQModp() const {
    return m_alphaQModp;
  }

  const std::vector<double>& GettPSHatInvModsDivsFrac() const {
    return m_tPSHatInvModsDivsFrac;
  }

  const std::vector<std::vector<NativeInteger>>& GettPSHatInvModsDivsModp()
      const {
    return m_tPSHatInvModsDivsModp;
  }

  const std::vector<NativeInteger>& GetPHatInvModp() const {
    return m_PHatInvModp;
  }

  const std::vector<NativeInteger>& GetPHatInvModpPrecon() const {
    return m_PHatInvModpPrecon;
  }

  const std::vector<std::vector<NativeInteger>>& GetPHatModq() const {
    return m_PHatModq;
  }

  const std::vector<std::vector<NativeInteger>>& GetalphaPModq() const {
    return m_alphaPModq;
  }

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

    if (el == nullptr) return false;

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

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

  // 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 "BFVrnsSchemeParameters"; }
  static uint32_t SerializedVersion() { return 1; }

 private:
  // Auxiliary CRT basis {P} = {p_j}
  // used in homomorphic multiplication
  shared_ptr<ILDCRTParams<BigInteger>> m_paramsP;

  // Auxiliary expanded CRT basis Q*P = {s_k}
  // used in homomorphic multiplication
  shared_ptr<ILDCRTParams<BigInteger>> m_paramsQP;

  // Stores \frac{1/q_i}
  std::vector<double> m_qInv;

  // Stores \frac{1/p_j}
  std::vector<double> m_pInv;

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

  // Barrett modulo reduction precomputation for p_j
  std::vector<DoubleNativeInt> m_modpBarrettMu;

  // Stores \frac{t*{Q/q_i}^{-1}/q_i}
  std::vector<double> m_tQHatInvModqDivqFrac;

  // when log2(q_i) >= 45 bits, B = \floor[2^{\ceil{log2(q_i)/2}}
  // Stores \frac{t*{Q/q_i}^{-1}*B/q_i}
  std::vector<double> m_tQHatInvModqBDivqFrac;

  // Stores [\floor{t*{Q/q_i}^{-1}/q_i}]_t
  std::vector<NativeInteger> m_tQHatInvModqDivqModt;
  // Stores NTL precomputations for [\floor{t*{Q/q_i}^{-1}/q_i}]_t
  std::vector<NativeInteger> m_tQHatInvModqDivqModtPrecon;

  // when log2(q_i) >= 45 bits, B = \floor[2^{\ceil{log2(q_i)/2}}
  // Stores [\floor{t*{Q/q_i}^{-1}*B/q_i}]_t
  std::vector<NativeInteger> m_tQHatInvModqBDivqModt;

  // when log2 q_i >= 45 bits, B = \floor[2^{\ceil{log2(q_i)/2}}
  // Stores NTL precomputations for [\floor{t*{Q/q_i}^{-1}*B/q_i}]_t
  std::vector<NativeInteger> m_tQHatInvModqBDivqModtPrecon;

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

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

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

  // Stores [\alpha*Q]_{p_j} for 0 <= alpha <= sizeQ
  std::vector<std::vector<NativeInteger>> m_alphaQModp;

  // S = QP
  // Stores [\floor{t*P*(S/s_k)^{-1}/s_k}]_{p_j}
  std::vector<std::vector<NativeInteger>> m_tPSHatInvModsDivsModp;

  // S = QP
  // Stores \frac{[t*P*(S/s_k)^{-1}]_{s_k}/s_k}
  std::vector<double> m_tPSHatInvModsDivsFrac;

  // Stores [(P/p_j)^{-1}]_{p_j}
  std::vector<NativeInteger> m_PHatInvModp;
  // Stores NTL precomputations for [(P/p_j)^{-1}]_{p_j}
  std::vector<NativeInteger> m_PHatInvModpPrecon;

  // Stores [P/p_j]_{q_i}
  std::vector<std::vector<NativeInteger>> m_PHatModq;

  // Stores [\alpha*P]_{q_i} for 0 <= alpha <= sizeP
  std::vector<std::vector<NativeInteger>> m_alphaPModq;
};

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

 public:
  LPAlgorithmParamsGenBFVrns() {}

  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;
};

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

 public:
  LPAlgorithmBFVrns() {}

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

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

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

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

 public:
  LPAlgorithmSHEBFVrns() {}

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

  Ciphertext<Element> EvalSub(ConstCiphertext<Element> ct1,
                              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 LPAlgorithmPREBFVrns : public LPAlgorithmPREBFV<Element> {
  using IntType = typename Element::Integer;
  using ParmType = typename Element::Params;
  using DggType = typename Element::DggType;
  using DugType = typename Element::DugType;
  using TugType = typename Element::TugType;

 public:
  LPAlgorithmPREBFVrns() {}

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

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

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

 public:
  LPAlgorithmMultipartyBFVrns() {}

  DecryptResult MultipartyDecryptFusion(
      const vector<Ciphertext<Element>>& ciphertextVec,
      NativePoly* plaintext) 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));
  }

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

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

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

 public:
  LPPublicKeyEncryptionSchemeBFVrns();

  bool operator==(
      const LPPublicKeyEncryptionScheme<Element>& sch) const override {
    return dynamic_cast<const LPPublicKeyEncryptionSchemeBFVrns<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