NFLLWE.cpp 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882
  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 "NFLLWE.hpp"
  18. #include "NFLLWESecurityEstimated.hpp"
  19. #include <fstream>
  20. #include <sstream>
  21. #include <string>
  22. #include <vector>
  23. #include <unistd.h>
  24. //#define bench
  25. //#define Repetition 10000
  26. void NFLLWE_DEBUG_MESSAGE(const char *s,poly64 p, unsigned int n){
  27. #ifdef CRYPTO_DEBUG
  28. std::cout<<s;
  29. NFLlib::print_poly64hex(p,n);
  30. #endif
  31. }
  32. // *********************************************************
  33. // Constructors and initialization
  34. // The constructors are not able to set all the parameters
  35. // and setNewParameters has to be called afterward,
  36. // the attribute alreadyInit reflects this uninitialized
  37. // status
  38. // *********************************************************
  39. NFLLWE::NFLLWE():
  40. LatticesBasedCryptosystem("LWE"),
  41. oldNbModuli(0),
  42. polyDegree(0)
  43. {
  44. publicParams.setcrypto_container(this);
  45. }
  46. // Expected format of the parameters
  47. // k:polyDegree:modululusBitsize:AbsorptionBitsize
  48. void NFLLWE::setNewParameters(const std::string& crypto_param_descriptor)
  49. {
  50. unsigned int polyDegree_, aggregatedModulusBitsize_;
  51. int abspc_bitsize = -1; // We don't know the absorption bit size yet
  52. std::vector<std::string> fields;
  53. boost::algorithm::split(fields, crypto_param_descriptor, boost::algorithm::is_any_of(":"));
  54. setsecurityBits(atoi(fields[1].c_str()));
  55. polyDegree_ = atoi(fields[2].c_str());
  56. aggregatedModulusBitsize_ = atoi(fields[3].c_str());
  57. // Does the fourth parameter exist ? If so set it
  58. if (fields.size() >= 5) abspc_bitsize = atoi(fields[4].c_str());
  59. setNewParameters(polyDegree_,aggregatedModulusBitsize_, abspc_bitsize);
  60. }
  61. // The setNewParameters method does the actual parameterization of the crypto object
  62. // it sets the alreadyInit attribute to reflects this
  63. void NFLLWE::setNewParameters(unsigned int polyDegree_, unsigned int aggregatedModulusBitsize_, int absPCBitsize_)
  64. {
  65. // Our public parameters need a pointer on us
  66. publicParams.setcrypto_container(this);
  67. // We still need to transfer this two attributes to the crypto_object
  68. // for the transition towards public parameter elimination
  69. publicParams.setAbsPCBitsize(absPCBitsize_);
  70. publicParams.setnoiseUB(5*getsecurityBits()/2);
  71. //#ifdef DEBUG
  72. // std::cout << "Security bits " << getsecurityBits()<<std::endl;
  73. // std::cout << "Noise UB " << publicParams.getnoiseUB()<<std::endl;
  74. //#endif
  75. // We don't use here the polyDegree setter as we would call twice NFLlib init
  76. polyDegree = polyDegree_;
  77. nflInstance.setNewParameters(polyDegree_,aggregatedModulusBitsize_);
  78. clearSecretKeys();
  79. nbModuli = nflInstance.getnbModuli();
  80. //used to free memory
  81. oldNbModuli = nbModuli;
  82. moduli= nflInstance.getmoduli();
  83. secretKey = new poly64[nbModuli];
  84. secretKeyShoup = new poly64[nbModuli];
  85. Abit_mod = new uint64_t[nbModuli];
  86. Abit_mod_shoup = new uint64_t[nbModuli];
  87. // initialize the secret key
  88. secretKey[0] = nflInstance.allocBoundedRandomPoly(0,true);
  89. for (unsigned short currentModulus = 0; currentModulus < nbModuli; currentModulus++) {
  90. secretKey[currentModulus] = secretKey[0] + polyDegree*currentModulus;
  91. secretKeyShoup[currentModulus] = (uint64_t*) calloc(polyDegree,sizeof(uint64_t));
  92. // compute the Shoup representation of the secret key
  93. for (unsigned int i=0; i < polyDegree; i++) {
  94. secretKeyShoup[currentModulus][i]=((uint128_t) secretKey[currentModulus][i] << 64) / moduli[currentModulus];
  95. }
  96. }
  97. recomputeNoiseAmplifiers();
  98. }
  99. // *********************************************************
  100. // Getters
  101. // *********************************************************
  102. poly64* NFLLWE::getsecretKey() { return secretKey; }
  103. unsigned int NFLLWE::getpolyDegree() { return polyDegree; }
  104. // *********************************************************
  105. // Setters
  106. // *********************************************************
  107. void NFLLWE::setmodulus(uint64_t modulus_)
  108. {
  109. // The modulus cannot be set from outside
  110. std::cout << "Warning(NFLLWE.c): Modulus cannot be set externally." << std::endl;
  111. }
  112. void NFLLWE::setpolyDegree(unsigned int polyDegree_)
  113. {
  114. polyDegree = polyDegree_;
  115. nflInstance.setpolyDegree(polyDegree_);
  116. }
  117. // *********************************************************
  118. // Serialize/Deserialize
  119. // *********************************************************
  120. poly64 *NFLLWE::deserializeDataNFL(unsigned char **inArrayOfBuffers, uint64_t nbrOfBuffers, uint64_t dataBitsizePerBuffer, uint64_t &polyNumber) {
  121. return nflInstance.deserializeDataNFL(inArrayOfBuffers, nbrOfBuffers, dataBitsizePerBuffer, publicParams.getAbsorptionBitsize()/polyDegree, polyNumber);
  122. }
  123. // *********************************************************
  124. // Additions and Multiplications of ciphertexts
  125. // *********************************************************
  126. void NFLLWE::add(lwe_cipher rop, lwe_cipher op1, lwe_cipher op2, int d)
  127. {
  128. nflInstance.addmodPoly(rop.a, op1.a, op2.a);
  129. nflInstance.addmodPoly(rop.b, op1.b, op2.b);
  130. }
  131. void NFLLWE::mulandadd(lwe_cipher rop, lwe_in_data op1, lwe_query op2, uint64_t current_poly, int rec_lvl)
  132. {
  133. NFLLWE_DEBUG_MESSAGE("in_data[0].p : ",op1.p[0],4);
  134. NFLLWE_DEBUG_MESSAGE("in_data[0].a : ",op2.a,4);
  135. NFLLWE_DEBUG_MESSAGE("in_data[0].b : ",op2.b,4);
  136. mulandaddCiphertextNTT(rop, op1, op2, current_poly);
  137. NFLLWE_DEBUG_MESSAGE("out_data[0].a : ",rop.a,4);
  138. NFLLWE_DEBUG_MESSAGE("out_data[0].b : ",rop.b,4);
  139. }
  140. // Shoup version
  141. void NFLLWE::mulandadd(lwe_cipher rop, const lwe_in_data op1, const lwe_query op2, const lwe_query op2prime, const uint64_t current_poly, int rec_lvl)
  142. {
  143. // Don't modify the pointers inside the data or it will be permanent
  144. poly64 ropa = rop.a, ropb = rop.b, op2a = op2.a, op2b = op2.b, op2primea = op2prime.a,
  145. op2primeb = op2prime.b, op1pcurrent = op1.p[current_poly];
  146. const unsigned int K = polyDegree;
  147. const unsigned int md = nbModuli;
  148. for(unsigned short currentModulus=0;currentModulus<md;currentModulus++)
  149. {
  150. for (unsigned i = 0; i < K; i++)
  151. {
  152. nflInstance.mulandaddShoup(ropa[i],op1pcurrent[i],op2a[i],op2primea[i],moduli[currentModulus]);
  153. }
  154. for (unsigned i = 0; i < K; i++)
  155. {
  156. nflInstance.mulandaddShoup(ropb[i],op1pcurrent[i],op2b[i],op2primeb[i],moduli[currentModulus]);
  157. }
  158. ropa+=K;
  159. ropb+=K;
  160. op1pcurrent+=K;
  161. op2a+=K;
  162. op2b+=K;
  163. op2primea+=K;
  164. op2primeb+=K;
  165. }
  166. }
  167. void NFLLWE::mul(lwe_cipher rop, const lwe_in_data op1, const lwe_query op2, const lwe_query op2prime, const uint64_t current_poly, int rec_lvl)
  168. {
  169. // Don't modify the pointers inside the data or it will be permanent
  170. poly64 ropa = rop.a, ropb = rop.b, op2a = op2.a, op2b = op2.b, op2primea = op2prime.a,
  171. op2primeb = op2prime.b, op1pcurrent = op1.p[current_poly];
  172. NFLLWE_DEBUG_MESSAGE("in_data[0].p : ",op1.p[current_poly],4);
  173. NFLLWE_DEBUG_MESSAGE("in_data[0].a : ",op2.a,4);
  174. NFLLWE_DEBUG_MESSAGE("in_data[0].b : ",op2.b,4);
  175. NFLLWE_DEBUG_MESSAGE("in_data[0].a' : ",op2prime.a,4);
  176. NFLLWE_DEBUG_MESSAGE("in_data[0].b' : ",op2.b,4);
  177. for(unsigned short currentModulus=0;currentModulus<nbModuli;currentModulus++)
  178. {
  179. for (unsigned i = 0; i < polyDegree; i++)
  180. {
  181. ropa[i] = nflInstance.mulmodShoup(op1pcurrent[i],op2a[i],op2primea[i],moduli[currentModulus]);
  182. ropb[i] = nflInstance.mulmodShoup(op1pcurrent[i],op2b[i],op2primeb[i],moduli[currentModulus]);
  183. }
  184. ropa+=polyDegree;
  185. ropb+=polyDegree;
  186. op1pcurrent+=polyDegree;
  187. op2a+=polyDegree;
  188. op2b+=polyDegree;
  189. op2primea+=polyDegree;
  190. op2primeb+=polyDegree;
  191. }
  192. NFLLWE_DEBUG_MESSAGE("out_data[0].a : ",rop.a,4);
  193. NFLLWE_DEBUG_MESSAGE("out_data[0].b : ",rop.b,4);
  194. }
  195. // Same comment as for musAndAddCiphertextNTT we do a simpler version above
  196. void NFLLWE::mulandadd(lwe_cipher rop, lwe_in_data op1, lwe_query op2, int rec_lvl)
  197. {
  198. NFLLWE_DEBUG_MESSAGE("in_data p: ",op1.p[0],4);
  199. NFLLWE_DEBUG_MESSAGE("in_data a: ",op2.a,4);
  200. NFLLWE_DEBUG_MESSAGE("in_data b: ",op2.b,4);
  201. mulandaddCiphertextNTT(rop, op1, op2);
  202. NFLLWE_DEBUG_MESSAGE("out_data.a : ",rop.a,4);
  203. NFLLWE_DEBUG_MESSAGE("out_data.b : ",rop.b,4);
  204. }
  205. // Deal just with one polynomial
  206. inline void NFLLWE::mulandaddCiphertextNTT(lwe_cipher rop, lwe_in_data op1, lwe_query op2, uint64_t current_poly)
  207. {
  208. nflInstance.mulandaddPolyNTT(rop.a, op1.p[current_poly], op2.a);
  209. nflInstance.mulandaddPolyNTT(rop.b, op1.p[current_poly], op2.b);
  210. }
  211. // Good method but too greedy in memory we start with a simpler one (below)
  212. // Needs to change as we always write in the same rop
  213. void NFLLWE::mulandaddCiphertextNTT(lwe_cipher rop, lwe_in_data op1, lwe_query op2)
  214. {
  215. for(uint64_t i=0;i<op1.nbPolys;i++)
  216. {
  217. nflInstance.mulandaddPolyNTT(rop.a, op1.p[i], op2.a);
  218. nflInstance.mulandaddPolyNTT(rop.b, op1.p[i], op2.b);
  219. }
  220. }
  221. //*********************************
  222. // Encryption and decryption
  223. //*********************************
  224. // The internal encrypt method
  225. void NFLLWE::enc(lwe_cipher *c, poly64 m)
  226. {
  227. bool uniform = true;
  228. NFLLWE_DEBUG_MESSAGE("Encrypting m: ",m, 4);
  229. c->a = (poly64) calloc(polyDegree * 2 * nbModuli, sizeof(uint64_t));
  230. c->b = c->a + polyDegree * nbModuli;
  231. // tmpa and tmpb are used to access the nbModuli polynoms of the CRT
  232. poly64 tmpa = c->a;
  233. poly64 tmpb = c->b;
  234. poly64 tmpm = m;
  235. // b = (a*s) % f + e * A + m;
  236. // Noise creation
  237. uint64_t Berr=publicParams.getnoiseUB();
  238. uint64_t A_bits= publicParams.getAbsorptionBitsize() / publicParams.getpolyDegree();
  239. // We deal with the nbModuli polynoms at once because the noise is the same size for all of them
  240. nflInstance.setBoundedRandomPoly(c->b, 2*Berr-1, !uniform);
  241. NFLLWE_DEBUG_MESSAGE("Noise used: ",c->b, 4);
  242. #ifdef CRYPTO_DEBUG
  243. std::cout << "NFLLWE: Noise amplifier: " << A_bits << std::endl;
  244. #endif
  245. // Adjustments and addition to plaintext
  246. for(unsigned short currentModulus=0;currentModulus<nbModuli;currentModulus++) {
  247. for(unsigned int i=0;i<polyDegree;i++) {
  248. // e is multiplied by the amplifier A for which we know the size A_bits
  249. // tmpb[i] = tmpb[i] << (unsigned) A_bits;
  250. // std::cout << "noise: " << tmpb[i] << std::endl;
  251. //std::cout << std::hex << tmpb[i] << " " << std::dec;
  252. tmpb[i] = nflInstance.mulmodShoup(tmpb[i], Abit_mod[currentModulus],Abit_mod_shoup[currentModulus], moduli[currentModulus]);
  253. // and shifted to be in [-(Berr-1) .. (Berr-1)]
  254. //tmpb[i] += moduli[currentModulus]-((Berr-1)<<A_bits);
  255. // We add the shifted noise to the plaintext
  256. tmpb[i] = nflInstance.addmod(tmpb[i], tmpm[i], moduli[currentModulus]);
  257. // And reduce the whole if needed
  258. if(tmpb[i]>moduli[currentModulus]) tmpb[i]-=moduli[currentModulus];
  259. }
  260. tmpb+=polyDegree;
  261. tmpm+=polyDegree;
  262. }
  263. tmpb=c->b;
  264. NFLLWE_DEBUG_MESSAGE("Amplified noise and message: ",c->b, 4);
  265. // Noise and plaintext are the only things that are not yet in the NTT space
  266. nflInstance.nttAndPowPhi(c->b);
  267. // We still have to get a. No NTT needed because uniformly taken
  268. nflInstance.setBoundedRandomPoly(tmpa, 0, uniform);
  269. #ifdef DEBUG
  270. poly64 tmp = (poly64) calloc(polyDegree*nbModuli, sizeof(uint64_t));
  271. #endif
  272. for(unsigned short currentModulus=0;currentModulus<nbModuli;currentModulus++)
  273. {
  274. // We multiply it by s and add to the previous message and noise
  275. for (unsigned int i = 0 ; i < polyDegree ; i++)
  276. {
  277. nflInstance.mulandaddShoup(tmpb[i],tmpa[i], secretKey[currentModulus][i],
  278. secretKeyShoup[currentModulus][i], moduli[currentModulus]);
  279. #ifdef DEBUG
  280. nflInstance.mulandaddShoup(tmp[i+currentModulus*polyDegree], tmpa[i],secretKey[currentModulus][i],secretKeyShoup[currentModulus][i], moduli[currentModulus]);
  281. #endif
  282. #ifdef SHOUP
  283. tmpa[i]=tmpa[i]%moduli[currentModulus];
  284. tmpb[i]=tmpb[i]%moduli[currentModulus];
  285. #endif
  286. }
  287. tmpa+=polyDegree;
  288. tmpb+=polyDegree;
  289. }
  290. // There is already a ifdef debug inside this function but
  291. // tmp is not defined if we are not in debug mode
  292. #ifdef DEBUG
  293. NFLLWE_DEBUG_MESSAGE("a*s: ",tmp, 4);
  294. free(tmp);
  295. #endif
  296. NFLLWE_DEBUG_MESSAGE("Ciphertext a: ",c->a, 4);
  297. NFLLWE_DEBUG_MESSAGE("Ciphertext b: ",c->b, 4);
  298. }
  299. void NFLLWE::dec(poly64 m, lwe_cipher *c)
  300. {
  301. uint64_t A_bits = publicParams.getAbsorptionBitsize() / publicParams.getpolyDegree();
  302. const uint64_t bitmask = (1ULL<<A_bits) -1;
  303. mpz_t moduliProduct;
  304. // Get the product of all moduli from the nflInstance object;
  305. nflInstance.copymoduliProduct(moduliProduct);
  306. // tmpa and tmpb are used to access the nbModuli polynoms of the CRT
  307. poly64 tmpa=c->a;
  308. poly64 tmpb=c->b;
  309. poly64 tmpm=m;
  310. for(unsigned short currentModulus=0;currentModulus<nbModuli;currentModulus++) {
  311. // We first get the amplified noise plus message (e*A+m =b-a*S)
  312. for (unsigned int i=0 ; i < polyDegree; i++)
  313. {
  314. uint64_t temp=0;
  315. nflInstance.mulandaddShoup(temp, tmpa[i], secretKey[currentModulus][i],
  316. secretKeyShoup[currentModulus][i], moduli[currentModulus]);
  317. tmpm[i] = nflInstance.submod(tmpb[i], temp, moduli[currentModulus]);
  318. }
  319. tmpa+=polyDegree;
  320. tmpb+=polyDegree;
  321. tmpm+=polyDegree;
  322. }
  323. tmpm=m;
  324. // In order to mask the noise bits we need to get out of NTT space through an inverse NTT
  325. nflInstance.invnttAndPowInvPhi(tmpm);
  326. NFLLWE_DEBUG_MESSAGE("Amplified noise and message (dec): ",tmpm, 4);
  327. NFLLWE_DEBUG_MESSAGE("Amplified noise and message (dec): ",tmpm+polyDegree, 4);
  328. if(nbModuli>1) {
  329. mpz_t *tmprez=nflInstance.poly2mpz(tmpm);
  330. // If e*A+m < p/2 we mask the message bits: bitmask = (1ULL<<A_bits) -1
  331. // If e *A+m > p/2 we do a little trick to avoid signed integers and modulus reduction
  332. // e[i]= e[i] + 2**61 - p (we replace p by 2**61) and then bitmask the message.
  333. mpz_t magicConstz;
  334. mpz_init(magicConstz);
  335. mpz_ui_pow_ui(magicConstz, 2, (kModulusBitsize + 1) * nbModuli);
  336. mpz_sub(magicConstz,magicConstz, moduliProduct);
  337. mpz_t bitmaskz;
  338. mpz_init(bitmaskz);
  339. mpz_ui_pow_ui(bitmaskz, 2, A_bits);
  340. mpz_sub_ui(bitmaskz, bitmaskz, 1);
  341. #ifdef CRYPTO_DEBUG
  342. gmp_printf("Mask used: %Zx\n",bitmaskz);
  343. #endif
  344. // Shall we prefetch here ?
  345. mpz_t tmpz;
  346. mpz_init(tmpz);
  347. // We need to zero tmpm as export writes nothing on the output for null values
  348. bzero(tmpm,polyDegree*nbModuli*sizeof(uint64_t));
  349. for (unsigned int i = 0 ; i < polyDegree ; i++)
  350. {
  351. //For testing we may do a hardcoded modulus but not always. m[i] = m[i] % modulus;
  352. mpz_mul_ui(tmpz, tmprez[i], 2UL);
  353. if (mpz_cmp(tmpz, moduliProduct)==1)// tmprez[i] > moduliProduct / 2
  354. {
  355. mpz_add(tmpz, tmprez[i], magicConstz);
  356. mpz_and(tmprez[i], tmpz, bitmaskz);
  357. }
  358. else
  359. {
  360. mpz_and(tmprez[i], tmprez[i], bitmaskz);
  361. }
  362. // Combien d'uint32 ?
  363. int combien = ceil((double)A_bits/32);
  364. mpz_export(((uint32_t*)tmpm)+i*combien, NULL, -1, sizeof(uint32_t), 0, 0, tmprez[i]);
  365. mpz_clear(tmprez[i]);
  366. }
  367. delete[] tmprez;
  368. mpz_clears(moduliProduct, tmpz, magicConstz, bitmaskz, NULL);
  369. } else { // nbModuli=1
  370. // If e*A+m < p/2 we mask the message bits: bitmask = (1ULL<<A_bits) -1
  371. // If e*A+m > p/2 we do a little trick to avoid signed integers and modulus reduction
  372. // e[i]= e[i] + 2**61 - p (we replace p by 2**61) and then bitmask the message.
  373. const uint64_t magicConst = (1ULL<<61)-moduli[0];// 2**61 - p
  374. // Shall we prefetch here ?
  375. for (unsigned int i = 0 ; i < polyDegree ; i++)
  376. {
  377. //For testing we may do a hardcoded modulus but not always. m[i] = m[i] % modulus;
  378. tmpm[i] = (tmpm[i] > moduli[0]/2) ? (tmpm[i] + magicConst)& bitmask : tmpm[i] & bitmask;
  379. }
  380. }
  381. }
  382. // MOK is here for the CRT modification
  383. // encrypts a uint (e.g. for producing a equest element with a 0 or a 1)
  384. // does not return a lwe_cipher but the (char*)pointer on two consecutively allocated poly64 (a and b)
  385. char* NFLLWE::encrypt(unsigned int ui, unsigned int d)
  386. {
  387. if ( ceil(log2(static_cast<double>(ui))) >= publicParams.getAbsorptionBitsize())
  388. {
  389. std::cerr << "NFFLWE: The given unsigned int does not fit in " << publicParams.getAbsorptionBitsize() << " bits"<< std::endl;
  390. ui %= 1<<publicParams.getAbsorptionBitsize();
  391. }
  392. lwe_cipher c;
  393. poly64 m = (poly64)calloc(nbModuli*polyDegree,sizeof(uint64_t));
  394. for (unsigned int cm = 0 ; cm < nbModuli ; cm++)
  395. {
  396. m[cm*polyDegree]=(uint64_t)ui;
  397. }
  398. enc(&c,m);
  399. free(m);
  400. return (char*) c.a;
  401. }
  402. char* NFLLWE::encrypt(char* data, size_t s, unsigned int exponent ){
  403. std::cerr << "char* NFLLWE::encrypt(char* data, size_t, unsigned int exponent) is not implemented"<< std::endl;
  404. return nullptr;
  405. }
  406. // Do a ciphertext for a plaintext with alternating bits (for performance tests)
  407. char* NFLLWE::encrypt_perftest()
  408. {
  409. lwe_cipher c;
  410. poly64 m = nflInstance.allocBoundedRandomPoly(0, true);
  411. enc(&c,m);
  412. free(m);
  413. return (char*) c.a;
  414. }
  415. char* NFLLWE::decrypt(char* cipheredData, unsigned int rec_lvl, size_t, size_t)
  416. {
  417. lwe_cipher ciphertext;
  418. ciphertext.a = (poly64)cipheredData;
  419. ciphertext.b = ciphertext.a + nbModuli * polyDegree;
  420. poly64 clear_data = (poly64) calloc(nbModuli * polyDegree, sizeof(uint64_t));
  421. unsigned int bits_per_coordinate = publicParams.getAbsorptionBitsize()/polyDegree;
  422. #ifdef DEBUG
  423. std::cout<<"Allocated (bytes): "<<nbModuli * polyDegree * sizeof(uint64_t)<<std::endl;
  424. std::cout<<"Bits per coordinate: "<<bits_per_coordinate<<std::endl;
  425. #endif
  426. dec(clear_data, &ciphertext);
  427. NFLLWE_DEBUG_MESSAGE("Decrypting ciphertext a: ",ciphertext.a, 4);
  428. NFLLWE_DEBUG_MESSAGE("Decrypting ciphertext b: ",ciphertext.b, 4);
  429. NFLLWE_DEBUG_MESSAGE("Result: ",clear_data, 4);
  430. // unsigned char* out_data = (unsigned char*) calloc(nbModuli * polyDegree+1, sizeof(uint64_t));
  431. // nflInstance.serializeData64 (clear_data, out_data, bits_per_coordinate, polyDegree);
  432. unsigned char* out_data = (unsigned char*) calloc(bits_per_coordinate*polyDegree/64 + 1, sizeof(uint64_t));
  433. if (nbModuli == 1)
  434. {
  435. nflInstance.serializeData64(clear_data, out_data, bits_per_coordinate, ceil((double)bits_per_coordinate/64)* polyDegree);
  436. }
  437. else // nbModuli > 1
  438. {
  439. nflInstance.serializeData32 ((uint32_t*)clear_data, out_data, bits_per_coordinate, ceil((double)bits_per_coordinate/32)* polyDegree);
  440. }
  441. #ifdef DEBUG
  442. //std::cout<<"Bitgrouped into: "<<out_data<<std::endl;
  443. #endif
  444. free(clear_data);
  445. return (char*) out_data;
  446. }
  447. unsigned int NFLLWE::getAllCryptoParams(std::set<std::string>& crypto_params)
  448. {
  449. unsigned int params_nbr = 0;
  450. unsigned int k_array_size = 5;
  451. unsigned int k[5] = {80, 100, 128, 192, 256};
  452. for (unsigned int i = 0 ; i < k_array_size ; i++)
  453. {
  454. params_nbr += getCryptoParams(k[i], crypto_params);
  455. }
  456. return params_nbr;
  457. }
  458. unsigned int NFLLWE::getCryptoParams(unsigned int k, std::set<std::string>& crypto_params)
  459. {
  460. using namespace std;
  461. unsigned int p_size, params_nbr = 0;
  462. for (unsigned int degree = kMinPolyDegree ; degree <= kMaxPolyDegree; degree <<= 1)
  463. {
  464. string param;
  465. p_size = findMaxModulusBitsize(k, degree);
  466. for (unsigned int i = 1; i * kModulusBitsize <= p_size && i * kModulusBitsize <= kMaxAggregatedModulusBitsize; i++)
  467. {
  468. param = cryptoName + ":" + to_string(estimateSecurity(degree,i*kModulusBitsize)) + ":" + to_string(degree) + ":" + to_string(i*kModulusBitsize) ;
  469. if (crypto_params.insert(param).second) params_nbr++;
  470. param = "";
  471. }
  472. }
  473. return params_nbr;
  474. }
  475. void NFLLWE::recomputeNoiseAmplifiers() {
  476. uint64_t A_bits= publicParams.getAbsorptionBitsize() / publicParams.getpolyDegree();
  477. mpz_t tmpz1,tmpz2;
  478. mpz_init(tmpz1);
  479. mpz_init(tmpz2);
  480. for(unsigned short currentModulus=0;currentModulus<nbModuli;currentModulus++) {
  481. mpz_ui_pow_ui(tmpz1, 2, A_bits);
  482. mpz_import(tmpz2, 1, 1, sizeof(uint64_t), 0, 0, moduli+currentModulus);
  483. mpz_mod(tmpz1, tmpz1, tmpz2);
  484. Abit_mod[currentModulus]=0;
  485. mpz_export(&Abit_mod[currentModulus], NULL, 1, sizeof(uint64_t), 0, 0, tmpz1);
  486. Abit_mod_shoup[currentModulus]=((uint128_t) Abit_mod[currentModulus] << 64) / moduli[currentModulus];
  487. }
  488. mpz_clears(tmpz1, tmpz2, NULL);
  489. }
  490. unsigned int NFLLWE::estimateSecurity(unsigned int n, unsigned int p_size)
  491. {
  492. using namespace std;
  493. // Read the string that contains security parameters
  494. istringstream estimations(securityParameters);
  495. // Initilaze vectors that will contain XPIR parameters and the security number of bits
  496. vector<unsigned int> nParameters;
  497. vector<unsigned int> qParameters;
  498. vector<unsigned int> nbrBits;
  499. string line;
  500. int i(0);
  501. // Read lines
  502. while(getline(estimations,line)){
  503. // Find the two positions of ':' to split the line
  504. int posPoint1=line.find(':',0);
  505. int posPoint2=line.find(':',posPoint1+1);
  506. // Add the n parameter to the vector
  507. unsigned int nData=atoi(line.substr(0,posPoint1).c_str());
  508. nParameters.push_back(nData);
  509. // Add the q parameter to the vector
  510. unsigned int qData=atoi(line.substr(posPoint1+1,posPoint2-(posPoint1+1)).c_str());
  511. qParameters.push_back(qData);
  512. // Add the number of bits to the vector
  513. unsigned int nbrBitsData=atoi(line.substr(posPoint2+1,line.size()-(posPoint2+1)).c_str());
  514. nbrBits.push_back(nbrBitsData);
  515. }
  516. // Initialize the estimation at 0
  517. unsigned int estimated_k(0);
  518. // Check all the n and q parmaters to find a correspondence with the inputs parameters
  519. for(int i(0); i<nbrBits.size(); i++){
  520. // Estimation takes the number of bits at the rank of the correspondence
  521. if(n==nParameters[i] && p_size==qParameters[i]){
  522. estimated_k=nbrBits[i];
  523. }
  524. }
  525. return estimated_k;
  526. }
  527. long NFLLWE::setandgetAbsBitPerCiphertext(unsigned int elt_nbr)
  528. {
  529. double Berr = static_cast<double>(publicParams.getnoiseUB());
  530. double nb_sum = elt_nbr;
  531. double p_size = getmodulusBitsize();
  532. double nbr_bit = floor(( (p_size - 1) - log2(nb_sum) - log2(Berr) -log2(static_cast<double>(polyDegree))) / 2.0);
  533. publicParams.setAbsPCBitsize(nbr_bit);
  534. recomputeNoiseAmplifiers();
  535. return long(nbr_bit);
  536. }
  537. unsigned int NFLLWE::findMaxModulusBitsize(unsigned int k, unsigned int n)
  538. {
  539. unsigned int p_size;
  540. //p_size can not be too low
  541. p_size = kModulusBitsize;
  542. while (!checkParamsSecure(k,n,p_size)) p_size+=kModulusBitsize;
  543. return p_size-kModulusBitsize;
  544. }
  545. bool NFLLWE::checkParamsSecure(unsigned int k, unsigned int n, unsigned int p_size)
  546. {
  547. return (estimateSecurity(n,p_size)<=k);
  548. }
  549. double NFLLWE::lllOutput(unsigned int n, double& p, double delta)
  550. {
  551. double m = 2*n + 128;
  552. //execution log(time) = 1.8/ log(delta) − 110 and -80 to compute processor cycles. We add a margin of 20 so we take k/2 = 1.8/log(delta) - 100
  553. double lll1 = pow(delta, m) * pow(p, n/m);
  554. double lll2 = 2 * sqrt(n * log2(p) * log2(delta));
  555. lll2 = pow(2, lll2);
  556. return std::min(lll1, lll2);
  557. }
  558. double NFLLWE::estimateAbsTime(std::string crypto_param)
  559. {
  560. using namespace std;
  561. vector<string> fields;
  562. boost::algorithm::split(fields, crypto_param, boost::algorithm::is_any_of(":"));
  563. unsigned int p_size = (unsigned) atoi(fields[3].c_str());
  564. double a = (p_size < 64) ? 1 : ceil(static_cast<double>(p_size)/64.0);
  565. unsigned int degree = (unsigned) atoi(fields[2].c_str());
  566. double b = degree/1024;
  567. return 1/(1.75 * pow(10, 5)/(a*b));
  568. }
  569. double NFLLWE::estimatePrecomputeTime(std::string crypto_param)
  570. {
  571. using namespace std;
  572. vector<string> fields;
  573. boost::algorithm::split(fields, crypto_param, boost::algorithm::is_any_of(":"));
  574. unsigned int p_size = (unsigned) atoi(fields[3].c_str());
  575. double a = (p_size < 64) ? 1 : ceil(static_cast<double>(p_size)/64.0);
  576. unsigned int degree = (unsigned) atoi(fields[2].c_str());
  577. double b = degree/1024;
  578. return 1/(0.75*pow(10, 5)/(a*b));
  579. }
  580. unsigned int NFLLWE::getmodulusBitsize() {
  581. return nbModuli*kModulusBitsize;
  582. }
  583. // *********************************************************
  584. // AbstractPublicParameters stuff
  585. // *********************************************************
  586. AbstractPublicParameters& NFLLWE::getPublicParameters()
  587. {
  588. //This was bug chasing but should not be necessary!
  589. publicParams.setcrypto_container(this);
  590. return publicParams;
  591. }
  592. std::string NFLLWE::getSerializedCryptoParams(bool shortversion)
  593. {
  594. return publicParams.getSerializedParams(shortversion);
  595. }
  596. NFLLWE::~NFLLWE()
  597. {
  598. clearSecretKeys();
  599. }
  600. std::string& NFLLWE::toString()
  601. {
  602. return cryptoName;
  603. }
  604. void NFLLWE::clearSecretKeys()
  605. {
  606. if(oldNbModuli)
  607. {
  608. // secreKey was allocated with a single allocation
  609. delete[] Abit_mod;
  610. delete[] Abit_mod_shoup;
  611. free(secretKey[0]);
  612. delete[] secretKey;
  613. }
  614. if(oldNbModuli)
  615. {
  616. for (unsigned int i = 0; i < oldNbModuli; i++) {
  617. free(secretKeyShoup[i]);
  618. }
  619. delete[] secretKeyShoup;
  620. }
  621. oldNbModuli = 0;
  622. }
  623. //This main is for benchmarking and tests
  624. //
  625. // int main(int c,char **v) {
  626. //
  627. // // Benchs et correctness enc/dec
  628. // NFLLWE n;
  629. // n.setNewParameters(1024,64,22);
  630. // n.setmodulus(P64);
  631. // n.getPublicParameters().computeNewParameters("lwe:80:1024:64:22");
  632. //
  633. // poly64 p=n.boundedRandomPoly(1024, 1023);
  634. // poly64 result=(poly64)calloc(1024,sizeof(uint64_t));
  635. //
  636. // std::cout<<"0-RND polynom: ";n.print_poly64(p,4);std::cout<<std::endl;
  637. //
  638. //
  639. // lwe_cipher cyph;
  640. // #ifdef bench
  641. // double start = omp_get_wtime();
  642. // for(int i = 0;i<Repetition;i++) {
  643. // #endif
  644. // n.enc(&cyph,p);
  645. // #ifdef bench
  646. //
  647. // }
  648. // double end = omp_get_wtime();
  649. // std::cout<<Repetition/(end-start)<<" chiffre/s"<<std::endl;
  650. //
  651. //
  652. // start = omp_get_wtime();
  653. // for(int i = 0;i<Repetition;i++) {
  654. // #endif
  655. //
  656. // n.dec(result,&cyph);
  657. // #ifdef bench
  658. // }
  659. // end = omp_get_wtime();
  660. // std::cout<<Repetition/(end-start)<<" dechiffre/s"<<std::endl;
  661. // #endif
  662. // NFLLWE_DEBUG_MESSAGE("Encrypted into a",cyph.a,4);
  663. // NFLLWE_DEBUG_MESSAGE("Encrypted into b",cyph.b,4);
  664. // NFLLWE_DEBUG_MESSAGE("1-Encoded-Decoded (but not unshoupified): ",result,4);
  665. //
  666. //
  667. // for(int i = 0;i<1024;i++) {
  668. // if((result[i]%P64)!=(result[i]%P64)) {
  669. // std::cout<<"err "<<(p[i])<<" != "<<(result[i]%P64)<<std::endl;
  670. // exit(1);
  671. // break;
  672. // }
  673. // }
  674. //
  675. // std::cout<< "enc/dec test passed"<<std::endl;
  676. //
  677. //
  678. //
  679. // // int bytesize=1024*22/8+1;
  680. // // char* mydata=(char*)calloc(bytesize,1);
  681. // // for(int i=0;i<bytesize;i++) {
  682. // // mydata[i]='A'+(i%('Z'-'A'));
  683. // // }
  684. // // std::cout<<"Initial data : "<<mydata<<std::endl;
  685. // //
  686. // // uint64_t bitsize=bytesize*8;
  687. // // uint64_t nbOfPolys;
  688. // // Warning, need to tranform this line with the new version of deserializeDataNTT which takes 4 parameters instead of 3 poly64 *mydata_poly=n.deserializeDataNTT((unsigned char*)mydata,bitsize,nbOfPolys);
  689. // //
  690. // // std::cout<<"The string has been encoded into ";n.print_poly64hex(*mydata_poly,1024*nbOfPolys);
  691. // // std::cout<<std::endl<<"nbOfPolys = "<<nbOfPolys<<std::endl;
  692. // //
  693. // // // encrypt of poly64 simulation
  694. // // lwe_cipher *cyphertext=new lwe_cipher[nbOfPolys];
  695. // // for(int i=0;i<nbOfPolys;i++) {
  696. // // n.enc(&(cyphertext[i]),*(mydata_poly + i*1024));
  697. // // //std::cout<<"The string has been cyphered into a["<<i<<"]";n.print_poly64(cyphertext[i].a,1024);
  698. // // //std::cout<<"The string has been cyphered into b["<<i<<"]";n.print_poly64(cyphertext[i].a,1024);
  699. // // }
  700. // //
  701. // // poly64 unciphereddata_poly[nbOfPolys];// = (poly64*)calloc(1024*nbOfPolys,sizeof(uint64_t));
  702. // // for(int i=0;i<nbOfPolys;i++) {
  703. // // unciphereddata_poly[i]=(poly64)n.decrypt((char*)(cyphertext[i].a), (unsigned int)0,(size_t) 0,(size_t) 0);
  704. // // std::cout<<"Decoded into polynom: ";n.print_poly64hex((poly64)unciphereddata_poly[i],128);std::cout<<std::endl;
  705. // // }
  706. // //
  707. // //
  708. // // unsigned char* unciphereddata=n.serializeData(unciphereddata_poly[0], nbOfPolys,bitsize, true);
  709. // //
  710. // // std::cout<<"Decoded into "<<std::hex<<unciphereddata<<std::endl;
  711. // // std::cout<<"A= "<<std::dec<<(short)'A'<<std::endl<<std::endl;
  712. // // std::cout<<"G= "<<std::dec<<(short)'G'<<std::endl<<std::endl;
  713. // //
  714. // //
  715. // //
  716. // // //lwe_cipher *cypherui;
  717. // // //cypherui=(lwe_cipher *)n.encrypt(1,0);
  718. // // //unciphereddata_poly = (poly64)n.decrypt((char*)(cypherui->a), (unsigned int)0,(size_t) 0,(size_t) 0);
  719. // // char *charptr;
  720. // // charptr=n.encrypt(1,0);
  721. // // unciphereddata_poly = (poly64)n.decrypt(charptr, (unsigned int)0,(size_t) 0,(size_t) 0);
  722. // // std::cout<<"1-Decoded into polynom: ";n.print_poly64(unciphereddata_poly,1024);std::cout<<std::endl;
  723. // // std::cout<<"Decoded into "<<std::hex<<unciphereddata_poly<<std::endl;
  724. // }