1 /* Copyright (C) 2012-2020 IBM Corp. 2 * This program is Licensed under the Apache License, Version 2.0 3 * (the "License"); you may not use this file except in compliance 4 * with the License. You may obtain a copy of the License at 5 * http://www.apache.org/licenses/LICENSE-2.0 6 * Unless required by applicable law or agreed to in writing, software 7 * distributed under the License is distributed on an "AS IS" BASIS, 8 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 9 * See the License for the specific language governing permissions and 10 * limitations under the License. See accompanying LICENSE file. 11 */ 12 13 #ifndef HELIB_KEY_SWITCHING_H 14 #define HELIB_KEY_SWITCHING_H 15 /** 16 * @file keySwitching.h 17 * @brief - Declaration of key switching matrices 18 * @brief - Other key switching-related free functions 19 * 20 * Copyright IBM Corporation 2019 All rights reserved. 21 */ 22 23 #include <climits> 24 #include <helib/DoubleCRT.h> 25 #include <helib/Context.h> 26 #include <helib/Ctxt.h> 27 28 namespace helib { 29 30 /** 31 * @class KeySwitch 32 * @brief Key-switching matrices 33 * 34 * There are basically two approaches for how to do key-switching: either 35 * decompose the mod-q ciphertext into bits (or digits) to make it low-norm, 36 * or perform the key-switching operation mod Q>>q. The tradeoff is that when 37 * decomposing the (coefficients of the) ciphertext into t digits, we need to 38 * increase the size of the key-switching matrix by a factor of t (and the 39 * running time similarly grows). On the other hand if we do not decompose at 40 * all then we need to work modulo Q>q^2, which means that the bitsize of our 41 * largest modulus q0 more than doubles (and hence also the parameter m more 42 * than doubles). In general if we decompose into digits of size B then we 43 * need to work with Q>q*B.) 44 * 45 * The part of the spectrum where we expect to find the sweet spot is when 46 * we decompose the ciphertext into digits of size B=q0^{1/t} for some small 47 * constant t (maybe t=2,3 or so). This means that our largest modulus 48 * has to be Q>q0^{1+1/t}, which increases also the parameter m by a factor 49 * (1+1/t). It also means that for key-switching in the top levels we would 50 * break the ciphertext to t digits, hence the key-switching matrix will have 51 * t columns. 52 * 53 * A key-switch matrix W[s'->s] converts a ciphertext-part with respect to 54 * secret-key polynomial s' into a canonical ciphertext (i.e. a two-part 55 * ciphertext with respect to (1,s)). The matrix W is a 2-by-t matrix of 56 * DoubleCRT objects. The bottom row are just (pseudo)random elements. Then 57 * for column j, if the bottom element is aj then the top element is set as 58 * bj = P*Bj*s' + p*ej - s * aj mod P*q0, 59 * where p is the plaintext space (i.e. 2 or 2^r, or 1 for CKKS) and Bj 60 * is the product of the digits-sizes corresponding to columns 0...i-1. 61 * (For example if we have digit sizes 3,5,7 then B0=1, B1=3, B2=15 and 62 * B3=105.) Also, q0 is the product of all the "ciphertext primes" and 63 * P is roughly the product of all the special primes. (Actually, for BGV, 64 * if Q is the product of all the special primes then P=Q*(Q^{-1} mod p).) 65 * 66 * In this implementation we save some space, by keeping only a PRG seed for 67 * generating the pseudo-random elements, rather than the elements themselves. 68 * 69 * To convert a ciphertext part R, we break R into digits R = sum_j Bj Rj, 70 * then set (q0,q1)^T = sum_j Rj * column-j. Note that we have 71 * <(1,s),(q0,q1)> = sum_j Rj*(s*aj - s*aj + p*ej +P*Bj*s') 72 * = P * sum_j Bj*Rj * s' + p sum_j Rj*ej 73 * = P * R * s' + p*a-small-element (mod P*q0) 74 * where the last element is small since the ej's are small and |Rj|<B. 75 * Note that if the ciphertext is encrypted relative to plaintext space p' 76 * and then key-switched with matrices W relative to plaintext space p, 77 * then we get a mew ciphertext with noise p'*small+p*small, so it is valid 78 * relative to plaintext space GCD(p',p). 79 * 80 * The matrix W is defined modulo Q>t*B*sigma*q0 (with sigma a bound on the 81 * size of the ej's), and Q is the product of all the small primes in our 82 * moduli chain. However, if p is much smaller than B then is is enough to 83 * use W mod Qi with Qi a smaller modulus, Q>p*sigma*q0. Also note that if 84 * p<Br then we will be using only first r columns of the matrix W. 85 ********************************************************************/ 86 class KeySwitch 87 { 88 public: 89 SKHandle fromKey; // A handle for the key s' 90 long toKeyID; // Index of the key s that we are switching into 91 long ptxtSpace; // either p or p^r 92 93 std::vector<DoubleCRT> b; // The top row, consisting of the bi's 94 NTL::ZZ prgSeed; // a seed to generate the random ai's in the bottom row 95 NTL::xdouble noiseBound; // high probability bound on noise magnitude 96 // in each column 97 98 explicit KeySwitch(long sPow = 0, 99 long xPow = 0, 100 long fromID = 0, 101 long toID = 0, 102 long p = 0); 103 explicit KeySwitch(const SKHandle& _fromKey, 104 long fromID = 0, 105 long toID = 0, 106 long p = 0); 107 108 bool operator==(const KeySwitch& other) const; 109 bool operator!=(const KeySwitch& other) const; 110 111 unsigned long NumCols() const; 112 113 //! @brief returns a dummy static matrix with toKeyId == -1 114 static const KeySwitch& dummy(); 115 bool isDummy() const; 116 117 //! A debugging method 118 void verify(SecKey& sk); 119 120 //! @brief Read a key-switching matrix from input 121 void readMatrix(std::istream& str, const Context& context); 122 123 //! Raw IO 124 void read(std::istream& str, const Context& context); 125 void write(std::ostream& str) const; 126 }; 127 std::ostream& operator<<(std::ostream& str, const KeySwitch& matrix); 128 // We DO NOT have std::istream& operator>>(std::istream& str, KeySwitch& 129 // matrix); instead must use the readMatrix method above, where you can specify 130 // context 131 132 //! @name Strategies for generating key-switching matrices 133 //! These functions are implemented in KeySwitching.cpp 134 135 //! @brief Constant defining threshold above which a baby-set/giant-step 136 //! strategy is used 137 #define HELIB_KEYSWITCH_THRESH (50) 138 139 //! @brief Constant defining threshold above which a single 140 //! giant step matrix is added even in HELIB_KSS_MIN mode. 141 //! This helps in the matmul routines. 142 #define HELIB_KEYSWITCH_MIN_THRESH (8) 143 144 //! @brief Function that returns number of baby steps. Used to keep 145 //! this and matmul routines "in sync". 146 long KSGiantStepSize(long D); 147 148 //! @brief Maximalistic approach: 149 //! generate matrices s(X^e)->s(X) for all e in Zm* 150 void addAllMatrices(SecKey& sKey, long keyID = 0); 151 152 //! @brief Generate matrices so every s(X^e) can be reLinearized 153 //! in at most two steps 154 void addFewMatrices(SecKey& sKey, long keyID = 0); 155 156 //! @brief Generate some matrices of the form s(X^{g^i})->s(X), but not all. 157 //! For a generator g whose order is larger than bound, generate only enough 158 //! matrices for the giant-step/baby-step procedures (2*sqrt(ord(g))of them). 159 void addSome1DMatrices(SecKey& sKey, 160 long bound = HELIB_KEYSWITCH_THRESH, 161 long keyID = 0); 162 163 //! @brief Generate all matrices s(X^{g^i})->s(X) for generators g of 164 //! Zm* /(p) and i<ord(g). If g has different orders in Zm* and Zm* /(p) 165 //! then generate also matrices of the form s(X^{g^{-i}})->s(X) 166 void add1DMatrices(SecKey& sKey, long keyID = 0); 167 168 void addBSGS1DMatrices(SecKey& sKey, long keyID = 0); 169 170 //! Generate all/some Frobenius matrices of the form s(X^{p^i})->s(X) 171 void addSomeFrbMatrices(SecKey& sKey, 172 long bound = HELIB_KEYSWITCH_THRESH, 173 long keyID = 0); 174 175 void addFrbMatrices(SecKey& sKey, long keyID = 0); 176 177 void addBSGSFrbMatrices(SecKey& sKey, long keyID = 0); 178 179 //! These routines just add a single matrix (or two, for bad dimensions) 180 void addMinimal1DMatrices(SecKey& sKey, long keyID = 0); 181 void addMinimalFrbMatrices(SecKey& sKey, long keyID = 0); 182 183 //! Generate all key-switching matrices for a given permutation network 184 class PermNetwork; 185 void addMatrices4Network(SecKey& sKey, const PermNetwork& net, long keyID = 0); 186 187 //! Generate specific key-switching matrices, described by the given set 188 void addTheseMatrices(SecKey& sKey, 189 const std::set<long>& automVals, 190 long keyID = 0); 191 192 } // namespace helib 193 194 #endif // HELIB_KEY_SWITCHING_H 195