HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
AltCRT.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 _AltCRT_H_
17 #define _AltCRT_H_
18 
28 #include <vector>
29 #include <NTL/ZZX.h>
30 #include <NTL/lzz_pX.h>
31 #include "NumbTh.h"
32 #include "IndexMap.h"
33 #include "FHEContext.h"
34 NTL_CLIENT
35 class SingleCRT;
36 
43 class AltCRTHelper : public IndexMapInit<zz_pX> {
44 private:
45  long val;
46 
47 public:
48  AltCRTHelper(const FHEcontext& context) {
49  val = context.zMStar.getPhiM();
50  }
51 
53  virtual void init(zz_pX& v) {
54  v.rep.SetMaxLength(val);
55  }
56 
58  virtual IndexMapInit<zz_pX> * clone() const {
59  return new AltCRTHelper(*this);
60  }
61 private:
62  AltCRTHelper(); // disable default constructor
63 };
64 
65 
76 class AltCRT {
77  const FHEcontext& context;
78  IndexMap<zz_pX> map;
79 
80 
83  void verify();
84 
85  // Generic operators.
86  // The behavior when *this and other use different primes depends on the flag
87  // matchIndexSets. When it is set to true then the effective modulus is
88  // determined by the union of the two index sets; otherwise, the index set
89  // of *this.
90 
91  class AddFun {
92  public:
93  void apply(zz_pX& a, const zz_pX& b, const zz_pXModulus& f)
94  { return add(a, a, b); }
95 
96  void apply(zz_pX& a, zz_p b)
97  { return add(a, a, b); }
98  };
99 
100  class SubFun {
101  public:
102  void apply(zz_pX& a, const zz_pX& b, const zz_pXModulus& f)
103  { return sub(a, a, b); }
104 
105  void apply(zz_pX& a, zz_p b)
106  { return sub(a, a, b); }
107  };
108 
109  class MulFun {
110  public:
111  void apply(zz_pX& a, const zz_pX& b, const zz_pXModulus& f)
112  { return MulMod(a, a, b, f); }
113 
114  void apply(zz_pX& a, zz_p b)
115  { return mul(a, a, b); }
116  };
117 
118 
119  template<class Fun>
120  AltCRT& Op(const AltCRT &other, Fun fun,
121  bool matchIndexSets=true);
122 
123  template<class Fun>
124  AltCRT& Op(const ZZ &num, Fun fun);
125 
126  template<class Fun>
127  AltCRT& Op(const ZZX &poly, Fun fun);
128 
129  static bool dryRun; // do not actually perform any of the operations
130 
131 public:
132 
133  // Constructors and assignment operators
134 
135  // representing an integer polynomial as AltCRT. If the set of primes
136  // to use is not specified, the resulting object uses all the primes in
137  // the context. If the coefficients of poly are larger than the product of
138  // the used primes, they are effectively reduced modulo that product
139 
140  // copy constructor: default
141 
143  AltCRT(const ZZX&poly, const FHEcontext& _context);
144 
148  AltCRT(const ZZX&poly, const FHEcontext& _context, const IndexSet& indexSet);
149 
151  // (run-time error if active context is NULL)
152  // declared "explicit" to avoid implicit type conversion
153  explicit AltCRT(const ZZX&poly);
154 
156  // declared "explicit" to avoid implicit type conversion
157  explicit AltCRT(const FHEcontext &_context);
158 
160  AltCRT(const FHEcontext &_context, const IndexSet& indexSet);
161 
162 
163  // Assignment operator, the following two lines are equivalent:
164  // AltCRT dCRT(poly, context, indexSet);
165  // or
166  // AltCRT dCRT(context, indexSet); dCRT = poly;
167 
168  AltCRT& operator=(const AltCRT& other);
169  AltCRT& operator=(const SingleCRT& other);
170  AltCRT& operator=(const ZZX& poly);
171  AltCRT& operator=(const ZZ& num);
172  AltCRT& operator=(const long num) { *this = to_ZZ(num); return *this; }
173 
175  void toPoly(ZZX& p, bool positive=false) const;
176 
183  void toPoly(ZZX& p, const IndexSet& s, bool positive=false) const;
184 
185  // The variant toPolyMod has another argument, which is a modulus Q, and it
186  // computes toPoly() mod Q. This is offerred as a separate function in the
187  // hope that one day we will figure out a more efficient method of computing
188  // this. Right now it is not implemented
189  //
190  // void toPolyMod(ZZX& p, const ZZ &Q, const IndexSet& s) const;
191 
192 
193  bool operator==(const AltCRT& other) const {
194  assert(&context == &other.context);
195  return map == other.map;
196  }
197 
198  bool operator!=(const AltCRT& other) const {
199  return !(*this==other);
200  }
201 
202  // @brief Set to zero
203  AltCRT& SetZero() {
204  *this = ZZ::zero();
205  return *this;
206  }
207  // @brief Set to one
208  AltCRT& SetOne() {
209  *this = 1;
210  return *this;
211  }
212 
215  void breakIntoDigits(vector<AltCRT>& dgts, long n) const;
216 
219  void addPrimes(const IndexSet& s1);
220 
223  double addPrimesAndScale(const IndexSet& s1);
224 
226  void removePrimes(const IndexSet& s1) {
227  map.remove(s1);
228  }
229 
235 
236 
237  // Addition, negation, subtraction
238  AltCRT& Negate(const AltCRT& other);
239  AltCRT& Negate() { return Negate(*this); }
240 
241  AltCRT& operator+=(const AltCRT &other) {
242  return Op(other, AddFun());
243  }
244 
245  AltCRT& operator+=(const ZZX &poly) {
246  return Op(poly, AddFun());
247  }
248 
249  AltCRT& operator+=(const ZZ &num) {
250  return Op(num, AddFun());
251  }
252 
253  AltCRT& operator+=(long num) {
254  return Op(to_ZZ(num), AddFun());
255  }
256 
257  AltCRT& operator-=(const AltCRT &other) {
258  return Op(other,SubFun());
259  }
260 
261  AltCRT& operator-=(const ZZX &poly) {
262  return Op(poly,SubFun());
263  }
264 
265  AltCRT& operator-=(const ZZ &num) {
266  return Op(num, SubFun());
267  }
268 
269  AltCRT& operator-=(long num) {
270  return Op(to_ZZ(num), SubFun());
271  }
272 
273  // These are the prefix versions, ++dcrt and --dcrt.
274  AltCRT& operator++() { return (*this += 1); };
275  AltCRT& operator--() { return (*this -= 1); };
276 
277  // These are the postfix versions -- return type is void,
278  // so it is offered just for style...
279  void operator++(int) { *this += 1; };
280  void operator--(int) { *this -= 1; };
281 
282 
283  // Multiplication
284  AltCRT& operator*=(const AltCRT &other) {
285  return Op(other,MulFun());
286  }
287 
288  AltCRT& operator*=(const ZZX &poly) {
289  return Op(poly,MulFun());
290  }
291 
292  AltCRT& operator*=(const ZZ &num) {
293  return Op(num,MulFun());
294  }
295 
296  AltCRT& operator*=(long num) {
297  return Op(to_ZZ(num),MulFun());
298  }
299 
300 
301  // Procedural equivalents, supporting also the matchIndexSets flag
302  void Add(const AltCRT &other, bool matchIndexSets=true) {
303  Op(other, AddFun(), matchIndexSets);
304  }
305 
306  void Sub(const AltCRT &other, bool matchIndexSets=true) {
307  Op(other, SubFun(), matchIndexSets);
308  }
309 
310  void Mul(const AltCRT &other, bool matchIndexSets=true) {
311  Op(other, MulFun(), matchIndexSets);
312  }
313 
314  // Division by constant
315  AltCRT& operator/=(const ZZ &num);
316  AltCRT& operator/=(long num) { return (*this /= to_ZZ(num)); }
317 
318 
320  void Exp(long k);
321 
322 
323  // Apply the automorphism F(X) --> F(X^k) (with gcd(k,m)=1)
324  void automorph(long k);
325  AltCRT& operator>>=(long k) { automorph(k); return *this; }
327 
328  // Utilities
329 
330  const FHEcontext& getContext() const { return context; }
331  const IndexMap<zz_pX>& getMap() const { return map; }
332  const IndexSet& getIndexSet() const { return map.getIndexSet(); }
333 
334  // Choose random AltCRT's, either at random or with small/Gaussian
335  // coefficients.
336 
338  void randomize(const ZZ* seed=NULL);
339 
341  void sampleSmall() {
342  ZZX poly;
343  ::sampleSmall(poly,context.zMStar.getPhiM()); // degree-(phi(m)-1) polynomial
344  *this = poly; // convert to AltCRT
345  }
346 
348  void sampleHWt(long Hwt) {
349  ZZX poly;
350  ::sampleHWt(poly,Hwt,context.zMStar.getPhiM());
351  *this = poly; // convert to AltCRT
352  }
353 
355  void sampleGaussian(double stdev=0.0) {
356  if (stdev==0.0) stdev=to_double(context.stdev);
357  ZZX poly;
358  ::sampleGaussian(poly, context.zMStar.getPhiM(), stdev);
359  *this = poly; // convert to AltCRT
360  }
361 
362 
364  // Restricted to the given index set, if specified
365  void toSingleCRT(SingleCRT& scrt, const IndexSet& s) const;
366  void toSingleCRT(SingleCRT& scrt) const;
367 
368  // used to implement modulus switching
369  void scaleDownToSet(const IndexSet& s, long ptxtSpace);
370 
371  // I/O: ONLY the matrix is outputted/recovered, not the moduli chain!! An
372  // error is raised on input if this is not consistent with the current chain
373 
374  friend ostream& operator<< (ostream &s, const AltCRT &d);
375  friend istream& operator>> (istream &s, AltCRT &d);
376 
381  static bool setDryRun(bool toWhat=true) { dryRun=toWhat; return dryRun; }
382 };
383 
384 
385 inline void conv(AltCRT &d, const ZZX &p) { d=p; }
386 
387 inline AltCRT to_AltCRT(const ZZX& p) {
388  return AltCRT(p);
389 }
390 
391 inline void conv(ZZX &p, const AltCRT &d) { d.toPoly(p); }
392 
393 inline ZZX to_ZZX(const AltCRT &d) { ZZX p; d.toPoly(p); return p; }
394 
395 inline void conv(AltCRT& d, const SingleCRT& s) { d=s; }
396 
397 
398 
399 
400 
401 #endif