NFLLWE.cpp 28 KB

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