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