PIRReplyGeneratorNFL_internal.cpp 32 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894
  1. /* Copyright (C) 2014 Carlos Aguilar Melchor, Joris Barrier, Marc-Olivier Killijian
  2. * This file is part of XPIR.
  3. *
  4. * XPIR is free software: you can redistribute it and/or modify
  5. * it under the terms of the GNU General Public License as published by
  6. * the Free Software Foundation, either version 3 of the License, or
  7. * (at your option) any later version.
  8. *
  9. * XPIR is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with XPIR. If not, see <http://www.gnu.org/licenses/>.
  16. */
  17. #include "PIRReplyGeneratorNFL_internal.hpp"
  18. #include "sys/time.h"
  19. //#define SIMULATE_PRE_NFL_DATA //Use this to simulate imported data is in NFL form
  20. //#define TEST_NFL_PERF_ITERATIONS //Loop to simulate very large databases
  21. //#define SNIFFER_CHUNK_BYTESIZE 12800
  22. //#define SNIFFER_CHUNK_BYTESIZE 2560
  23. //#define SNIFFER_CHUNK_BYTESIZE 1500
  24. //#define SNIFFER_CHUNK_BYTESIZE 600
  25. //#define SNIFFER //Use this to activate a sniffer like behavior
  26. PIRReplyGeneratorNFL_internal::PIRReplyGeneratorNFL_internal():
  27. lwe(false)
  28. {
  29. }
  30. /**
  31. * Constructor of the class.
  32. * Params :
  33. * - vector <File*>& database : reference of a File pointer vector.
  34. * - PIRParameters& param : reference to a PIRParameters object.
  35. **/
  36. PIRReplyGeneratorNFL_internal::PIRReplyGeneratorNFL_internal( PIRParameters& param, DBHandler* db):
  37. lwe(false),
  38. currentMaxNbPolys(1),
  39. GenericPIRReplyGenerator(param,db),
  40. current_query_index(0),
  41. current_dim_index(0)
  42. {
  43. // cryptoMethod will be set later by setCryptoMethod
  44. }
  45. void PIRReplyGeneratorNFL_internal::importFakeData(uint64_t plaintext_nbr)
  46. {
  47. uint64_t files_nbr = 1;
  48. for (unsigned int i = 0 ; i < pirParam.d ; i++) files_nbr *= pirParam.n[i];
  49. uint64_t plain_bytesize = cryptoMethod->getnflInstance().getpolyDegree()*cryptoMethod->getnflInstance().getnbModuli()*8;
  50. dbhandler = new DBGenerator(files_nbr, plaintext_nbr*plain_bytesize, true);
  51. currentMaxNbPolys = plaintext_nbr;
  52. importDataNFL(0, plaintext_nbr*plain_bytesize);
  53. }
  54. /**
  55. * Convert raw data from file in usable NFL data.
  56. **/
  57. void PIRReplyGeneratorNFL_internal::importDataNFL(uint64_t offset, uint64_t bytes_per_file)
  58. {
  59. uint64_t fileByteSize = min(bytes_per_file, dbhandler->getmaxFileBytesize()-offset);
  60. uint64_t theoretical_files_nbr = 1;
  61. uint64_t nbFiles = dbhandler->getNbStream();
  62. for (unsigned int i = 0 ; i < pirParam.d ; i++) theoretical_files_nbr *= pirParam.n[i];
  63. input_data = new lwe_in_data[theoretical_files_nbr];
  64. char *rawBits = (char*)calloc(fileByteSize*pirParam.alpha, sizeof(char));
  65. currentMaxNbPolys=0;
  66. #ifdef PERF_TIMERS
  67. double vtstart = omp_get_wtime();
  68. bool wasVerbose = false;
  69. uint64_t lastindex = 0;
  70. #endif
  71. // For global time measurement
  72. double start = omp_get_wtime();double now,delta;
  73. int nbruns=ceil((double)nbFiles/pirParam.alpha);
  74. // WARNING this section should not be multithreade as rawbits is shared and readAggregatedStream
  75. // is not threadsafe
  76. for (int i=0; i < nbruns; i++)
  77. {
  78. dbhandler->readAggregatedStream(i, pirParam.alpha, offset, bytes_per_file, rawBits);
  79. #ifdef SIMULATE_PRE_NFL_DATA
  80. uint64_t abssize = cryptoMethod->getPublicParameters().getAbsorptionBitsize();
  81. uint64_t polysize = cryptoMethod->getpolyDegree() * cryptoMethod->getnbModuli()*sizeof(uint64_t);
  82. uint64_t nbpolys = ceil((double)fileByteSize * pirParam.alpha * 8 / abssize);
  83. input_data[i].p = (poly64*) malloc(nbpolys*sizeof(poly64*));
  84. input_data[i].p[0] = (poly64) malloc(nbpolys*polysize);
  85. for (unsigned j = 0; j < nbpolys ; j++)
  86. {
  87. input_data[i].p[j] = input_data[i].p[0]+j*polysize/8;
  88. memcpy(input_data[i].p[j], rawBits, min(fileByteSize, polysize));
  89. }
  90. input_data[i].nbPolys = nbpolys;
  91. #else
  92. input_data[i].p = cryptoMethod->deserializeDataNFL((unsigned char**)&rawBits, (uint64_t) 1, fileByteSize*pirParam.alpha*GlobalConstant::kBitsPerByte, input_data[i].nbPolys);
  93. #endif
  94. #ifdef PERF_TIMERS
  95. // Give some feedback if it takes too long
  96. double vtstop = omp_get_wtime();
  97. if (vtstop - vtstart > 1)
  98. {
  99. vtstart = vtstop;
  100. std::cout <<"PIRReplyGeneratorNFL_internal: Element " << i+1 << "/" << nbruns << " imported\r" << std::flush;
  101. wasVerbose = true;
  102. lastindex = i+1;
  103. }
  104. #endif
  105. }
  106. for (int i=0; i < nbruns; i++)
  107. if (input_data[i].nbPolys>currentMaxNbPolys) currentMaxNbPolys=input_data[i].nbPolys;
  108. #ifdef PERF_TIMERS
  109. // If feedback was given say we finished
  110. if (wasVerbose && lastindex != nbFiles) std::cout <<"PIRReplyGeneratorNFL_internal: Element " << nbruns << "/" << nbFiles/pirParam.alpha << " imported" << std::endl;
  111. #endif
  112. /** FILE PADDING **/
  113. for (uint64_t i = ceil((double)nbFiles/pirParam.alpha) ; i < theoretical_files_nbr ; i++)
  114. {
  115. input_data[i].p = (poly64 *) malloc(currentMaxNbPolys*sizeof(poly64));
  116. input_data[i].p[0] = (poly64) calloc(cryptoMethod->getpolyDegree()*cryptoMethod->getnbModuli()*currentMaxNbPolys,sizeof(uint64_t));
  117. for (uint64_t j = 1 ; j < currentMaxNbPolys ; j++) input_data[i].p[j] = input_data[i].p[0]+cryptoMethod->getpolyDegree()*cryptoMethod->getnbModuli()*j;
  118. input_data[i].nbPolys = currentMaxNbPolys;
  119. }
  120. free(rawBits);
  121. std::cout<<"PIRReplyGeneratorNFL_internal: Finished importing the database in " << omp_get_wtime() - start << " seconds" << std::endl;
  122. }
  123. #ifdef SNIFFER
  124. imported_database_t PIRReplyGeneratorNFL_internal::generateReplyGeneric(bool keep_imported_data)
  125. {
  126. imported_database_t database_wrapper;
  127. boost::mutex::scoped_lock l(mutex);
  128. const uint64_t chunkBytesize = SNIFFER_CHUNK_BYTESIZE;
  129. const uint64_t iterations = dbhandler->getmaxFileBytesize()/(chunkBytesize+1);
  130. // std::ifstream *is = dbhandler->openStream(0,0);
  131. const uint64_t nbFiles = dbhandler->getNbStream();
  132. const unsigned int polysize = cryptoMethod->getpolyDegree()*cryptoMethod->getnbModuli();
  133. const unsigned int jumpcipher = 2*polysize / sizeof(uint64_t);
  134. currentMaxNbPolys=0;
  135. lwe_in_data *input = new lwe_in_data[iterations];
  136. lwe_cipher *resul = new lwe_cipher[iterations];
  137. uint64_t index;
  138. lwe_query **queries;
  139. char **rawBits = (char**) malloc(iterations*sizeof(char*));
  140. cryptoMethod->setandgetAbsBitPerCiphertext(1);
  141. queries = queriesBuf[0];
  142. const uint64_t mask = (1<<((int)log2(nbFiles)))-1;
  143. for (uint64_t it = 0 ; it < iterations ; it++)
  144. {
  145. resul[it].a = (uint64_t *) malloc(2*polysize*sizeof(uint64_t));
  146. resul[it].b = (uint64_t *) resul[it].a + polysize;
  147. rawBits[it] = (char*)malloc(((chunkBytesize)*sizeof(char)+sizeof(int)));
  148. }
  149. double start = omp_get_wtime();
  150. #pragma omp parallel for firstprivate(input,queries,resul)
  151. for (uint64_t it = 0 ; it < iterations ; it++)
  152. {
  153. dbhandler->readStream(0, rawBits[it], chunkBytesize+sizeof(int));
  154. input[it].p = cryptoMethod->deserializeDataNFL((unsigned char**)&(rawBits[it]), (uint64_t) 1, chunkBytesize*GlobalConstant::kBitsPerByte, input[it].nbPolys);
  155. index = *(int *)(rawBits[it]+chunkBytesize) & mask;
  156. cryptoMethod->mul(resul[it], input[it], queries[0][index],queries[1][index], 0, 0);
  157. }
  158. double end = omp_get_wtime();
  159. std::cout<<"PIRReplyGeneratorNFL_internal: Finished processing the sniffed data in " << end - start << " seconds" << std::endl;
  160. std::cout<<"PIRReplyGeneratorNFL_internal: Processing throughput " << (double)chunkBytesize*8*iterations / ((end - start)*1000000000ULL) << " Gbps" << std::endl;
  161. return database_wrapper;
  162. }
  163. #else
  164. imported_database_t PIRReplyGeneratorNFL_internal::generateReplyGeneric(bool keep_imported_data)
  165. {
  166. imported_database_t database_wrapper;
  167. uint64_t usable_memory, database_size, max_memory_per_file, max_readable_size, nbr_of_iterations;
  168. double start, end;
  169. // Init database_wrapper to NULL values so that we are able to know if it has been initialized
  170. database_wrapper.imported_database_ptr = NULL;
  171. database_wrapper.nbElements = 0;
  172. database_wrapper.polysPerElement = 0;
  173. // Don't use more than half of the computer's memory
  174. usable_memory = getTotalSystemMemory()/2;
  175. database_size = dbhandler->getmaxFileBytesize() * dbhandler->getNbStream();
  176. #ifndef TEST_NFL_PERF_ITERATIONS
  177. // This is the maximum amount of data per file we can get in memory
  178. max_memory_per_file = usable_memory / dbhandler->getNbStream();
  179. // Given the expansion factor of importation we get the max we can read per file
  180. max_readable_size = max_memory_per_file / 4 ;
  181. // Reduce it so that we have full absorption in all the ciphertexts sent
  182. max_readable_size = (max_readable_size * GlobalConstant::kBitsPerByte / cryptoMethod->getPublicParameters().getAbsorptionBitsize(0)) * cryptoMethod->getPublicParameters().getAbsorptionBitsize(0)/GlobalConstant::kBitsPerByte;
  183. #else
  184. // For our tests we will need to have databases of an integer amount of gigabits
  185. max_readable_size = 1280000000UL/dbhandler->getNbStream();
  186. #endif
  187. // If we reduced it too much set it at least to a ciphertext
  188. if (max_readable_size == 0) max_readable_size = cryptoMethod->getPublicParameters().getAbsorptionBitsize(0);
  189. // Ensure it is not larger than maxfilebytesize
  190. max_readable_size = min(max_readable_size, dbhandler->getmaxFileBytesize());
  191. // Given readable size we get how many iterations we need
  192. nbr_of_iterations = ceil((double)dbhandler->getmaxFileBytesize()/max_readable_size);
  193. #ifndef TEST_NFL_PERF_ITERATIONS
  194. // If aggregation is used we cannot iterate
  195. if ((pirParam.alpha != 1 || pirParam.d > 1) && nbr_of_iterations > 1)
  196. {
  197. std::cout << "PIRReplyGeneratorNFL_internal: Cannot handle aggregation or dimensions on databases requiring multiple iterations" << std::endl;
  198. std::cout << "PIRReplyGeneratorNFL_internal: Handling the database on a single iteration, this can cause memory issues ..." << std::endl;
  199. nbr_of_iterations = 1;
  200. max_readable_size = dbhandler->getmaxFileBytesize();
  201. }
  202. // If we cannot read the whole database we cannot store it precomputed
  203. if (nbr_of_iterations > 1) keep_imported_data = false;
  204. #endif
  205. // If we need to do more than an iteration say it
  206. if (nbr_of_iterations > 1)
  207. {
  208. std::cout << "PIRReplyGeneratorNFL_internal: Database is considered too large, processing it in "
  209. << nbr_of_iterations << " iterations" << std::endl;
  210. }
  211. start = omp_get_wtime();
  212. // #pragma omp parallel for
  213. for (unsigned iteration = 0; iteration < nbr_of_iterations; iteration++)
  214. {
  215. if (nbr_of_iterations > 1) cout << "PIRReplyGeneratorNFL_internal: Iteration " << iteration << endl;
  216. repliesIndex = computeReplySizeInChunks(iteration*max_readable_size);
  217. // Import a chunk of max_readable_size bytes per file with an adapted offset
  218. importDataNFL(iteration*max_readable_size, max_readable_size);
  219. if(keep_imported_data && iteration == nbr_of_iterations - 1) // && added for Perf test but is no harmful
  220. {
  221. database_wrapper.polysPerElement = currentMaxNbPolys;
  222. }
  223. boost::mutex::scoped_lock l(mutex);
  224. generateReply();
  225. end = omp_get_wtime();
  226. if(keep_imported_data && iteration == nbr_of_iterations - 1) // && added for Perf test but is no harmful
  227. {
  228. database_wrapper.imported_database_ptr = (void*)input_data;
  229. }
  230. else
  231. {
  232. freeInputData();
  233. }
  234. }
  235. std::cout<<"PIRReplyGeneratorNFL_internal: Total process time " << end - start << " seconds" << std::endl;
  236. std::cout<<"PIRReplyGeneratorNFL_internal: DB processing throughput " << 8*database_size/(end - start) << "bps" << std::endl;
  237. std::cout<<"PIRReplyGeneratorNFL_internal: Client cleartext reception throughput " << 8*dbhandler->getmaxFileBytesize()/(end - start) << "bps" << std::endl;
  238. freeQuery();
  239. return database_wrapper;
  240. }
  241. #endif
  242. // Function used to generate a PIR reply if:
  243. // - database is small enough to be kept in memory
  244. // - it has already been imported to it
  245. void PIRReplyGeneratorNFL_internal::generateReplyGenericFromData(const imported_database_t database)
  246. {
  247. #ifndef TEST_NFL_PERF_ITERATIONS
  248. input_data = (lwe_in_data*) database.imported_database_ptr;
  249. currentMaxNbPolys = database.polysPerElement;
  250. boost::mutex::scoped_lock l(mutex);
  251. double start = omp_get_wtime();
  252. generateReply();
  253. #else
  254. uint64_t max_readable_size, database_size, nbr_of_iterations;
  255. database_size = dbhandler->getmaxFileBytesize() * dbhandler->getNbStream();
  256. max_readable_size = 1280000000UL/dbhandler->getNbStream();
  257. // Ensure it is not larger than maxfilebytesize
  258. max_readable_size = min(max_readable_size, dbhandler->getmaxFileBytesize());
  259. // Given readable size we get how many iterations we need
  260. nbr_of_iterations = ceil((double)dbhandler->getmaxFileBytesize()/max_readable_size);
  261. boost::mutex::scoped_lock l(mutex);
  262. double start = omp_get_wtime();
  263. for (unsigned iteration = 0; iteration < nbr_of_iterations; iteration++)
  264. {
  265. input_data = (lwe_in_data*) database.imported_database_ptr;
  266. currentMaxNbPolys = database.polysPerElement;
  267. generateReply();
  268. }
  269. freeInputData();
  270. #endif
  271. double end = omp_get_wtime();
  272. std::cout<<"PIRReplyGeneratorNFL_internal: Total process time " << end - start << " seconds" << std::endl;
  273. std::cout<<"PIRReplyGeneratorNFL_internal: DB processing throughput " << 8*dbhandler->getmaxFileBytesize()*dbhandler->getNbStream()/(end - start) << "bps" << std::endl;
  274. std::cout<<"PIRReplyGeneratorNFL_internal: Client cleartext reception throughput " << 8*dbhandler->getmaxFileBytesize()/(end - start) << "bps" << std::endl;
  275. freeQuery();
  276. }
  277. // Function used to generate a PIR reply if:
  278. // - database is small enough to be kept in memory
  279. // - it has already been imported to it
  280. void PIRReplyGeneratorNFL_internal::generateReplyExternal(imported_database_t* database)
  281. {
  282. uint64_t max_readable_size, database_size, nbr_of_iterations;
  283. database_size = dbhandler->getmaxFileBytesize() * dbhandler->getNbStream();
  284. max_readable_size = 1280000000UL/dbhandler->getNbStream();
  285. // Ensure it is not larger than maxfilebytesize
  286. max_readable_size = min(max_readable_size, dbhandler->getmaxFileBytesize());
  287. // Given readable size we get how many iterations we need
  288. nbr_of_iterations = ceil((double)dbhandler->getmaxFileBytesize()/max_readable_size);
  289. boost::mutex::scoped_lock l(mutex);
  290. double start = omp_get_wtime();
  291. for (unsigned iteration = 0; iteration < nbr_of_iterations; iteration++)
  292. {
  293. input_data = (lwe_in_data*) database->imported_database_ptr;
  294. currentMaxNbPolys = database->polysPerElement;
  295. generateReply();
  296. }
  297. freeInputData();
  298. double end = omp_get_wtime();
  299. std::cout<<"PIRReplyGeneratorNFL_internal: Total process time " << end - start << " seconds" << std::endl;
  300. std::cout<<"PIRReplyGeneratorNFL_internal: DB processing throughput " << 8*dbhandler->getmaxFileBytesize()*dbhandler->getNbStream()/(end - start) << "bps" << std::endl;
  301. std::cout<<"PIRReplyGeneratorNFL_internal: Client cleartext reception throughput " << 8*dbhandler->getmaxFileBytesize()/(end - start) << "bps" << std::endl;
  302. freeQuery();
  303. }
  304. /**
  305. * Prepare reply and start absoptions.
  306. **/
  307. void PIRReplyGeneratorNFL_internal::generateReply()
  308. {
  309. lwe_in_data *in_data = input_data;
  310. lwe_cipher **inter_reply;
  311. #ifdef SHOUP
  312. lwe_query **queries;
  313. #else
  314. lwe_query *queries;
  315. #endif
  316. uint64_t old_reply_elt_nbr = 0;
  317. uint64_t reply_elt_nbr = 1;
  318. uint64_t old_poly_nbr = 1;
  319. // Allocate memory for the reply array
  320. repliesAmount = computeReplySizeInChunks(dbhandler->getmaxFileBytesize());
  321. repliesArray = (char**)calloc(repliesAmount,sizeof(char*));
  322. // Start global timers
  323. double start = omp_get_wtime();
  324. #ifdef PERF_TIMERS
  325. double vtstart = start;
  326. bool wasVerbose = false;
  327. #endif
  328. for (unsigned int i = 0 ; i < pirParam.d ; i++) // For each recursion level
  329. {
  330. old_reply_elt_nbr = reply_elt_nbr;
  331. reply_elt_nbr = 1;
  332. for (unsigned int j = i + 1 ; j < pirParam.d ; j++ ) reply_elt_nbr *= pirParam.n[j];
  333. #ifdef DEBUG
  334. cout << "PIRReplyGeneratorNFL_internal: currentMaxNbPolys = " << currentMaxNbPolys << endl;
  335. #endif
  336. inter_reply = new lwe_cipher*[reply_elt_nbr]();
  337. queries = queriesBuf[i];
  338. for (uint64_t j = 0 ; j < reply_elt_nbr ; j++) // Boucle de reply_elt_nbr PIR
  339. {
  340. inter_reply[j] = new lwe_cipher[currentMaxNbPolys];
  341. // Warning of the trick in case SHOUP is defined : we cast quesries to a (lwe_query*) and will have to uncast it
  342. generateReply((lwe_query*)queries , in_data + (pirParam.n[i] * j ), i, inter_reply[j]);
  343. #ifdef DEBUG_WITH_FILE_OUTPUT
  344. if (i ==0 && j==1) {
  345. std::ofstream file(std::string("output_level_"+ std::to_string(i)).c_str(), std::ios::out| std::ios::binary);
  346. for (int k = 0 ; k < currentMaxNbPolys ; k++)
  347. {
  348. file.write((char*)inter_reply[j][k].a,1024*2*8);
  349. }
  350. file.close();
  351. }
  352. #endif
  353. #ifdef PERF_TIMERS
  354. // Give some feedback if it takes too long
  355. double vtstop = omp_get_wtime();
  356. if (vtstop - vtstart > 1)
  357. {
  358. vtstart = vtstop;
  359. std::cout <<"PIRReplyGeneratorNFL_internal: Reply " << j+1 << "/" << reply_elt_nbr << " generated\r" << std::flush;
  360. wasVerbose = true;
  361. }
  362. #endif
  363. }
  364. /*****************/
  365. /*MEMORY CLEANING*/
  366. /*****************/
  367. if ( i > 0)
  368. {
  369. #ifdef DEBUG
  370. cout << "PIRReplyGeneratorNFL_internal: reply_elt_nbr_OLD: " << old_reply_elt_nbr << endl;
  371. #endif
  372. // for (unsigned int j = 0 ; j < old_reply_elt_nbr ; j++) {
  373. // free(in_data[j].p[0]);
  374. // free(in_data[j].p);
  375. // }
  376. // delete[] in_data;
  377. }
  378. // When i i=> 2 clean old in_data.
  379. if (i < pirParam.d - 1) {
  380. old_poly_nbr = currentMaxNbPolys;
  381. in_data = fromResulttoInData(inter_reply, reply_elt_nbr, i);
  382. }
  383. for (uint64_t j = 0 ; j < reply_elt_nbr ; j++) {
  384. for (uint64_t k = 0 ; (k < old_poly_nbr) && (i < pirParam.d - 1); k++) free(inter_reply[j][k].a);
  385. delete[] inter_reply[j];
  386. }
  387. delete[] inter_reply; // allocated with a 'new' above.
  388. }
  389. // Compute execution time
  390. printf( "PIRReplyGeneratorNFL_internal: Global reply generation took %f (omp)seconds\n", omp_get_wtime() - start);
  391. }
  392. double PIRReplyGeneratorNFL_internal::generateReplySimulation(const PIRParameters& pir_params, uint64_t plaintext_nbr)
  393. {
  394. setPirParams((PIRParameters&)pir_params);
  395. initQueriesBuffer();
  396. pushFakeQuery();
  397. importFakeData(plaintext_nbr);
  398. uint64_t repliesAmount = computeReplySizeInChunks(cryptoMethod->getPublicParameters().getCiphertextBitsize() / CHAR_BIT);
  399. repliesArray = (char**)calloc(repliesAmount,sizeof(char*));
  400. repliesIndex = 0;
  401. double start = omp_get_wtime();
  402. generateReply();
  403. double result = omp_get_wtime() - start;
  404. freeQuery();
  405. freeInputData();
  406. freeResult();
  407. delete dbhandler;
  408. return result;
  409. }
  410. double PIRReplyGeneratorNFL_internal::precomputationSimulation(const PIRParameters& pir_params, uint64_t plaintext_nbr)
  411. {
  412. NFLlib *nflptr = &(cryptoMethod->getnflInstance());
  413. setPirParams((PIRParameters&)pir_params);
  414. initQueriesBuffer();
  415. pushFakeQuery();
  416. importFakeData(plaintext_nbr);
  417. uint64_t files_nbr = 1;
  418. for (unsigned int i = 0 ; i < pir_params.d ; i++) files_nbr *= pir_params.n[i];
  419. double start = omp_get_wtime();
  420. for (unsigned int i = 0 ; i < files_nbr ; i++)
  421. {
  422. {
  423. poly64 *tmp;
  424. tmp= cryptoMethod->deserializeDataNFL((unsigned char**)(input_data[i].p), (uint64_t) plaintext_nbr, cryptoMethod->getPublicParameters().getCiphertextBitsize()/2 , input_data[i].nbPolys);
  425. free(tmp[0]);
  426. }
  427. }
  428. double result = omp_get_wtime() - start;
  429. std::cout << "PIRReplyGeneratorNFL_internal: Deserialize took " << result << " (omp)seconds" << std::endl;
  430. freeQuery();
  431. freeInputData();
  432. freeResult();
  433. delete dbhandler;
  434. return result;
  435. }
  436. /**
  437. * Multiply each query parts by each files and sum the result.
  438. * Params :
  439. * - lwe_queries* : the query ;
  440. * - lwe_in_data* : data to be processed.
  441. * - int begin_data : index where begins the data absorption
  442. * - int lvl : recursion level ;
  443. * - lwe_cipher* result : Array to store the result.
  444. **/
  445. void PIRReplyGeneratorNFL_internal::generateReply( lwe_query *queries_,
  446. lwe_in_data* data,
  447. unsigned int lvl,
  448. lwe_cipher* result)
  449. {
  450. #ifdef SHOUP
  451. lwe_query **queries=(lwe_query**)queries_;
  452. #else
  453. lwe_query *queries=queries_;
  454. #endif
  455. unsigned int query_size = pirParam.n[lvl];
  456. #ifdef PERF_TIMERS
  457. bool wasVerbose = false;
  458. double vtstart = omp_get_wtime();
  459. #endif
  460. // In order to parallelize we must ensure replies are somehow ordered
  461. // (see comment at the end of PIRReplyExtraction)
  462. //#pragma omp parallel for firstprivate(result,data, lvl, queries)
  463. #ifdef MULTI_THREAD
  464. # pragma omp parallel for
  465. #endif
  466. for (unsigned int current_poly=0 ; current_poly < currentMaxNbPolys ; current_poly++)
  467. {
  468. posix_memalign((void**) &(result[current_poly].a), 32,
  469. 2*cryptoMethod->getpolyDegree()*cryptoMethod->getnbModuli()*sizeof(uint64_t));
  470. memset(result[current_poly].a,0,
  471. 2*cryptoMethod->getpolyDegree()*cryptoMethod->getnbModuli()*sizeof(uint64_t));
  472. result[current_poly].b = (uint64_t *) result[current_poly].a +
  473. cryptoMethod->getpolyDegree()*cryptoMethod->getnbModuli();
  474. for (unsigned int offset = 0; offset < query_size; offset += 200)
  475. {
  476. for (unsigned int query_index = offset, ggg=0; query_index < query_size && ggg < 200 ;
  477. query_index++, ggg++)
  478. {
  479. #ifdef SHOUP
  480. #ifdef CRYPTO_DEBUG
  481. if(current_poly==0)
  482. {
  483. std::cout<<"Query poped.a ";NFLTools::print_poly64hex(queries[0][query_index].a,4);
  484. if (lwe)
  485. {
  486. std::cout<<"Query poped.b ";NFLTools::print_poly64hex(queries[0][query_index].b,4);
  487. }
  488. std::cout<<"Query poped.a' ";NFLTools::print_poly64hex(queries[1][query_index].a,4);
  489. if (lwe)
  490. {
  491. std::cout<<"Query poped.b' ";NFLTools::print_poly64hex(queries[1][query_index].b,4);
  492. }
  493. }
  494. #endif
  495. cryptoMethod->mulandadd(result[current_poly], data[query_index], queries[0][query_index],
  496. queries[1][query_index], current_poly, lvl);
  497. #else
  498. cryptoMethod->mulandadd(result[current_poly], data[query_index], queries[query_index],
  499. current_poly, lvl);
  500. #endif
  501. }
  502. if ( lvl == pirParam.d-1 && offset + 200 >= query_size)
  503. {
  504. // Watchout lwe_cipher.a and .b need to be allocated contiguously
  505. repliesArray[repliesIndex+current_poly] = (char*)result[current_poly].a;
  506. }
  507. #ifdef PERF_TIMERS
  508. // Give some feedback if it takes too long
  509. double vtstop = omp_get_wtime();
  510. if (vtstop - vtstart > 1)
  511. {
  512. vtstart = vtstop;
  513. if(currentMaxNbPolys != 1) std::cout <<"PIRReplyGeneratorNFL_internal: Dealt with chunk " <<
  514. current_poly+1 << "/" << currentMaxNbPolys << "\r" << std::flush;
  515. wasVerbose = true;
  516. }
  517. #endif
  518. }
  519. }
  520. #ifdef PERF_TIMERS
  521. if (wasVerbose) std::cout <<" \r" << std::flush;
  522. #endif
  523. }
  524. // New version using the multiple buffer serialize function
  525. lwe_in_data* PIRReplyGeneratorNFL_internal::fromResulttoInData(lwe_cipher** inter_reply, uint64_t reply_elt_nbr, unsigned int reply_rec_lvl)
  526. {
  527. uint64_t in_data2b_bytes = cryptoMethod->getPublicParameters().getAbsorptionBitsize()/8;
  528. uint64_t in_data2b_nbr_polys = ceil((double(currentMaxNbPolys * cryptoMethod->getPublicParameters().getCiphertextBitsize())/8.)/double(in_data2b_bytes));
  529. lwe_in_data *in_data2b = new lwe_in_data[reply_elt_nbr]();
  530. uint64_t **bufferOfBuffers = (uint64_t **) calloc(currentMaxNbPolys,sizeof(uint64_t*));
  531. //For each element in the reply
  532. for (uint64_t i = 0 ; i < reply_elt_nbr ; i++)
  533. {
  534. //Build the buffer of buffers
  535. for (uint64_t j = 0 ; j < currentMaxNbPolys ; j++)
  536. {
  537. bufferOfBuffers[j]=inter_reply[i][j].a;
  538. }
  539. // Ciphertexts can be serialized in a single block as a,b are allocatted contiguously
  540. in_data2b[i].p = cryptoMethod->deserializeDataNFL((unsigned char**)bufferOfBuffers,
  541. currentMaxNbPolys,
  542. cryptoMethod->getPublicParameters().getCiphertextBitsize(),
  543. in_data2b[i].nbPolys);
  544. //delete[] inter_reply[i]; free in generateReplyGeneric
  545. }
  546. //delete[] inter_reply;
  547. free(bufferOfBuffers);
  548. currentMaxNbPolys = in_data2b_nbr_polys;
  549. return in_data2b;
  550. }
  551. //// Original function
  552. //lwe_in_data* PIRReplyGeneratorNFL_internal::fromResulttoInData(lwe_cipher** inter_reply, uint64_t reply_elt_nbr, unsigned int reply_rec_lvl)
  553. //{
  554. // uint64_t in_data2b_bytes = cryptoMethod->getPublicParameters().getAbsorptionBitsize()/8;
  555. // uint64_t in_data2b_polys_per_reply_poly = ceil((double)(cryptoMethod->getPublicParameters().getCiphertextBitsize()/8)/in_data2b_bytes);
  556. // uint64_t in_data2b_nbr_polys = currentMaxNbPolys * in_data2b_polys_per_reply_poly;
  557. //
  558. // lwe_in_data *in_data2b = new lwe_in_data[reply_elt_nbr]();
  559. // lwe_in_data tmp_in_data;
  560. //
  561. // //For each element in the reply
  562. // for (uint64_t i = 0 ; i < reply_elt_nbr ; i++)
  563. // {
  564. // in_data2b[i].p = (poly64 *) malloc(in_data2b_nbr_polys*sizeof(poly64));
  565. // in_data2b[i].nbPolys = 0;
  566. //
  567. // // For each polynomial in a reply element
  568. // for (uint64_t j = 0 ; j < currentMaxNbPolys ; j++)
  569. // {
  570. // // Ciphertexts can be serialized in a single block as a,b are allocatted contiguously
  571. // tmp_in_data.p = cryptoMethod->deserializeDataNFL((unsigned char*)inter_reply[i][j].a, cryptoMethod->getPublicParameters().getCiphertextBitsize(), tmp_in_data.nbPolys);
  572. // for (uint64_t k = 0 ; k < in_data2b_polys_per_reply_poly; k++)
  573. // {
  574. // in_data2b[i].p[k + j * in_data2b_polys_per_reply_poly] = tmp_in_data.p[k];
  575. // }
  576. // in_data2b[i].nbPolys += in_data2b_polys_per_reply_poly;
  577. // }
  578. // delete[] inter_reply[i];
  579. // }
  580. // delete[] inter_reply;
  581. //
  582. // currentMaxNbPolys = in_data2b_nbr_polys;
  583. // return in_data2b;
  584. //}
  585. /**
  586. * Compute Reply Size une chunks.
  587. * WARNING blocking function.
  588. **/
  589. unsigned long PIRReplyGeneratorNFL_internal::computeReplySizeInChunks(unsigned long int maxFileBytesize)
  590. {
  591. using namespace GlobalConstant;
  592. unsigned int out = ceil((double)maxFileBytesize*kBitsPerByte*pirParam.alpha/cryptoMethod->getPublicParameters().getAbsorptionBitsize(0));
  593. for (unsigned int i = 1; i < pirParam.d; i++) {
  594. out = ceil(out * double(cryptoMethod->getPublicParameters().getCiphBitsizeFromRecLvl(i)/kBitsPerByte) / double(cryptoMethod->getPublicParameters().getAbsorptionBitsize(i) / kBitsPerByte));
  595. }
  596. return out;
  597. }
  598. /**
  599. * Overloaded fonction from GenericPIRReplyGenerator.
  600. * Initalise queriesBuf.
  601. **/
  602. void PIRReplyGeneratorNFL_internal::initQueriesBuffer() {
  603. const unsigned int nbQueriesBuf=pirParam.d;;
  604. #ifdef SHOUP
  605. queriesBuf = new lwe_query**[nbQueriesBuf]();
  606. for (unsigned int i = 0 ; i < nbQueriesBuf ; i++)
  607. {
  608. queriesBuf[i] = new lwe_query*[2];
  609. queriesBuf[i][0] = new lwe_query[pirParam.n[i]]();
  610. queriesBuf[i][1] = new lwe_query[pirParam.n[i]]();
  611. }
  612. #else
  613. queriesBuf = new lwe_query*[nbQueriesBuf]();
  614. for (unsigned int i = 0 ; i < nbQueriesBuf ; i++)
  615. {
  616. queriesBuf[i] = new lwe_query[pirParam.n[i]]();
  617. }
  618. #endif
  619. #ifdef DEBUG
  620. std::cout<<"Created a queriesBuf for "<<nbQueriesBuf<<" queries"<<std::endl;
  621. #endif
  622. }
  623. void PIRReplyGeneratorNFL_internal::pushFakeQuery()
  624. {
  625. char* query_element = cryptoMethod->encrypt(0, 1);
  626. for (unsigned int dim = 0 ; dim < pirParam.d ; dim++) {
  627. for(unsigned int j = 0 ; j < pirParam.n[dim] ; j++) {
  628. pushQuery(query_element, cryptoMethod->getPublicParameters().getCiphertextBitsize()/8, dim, j);
  629. }
  630. }
  631. free(query_element);
  632. }
  633. void PIRReplyGeneratorNFL_internal::pushQuery(char* rawQuery)
  634. {
  635. pushQuery(rawQuery, cryptoMethod->getPublicParameters().getCiphertextBitsize()/8, current_dim_index, current_query_index);
  636. current_query_index++;
  637. if (current_query_index >= pirParam.n[current_dim_index])
  638. {
  639. current_query_index = 0;
  640. current_dim_index++;
  641. }
  642. if (current_dim_index >= pirParam.d)
  643. {
  644. std::cout << "PIRReplyGeneratorNFL: Finished importing query (this message should appear only once)" << std::endl;
  645. }
  646. }
  647. void PIRReplyGeneratorNFL_internal::pushQuery(char* rawQuery, unsigned int size, int dim, int nbr)
  648. {
  649. unsigned int polyDegree = cryptoMethod->getpolyDegree();
  650. unsigned int nbModuli = cryptoMethod->getnbModuli();
  651. // Trick, we get both a and b at the same time, b needs to be set afterwards
  652. uint64_t *a,*b;
  653. a = (poly64) calloc(size, 1);
  654. memcpy(a,rawQuery,size);
  655. if (lwe) b = a+nbModuli*polyDegree;
  656. #ifdef CRYPTO_DEBUG
  657. std::cout<<"\nQuery received.a ";NFLTools::print_poly64(a,4);
  658. if (lwe) {std::cout<<"Query received.b ";NFLTools::print_poly64hex(b,4);}
  659. #endif
  660. #ifdef SHOUP
  661. uint64_t *ap,*bp;
  662. ap = (poly64) calloc(size, 1);
  663. if (lwe) bp = ap+nbModuli*polyDegree;
  664. for (unsigned int cm = 0 ; cm < nbModuli ; cm++)
  665. {
  666. for (unsigned i = 0 ; i < polyDegree ;i++)
  667. {
  668. ap[i+cm*polyDegree] = ((uint128_t) a[i+cm*polyDegree] << 64) / cryptoMethod->getmoduli()[cm];
  669. if (lwe) bp[i+cm*polyDegree] = ((uint128_t) b[i+cm*polyDegree] << 64) / cryptoMethod->getmoduli()[cm];
  670. }
  671. }
  672. queriesBuf[dim][0][nbr].a = a;
  673. queriesBuf[dim][0][nbr].b = b;
  674. queriesBuf[dim][1][nbr].a = ap;
  675. queriesBuf[dim][1][nbr].b = bp;
  676. #ifdef CRYPTO_DEBUG
  677. std::cout << "Query NFL pushed.a' "; NFLTools::print_poly64hex(queriesBuf[dim][1][nbr].a,4);
  678. if (lwe) { std::cout << "Query NFL pushed.b' "; NFLTools::print_poly64hex(queriesBuf[dim][1][nbr].b,4);}
  679. #endif
  680. #else
  681. queriesBuf[dim][nbr].a = a;
  682. queriesBuf[dim][nbr].b = b;
  683. #endif
  684. }
  685. size_t PIRReplyGeneratorNFL_internal::getTotalSystemMemory()
  686. {
  687. #ifdef __APPLE__
  688. int m[2];
  689. m[0] = CTL_HW;
  690. m[1] = HW_MEMSIZE;
  691. int64_t size = 0;
  692. size_t len = sizeof( size );
  693. sysctl( m, 2, &size, &len, NULL, 0 );
  694. return (size_t)size;
  695. #else
  696. long pages = /*get_phys_pages();*/sysconf(_SC_PHYS_PAGES);
  697. long page_size = /*getpagesize();*/sysconf(_SC_PAGE_SIZE);
  698. return pages * page_size;
  699. #endif
  700. }
  701. PIRReplyGeneratorNFL_internal::~PIRReplyGeneratorNFL_internal()
  702. {
  703. freeResult();
  704. }
  705. void PIRReplyGeneratorNFL_internal::setPirParams(PIRParameters& param)
  706. {
  707. pirParam = param;
  708. cryptoMethod->setandgetAbsBitPerCiphertext(pirParam.n[0]);
  709. }
  710. void PIRReplyGeneratorNFL_internal::setCryptoMethod(CryptographicSystem* cm)
  711. {
  712. //cryptoMethod = (NFLLWE*) cm;
  713. cryptoMethod = (LatticesBasedCryptosystem*) cm;
  714. lwe = (cryptoMethod->toString() == "LWE") ? true : false;
  715. }
  716. void PIRReplyGeneratorNFL_internal::freeInputData()
  717. {
  718. uint64_t theoretical_files_nbr = 1;
  719. for (unsigned int i = 0 ; i < pirParam.d ; i++) theoretical_files_nbr *= pirParam.n[i];
  720. for (unsigned int i = 0 ; i < theoretical_files_nbr ; i++){
  721. #ifdef DEBUG
  722. printf( "PIRReplyGeneratorNFL_internal: freeing input_data[%d]\n",i);
  723. #endif
  724. free(input_data[i].p[0]);
  725. free(input_data[i].p);
  726. }
  727. delete[] input_data;
  728. #ifdef DEBUG
  729. printf( "PIRReplyGeneratorNFL_internal: input_data freed\n");
  730. #endif
  731. }
  732. void PIRReplyGeneratorNFL_internal::freeQuery()
  733. {
  734. for (unsigned int i = 0; i < pirParam.d; i++)
  735. {
  736. #ifdef SHOUP
  737. for (unsigned int j = 0 ; j < pirParam.n[i] ; j++) {
  738. free(queriesBuf[i][0][j].a); //only free a because a and b and contingus, see pushQuery
  739. free(queriesBuf[i][1][j].a); //only free a because a and b and contingus, see pushQuery
  740. }
  741. delete[] queriesBuf[i][0]; //allocated in intQueriesBuf with new.
  742. delete[] queriesBuf[i][1]; //allocated in intQueriesBuf with new.
  743. delete[] queriesBuf[i];
  744. #else
  745. for (unsigned int j = 0 ; j < pirParam.n[i] ; j++) free(queriesBuf[i][j].a); //only free a because a and b and contingus, see pushQuery
  746. delete[] queriesBuf[i]; //allocated in intQueriesBuf with new.
  747. #endif
  748. }
  749. delete[] queriesBuf;//allocated in intQueriesBuf with new.
  750. #ifdef DEBUG
  751. printf( "queriesBuf freed\n");
  752. #endif
  753. }
  754. void PIRReplyGeneratorNFL_internal::freeResult()
  755. {
  756. if(repliesArray!=NULL)
  757. {
  758. for(unsigned i=0 ; i < repliesAmount; i++)
  759. {
  760. if(repliesArray[i]!=NULL) free(repliesArray[i]);
  761. repliesArray[i] = NULL;
  762. }
  763. free(repliesArray);
  764. repliesArray=NULL;
  765. }
  766. }