HElib  1.0
Implementing Homomorphic Encryption
 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 
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>
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_