HElib 1.0 Implementing Homomorphic Encryption

- Main Page
- Classes
- Files

- File List
- File Members

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