HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
DoubleCRT.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  */
21 #if 0 // change to #if 1 to get an alternative implementation
22 
23 #define DoubleCRT AltCRT
24 #include "AltCRT.h"
25 #else
26 #ifndef _DoubleCRT_H_
27 #define _DoubleCRT_H_
28 
29 #include <vector>
30 #include <NTL/ZZX.h>
31 #include <NTL/vec_vec_long.h>
32 #include "NumbTh.h"
33 #include "IndexMap.h"
34 #include "FHEContext.h"
35 NTL_CLIENT
36 
37 class SingleCRT;
38 
45 class DoubleCRTHelper : public IndexMapInit<vec_long> {
46 private:
47  long val;
48 
49 public:
50  DoubleCRTHelper(const FHEcontext& context) {
51  val = context.zMStar.getPhiM();
52  }
53 
55  virtual void init(vec_long& v) {
56  v.FixLength(val);
57  }
58 
60  virtual IndexMapInit<vec_long> * clone() const {
61  return new DoubleCRTHelper(*this);
62  }
63 private:
64  DoubleCRTHelper(); // disable default constructor
65 };
66 
67 
88 class DoubleCRT {
89  const FHEcontext& context; // the context
90  IndexMap<vec_long> map; // the data itself: if the i'th prime is in use then
91  // map[i] is the vector of evaluations wrt this prime
92 
95  void verify();
96 
97  // Generic operators.
98  // The behavior when *this and other use different primes depends on the flag
99  // matchIndexSets. When it is set to true then the effective modulus is
100  // determined by the union of the two index sets; otherwise, the index set
101  // of *this.
102 
103  class AddFun {
104  public:
105  long apply(long a, long b, long n) { return AddMod(a, b, n); }
106  };
107 
108  class SubFun {
109  public:
110  long apply(long a, long b, long n) { return SubMod(a, b, n); }
111  };
112 
113  class MulFun {
114  public:
115  long apply(long a, long b, long n) { return MulMod(a, b, n); }
116  };
117 
118 
119  template<class Fun>
120  DoubleCRT& Op(const DoubleCRT &other, Fun fun,
121  bool matchIndexSets=true);
122 
123  template<class Fun>
124  DoubleCRT& Op(const ZZ &num, Fun fun);
125 
126  template<class Fun>
127  DoubleCRT& 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 DoubleCRT. 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 
146  DoubleCRT(const ZZX&poly, const FHEcontext& _context, const IndexSet& indexSet);
147  DoubleCRT(const ZZX&poly, const FHEcontext& _context);
148 
150  // (run-time error if active context is NULL)
151  // declared "explicit" to avoid implicit type conversion
152  explicit DoubleCRT(const ZZX&poly);
153 
154  // Without specifying a ZZX, we get the zero polynomial
155  explicit DoubleCRT(const FHEcontext &_context);
156  // declare "explicit" to avoid implicit type conversion
157 
159  DoubleCRT(const FHEcontext &_context, const IndexSet& indexSet);
160 
161  // Assignment operator, the following two lines are equivalent:
162  // DoubleCRT dCRT(poly, context, indexSet);
163  // or
164  // DoubleCRT dCRT(context, indexSet); dCRT = poly;
165 
166  DoubleCRT& operator=(const DoubleCRT& other);
167 
168  // Copy only the primes in s \intersect other.getIndexSet()
169  // void partialCopy(const DoubleCRT& other, const IndexSet& s);
170 
171  DoubleCRT& operator=(const SingleCRT& other);
172  DoubleCRT& operator=(const ZZX& poly);
173  DoubleCRT& operator=(const ZZ& num);
174  DoubleCRT& operator=(const long num) { *this = to_ZZ(num); return *this; }
175 
182  void toPoly(ZZX& p, const IndexSet& s, bool positive=false) const;
183  void toPoly(ZZX& p, 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 DoubleCRT& other) const {
194  assert(&context == &other.context);
195  return map == other.map;
196  }
197 
198  bool operator!=(const DoubleCRT& other) const {
199  return !(*this==other);
200  }
201 
202  // @brief Set to zero
203  DoubleCRT& SetZero() {
204  *this = ZZ::zero();
205  return *this;
206  }
207 
208  // @brief Set to one
209  DoubleCRT& SetOne() {
210  *this = 1;
211  return *this;
212  }
213 
216  void breakIntoDigits(vector<DoubleCRT>& dgts, long n) const;
217 
220  void addPrimes(const IndexSet& s1);
221 
224  double addPrimesAndScale(const IndexSet& s1);
225 
227  void removePrimes(const IndexSet& s1) {
228  map.remove(s1);
229  }
230 
231 
237 
238 
239  // Addition, negation, subtraction
240  DoubleCRT& Negate(const DoubleCRT& other);
241  DoubleCRT& Negate() { return Negate(*this); }
242 
243  DoubleCRT& operator+=(const DoubleCRT &other) {
244  return Op(other, AddFun());
245  }
246 
247  DoubleCRT& operator+=(const ZZX &poly) {
248  return Op(poly, AddFun());
249  }
250 
251  DoubleCRT& operator+=(const ZZ &num) {
252  return Op(num, AddFun());
253  }
254 
255  DoubleCRT& operator+=(long num) {
256  return Op(to_ZZ(num), AddFun());
257  }
258 
259  DoubleCRT& operator-=(const DoubleCRT &other) {
260  return Op(other,SubFun());
261  }
262 
263  DoubleCRT& operator-=(const ZZX &poly) {
264  return Op(poly,SubFun());
265  }
266 
267  DoubleCRT& operator-=(const ZZ &num) {
268  return Op(num, SubFun());
269  }
270 
271  DoubleCRT& operator-=(long num) {
272  return Op(to_ZZ(num), SubFun());
273  }
274 
275  // These are the prefix versions, ++dcrt and --dcrt.
276  DoubleCRT& operator++() { return (*this += 1); };
277  DoubleCRT& operator--() { return (*this -= 1); };
278 
279  // These are the postfix versions -- return type is void,
280  // so it is offered just for style...
281  void operator++(int) { *this += 1; };
282  void operator--(int) { *this -= 1; };
283 
284 
285  // Multiplication
286  DoubleCRT& operator*=(const DoubleCRT &other) {
287  return Op(other,MulFun());
288  }
289 
290  DoubleCRT& operator*=(const ZZX &poly) {
291  return Op(poly,MulFun());
292  }
293 
294  DoubleCRT& operator*=(const ZZ &num) {
295  return Op(num,MulFun());
296  }
297 
298  DoubleCRT& operator*=(long num) {
299  return Op(to_ZZ(num),MulFun());
300  }
301 
302 
303  // Procedural equivalents, supporting also the matchIndexSets flag
304  void Add(const DoubleCRT &other, bool matchIndexSets=true) {
305  Op(other, AddFun(), matchIndexSets);
306  }
307 
308  void Sub(const DoubleCRT &other, bool matchIndexSets=true) {
309  Op(other, SubFun(), matchIndexSets);
310  }
311 
312  void Mul(const DoubleCRT &other, bool matchIndexSets=true) {
313  Op(other, MulFun(), matchIndexSets);
314  }
315 
316  // Division by constant
317  DoubleCRT& operator/=(const ZZ &num);
318  DoubleCRT& operator/=(long num) { return (*this /= to_ZZ(num)); }
319 
321  void Exp(long k);
322 
323  // Apply the automorphism F(X) --> F(X^k) (with gcd(k,m)=1)
324  void automorph(long k);
325  DoubleCRT& operator>>=(long k) { automorph(k); return *this; }
327 
328  // Utilities
329 
330  const FHEcontext& getContext() const { return context; }
331  const IndexMap<vec_long>& getMap() const { return map; }
332  const IndexSet& getIndexSet() const { return map.getIndexSet(); }
333 
334  // Choose random DoubleCRT'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 DoubleCRT
345  }
346 
348  void sampleHWt(long Hwt) {
349  ZZX poly;
350  ::sampleHWt(poly,Hwt,context.zMStar.getPhiM());
351  *this = poly; // convert to DoubleCRT
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 DoubleCRT
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 DoubleCRT &d);
375  friend istream& operator>> (istream &s, DoubleCRT &d);
376 
381  static bool setDryRun(bool toWhat=true) { dryRun=toWhat; return dryRun; }
382 };
383 
384 
385 
386 
387 inline void conv(DoubleCRT &d, const ZZX &p) { d=p; }
388 
389 inline DoubleCRT to_DoubleCRT(const ZZX& p) {
390  return DoubleCRT(p);
391 }
392 
393 inline void conv(ZZX &p, const DoubleCRT &d) { d.toPoly(p); }
394 
395 inline ZZX to_ZZX(const DoubleCRT &d) { ZZX p; d.toPoly(p); return p; }
396 
397 inline void conv(DoubleCRT& d, const SingleCRT& s) { d=s; }
398 
399 
400 #endif // #ifndef _DoubleCRT_H_
401 
402 #endif // DoubleCRT or AltCRT