HElib  1.0
Implementing Homomorphic Encryption
 All Classes Files Functions Variables Friends Pages
FHE.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 _FHE_H_
17 #define _FHE_H_
18 
22 #include <vector>
23 #include "NTL/ZZX.h"
24 #include "DoubleCRT.h"
25 #include "FHEContext.h"
26 #include "Ctxt.h"
27 
84 class KeySwitch {
85 public:
86  SKHandle fromKey; // A handle for the key s'
87  long toKeyID; // Index of the key s that we are switching into
88  long ptxtSpace; // either 2 or 2^r
89 
90  vector<DoubleCRT> b; // The top row, consisting of the bi's
91  ZZ prgSeed; // a seed to generate the random ai's in the bottom row
92  // NOTE: THIS USE OF THE NTL PRG IS NOT THREAD-SAFE
93 
94  explicit
95  KeySwitch(long sPow=0, long xPow=0, long fromID=0, long toID=0, long p=0):
96  fromKey(sPow,xPow,fromID),toKeyID(toID),ptxtSpace(p) {}
97  explicit
98  KeySwitch(const SKHandle& _fromKey, long fromID=0, long toID=0, long p=0):
99  fromKey(_fromKey),toKeyID(toID),ptxtSpace(p) {}
100 
101  bool operator==(const KeySwitch& other) const;
102  bool operator!=(const KeySwitch& other) const {return !(*this==other);}
103 
104  unsigned NumCols() const { return b.size(); }
105 
107  static const KeySwitch& dummy();
108 
110  void verify(FHESecKey& sk);
111 
113  void readMatrix(istream& str, const FHEcontext& context);
114 };
115 ostream& operator<<(ostream& str, const KeySwitch& matrix);
116 // We DO NOT have istream& operator>>(istream& str, KeySwitch& matrix);
117 // instead must use the readMatrix method above, where you can specify context
118 
119 
124 class FHEPubKey { // The public key
125  const FHEcontext& context; // The context
126 
130  Ctxt pubEncrKey;
131 
132  vector<long> skHwts; // The Hamming weight of the secret keys
133  vector<KeySwitch> keySwitching; // The key-switching matrices
134 
135  // The keySwitchMap structure contains pointers to key-switching matrices
136  // for re-linearizing automorphisms. The entry keySwitchMap[i][n] contains
137  // the index j such that keySwitching[j] is the first matrix one needs to
138  // use when re-linearizing s_i(X^n).
139  vector< vector<long> > keySwitchMap;
140 
141 public:
142  FHEPubKey(): // this constructor thorws run-time error if activeContext=NULL
143  context(*activeContext), pubEncrKey(*this) {}
144 
145  explicit
146  FHEPubKey(const FHEcontext& _context):
147  context(_context), pubEncrKey(*this) {}
148 
149  void clear() { // clear all public-key data
150  pubEncrKey.clear(); skHwts.clear();
151  keySwitching.clear(); keySwitchMap.clear();
152  }
153 
154  bool operator==(const FHEPubKey& other) const;
155  bool operator!=(const FHEPubKey& other) const {return !(*this==other);}
156 
157  // Access methods
158  const FHEcontext& getContext() const {return context;}
160  long getSKeyWeight(long keyID=0) const {return skHwts[keyID];}
161 
164 
167  const KeySwitch& getKeySWmatrix(const SKHandle& from, long toID=0) const;
168  const KeySwitch& getKeySWmatrix(long fromSPower, long fromXPower, long fromID=0, long toID=0) const
169  { return getKeySWmatrix(SKHandle(fromSPower,fromXPower,fromID), toID); }
170 
171  bool haveKeySWmatrix(const SKHandle& from, long toID=0) const
172  { return getKeySWmatrix(from,toID).toKeyID >= 0; }
173 
174  bool haveKeySWmatrix(long fromSPower, long fromXPower, long fromID=0, long toID=0) const
175  { return haveKeySWmatrix(SKHandle(fromSPower,fromXPower,fromID), toID); }
176 
178  const KeySwitch& getAnyKeySWmatrix(const SKHandle& from) const;
179  bool haveAnyKeySWmatrix(const SKHandle& from) const
180  { return getAnyKeySWmatrix(from).toKeyID >= 0; }
181 
184  const KeySwitch& getNextKSWmatrix(long fromXPower, long fromID=0) const
185  { long matIdx = keySwitchMap.at(fromID).at(fromXPower);
186  return (matIdx>=0? keySwitching.at(matIdx) : KeySwitch::dummy());
187  }
189 
192  bool isReachable(long k, long keyID=0) const
193  { return keySwitchMap.at(keyID).at(k)>=0; }
194 
197  void setKeySwitchMap(long keyId=0); // Computes the keySwitchMap pointers
198 
201  long Encrypt(Ctxt &ciphertxt, const ZZX& plaintxt, long ptxtSpace=0) const;
202 
203  friend class FHESecKey;
204  friend ostream& operator << (ostream& str, const FHEPubKey& pk);
205  friend istream& operator >> (istream& str, FHEPubKey& pk);
206 };
207 
212 class FHESecKey: public FHEPubKey { // The secret key
213 public:
214  vector<DoubleCRT> sKeys; // The secret key(s) themselves
215 
216 public:
217 
218  // Constructors just call the ones for the base class
219  FHESecKey(){}
220 
221  explicit
222  FHESecKey(const FHEcontext& _context): FHEPubKey(_context) {}
223 
224  bool operator==(const FHESecKey& other) const;
225  bool operator!=(const FHESecKey& other) const {return !(*this==other);}
226 
227  void clear() // clear all secret-key data
228  { FHEPubKey::clear(); sKeys.clear(); }
229 
236  long ImportSecKey(const DoubleCRT& sKey, long hwt, long ptxtSpace=0);
237 
240  long GenSecKey(long hwt, long ptxtSpace=0)
241  { DoubleCRT newSk(context); // defined relative to all primes, special or not
242  newSk.sampleHWt(hwt); // samle a Hamming-weight-hwt polynomial
243  return ImportSecKey(newSk, hwt, ptxtSpace);
244  }
245 
252  void GenKeySWmatrix(long fromSPower, long fromXPower, long fromKeyIdx=0,
253  long toKeyIdx=0, long ptxtSpace=0);
254 
255  // Decryption
256  void Decrypt(ZZX& plaintxt, const Ctxt &ciphertxt) const;
257 
260  void Decrypt(ZZX& plaintxt, const Ctxt &ciphertxt, ZZX& f) const;
261 
263  long Encrypt(Ctxt &ctxt, const ZZX& ptxt,
264  long ptxtSpace=0, long skIdx=0) const;
265 
266  friend ostream& operator << (ostream& str, const FHESecKey& sk);
267  friend istream& operator >> (istream& str, FHESecKey& sk);
268 };
269 
272 
275 void addAllMatrices(FHESecKey& sKey, long keyID=0);
276 
279 void addFewMatrices(FHESecKey& sKey, long keyID=0);
280 
284 void add1DMatrices(FHESecKey& sKey, long keyID=0);
285 
289 void addSome1DMatrices(FHESecKey& sKey, long bound=100, long keyID=0);
290 
292 void addFrbMatrices(FHESecKey& sKey, long keyID=0);
293 
294 #endif // ifndef _FHE_H_