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 * @file keySwitching.cpp
14 * @brief A few strategies for generating key-switching matrices
15 *
16 * Copyright IBM Corporation 2012 All rights reserved.
17 */
18 #include <unordered_set>
19 #include <NTL/ZZ.h>
20 #include <helib/permutations.h>
21
22 #include <helib/binio.h>
23 #include <helib/keySwitching.h>
24 #include <helib/keys.h>
25 #include <helib/apiAttributes.h>
26 #include <helib/log.h>
27
28 namespace helib {
29
30 /******************** KeySwitch implementation **********************/
31 /********************************************************************/
32
KeySwitch(long sPow,long xPow,long fromID,long toID,long p)33 KeySwitch::KeySwitch(long sPow, long xPow, long fromID, long toID, long p) :
34 fromKey(sPow, xPow, fromID), toKeyID(toID), ptxtSpace(p)
35 {}
36
KeySwitch(const SKHandle & _fromKey,UNUSED long fromID,long toID,long p)37 KeySwitch::KeySwitch(const SKHandle& _fromKey,
38 UNUSED long fromID,
39 long toID,
40 long p) :
41 fromKey(_fromKey), toKeyID(toID), ptxtSpace(p)
42 {}
43
operator ==(const KeySwitch & other) const44 bool KeySwitch::operator==(const KeySwitch& other) const
45 {
46 if (this == &other)
47 return true;
48
49 if (fromKey != other.fromKey)
50 return false;
51 if (toKeyID != other.toKeyID)
52 return false;
53 if (ptxtSpace != other.ptxtSpace)
54 return false;
55
56 if (prgSeed != other.prgSeed)
57 return false;
58
59 if (b.size() != other.b.size())
60 return false;
61 for (size_t i = 0; i < b.size(); i++)
62 if (b[i] != other.b[i])
63 return false;
64
65 return true;
66 }
operator !=(const KeySwitch & other) const67 bool KeySwitch::operator!=(const KeySwitch& other) const
68 {
69 return !(*this == other);
70 }
71
NumCols() const72 unsigned long KeySwitch::NumCols() const { return b.size(); }
73
isDummy() const74 bool KeySwitch::isDummy() const { return (toKeyID == -1); }
75
verify(SecKey & sk)76 void KeySwitch::verify(SecKey& sk)
77 {
78 long fromSPower = fromKey.getPowerOfS();
79 long fromXPower = fromKey.getPowerOfX();
80 long fromIdx = fromKey.getSecretKeyID();
81 long toIdx = toKeyID;
82 long p = ptxtSpace;
83 long n = b.size();
84
85 std::cout << "KeySwitch::verify\n";
86 std::cout << "fromS = " << fromSPower << " fromX = " << fromXPower
87 << " fromIdx = " << fromIdx << " toIdx = " << toIdx << " p = " << p
88 << " n = " << n << "\n";
89
90 if (fromSPower != 1 || fromXPower != 1 || (fromIdx == toIdx) || n == 0) {
91 std::cout << "KeySwitch::verify: these parameters not checkable\n";
92 return;
93 }
94
95 const Context& context = b[0].getContext();
96
97 // we don't store the context in the ks matrix, so let's
98 // check that they are consistent
99
100 for (long i = 0; i < n; i++) {
101 if (&context != &(b[i].getContext()))
102 std::cout << "KeySwitch::verify: bad context " << i << "\n";
103 }
104
105 std::cout << "context.ctxtPrimes = " << context.ctxtPrimes << "\n";
106 std::cout << "context.specialPrimes = " << context.specialPrimes << "\n";
107 IndexSet fullPrimes = context.fullPrimes(); // ctxtPrimes | specialPrimes;
108
109 std::cout << "digits: ";
110 for (long i = 0; i < n; i++)
111 std::cout << context.digits[i] << " ";
112 std::cout << "\n";
113
114 std::cout << "IndexSets of b: ";
115 for (long i = 0; i < n; i++)
116 std::cout << b[i].getMap().getIndexSet() << " ";
117 std::cout << "\n";
118
119 // VJS: suspicious shadowing of fromKey, toKey
120 const DoubleCRT& _fromKey = sk.sKeys.at(fromIdx);
121 const DoubleCRT& _toKey = sk.sKeys.at(toIdx);
122
123 std::cout << "IndexSet of fromKey: " << _fromKey.getMap().getIndexSet()
124 << "\n";
125 std::cout << "IndexSet of toKey: " << _toKey.getMap().getIndexSet() << "\n";
126
127 std::vector<DoubleCRT> a;
128 a.resize(n, DoubleCRT(context, fullPrimes)); // defined modulo all primes
129
130 {
131 RandomState state;
132
133 SetSeed(prgSeed);
134 for (long i = 0; i < n; i++)
135 a[i].randomize();
136
137 } // the RandomState destructor "restores the state" (see NumbTh.h)
138
139 std::vector<NTL::ZZX> A, B;
140
141 A.resize(n);
142 B.resize(n);
143
144 for (long i = 0; i < n; i++) {
145 a[i].toPoly(A[i]);
146 b[i].toPoly(B[i]);
147 }
148
149 NTL::ZZX FromKey, ToKey;
150 _fromKey.toPoly(FromKey, fullPrimes);
151 _toKey.toPoly(ToKey, fullPrimes);
152
153 NTL::ZZ Q = context.productOfPrimes(fullPrimes);
154 NTL::ZZ prod = context.productOfPrimes(context.specialPrimes);
155 NTL::ZZX C, D;
156 NTL::ZZX PhimX = context.zMStar.getPhimX();
157
158 long nb = 0;
159 for (long i = 0; i < n; i++) {
160 C = (B[i] - FromKey * prod + ToKey * A[i]) % PhimX;
161 PolyRed(C, Q);
162 if (!divide(D, C, p)) {
163 std::cout << "*** not divisible by p at " << i << "\n";
164 } else {
165 for (long j = 0; j <= deg(D); j++)
166 if (NumBits(coeff(D, j)) > nb)
167 nb = NumBits(coeff(D, j));
168 }
169 prod *= context.productOfPrimes(context.digits[i]);
170 }
171
172 std::cout << "error ratio: " << ((double)nb) / ((double)NumBits(Q)) << "\n";
173 }
174
dummy()175 const KeySwitch& KeySwitch::dummy()
176 {
177 static const KeySwitch dummy(-1, -1, -1, -1);
178 return dummy;
179 }
180
operator <<(std::ostream & str,const KeySwitch & matrix)181 std::ostream& operator<<(std::ostream& str, const KeySwitch& matrix)
182 {
183 str << "[" << matrix.fromKey << " " << matrix.toKeyID << " "
184 << matrix.ptxtSpace << " " << matrix.b.size() << std::endl;
185 for (long i = 0; i < (long)matrix.b.size(); i++)
186 str << matrix.b[i] << std::endl;
187 str << matrix.prgSeed << " " << matrix.noiseBound << "]";
188 return str;
189 }
190
191 // Used in lieu of std::istream& operator>>(std::istream& str, KeySwitch&
192 // matrix)
readMatrix(std::istream & str,const Context & context)193 void KeySwitch::readMatrix(std::istream& str, const Context& context)
194 {
195 seekPastChar(str, '['); // defined in NumbTh.cpp
196 str >> fromKey;
197 str >> toKeyID;
198 str >> ptxtSpace;
199
200 long nDigits;
201 str >> nDigits;
202 b.resize(nDigits, DoubleCRT(context, IndexSet::emptySet()));
203 for (long i = 0; i < nDigits; i++)
204 str >> b[i];
205 str >> prgSeed;
206 str >> noiseBound;
207 seekPastChar(str, ']');
208 }
209
write(std::ostream & str) const210 void KeySwitch::write(std::ostream& str) const
211 {
212 writeEyeCatcher(str, BINIO_EYE_SKM_BEGIN);
213 /*
214 Write out raw
215 1. SKHandle fromKey;
216 2. long toKeyID;
217 3. long ptxtSpace;
218 4. vector<DoubleCRT> b;
219 5. ZZ prgSeed;
220 6. xdouble noiseBound;
221 */
222
223 fromKey.write(str);
224 write_raw_int(str, toKeyID);
225 write_raw_int(str, ptxtSpace);
226
227 write_raw_vector(str, b);
228
229 write_raw_ZZ(str, prgSeed);
230 write_raw_xdouble(str, noiseBound);
231
232 writeEyeCatcher(str, BINIO_EYE_SKM_END);
233 }
234
read(std::istream & str,const Context & context)235 void KeySwitch::read(std::istream& str, const Context& context)
236 {
237 int eyeCatcherFound = readEyeCatcher(str, BINIO_EYE_SKM_BEGIN);
238 assertEq(eyeCatcherFound, 0, "Could not find pre-secret key eyecatcher");
239
240 fromKey.read(str);
241 toKeyID = read_raw_int(str);
242 ptxtSpace = read_raw_int(str);
243 DoubleCRT blankDCRT(context, IndexSet::emptySet());
244 read_raw_vector(str, b, blankDCRT);
245 read_raw_ZZ(str, prgSeed);
246 noiseBound = read_raw_xdouble(str);
247
248 eyeCatcherFound = readEyeCatcher(str, BINIO_EYE_SKM_END);
249 assertEq(eyeCatcherFound, 0, "Could not find post-secret key eyecatcher");
250 }
251
KSGiantStepSize(long D)252 long KSGiantStepSize(long D)
253 {
254 assertTrue<InvalidArgument>(D > 0l, "Step size must be positive");
255 long g = NTL::SqrRoot(D);
256 if (g * g < D)
257 g++; // g = ceiling(sqrt(D))
258 return g;
259 }
260
261 // A maximalistic approach: generate matrices s(X^e)->s(X) for all e \in Zm*
addAllMatrices(SecKey & sKey,long keyID)262 void addAllMatrices(SecKey& sKey, long keyID)
263 {
264 const Context& context = sKey.getContext();
265 long m = context.zMStar.getM();
266
267 // key-switching matrices for the automorphisms
268 for (long i = 0; i < m; i++) {
269 if (!context.zMStar.inZmStar(i))
270 continue;
271 sKey.GenKeySWmatrix(1, i, keyID, keyID);
272 }
273 sKey.setKeySwitchMap(); // re-compute the key-switching map
274 }
275
276 // TODO: generate matrices s.t. you can reLinearize each s(X^e) in at most two
277 // steps void addFewMatrices(SecKey& sKey, long keyID)
278 // {
279 // throw LogicError("addFewMatrices not implemented yet");
280 // }
281
282 // This code block appears at least twice below
283 #define computeParams(context, m, i) \
284 bool native; \
285 long ord, gi, g2md; \
286 NTL::mulmod_precon_t g2mdminv; \
287 if (i == context.zMStar.numOfGens()) { /* Frobenius matrices */ \
288 ord = context.zMStar.getOrdP(); \
289 gi = context.zMStar.getP(); \
290 native = true; \
291 } else { /* one of the "regular" dimensions */ \
292 ord = context.zMStar.OrderOf(i); \
293 gi = context.zMStar.ZmStarGen(i); \
294 native = context.zMStar.SameOrd(i); \
295 if (!native) { \
296 g2md = PowerMod(gi, -ord, m); /* g^{-ord} mod m */ \
297 g2mdminv = PrepMulModPrecon(g2md, m); \
298 } \
299 } \
300 NTL::mulmod_precon_t giminv = PrepMulModPrecon(gi, m);
301
302 #if 0
303 static void add1Dmats4dim(SecKey& sKey, long i, long keyID)
304 {
305 const Context &context = sKey.getContext();
306 long m = context.zMStar.getM();
307 computeParams(context,m,i); // defines vars: native, ord, gi, g2md, giminv, g2mdminv
308
309 /* MAUTO std::vector<long> vals; */
310 for (long j=1,val=gi; j < ord; j++) {
311 // From s(X^val) to s(X)
312 sKey.GenKeySWmatrix(1, val, keyID, keyID);
313 if (!native) { // also from s(X^{g^{i-ord}}) to s(X)
314 long val2 = MulModPrecon(val,g2md,m,g2mdminv);
315 sKey.GenKeySWmatrix(1, val2, keyID, keyID);
316 /* MAUTO vals.push_back(val2); */
317 }
318 /* MAUTO vals.push_back(val); */
319 val = MulModPrecon(val, gi, m, giminv); // val *= g mod m (= g^{j+1})
320 }
321
322 if (!native) {
323 sKey.GenKeySWmatrix(1, context.zMStar.genToPow(i, -ord), keyID, keyID);
324 }
325
326
327 /* MAUTO
328 sKey.resetTree(i,keyID); // remove existing tree, if any
329 sKey.add2tree(i, 1, vals, keyID);
330 */
331 }
332 #else
333 // adds all matrices for dim i.
334 // i == -1 => Frobenius (NOTE: in matmul1D, i ==#gens means something else,
335 // so it is best to avoid that).
add1Dmats4dim(SecKey & sKey,long i,long keyID)336 static void add1Dmats4dim(SecKey& sKey, long i, long keyID)
337 {
338 const PAlgebra& zMStar = sKey.getContext().zMStar;
339 long ord;
340 bool native;
341
342 if (i != -1) {
343 ord = zMStar.OrderOf(i);
344 native = zMStar.SameOrd(i);
345 } else {
346 // Frobenius
347 ord = zMStar.getOrdP();
348 native = true;
349 }
350
351 for (long j = 1; j < ord; j++)
352 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, j), keyID, keyID);
353
354 if (!native)
355 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, -ord), keyID, keyID);
356
357 sKey.setKSStrategy(i, HELIB_KSS_FULL);
358 }
359
360 #endif
361
362 #if 0
363 static std::pair<long,long> computeSteps(long ord, long bound, bool native)
364 {
365 long baby,giant;
366 if (native) { // using giant+baby matrices
367 if (bound*bound >= 4*ord)
368 giant = ceil((bound - sqrt((double)bound*bound -4*ord))/2.0);
369 else
370 giant = sqrt((double)ord);
371 }
372 else { // using giant+2*baby matrices
373 if (bound*bound >= 8*ord)
374 giant = ceil((bound - sqrt((double)bound*bound -8*ord))/2.0);
375 else
376 giant = sqrt((double)ord);
377 }
378 baby = ord/giant;
379 if (baby*giant<ord) baby++;
380
381 //std::cerr << "*** giant steps = " << giant << "\n";
382 return std::pair<long,long>(baby,giant);
383 }
384
385 static void addSome1Dmats4dim(SecKey& sKey, long i, long bound, long keyID)
386 {
387 const Context &context = sKey.getContext();
388 long m = context.zMStar.getM();
389 computeParams(context,m,i); // defines vars: native, ord, gi, g2md, giminv, g2mdminv
390
391 long baby, giant;
392 std::tie(baby,giant) = computeSteps(ord, bound, native);
393
394 for (long j=1,val=gi; j<=baby; j++) { // Add matrices for baby steps
395 sKey.GenKeySWmatrix(1, val, keyID, keyID);
396 if (!native) {
397 long val2 = MulModPrecon(val,g2md,m,g2mdminv);
398 sKey.GenKeySWmatrix(1, val2, keyID, keyID);
399 }
400 val = MulModPrecon(val, gi, m, giminv); // val *= g mod m (= g^{j+1})
401 }
402
403 long gb = PowerMod(gi,baby,m); // g^baby
404 NTL::mulmod_precon_t gbminv = PrepMulModPrecon(gb, m);
405 for (long j=2,val=gb; j < giant; j++) { // Add matrices for giant steps
406 val = MulModPrecon(val, gb, m, gbminv); // val = g^{(j+1)*baby}
407 sKey.GenKeySWmatrix(1, val, keyID, keyID);
408 }
409
410 if (!native) {
411 sKey.GenKeySWmatrix(1, context.zMStar.genToPow(i, -ord), keyID, keyID);
412 }
413
414 // VJS: experimantal feature...because the replication code
415 // uses rotations by -1, -2, -4, -8, we add a few
416 // of these as well...only the small ones are important,
417 // and we only need them if SameOrd(i)...
418 // Note: we do indeed get a nontrivial speed-up
419
420 if (native && i<context.zMStar.numOfGens()) {
421 for (long k = 1; k < giant; k = 2*k) {
422 long j = ord - k;
423 long val = PowerMod(gi, j, m); // val = g^j
424 sKey.GenKeySWmatrix(1, val, keyID, keyID);
425 }
426 }
427
428 #if 0
429 MAUTO
430
431 // build the tree for this dimension, the internal nodes are 1 and
432 // (subset of) gi^{giant}, gi^{2*giant}, ..., gi^{baby*giant}. We
433
434 MAUTO sKey.resetTree(i,keyID); // remove existing tree, if any
435
436 // keep a list of all the elements that are covered by the tree so far,
437 // initialized to only the root (=1).
438 std::unordered_set<long> covered({1});
439
440 // Make a list of the automorphisms for this dimension
441 std::vector<long> autos;
442 for (long j=1,val=gi; j<ord; j++) {
443 // Do we have matrices for val and/or val/gi^{di}?
444 if (!native) {
445 long val2 = MulModPrecon(val, g2md, m, g2mdminv);
446 if (sKey.haveKeySWmatrix(1,val2,keyID,keyID)) {
447 autos.push_back(val2);
448 }
449 }
450 if (sKey.haveKeySWmatrix(1,val,keyID,keyID)) {
451 autos.push_back(val);
452 }
453 val = MulModPrecon(val, gi, m, giminv); // g^{j+1}
454 }
455
456 // Insert internal nodes and their children to tree
457 for (long j=0,fromVal=1; j<giant; j++) {
458 NTL::mulmod_precon_t fromminv = PrepMulModPrecon(fromVal, m);
459 std::vector<long> children;
460 for (long k: autos) {
461 long toVal = MulModPrecon(k, fromVal, m, fromminv);
462 if (covered.count(toVal)==0) { // toVal not covered yet
463 covered.insert(toVal);
464 children.push_back(toVal);
465 }
466 }
467 if (!children.empty()) { // insert fromVal with its children
468 sKey.add2tree(i, fromVal, children, keyID);
469 }
470 fromVal = MulModPrecon(fromVal, gb, m, gbminv); // g^{(j+1)*baby}
471 }
472
473 // Sanity-check, did we cover everything?
474 long toCover = native? ord: (2*ord-1);
475 if (covered.size()<toCover)
476 std::cerr << "**Warning: order-"<<ord<<" dimension, covered "<<covered.size()
477 << " of "<<toCover<<std::endl;
478 #endif
479 }
480
481 #else
482 // same as above, but uses BS/GS strategy
addSome1Dmats4dim(SecKey & sKey,long i,UNUSED long bound,long keyID)483 static void addSome1Dmats4dim(SecKey& sKey,
484 long i,
485 UNUSED long bound,
486 long keyID)
487 {
488 const PAlgebra& zMStar = sKey.getContext().zMStar;
489 long ord;
490 bool native;
491
492 if (i != -1) {
493 ord = zMStar.OrderOf(i);
494 native = zMStar.SameOrd(i);
495 } else {
496 // Frobenius
497 ord = zMStar.getOrdP();
498 native = true;
499 }
500
501 long g = KSGiantStepSize(ord);
502
503 // baby steps
504 for (long j = 1; j < g; j++)
505 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, j), keyID, keyID);
506
507 // giant steps
508 for (long j = g; j < ord; j += g)
509 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, j), keyID, keyID);
510
511 if (!native)
512 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, -ord), keyID, keyID);
513
514 sKey.setKSStrategy(i, HELIB_KSS_BSGS);
515
516 // NOTE: the old code also added matrices for ord-2^k for small k,
517 // in the case of (native && i<context.zMStar.numOfGens()).
518 // This supposedly speeds up the replication code, but for now
519 // we are leaving this out, for simplicity. Also, it is a waste
520 // of space for applications that don't use replication.
521 }
522
523 #endif
524
525 // generate only matrices of the form s(X^{g^i})->s(X), but not all of them.
526 // For a generator g whose order is larger than bound, generate only enough
527 // matrices for the giant-step/baby-step procedures (2*sqrt(ord(g))of them).
addSome1DMatrices(SecKey & sKey,long bound,long keyID)528 void addSome1DMatrices(SecKey& sKey, long bound, long keyID)
529 {
530 const Context& context = sKey.getContext();
531
532 // key-switching matrices for the automorphisms
533 for (long i : range(context.zMStar.numOfGens())) {
534 // For generators of small order, add all the powers
535 if (bound >= context.zMStar.OrderOf(i))
536 add1Dmats4dim(sKey, i, keyID);
537 else // For generators of large order, add only some of the powers
538 addSome1Dmats4dim(sKey, i, bound, keyID);
539 }
540 sKey.setKeySwitchMap(); // re-compute the key-switching map
541 }
542
add1DMatrices(SecKey & sKey,long keyID)543 void add1DMatrices(SecKey& sKey, long keyID)
544 {
545 addSome1DMatrices(sKey, LONG_MAX, keyID);
546 }
547
addBSGS1DMatrices(SecKey & sKey,long keyID)548 void addBSGS1DMatrices(SecKey& sKey, long keyID)
549 {
550 addSome1DMatrices(sKey, 0, keyID);
551 }
552
553 // Generate all Frobenius matrices of the form s(X^{p^i})->s(X)
addSomeFrbMatrices(SecKey & sKey,long bound,long keyID)554 void addSomeFrbMatrices(SecKey& sKey, long bound, long keyID)
555 {
556 const Context& context = sKey.getContext();
557 if (bound >= LONG(context.zMStar.getOrdP()))
558 add1Dmats4dim(sKey, -1, keyID);
559 else // For generators of large order, add only some of the powers
560 addSome1Dmats4dim(sKey, -1, bound, keyID);
561
562 sKey.setKeySwitchMap(); // re-compute the key-switching map
563 }
564
addFrbMatrices(SecKey & sKey,long keyID)565 void addFrbMatrices(SecKey& sKey, long keyID)
566 {
567 addSomeFrbMatrices(sKey, LONG_MAX, keyID);
568 }
569
addBSGSFrbMatrices(SecKey & sKey,long keyID)570 void addBSGSFrbMatrices(SecKey& sKey, long keyID)
571 {
572 addSomeFrbMatrices(sKey, 0, keyID);
573 }
574
addMinimal1Dmats4dim(SecKey & sKey,long i,long keyID)575 static void addMinimal1Dmats4dim(SecKey& sKey, long i, long keyID)
576 {
577 const PAlgebra& zMStar = sKey.getContext().zMStar;
578 long ord;
579 bool native;
580
581 if (i != -1) {
582 ord = zMStar.OrderOf(i);
583 native = zMStar.SameOrd(i);
584 } else {
585 // Frobenius
586 ord = zMStar.getOrdP();
587 native = true;
588 }
589
590 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, 1), keyID, keyID);
591
592 if (!native)
593 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, -ord), keyID, keyID);
594
595 if (ord > HELIB_KEYSWITCH_MIN_THRESH) {
596 long g = KSGiantStepSize(ord);
597 sKey.GenKeySWmatrix(1, zMStar.genToPow(i, g), keyID, keyID);
598 }
599
600 sKey.setKSStrategy(i, HELIB_KSS_MIN);
601 }
602
addMinimal1DMatrices(SecKey & sKey,long keyID)603 void addMinimal1DMatrices(SecKey& sKey, long keyID)
604 {
605 const Context& context = sKey.getContext();
606
607 // key-switching matrices for the automorphisms
608 for (long i : range(context.zMStar.numOfGens())) {
609 addMinimal1Dmats4dim(sKey, i, keyID);
610 }
611 sKey.setKeySwitchMap(); // re-compute the key-switching map
612 }
613
614 // Generate all Frobenius matrices of the form s(X^{p^i})->s(X)
addMinimalFrbMatrices(SecKey & sKey,long keyID)615 void addMinimalFrbMatrices(SecKey& sKey, long keyID)
616 {
617 addMinimal1Dmats4dim(sKey, -1, keyID);
618 sKey.setKeySwitchMap(); // re-compute the key-switching map
619 }
620
621 // Generate all key-switching matrices for a given permutation network
addMatrices4Network(SecKey & sKey,const PermNetwork & net,long keyID)622 void addMatrices4Network(SecKey& sKey, const PermNetwork& net, long keyID)
623 {
624 const Context& context = sKey.getContext();
625 long m = context.zMStar.getM();
626
627 for (long i = 0; i < net.depth(); i++) {
628 long e = net.getLayer(i).getE();
629 long gIdx = net.getLayer(i).getGenIdx();
630 long g = context.zMStar.ZmStarGen(gIdx);
631 long g2e = NTL::PowerMod(g, e, m); // g^e mod m
632 const NTL::Vec<long>& shamts = net.getLayer(i).getShifts();
633 for (long j = 0; j < shamts.length(); j++) {
634 if (shamts[j] == 0)
635 continue;
636 long val = NTL::PowerMod(g2e, shamts[j], m);
637 sKey.GenKeySWmatrix(1, val, keyID, keyID);
638 }
639 }
640 sKey.setKeySwitchMap(); // re-compute the key-switching map
641 }
642
addTheseMatrices(SecKey & sKey,const std::set<long> & automVals,long keyID)643 void addTheseMatrices(SecKey& sKey, const std::set<long>& automVals, long keyID)
644 {
645 std::set<long>::iterator it;
646 for (it = automVals.begin(); it != automVals.end(); ++it) {
647 long k = *it;
648 sKey.GenKeySWmatrix(1, k, keyID, keyID);
649 }
650 sKey.setKeySwitchMap(); // re-compute the key-switching map
651 }
652
653 } // namespace helib
654