1 // @file bfvrnsB.h -- Operations for the BEHZ variant of BFV. 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 BEHZ variant of the Brakerski-Fan-Vercauteren (BFV) 27 *homomorphic encryption scheme. This scheme is also referred to as the FV 28 *scheme. 29 * 30 * The BFV scheme is introduced in the following papers: 31 * - Zvika Brakerski (2012). Fully Homomorphic Encryption without Modulus 32 *Switching from Classical GapSVP. Cryptology ePrint Archive, Report 2012/078. 33 *(https://eprint.iacr.org/2012/078) 34 * - Junfeng Fan and Frederik Vercauteren (2012). Somewhat Practical Fully 35 *Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. 36 *(https://eprint.iacr.org/2012/144.pdf) 37 * 38 * Our implementation builds from the designs here: 39 * - Jean-Claude Bajard and Julien Eynard and Anwar Hasan and Vincent 40 *Zucca (2016). A Full RNS Variant of FV like Somewhat Homomorphic Encryption 41 *Schemes. Cryptology ePrint Archive, Report 2016/510. 42 *(https://eprint.iacr.org/2016/510) 43 * - Lepoint T., Naehrig M. (2014) A Comparison of the Homomorphic Encryption 44 *Schemes FV and YASHE. In: Pointcheval D., Vergnaud D. (eds) Progress in 45 *Cryptology – AFRICACRYPT 2014. AFRICACRYPT 2014. Lecture Notes in Computer 46 *Science, vol 8469. Springer, Cham. (https://eprint.iacr.org/2014/062.pdf) 47 * - Ahmad Al Badawi and Yuriy Polyakov and Khin Mi Mi Aung and Bharadwaj 48 *Veeravalli and Kurt Rohloff (2018). Implementation and Performance Evaluation 49 *of RNS Variants of the BFV Homomorphic Encryption Scheme. Cryptology ePrint 50 *Archive, Report 2018/589. {https://eprint.iacr.org/2018/589} 51 * 52 */ 53 54 #ifndef LBCRYPTO_CRYPTO_BFVRNS_B_H 55 #define LBCRYPTO_CRYPTO_BFVRNS_B_H 56 57 #include <memory> 58 #include <string> 59 #include <vector> 60 61 #include "palisade.h" 62 63 namespace lbcrypto { 64 65 /** 66 * @brief This is the parameters class for the BFVrnsB encryption scheme. This 67 * scheme is also referred to as the FVrns scheme. 68 * 69 * @tparam Element a ring element type. 70 */ 71 template <class Element> 72 class LPCryptoParametersBFVrnsB : public LPCryptoParametersRLWE<Element> { 73 using ParmType = typename Element::Params; 74 using IntType = typename Element::Integer; 75 using DugType = typename Element::DugType; 76 using DggType = typename Element::DggType; 77 using TugType = typename Element::TugType; 78 79 public: 80 /** 81 * Default constructor. 82 */ 83 LPCryptoParametersBFVrnsB(); 84 85 /** 86 * Copy constructor. 87 * @param rhs - source 88 */ 89 LPCryptoParametersBFVrnsB(const LPCryptoParametersBFVrnsB &rhs); 90 /** 91 * Constructor that initializes values. Note that it is possible to set 92 * parameters in a way that is overall infeasible for actual use. There are 93 * fewer degrees of freedom than parameters provided. Typically one chooses 94 * the basic noise, assurance and security parameters as the typical 95 * community-accepted values, then chooses the plaintext modulus and depth 96 * as needed. The element parameters should then be choosen to provide 97 * correctness and security. In some cases we would need to operate over 98 * already encrypted/provided ciphertext and the depth needs to be 99 * pre-computed for initial settings. 100 * 101 * @param ¶ms Element parameters. This will depend on the specific 102 * class of element being used. 103 * @param &plaintextModulus Plaintext modulus, typically denoted as p in 104 * most publications. 105 * @param distributionParameter Noise distribution parameter, typically 106 * denoted as /sigma in most publications. Community standards typically 107 * call for a value of 3 to 6. Lower values provide more room for 108 * computation while larger values provide more security. 109 * @param assuranceMeasure Assurance level, typically denoted as w in most 110 * applications. This is oftern perceived as a fudge factor in the 111 * literature, with a typical value of 9. 112 * @param securityLevel Security level as Root Hermite Factor. We use the 113 * Root Hermite Factor representation of the security level to better 114 * conform with US ITAR and EAR export regulations. This is typically 115 * represented as /delta in the literature. Typically a Root Hermite Factor 116 * of 1.006 or less provides reasonable security for RLWE crypto schemes. 117 * @param relinWindow The size of the relinearization window. This is 118 * relevant when using this scheme for proxy re-encryption, and the value is 119 * denoted as r in the literature. 120 * @param mode optimization setting (RLWE vs OPTIMIZED) 121 * @param depth is the depth of computation circuit supported for these 122 * parameters (not used now; for future use). 123 * @param maxDepth the maximum power of secret key for which the 124 * relinearization key is generated 125 */ 126 LPCryptoParametersBFVrnsB(shared_ptr<typename Element::Params> params, 127 const PlaintextModulus &plaintextModulus, 128 float distributionParameter, float assuranceMeasure, 129 float securityLevel, usint relinWindow, 130 MODE mode = RLWE, int depth = 1, int maxDepth = 2); 131 132 /** 133 * Constructor that initializes values. 134 * 135 * @param params element parameters. 136 * @param encodingParams plaintext space parameters. 137 * @param distributionParameter noise distribution parameter. 138 * @param assuranceMeasure assurance level. = BigInteger::ZERO 139 * @param securityLevel security level (root Hermite factor). 140 * @param relinWindow the size of the relinearization window. 141 * @param mode optimization setting (RLWE vs OPTIMIZED) 142 * @param depth is the depth of computation circuit supported for these 143 * parameters (not used now; for future use). 144 * @param maxDepth the maximum power of secret key for which the 145 * relinearization key is generated 146 */ 147 LPCryptoParametersBFVrnsB(shared_ptr<typename Element::Params> params, 148 EncodingParams encodingParams, 149 float distributionParameter, float assuranceMeasure, 150 float securityLevel, usint relinWindow, 151 MODE mode = RLWE, int depth = 1, int maxDepth = 2); 152 153 /** 154 * Constructor that initializes values. 155 * 156 * @param params element parameters. 157 * @param encodingParams plaintext space parameters. 158 * @param distributionParameter noise distribution parameter. 159 * @param assuranceMeasure assurance level. = BigInteger::ZERO 160 * @param securityLevel standard security level 161 * @param relinWindow the size of the relinearization window. 162 * @param mode optimization setting (RLWE vs OPTIMIZED) 163 * @param depth is the depth of computation circuit supported for these 164 * parameters (not used now; for future use). 165 * @param maxDepth the maximum power of secret key for which the 166 * relinearization key is generated 167 */ 168 LPCryptoParametersBFVrnsB(shared_ptr<typename Element::Params> params, 169 EncodingParams encodingParams, 170 float distributionParameter, float assuranceMeasure, 171 SecurityLevel securityLevel, usint relinWindow, 172 MODE mode = RLWE, int depth = 1, int maxDepth = 2); 173 174 /** 175 * Destructor 176 */ ~LPCryptoParametersBFVrnsB()177 virtual ~LPCryptoParametersBFVrnsB() {} 178 179 /** 180 * Computes all tables needed for decryption, homomorphic multiplication, 181 * and key switching 182 * @return true on success 183 */ 184 bool PrecomputeCRTTables(); 185 186 /** 187 * == operator to compare to this instance of LPCryptoParametersBFVrnsB 188 * object. 189 * 190 * @param &rhs LPCryptoParameters to check equality against. 191 */ 192 bool operator==(const LPCryptoParameters<Element> &rhs) const { 193 const auto *el = 194 dynamic_cast<const LPCryptoParametersBFVrnsB<Element> *>(&rhs); 195 196 if (el == nullptr) return false; 197 198 return LPCryptoParametersRLWE<Element>::operator==(rhs); 199 } 200 PrintParameters(std::ostream & os)201 void PrintParameters(std::ostream &os) const { 202 LPCryptoParametersRLWE<Element>::PrintParameters(os); 203 } 204 205 /** 206 * Gets the Auxiliary CRT basis {Bsk} = {B U msk} 207 * used in homomorphic multiplication 208 * 209 * @return the precomputed CRT params 210 */ GetParamsBsk()211 const shared_ptr<ILDCRTParams<BigInteger>> GetParamsBsk() const { 212 return m_paramsBsk; 213 } 214 215 /** 216 * Gets the precomputed table of q_i 217 * 218 * @return the precomputed table 219 */ GetModuliQ()220 std::vector<NativeInteger> const &GetModuliQ() const { return m_moduliQ; } 221 222 /** 223 * Gets the Barrett modulo reduction precomputation for q_i 224 * 225 * @return the precomputed table 226 */ GetModqBarrettMu()227 std::vector<DoubleNativeInt> const &GetModqBarrettMu() const { 228 return m_modqBarrettMu; 229 } 230 231 /** 232 * Gets the precomputed table of bsk_j 233 * 234 * @return the precomputed table 235 */ GetModuliBsk()236 std::vector<NativeInteger> const &GetModuliBsk() const { return m_moduliBsk; } 237 238 /** 239 * Gets the Barrett modulo reduction precomputation for bsk_j 240 * 241 * @return the precomputed table 242 */ GetModbskBarrettMu()243 std::vector<DoubleNativeInt> const &GetModbskBarrettMu() const { 244 return m_modbskBarrettMu; 245 } 246 247 /** 248 * Gets the precomputed table of [\floor{Q/t}]_{q_i} 249 * 250 * @return the precomputed table 251 */ GetDelta()252 const std::vector<NativeInteger> &GetDelta() const { return m_QDivtModq; } 253 254 /** 255 * Gets the precomputed table of [mtilde*(Q/q_i)^{-1}]_{q_i} 256 * 257 * @return the precomputed table 258 */ GetmtildeQHatInvModq()259 std::vector<NativeInteger> const &GetmtildeQHatInvModq() const { 260 return m_mtildeQHatInvModq; 261 } 262 263 /** 264 * Gets the NTL precomputations for [mtilde*(Q/q_i)^{-1}]_{q_i} 265 * 266 * @return the precomputed table 267 */ GetmtildeQHatInvModqPrecon()268 std::vector<NativeInteger> const &GetmtildeQHatInvModqPrecon() const { 269 return m_mtildeQHatInvModqPrecon; 270 } 271 272 /** 273 * Gets the precomputed table of [Q/q_i]_{bsk_j} 274 * 275 * @return the precomputed table 276 */ GetQHatModbsk()277 std::vector<std::vector<NativeInteger>> const &GetQHatModbsk() const { 278 return m_QHatModbsk; 279 } 280 281 /** 282 * Gets the precomputed table of [(q_i)^{-1}]_{bsk_j} 283 * 284 * @return the precomputed table 285 */ GetqInvModbsk()286 std::vector<std::vector<NativeInteger>> const &GetqInvModbsk() const { 287 return m_qInvModbsk; 288 } 289 290 /** 291 * Gets the precomputed table of [Q/q_i]_{mtilde} 292 * 293 * @return the precomputed table 294 */ GetQHatModmtilde()295 std::vector<uint16_t> const &GetQHatModmtilde() const { 296 return m_QHatModmtilde; 297 } 298 299 /** 300 * Gets the precomputed table of [Q]_{bsk_j} 301 * 302 * @return the precomputed table 303 */ GetQModbsk()304 std::vector<NativeInteger> const &GetQModbsk() const { return m_QModbsk; } 305 306 /** 307 * Gets the NTL precomputations for [Q]_{bsk_j} 308 * 309 * @return the precomputed table 310 */ GetQModbskPrecon()311 std::vector<NativeInteger> const &GetQModbskPrecon() const { 312 return m_QModbskPrecon; 313 } 314 315 /** 316 * Gets the precomputed [-Q^{-1}]_{mtilde} 317 * 318 * @return the precomputed value 319 */ GetNegQInvModmtilde()320 uint16_t const &GetNegQInvModmtilde() const { return m_negQInvModmtilde; } 321 322 /** 323 * Gets the precomputed table of [mtilde^{-1}]_{bsk_j} 324 * 325 * @return the precomputed table 326 */ GetmtildeInvModbsk()327 std::vector<NativeInteger> const &GetmtildeInvModbsk() const { 328 return m_mtildeInvModbsk; 329 } 330 331 /** 332 * Gets the NTL precomputations for [mtilde^{-1}]_{bsk_j} 333 * 334 * @return the precomputed table 335 */ GetmtildeInvModbskPrecon()336 std::vector<NativeInteger> const &GetmtildeInvModbskPrecon() const { 337 return m_mtildeInvModbskPrecon; 338 } 339 340 /** 341 * Gets the precomputed table of [(Q/q_i)^{-1}]_{q_i} 342 * 343 * @return the precomputed table 344 */ GetQHatInvModq()345 std::vector<NativeInteger> const &GetQHatInvModq() const { 346 return m_QHatInvModq; 347 } 348 349 /** 350 * Gets the precomputed table of [t*(Q/q_i)^{-1}]_{q_i} 351 * 352 * @return the precomputed table 353 */ GettQHatInvModq()354 std::vector<NativeInteger> const &GettQHatInvModq() const { 355 return m_tQHatInvModq; 356 } 357 358 /** 359 * Gets the NTL precomputations for [t*(Q/q_i)^{-1}]_{q_i} 360 * 361 * @return the precomputed table 362 */ GettQHatInvModqPrecon()363 std::vector<NativeInteger> const &GettQHatInvModqPrecon() const { 364 return m_tQHatInvModqPrecon; 365 } 366 367 /** 368 * Gets the precomputed table of [t*gamma*(Q/q_i)^(-1)]_{q_i} 369 * 370 * @return the precomputed table 371 */ GettgammaQHatInvModq()372 std::vector<NativeInteger> const &GettgammaQHatInvModq() const { 373 return m_tgammaQHatInvModq; 374 } 375 376 /** 377 * Gets the NTL precomputations for [t*gamma*(Q/q_i)^(-1)]_{q_i} 378 * 379 * @return the precomputed table 380 */ GettgammaQHatInvModqPrecon()381 std::vector<NativeInteger> const &GettgammaQHatInvModqPrecon() const { 382 return m_tgammaQHatInvModqPrecon; 383 } 384 385 /** 386 * Gets the precomputed table of [t/Q]_{bsk_j} 387 * 388 * @return the precomputed table 389 */ GettQInvModbsk()390 std::vector<NativeInteger> const &GettQInvModbsk() const { 391 return m_tQInvModbsk; 392 } 393 394 /** 395 * Gets the NTL precomputations for [t/Q]_{bsk_j} 396 * 397 * @return the precomputed table 398 */ GettQInvModbskPrecon()399 std::vector<NativeInteger> const &GettQInvModbskPrecon() const { 400 return m_tQInvModbskPrecon; 401 } 402 403 /** 404 * Gets the precomputed table of [(B/b_j)^{-1}]_{b_j} 405 * 406 * @return the precomputed table 407 */ GetBHatInvModb()408 std::vector<NativeInteger> const &GetBHatInvModb() const { 409 return m_BHatInvModb; 410 } 411 412 /** 413 * Gets the NTL precomputations for [(B/b_j)^{-1}]_{b_j} 414 * 415 * @return the precomputed table 416 */ GetBHatInvModbPrecon()417 std::vector<NativeInteger> const &GetBHatInvModbPrecon() const { 418 return m_BHatInvModbPrecon; 419 } 420 421 /** 422 * Gets the precomputed table of [B/b_j]_{msk} 423 * 424 * @return the precomputed table 425 */ GetBHatModmsk()426 std::vector<NativeInteger> const &GetBHatModmsk() const { 427 return m_BHatModmsk; 428 } 429 430 /** 431 * Gets the precomputed [B^{-1}]_msk 432 * 433 * @return the precomputed value 434 */ GetBInvModmsk()435 NativeInteger const &GetBInvModmsk() const { return m_BInvModmsk; } 436 437 /** 438 * Gets the NTL precomputions for [B^{-1}]_msk 439 * 440 * @return the precomputed value 441 */ GetBInvModmskPrecon()442 NativeInteger const &GetBInvModmskPrecon() const { 443 return m_BInvModmskPrecon; 444 } 445 446 /** 447 * Gets the precomputed table of [B/b_j]_{q_i} 448 * 449 * @return the precomputed table 450 */ GetBHatModq()451 std::vector<std::vector<NativeInteger>> const &GetBHatModq() const { 452 return m_BHatModq; 453 } 454 455 /** 456 * Gets the precomputed table of [B]_{q_i} 457 * 458 * @return the precomputed table 459 */ GetBModq()460 std::vector<NativeInteger> const &GetBModq() const { return m_BModq; } 461 462 /** 463 * Gets the NTL precomputions for [B]_{q_i} 464 * 465 * @return the precomputed table 466 */ GetBModqPrecon()467 std::vector<NativeInteger> const &GetBModqPrecon() const { 468 return m_BModqPrecon; 469 } 470 471 /** 472 * Gets auxiliary modulus gamma 473 * 474 * @return gamma 475 */ Getgamma()476 uint32_t const &Getgamma() const { return m_gamma; } 477 478 // TODO: use 64 bit words in case NativeInteger uses smaller word size 479 /** 480 * Gets t*gamma where t - plaintext modulus, gamma - auxiliary modulus 481 * 482 * @return t*gamma 483 */ Gettgamma()484 NativeInteger const &Gettgamma() const { return m_tgamma; } 485 486 /** 487 * Gets the precomputed table of [-(q_i)^{-1}]_{t*gamma} 488 * 489 * @return the precomputed table 490 */ GetNegInvqModtgamma()491 std::vector<NativeInteger> const &GetNegInvqModtgamma() const { 492 return m_negInvqModtgamma; 493 } 494 495 /** 496 * Gets the NTL precomputions for [-(q_i)^{-1}]_{t*gamma} 497 * 498 * @return the precomputed table 499 */ GetNegInvqModtgammaPrecon()500 std::vector<NativeInteger> const &GetNegInvqModtgammaPrecon() const { 501 return m_negInvqModtgammaPrecon; 502 } 503 504 // NOTE that we do not serialize any of the members declared in this class. 505 // they are all cached computations, and get recomputed in any 506 // implementation that does a deserialization 507 template <class Archive> save(Archive & ar,std::uint32_t const version)508 void save(Archive &ar, std::uint32_t const version) const { 509 ar(::cereal::base_class<LPCryptoParametersRLWE<Element>>(this)); 510 } 511 512 template <class Archive> load(Archive & ar,std::uint32_t const version)513 void load(Archive &ar, std::uint32_t const version) { 514 if (version > SerializedVersion()) { 515 PALISADE_THROW(deserialize_error, 516 "serialized object version " + std::to_string(version) + 517 " is from a later version of the library"); 518 } 519 ar(::cereal::base_class<LPCryptoParametersRLWE<Element>>(this)); 520 } 521 SerializedObjectName()522 std::string SerializedObjectName() const { return "BFVrnsBSchemeParameters"; } SerializedVersion()523 static uint32_t SerializedVersion() { return 1; } 524 525 private: 526 // Stores a precomputed table of [\floor{Q/t}]_{q_i} 527 std::vector<NativeInteger> m_QDivtModq; 528 529 // Auxiliary CRT basis {Bsk} = {B U msk} = {{b_j} U msk} 530 shared_ptr<ILDCRTParams<BigInteger>> m_paramsBsk; 531 532 // number of moduli in the base {Q} 533 uint32_t m_numq; 534 535 // number of moduli in the auxilliary base {B} 536 uint32_t m_numb; 537 538 // mtilde = 2^16 539 NativeInteger m_mtilde = NativeInteger((uint64_t)1 << 16); 540 541 // Auxiliary modulus msk 542 NativeInteger m_msk; 543 544 // Stores q_i 545 std::vector<NativeInteger> m_moduliQ; 546 547 // Barrett modulo reduction precomputation for q_i 548 std::vector<DoubleNativeInt> m_modqBarrettMu; 549 550 // Stores auxilliary base moduli b_j 551 std::vector<NativeInteger> m_moduliB; 552 553 // Stores the roots of unity modulo bsk_j 554 std::vector<NativeInteger> m_rootsBsk; 555 556 // Stores moduli {bsk_i} = {{b_j} U msk} 557 std::vector<NativeInteger> m_moduliBsk; 558 559 // Barrett modulo reduction precomputation for bsk_j 560 std::vector<DoubleNativeInt> m_modbskBarrettMu; 561 562 // Stores [(Q/q_i)^{-1}]_{q_i} 563 std::vector<NativeInteger> m_QHatInvModq; 564 565 // Stores [t*(Q/q_i)^{-1}]_{q_i} 566 std::vector<NativeInteger> m_tQHatInvModq; 567 568 // Stores NTL precomputations for [t*(Q/q_i)^{-1}]_{q_i} 569 std::vector<NativeInteger> m_tQHatInvModqPrecon; 570 571 // Stores [Q/q_i]_{bsk_j} 572 std::vector<std::vector<NativeInteger>> m_QHatModbsk; 573 574 // Stores [(q_i)^{-1}]_{bsk_j} 575 std::vector<std::vector<NativeInteger>> m_qInvModbsk; 576 577 // Stores [Q/q_i]_{mtilde} 578 std::vector<uint16_t> m_QHatModmtilde; 579 580 // Stores [mtilde*(Q/q_i)^{-1}]_{q_i} 581 std::vector<NativeInteger> m_mtildeQHatInvModq; 582 583 // Stores NTL precomputations for [mtilde*(Q/q_i)^{-1}]_{q_i} 584 std::vector<NativeInteger> m_mtildeQHatInvModqPrecon; 585 586 // Stores [-Q^{-1}]_{mtilde} 587 uint16_t m_negQInvModmtilde; 588 589 // Stores [Q]_{bsk_j} 590 std::vector<NativeInteger> m_QModbsk; 591 // Stores NTL precomputations for [Q]_{bsk_j} 592 std::vector<NativeInteger> m_QModbskPrecon; 593 594 // Stores [mtilde^{-1}]_{bsk_j} 595 std::vector<NativeInteger> m_mtildeInvModbsk; 596 // Stores NTL precomputations for [mtilde^{-1}]_{bsk_j} 597 std::vector<NativeInteger> m_mtildeInvModbskPrecon; 598 599 // Stores [t/Q]_{bsk_j} 600 std::vector<NativeInteger> m_tQInvModbsk; 601 // Stores NTL precomputations for [t/Q]_{bsk_j} 602 std::vector<NativeInteger> m_tQInvModbskPrecon; 603 604 // Stores [(B/b_j)^{-1}]_{b_j} 605 std::vector<NativeInteger> m_BHatInvModb; 606 // Stores NTL precomputations for [(B/b_j)^{-1}]_{b_j} 607 std::vector<NativeInteger> m_BHatInvModbPrecon; 608 609 // Stores [B/b_j]_{q_i} 610 std::vector<std::vector<NativeInteger>> m_BHatModq; 611 612 // stores [B/b_j]_{msk} 613 std::vector<NativeInteger> m_BHatModmsk; 614 615 // Stores [B^{-1}]_msk 616 NativeInteger m_BInvModmsk; 617 // Stores NTL precomputations for [B^{-1}]_msk 618 NativeInteger m_BInvModmskPrecon; 619 620 // Stores [B]_{q_i} 621 std::vector<NativeInteger> m_BModq; 622 // Stores NTL precomputations for [B]_{q_i} 623 std::vector<NativeInteger> m_BModqPrecon; 624 625 // Stores gamma = 2^26; 626 uint32_t m_gamma = 1 << 26; 627 628 // TODO: use 64 bit words in case NativeInteger uses smaller word size 629 // Stores t*gamma on a uint64_t word 630 NativeInteger m_tgamma; 631 632 // Stores [-(q_i)^{-1}]_{t*gamma} 633 std::vector<NativeInteger> m_negInvqModtgamma; 634 // Stores NTL precomputations for [-(q_i)^{-1}]_{t*gamma} 635 std::vector<NativeInteger> m_negInvqModtgammaPrecon; 636 637 // Stores [t*gamma*(Q/q_i)^(-1)]_{q_i} 638 std::vector<NativeInteger> m_tgammaQHatInvModq; 639 // Stores NTL precomputations for [t*gamma*(Q/q_i)^(-1)]_{q_i} 640 std::vector<NativeInteger> m_tgammaQHatInvModqPrecon; 641 }; 642 643 /** 644 * @brief Parameter generation for BFVrnsB. This scheme is also referred to 645 * as the FV scheme. 646 * 647 * @tparam Element a ring element. 648 */ 649 template <class Element> 650 class LPAlgorithmParamsGenBFVrnsB : public LPAlgorithmParamsGenBFV<Element> { 651 using ParmType = typename Element::Params; 652 using IntType = typename Element::Integer; 653 using DugType = typename Element::DugType; 654 using DggType = typename Element::DggType; 655 using TugType = typename Element::TugType; 656 657 public: 658 /** 659 * Default constructor 660 */ LPAlgorithmParamsGenBFVrnsB()661 LPAlgorithmParamsGenBFVrnsB() {} 662 663 /** 664 * Method for computing all derived parameters based on chosen primitive 665 * parameters 666 * 667 * @param cryptoParams the crypto parameters object to be populated with 668 * parameters. 669 * @param evalAddCount number of EvalAdds assuming no EvalMult and KeySwitch 670 * operations are performed. 671 * @param evalMultCount number of EvalMults assuming no EvalAdd and 672 * KeySwitch operations are performed. 673 * @param keySwitchCount number of KeySwitch operations assuming no EvalAdd 674 * and EvalMult operations are performed. 675 * @param n ring dimension in case the user wants to use a custom ring 676 * dimension 677 */ 678 bool ParamsGen(shared_ptr<LPCryptoParameters<Element>> cryptoParams, 679 int32_t evalAddCount = 0, int32_t evalMultCount = 0, 680 int32_t keySwitchCount = 0, size_t dcrBits = 60, 681 uint32_t n = 0) const override; 682 }; 683 684 /** 685 * @brief Encryption algorithm implementation for BFVrnsB for the basic public 686 * key encrypt, decrypt and key generation methods for the BFVrnsB encryption 687 * scheme. 688 * 689 * @tparam Element a ring element. 690 */ 691 template <class Element> 692 class LPAlgorithmBFVrnsB : public LPAlgorithmBFV<Element> { 693 using ParmType = typename Element::Params; 694 using IntType = typename Element::Integer; 695 using DugType = typename Element::DugType; 696 using DggType = typename Element::DggType; 697 using TugType = typename Element::TugType; 698 699 public: 700 /** 701 * Default constructor 702 */ LPAlgorithmBFVrnsB()703 LPAlgorithmBFVrnsB() {} 704 705 /** 706 * Method for encrypting plaintext using BFVrnsB. 707 * 708 * @param publicKey public key used for encryption. 709 * @param plaintext the plaintext input. 710 * @return ciphertext which results from encryption. 711 */ 712 Ciphertext<Element> Encrypt(const LPPublicKey<Element> publicKey, 713 Element plaintext) const override; 714 715 /** 716 * Method for encrypting plaintext with private key using BFVrnsB. 717 * 718 * @param privateKey private key used for encryption. 719 * @param plaintext the plaintext input. 720 * @return ciphertext which results from encryption. 721 */ 722 Ciphertext<Element> Encrypt(const LPPrivateKey<Element> privateKey, 723 Element plaintext) const override; 724 725 /** 726 * Method for decrypting using BFVrnsB. See the class description for 727 * citations on where the algorithms were taken from. 728 * 729 * @param privateKey private key used for decryption. 730 * @param ciphertext ciphertext to be decrypted. 731 * @param *plaintext the plaintext output. 732 * @return the decrypted plaintext returned. 733 */ 734 DecryptResult Decrypt(const LPPrivateKey<Element> privateKey, 735 ConstCiphertext<Element> ciphertext, 736 NativePoly *plaintext) const override; 737 }; 738 739 /** 740 * @brief SHE algorithms implementation for BFVrnsB. 741 * 742 * @tparam Element a ring element. 743 */ 744 template <class Element> 745 class LPAlgorithmSHEBFVrnsB : public LPAlgorithmSHEBFV<Element> { 746 using ParmType = typename Element::Params; 747 using IntType = typename Element::Integer; 748 using DugType = typename Element::DugType; 749 using DggType = typename Element::DggType; 750 using TugType = typename Element::TugType; 751 752 public: 753 /** 754 * Default constructor 755 */ LPAlgorithmSHEBFVrnsB()756 LPAlgorithmSHEBFVrnsB() {} 757 758 /** 759 * Function for homomorphic addition of ciphertext and plaintext. 760 * 761 * @param ct input ciphertext. 762 * @param pt input plaintext. 763 * @return new ciphertext. 764 */ 765 Ciphertext<Element> EvalAdd(ConstCiphertext<Element> ct, 766 ConstPlaintext pt) const override; 767 768 /** 769 * Function for homomorphic subtraction of ciphertext ans plaintext. 770 * 771 * @param ct input ciphertext. 772 * @param pt input plaintext. 773 * @return new ciphertext. 774 */ 775 Ciphertext<Element> EvalSub(ConstCiphertext<Element> ct, 776 ConstPlaintext pt) const override; 777 778 /** 779 * Function for homomorphic evaluation of ciphertexts. 780 * The multiplication is supported for a fixed level without keyswitching 781 * requirement (default level=2). If the total depth of the ciphertexts 782 * exceeds the supported level, it throws an error. 783 * 784 * @param ct1 first input ciphertext. 785 * @param ct2 second input ciphertext. 786 * @return resulting EvalMult ciphertext. 787 */ 788 Ciphertext<Element> EvalMult(ConstCiphertext<Element> ct1, 789 ConstCiphertext<Element> ct2) const override; 790 791 /** 792 * Method for generating a KeySwitchHint using RLWE relinearization 793 * 794 * @param oldKey Original private key used for encryption. 795 * @param newKey New private key to generate the keyswitch hint. 796 * @return resulting keySwitchHint. 797 */ 798 LPEvalKey<Element> KeySwitchGen( 799 const LPPrivateKey<Element> oldKey, 800 const LPPrivateKey<Element> newKey) const override; 801 802 /** 803 * Method for in-place key switching based on a KeySwitchHint using RLWE 804 * relinearization 805 * 806 * @param keySwitchHint Hint required to perform the ciphertext switching. 807 * @param &cipherText Original ciphertext to perform in-place key switching 808 * on. 809 */ 810 void KeySwitchInPlace(const LPEvalKey<Element> keySwitchHint, 811 Ciphertext<Element>& ciphertext) const override; 812 813 /** 814 * Function for evaluating multiplication on ciphertext followed by 815 * relinearization operation. Currently it assumes that the input arguments 816 * have total depth smaller than the supported depth. Otherwise, it throws 817 * an error. 818 * 819 * @param ct1 first input ciphertext. 820 * @param ct2 second input ciphertext. 821 * @param &ek is the evaluation key to make the newCiphertext 822 * decryptable by the same secret key as that of ciphertext1 and 823 * ciphertext2. 824 * @return new ciphertext 825 */ 826 Ciphertext<Element> EvalMultAndRelinearize( 827 ConstCiphertext<Element> ct1, ConstCiphertext<Element> ct2, 828 const vector<LPEvalKey<Element>> &ek) const override; 829 }; 830 831 /** 832 * @brief PRE algorithms implementation for BFVrnsB. 833 * 834 * @tparam Element a ring element. 835 */ 836 template <class Element> 837 class LPAlgorithmPREBFVrnsB : public LPAlgorithmPREBFV<Element> { 838 using ParmType = typename Element::Params; 839 using IntType = typename Element::Integer; 840 using DugType = typename Element::DugType; 841 using DggType = typename Element::DggType; 842 using TugType = typename Element::TugType; 843 844 public: 845 /** 846 * Default constructor 847 */ LPAlgorithmPREBFVrnsB()848 LPAlgorithmPREBFVrnsB() {} 849 850 /** 851 * The generation of re-encryption keys is based on the BG-PRE scheme 852 * described in Polyakov, et. al., "Fast proxy re-encryption for 853 * publish/subscribe systems". 854 * 855 * The above scheme was found to have a weakness in Cohen, "What about Bob? 856 * The inadequacy of CPA Security for proxy re-encryption". Section 5.1 857 * shows an attack where given an original ciphertext c=(c0,c1) and a 858 * re-encrypted ciphertext c'=(c'0, c'1), the subscriber (Bob) can compute 859 * the secret key of the publisher (Alice). 860 * 861 * We fix this vulnerability by making re-encryption keys be encryptions of 862 * the s*(2^{i*r}) terms, instead of simple addition as previously defined. 863 * This makes retrieving the secret key using the above attack as hard as 864 * breaking the RLWE assumption. 865 * 866 * Our modification makes the scheme CPA-secure, but does not achieve 867 * HRA-security as it was defined in the Cohen paper above. Please look at 868 * the ReEncrypt method for an explanation of the two security definitions 869 * and how to achieve each in Palisade. 870 * 871 * @param newKey public key for the new private key. 872 * @param oldKey original private key used for decryption. 873 * @return evalKey the evaluation key for switching the ciphertext to be 874 * decryptable by new private key. 875 */ 876 LPEvalKey<Element> ReKeyGen( 877 const LPPublicKey<Element> newKey, 878 const LPPrivateKey<Element> oldKey) const override; 879 880 /** 881 * This method implements re-encryption using the evaluation key generated 882 * by ReKeyGen. 883 * 884 * The PRE scheme used can achieve two different levels of security, based 885 * on the value supplied in the publicKey argument: 886 * 887 * If publicKey is nullptr, the PRE scheme is CPA-secure. If the publicKey 888 * of the recipient of the re-encrypted ciphertext is supplied, then the 889 * scheme is HRA- secure. Please refer to Cohen, "What about Bob? The 890 * inadequacy of CPA Security for proxy re-encryption", for more information 891 * on HRA security. 892 * 893 * The tradeoff of going for HRA is twofold: (1) performance is a little 894 * worst because we add one additional encryption and homomorphic addition 895 * to the result, and (2) more noise is added to the result because of the 896 * additional operations - in particular, the extra encryption draws noise 897 * from a distribution whose standard deviation is scaled by K, the number 898 * of digits in the PRE decomposition. 899 * 900 * @param ek the evaluation key. 901 * @param ciphertext the input ciphertext. 902 * @param publicKey the public key of the recipient of the re-encrypted 903 * ciphertext. 904 * @return resulting ciphertext after the re-encryption operation. 905 */ 906 Ciphertext<Element> ReEncrypt( 907 const LPEvalKey<Element> ek, ConstCiphertext<Element> ciphertext, 908 const LPPublicKey<Element> publicKey = nullptr) const override; 909 }; 910 911 /** 912 * @brief Concrete class for the FHE Multiparty algorithms on BFVrnsB. This 913 * scheme is also referred to as the FV scheme. A version of this multiparty 914 * scheme built on the BGV scheme is seen here: 915 * - Asharov G., Jain A., López-Alt A., Tromer E., Vaikuntanathan V., Wichs 916 * D. (2012) Multiparty Computation with Low Communication, Computation and 917 * Interaction via Threshold FHE. In: Pointcheval D., Johansson T. (eds) 918 * Advances in Cryptology – EUROCRYPT 2012. EUROCRYPT 2012. Lecture Notes in 919 * Computer Science, vol 7237. Springer, Berlin, Heidelberg 920 * 921 * During offline key generation, this multiparty scheme relies on the clients 922 * coordinating their public key generation. To do this, a single client 923 * generates a public-secret key pair. This public key is shared with other 924 * keys which use an element in the public key to generate their own public 925 * keys. The clients generate a shared key pair using a scheme-specific 926 * approach, then generate re-encryption keys. Re-encryption keys are 927 * uploaded to the server. Clients encrypt data with their public keys and 928 * send the encrypted data server. The data is re-encrypted. Computations are 929 * then run on the data. The result is sent to each of the clients. One client 930 * runs a "Leader" multiparty decryption operation with its own secret key. 931 * All other clients run a regular "Main" multiparty decryption with their own 932 * secret key. The resulting partially decrypted ciphertext are then fully 933 * decrypted with the decryption fusion algorithms. 934 * 935 * @tparam Element a ring element. 936 */ 937 template <class Element> 938 class LPAlgorithmMultipartyBFVrnsB : public LPAlgorithmMultipartyBFV<Element> { 939 using ParmType = typename Element::Params; 940 using IntType = typename Element::Integer; 941 using DugType = typename Element::DugType; 942 using DggType = typename Element::DggType; 943 using TugType = typename Element::TugType; 944 945 public: 946 /** 947 * Default constructor 948 */ LPAlgorithmMultipartyBFVrnsB()949 LPAlgorithmMultipartyBFVrnsB() {} 950 951 /** 952 * Threshold FHE: Method for combining the partially decrypted ciphertexts 953 * and getting the final decryption in the clear as a NativePoly. 954 * 955 * @param &ciphertextVec vector of "partial" decryptions. 956 * @param *plaintext the plaintext output as a NativePoly. 957 * @return the decoding result. 958 */ 959 DecryptResult MultipartyDecryptFusion( 960 const vector<Ciphertext<Element>> &ciphertextVec, 961 NativePoly *plaintext) const override; 962 963 /** 964 * Threshold FHE: Generates a joined evaluation key 965 * from the current secret share and a prior joined 966 * evaluation key 967 * 968 * @param oldKey secret key transformed from. 969 * @param newKey secret key transformed to. 970 * @param ek the prior joined evaluation key. 971 * @return the new joined evaluation key. 972 */ 973 LPEvalKey<Element> MultiKeySwitchGen( 974 const LPPrivateKey<Element> oldKey, const LPPrivateKey<Element> newKey, 975 const LPEvalKey<Element> ek) const override; 976 977 template <class Archive> save(Archive & ar)978 void save(Archive &ar) const { 979 ar(cereal::base_class<LPAlgorithmMultipartyBFV<Element>>(this)); 980 } 981 982 template <class Archive> load(Archive & ar)983 void load(Archive &ar) { 984 ar(cereal::base_class<LPAlgorithmMultipartyBFV<Element>>(this)); 985 } 986 SerializedObjectName()987 std::string SerializedObjectName() const { return "BFVrnsBMultiparty"; } 988 }; 989 990 /** 991 * @brief Main public key encryption scheme for BFVrnsB implementation, 992 * @tparam Element a ring element. 993 */ 994 template <class Element> 995 class LPPublicKeyEncryptionSchemeBFVrnsB 996 : public LPPublicKeyEncryptionScheme<Element> { 997 using ParmType = typename Element::Params; 998 using IntType = typename Element::Integer; 999 using DugType = typename Element::DugType; 1000 using DggType = typename Element::DggType; 1001 using TugType = typename Element::TugType; 1002 1003 public: 1004 LPPublicKeyEncryptionSchemeBFVrnsB(); 1005 1006 bool operator==( 1007 const LPPublicKeyEncryptionScheme<Element> &sch) const override { 1008 return dynamic_cast<const LPPublicKeyEncryptionSchemeBFVrnsB<Element> *>( 1009 &sch) != nullptr; 1010 } 1011 1012 void Enable(PKESchemeFeature feature) override; 1013 1014 template <class Archive> save(Archive & ar,std::uint32_t const version)1015 void save(Archive &ar, std::uint32_t const version) const { 1016 ar(::cereal::base_class<LPPublicKeyEncryptionScheme<Element>>(this)); 1017 } 1018 1019 template <class Archive> load(Archive & ar,std::uint32_t const version)1020 void load(Archive &ar, std::uint32_t const version) { 1021 ar(::cereal::base_class<LPPublicKeyEncryptionScheme<Element>>(this)); 1022 } 1023 SerializedObjectName()1024 std::string SerializedObjectName() const override { return "BFVrnsScheme"; } 1025 }; 1026 1027 } // namespace lbcrypto 1028 1029 #endif 1030