HElib 1.0 Implementing Homomorphic Encryption

- Main Page
- Classes
- Files

- File List
- File Members

All Classes Files Functions Variables Friends Pages
Ctxt.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 _Ctxt_H_
17 #define _Ctxt_H_
18
61 #include <vector>
62 #include <NTL/xdouble.h>
63 #include "DoubleCRT.h"
64
65 class KeySwitch;
66 class FHEPubKey;
67 class FHESecKey;
68
73 class SKHandle {
74 long powerOfS, powerOfX, secretKeyID;
75
76 public:
77 friend class Ctxt;
78
79 SKHandle(long newPowerOfS=0, long newPowerOfX=1, long newSecretKeyID=0)
80 {
81 powerOfS = newPowerOfS;
82 powerOfX = newPowerOfX;
83 secretKeyID = newSecretKeyID;
84 }
85
87 void setBase(long newSecretKeyID=-1)
88 {
89 powerOfS = 1;
90 powerOfX = 1;
91 if (newSecretKeyID >= 0) secretKeyID = newSecretKeyID;
92 }
93
95 bool isBase(long ofKeyID=0) const
96 {
97 // If ofKeyID<0, only check that this is base of some key,
98 // otherwise check that this is base of the given key
99 return powerOfS == 1 && powerOfX == 1 &&
100 (ofKeyID<0 || secretKeyID == ofKeyID);
101 }
102
104 void setOne(long newSecretKeyID=-1)
105 {
106 powerOfS = 0;
107 powerOfX = 1;
108 if (newSecretKeyID >= 0) secretKeyID = newSecretKeyID;
109 }
110
112 bool isOne() const
113 {
114 return powerOfS == 0;
115 }
116
117 bool operator==(const SKHandle& other) const
118 {
119 if (powerOfS==0 && other.powerOfS==0) return true;
120 return powerOfS==other.powerOfS &&
121 powerOfX==other.powerOfX &&
122 secretKeyID==other.secretKeyID;
123 }
124
125 bool operator!=(const SKHandle& other) const {return !(*this==other);}
126
127 /* access functions */
128
129 long getPowerOfS() const { return powerOfS; }
130 long getPowerOfX() const { return powerOfX; }
131 long getSecretKeyID() const { return secretKeyID; }
132
145 bool mul(const SKHandle& a, const SKHandle& b)
146 {
147 // If either of the inputs is one, the output equals to the other input
148 if (a.isOne()) {
149 *this = b;
150 return (b.secretKeyID >= 0);
151 }
152 if (b.isOne()) {
153 *this = a;
154 return (a.secretKeyID >= 0);
155 }
156
157 if (a.secretKeyID == -1 || b.secretKeyID == -1) {
158 secretKeyID = -1; // -1 will be used to indicate an "error state"
159 return false;
160 }
161
162 if (a.secretKeyID != b.secretKeyID) {
163 secretKeyID = -1;
164 return false;
165 }
166
167 if (a.powerOfX != b.powerOfX) {
168 secretKeyID = -1;
169 return false;
170 }
171
172 secretKeyID = a.secretKeyID;
173 powerOfX = a.powerOfX;
174 powerOfS = a.powerOfS + b.powerOfS;
175 return true;
176 }
177
178 friend istream& operator>>(istream& s, SKHandle& handle);
179 };
180 inline ostream& operator<<(ostream& s, const SKHandle& handle)
181 {
182 return s << "[" << handle.getPowerOfS() << " " << handle.getPowerOfX()
183 << " " << handle.getSecretKeyID() << "]";
184 }
185
193 class CtxtPart: public DoubleCRT {
194 public:
196 SKHandle skHandle; // The secret-key polynomial corresponding to this part
197
198 bool operator==(const CtxtPart& other) const;
199 bool operator!=(const CtxtPart& other) const {return !(*this==other);}
200
201 // Copy constructor from the base class
202
203 explicit
204 CtxtPart(const FHEcontext& _context): DoubleCRT(_context)
205 { skHandle.setOne(); }
206
207 CtxtPart(const FHEcontext& _context, const IndexSet& s):
208 DoubleCRT(_context,s) { skHandle.setOne(); }
209
210 CtxtPart(const FHEcontext& _context, const IndexSet& s,
211 const SKHandle& otherHandle):
212 DoubleCRT(_context,s), skHandle(otherHandle) {}
213
214 explicit
215 CtxtPart(const DoubleCRT& other): DoubleCRT(other) { skHandle.setOne(); }
216
217 CtxtPart(const DoubleCRT& other, const SKHandle& otherHandle):
218 DoubleCRT(other), skHandle(otherHandle) {}
219 };
220 istream& operator>>(istream& s, CtxtPart& p);
221 ostream& operator<<(ostream& s, const CtxtPart& p);
222
249 class Ctxt {
250 friend class FHEPubKey;
251 friend class FHESecKey;
252
253 const FHEcontext& context; // points to the parameters of this FHE instance
254 const FHEPubKey& pubKey; // points to the public encryption key;
255 vector<CtxtPart> parts; // the ciphertexe parts
256 IndexSet primeSet; // the primes relative to which the parts are defined
257 long ptxtSpace; // plaintext space for this ciphertext (either p or p^r)
258 xdouble noiseVar; // estimating the noise variance in this ciphertext
259
260 // Create a tensor product of c1,c2. It is assumed that *this,c1,c2
261 // are defined relative to the same set of primes and plaintext space,
262 // and that *this DOES NOT point to the same object as c1,c2
263 void tensorProduct(const Ctxt& c1, const Ctxt& c2);
264
265 // Add/subtract a ciphertext part to/from a ciphertext. These are private
266 // methods, they cannot update the noiseVar estimate so they must be called
267 // from a procedure that will eventually update that estimate.
268 Ctxt& operator-=(const CtxtPart& part) { subPart(part); return *this; }
269 Ctxt& operator+=(const CtxtPart& part) { addPart(part); return *this; }
270
271 // Procedureal versions with additional parameter
272 void subPart(const CtxtPart& part, bool matchPrimeSet=false)
273 { subPart(part, part.skHandle, matchPrimeSet); }
274 void addPart(const CtxtPart& part, bool matchPrimeSet=false)
275 { addPart(part, part.skHandle, matchPrimeSet); }
276
277 void subPart(const DoubleCRT& part,
278 const SKHandle& handle, bool matchPrimeSet=false)
279 { addPart(part, handle, matchPrimeSet, true); }
280 void addPart(const DoubleCRT& part, const SKHandle& handle,
281 bool matchPrimeSet=false, bool negative=false);
282
283 // Takes as arguments a ciphertext-part p relative to s' and a key-switching
284 // matrix W = W[s'->s], use W to switch p relative to (1,s), and add the
285 // result to *this.
286 void keySwitchPart(const CtxtPart& p, const KeySwitch& W);
287
288 long getPartIndexByHandle(const SKHandle& hanle) const {
289 for (size_t i=0; i<parts.size(); i++)
290 if (parts[i].skHandle==hanle) return i;
291 return -1;
292 }
293
294 public:
295 Ctxt(const FHEPubKey& newPubKey, long newPtxtSpace=2); // constructor
296 Ctxt& operator=(const Ctxt& other); // assignment
297
298 bool operator==(const Ctxt& other) const { return equalsTo(other); }
299 bool operator!=(const Ctxt& other) const { return !equalsTo(other); }
300
301 // a procedural variant with an additional parameter
302 bool equalsTo(const Ctxt& other, bool comparePkeys=true) const;
303
304 void clear() { // set as an empty ciphertext
305 primeSet.clear();
306 parts.clear();
307 noiseVar = to_xdouble(0.0);
308 }
309
310 // Encryption and decryption are done by the friends FHE[Pub|Sec]Key
311
314 void negate();
315
316 // Add/subtract aonther ciphertext
317 Ctxt& operator+=(const Ctxt& other) { addCtxt(other); return *this; }
318 Ctxt& operator-=(const Ctxt& other) { addCtxt(other,true); return *this; }
319 void addCtxt(const Ctxt& other, bool negative=false);
320
321 Ctxt& operator*=(const Ctxt& other); // Multiply by aonther ciphertext
322 void automorph(long k); // Apply automorphism F(X) -> F(X^k) (gcd(k,m)=1)
323 Ctxt& operator>>=(long k) { automorph(k); return *this; }
324
326 void smartAutomorph(long k);
327 // Apply F(X)->F(X^k) followed by re-liearization. The automorphism is
328 // possibly evaluated via a sequence of steps, to ensure that we can
329 // re-linearize the result of every step.
330
331 // Add a constant polynomial. If the size is not given, we use
332 // phi(m)*ptxtSpace^2 as the default value.
333 void addConstant(const DoubleCRT& dcrt, double size=0.0);
334 void addConstant(const ZZX& poly, double size=0.0)
335 { addConstant(DoubleCRT(poly,context,primeSet),size); }
336
337 // Multiply-by-constant. If the size is not given, we use
338 // phi(m)*ptxtSpace^2 as the default value.
339 void multByConstant(const DoubleCRT& dcrt, double size=0.0);
340 void multByConstant(const ZZX& poly, double size=0.0)
341 { multByConstant(DoubleCRT(poly,context,primeSet),size); }
342
343 // Higher-level multiply routines
344 void multiplyBy(const Ctxt& other);
345 void multiplyBy2(const Ctxt& other1, const Ctxt& other2);
346 void square() { multiplyBy(*this); }
347 void cube() { multiplyBy2(*this, *this); }
349
352 void reLinearize(long keyIdx=0);
353 // key-switch to (1,s_i), s_i is the base key with index keyIdx
354
356 xdouble modSwitchAddedNoiseVar() const;
357
361 void modUpToSet(const IndexSet &s);
362
366 void modDownToSet(const IndexSet &s);
367
371 void findBaseSet(IndexSet& s) const;
373
376
378 bool inCanonicalForm(long keyID=0) const {
379 return (parts.size()==2 &&
380 parts[0].skHandle.isOne() && parts[1].skHandle.isBase(keyID));
381 }
382
384 bool isCorrect() const {
385 ZZ q = context.productOfPrimes(primeSet);
386 return (to_xdouble(q) > sqrt(noiseVar)*2);
387 }
388 const FHEcontext& getContext() const { return context; }
389 const FHEPubKey& getPubKey() const { return pubKey; }
390 const IndexSet& getPrimeSet() const { return primeSet; }
391 const xdouble& getNoiseVar() const { return noiseVar; }
392 const long getPtxtSpace() const { return ptxtSpace;}
393 const long getKeyID() const;
394
396 const long getLevel() const {
397 IndexSet s;
398 findBaseSet(s);
399 return card(s);
400 }
401
403 double log_of_ratio() const
404 {return (log(getNoiseVar())/2 - context.logOfProduct(getPrimeSet()));}
406 friend istream& operator>>(istream& str, Ctxt& ctxt);
407 friend ostream& operator<<(ostream& str, const Ctxt& ctxt);
408 };
409
410 inline IndexSet baseSetOf(const Ctxt& c) {
411 IndexSet s; c.findBaseSet(s); return s;
412 }
413
414
415 // print to cerr some info about ciphertext
416 void CheckCtxt(const Ctxt& c, const char* label);
417
418 #endif // ifndef _Ctxt_H_