symmetric_encryption_with_prng.h 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113
  1. /*
  2. * Copyright 2018 Google LLC.
  3. * Licensed under the Apache License, Version 2.0 (the "License");
  4. * you may not use this file except in compliance with the License.
  5. * You may obtain a copy of the License at
  6. *
  7. * https://www.apache.org/licenses/LICENSE-2.0
  8. *
  9. * Unless required by applicable law or agreed to in writing, software
  10. * distributed under the License is distributed on an "AS IS" BASIS,
  11. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. * See the License for the specific language governing permissions and
  13. * limitations under the License.
  14. */
  15. // Implementation of compressed ciphertexts.
  16. //
  17. // In the RLWE encryption scheme, the second component of the ciphertext, a, is
  18. // drawn uniformly at random (that is, each coefficient is drawn uniformly at
  19. // random). If we the second components of a series of ciphertexts are
  20. // constructed using the pseudorandom outputs of a PRNG, the second components
  21. // can be encoded using the PRNG's seed, which is the functionality provided
  22. // here.
  23. //
  24. // An important note is that the order of encrypting the ciphertexts is
  25. // important. When decompressing, the order of the ciphertexts must be given in
  26. // the exact same order that the ciphertexts were encrypted to ensure the same
  27. // random polynomials are constructed for the correct ciphertext. Since a party
  28. // without the private key will be decompressing, it is impossible to check if
  29. // the decompressions were performed properly.
  30. #ifndef RLWE_SYMMETRIC_ENCRYPTION_WITH_PRNG_H_
  31. #define RLWE_SYMMETRIC_ENCRYPTION_WITH_PRNG_H_
  32. #include <vector>
  33. #include "polynomial.h"
  34. #include "prng/integral_prng_types.h"
  35. #include "prng/prng.h"
  36. #include "status_macros.h"
  37. #include "statusor.h"
  38. #include "symmetric_encryption.h"
  39. namespace rlwe {
  40. // Encrypts a set of plaintexts using randomness-of-encryption sampled using the
  41. // specified PRNG.
  42. //
  43. // When encrypting a plaintext, the c0 component of a ciphertext incorporates a
  44. // polynomial "a" where each coefficient is drawn uniformly and independently at
  45. // random. The c1 component of the ciphertext is exactly "-a" to ensure
  46. // homomorphic operations and decryption may occur. Instead of sending "a"
  47. // explicitly, we may construct "a" using the seed of a pseudorandom number
  48. // generator. Then, we may simply send the seed used to generate all "a"s
  49. // together with only the c0 components of each ciphertext. This would allow the
  50. // server to replay the PRNG and recover all "a"s and thereby reconstruct the
  51. // c1 components of the ciphertexts. As a result, the required communication
  52. // would be cut almost in half.
  53. //
  54. // Note, the c0 components of the ciphertext have an additional error vector
  55. // added to them. This error vector is drawn separately from the PRNG used to
  56. // compute all "a"s. The error vector remaining hidden is important for
  57. // security.
  58. //
  59. // Importantly, the order of the compressed ciphertexts must remain static
  60. // before decompression. Otherwise, the decompression will be incorrect.
  61. //
  62. // Two PRNGs are being passed: one is used to sample random polynomials that
  63. // is required to be used for decryption. The other PRNG is used to sample error
  64. // that does not need to be used for decryption.
  65. template <typename ModularInt>
  66. rlwe::StatusOr<std::vector<Polynomial<ModularInt>>> EncryptWithPrng(
  67. const SymmetricRlweKey<ModularInt>& key,
  68. const std::vector<Polynomial<ModularInt>>& plaintexts, SecurePrng* prng,
  69. SecurePrng* prng_encryption) {
  70. std::vector<Polynomial<ModularInt>> c0s(plaintexts.size());
  71. for (int i = 0; i < c0s.size(); ++i) {
  72. RLWE_ASSIGN_OR_RETURN(auto a, SamplePolynomialFromPrng<ModularInt>(
  73. key.Len(), prng, key.ModulusParams()));
  74. RLWE_ASSIGN_OR_RETURN(
  75. c0s[i], internal::Encrypt(key, plaintexts[i], a, prng_encryption));
  76. }
  77. return c0s;
  78. }
  79. // Given a list of compressed encryption and the seed of the PRNG used for
  80. // compression, this function will decompress the encryptions so the ciphertexts
  81. // can now be used in homomorphic operations.
  82. //
  83. // The compressed ciphertexts must be given in the same order as they were given
  84. // to be encrypted.
  85. template <typename ModularInt>
  86. rlwe::StatusOr<std::vector<SymmetricRlweCiphertext<ModularInt>>> ExpandFromPrng(
  87. std::vector<Polynomial<ModularInt>> c0,
  88. const typename ModularInt::Params* modulus_params,
  89. const NttParameters<ModularInt>* ntt_params,
  90. const ErrorParams<ModularInt>* error_params, SecurePrng* prng) {
  91. std::vector<SymmetricRlweCiphertext<ModularInt>> ciphertexts;
  92. for (int i = 0; i < c0.size(); ++i) {
  93. RLWE_ASSIGN_OR_RETURN(auto a, SamplePolynomialFromPrng<ModularInt>(
  94. c0[i].Len(), prng, modulus_params));
  95. // Ciphertexts that can be expanded from PRNG must be fresh encryptions.
  96. ciphertexts.emplace_back(
  97. std::vector<Polynomial<ModularInt>>(
  98. {std::move(c0[i]), std::move(a.NegateInPlace(modulus_params))}),
  99. 1, error_params->B_encryption(), modulus_params, error_params);
  100. }
  101. return ciphertexts;
  102. }
  103. } // namespace rlwe
  104. #endif // RLWE_SYMMETRIC_ENCRYPTION_WITH_PRNG_H_