HElib 1.0 Implementing Homomorphic Encryption

- Main Page
- Classes
- Files

- File List
- File Members

All Classes Files Functions Variables Friends Pages
PAlgebra.h
Go to the documentation of this file.
1 /* Copyright (C) 2012,2013 IBM Corp.
2 * This program is free software; you can redistribute it and/or modify
3 * it under the terms of the GNU General Public License as published by
4 * the Free Software Foundation; either version 2 of the License, or
5 * (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
10 * See the GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License along
13 * with this program; if not, write to the Free Software Foundation, Inc.,
14 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
15 */
16 #ifndef _PAlgebra_H_
17 #define _PAlgebra_H_
18
50 #include <vector>
51 #include <NTL/ZZX.h>
52 #include <NTL/GF2X.h>
53 #include <NTL/vec_GF2.h>
54 #include <NTL/GF2EX.h>
55 #include <NTL/lzz_pEX.h>
56 #include "cloned_ptr.h"
57 NTL_CLIENT
58
59 class PAlgebra {
60 unsigned m; // the integer m defines (Z/mZ)^*, Phi_m(X), etc.
61 unsigned p; // the prime base of the plaintext space
62
63 unsigned phiM; // phi(m)
64 unsigned ordP; // the order of p in (Z/mZ)^*
65 unsigned nSlots; // phi(m)/ordP = # of plaintext slots
66
67 vector<unsigned> gens; // Our generators for (Z/mZ)^* (other than p)
68 vector<long> ords; // ords[i] is the order of gens[i] in quotient group kept
69 // with a negative sign if different than order in (Z/mZ)*
70
71 ZZX PhimX; // Holds the integer polynomial Phi_m(X)
72 double cM; // the ring constant c_m for Z[X]/Phi_m(X)
73
74 vector<unsigned> T; // The representatives for the quotient group (Z/mZ)^*/(p)
75 vector<long> Tidx; // i=Tidx[t] is the index i s.t. T[i]=t.
76 // Tidx[t]==-1 if t notin T
77
78 vector<long> zmsIdx; // if t is the i'th element in (Z/mZ)* then zmsIdx[t]=i
79 // zmsIdx[t]==-1 if t notin (Z/mZ)*
80
81 vector<int> dLogT;
82 // holds the discrete-logarithms for elements in T: If (z/mZ)^*/(p)
83 // has n generators then dLogT is an array of n*nSlots interest, where
84 // the entries [in, in+1,...,(i+1)n-1] hold the discrete-logarithms for
85 // the i'th element of (z/mZ)^*/(p).
86 // Namely, for i<nSlots we have dLogT[in,...,(i+1)n-1] = [e1,...,en]
87 // s.t. T[i] = prod_{i=1}^n gi^{ei} mod m (with n=gens.size())
88
89 public:
90
91 PAlgebra(unsigned mm, unsigned pp = 2); // constructor
92
93 bool operator==(const PAlgebra& other) const;
94 bool operator!=(const PAlgebra& other) const {return !(*this==other);}
95 // comparison
96
97 /* I/O methods */
98
100 void printout() const;
101
102 /* Access methods */
103
105 unsigned getM() const { return m; }
106
108 unsigned getP() const { return p; }
109
111 unsigned getPhiM() const { return phiM; }
112
114 unsigned getOrdP() const { return ordP; }
115
117 unsigned getNSlots() const { return nSlots; }
118
120 const ZZX& getPhimX() const { return PhimX; }
121
123 unsigned numOfGens() const { return gens.size(); }
124
126 unsigned ZmStarGen(unsigned i) const
127 { return (i<gens.size())? gens[i] : 0; }
128
130 unsigned OrderOf(unsigned i) const
131 { return (i<ords.size())? abs(ords[i]) : 0; }
132
134 bool SameOrd(unsigned i) const
135 { return (i<ords.size())? (ords[i]>0) : false; }
136
138
140 unsigned ith_rep(unsigned i) const
141 { return (i<nSlots)? T[i]: 0; }
142
144 int indexOfRep(unsigned t) const
145 { return (t>0 && t<m)? Tidx[t]: -1; }
146
148 bool isRep(unsigned t) const
149 { return (t>0 && t<m && Tidx[t]>-1); }
150
152 int indexInZmstar(unsigned t) const
153 { return (t>0 && t<m)? zmsIdx[t]: -1; }
154
156 bool inZmStar(unsigned t) const
157 { return (t>0 && t<m && zmsIdx[t]>-1); }
158
161 long coordinate(long i, long k) const;
162
165 unsigned exponentiate(const vector<unsigned>& exps,
166 bool onlySameOrd=false) const;
167
169 const int* dLog(unsigned t) const {
170 int i = indexOfRep(t);
171 if (i<0) return NULL;
172 return &(dLogT[i*gens.size()]); // bug: this should be an iterator
173 }
174
175 /* Miscellaneous */
176
179 unsigned qGrpOrd(bool onlySameOrd=false) const {
180 if (gens.size()<=0) return 1;
181 unsigned ord = 1;
182 for (unsigned i=0; i<ords.size(); i++)
183 if (!onlySameOrd || SameOrd(i)) ord *= abs(ords[i]);
184 return ord;
185 }
186
190 bool nextExpVector(vector<unsigned>& exps) const;
191 };
192
193
194 enum PA_tag { PA_GF2_tag, PA_zz_p_tag };
195
223
224 class DummyBak {
225 // placeholder class used in GF2X impl
226
227 public:
228 void save() {}
229 void restore() const {}
230 };
231
232 class DummyContext {
233 // placeholder class used in GF2X impl
234
235 public:
236 void save() {}
237 void restore() const {}
238 DummyContext() {}
239 DummyContext(long) {}
240 };
241
242 class PA_GF2 {
243 // typedefs for algebraic structires built up from GF2
244
245 public:
246 static const PA_tag tag = PA_GF2_tag;
247 typedef GF2X RX;
248 typedef vec_GF2X vec_RX;
249 typedef GF2XModulus RXModulus;
250 typedef DummyBak RBak;
251 typedef DummyContext RContext;
252 typedef GF2E RE;
253 typedef vec_GF2E vec_RE;
254 typedef GF2EX REX;
255 typedef GF2EBak REBak;
256 typedef vec_GF2EX vec_REX;
257 typedef GF2EContext REContext;
258 };
259
260
261 class PA_zz_p {
262 // typedefs for algebraic structires built up from zz_p
263
264 public:
265 static const PA_tag tag = PA_zz_p_tag;
266 typedef zz_pX RX;
267 typedef vec_zz_pX vec_RX;
268 typedef zz_pXModulus RXModulus;
269 typedef zz_pBak RBak;
270 typedef zz_pContext RContext;
271 typedef zz_pE RE;
272 typedef vec_zz_pE vec_RE;
273 typedef zz_pEX REX;
274 typedef zz_pEBak REBak;
275 typedef vec_zz_pEX vec_REX;
276 typedef zz_pEContext REContext;
277 };
279
280
282 class PAlgebraModBase {
283
284 public:
285
286 virtual ~PAlgebraModBase() {}
287 virtual PAlgebraModBase* clone() const = 0;
288
290 virtual PA_tag getTag() const = 0;
291
293 virtual const PAlgebra& getZMStar() const = 0;
294
296 virtual const vector<ZZX>& getFactorsOverZZ() const = 0;
297
299 virtual long getR() const = 0;
300
302 virtual long getPPowR() const = 0;
303
305 virtual void restoreContext() const = 0;
306
318 virtual void genMaskTable() const = 0;
319 };
320
321 #ifndef DOXYGEN_IGNORE
322 #define PA_INJECT(typ)\
323 static const PA_tag tag = typ::tag; \
324 typedef typename typ::RX RX; \
325 typedef typename typ::vec_RX vec_RX; \
326 typedef typename typ::RXModulus RXModulus; \
327 typedef typename typ::RBak RBak; \
328 typedef typename typ::RContext RContext; \
329 typedef typename typ::RE RE; \
330 typedef typename typ::vec_RE vec_RE; \
331 typedef typename typ::REX REX; \
332 typedef typename typ::REBak REBak; \
333 typedef typename typ::vec_REX vec_REX; \
334 typedef typename typ::REContext REContext; \
335
336 #endif
337
338 template<class type> class PAlgebraModDerived;
339 // forward declaration
340
342 template<class type> class MappingData {
343
344 public:
345 PA_INJECT(type)
346
347 friend class PAlgebraModDerived<type>;
348
349 private:
350 RX G; // the polynomial defining the field extension
351 long degG; // the degree of the polynomial
352
353 /* the remaining fields are visible only to PAlgebraModDerived */
354
355 vector<RX> maps;
356 REContext contextForG;
357 vector<REX> rmaps;
358
359 public:
360 const RX& getG() const { return G; }
361 long getDegG() const { return degG; }
362 };
363
365 template<class type> class PAlgebraModDerived : public PAlgebraModBase {
366 public:
367 PA_INJECT(type)
368
369 private:
370 const PAlgebra& zMStar;
371 long r;
372 long pPowR;
373 RContext pPowRContext;
374
375 RXModulus PhimXMod;
376
377 vec_RX factors;
378 vector<ZZX> factorsOverZZ;
379 vec_RX crtCoeffs;
380 vector< vector< RX > > maskTable;
381
382
383 public:
384
385 PAlgebraModDerived(const PAlgebra& zMStar, long r);
386
387 PAlgebraModDerived(const PAlgebraModDerived& other) // copy constructor
388 : zMStar(other.zMStar), r(other.r), pPowR(other.pPowR),
389 pPowRContext(other.pPowRContext)
390 {
391 RBak bak; bak.save(); restoreContext();
392 PhimXMod = other.PhimXMod;
393 factors = other.factors;
394 maskTable = other.maskTable;
395 }
396
397 PAlgebraModDerived& operator=(const PAlgebraModDerived& other) // assignment
398 {
399 if (this == &other) return *this;
400
401 assert(&zMStar == &other.zMStar);
402 r = other.r;
403 pPowR = other.pPowR;
404 pPowRContext = other.pPowRContext;
405
406 RBak bak; bak.save(); restoreContext();
407 PhimXMod = other.PhimXMod;
408 factors = other.factors;
409 maskTable = other.maskTable;
410
411 return *this;
412 }
413
415 virtual PAlgebraModBase* clone() const { return new PAlgebraModDerived(*this); }
416
418 virtual PA_tag getTag() const { return tag; }
419
421 virtual const PAlgebra& getZMStar() const { return zMStar; }
422
424 virtual const vector<ZZX>& getFactorsOverZZ() const { return factorsOverZZ; }
425
427 virtual long getR() const { return r; }
428
430 virtual long getPPowR() const { return pPowR; }
431
433 virtual void restoreContext() const { pPowRContext.restore(); }
434
446 virtual void genMaskTable() const; // logically, but not really, const
447
448 /* In all of the following functions, it is expected that the caller
449 has already restored the relevant modulus (p^r), which
450 can be done by invoking the method restoreContext()
451 */
452
454 const RXModulus& getPhimXMod() const { return PhimXMod; }
455
457 const vec_RX& getFactors() const { return factors; }
458
462 const vec_RX& getCrtCoeffs() const { return crtCoeffs; }
463
464
477 const vector< vector< RX > >& getMaskTable() const // logically, but not really, const
478 {
479 if (maskTable.size() == 0)
480 genMaskTable();
481 return maskTable;
482 }
483
490
492 void CRT_decompose(vector<RX>& crt, const RX& H) const;
493
496 void CRT_reconstruct(RX& H, vector<RX>& crt) const;
497
501 void mapToSlots(MappingData<type>& mappingData, const RX& G) const;
502
509 void embedInAllSlots(RX& H, const RX& alpha,
510 const MappingData<type>& mappingData) const;
511
518 void embedInSlots(RX& H, const vector<RX>& alphas,
519 const MappingData<type>& mappingData) const;
520
525 void decodePlaintext(vector<RX>& alphas, const RX& ptxt,
526 const MappingData<type>& mappingData) const;
527
536 void buildLinPolyCoeffs(vector<RX>& C, const vector<RX>& L,
537 const MappingData<type>& mappingData) const;
539 private:
540 /* internal functions, not for public consumption */
541
542 static void SetModulus(long p) {
543 RContext context(p);
544 context.restore();
545 }
546
548 void mapToF1(RX& w, const RX& G) const { mapToFt(w,G,1); }
549
552 void mapToFt(RX& w, const RX& G, unsigned t, const RX* rF1=NULL) const;
553 };
554
556 PAlgebraModBase *buildPAlgebraMod(const PAlgebra& zMStar, long r);
557
558 // A simple wrapper for a pointer to an object of type PAlgebraModBase.
559 //
560 // Direct access to the virtual methods of PAlgebraModBase is provided,
561 // along with a "downcast" operator to get a reference to the object
562 // as a derived type, and == and != operators.
563 class PAlgebraMod {
564
565 private:
566 cloned_ptr<PAlgebraModBase> rep;
567
568 public:
569 // copy constructor: default
570 // assignment: default
571 // destructor: default
572 // NOTE: the use of cloned_ptr ensures that the default copy constructor,
573 // assignment operator, and destructor will work correctly.
574
575 explicit
576 PAlgebraMod(const PAlgebra& zMStar, long r)
577 : rep( buildPAlgebraMod(zMStar, r) )
578 { }
579 // constructor
580
583 template<class type>
584 const PAlgebraModDerived<type>& getDerived(type) const
585 { return dynamic_cast< const PAlgebraModDerived<type>& >( *rep ); }
586
587
588 bool operator==(const PAlgebraMod& other) const
589 {
590 return getZMStar() == getZMStar() && getR() == other.getR();
591 }
592 // comparison
593
594 bool operator!=(const PAlgebraMod& other) const
595 {
596 return !(*this == other);
597 }
598 // comparison
599
600 /* direct access to the PAlgebraModBase methods */
601
603 PA_tag getTag() const { return rep->getTag(); }
605 const PAlgebra& getZMStar() const { return rep->getZMStar(); }
607 const vector<ZZX>& getFactorsOverZZ() const { return rep->getFactorsOverZZ(); }
609 long getR() const { return rep->getR(); }
611 long getPPowR() const { return rep->getPPowR(); }
613 void restoreContext() const { rep->restoreContext(); }
614
626 void genMaskTable() const { rep->genMaskTable(); }
627 };
628
629 #endif // #ifdef _PAlgebra_H_