1 // @file transfrm.h This file contains the linear transform interface 2 // functionality. 3 // @author TPOC: contact@palisade-crypto.org 4 // 5 // @copyright Copyright (c) 2019, New Jersey Institute of Technology (NJIT) 6 // All rights reserved. 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 1. Redistributions of source code must retain the above copyright notice, 10 // this list of conditions and the following disclaimer. 11 // 2. Redistributions in binary form must reproduce the above copyright notice, 12 // this list of conditions and the following disclaimer in the documentation 13 // and/or other materials provided with the distribution. THIS SOFTWARE IS 14 // PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR 15 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 16 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 17 // EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 18 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 23 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 25 #ifndef LBCRYPTO_MATH_TRANSFRM_H 26 #define LBCRYPTO_MATH_TRANSFRM_H 27 28 #include <time.h> 29 #include <chrono> 30 #include <complex> 31 #include <fstream> 32 #include <map> 33 #include <mutex> 34 #include <thread> 35 #include <utility> 36 #include <vector> 37 38 #include "math/backend.h" 39 #include "math/nbtheory.h" 40 #include "utils/utilities.h" 41 42 #ifdef WITH_INTEL_HEXL 43 #include "hexl/hexl.hpp" 44 #endif 45 46 #ifndef M_PI 47 #define M_PI 3.14159265358979323846 48 #endif 49 50 /** 51 * @namespace lbcrypto 52 * The namespace of lbcrypto 53 */ 54 namespace lbcrypto { 55 56 struct HashPair { 57 template <class T1, class T2> operatorHashPair58 size_t operator()(const std::pair<T1, T2>& p) const { 59 auto hash1 = std::hash<T1>{}(std::get<0>(p)); 60 auto hash2 = std::hash<T2>{}(std::get<1>(p)); 61 return HashCombine(hash1, hash2); 62 } 63 HashCombineHashPair64 static size_t HashCombine(size_t lhs, size_t rhs) { 65 lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2); 66 return lhs; 67 } 68 }; 69 70 /** 71 * @brief Number Theoretic Transform implemetation 72 */ 73 template <typename VecType> 74 class NumberTheoreticTransform { 75 using IntType = typename VecType::Integer; 76 77 public: 78 /** 79 * Forward transform in the ring Z_q[X]/(X^n-1). 80 * 81 * @param &element is the input to the transform of type VecType and length n 82 * s.t. n|q-1. 83 * @param &rootOfUnityTable is the table with the root of unity powers. 84 * @return is the result of the transform, a VecType should be of the same 85 * size as input or a throw if an error occurs. 86 */ 87 static void ForwardTransformIterative(const VecType& element, 88 const VecType& rootOfUnityTable, 89 VecType* result); 90 91 /** 92 * Inverse transform in the ring Z_q[X]/(X^n-1) with prime q and power-of-two 93 * n s.t. n|q-1. 94 * 95 * @param[in,out] &element is the input and output to the transform of type VecType and length n. 96 * @param &rootOfUnityTable is the table with the inverse n-th root of unity 97 * powers. 98 * @return is the result of the transform, a VecType should be of the same 99 * size as input or a throw if an error occurs. 100 */ 101 static void InverseTransformIterative(const VecType& element, 102 const VecType& rootOfUnityInverseTable, 103 VecType* result); 104 105 /** 106 * Copies \p element into \p result and calls ForwardTransformToBitReverseInPlace() 107 * 108 * Forward transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two 109 * n s.t. 2n|q-1. Bit reversing indexes. [Algorithm 1 in 110 * https://eprint.iacr.org/2016/504.pdf] 111 * 112 * @param[in] &element is the input to the transform of type VecType and length n. 113 * @param &rootOfUnityTable is the table with the n-th root of unity powers in 114 * bit reverse order. 115 * @param[out] *result is the result of the transform, a VecType should be of the same 116 * size as input or a throw if an error occurs. 117 * @see ForwardTransformToBitReverseInPlace() 118 */ 119 static void ForwardTransformToBitReverse(const VecType& element, 120 const VecType& rootOfUnityTable, 121 VecType* result); 122 /** 123 * In-place forward transform in the ring Z_q[X]/(X^n+1) with prime q and 124 * power-of-two n s.t. 2n|q-1. Bit reversing indexes. [Algorithm 1 in 125 * https://eprint.iacr.org/2016/504.pdf] 126 * 127 * @param &rootOfUnityTable is the table with the n-th root of unity powers in 128 * bit reverse order. 129 * @param &element[in,out] is the input/output of the transform of type VecType and length n. 130 * @return none 131 */ 132 static void ForwardTransformToBitReverseInPlace( 133 const VecType& rootOfUnityTable, VecType* element); 134 135 /** 136 * Copies \p element into \p result and calls ForwardTransformToBitReverseInPlace() 137 * 138 * Forward transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two 139 * n s.t. 2n|q-1. Bit reversing indexes. The method works for the 140 * NativeInteger case based on NTL's modular multiplication. [Algorithm 1 in 141 * https://eprint.iacr.org/2016/504.pdf] 142 * 143 * @param &element is the input to the transform of type VecType and length n. 144 * @param &rootOfUnityTable is the table with the root of unity powers in bit 145 * reverse order. 146 * @param &preconRootOfUnityTable is NTL-specific precomputations for 147 * optimized NativeInteger modulo multiplications. 148 * @param[out] *result is the result of the transform, a VecType should be of the same 149 * size as input or a throw if an error occurs. 150 * @return none 151 * @see ForwardTransformToBitReverseInPlace() 152 */ 153 static void ForwardTransformToBitReverse( 154 const VecType& element, const VecType& rootOfUnityTable, 155 const NativeVector& preconRootOfUnityTable, VecType* result); 156 157 /** 158 * In-place forward transform in the ring Z_q[X]/(X^n+1) with prime q and 159 * power-of-two n s.t. 2n|q-1. Bit reversing indexes. The method works for the 160 * NativeInteger case based on NTL's modular multiplication. [Algorithm 1 in 161 * https://eprint.iacr.org/2016/504.pdf] 162 * 163 * @param &rootOfUnityTable is the table with the root of unity powers in bit 164 * reverse order. 165 * @param &preconRootOfUnityTable is NTL-specific precomputations for 166 * optimized NativeInteger modulo multiplications. 167 * @param[in,out] &element is the input/output of the transform of type VecType and length n. 168 * @return none 169 */ 170 static void ForwardTransformToBitReverseInPlace( 171 const VecType& rootOfUnityTable, 172 const NativeVector& preconRootOfUnityTable, VecType* element); 173 174 /** 175 * Copies \p element into \p result and calls InverseTransformFromBitReverseInPlace() 176 * 177 * Inverse transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two 178 * n s.t. 2n|q-1. Bit reversing indexes. [Algorithm 2 in 179 * https://eprint.iacr.org/2016/504.pdf] 180 * 181 * @param &element is the input to the transform of type VecType and length n. 182 * @param &rootOfUnityInverseTable is the table with the inverse 2n-th root of 183 * unity powers in bit reverse order. 184 * @param &cycloOrderInv is inverse of n modulo q 185 * @param[out] *result is the result of the transform, a VecType should be of the same 186 * size as input or a throw if an error occurs. 187 * @return none 188 * @see InverseTransformFromBitReverseInPlace() 189 */ 190 static void InverseTransformFromBitReverse( 191 const VecType& element, const VecType& rootOfUnityInverseTable, 192 const IntType& cycloOrderInv, VecType* result); 193 194 /** 195 * In-place inverse transform in the ring Z_q[X]/(X^n+1) with prime q and 196 * power-of-two n s.t. 2n|q-1. Bit reversing indexes. [Algorithm 2 in 197 * https://eprint.iacr.org/2016/504.pdf] 198 * 199 * @param &rootOfUnityInverseTable is the table with the inverse 2n-th root of 200 * unity powers in bit reverse order. 201 * @param &cycloOrderInv is inverse of n modulo q 202 * @param[in,out] &element is the input/output of the transform of type VecType and length n. 203 * @return none 204 */ 205 static void InverseTransformFromBitReverseInPlace( 206 const VecType& rootOfUnityInverseTable, const IntType& cycloOrderInv, 207 VecType* element); 208 209 /** 210 * Copies \p element into \p result and calls InverseTransformFromBitReverseInPlace() 211 * 212 * Inverse transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two 213 * n s.t. 2n|q-1. Bit reversing indexes. The method works for the 214 * NativeInteger case based on NTL's modular multiplication. [Algorithm 2 in 215 * https://eprint.iacr.org/2016/504.pdf] 216 * 217 * @param &element is the input to the transform of type VecType and length n. 218 * @param &rootOfUnityInverseTable is the table with the inverse 2n-th root of 219 * unity powers in bit reverse order. 220 * @param &preconRootOfUnityInverseTable is NTL-specific precomputations for 221 * optimized NativeInteger modulo multiplications. 222 * @param &cycloOrderInv is inverse of n modulo q 223 * @param &preconCycloOrderInv is NTL-specific precomputations for optimized 224 * NativeInteger modulo multiplications. 225 * @param *result is the result of the transform, a VecType should be of the same 226 * size as input or a throw if an error occurs. 227 * @return none. 228 * @see InverseTransformFromBitReverseInPlace() 229 */ 230 static void InverseTransformFromBitReverse( 231 const VecType& element, const VecType& rootOfUnityInverseTable, 232 const NativeVector& preconRootOfUnityInverseTable, 233 const IntType& cycloOrderInv, const NativeInteger& preconCycloOrderInv, 234 VecType* result); 235 236 /** 237 * In-place Inverse transform in the ring Z_q[X]/(X^n+1) with prime q and 238 * power-of-two n s.t. 2n|q-1. Bit reversing indexes. The method works for the 239 * NativeInteger case based on NTL's modular multiplication. [Algorithm 2 in 240 * https://eprint.iacr.org/2016/504.pdf] 241 * 242 * @param &rootOfUnityInverseTable is the table with the inverse 2n-th root of 243 * unity powers in bit reverse order. 244 * @param &preconRootOfUnityInverseTable is NTL-specific precomputations for 245 * optimized NativeInteger modulo multiplications. 246 * @param &cycloOrderInv is inverse of n modulo q 247 * @param &preconCycloOrderInv is NTL-specific precomputations for optimized 248 * NativeInteger modulo multiplications. 249 * @param &element[in,out] is the input/output of the transform of type VecType and length n. 250 * @return none 251 */ 252 static void InverseTransformFromBitReverseInPlace( 253 const VecType& rootOfUnityInverseTable, 254 const NativeVector& preconRootOfUnityInverseTable, 255 const IntType& cycloOrderInv, const NativeInteger& preconCycloOrderInv, 256 VecType* element); 257 }; 258 259 /** 260 * @brief Golden Chinese Remainder Transform FFT implemetation. 261 */ 262 template <typename VecType> 263 class ChineseRemainderTransformFTT { 264 using IntType = typename VecType::Integer; 265 266 public: 267 /** 268 * Copies \p element into \p result and calls NumberTheoreticTransform::ForwardTransformToBitReverseInPlace() 269 * 270 * Forward Transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two 271 * n s.t. 2n|q-1. Bit reversing indexes. 272 * 273 * @param[in] &element is the input to the transform of type VecType and length n. 274 * @param &rootOfUnity is the 2n-th root of unity in Z_q. Used to precompute 275 * the root of unity tables if needed. If rootOfUnity == 0 or 1, then the 276 * result == input. 277 * @param CycloOrder is 2n, should be a power-of-two or a throw if an error 278 * occurs. 279 * @param[out] *result is the result of the transform, a VecType should be of the same 280 * size as input or a throw of error occurs. 281 * @see NumberTheoreticTransform::ForwardTransformToBitReverseInPlace() 282 */ 283 static void ForwardTransformToBitReverse(const VecType& element, 284 const IntType& rootOfUnity, 285 const usint CycloOrder, 286 VecType* result); 287 288 /** 289 * In-place Forward Transform in the ring Z_q[X]/(X^n+1) with prime q and 290 * power-of-two n s.t. 2n|q-1. Bit reversing indexes. 291 * 292 * @param &rootOfUnity is the 2n-th root of unity in Z_q. Used to precompute 293 * the root of unity tables if needed. If rootOfUnity == 0 or 1, then the 294 * result == input. 295 * @param CycloOrder is 2n, should be a power-of-two or a throw if an error 296 * occurs. 297 * @param[in,out] &element is the input to the transform of type VecType and length n. 298 * @return none 299 * @see NumberTheoreticTransform::ForwardTransformToBitReverseInPlace() 300 */ 301 static void ForwardTransformToBitReverseInPlace(const IntType& rootOfUnity, 302 const usint CycloOrder, 303 VecType* element); 304 305 /** 306 * Copies \p element into \p result and calls NumberTheoreticTransform::InverseTransformFromBitReverseInPlace() 307 * 308 * Inverse Transform in the ring Z_q[X]/(X^n+1) with prime q and power-of-two 309 * n s.t. 2n|q-1. Bit reversing indexes. 310 * 311 * @param &element[in] is the input to the transform of type VecType and length n. 312 * @param &rootOfUnity is the 2n-th root of unity in Z_q. Used to precompute 313 * the root of unity tables if needed. If rootOfUnity == 0 or 1, then the 314 * result == input. 315 * @param CycloOrder is 2n, should be a power-of-two or a throw if an error 316 * occurs. 317 * @param[out] *result is the result of the transform, a VecType should be of the same 318 * size as input or a throw if an error occurs. 319 * @return none 320 * @see NumberTheoreticTransform::InverseTransformFromBitReverseInPlace() 321 */ 322 static void InverseTransformFromBitReverse(const VecType& element, 323 const IntType& rootOfUnity, 324 const usint CycloOrder, 325 VecType* result); 326 327 /** 328 * In-place Inverse Transform in the ring Z_q[X]/(X^n+1) with prime q and 329 * power-of-two n s.t. 2n|q-1. Bit reversing indexes. 330 * 331 * @param &rootOfUnity is the 2n-th root of unity in Z_q. Used to precompute 332 * the root of unity tables if needed. If rootOfUnity == 0 or 1, then the 333 * result == input. 334 * @param CycloOrder is 2n, should be a power-of-two or a throw if an error 335 * occurs. 336 * @param[in,out] &element is the input/output of the transform of type VecType and length n. 337 * @return none 338 * @see NumberTheoreticTransform::InverseTransformFromBitReverseInPlace() 339 */ 340 static void InverseTransformFromBitReverseInPlace(const IntType& rootOfUnity, 341 const usint CycloOrder, 342 VecType* element); 343 344 /** 345 * Precomputation of root of unity tables for transforms in the ring 346 * Z_q[X]/(X^n+1) 347 * 348 * @param &rootOfUnity is the 2n-th root of unity in Z_q. Used to precompute 349 * the root of unity tables if needed. If rootOfUnity == 0 or 1, then the 350 * result == input. 351 * @param CycloOrder is a power-of-two, equal to 2n. 352 * @param modulus is q, the prime modulus 353 */ 354 static void PreCompute(const IntType& rootOfUnity, const usint CycloOrder, 355 const IntType& modulus); 356 357 /** 358 * Precomputation of root of unity tables for transforms in the ring 359 * Z_q[X]/(X^n+1) 360 * 361 * @param &rootOfUnity is the 2n-th root of unity in Z_q. Used to precompute 362 * the root of unity tables if needed. If rootOfUnity == 0 or 1, then the 363 * result == input. 364 * @param CycloOrder is a power-of-two, equal to 2n. 365 * @param &moduliChain is the vector of prime moduli qi such that 2n|qi-1 366 */ 367 static void PreCompute(std::vector<IntType>& rootOfUnity, 368 const usint CycloOrder, 369 std::vector<IntType>& moduliChain); 370 371 /** 372 * Reset cached values for the root of unity tables to empty. 373 */ 374 static void Reset(); 375 376 // private: 377 378 /// map to store the cyclo order inverse with modulus as a key 379 /// For inverse FTT, we also need #m_cycloOrderInversePreconTableByModulus (this is to use an N-size NTT for FTT instead of 2N-size NTT). 380 static std::map<IntType, VecType> m_cycloOrderInverseTableByModulus; 381 382 /// map to store the cyclo order inverse preconditioned with modulus as a key 383 /// Shoup's precomputation of above #m_cycloOrderInverseTableByModulus 384 static std::map<IntType, NativeVector> m_cycloOrderInversePreconTableByModulus; 385 386 /// map to store the forward roots of Unity for NTT, with bits reversed, with modulus as a key (aka twiddle factors) 387 static std::map<IntType, VecType> m_rootOfUnityReverseTableByModulus; 388 389 /// map to store inverse roots of unity for iNTT, with bits reversed, with modulus as a key (aka inverse twiddle factors) 390 static std::map<IntType, VecType> m_rootOfUnityInverseReverseTableByModulus; 391 392 /// map to store Shoup's precomputations of forward roots of unity for NTT, with bits reversed, with modulus as a key 393 static std::map<IntType, NativeVector> m_rootOfUnityPreconReverseTableByModulus; 394 395 /// map to store Shoup's precomputations of inverse rou for iNTT, with bits reversed, with modulus as a key 396 static std::map<IntType, NativeVector> m_rootOfUnityInversePreconReverseTableByModulus; 397 398 #ifdef WITH_INTEL_HEXL 399 // Key is <modulus, CycloOrderHalf> 400 static std::unordered_map<std::pair<uint64_t, uint64_t>, intel::hexl::NTT, 401 HashPair> 402 m_IntelNtt; 403 static std::mutex m_mtxIntelNTT; 404 #endif 405 }; 406 407 // struct used as a key in BlueStein transform 408 template <typename IntType> 409 using ModulusRoot = std::pair<IntType, IntType>; 410 411 template <typename IntType> 412 using ModulusRootPair = std::pair<ModulusRoot<IntType>, ModulusRoot<IntType>>; 413 414 /** 415 * @brief Bluestein Fast Fourier Transform implemetation 416 */ 417 template <typename VecType> 418 class BluesteinFFT { 419 using IntType = typename VecType::Integer; 420 421 public: 422 /** 423 * Forward transform. 424 * 425 * @param element is the element to perform the transform on. 426 * @param rootOfUnityTable the root of unity table. 427 * @param cycloOrder is the cyclotomic order. 428 * @return is the output result of the transform. 429 */ 430 static VecType ForwardTransform(const VecType& element, const IntType& root, 431 const usint cycloOrder); 432 static VecType ForwardTransform(const VecType& element, const IntType& root, 433 const usint cycloOrder, 434 const ModulusRoot<IntType>& nttModulusRoot); 435 436 /** 437 * 438 * @param a is the input vector to be padded with zeros. 439 * @param finalSize is the length of the output vector. 440 * @return output vector padded with (finalSize - initial size)additional 441 * zeros. 442 */ 443 static VecType PadZeros(const VecType& a, const usint finalSize); 444 445 /** 446 * 447 * @param a is the input vector to be resized. 448 * @param lo is lower coefficient index. 449 * @param hi is higher coefficient index. 450 * @return output vector s.t output vector = a[lo]...a[hi]. 451 */ 452 static VecType Resize(const VecType& a, usint lo, usint hi); 453 454 // void PreComputeNTTModulus(usint cycloOrder, const std::vector<IntType> 455 // &modulii); 456 457 /** 458 * @brief Precomputes the modulus needed for NTT operation in forward 459 * Bluestein transform. 460 * @param cycloOrder is the cyclotomic order of the polynomial. 461 * @param modulus is the modulus of the polynomial. 462 */ 463 static void PreComputeDefaultNTTModulusRoot(usint cycloOrder, 464 const IntType& modulus); 465 466 /** 467 * @brief Precomputes the root of unity table needed for NTT operation in 468 * forward Bluestein transform. 469 * @param cycloOrder is the cyclotomic order of the polynomial ring. 470 * @param modulus is the modulus of the polynomial. 471 */ 472 static void PreComputeRootTableForNTT( 473 usint cycloOrder, const ModulusRoot<IntType>& nttModulusRoot); 474 475 /** 476 * @brief precomputes the powers of root used in forward Bluestein transform. 477 * @param cycloOrder is the cyclotomic order of the polynomial ring. 478 * @param modulus is the modulus of the polynomial ring. 479 * @param root is the root of unity s.t. root^2m = 1. 480 */ 481 static void PreComputePowers(usint cycloOrder, 482 const ModulusRoot<IntType>& modulusRoot); 483 484 /** 485 * @brief precomputes the NTT transform of the power of root of unity used in 486 * the Bluestein transform. 487 * @param cycloOrder is the cyclotomic order of the polynomial ring. 488 * @param modulus is the modulus of the polynomial ring. 489 * @param root is the root of unity s.t. root^2m = 1. 490 * @param bigMod is the modulus required for the NTT transform. 491 * @param bigRoot is the root of unity required for the NTT transform. 492 */ 493 static void PreComputeRBTable( 494 usint cycloOrder, const ModulusRootPair<IntType>& modulusRootPair); 495 496 /** 497 * Reset cached values for the transform to empty. 498 */ 499 static void Reset(); 500 501 // map to store the root of unity table with modulus as key. 502 static std::map<ModulusRoot<IntType>, VecType> 503 m_rootOfUnityTableByModulusRoot; 504 505 // map to store the root of unity inverse table with modulus as key. 506 static std::map<ModulusRoot<IntType>, VecType> 507 m_rootOfUnityInverseTableByModulusRoot; 508 509 // map to store the power of roots as a table with modulus + root of unity as 510 // key. 511 static std::map<ModulusRoot<IntType>, VecType> m_powersTableByModulusRoot; 512 513 // map to store the forward transform of power table with modulus + root of 514 // unity as key. 515 static std::map<ModulusRootPair<IntType>, VecType> m_RBTableByModulusRootPair; 516 517 private: 518 // map to store the precomputed NTT modulus with modulus as key. 519 static std::map<IntType, ModulusRoot<IntType>> m_defaultNTTModulusRoot; 520 }; 521 522 /** 523 * @brief Chinese Remainder Transform for arbitrary cyclotomics. 524 */ 525 template <typename VecType> 526 class ChineseRemainderTransformArb { 527 using IntType = typename VecType::Integer; 528 529 public: 530 /** 531 * Sets the cyclotomic polynomial. 532 * 533 */ 534 static void SetCylotomicPolynomial(const VecType& poly, const IntType& mod); 535 536 /** 537 * Forward transform. 538 * 539 * @param element is the element to perform the transform on. 540 * @param root is the 2mth root of unity w.r.t the ring modulus. 541 * @param cycloOrder is the cyclotomic order of the ring element. 542 * @param bigMod is the addtional modulus needed for NTT operation. 543 * @param bigRoot is the addtional root of unity w.r.t bigMod needed for NTT 544 * operation. 545 * @return is the output result of the transform. 546 */ 547 static VecType ForwardTransform(const VecType& element, const IntType& root, 548 const IntType& bigMod, const IntType& bigRoot, 549 const usint cycloOrder); 550 551 /** 552 * Inverse transform. 553 * 554 * @param element is the element to perform the transform on. 555 * @param root is the 2mth root of unity w.r.t the ring modulus. 556 * @param cycloOrder is the cyclotomic order of the ring element. 557 * @param bigMod is the addtional modulus needed for NTT operation. 558 * @param bigRoot is the addtional root of unity w.r.t bigMod needed for NTT 559 * operation. 560 * @return is the output result of the transform. 561 */ 562 static VecType InverseTransform(const VecType& element, const IntType& root, 563 const IntType& bigMod, const IntType& bigRoot, 564 const usint cycloOrder); 565 566 /** 567 * Reset cached values for the transform to empty. 568 */ 569 static void Reset(); 570 571 /** 572 * @brief Precomputes the root of unity and modulus needed for NTT operation 573 * in forward Bluestein transform. 574 * @param cycloOrder is the cyclotomic order of the polynomial ring. 575 * @param modulus is the modulus of the polynomial ring. 576 */ 577 static void PreCompute(const usint cyclotoOrder, const IntType& modulus); 578 579 /** 580 * @brief Sets the precomputed root of unity and modulus needed for NTT 581 * operation in forward Bluestein transform. 582 * @param cycloOrder is the cyclotomic order of the polynomial ring. 583 * @param modulus is the modulus of the polynomial ring. 584 * @param nttMod is the modulus needed for the NTT operation in forward 585 * Bluestein transform. 586 * @param nttRoot is the root of unity needed for the NTT operation in forward 587 * Bluestein transform. 588 */ 589 static void SetPreComputedNTTModulus(usint cyclotoOrder, 590 const IntType& modulus, 591 const IntType& nttMod, 592 const IntType& nttRoot); 593 594 /** 595 * @brief Sets the precomputed root of unity and modulus needed for NTT 596 * operation and computes m_cyclotomicPolyReveseNTTMap,m_cyclotomicPolyNTTMap. 597 * Always called after setting the cyclotomic polynomial. 598 * @param cycloOrder is the cyclotomic order of the polynomial ring. 599 * @param modulus is the modulus of the polynomial ring. 600 * @param nttMod is the modulus needed for the NTT operation in forward 601 * Bluestein transform. 602 * @param nttRoot is the root of unity needed for the NTT operation in forward 603 * Bluestein transform. 604 */ 605 static void SetPreComputedNTTDivisionModulus(usint cyclotoOrder, 606 const IntType& modulus, 607 const IntType& nttMod, 608 const IntType& nttRoot); 609 610 /** 611 * @brief Computes the inverse of the cyclotomic polynomial using 612 * Newton-Iteration method. 613 * @param cycloPoly is the cyclotomic polynomial. 614 * @param modulus is the modulus of the polynomial ring. 615 * @return inverse polynomial. 616 */ 617 static VecType InversePolyMod(const VecType& cycloPoly, 618 const IntType& modulus, usint power); 619 620 private: 621 /** 622 * @brief Padding zeroes to a vector 623 * @param &element is the input of type VecType to be padded with zeros. 624 * @param cycloOrder is the cyclotomic order of the ring 625 * @param forward is a flag for forward/inverse transform padding. 626 * @return is result vector with &element values with padded zeros to it 627 */ 628 static VecType Pad(const VecType& element, const usint cycloOrder, 629 bool forward); 630 631 /** 632 * @brief Dropping elements from a vector 633 * @param &element is the input of type VecType. 634 * @param cycloOrder is the cyclotomic order of the ring 635 * @param forward is a flag for forward/inverse transform dropping. 636 * @param &bigMod is a modulus used to precompute the root of unity tables if 637 * needed. The tables are used in the inverse dropping computations 638 * @param &bigRoot is a root of unity used to precompute the root of unity 639 * tables if needed. The tables are used in the inverse dropping computations 640 * @return is result vector with &element values with dropped elements from it 641 */ 642 static VecType Drop(const VecType& element, const usint cycloOrder, 643 bool forward, const IntType& bigMod, 644 const IntType& bigRoot); 645 646 // map to store the cyclotomic polynomial with polynomial ring's modulus as 647 // key. 648 static std::map<IntType, VecType> m_cyclotomicPolyMap; 649 650 // map to store the forward NTT transform of the inverse of cyclotomic 651 // polynomial with polynomial ring's modulus as key. 652 static std::map<IntType, VecType> m_cyclotomicPolyReverseNTTMap; 653 654 // map to store the forward NTT transform of the cyclotomic polynomial with 655 // polynomial ring's modulus as key. 656 static std::map<IntType, VecType> m_cyclotomicPolyNTTMap; 657 658 // map to store the root of unity table used in NTT based polynomial division. 659 static std::map<IntType, VecType> m_rootOfUnityDivisionTableByModulus; 660 661 // map to store the root of unity table for computing forward NTT of inverse 662 // cyclotomic polynomial used in NTT based polynomial division. 663 static std::map<IntType, VecType> m_rootOfUnityDivisionInverseTableByModulus; 664 665 // modulus used in NTT based polynomial division. 666 static std::map<IntType, IntType> m_DivisionNTTModulus; 667 668 // root of unity used in NTT based polynomial division. 669 static std::map<IntType, IntType> m_DivisionNTTRootOfUnity; 670 671 // dimension of the NTT transform in NTT based polynomial division. 672 static std::map<usint, usint> m_nttDivisionDim; 673 }; 674 } // namespace lbcrypto 675 676 #endif 677