1 /* Copyright (C) 2012-2019 IBM Corp.
2 * This program is Licensed under the Apache License, Version 2.0
3 * (the "License"); you may not use this file except in compliance
4 * with the License. You may obtain a copy of the License at
5 * http://www.apache.org/licenses/LICENSE-2.0
6 * Unless required by applicable law or agreed to in writing, software
7 * distributed under the License is distributed on an "AS IS" BASIS,
8 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
9 * See the License for the specific language governing permissions and
10 * limitations under the License. See accompanying LICENSE file.
11 */
12
13 /* Test_Permutations.cpp - Applying plaintext permutation to encrypted vector
14 */
15 #include <NTL/ZZ.h>
16 NTL_CLIENT
17
18 #include <helib/NumbTh.h>
19 #include <helib/timing.h>
20 #include <helib/permutations.h>
21 #include <helib/EncryptedArray.h>
22 #include <helib/ArgMap.h>
23
24 using namespace helib;
25
26 static bool noPrint = true;
27
28 void testCtxt(long m, long p, long widthBound=0, long L=0, long r=1);
29
30 // OLD CODE
31 //void usage(char *prog)
32 //{
33 // cout << "Usage: "<<prog<<" [test=? [optional parameters...]]\n";
34 // cout << " optional parameters have the form 'attr1=val1 attr2=val2 ...'\n";
35 // cout << " e.g, 'test=1 m=108 p=2 r=1\n";
36 // cout << " test is either 0 (plaintext) or 1 (ciphertext)[default=1]\n\n";
37 // cout << "test=0, permuting plaintext hypercubes (dimension upto 4):\n";
38 // cout << " ord1,ord2,ord3,ord4 size of dimensions 1..4 [default ord1=30, ord2,3,4=0]\n";
39 // cout << " good1,good2,good3,good4 native rotation flags (0/1) [default=1]\n";
40 // cout << " depth bounds the depth of permutation network [default=5]\n";
41 // cout << "\ntest=1, permuting ciphertext slots:\n";
42 // cout << " m is the cyclotomic field [default=4369]\n";
43 // cout << " p,r define the plaintext space p^r [default p=2,r=1]\n";
44 // cout << " depth bounds the depth of permutation network [default=5]\n";
45 // cout << " L is number of bits in chain [default=30*depth]\n\n";
46 // cout << "dry=1 for dry run [default=0]\n";
47 // exit(0);
48 //}
49
testCube(Vec<GenDescriptor> & vec,long widthBound)50 void testCube(Vec<GenDescriptor>& vec, long widthBound)
51 {
52 GeneratorTrees trees;
53 long cost = trees.buildOptimalTrees(vec, widthBound);
54 if (!noPrint) {
55 cout << "@TestCube: trees=" << trees << endl;
56 cout << " cost =" << cost << endl;
57 }
58 Vec<long> dims;
59 trees.getCubeDims(dims);
60 CubeSignature sig(dims);
61
62 for (long cnt=0; cnt<3; cnt++) {
63 Permut pi;
64 randomPerm(pi, trees.getSize());
65
66 PermNetwork net;
67 net.buildNetwork(pi, trees);
68
69 HyperCube<long> cube1(sig), cube2(sig);
70 for (long i=0; i<cube1.getSize(); i++) cube1[i] = i;
71 HyperCube<long> cube3 = cube1;
72 applyPermToVec(cube2.getData(), cube1.getData(), pi); // direct application
73 net.applyToCube(cube3); // applying permutation netwrok
74 if (cube2==cube3) cout << "GOOD\n";
75 else {
76 cout << "BAD\n";
77 if (cube1.getSize()<100 && !noPrint) {
78 cout << "in="<<cube1.getData() << endl;
79 cout << "out1="<<cube2.getData()<<", out2="
80 << cube3.getData()<<endl<<endl;
81 }
82 }
83 }
84 }
85
testCtxt(long m,long p,long widthBound,long L,long r)86 void testCtxt(long m, long p, long widthBound, long L, long r)
87 {
88 if (!noPrint)
89 cout << "@testCtxt(m="<<m<<",p="<<p<<",depth="<<widthBound<< ",r="<<r<<")";
90
91 Context context(m,p,r);
92 EncryptedArray ea(context); // Use G(X)=X for this ea object
93
94 // Some arbitrary initial plaintext array
95 vector<long> in(ea.size());
96 for (long i=0; i<ea.size(); i++) in[i] = i % p;
97
98 // Setup generator-descriptors for the PAlgebra generators
99 Vec<GenDescriptor> vec(INIT_SIZE, ea.dimension());
100 for (long i=0; i<ea.dimension(); i++)
101 vec[i] = GenDescriptor(/*order=*/ea.sizeOfDimension(i),
102 /*good=*/ ea.nativeDimension(i), /*genIdx=*/i);
103
104 // Some default for the width-bound, if not provided
105 if (widthBound<=0) widthBound = 1+log2((double)ea.size());
106
107 // Get the generator-tree structures and the corresponding hypercube
108 GeneratorTrees trees;
109 long cost = trees.buildOptimalTrees(vec, widthBound);
110 if (!noPrint) {
111 context.zMStar.printout();
112 cout << ": trees=" << trees << endl;
113 cout << " cost =" << cost << endl;
114 }
115 // Vec<long> dims;
116 // trees.getCubeDims(dims);
117 // CubeSignature sig(dims);
118
119 // 1/2 prime per level should be more or less enough, here we use 1 per layer
120 if (L<=0) L = (1+trees.numLayers())*context.BPL();
121 buildModChain(context, /*nLevels=*/L, /*nDigits=*/3);
122 if (!noPrint) cout << "**Using "<<L<<" and "
123 << context.ctxtPrimes.card() << " Ctxt-primes\n";
124
125 // Generate a sk/pk pair
126 SecKey secretKey(context);
127 const PubKey& publicKey = secretKey;
128 secretKey.GenSecKey(); // A +-1/0 secret key
129 Ctxt ctxt(publicKey);
130
131 for (long cnt=0; cnt<3; cnt++) {
132 resetAllTimers();
133 // Choose a random permutation
134 Permut pi;
135 randomPerm(pi, trees.getSize());
136
137 // Build a permutation network for pi
138 PermNetwork net;
139 net.buildNetwork(pi, trees);
140
141 // make sure we have the key-switching matrices needed for this network
142 addMatrices4Network(secretKey, net);
143
144 // Apply the permutation pi to the plaintext
145 vector<long> out1(ea.size());
146 vector<long> out2(ea.size());
147 applyPermToVec(out1, in, pi); // direct application
148
149 // Encrypt plaintext array, then apply permutation network to ciphertext
150 ea.encrypt(ctxt, publicKey, in);
151 if (!noPrint)
152 cout << " ** applying permutation network to ciphertext... " << flush;
153 double t = GetTime();
154 net.applyToCtxt(ctxt, ea); // applying permutation netwrok
155 t = GetTime() -t;
156 if (!noPrint)
157 cout << "done in " << t << " seconds" << endl;
158 ea.decrypt(ctxt, secretKey, out2);
159
160 if (out1==out2) cout << "GOOD\n";
161 else {
162 cout << "************ BAD\n";
163 }
164 // printAllTimers();
165 }
166 }
167
168
169 /* m = 31, p = 2, phi(m) = 30
170 ord(p)=5
171 generator 6 has order (== Z_m^*) of 6
172 T = [1 6 5 30 25 26 ]
173
174 m = 61, p = 3, phi(m) = 60
175 ord(p)=10
176 generator 13 has order (== Z_m^*) of 3
177 generator 2 has order (!= Z_m^*) of 2
178 T = [1 2 13 26 47 33 ]
179
180 m = 683, p = 2, phi(m) = 682
181 ord(p)=22
182 generator 3 has order (== Z_m^*) of 31
183
184 m = 47127, p = 2, phi(m) = 30008
185 ord(p)=22
186 generator 5 has order (== Z_m^*) of 682
187 generator 13661 has order (== Z_m^*) of 2
188 */
189
main(int argc,char * argv[])190 int main(int argc, char *argv[])
191 {
192 long test = 1;
193 long p = 2;
194 long r = 1;
195 long m = 4369;
196 long depth = 5;
197 long L = 0;
198
199 long ord1 = 30;
200 long ord2 = 0;
201 long ord3 = 0;
202 long ord4 = 0;
203 long good1 = 1;
204 long good2 = 1;
205 long good3 = 1;
206 long good4 = 1;
207
208 bool dry = 0;
209 noPrint = 1;
210
211 ArgMap amap;
212 amap.arg("test", test);
213 amap.arg("p", p);
214 amap.arg("r", r);
215 amap.arg("m", m);
216 amap.arg("depth", depth);
217 amap.arg("L", L);
218 amap.arg("ord1", ord1);
219 amap.arg("ord2", ord2);
220 amap.arg("ord3", ord3);
221 amap.arg("ord4", ord4);
222 amap.arg("good1", good1);
223 amap.arg("good2", good2);
224 amap.arg("good3", good3);
225 amap.arg("good4", good4);
226 amap.arg("dry", dry);
227 amap.arg("noPrint", noPrint);
228 amap.parse(argc, argv);
229
230 // get parameters from the command line
231 //if (!parseArgs(argc, argv, argmap)) usage(argv[0]);
232
233 setDryRun(dry);
234 if (test==0 || dry!=0) {
235 Vec<GenDescriptor> vec;
236 long nGens;
237 if (ord2<=1) nGens=1;
238 else if (ord3<=1) nGens=2;
239 else if (ord4<=1) nGens=3;
240 else nGens=4;
241 vec.SetLength(nGens);
242
243 switch (nGens) {
244 case 4: vec[3] = GenDescriptor(ord4, good4, /*genIdx=*/3);
245 case 3: vec[2] = GenDescriptor(ord3, good3, /*genIdx=*/2);
246 case 2: vec[1] = GenDescriptor(ord2, good2, /*genIdx=*/1);
247 default: vec[0] = GenDescriptor(ord1, good1, /*genIdx=*/0);
248 }
249 if (!noPrint) {
250 cout << "***Testing ";
251 if (isDryRun()) cout << "(dry run) ";
252 for (long i=0; i<vec.length(); i++)
253 cout << "("<<vec[i].order<<","<<vec[i].good<<")";
254 cout << ", depth="<<depth<<"\n";
255 }
256 testCube(vec, depth);
257 }
258 else {
259 setTimersOn();
260 if (!noPrint)
261 cout << "***Testing m="<<m<<", p="<<p<<", depth="<<depth<< endl;
262 testCtxt(m,p,depth,L,r);
263 }
264 }
265
266
267
268 #if 0
269 cout << "***Testing m=31, p=2, width=3\n"; // (6 good)
270 testCtxt(/*m=*/31, /*p=*/2, /*width=*/3);
271
272 cout << "\n***Testing m=61, p=3, width=3\n"; // (3 good), (2, bad)
273 testCtxt(/*m=*/61, /*p=*/3, /*width=*/3);
274
275 cout << "\n***Testing m=683, p=2, width=5\n"; // (31, good)
276 testCtxt(/*m=*/683, /*p=*/2, /*width=*/5);
277
278 // cout << "\n***Testing m=47127, p=2, width=11\n"; // (682,good),(2,good)
279 // testCtxt(/*m=*/47127, /*p=*/2, /*width=*/11);
280
281 // Test 1: a single good small prime-order generator (3)
282 {
283 Vec<GenDescriptor> vec(INIT_SIZE, 1);
284 vec[0] = GenDescriptor(/*order=*/3, /*good=*/true, /*genIdx=*/0);
285 cout << "***Testing (3,good), width=1\n";
286 testCube(vec, /*width=*/1);
287 }
288
289 // Test 2: a single bad larger prime-order generator (31)
290 {
291 Vec<GenDescriptor> vec(INIT_SIZE, 1);
292 vec[0] = GenDescriptor(/*order=*/31, /*good=*/false, /*genIdx=*/0);
293 cout << "\n***Testing (31,bad), width=5\n";
294 testCube(vec, /*width=*/5);
295 }
296
297 // Test 3: two generators with small prime orders (2,3), both bad
298 {
299 Vec<GenDescriptor> vec(INIT_SIZE, 2);
300 vec[0] = GenDescriptor(/*order=*/2, /*good=*/false, /*genIdx=*/0);
301 vec[1] = GenDescriptor(/*order=*/3, /*good=*/false, /*genIdx=*/1);
302 cout << "\n***Testing [(2,bad),(3,bad)], width=3\n";
303 testCube(vec, /*width=*/3);
304 }
305
306 // Test 4: two generators with small prime orders (2,3), one good
307 {
308 Vec<GenDescriptor> vec(INIT_SIZE, 2);
309 vec[0] = GenDescriptor(/*order=*/3, /*good=*/true, /*genIdx=*/0);
310 vec[1] = GenDescriptor(/*order=*/2, /*good=*/false, /*genIdx=*/1);
311 cout << "\n***Testing [(3,good),(2,bad)], width=3\n";
312 testCube(vec, /*width=*/3);
313 }
314
315 // Test 5: a single good composite-order generator (6)
316 {
317 Vec<GenDescriptor> vec(INIT_SIZE, 1);
318 vec[0] = GenDescriptor(/*order=*/6, /*good=*/true, /*genIdx=*/0);
319 cout << "\n***Testing (6,good), width=3\n";
320 testCube(vec, /*width=*/3);
321 }
322
323 // Test 6: (6,good),(2,bad)
324 {
325 Vec<GenDescriptor> vec(INIT_SIZE, 2);
326 vec[0] = GenDescriptor(/*order=*/6,/*good=*/true, /*genIdx=*/0);
327 vec[1] = GenDescriptor(/*order=*/ 2, /*good=*/false,/*genIdx=*/1);
328 cout << "\n**Testing [(6,good),(2,bad)], width=5\n";
329 testCube(vec, /*width=*/5);
330 }
331
332 // Test 7: the "general case", (682,good),(2,bad)
333 {
334 Vec<GenDescriptor> vec(INIT_SIZE, 2);
335 vec[0] = GenDescriptor(/*order=*/682,/*good=*/true, /*genIdx=*/0);
336 vec[1] = GenDescriptor(/*order=*/ 2, /*good=*/false,/*genIdx=*/1);
337 cout << "\n**Testing [(682,good),(2,bad)], width=11\n";
338 testCube(vec, /*width=*/11);
339 }
340 #endif
341