pir.cpp 8.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293
  1. #include "pir.hpp"
  2. using namespace std;
  3. using namespace seal;
  4. using namespace seal::util;
  5. vector<uint64_t> get_dimensions(uint64_t plaintext_num, uint32_t d) {
  6. assert(d > 0);
  7. assert(plaintext_num > 0);
  8. vector<uint64_t> dimensions(d);
  9. for (uint32_t i = 0; i < d; i++) {
  10. dimensions[i] = std::max((uint32_t) 2, (uint32_t) floor(pow(plaintext_num, 1.0/d)));
  11. }
  12. uint32_t product = 1;
  13. uint32_t j = 0;
  14. // if plaintext_num is not a d-power
  15. if ((double) dimensions[0] != pow(plaintext_num, 1.0 / d)) {
  16. while (product < plaintext_num && j < d) {
  17. product = 1;
  18. dimensions[j++]++;
  19. for (uint32_t i = 0; i < d; i++) {
  20. product *= dimensions[i];
  21. }
  22. }
  23. }
  24. return dimensions;
  25. }
  26. void gen_params(uint64_t ele_num, uint64_t ele_size, uint32_t N, uint32_t logt,
  27. uint32_t d, EncryptionParameters &params, EncryptionParameters &expanded_params,
  28. PirParams &pir_params) {
  29. // Determine the maximum size of each dimension
  30. uint32_t logtp = plainmod_after_expansion(logt, N, d, ele_num, ele_size);
  31. uint64_t plain_mod = static_cast<uint64_t>(1) << logt;
  32. uint64_t expanded_plain_mod = static_cast<uint64_t>(1) << logtp;
  33. uint64_t plaintext_num = plaintexts_per_db(logtp, N, ele_num, ele_size);
  34. #ifdef DEBUG
  35. cout << "log(plain mod) before expand = " << logt << endl;
  36. cout << "log(plain mod) after expand = " << logtp << endl;
  37. cout << "number of FV plaintexts = " << plaintext_num << endl;
  38. #endif
  39. vector<SmallModulus> coeff_mod_array;
  40. uint32_t logq = 0;
  41. for (uint32_t i = 0; i < 1; i++) {
  42. coeff_mod_array.emplace_back(SmallModulus());
  43. coeff_mod_array[i] = small_mods_60bit(i);
  44. logq += coeff_mod_array[i].bit_count();
  45. }
  46. params.set_poly_modulus("1x^" + to_string(N) + " + 1");
  47. params.set_coeff_modulus(coeff_mod_array);
  48. params.set_plain_modulus(plain_mod);
  49. expanded_params.set_poly_modulus("1x^" + to_string(N) + " + 1");
  50. expanded_params.set_coeff_modulus(coeff_mod_array);
  51. expanded_params.set_plain_modulus(expanded_plain_mod);
  52. vector<uint64_t> nvec = get_dimensions(plaintext_num, d);
  53. uint32_t expansion_ratio = 0;
  54. for (uint32_t i = 0; i < params.coeff_modulus().size(); ++i) {
  55. double logqi = log2(params.coeff_modulus()[i].value());
  56. expansion_ratio += ceil(logqi / logtp);
  57. }
  58. pir_params.d = d;
  59. pir_params.dbc = 6;
  60. pir_params.n = plaintext_num;
  61. pir_params.nvec = nvec;
  62. pir_params.expansion_ratio = expansion_ratio << 1;
  63. }
  64. void update_params(uint64_t ele_num, uint64_t ele_size, uint32_t d,
  65. const EncryptionParameters &old_params, EncryptionParameters &expanded_params,
  66. PirParams &pir_params) {
  67. uint32_t logt = ceil(log2(old_params.plain_modulus().value()));
  68. uint32_t N = old_params.poly_modulus().coeff_count() - 1;
  69. // Determine the maximum size of each dimension
  70. uint32_t logtp = plainmod_after_expansion(logt, N, d, ele_num, ele_size);
  71. uint64_t expanded_plain_mod = static_cast<uint64_t>(1) << logtp;
  72. uint64_t plaintext_num = plaintexts_per_db(logtp, N, ele_num, ele_size);
  73. #ifdef DEBUG
  74. cout << "log(plain mod) before expand = " << logt << endl;
  75. cout << "log(plain mod) after expand = " << logtp << endl;
  76. cout << "number of FV plaintexts = " << plaintext_num << endl;
  77. #endif
  78. expanded_params.set_poly_modulus(old_params.poly_modulus());
  79. expanded_params.set_coeff_modulus(old_params.coeff_modulus());
  80. expanded_params.set_plain_modulus(expanded_plain_mod);
  81. // Assumes dimension of database is 2
  82. vector<uint64_t> nvec = get_dimensions(plaintext_num, d);
  83. uint32_t expansion_ratio = 0;
  84. for (uint32_t i = 0; i < old_params.coeff_modulus().size(); ++i) {
  85. double logqi = log2(old_params.coeff_modulus()[i].value());
  86. expansion_ratio += ceil(logqi / logtp);
  87. }
  88. pir_params.d = d;
  89. pir_params.dbc = 6;
  90. pir_params.n = plaintext_num;
  91. pir_params.nvec = nvec;
  92. pir_params.expansion_ratio = expansion_ratio << 1;
  93. }
  94. uint32_t plainmod_after_expansion(uint32_t logt, uint32_t N, uint32_t d,
  95. uint64_t ele_num, uint64_t ele_size) {
  96. // Goal: find max logtp such that logtp + ceil(log(ceil(d_root(n)))) <= logt
  97. // where n = ceil(ele_num / floor(N*logtp / ele_size *8))
  98. for (uint32_t logtp = logt; logtp >= 2; logtp--) {
  99. uint64_t n = plaintexts_per_db(logtp, N, ele_num, ele_size);
  100. if (logtp == logt && n == 1) {
  101. return logtp - 1;
  102. }
  103. if ((double)logtp + ceil(log2(ceil(pow(n, 1.0/(double)d)))) <= logt) {
  104. return logtp;
  105. }
  106. }
  107. assert(0); // this should never happen
  108. return logt;
  109. }
  110. // Number of coefficients needed to represent a database element
  111. uint64_t coefficients_per_element(uint32_t logtp, uint64_t ele_size) {
  112. return ceil(8 * ele_size / (double)logtp);
  113. }
  114. // Number of database elements that can fit in a single FV plaintext
  115. uint64_t elements_per_ptxt(uint32_t logtp, uint64_t N, uint64_t ele_size) {
  116. uint64_t coeff_per_ele = coefficients_per_element(logtp, ele_size);
  117. uint64_t ele_per_ptxt = N / coeff_per_ele;
  118. assert(ele_per_ptxt > 0);
  119. return ele_per_ptxt;
  120. }
  121. // Number of FV plaintexts needed to represent the database
  122. uint64_t plaintexts_per_db(uint32_t logtp, uint64_t N, uint64_t ele_num, uint64_t ele_size) {
  123. uint64_t ele_per_ptxt = elements_per_ptxt(logtp, N, ele_size);
  124. return ceil((double)ele_num / ele_per_ptxt);
  125. }
  126. vector<uint64_t> bytes_to_coeffs(uint32_t limit, const uint8_t *bytes, uint64_t size) {
  127. uint64_t size_out = coefficients_per_element(limit, size);
  128. vector<uint64_t> output(size_out);
  129. uint32_t room = limit;
  130. uint64_t *target = &output[0];
  131. for (uint32_t i = 0; i < size; i++) {
  132. uint8_t src = bytes[i];
  133. uint32_t rest = 8;
  134. while (rest) {
  135. if (room == 0) {
  136. target++;
  137. room = limit;
  138. }
  139. uint32_t shift = rest;
  140. if (room < rest) {
  141. shift = room;
  142. }
  143. *target = *target << shift;
  144. *target = *target | (src >> (8 - shift));
  145. src = src << shift;
  146. room -= shift;
  147. rest -= shift;
  148. }
  149. }
  150. *target = *target << room;
  151. return output;
  152. }
  153. void coeffs_to_bytes(uint32_t limit, const Plaintext &coeffs, uint8_t *output, uint32_t size_out) {
  154. uint32_t room = 8;
  155. uint32_t j = 0;
  156. uint8_t *target = output;
  157. for (uint32_t i = 0; i < coeffs.coeff_count(); i++) {
  158. uint64_t src = coeffs[i];
  159. uint32_t rest = limit;
  160. while (rest && j < size_out) {
  161. uint32_t shift = rest;
  162. if (room < rest) {
  163. shift = room;
  164. }
  165. target[j] = target[j] << shift;
  166. target[j] = target[j] | (src >> (limit - shift));
  167. src = src << shift;
  168. room -= shift;
  169. rest -= shift;
  170. if (room == 0) {
  171. j++;
  172. room = 8;
  173. }
  174. }
  175. }
  176. }
  177. void vector_to_plaintext(const vector<uint64_t> &coeffs, Plaintext &plain) {
  178. uint32_t coeff_count = coeffs.size();
  179. plain.resize(coeff_count);
  180. util::set_uint_uint(coeffs.data(), coeff_count, plain.data());
  181. }
  182. vector<uint64_t> compute_indices(uint64_t desiredIndex, vector<uint64_t> Nvec) {
  183. uint32_t num = Nvec.size();
  184. uint64_t product = 1;
  185. for (uint32_t i = 0; i < num; i++) {
  186. product *= Nvec[i];
  187. }
  188. uint64_t j = desiredIndex;
  189. vector<uint64_t> result;
  190. for (uint32_t i = 0; i < num; i++) {
  191. product /= Nvec[i];
  192. uint64_t ji = j / product;
  193. result.push_back(ji);
  194. j -= ji * product;
  195. }
  196. return result;
  197. }
  198. inline Ciphertext deserialize_ciphertext(string s) {
  199. Ciphertext c;
  200. std::stringstream input(std::ios::binary | std::ios::in);
  201. input.str(s);
  202. c.load(input);
  203. return c;
  204. }
  205. vector<Ciphertext> deserialize_ciphertexts(uint32_t count, string s, uint32_t len_ciphertext) {
  206. vector<Ciphertext> c;
  207. for (uint32_t i = 0; i < count; i++) {
  208. c.push_back(deserialize_ciphertext(s.substr(i * len_ciphertext, len_ciphertext)));
  209. }
  210. return c;
  211. }
  212. inline string serialize_ciphertext(Ciphertext c) {
  213. std::stringstream output(std::ios::binary | std::ios::out);
  214. c.save(output);
  215. return output.str();
  216. }
  217. string serialize_ciphertexts(vector<Ciphertext> c) {
  218. string s;
  219. for (uint32_t i = 0; i < c.size(); i++) {
  220. s.append(serialize_ciphertext(c[i]));
  221. }
  222. return s;
  223. }
  224. string serialize_galoiskeys(GaloisKeys g) {
  225. std::stringstream output(std::ios::binary | std::ios::out);
  226. g.save(output);
  227. return output.str();
  228. }
  229. GaloisKeys *deserialize_galoiskeys(string s) {
  230. GaloisKeys *g = new GaloisKeys();
  231. std::stringstream input(std::ios::binary | std::ios::in);
  232. input.str(s);
  233. g->load(input);
  234. return g;
  235. }