galois_key.h 5.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125
  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. #ifndef RLWE_GALOIS_KEY_H_
  16. #define RLWE_GALOIS_KEY_H_
  17. #include <cstdint>
  18. #include <vector>
  19. #include "absl/strings/str_cat.h"
  20. #include "relinearization_key.h"
  21. #include "status_macros.h"
  22. #include "statusor.h"
  23. #include "third_party/shell-encryption/base/shell_encryption_export.h"
  24. #include "third_party/shell-encryption/base/shell_encryption_export_template.h"
  25. namespace rlwe {
  26. // Implements a GaloisKey, a type of key-switching matrix that transforms a
  27. // ciphertext encrypted with (1, s(x^substitution_power)) to a ciphertext that
  28. // encrypts the same message under the canonical secret key (1, s). This can be
  29. // viewed as a RelinearizationKey of length two and a substitution_power > 1. A
  30. // GaloisKey can only be applied to ciphertexts whose PowerOfS exactly matches
  31. // the substitution_power.
  32. //
  33. // GaloisKeys are constructed based on the secret key. Two GaloisKeys that
  34. // correspond to the same secret key, substitution power, and use the same
  35. // decomposition modulus will not necessarily be equal. This is due to
  36. // randomness that is sampled when a GaloisKey is created. However, either
  37. // GaloisKey may be used to key-switch the same ciphertext.
  38. //
  39. // Details can be found in Appendix D.2 of https://eprint.iacr.org/2011/566.pdf
  40. template <typename ModularInt>
  41. class EXPORT_TEMPLATE_DECLARE(SHELL_ENCRYPTION_EXPORT) GaloisKey {
  42. public:
  43. // Initializes a GaloisKey based on a SymmetricRlweKey key that can key-switch
  44. // two component ciphertexts. A positive log_decomposition_modulus corresponds
  45. // to the decomposition modulus T. The substitution_power corresponds to the
  46. // power of x in the secret key polynomial s(x^substitution_power) that the
  47. // ciphertext is encrypted with. The prng_seed is used to generate and encode
  48. // the bottom row of the matrix, which consists of random entries.
  49. static SHELL_ENCRYPTION_EXPORT rlwe::StatusOr<GaloisKey> Create(
  50. const SymmetricRlweKey<ModularInt>& key, absl::string_view prng_seed,
  51. Uint64 substitution_power, Uint64 log_decomposition_modulus) {
  52. RLWE_ASSIGN_OR_RETURN(auto relinearization_key,
  53. RelinearizationKey<ModularInt>::Create(
  54. key, prng_seed, /*num_parts=*/2,
  55. log_decomposition_modulus, substitution_power));
  56. return GaloisKey(std::move(relinearization_key));
  57. }
  58. // Takes a SymmetricRlweCiphertext with 2 components encrypted under
  59. // s(x^{substitution_power}) and returns a 2 component SymmetricRlweCiphertext
  60. // encoding the same message. The PowerOfS of the ciphertext is updated to 1.
  61. // Returns an error when the number of components is larger than 2.
  62. rlwe::StatusOr<SymmetricRlweCiphertext<ModularInt>> ApplyTo(
  63. const SymmetricRlweCiphertext<ModularInt>& ciphertext) const {
  64. if (ciphertext.PowerOfS() != SubstitutionPower()) {
  65. return absl::InvalidArgumentError(absl::StrCat(
  66. "Ciphertext PowerOfS: ", ciphertext.PowerOfS(),
  67. " doesn't match the key substitution power: ", SubstitutionPower()));
  68. }
  69. return relinearization_key_.ApplyTo(ciphertext);
  70. }
  71. // Returns a SerializedGaloisKey containing a representation of the
  72. // key-switching matrix and the power of s that corresponds to this
  73. // key-switching matrix.
  74. rlwe::StatusOr<SerializedGaloisKey> Serialize() const {
  75. SerializedGaloisKey output;
  76. RLWE_ASSIGN_OR_RETURN(*output.mutable_key(),
  77. relinearization_key_.Serialize());
  78. return output;
  79. }
  80. // Requires that the number of NTT Polynomials in the key field of the
  81. // SerializedGaloisKey is (2 * num_parts * dimension) where dimension is the
  82. // number of digits needed to represent the modulus in base
  83. // 2^{log_decomposition_modulus}. Crashes for non-valid input parameters.
  84. static SHELL_ENCRYPTION_EXPORT rlwe::StatusOr<GaloisKey> Deserialize(
  85. const SerializedGaloisKey& serialized,
  86. const typename ModularInt::Params* modulus_params,
  87. const NttParameters<ModularInt>* ntt_params) {
  88. RLWE_ASSIGN_OR_RETURN(RelinearizationKey<ModularInt> key,
  89. RelinearizationKey<ModularInt>::Deserialize(
  90. serialized.key(), modulus_params, ntt_params));
  91. return GaloisKey(std::move(key));
  92. }
  93. // Substitution Power accessor.
  94. int SubstitutionPower() const {
  95. return relinearization_key_.SubstitutionPower();
  96. }
  97. private:
  98. GaloisKey(RelinearizationKey<ModularInt> relinearization_key)
  99. : relinearization_key_(std::move(relinearization_key)) {}
  100. // A relinearization key.
  101. RelinearizationKey<ModularInt> relinearization_key_;
  102. };
  103. template class EXPORT_TEMPLATE_DECLARE(
  104. SHELL_ENCRYPTION_EXPORT) GaloisKey<rlwe::MontgomeryInt<Uint16>>;
  105. template class EXPORT_TEMPLATE_DECLARE(
  106. SHELL_ENCRYPTION_EXPORT) GaloisKey<rlwe::MontgomeryInt<Uint32>>;
  107. template class EXPORT_TEMPLATE_DECLARE(
  108. SHELL_ENCRYPTION_EXPORT) GaloisKey<rlwe::MontgomeryInt<Uint64>>;
  109. template class EXPORT_TEMPLATE_DECLARE(
  110. SHELL_ENCRYPTION_EXPORT) GaloisKey<rlwe::MontgomeryInt<absl::uint128>>;
  111. } // namespace rlwe
  112. #endif // RLWE_GALOIS_KEY_H_