galois_key_test.cc 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415
  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. #include "galois_key.h"
  16. #include <gmock/gmock.h>
  17. #include <gtest/gtest.h>
  18. #include <google/protobuf/util/message_differencer.h>
  19. #include "constants.h"
  20. #include "montgomery.h"
  21. #include "ntt_parameters.h"
  22. #include "polynomial.h"
  23. #include "prng/integral_prng_types.h"
  24. #include "status_macros.h"
  25. #include "symmetric_encryption.h"
  26. #include "testing/protobuf_matchers.h"
  27. #include "testing/status_matchers.h"
  28. #include "testing/status_testing.h"
  29. #include "testing/testing_prng.h"
  30. #include "testing/testing_utils.h"
  31. namespace {
  32. using Uint64 = rlwe::Uint64;
  33. unsigned int seed = 0;
  34. // Set constants.
  35. const Uint64 kLogPlaintextModulus = 1;
  36. const Uint64 kPlaintextModulus = (1 << kLogPlaintextModulus) + 1;
  37. const Uint64 kLogDecompositionModulus = 2;
  38. const Uint64 kLargeLogDecompositionModulus = 31;
  39. // Useful typedefs.
  40. using uint_m = rlwe::MontgomeryInt<Uint64>;
  41. using Polynomial = rlwe::Polynomial<uint_m>;
  42. using Ciphertext = rlwe::SymmetricRlweCiphertext<uint_m>;
  43. using Key = rlwe::SymmetricRlweKey<uint_m>;
  44. using ::rlwe::testing::EqualsProto;
  45. using ::rlwe::testing::StatusIs;
  46. using ::testing::HasSubstr;
  47. // Test fixture.
  48. class GaloisKeyTest : public ::testing::Test {
  49. protected:
  50. void SetUp() override {
  51. ASSERT_OK_AND_ASSIGN(params59_, uint_m::Params::Create(rlwe::kModulus59));
  52. ASSERT_OK_AND_ASSIGN(auto ntt_params,
  53. rlwe::InitializeNttParameters<uint_m>(
  54. rlwe::testing::kLogCoeffs, params59_.get()));
  55. ntt_params_ = absl::make_unique<const rlwe::NttParameters<uint_m>>(
  56. std::move(ntt_params));
  57. ASSERT_OK_AND_ASSIGN(
  58. auto error_params,
  59. rlwe::ErrorParams<uint_m>::Create(rlwe::testing::kDefaultLogT,
  60. rlwe::testing::kDefaultVariance,
  61. params59_.get(), ntt_params_.get()));
  62. error_params_ =
  63. absl::make_unique<const rlwe::ErrorParams<uint_m>>(error_params);
  64. }
  65. // Sample a random key.
  66. rlwe::StatusOr<Key> SampleKey(
  67. Uint64 variance = rlwe::testing::kDefaultVariance,
  68. Uint64 log_t = kLogPlaintextModulus) {
  69. RLWE_ASSIGN_OR_RETURN(std::string prng_seed,
  70. rlwe::SingleThreadPrng::GenerateSeed());
  71. RLWE_ASSIGN_OR_RETURN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
  72. return Key::Sample(rlwe::testing::kLogCoeffs, variance, log_t,
  73. params59_.get(), ntt_params_.get(), prng.get());
  74. }
  75. // Convert a vector of integers to a vector of montgomery integers.
  76. rlwe::StatusOr<std::vector<uint_m>> ConvertToMontgomery(
  77. const std::vector<uint_m::Int>& coeffs, const uint_m::Params* params) {
  78. std::vector<uint_m> output(coeffs.size(), uint_m::ImportZero(params));
  79. for (unsigned int i = 0; i < output.size(); i++) {
  80. RLWE_ASSIGN_OR_RETURN(output[i], uint_m::ImportInt(coeffs[i], params));
  81. }
  82. return output;
  83. }
  84. // Sample a random plaintext.
  85. std::vector<uint_m::Int> SamplePlaintext(
  86. uint_m::Int t = kPlaintextModulus,
  87. Uint64 coeffs = rlwe::testing::kCoeffs) {
  88. std::vector<uint_m::Int> plaintext(coeffs);
  89. for (unsigned int i = 0; i < coeffs; i++) {
  90. plaintext[i] = rand_r(&seed) % t;
  91. }
  92. return plaintext;
  93. }
  94. // Encrypt a plaintext.
  95. rlwe::StatusOr<Ciphertext> Encrypt(
  96. const Key& key, const std::vector<uint_m::Int>& plaintext) {
  97. RLWE_ASSIGN_OR_RETURN(auto mp,
  98. ConvertToMontgomery(plaintext, params59_.get()));
  99. auto plaintext_ntt =
  100. Polynomial::ConvertToNtt(mp, ntt_params_.get(), params59_.get());
  101. RLWE_ASSIGN_OR_RETURN(std::string prng_seed,
  102. rlwe::SingleThreadPrng::GenerateSeed());
  103. RLWE_ASSIGN_OR_RETURN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
  104. return rlwe::Encrypt<uint_m>(key, plaintext_ntt, error_params_.get(),
  105. prng.get());
  106. }
  107. std::unique_ptr<const uint_m::Params> params59_;
  108. std::unique_ptr<const rlwe::NttParameters<uint_m>> ntt_params_;
  109. std::unique_ptr<const rlwe::ErrorParams<uint_m>> error_params_;
  110. };
  111. TEST_F(GaloisKeyTest, GaloisKeyPowerOfSDoesNotMatchSubPower) {
  112. int substitution_power = 3;
  113. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  114. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  115. rlwe::SingleThreadPrng::GenerateSeed());
  116. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  117. key, prng_seed, substitution_power,
  118. kLargeLogDecompositionModulus));
  119. auto plaintext = SamplePlaintext(kPlaintextModulus);
  120. ASSERT_OK_AND_ASSIGN(auto ciphertext, Encrypt(key, plaintext));
  121. ASSERT_OK_AND_ASSIGN(
  122. auto subbed_ciphertext,
  123. ciphertext.Substitute(substitution_power + 2, ntt_params_.get()));
  124. EXPECT_THAT(
  125. galois_key.ApplyTo(subbed_ciphertext),
  126. StatusIs(::absl::StatusCode::kInvalidArgument,
  127. HasSubstr(absl::StrCat(
  128. "Ciphertext PowerOfS: ", subbed_ciphertext.PowerOfS(),
  129. " doesn't match the key substitution power: ",
  130. substitution_power))));
  131. }
  132. TEST_F(GaloisKeyTest, GaloisKeyUpdatesPowerOfS) {
  133. int substitution_power = 3;
  134. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  135. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  136. rlwe::SingleThreadPrng::GenerateSeed());
  137. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  138. key, prng_seed, substitution_power,
  139. kLargeLogDecompositionModulus));
  140. auto plaintext = SamplePlaintext(kPlaintextModulus);
  141. // Substituted ciphertext has substition_power PowerOfS.
  142. ASSERT_OK_AND_ASSIGN(auto ciphertext, Encrypt(key, plaintext));
  143. ASSERT_OK_AND_ASSIGN(
  144. auto subbed_ciphertext,
  145. ciphertext.Substitute(substitution_power, ntt_params_.get()));
  146. EXPECT_EQ(subbed_ciphertext.PowerOfS(), substitution_power);
  147. // PowerOfS transformed back to 1.
  148. ASSERT_OK_AND_ASSIGN(auto transformed_ciphertext,
  149. galois_key.ApplyTo(subbed_ciphertext));
  150. EXPECT_EQ(transformed_ciphertext.PowerOfS(), 1);
  151. }
  152. TEST_F(GaloisKeyTest, KeySwitchedCiphertextDecrypts) {
  153. int substitution_power = 3;
  154. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  155. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  156. rlwe::SingleThreadPrng::GenerateSeed());
  157. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  158. key, prng_seed, substitution_power,
  159. kLogDecompositionModulus));
  160. // Create the initial plaintexts.
  161. std::vector<uint_m::Int> plaintext = SamplePlaintext(kPlaintextModulus);
  162. // Create the expected polynomial output by substituting the plaintext.
  163. ASSERT_OK_AND_ASSIGN(auto mp1,
  164. ConvertToMontgomery(plaintext, params59_.get()));
  165. Polynomial plaintext_ntt =
  166. Polynomial::ConvertToNtt(mp1, ntt_params_.get(), params59_.get());
  167. ASSERT_OK_AND_ASSIGN(
  168. Polynomial expected_ntt,
  169. plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
  170. params59_.get()));
  171. std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
  172. expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
  173. params59_->modulus, kPlaintextModulus, params59_.get());
  174. // Encrypt and substitute the ciphertext. Decrypt with a substituted key.
  175. ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
  176. ASSERT_OK_AND_ASSIGN(
  177. auto ciphertext,
  178. intermediate.Substitute(substitution_power, ntt_params_.get()));
  179. ASSERT_OK_AND_ASSIGN(auto transformed_ciphertext,
  180. galois_key.ApplyTo(ciphertext));
  181. ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
  182. rlwe::Decrypt<uint_m>(key, transformed_ciphertext));
  183. EXPECT_EQ(decrypted, expected);
  184. }
  185. TEST_F(GaloisKeyTest, ComposingSubstitutions) {
  186. // Ensure that a ciphertext can be substituted by composing substitutions in
  187. // steps that have GaloisKeys.
  188. int substitution_power = 9;
  189. // Applying the substitution s -> s(x^3) twice will yield the substitution
  190. // power.
  191. int galois_power = 3;
  192. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  193. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  194. rlwe::SingleThreadPrng::GenerateSeed());
  195. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  196. key, prng_seed, galois_power,
  197. kLogDecompositionModulus));
  198. auto plaintext = SamplePlaintext(kPlaintextModulus);
  199. // Create the expected polynomial output by substituting the plaintext.
  200. ASSERT_OK_AND_ASSIGN(auto mp1,
  201. ConvertToMontgomery(plaintext, params59_.get()));
  202. Polynomial plaintext_ntt =
  203. Polynomial::ConvertToNtt(mp1, ntt_params_.get(), params59_.get());
  204. ASSERT_OK_AND_ASSIGN(
  205. Polynomial expected_ntt,
  206. plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
  207. params59_.get()));
  208. std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
  209. expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
  210. params59_->modulus, kPlaintextModulus, params59_.get());
  211. // Encrypt and substitute the ciphertext in steps using a single galois key.
  212. ASSERT_OK_AND_ASSIGN(auto ciphertext, Encrypt(key, plaintext));
  213. ASSERT_OK_AND_ASSIGN(auto sub_ciphertext,
  214. ciphertext.Substitute(galois_power, ntt_params_.get()));
  215. ASSERT_OK_AND_ASSIGN(auto ciphertext_power_3,
  216. galois_key.ApplyTo(sub_ciphertext));
  217. ASSERT_OK_AND_ASSIGN(
  218. auto sub_ciphertext_power_3,
  219. ciphertext_power_3.Substitute(galois_power, ntt_params_.get()));
  220. ASSERT_OK_AND_ASSIGN(auto ciphertext_power_9,
  221. galois_key.ApplyTo(sub_ciphertext_power_3));
  222. EXPECT_EQ(ciphertext_power_9.PowerOfS(), 1);
  223. ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
  224. rlwe::Decrypt<uint_m>(key, ciphertext_power_9));
  225. EXPECT_EQ(decrypted, expected);
  226. }
  227. TEST_F(GaloisKeyTest, LargeDecompositionModulus) {
  228. int substitution_power = 3;
  229. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  230. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  231. rlwe::SingleThreadPrng::GenerateSeed());
  232. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  233. key, prng_seed, substitution_power,
  234. kLargeLogDecompositionModulus));
  235. auto plaintext = SamplePlaintext(kPlaintextModulus);
  236. // Create the expected polynomial output by substituting the plaintext.
  237. ASSERT_OK_AND_ASSIGN(auto mp1,
  238. ConvertToMontgomery(plaintext, params59_.get()));
  239. Polynomial plaintext_ntt =
  240. Polynomial::ConvertToNtt(mp1, ntt_params_.get(), params59_.get());
  241. ASSERT_OK_AND_ASSIGN(
  242. Polynomial expected_ntt,
  243. plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
  244. params59_.get()));
  245. std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
  246. expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
  247. params59_->modulus, kPlaintextModulus, params59_.get());
  248. // Encrypt and substitute the ciphertext. Decrypt with a substituted key.
  249. ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
  250. ASSERT_OK_AND_ASSIGN(
  251. auto ciphertext,
  252. intermediate.Substitute(substitution_power, ntt_params_.get()));
  253. ASSERT_OK_AND_ASSIGN(auto transformed_ciphertext,
  254. galois_key.ApplyTo(ciphertext));
  255. ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
  256. rlwe::Decrypt<uint_m>(key, transformed_ciphertext));
  257. EXPECT_EQ(decrypted, expected);
  258. }
  259. TEST_F(GaloisKeyTest, CiphertextWithTooManyComponents) {
  260. int substitution_power = 3;
  261. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  262. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  263. rlwe::SingleThreadPrng::GenerateSeed());
  264. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  265. key, prng_seed, substitution_power,
  266. kLargeLogDecompositionModulus));
  267. auto plaintext = SamplePlaintext(kPlaintextModulus);
  268. ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
  269. ASSERT_OK_AND_ASSIGN(
  270. auto ciphertext,
  271. intermediate.Substitute(substitution_power, ntt_params_.get()));
  272. ASSERT_OK_AND_ASSIGN(auto product, ciphertext* ciphertext);
  273. EXPECT_THAT(galois_key.ApplyTo(product),
  274. StatusIs(::absl::StatusCode::kInvalidArgument,
  275. HasSubstr("RelinearizationKey not large enough")));
  276. }
  277. TEST_F(GaloisKeyTest, DeserializedKeySwitches) {
  278. int substitution_power = 3;
  279. auto plaintext = SamplePlaintext(kPlaintextModulus);
  280. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  281. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  282. rlwe::SingleThreadPrng::GenerateSeed());
  283. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  284. key, prng_seed, substitution_power,
  285. kLargeLogDecompositionModulus));
  286. // Serialize and deserialize.
  287. ASSERT_OK_AND_ASSIGN(auto serialized, galois_key.Serialize());
  288. ASSERT_OK_AND_ASSIGN(auto deserialized,
  289. rlwe::GaloisKey<uint_m>::Deserialize(
  290. serialized, params59_.get(), ntt_params_.get()));
  291. // Create the expected polynomial output by substituting the plaintext.
  292. ASSERT_OK_AND_ASSIGN(auto mp,
  293. ConvertToMontgomery(plaintext, params59_.get()));
  294. Polynomial plaintext_ntt =
  295. Polynomial::ConvertToNtt(mp, ntt_params_.get(), params59_.get());
  296. ASSERT_OK_AND_ASSIGN(
  297. Polynomial expected_ntt,
  298. plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
  299. params59_.get()));
  300. std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
  301. expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
  302. params59_->modulus, kPlaintextModulus, params59_.get());
  303. // Encrypt and substitute the ciphertext.
  304. ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
  305. ASSERT_OK_AND_ASSIGN(
  306. auto ciphertext,
  307. intermediate.Substitute(substitution_power, ntt_params_.get()));
  308. // Key-switch with the original galois key.
  309. ASSERT_OK_AND_ASSIGN(auto key_switched_ciphertext,
  310. galois_key.ApplyTo(ciphertext));
  311. ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
  312. rlwe::Decrypt<uint_m>(key, key_switched_ciphertext));
  313. // Key-switch with the deserialized galois key.
  314. ASSERT_OK_AND_ASSIGN(auto key_switched_ciphertext_deserialized,
  315. deserialized.ApplyTo(ciphertext));
  316. ASSERT_OK_AND_ASSIGN(
  317. std::vector<uint_m::Int> deserialized_decrypted,
  318. rlwe::Decrypt<uint_m>(key, key_switched_ciphertext_deserialized));
  319. EXPECT_EQ(deserialized_decrypted, expected);
  320. EXPECT_EQ(deserialized_decrypted, decrypted);
  321. }
  322. TEST_F(GaloisKeyTest, DeserializationFailsWithIncorrectModulus) {
  323. int substitution_power = 3;
  324. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  325. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  326. rlwe::SingleThreadPrng::GenerateSeed());
  327. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  328. key, prng_seed, substitution_power,
  329. kLargeLogDecompositionModulus));
  330. ASSERT_OK_AND_ASSIGN(auto params29, uint_m::Params::Create(rlwe::kModulus29));
  331. // Serialize and deserialize.
  332. ASSERT_OK_AND_ASSIGN(auto serialized, galois_key.Serialize());
  333. EXPECT_THAT(
  334. rlwe::GaloisKey<uint_m>::Deserialize(serialized, params29.get(),
  335. ntt_params_.get()),
  336. StatusIs(::absl::StatusCode::kInvalidArgument,
  337. HasSubstr(absl::StrCat(
  338. "Log decomposition modulus, ", kLargeLogDecompositionModulus,
  339. ", must be at most: ", params29->log_modulus, "."))));
  340. }
  341. TEST_F(GaloisKeyTest, SerializationsOfIdentialKeysEqual) {
  342. int substitution_power = 3;
  343. auto plaintext = SamplePlaintext(kPlaintextModulus);
  344. ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
  345. ASSERT_OK_AND_ASSIGN(std::string prng_seed,
  346. rlwe::SingleThreadPrng::GenerateSeed());
  347. ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
  348. key, prng_seed, substitution_power,
  349. kLargeLogDecompositionModulus));
  350. auto galois_key_copy = galois_key;
  351. // Serialize both matrices.
  352. ASSERT_OK_AND_ASSIGN(auto serialized, galois_key.Serialize());
  353. ASSERT_OK_AND_ASSIGN(auto serialized_copy, galois_key_copy.Serialize());
  354. // Check that two serializations of the same matrix are equal.
  355. EXPECT_EQ(serialized_copy.SerializeAsString(), serialized.SerializeAsString());
  356. }
  357. } // namespace