PALISADE Lattice Crypto Library  1.11.9
A lattice crypto library for software engineers by software engineers.
bfv.h
1 // @file bfv.h -- Operations for the BFV cryptoscheme.
2 // @author TPOC: contact@palisade-crypto.org
3 //
4 // @copyright Copyright (c) 2019, New Jersey Institute of Technology (NJIT)
5 // All rights reserved.
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
8 // 1. Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 // 2. Redistributions in binary form must reproduce the above copyright notice,
11 // this list of conditions and the following disclaimer in the documentation
12 // and/or other materials provided with the distribution. THIS SOFTWARE IS
13 // PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
14 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
15 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
16 // EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
17 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
18 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
19 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
20 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
21 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
22 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 
24 /*
25  *
26  * This code implements the Brakerski-Fan-Vercauteren (BFV) homomorphic
27  * encryption scheme. This scheme is also referred to as the FV scheme. The BFV
28  * scheme is introduced here:
29  * - Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully
30  * Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144.
31  * (https://eprint.iacr.org/2012/144.pdf)
32  *
33  * Our implementation builds from the designs here:
34  * - Lepoint T., Naehrig M. (2014) A Comparison of the Homomorphic Encryption
35  * Schemes FV and YASHE. In: Pointcheval D., Vergnaud D. (eds) Progress in
36  * Cryptology – AFRICACRYPT 2014. AFRICACRYPT 2014. Lecture Notes in Computer
37  * Science, vol 8469. Springer, Cham. (https://eprint.iacr.org/2014/062.pdf)
38  *
39  */
40 
41 #ifndef LBCRYPTO_CRYPTO_BFV_H
42 #define LBCRYPTO_CRYPTO_BFV_H
43 
44 #include <map>
45 #include <memory>
46 #include <string>
47 #include <vector>
48 
49 #include "palisade.h"
50 #include "utils/caller_info.h"
51 
52 namespace lbcrypto {
53 
71 template <class Element>
72 class LPCryptoParametersBFV : public LPCryptoParametersRLWE<Element> {
73  using IntType = typename Element::Integer;
74  using ParmType = typename Element::Params;
75 
76  public:
81 
87 
132  LPCryptoParametersBFV(shared_ptr<ParmType> params,
133  const PlaintextModulus &plaintextModulus,
134  float distributionParameter, float assuranceMeasure,
135  float securityLevel, usint relinWindow,
136  const IntType &delta = IntType(0), MODE mode = RLWE,
137  const IntType &bigModulus = IntType(0),
138  const IntType &bigRootOfUnity = IntType(0),
139  const IntType &bigModulusArb = IntType(0),
140  const IntType &bigRootOfUnityArb = IntType(0),
141  int depth = 1, int maxDepth = 2);
142 
166  LPCryptoParametersBFV(shared_ptr<ParmType> params,
167  EncodingParams encodingParams,
168  float distributionParameter, float assuranceMeasure,
169  float securityLevel, usint relinWindow,
170  const IntType &delta = IntType(0), MODE mode = RLWE,
171  const IntType &bigModulus = IntType(0),
172  const IntType &bigRootOfUnity = IntType(0),
173  const IntType &bigModulusArb = IntType(0),
174  const IntType &bigRootOfUnityArb = IntType(0),
175  int depth = 1, int maxDepth = 2);
176 
200  LPCryptoParametersBFV(shared_ptr<ParmType> params,
201  EncodingParams encodingParams,
202  float distributionParameter, float assuranceMeasure,
203  SecurityLevel securityLevel, usint relinWindow,
204  const IntType &delta = IntType(0), MODE mode = RLWE,
205  const IntType &bigModulus = IntType(0),
206  const IntType &bigRootOfUnity = IntType(0),
207  const IntType &bigModulusArb = IntType(0),
208  const IntType &bigRootOfUnityArb = IntType(0),
209  int depth = 1, int maxDepth = 2);
210 
215 
222  const IntType &GetDelta() const { return m_delta; }
223 
229  const IntType &GetBigModulus() const { return m_bigModulus; }
230 
237  const IntType &GetBigRootOfUnity() const { return m_bigRootOfUnity; }
238 
245  const IntType &GetBigModulusArb() const { return m_bigModulusArb; }
246 
253  const IntType &GetBigRootOfUnityArb() const { return m_bigRootOfUnityArb; }
254 
259  void SetDelta(const IntType &delta) { m_delta = delta; }
260 
266  void SetBigModulus(const IntType &bigModulus) { m_bigModulus = bigModulus; }
267 
273  void SetBigRootOfUnity(const IntType &bigRootOfUnity) {
274  m_bigRootOfUnity = bigRootOfUnity;
275  }
276 
281  void SetBigModulusArb(const IntType &bigModulusArb) {
282  m_bigModulusArb = bigModulusArb;
283  }
284 
289  void SetBigRootOfUnityArb(const IntType &bigRootOfUnityArb) {
290  m_bigRootOfUnityArb = bigRootOfUnityArb;
291  }
292 
298  bool operator==(const LPCryptoParameters<Element> &rhs) const {
299  const auto *el = dynamic_cast<const LPCryptoParametersBFV<Element> *>(&rhs);
300 
301  if (el == nullptr) return false;
302 
303  if (m_delta != el->m_delta) return false;
304  if (m_bigModulus != el->m_bigModulus) return false;
305  if (m_bigRootOfUnity != el->m_bigRootOfUnity) return false;
306  if (m_bigModulusArb != el->m_bigModulusArb) return false;
307  if (m_bigRootOfUnityArb != el->m_bigRootOfUnityArb) return false;
308 
310  }
311 
312  void PrintParameters(std::ostream &os) const {
314 
315  os << " delta: " << m_delta << " bigmodulus: " << m_bigModulus
316  << " bigrootofunity: " << m_bigRootOfUnity
317  << " bigmodulusarb: " << m_bigModulusArb
318  << " bigrootofunityarb: " << m_bigRootOfUnityArb;
319  }
320 
321  template <class Archive>
322  void save(Archive &ar, std::uint32_t const version) const {
323  ar(::cereal::base_class<LPCryptoParametersRLWE<Element>>(this));
324  ar(::cereal::make_nvp("d", m_delta));
325  ar(::cereal::make_nvp("bm", m_bigModulus));
326  ar(::cereal::make_nvp("br", m_bigRootOfUnity));
327  ar(::cereal::make_nvp("bma", m_bigModulusArb));
328  ar(::cereal::make_nvp("bra", m_bigRootOfUnityArb));
329  }
330 
331  template <class Archive>
332  void load(Archive &ar, std::uint32_t const version) {
333  if (version > SerializedVersion()) {
334  PALISADE_THROW(deserialize_error,
335  "serialized object version " + std::to_string(version) +
336  " is from a later version of the library");
337  }
338  ar(::cereal::base_class<LPCryptoParametersRLWE<Element>>(this));
339  ar(::cereal::make_nvp("d", m_delta));
340  ar(::cereal::make_nvp("bm", m_bigModulus));
341  ar(::cereal::make_nvp("br", m_bigRootOfUnity));
342  ar(::cereal::make_nvp("bma", m_bigModulusArb));
343  ar(::cereal::make_nvp("bra", m_bigRootOfUnityArb));
344  }
345 
346  std::string SerializedObjectName() const { return "BFVSchemeParameters"; }
347  static uint32_t SerializedVersion() { return 1; }
348 
349  private:
350  // factor delta = floor(q/p) that is multipled by the plaintext polynomial
351  // in BFV (most significant bit ranges are used to represent the message)
352  IntType m_delta;
353 
354  // larger modulus that is used in polynomial multiplications within EvalMult
355  // (before rounding is done)
356  IntType m_bigModulus;
357 
358  // primitive root of unity for m_bigModulus
359  IntType m_bigRootOfUnity;
360 
361  // Large modulus used for CRT with m_bigModulus
362  IntType m_bigModulusArb;
363 
364  // Primitive root of unity for m_bigModulusArb
365  IntType m_bigRootOfUnityArb;
366 };
367 
385 template <class Element>
387  using IntType = typename Element::Integer;
388  using ParmType = typename Element::Params;
389 
390  public:
395 
412  virtual bool ParamsGen(shared_ptr<LPCryptoParameters<Element>> cryptoParams,
413  int32_t evalAddCount = 0, int32_t evalMultCount = 0,
414  int32_t keySwitchCount = 0, size_t dcrtBits = 0,
415  uint32_t n = 0) const;
416 
417  virtual ~LPAlgorithmParamsGenBFV() {}
418 };
419 
438 template <class Element>
439 class LPAlgorithmBFV : public LPEncryptionAlgorithm<Element> {
440  using IntType = typename Element::Integer;
441  using ParmType = typename Element::Params;
442  using DggType = typename Element::DggType;
443  using DugType = typename Element::DugType;
444  using TugType = typename Element::TugType;
445 
446  public:
451 
452  virtual ~LPAlgorithmBFV() {}
453 
461  virtual Ciphertext<Element> Encrypt(const LPPublicKey<Element> publicKey,
462  Element plaintext) const;
463 
471  virtual Ciphertext<Element> Encrypt(const LPPrivateKey<Element> privateKey,
472  Element plaintext) const;
473 
483  virtual DecryptResult Decrypt(const LPPrivateKey<Element> privateKey,
484  ConstCiphertext<Element> ciphertext,
485  NativePoly *plaintext) const;
486 
496  LPKeyPair<Element> KeyGen(CryptoContext<Element> cc, bool makeSparse = false);
497 };
498 
516 template <class Element>
517 class LPAlgorithmSHEBFV : public LPSHEAlgorithm<Element> {
518  using IntType = typename Element::Integer;
519  using ParmType = typename Element::Params;
520  using DggType = typename Element::DggType;
521  using DugType = typename Element::DugType;
522  using TugType = typename Element::TugType;
523 
524  public:
529 
530  virtual ~LPAlgorithmSHEBFV() {}
531 
539  void EvalAddInPlace(Ciphertext<Element>& ct1,
540  ConstCiphertext<Element> ct2) const override;
541 
549  Ciphertext<Element> EvalAdd(ConstCiphertext<Element> ct,
550  ConstPlaintext pt) const override;
551 
559  Ciphertext<Element> EvalSub(ConstCiphertext<Element> ct1,
560  ConstCiphertext<Element> ct2) const override;
561 
569  Ciphertext<Element> EvalSub(ConstCiphertext<Element> ct1,
570  ConstPlaintext pt) const override;
571 
582  Ciphertext<Element> EvalMult(ConstCiphertext<Element> ct1,
583  ConstCiphertext<Element> ct2) const override;
584 
592  Ciphertext<Element> EvalMult(ConstCiphertext<Element> ciphertext,
593  ConstPlaintext plaintext) const override;
594 
607  Ciphertext<Element> EvalMult(ConstCiphertext<Element> ct1,
608  ConstCiphertext<Element> ct,
609  const LPEvalKey<Element> ek) const override;
610 
624  Ciphertext<Element> EvalMultMany(
625  const vector<Ciphertext<Element>> &cipherTextList,
626  const vector<LPEvalKey<Element>> &evalKeys) const override;
627 
640  Ciphertext<Element> EvalMultAndRelinearize(
641  ConstCiphertext<Element> ct1, ConstCiphertext<Element> ct,
642  const vector<LPEvalKey<Element>> &ek) const override;
643 
650  Ciphertext<Element> EvalNegate(ConstCiphertext<Element> ct) const override;
651 
659  LPEvalKey<Element> KeySwitchGen(
660  const LPPrivateKey<Element> originalPrivateKey,
661  const LPPrivateKey<Element> newPrivateKey) const override;
662 
671  void KeySwitchInPlace(const LPEvalKey<Element> keySwitchHint,
672  Ciphertext<Element> &cipherText) const override;
673 
681  LPEvalKey<Element> EvalMultKeyGen(
682  const LPPrivateKey<Element> k1) const override;
683 
694  vector<LPEvalKey<Element>> EvalMultKeysGen(
695  const LPPrivateKey<Element> k1) const override;
696 
706  Ciphertext<Element> EvalAutomorphism(
707  ConstCiphertext<Element> ciphertext, usint i,
708  const std::map<usint, LPEvalKey<Element>> &evalKeys,
709  CALLER_INFO_ARGS_HDR) const override;
710 
719  shared_ptr<std::map<usint, LPEvalKey<Element>>> EvalAutomorphismKeyGen(
720  const LPPrivateKey<Element> privateKey,
721  const std::vector<usint> &indexList) const override;
722 
732  shared_ptr<std::map<usint, LPEvalKey<Element>>> EvalAutomorphismKeyGen(
733  const LPPublicKey<Element> publicKey,
734  const LPPrivateKey<Element> privateKey,
735  const std::vector<usint> &indexList) const override {
736  std::string errMsg =
737  "LPAlgorithmSHEBFV::EvalAutomorphismKeyGen is not implemented for BFV "
738  "SHE Scheme.";
739  PALISADE_THROW(not_implemented_error, errMsg);
740  }
741 };
742 
748 template <class Element>
749 class LPAlgorithmPREBFV : public LPPREAlgorithm<Element> {
750  using IntType = typename Element::Integer;
751  using ParmType = typename Element::Params;
752  using DggType = typename Element::DggType;
753  using TugType = typename Element::TugType;
754 
755  public:
760 
761  /*
762  * DISABLED. Function to generate a re-encryption key as 1..log(q) encryptions
763  * for each bit of the original private key Variant that uses the new secret
764  * key directly.
765  *
766  * @param newKey new private key for the new ciphertext.
767  * @param origPrivateKey original private key used for decryption.
768  * @return evalKey the evaluation key for switching the ciphertext to be
769  * decryptable by new private key.
770  */
771  LPEvalKey<Element> ReKeyGen(const LPPrivateKey<Element> newKey,
772  const LPPrivateKey<Element> origPrivateKey) const;
773 
800  LPEvalKey<Element> ReKeyGen(const LPPublicKey<Element> newKey,
801  const LPPrivateKey<Element> origPrivateKey) const;
802 
829  Ciphertext<Element> ReEncrypt(
830  const LPEvalKey<Element> evalKey, ConstCiphertext<Element> ciphertext,
831  const LPPublicKey<Element> publicKey = nullptr) const;
832 };
833 
859 template <class Element>
861  using IntType = typename Element::Integer;
862  using ParmType = typename Element::Params;
863  using DggType = typename Element::DggType;
864  using DugType = typename Element::DugType;
865  using TugType = typename Element::TugType;
866 
867  public:
872 
873  virtual ~LPAlgorithmMultipartyBFV() {}
874 
889  LPKeyPair<Element> MultipartyKeyGen(CryptoContext<Element> cc,
890  const LPPublicKey<Element> pk1,
891  bool makeSparse = false,
892  bool fresh = false) override;
893 
905  LPKeyPair<Element> MultipartyKeyGen(
906  CryptoContext<Element> cc,
907  const vector<LPPrivateKey<Element>> &secretKeys,
908  bool makeSparse = false) override;
909 
917  Ciphertext<Element> MultipartyDecryptMain(
918  const LPPrivateKey<Element> privateKey,
919  ConstCiphertext<Element> ciphertext) const override;
920 
928  Ciphertext<Element> MultipartyDecryptLead(
929  const LPPrivateKey<Element> privateKey,
930  ConstCiphertext<Element> ciphertext) const override;
931 
940  DecryptResult MultipartyDecryptFusion(
941  const vector<Ciphertext<Element>> &ciphertextVec,
942  NativePoly *plaintext) const override;
943 
954  LPEvalKey<Element> MultiKeySwitchGen(
955  const LPPrivateKey<Element> originalPrivateKey,
956  const LPPrivateKey<Element> newPrivateKey,
957  const LPEvalKey<Element> ek) const override;
958 
969  shared_ptr<std::map<usint, LPEvalKey<Element>>> MultiEvalAutomorphismKeyGen(
970  const LPPrivateKey<Element> privateKey,
971  const shared_ptr<std::map<usint, LPEvalKey<Element>>> eAuto,
972  const std::vector<usint> &indexList) const override;
973 
983  shared_ptr<std::map<usint, LPEvalKey<Element>>> MultiEvalSumKeyGen(
984  const LPPrivateKey<Element> privateKey,
985  const shared_ptr<std::map<usint, LPEvalKey<Element>>> eSum)
986  const override;
987 
995  LPEvalKey<Element> MultiAddEvalKeys(
996  LPEvalKey<Element> evalKey1, LPEvalKey<Element> evalKey2) const override;
997 
1007  LPEvalKey<Element> MultiMultEvalKey(LPEvalKey<Element> evalKey,
1008  LPPrivateKey<Element> sk) const override;
1009 
1010  template <class Archive>
1011  void save(Archive &ar) const {
1012  ar(cereal::base_class<LPMultipartyAlgorithm<Element>>(this));
1013  }
1014 
1015  template <class Archive>
1016  void load(Archive &ar) {
1017  ar(cereal::base_class<LPMultipartyAlgorithm<Element>>(this));
1018  }
1019 
1020  std::string SerializedObjectName() const { return "BFVMultiparty"; }
1021 };
1022 
1027 template <class Element>
1029  : public LPPublicKeyEncryptionScheme<Element> {
1030  using IntType = typename Element::Integer;
1031  using ParmType = typename Element::Params;
1032  using DggType = typename Element::DggType;
1033  using TugType = typename Element::TugType;
1034 
1035  public:
1037 
1038  bool operator==(
1039  const LPPublicKeyEncryptionScheme<Element> &sch) const override {
1040  return dynamic_cast<const LPPublicKeyEncryptionSchemeBFV<Element> *>(
1041  &sch) != nullptr;
1042  }
1043 
1044  void Enable(PKESchemeFeature feature) override;
1045 
1046  template <class Archive>
1047  void save(Archive &ar, std::uint32_t const version) const {
1048  ar(::cereal::base_class<LPPublicKeyEncryptionScheme<Element>>(this));
1049  }
1050 
1051  template <class Archive>
1052  void load(Archive &ar, std::uint32_t const version) {
1053  ar(::cereal::base_class<LPPublicKeyEncryptionScheme<Element>>(this));
1054  }
1055 
1056  std::string SerializedObjectName() const override { return "BFVScheme"; }
1057 };
1058 
1059 } // namespace lbcrypto
1060 
1061 #endif
LPAlgorithmBFV()
Definition: bfv.h:450
Abstract interface for parameter generation algorithm.
Definition: pubkeylp.h:899
void SetBigModulus(const IntType &bigModulus)
Definition: bfv.h:266
PRE scheme based on BFV. This functionality is currently DISABLED in LPPublicKeyEncryptionSchemeBFV b...
Definition: bfv.h:749
Decryption result. This represents whether the decryption of a cipheretext was performed correctly...
Definition: pubkeylp.h:105
shared_ptr< std::map< usint, LPEvalKey< Element > > > EvalAutomorphismKeyGen(const LPPublicKey< Element > publicKey, const LPPrivateKey< Element > privateKey, const std::vector< usint > &indexList) const override
Definition: bfv.h:732
LPAlgorithmSHEBFV()
Definition: bfv.h:528
const IntType & GetDelta() const
Definition: bfv.h:222
Template for crypto parameters.
Definition: rlwe.h:47
void SetDelta(const IntType &delta)
Definition: bfv.h:259
Concrete class for the FHE Multiparty algorithms on BFV. A version of this multiparty scheme built on...
Definition: bfv.h:860
bool operator==(const LPCryptoParameters< Element > &rhs) const
Definition: rlwe.h:284
void SetBigRootOfUnityArb(const IntType &bigRootOfUnityArb)
Definition: bfv.h:289
Abstract interface class for LBC Multiparty algorithms based on threshold FHE. A version of this mult...
Definition: pubkeylp.h:1299
const IntType & GetBigModulus() const
Definition: bfv.h:229
Definition: exception.h:119
bool operator==(const LPCryptoParameters< Element > &rhs) const
Definition: bfv.h:298
Definition: exception.h:147
virtual ~LPCryptoParametersBFV()
Definition: bfv.h:214
Abstract interface for encryption algorithm.
Definition: pubkeylp.h:1016
LPAlgorithmMultipartyBFV()
Definition: bfv.h:871
LPAlgorithmParamsGenBFV()
Definition: bfv.h:394
This is the parameters class for the BFV encryption scheme. This scheme is also referred to as the FV...
Definition: pubkeylp.h:76
Parameter generation for BFV. This scheme is also referred to as the FV scheme.
Definition: bfv.h:386
void SetBigRootOfUnity(const IntType &bigRootOfUnity)
Definition: bfv.h:273
Main public key encryption scheme for BFV implementation,.
Definition: bfv.h:1028
const IntType & GetBigRootOfUnityArb() const
Definition: bfv.h:253
void SetBigModulusArb(const IntType &bigModulusArb)
Definition: bfv.h:281
Encryption algorithm implementation for BFV for the basic public key encrypt, decrypt and key generat...
Definition: bfv.h:439
LPCryptoParametersBFV()
Definition: bfv.cpp:65
const IntType & GetBigRootOfUnity() const
Definition: bfv.h:237
Abstract interface class for LBC PRE algorithms.
Definition: pubkeylp.h:1239
const IntType & GetBigModulusArb() const
Definition: bfv.h:245
main implementation class to capture essential cryptoparameters of any LBC system ...
Definition: pubkeylp.h:73
Definition: pubkeylp.h:879
Abstract interface class for LBC SHE algorithms.
Definition: pubkeylp.h:1679
Definition: binfhecontext.h:36
SHE algorithms implementation for BFV. This scheme is also referred to as the FV scheme.
Definition: bfv.h:517
Abstract interface for public key encryption schemes.
Definition: pubkeylp.h:3181
LPAlgorithmPREBFV()
Definition: bfv.h:759