Percy++
A C++ implementation of Private Information Retrieval (PIR) protocols
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Pages
itserver_impl.h
1 // Percy++ Copyright 2007,2012,2013,2014
2 // Ian Goldberg <iang@cs.uwaterloo.ca>,
3 // Casey Devet <cjdevet@uwaterloo.ca>,
4 // Wouter Lueks <wouter@telox.net>
5 //
6 // This program is free software; you can redistribute it and/or modify
7 // it under the terms of version 2 of the GNU General Public License as
8 // published by the Free Software Foundation.
9 //
10 // This program is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // There is a copy of the GNU General Public License in the COPYING file
16 // packaged with this plugin; if you cannot find it, write to the Free
17 // Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
18 // 02110-1301 USA
19 
20 #ifndef __ITSERVER_IMPL_H__
21 #define __ITSERVER_IMPL_H__
22 
23 #include <iostream>
24 #include <string.h>
25 #include "percyparams.h"
26 #include "gf2e.h"
27 #include "xor.h"
28 #include "gf2e_matrix.h"
29 
31 
32 template <typename GF2E_Element>
34  const PercyServerParams * params, PercyStats * stats)
35 :
36  PercyServer(datastore, params, stats),
37  params(static_cast<const GF2EParams*>(params->percy_params()))
38 {}
39 
40 template <typename GF2E_Element>
42 {}
43 
44 template <typename GF2E_Element>
45 inline void compute_outputvec_single(
46  const GF2E_Element *data, const GF2E_Element *inputvec,
47  GF2E_Element *outputvec, dbsize_t num_blocks, dbsize_t words_per_block,
48  dbsize_t virtual_block_size = 1);
49 
50 template <>
51 inline void compute_outputvec_single<GF28_Element>(
52  const GF28_Element *data, const GF28_Element *inputvec,
53  GF28_Element *outputvec, dbsize_t num_blocks, dbsize_t words_per_block,
54  dbsize_t virtual_block_size)
55 {
56  const GF28_Element *block = data;
57  dbsize_t num_virtual_blocks = (num_blocks - 1) / virtual_block_size + 1;
58  dbsize_t words_per_virtual_block = words_per_block * virtual_block_size;
59  for (unsigned int j = 0; j < num_virtual_blocks; ++j) {
60  const GF28_Element *multrow = GF28_mult_table[inputvec[j]];
61  const GF28_Element *blockc = block;
62  if (j == num_virtual_blocks-1) {
63  words_per_virtual_block = words_per_block *
64  ((num_blocks - 1) % virtual_block_size + 1);
65  }
66  GF28_Element *oc = outputvec;
67  GF28_Element *oc_end = oc + (words_per_virtual_block & ~7);
68  while (oc < oc_end) {
69  uint64_t accum = (uint64_t) multrow[*(blockc++)];
70  accum |= (uint64_t) multrow[*(blockc++)] << 8;
71  accum |= (uint64_t) multrow[*(blockc++)] << 16;
72  accum |= (uint64_t) multrow[*(blockc++)] << 24;
73  accum |= (uint64_t) multrow[*(blockc++)] << 32;
74  accum |= (uint64_t) multrow[*(blockc++)] << 40;
75  accum |= (uint64_t) multrow[*(blockc++)] << 48;
76  accum |= (uint64_t) multrow[*(blockc++)] << 56;
77  *((uint64_t *) oc) ^= accum;
78  oc+=8;
79  }
80  for (unsigned int c = 0; c < (words_per_virtual_block & 7); ++c) {
81  *(oc++) ^= multrow[*(blockc++)];
82  }
83  block += words_per_virtual_block;
84  }
85 }
86 
87 template <>
88 inline void compute_outputvec_single<GF216_Element>(
89  const GF216_Element *data, const GF216_Element *inputvec,
90  GF216_Element *outputvec, dbsize_t num_blocks, dbsize_t words_per_block,
91  dbsize_t virtual_block_size)
92 {
93  const GF216_Element *block = data;
94  dbsize_t num_virtual_blocks = (num_blocks - 1) / virtual_block_size + 1;
95  dbsize_t words_per_virtual_block = words_per_block * virtual_block_size;
96  for (dbsize_t j = 0; j < num_virtual_blocks; ++j) {
97  GF216_Element inpv_j = inputvec[j];
98  if (j == num_virtual_blocks-1) {
99  words_per_virtual_block = words_per_block *
100  ((num_blocks - 1) % virtual_block_size + 1);
101  }
102  if (inpv_j == 0) {
103  block += words_per_virtual_block;
104  continue;
105  }
106  GF216_Element log_j = GF216_log_table[inpv_j];
107  const GF216_Element *start = GF216_exp_table + log_j;
108  const GF216_Element *blockc = block;
109  GF216_Element *oc = outputvec;
110  GF216_Element *oc_end = oc + (words_per_virtual_block & ~3);
111  GF216_Element block_c;
112  while(oc < oc_end) {
113  uint64_t accum = 0;
114  block_c = *(blockc++);
115  if (block_c != 0) {
116  GF216_Element log_c = GF216_log_table[block_c];
117  accum |= (uint64_t) start[log_c];
118  }
119  block_c = *(blockc++);
120  if (block_c != 0) {
121  GF216_Element log_c = GF216_log_table[block_c];
122  accum |= (uint64_t) start[log_c] << 16;
123  }
124  block_c = *(blockc++);
125  if (block_c != 0) {
126  GF216_Element log_c = GF216_log_table[block_c];
127  accum |= (uint64_t) start[log_c] << 32;
128  }
129  block_c = *(blockc++);
130  if (block_c != 0) {
131  GF216_Element log_c = GF216_log_table[block_c];
132  accum |= (uint64_t) start[log_c] << 48;
133  }
134  *((uint64_t *) oc) ^= accum;
135  oc+=4;
136  }
137  for (dbsize_t c = 0; c < (words_per_virtual_block & 3); ++c, ++oc) {
138  block_c = *(blockc++);
139  if (block_c != 0) {
140  GF216_Element log_c = GF216_log_table[block_c];
141  *oc ^= start[log_c];
142  }
143  }
144  block += words_per_virtual_block;
145  }
146 }
147 
148 template <typename GF2E_Element>
149 inline void compute_outputvec_multi(
150  const GF2E_Element *data, const std::vector<GF2E_Element*> inputvecs,
151  std::vector<GF2E_Element*> outputvecs, nqueries_t num_queries,
152  dbsize_t num_blocks, dbsize_t words_per_block,
153  dbsize_t virtual_block_size = 1);
154 
155 template <>
156 inline void compute_outputvec_multi<GF28_Element>(
157  const GF28_Element *data, const std::vector<GF28_Element*> inputvecs,
158  std::vector<GF28_Element*> outputvecs, nqueries_t num_queries,
159  dbsize_t num_blocks, dbsize_t words_per_block,
160  dbsize_t virtual_block_size)
161 {
162  dbsize_t num_virtual_blocks = (num_blocks - 1) / virtual_block_size + 1;
163  if (num_queries == 2) {
164  const GF28_Element *block = data;
165  const GF28_Element *inp1 = inputvecs[0];
166  const GF28_Element *inp2 = inputvecs[1];
167  dbsize_t words_per_virtual_block = words_per_block * virtual_block_size;
168  for (unsigned int j = 0; j < num_virtual_blocks; ++j) {
169  const GF28_Element *multrow1 = GF28_mult_table[*(inp1++)];
170  const GF28_Element *multrow2 = GF28_mult_table[*(inp2++)];
171  GF28_Element *oc1 = outputvecs[0];
172  GF28_Element *oc2 = outputvecs[1];
173  if (j == num_virtual_blocks-1) {
174  words_per_virtual_block = words_per_block *
175  ((num_blocks - 1) % virtual_block_size + 1);
176  }
177  const GF28_Element *blockc = block;
178  GF28_Element *oc1_end = oc1 + (words_per_virtual_block & ~7);
179  while (oc1 < oc1_end) {
180  GF28_Element v1 = *(blockc++);
181  uint64_t accum1 = (uint64_t) multrow1[v1];
182  uint64_t accum2 = (uint64_t) multrow2[v1];
183  GF28_Element v2 = *(blockc++);
184  accum1 |= (uint64_t) multrow1[v2] << 8;
185  accum2 |= (uint64_t) multrow2[v2] << 8;
186  GF28_Element v3 = *(blockc++);
187  accum1 |= (uint64_t) multrow1[v3] << 16;
188  accum2 |= (uint64_t) multrow2[v3] << 16;
189  GF28_Element v4 = *(blockc++);
190  accum1 |= (uint64_t) multrow1[v4] << 24;
191  accum2 |= (uint64_t) multrow2[v4] << 24;
192  GF28_Element v5 = *(blockc++);
193  accum1 |= (uint64_t) multrow1[v5] << 32;
194  accum2 |= (uint64_t) multrow2[v5] << 32;
195  GF28_Element v6 = *(blockc++);
196  accum1 |= (uint64_t) multrow1[v6] << 40;
197  accum2 |= (uint64_t) multrow2[v6] << 40;
198  GF28_Element v7 = *(blockc++);
199  accum1 |= (uint64_t) multrow1[v7] << 48;
200  accum2 |= (uint64_t) multrow2[v7] << 48;
201  GF28_Element v8 = *(blockc++);
202  accum1 |= (uint64_t) multrow1[v8] << 56;
203  accum2 |= (uint64_t) multrow2[v8] << 56;
204  *((uint64_t *) oc1) ^= accum1;
205  *((uint64_t *) oc2) ^= accum2;
206  oc1+=8;
207  oc2+=8;
208  }
209  for (unsigned int c = 0; c < (words_per_virtual_block & 7); ++c) {
210  GF28_Element v = *(blockc++);
211  *(oc1++) ^= multrow1[v];
212  *(oc2++) ^= multrow2[v];
213  }
214  block += words_per_virtual_block;
215  }
216  } else if (num_queries == 3) {
217  const GF28_Element *block = data;
218  const GF28_Element *inp1 = inputvecs[0];
219  const GF28_Element *inp2 = inputvecs[1];
220  const GF28_Element *inp3 = inputvecs[2];
221  dbsize_t words_per_virtual_block = words_per_block * virtual_block_size;
222  for (unsigned int j = 0; j < num_virtual_blocks; ++j) {
223  const GF28_Element *multrow1 = GF28_mult_table[*(inp1++)];
224  const GF28_Element *multrow2 = GF28_mult_table[*(inp2++)];
225  const GF28_Element *multrow3 = GF28_mult_table[*(inp3++)];
226  const GF28_Element *blockc = block;
227  GF28_Element *oc1 = outputvecs[0];
228  GF28_Element *oc2 = outputvecs[1];
229  GF28_Element *oc3 = outputvecs[2];
230  if (j == num_virtual_blocks-1) {
231  words_per_virtual_block = words_per_block *
232  ((num_blocks - 1) % virtual_block_size + 1);
233  }
234  GF28_Element *oc1_end = oc1 + (words_per_virtual_block & ~7);
235  while (oc1 < oc1_end) {
236  GF28_Element v1 = *(blockc++);
237  uint64_t accum1 = (uint64_t) multrow1[v1];
238  uint64_t accum2 = (uint64_t) multrow2[v1];
239  uint64_t accum3 = (uint64_t) multrow3[v1];
240  GF28_Element v2 = *(blockc++);
241  accum1 |= (uint64_t) multrow1[v2] << 8;
242  accum2 |= (uint64_t) multrow2[v2] << 8;
243  accum3 |= (uint64_t) multrow3[v2] << 8;
244  GF28_Element v3 = *(blockc++);
245  accum1 |= (uint64_t) multrow1[v3] << 16;
246  accum2 |= (uint64_t) multrow2[v3] << 16;
247  accum3 |= (uint64_t) multrow3[v3] << 16;
248  GF28_Element v4 = *(blockc++);
249  accum1 |= (uint64_t) multrow1[v4] << 24;
250  accum2 |= (uint64_t) multrow2[v4] << 24;
251  accum3 |= (uint64_t) multrow3[v4] << 24;
252  GF28_Element v5 = *(blockc++);
253  accum1 |= (uint64_t) multrow1[v5] << 32;
254  accum2 |= (uint64_t) multrow2[v5] << 32;
255  accum3 |= (uint64_t) multrow3[v5] << 32;
256  GF28_Element v6 = *(blockc++);
257  accum1 |= (uint64_t) multrow1[v6] << 40;
258  accum2 |= (uint64_t) multrow2[v6] << 40;
259  accum3 |= (uint64_t) multrow3[v6] << 40;
260  GF28_Element v7 = *(blockc++);
261  accum1 |= (uint64_t) multrow1[v7] << 48;
262  accum2 |= (uint64_t) multrow2[v7] << 48;
263  accum3 |= (uint64_t) multrow3[v7] << 48;
264  GF28_Element v8 = *(blockc++);
265  accum1 |= (uint64_t) multrow1[v8] << 56;
266  accum2 |= (uint64_t) multrow2[v8] << 56;
267  accum3 |= (uint64_t) multrow3[v8] << 56;
268  *((uint64_t *) oc1) ^= accum1;
269  *((uint64_t *) oc2) ^= accum2;
270  *((uint64_t *) oc3) ^= accum3;
271  oc1+=8;
272  oc2+=8;
273  oc3+=8;
274  }
275  for (unsigned int c = 0; c < (words_per_virtual_block & 7); ++c) {
276  GF28_Element v = *(blockc++);
277  *(oc1++) ^= multrow1[v];
278  *(oc2++) ^= multrow2[v];
279  *(oc3++) ^= multrow3[v];
280  }
281  block += words_per_virtual_block;
282  }
283  } else {
284  const GF28_Element *block = data;
285  const GF28_Element **inpv = new const GF28_Element*[num_queries];
286  const GF28_Element **multrowv = new const GF28_Element*[num_queries];
287  GF28_Element **ocv = new GF28_Element*[num_queries];
288  for (unsigned int q=0; q<num_queries; ++q) {
289  inpv[q] = inputvecs[q];
290  }
291  dbsize_t words_per_virtual_block = words_per_block * virtual_block_size;
292  for (unsigned int j = 0; j < num_virtual_blocks; ++j) {
293  for (unsigned int q=0; q<num_queries; ++q) {
294  multrowv[q] = GF28_mult_table[*(inpv[q]++)];
295  }
296  const GF28_Element *blockc = block;
297  GF28_Element *ocv0 = outputvecs[0];
298  if (j == num_virtual_blocks-1) {
299  words_per_virtual_block = words_per_block *
300  ((num_blocks - 1) % virtual_block_size + 1);
301  }
302  for (unsigned int q=1; q<num_queries; ++q) {
303  ocv[q] = outputvecs[q];
304  }
305  GF28_Element *oc_end = ocv0 + (words_per_virtual_block & ~7);
306  while (ocv0 < oc_end) {
307  GF28_Element v1 = *(blockc++);
308  GF28_Element v2 = *(blockc++);
309  GF28_Element v3 = *(blockc++);
310  GF28_Element v4 = *(blockc++);
311  GF28_Element v5 = *(blockc++);
312  GF28_Element v6 = *(blockc++);
313  GF28_Element v7 = *(blockc++);
314  GF28_Element v8 = *(blockc++);
315  uint64_t accum = (uint64_t) multrowv[0][v1];
316  accum |= (uint64_t) multrowv[0][v2] << 8;
317  accum |= (uint64_t) multrowv[0][v3] << 16;
318  accum |= (uint64_t) multrowv[0][v4] << 24;
319  accum |= (uint64_t) multrowv[0][v5] << 32;
320  accum |= (uint64_t) multrowv[0][v6] << 40;
321  accum |= (uint64_t) multrowv[0][v7] << 48;
322  accum |= (uint64_t) multrowv[0][v8] << 56;
323  *((uint64_t *) ocv0) ^= accum;
324  ocv0 += 8;
325  for (unsigned int q=1; q<num_queries; ++q) {
326  uint64_t accum = (uint64_t) multrowv[q][v1];
327  accum |= (uint64_t) multrowv[q][v2] << 8;
328  accum |= (uint64_t) multrowv[q][v3] << 16;
329  accum |= (uint64_t) multrowv[q][v4] << 24;
330  accum |= (uint64_t) multrowv[q][v5] << 32;
331  accum |= (uint64_t) multrowv[q][v6] << 40;
332  accum |= (uint64_t) multrowv[q][v7] << 48;
333  accum |= (uint64_t) multrowv[q][v8] << 56;
334  *((uint64_t *) ocv[q]) ^= accum;
335  ocv[q] += 8;
336  }
337  }
338  for (unsigned int c = 0; c < (words_per_virtual_block & 7); ++c) {
339  GF28_Element v = *(blockc++);
340  *(ocv0++) ^= multrowv[0][v];
341  for (unsigned int q=1; q<num_queries; ++q) {
342  *(ocv[q]++) ^= multrowv[q][v];
343  }
344  }
345  block += words_per_virtual_block;
346  }
347  delete[] inpv;
348  delete[] multrowv;
349  delete[] ocv;
350  }
351 }
352 
353 template <>
354 inline void compute_outputvec_multi<GF216_Element>(
355  const GF216_Element *data, const std::vector<GF216_Element*> inputvecs,
356  std::vector<GF216_Element*> outputvecs, nqueries_t num_queries,
357  dbsize_t num_blocks, dbsize_t words_per_block,
358  dbsize_t virtual_block_size)
359 {
360  for (nqueries_t q = 0; q < num_queries; q++) {
361  compute_outputvec_single<GF216_Element>(data, inputvecs[q],
362  outputvecs[q], num_blocks, words_per_block);
363  }
364 }
365 
366 template<>
368  nqueries_t res_rows, dbsize_t inner_dim, dbsize_t res_cols)
369 {
370  nqueries_t depth = 0;
371  if( res_rows < 10 ) {
372  // Don't do Strassen
373  return 0;
374  }
375 
376  nqueries_t max_number_rows = 3;
377 
378  // For larger database don't go so far down yet
379  if( (inner_dim >= 32768 && res_rows < 48) ||
380  (inner_dim >= 16384 && res_rows < 32)) {
381  max_number_rows = 7;
382  }
383 
384  // The optimal level of 3 for res_rows results from the optimized
385  // multiplication routines for 1, 2 and 3 queries
386  while(res_rows > max_number_rows && inner_dim > 1 && res_cols > 1) {
387  res_rows /= 2;
388  inner_dim /= 2;
389  res_cols /= 2;
390 
391  depth++;
392  }
393 
394  return depth;
395 }
396 
397 template<>
399  nqueries_t res_rows, dbsize_t inner_dim, dbsize_t res_cols)
400 {
401  std::cerr << "Warning: optimal levels for GF216 not yet determined"
402  << std::endl;
403 
404  nqueries_t depth = 0;
405  if( res_rows < 10 ) {
406  // Don't do Strassen
407  return 0;
408  }
409 
410  while(res_rows > 4 && inner_dim > 1 && res_cols > 1) {
411  res_rows /= 2;
412  inner_dim /= 2;
413  res_cols /= 2;
414 
415  depth++;
416  }
417 
418  return depth;
419 }
420 
421 template <typename GF2E_Element>
423  nqueries_t res_rows, dbsize_t inner_dim, dbsize_t res_cols)
424 {
425  size_t num_elts = 0;
426 
427  while(res_rows > 1 && inner_dim > 1 && res_cols > 1) {
428  res_rows /= 2;
429  inner_dim /= 2;
430  res_cols /= 2;
431 
432  num_elts += res_rows * inner_dim;
433  num_elts += inner_dim * res_cols;
434  num_elts += res_rows * res_cols;
435  }
436 
437  GF2E_Element * memory = new GF2E_Element[num_elts];
438 
439  return memory;
440 }
441 
442 template <typename GF2E_Element>
444  GF2E_Element * memory)
445 {
446  delete[] memory;
447 }
448 
449 template <typename GF2E_Element>
453  dbsize_t depth, GF2E_Element * memory)
454 {
455  dbsize_t q, r, s, qrem, rrem, srem;
456 
457  dbsize_t res_rows = mat_a.num_rows;
458  dbsize_t inner_dim = mat_a.num_cols;
459  dbsize_t res_cols = mat_b.num_cols;
460 
461  mat_c.clear();
462 
463  if( res_rows <= 1 || inner_dim <= 1 ||
464  res_cols <= 1 || depth > strassen_real_max_depth) {
465  if(res_rows > 1) {
466  // TODO: See if we want to change this.
467  std::vector<GF2E_Element*> inputvec, outputvec;
468  for (nqueries_t q = 0; q < res_rows; ++q) {
469  inputvec.push_back(const_cast<GF2E_Element*>(mat_a.data + q * mat_a.num_cols));
470  outputvec.push_back(const_cast<GF2E_Element*>(mat_c.data + q * mat_c.num_cols));
471  }
472  compute_outputvec_multi(mat_b.data, inputvec, outputvec,
473  res_rows, inner_dim, res_cols);
474  } else {
475  compute_outputvec_single(mat_b.data, mat_a.data, mat_c.data,
476  inner_dim, res_cols);
477  }
478 
479  return;
480  }
481 
482  if(depth > strassen_level_reached) {
483  strassen_level_reached = depth;
484  }
485 
486  qrem = res_rows % 2;
487  rrem = inner_dim % 2;
488  srem = res_cols % 2;
489 
490  q = res_rows - qrem;
491  r = inner_dim - rrem;
492  s = res_cols - srem;
493 
495  SubMatrix<const GF2E_Element> (mat_a, 0, 0, q, r);
497  Col<const GF2E_Element> (mat_a, 0, r, q);
499  Row<const GF2E_Element> (mat_a, q, 0, r);
501  Elem<const GF2E_Element> (mat_a, q, r);
502 
504  SubMatrix<const GF2E_Element> (mat_b, 0, 0, r, s);
506  Col<const GF2E_Element> (mat_b, 0, s, r);
508  Row<const GF2E_Element> (mat_b, r, 0, s);
510  Elem<const GF2E_Element> (mat_b, r, s);
511 
513  SubMatrix<GF2E_Element> (mat_c, 0, 0, q, s);
514  Col<GF2E_Element> c12 =
515  Col<GF2E_Element> (mat_c, 0, s, q);
516  Row<GF2E_Element> c21 =
517  Row<GF2E_Element> (mat_c, q, 0, s);
518  Elem<GF2E_Element> c22 =
519  Elem<GF2E_Element> (mat_c, q, s);
520 
521  // A21 * B11
522  if(qrem > 0) {
523  c21.add_mult_of(a21, b11);
524  }
525 
526  // A11 * B12
527  if(srem > 0) {
528  c12.add_mult_of(a11, b12);
529  }
530 
531  // A21 * B12
532  if(qrem > 0 && srem > 0) {
533  c22.add_mult_of(a21, b12);
534  }
535 
536  if(rrem > 0) {
537  // A12 * B21
538  c11.add_mult_of(a12, b21);
539 
540  // A22 * B21
541  if(qrem > 0) {
542  c21.add_mult_of(a22, b21);
543  }
544 
545  // A12 * B22
546  if(srem > 0) {
547  c12.add_mult_of(a12, b22);
548  }
549 
550  // A22 * B22
551  if(qrem > 0 && srem > 0) {
552  c22.add_mult_of(a22, b22);
553  }
554  }
555 
556  strassen_mult(mat_a, mat_b, mat_c, depth, memory);
557 }
558 
559 
560 template <typename GF2E_Element>
564  dbsize_t depth, GF2E_Element * memory)
565 {
566  dbsize_t nq = mat_a.num_rows / 2;
567  dbsize_t nr = mat_a.num_cols / 2;
568  dbsize_t ns = mat_b.num_cols / 2;
569 
570  Matrix<const GF2E_Element> matrix_left =
571  Matrix<const GF2E_Element>(memory, nq, nr);
572  memory += nq * nr;
573  Matrix<const GF2E_Element> matrix_right =
574  Matrix<const GF2E_Element>(memory, nr, ns);
575  memory += nr * ns;
576  Matrix<GF2E_Element> matrix_subresult =
577  Matrix<GF2E_Element>(memory, nq, ns);
578  memory += nq * ns;
579 
580  SubMatrix<const GF2E_Element> a11, a12, a21, a22;
581  mat_a.strassen_submatrices(a11, a12, a21, a22);
582 
583  SubMatrix<const GF2E_Element> b11, b12, b21, b22;
584  mat_b.strassen_submatrices(b11, b12, b21, b22);
585 
586  SubMatrix<GF2E_Element> c11, c12, c21, c22;
587  mat_c.strassen_submatrices(c11, c12, c21, c22);
588 
589  // #1
590  matrix_left.is_sum_of(a11, a22);
591  matrix_right.is_sum_of(b11, b22);
592  strassen_split(matrix_left, matrix_right, matrix_subresult,
593  depth + 1, memory);
594  c11.add(matrix_subresult);
595  c22.add(matrix_subresult);
596 
597  // #2
598  matrix_left.is_sum_of(a21, a22);
599  matrix_right.copy_from(b11);
600  strassen_split(matrix_left, matrix_right, matrix_subresult,
601  depth + 1, memory);
602  c21.add(matrix_subresult);
603  c22.add(matrix_subresult);
604 
605  // #3
606  matrix_left.copy_from(a11);
607  matrix_right.is_sum_of(b12, b22);
608  strassen_split(matrix_left, matrix_right, matrix_subresult,
609  depth + 1, memory);
610  c12.add(matrix_subresult);
611  c22.add(matrix_subresult);
612 
613  // #4
614  matrix_left.copy_from(a22);
615  matrix_right.is_sum_of(b21, b11);
616  strassen_split(matrix_left, matrix_right, matrix_subresult,
617  depth + 1, memory);
618  c11.add(matrix_subresult);
619  c21.add(matrix_subresult);
620 
621  // #5
622  matrix_left.is_sum_of(a11, a12);
623  matrix_right.copy_from(b22);
624  strassen_split(matrix_left, matrix_right, matrix_subresult,
625  depth + 1, memory);
626  c11.add(matrix_subresult);
627  c12.add(matrix_subresult);
628 
629  // #6
630  matrix_left.is_sum_of(a21, a11);
631  matrix_right.is_sum_of(b11, b12);
632  strassen_split(matrix_left, matrix_right, matrix_subresult,
633  depth + 1, memory);
634  c22.add(matrix_subresult);
635 
636  // #7
637  matrix_left.is_sum_of(a12, a22);
638  matrix_right.is_sum_of(b21, b22);
639  strassen_split(matrix_left, matrix_right, matrix_subresult,
640  depth + 1, memory);
641  c11.add(matrix_subresult);
642 }
643 
644 template <typename GF2E_Element>
645 nqueries_t PercyServer_GF2E<GF2E_Element>::optimal_strassen_num_queries(nqueries_t num_queries)
646 {
647  int bitlength = 0;
648  nqueries_t tmp = num_queries;
649  nqueries_t increased;
650  double factor;
651 
652  while(tmp > 0) {
653  bitlength++;
654  tmp /= 2;
655  }
656 
657  nqueries_t ptwo = 2 << (bitlength - 1);
658  nqueries_t pthree = 3 << (bitlength - 2);
659 
660  if(pthree > num_queries) {
661  increased = pthree;
662  factor = 1.125;
663  } else {
664  increased = ptwo;
665  factor = 1.05;
666  }
667 
668  // Only increase size if the cost is not too much
669  if (((double) increased) / num_queries < factor) {
670  return increased;
671  } else {
672  return num_queries;
673  }
674 }
675 
676 template <typename GF2E_Element>
678  const std::vector<unsigned char*> &requests,
679  const std::vector<unsigned char*> &responses)
680 {
681  nqueries_t num_queries = requests.size();
682  if (responses.size() != num_queries) {
683  return false;
684  }
685 
686  // Read some values from the params
687  dbsize_t words_per_block = params->words_per_block();
688  dbsize_t num_blocks = params->num_blocks();
689  dbsize_t block_size = params->block_size();
690  dbsize_t virtual_block_size = params->virtual_block_size();
691 
692  // Strassen is more efficient for certain number of queries,
693  // so we test if a resize is necessary.
694  dbsize_t optimal_num_queries = optimal_strassen_num_queries(num_queries);
695 
696  const GF2E_Element *data = (const GF2E_Element*)(datastore->get_data());
697 
698  strassen_level_reached = 0;
699 
700  // Compute the output vector and send it back to the client
701 
702  //struct timeval ts, te;
703  //gettimeofday(&ts, NULL);
704  if (num_queries > 1) {
705  if (strassen_max_depth == PercyServer::STRASSEN_OPTIMAL) {
706  strassen_real_max_depth =
707  optimal_strassen_depth(optimal_num_queries, num_blocks,
708  words_per_block);
709  } else {
710  strassen_real_max_depth = strassen_max_depth;
711  }
712 
713  if (strassen_real_max_depth == 0 || virtual_block_size > 1) {
714  std::vector<GF2E_Element*> inputvecs, outputvecs;
715  for (nqueries_t q = 0; q < num_queries; ++q) {
716  memset(responses[q], '\0', block_size);
717  inputvecs.push_back((GF2E_Element*)(requests[q]));
718  outputvecs.push_back((GF2E_Element*)(responses[q]));
719  }
720  compute_outputvec_multi<GF2E_Element>(data, inputvecs, outputvecs,
721  num_queries, num_blocks, words_per_block,
722  virtual_block_size);
723  } else {
724  // TODO: Take a look at this and see if it needs to change
725  GF2E_Element * input =
726  new GF2E_Element[optimal_num_queries * num_blocks];
727  GF2E_Element * output =
728  new GF2E_Element[optimal_num_queries * words_per_block];
729  memset(output, '\0', optimal_num_queries * words_per_block *
730  sizeof(GF2E_Element));
731  for (nqueries_t q = 0; q < num_queries; ++q) {
732  memcpy(input + q*num_blocks*sizeof(GF2E_Element), requests[q],
733  num_blocks*sizeof(GF2E_Element));
734  }
735  if (optimal_num_queries > num_queries) {
736  memset(input +
737  num_queries * num_blocks * sizeof(GF2E_Element),
738  '\0', (optimal_num_queries - num_queries) *
739  num_blocks * sizeof(GF2E_Element));
740  }
741 
742  GF2E_Element * memory = alloc_strassen_memory(
743  optimal_num_queries, num_blocks, words_per_block);
744  Matrix<const GF2E_Element> mat_input =
745  Matrix<const GF2E_Element>(input, optimal_num_queries,
746  num_blocks);
747  Matrix<const GF2E_Element> mat_data =
748  Matrix<const GF2E_Element>(data, num_blocks,
749  words_per_block);
750  Matrix<GF2E_Element> mat_output =
751  Matrix<GF2E_Element>(output, optimal_num_queries,
752  words_per_block);
753  strassen_split(mat_input, mat_data, mat_output, 1, memory);
754  free_strassen_memory(memory);
755 
756  for (nqueries_t q = 0; q < num_queries; ++q) {
757  memcpy(responses[q], output + q*words_per_block*sizeof(GF2E_Element),
758  block_size);
759  }
760  }
761  } else {
762  memset(responses[0], '\0', block_size);
763  compute_outputvec_single<GF2E_Element>(data,
764  (GF2E_Element*)(requests[0]), (GF2E_Element*)(responses[0]),
765  num_blocks, words_per_block, virtual_block_size);
766  }
767 
768  //gettimeofday(&te, NULL);
769  //int td = (te.tv_sec - ts.tv_sec)*1000000 + (te.tv_usec - ts.tv_usec);
770  //fprintf(stderr, "%d.%3d msec computation\n", td/1000, td%1000);
771 
772  // If the server is Byzantine, give wrong output
773  if (byzantine) {
774  for (nqueries_t q = 0; q < num_queries; q++) {
775  for (dbsize_t i = 0; i < words_per_block; i++) {
776  responses[q][i]++;
777  }
778  }
779  }
780 
781  return true;
782 }
783 
784 template <typename GF2E_Element>
785 void PercyServer_GF2E<GF2E_Element>::combine_results (unsigned char * result,
786  const std::vector<unsigned char*> &worker_results)
787 {
788  dbsize_t block_size = params->block_size() * params->virtual_block_size();
789  for (nservers_t i = 0; i < worker_results.size(); ++i) {
790  XOR_equal(result, worker_results[i], block_size);
791  }
792 }
793 
794 #endif
Definition: percystats.h:66
A simple database object.
Definition: datastore.h:34
A PIR server for the IT-PIR protocol by Goldberg (2007) over GF(2^E).
Definition: itserver.h:143
An abstract base class for a PIR server.
Definition: percyserver.h:34
Definition: old_matrix.h:28
Definition: old_matrix.h:33
Definition: old_matrix.h:29
Definition: old_matrix.h:30
static const nqueries_t STRASSEN_OPTIMAL
Special strassen max level, when set to this value, the optimal strategy is used. ...
Definition: percyserver.h:53
virtual ~PercyServer_GF2E()
Destructor.
Definition: itserver_impl.h:41
Server parameters.
Definition: percyparams.h:251
Definition: old_matrix.h:27
Defines the basic structure of protocol parameters (PercyParams), client parameters (PercyClientParam...
PercyServer_GF2E(DataStore *datastore, const PercyServerParams *params, PercyStats *stats=NULL)
Constructor.
Definition: itserver_impl.h:33
Definition: itparams.h:144