1 /*
2 * Copyright 2017 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
16 #include "symmetric_encryption.h"
17
18 #include <algorithm>
19 #include <cstdint>
20 #include <functional>
21 #include <iostream>
22 #include <random>
23 #include <vector>
24
25 #include <gmock/gmock.h>
26 #include <gtest/gtest.h>
27 #include "constants.h"
28 #include "context.h"
29 #include "montgomery.h"
30 #include "ntt_parameters.h"
31 #include "polynomial.h"
32 #include "prng/integral_prng_types.h"
33 #include "serialization.pb.h"
34 #include "status_macros.h"
35 #include "testing/parameters.h"
36 #include "testing/status_matchers.h"
37 #include "testing/status_testing.h"
38 #include "testing/testing_prng.h"
39 #include "testing/testing_utils.h"
40
41 namespace {
42
43 using ::rlwe::testing::StatusIs;
44 using ::testing::Eq;
45 using ::testing::HasSubstr;
46
47 // Set constants.
48 const int kTestingRounds = 10;
49
50 // Tests symmetric-key encryption scheme, including the following homomorphic
51 // operations: addition, scalar multiplication by a polynomial (absorb), and
52 // multiplication. Substitutions are implemented in
53 // testing/coefficient_polynomial_ciphertext.h, and SymmetricRlweKey::Substitute
54 // and SymmetricRlweCiphertext::PowersOfS() (updated on substitution calls) are
55 // further tested in testing/coefficient_polynomial_ciphertext_test.cc.
56 template <typename ModularInt>
57 class SymmetricRlweEncryptionTest : public ::testing::Test {
58 public:
59 // Sample a random key.
SampleKey(const rlwe::RlweContext<ModularInt> * context)60 rlwe::StatusOr<rlwe::SymmetricRlweKey<ModularInt>> SampleKey(
61 const rlwe::RlweContext<ModularInt>* context) {
62 RLWE_ASSIGN_OR_RETURN(std::string prng_seed,
63 rlwe::SingleThreadPrng::GenerateSeed());
64 RLWE_ASSIGN_OR_RETURN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
65 return rlwe::SymmetricRlweKey<ModularInt>::Sample(
66 context->GetLogN(), context->GetVariance(), context->GetLogT(),
67 context->GetModulusParams(), context->GetNttParams(), prng.get());
68 }
69
70 // Encrypt a plaintext.
Encrypt(const rlwe::SymmetricRlweKey<ModularInt> & key,const std::vector<typename ModularInt::Int> & plaintext,const rlwe::RlweContext<ModularInt> * context)71 rlwe::StatusOr<rlwe::SymmetricRlweCiphertext<ModularInt>> Encrypt(
72 const rlwe::SymmetricRlweKey<ModularInt>& key,
73 const std::vector<typename ModularInt::Int>& plaintext,
74 const rlwe::RlweContext<ModularInt>* context) {
75 RLWE_ASSIGN_OR_RETURN(auto mont,
76 rlwe::testing::ConvertToMontgomery<ModularInt>(
77 plaintext, context->GetModulusParams()));
78 auto plaintext_ntt = rlwe::Polynomial<ModularInt>::ConvertToNtt(
79 mont, context->GetNttParams(), context->GetModulusParams());
80 RLWE_ASSIGN_OR_RETURN(std::string prng_seed,
81 rlwe::SingleThreadPrng::GenerateSeed());
82 RLWE_ASSIGN_OR_RETURN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
83 return rlwe::Encrypt<ModularInt>(key, plaintext_ntt,
84 context->GetErrorParams(), prng.get());
85 }
86 };
87 TYPED_TEST_SUITE(SymmetricRlweEncryptionTest, rlwe::testing::ModularIntTypes);
88
89 // Ensure that RemoveError works correctly on negative numbers for several
90 // different values of t.
TYPED_TEST(SymmetricRlweEncryptionTest,RemoveErrorNegative)91 TYPED_TEST(SymmetricRlweEncryptionTest, RemoveErrorNegative) {
92 unsigned int seed = 0;
93 for (const auto& params :
94 rlwe::testing::ContextParameters<TypeParam>::Value()) {
95 ASSERT_OK_AND_ASSIGN(auto context,
96 rlwe::RlweContext<TypeParam>::Create(params));
97
98 for (int t = 2; t < 16; t++) {
99 for (int i = 0; i < kTestingRounds; i++) {
100 // Sample a plaintext in the range (modulus/2, modulus)
101 typename TypeParam::Int plaintext =
102 (rand_r(&seed) % (context->GetModulus() / 2)) +
103 context->GetModulus() / 2 + 1;
104 // Create a vector that exclusively contains the value "plaintext".
105 ASSERT_OK_AND_ASSIGN(
106 auto m_plaintext,
107 TypeParam::ImportInt(plaintext, context->GetModulusParams()));
108 std::vector<TypeParam> error_and_message(context->GetN(), m_plaintext);
109 auto result = rlwe::RemoveError<TypeParam>(error_and_message,
110 context->GetModulus(), t,
111 context->GetModulusParams());
112
113 // Compute the expected result using signed arithmetic. Derive its
114 // negative equivalent by subtracting out testing::kModulus and taking
115 // that negative value (mod t).
116 absl::int128 expected =
117 (static_cast<absl::int128>(plaintext) -
118 static_cast<absl::int128>(context->GetModulus())) %
119 t;
120
121 // Finally, turn any negative values into their positive equivalents
122 // (mod t).
123 if (expected < 0) {
124 expected += t;
125 }
126
127 for (unsigned int j = 0; j < context->GetN(); j++) {
128 EXPECT_EQ(expected, result[j]) << t << plaintext;
129 }
130 }
131 }
132 }
133 }
134
135 // Ensure that RemoveError works correctly on positive numbers for several
136 // different values of t.
TYPED_TEST(SymmetricRlweEncryptionTest,RemoveErrorPositive)137 TYPED_TEST(SymmetricRlweEncryptionTest, RemoveErrorPositive) {
138 for (const auto& params :
139 rlwe::testing::ContextParameters<TypeParam>::Value()) {
140 ASSERT_OK_AND_ASSIGN(auto context,
141 rlwe::RlweContext<TypeParam>::Create(params));
142 unsigned int seed = 0;
143
144 for (int t = 2; t < 16; t++) {
145 for (int i = 0; i < kTestingRounds; i++) {
146 // Sample a plaintext in the range (0, modulus/2)
147 typename TypeParam::Int plaintext =
148 rand_r(&seed) % (context->GetModulus() / 2);
149
150 // Create a vector that exclusively contains the value "plaintext".
151 ASSERT_OK_AND_ASSIGN(
152 auto m_plaintext,
153 TypeParam::ImportInt(plaintext, context->GetModulusParams()));
154 std::vector<TypeParam> error_and_message(context->GetN(), m_plaintext);
155 auto result = rlwe::RemoveError<TypeParam>(error_and_message,
156 context->GetModulus(), t,
157 context->GetModulusParams());
158
159 for (unsigned int j = 0; j < context->GetN(); j++) {
160 EXPECT_EQ(plaintext % t, result[j]);
161 }
162 }
163 }
164 }
165 }
166
167 // Ensure that the encryption scheme can decrypt its own ciphertexts.
TYPED_TEST(SymmetricRlweEncryptionTest,CanDecrypt)168 TYPED_TEST(SymmetricRlweEncryptionTest, CanDecrypt) {
169 for (const auto& params :
170 rlwe::testing::ContextParameters<TypeParam>::Value()) {
171 ASSERT_OK_AND_ASSIGN(auto context,
172 rlwe::RlweContext<TypeParam>::Create(params));
173 for (unsigned int i = 0; i < kTestingRounds; i++) {
174 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
175 auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(
176 context->GetN(), context->GetT());
177 ASSERT_OK_AND_ASSIGN(auto ciphertext,
178 this->Encrypt(key, plaintext, context.get()));
179 ASSERT_OK_AND_ASSIGN(auto decrypted,
180 rlwe::Decrypt<TypeParam>(key, ciphertext));
181
182 EXPECT_EQ(plaintext, decrypted);
183 }
184 }
185 }
186
187 // Accessing out of bounds raises errors
TYPED_TEST(SymmetricRlweEncryptionTest,OutOfBoundsIndex)188 TYPED_TEST(SymmetricRlweEncryptionTest, OutOfBoundsIndex) {
189 for (const auto& params :
190 rlwe::testing::ContextParameters<TypeParam>::Value()) {
191 ASSERT_OK_AND_ASSIGN(auto context,
192 rlwe::RlweContext<TypeParam>::Create(params));
193 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
194 auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
195 context->GetT());
196 ASSERT_OK_AND_ASSIGN(auto ciphertext,
197 this->Encrypt(key, plaintext, context.get()));
198 ASSERT_OK(ciphertext.Component(ciphertext.Len() - 1));
199 EXPECT_THAT(ciphertext.Component(ciphertext.Len()),
200 StatusIs(::absl::StatusCode::kInvalidArgument,
201 HasSubstr("Index out of range.")));
202 EXPECT_THAT(ciphertext.Component(-1),
203 StatusIs(::absl::StatusCode::kInvalidArgument,
204 HasSubstr("Index out of range.")));
205 }
206 }
207
208 // Check that the HE scheme is additively homomorphic.
TYPED_TEST(SymmetricRlweEncryptionTest,AdditivelyHomomorphic)209 TYPED_TEST(SymmetricRlweEncryptionTest, AdditivelyHomomorphic) {
210 for (const auto& params :
211 rlwe::testing::ContextParameters<TypeParam>::Value()) {
212 ASSERT_OK_AND_ASSIGN(auto context,
213 rlwe::RlweContext<TypeParam>::Create(params));
214 for (unsigned int i = 0; i < kTestingRounds; i++) {
215 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
216
217 std::vector<typename TypeParam::Int> plaintext1 =
218 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
219 context->GetT());
220 std::vector<typename TypeParam::Int> plaintext2 =
221 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
222 context->GetT());
223
224 ASSERT_OK_AND_ASSIGN(auto ciphertext1,
225 this->Encrypt(key, plaintext1, context.get()));
226 ASSERT_OK_AND_ASSIGN(auto ciphertext2,
227 this->Encrypt(key, plaintext2, context.get()));
228 ASSERT_OK_AND_ASSIGN(auto ciphertext_add, ciphertext1 + ciphertext2);
229 ASSERT_OK_AND_ASSIGN(auto ciphertext_sub, ciphertext1 - ciphertext2);
230
231 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted_add,
232 rlwe::Decrypt<TypeParam>(key, ciphertext_add));
233 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted_sub,
234 rlwe::Decrypt<TypeParam>(key, ciphertext_sub));
235
236 for (unsigned int j = 0; j < plaintext1.size(); j++) {
237 EXPECT_EQ((plaintext1[j] + plaintext2[j]) % context->GetT(),
238 decrypted_add[j]);
239 EXPECT_EQ(
240 (context->GetT() + plaintext1[j] - plaintext2[j]) % context->GetT(),
241 decrypted_sub[j]);
242 // Check that the error grows additively.
243 EXPECT_EQ(ciphertext_add.Error(),
244 ciphertext1.Error() + ciphertext2.Error());
245 EXPECT_EQ(ciphertext_sub.Error(),
246 ciphertext1.Error() + ciphertext2.Error());
247 }
248 }
249 }
250 }
251
252 // Check that homomorphic addition can be performed in place.
TYPED_TEST(SymmetricRlweEncryptionTest,AddHomomorphicallyInPlace)253 TYPED_TEST(SymmetricRlweEncryptionTest, AddHomomorphicallyInPlace) {
254 for (const auto& params :
255 rlwe::testing::ContextParameters<TypeParam>::Value()) {
256 ASSERT_OK_AND_ASSIGN(auto context,
257 rlwe::RlweContext<TypeParam>::Create(params));
258 for (unsigned int i = 0; i < kTestingRounds; i++) {
259 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
260
261 std::vector<typename TypeParam::Int> plaintext1 =
262 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
263 context->GetT());
264 std::vector<typename TypeParam::Int> plaintext2 =
265 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
266 context->GetT());
267
268 ASSERT_OK_AND_ASSIGN(auto ciphertext1_add,
269 this->Encrypt(key, plaintext1, context.get()));
270 ASSERT_OK_AND_ASSIGN(auto ciphertext1_sub,
271 this->Encrypt(key, plaintext1, context.get()));
272 ASSERT_OK_AND_ASSIGN(auto ciphertext2,
273 this->Encrypt(key, plaintext2, context.get()));
274 const double ciphertext1_add_error = ciphertext1_add.Error();
275 const double ciphertext1_sub_error = ciphertext1_sub.Error();
276
277 ASSERT_OK(ciphertext1_add.AddInPlace(ciphertext2));
278 ASSERT_OK(ciphertext1_sub.SubInPlace(ciphertext2));
279
280 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted1_add,
281 rlwe::Decrypt<TypeParam>(key, ciphertext1_add));
282 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted1_sub,
283 rlwe::Decrypt<TypeParam>(key, ciphertext1_sub));
284
285 for (unsigned int j = 0; j < plaintext1.size(); j++) {
286 EXPECT_EQ((plaintext1[j] + plaintext2[j]) % context->GetT(),
287 decrypted1_add[j]);
288 EXPECT_EQ(
289 (context->GetT() + plaintext1[j] - plaintext2[j]) % context->GetT(),
290 decrypted1_sub[j]);
291 // Check that the error grows additively.
292 EXPECT_EQ(ciphertext1_add.Error(),
293 ciphertext1_add_error + ciphertext2.Error());
294 EXPECT_EQ(ciphertext1_sub.Error(),
295 ciphertext1_sub_error + ciphertext2.Error());
296 }
297 }
298 }
299 }
300
301 // Check that homomorphic addition to a 0-ciphertext does not change the
302 // plaintext.
TYPED_TEST(SymmetricRlweEncryptionTest,AddToZero)303 TYPED_TEST(SymmetricRlweEncryptionTest, AddToZero) {
304 for (const auto& params :
305 rlwe::testing::ContextParameters<TypeParam>::Value()) {
306 ASSERT_OK_AND_ASSIGN(auto context,
307 rlwe::RlweContext<TypeParam>::Create(params));
308 for (unsigned int i = 0; i < kTestingRounds; i++) {
309 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
310
311 std::vector<typename TypeParam::Int> plaintext =
312 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
313 context->GetT());
314
315 rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext1(
316 context->GetModulusParams(), context->GetErrorParams());
317 ASSERT_OK_AND_ASSIGN(auto ciphertext2,
318 this->Encrypt(key, plaintext, context.get()));
319 ASSERT_OK_AND_ASSIGN(auto ciphertext3, ciphertext1 + ciphertext2);
320
321 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
322 rlwe::Decrypt<TypeParam>(key, ciphertext3));
323
324 EXPECT_EQ(plaintext, decrypted);
325 }
326 }
327 }
328
329 // Check that homomorphic absorption works.
TYPED_TEST(SymmetricRlweEncryptionTest,Absorb)330 TYPED_TEST(SymmetricRlweEncryptionTest, Absorb) {
331 for (const auto& params :
332 rlwe::testing::ContextParameters<TypeParam>::Value()) {
333 ASSERT_OK_AND_ASSIGN(auto context,
334 rlwe::RlweContext<TypeParam>::Create(params));
335 for (unsigned int i = 0; i < kTestingRounds; i++) {
336 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
337
338 // Create the initial plaintexts.
339 std::vector<typename TypeParam::Int> plaintext =
340 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
341 context->GetT());
342 ASSERT_OK_AND_ASSIGN(auto m_plaintext,
343 rlwe::testing::ConvertToMontgomery<TypeParam>(
344 plaintext, context->GetModulusParams()));
345 rlwe::Polynomial<TypeParam> plaintext_ntt =
346 rlwe::Polynomial<TypeParam>::ConvertToNtt(
347 m_plaintext, context->GetNttParams(),
348 context->GetModulusParams());
349 std::vector<typename TypeParam::Int> to_absorb =
350 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
351 context->GetT());
352 ASSERT_OK_AND_ASSIGN(auto m_to_absorb,
353 rlwe::testing::ConvertToMontgomery<TypeParam>(
354 to_absorb, context->GetModulusParams()));
355 rlwe::Polynomial<TypeParam> to_absorb_ntt =
356 rlwe::Polynomial<TypeParam>::ConvertToNtt(
357 m_to_absorb, context->GetNttParams(),
358 context->GetModulusParams());
359
360 // Create our expected value.
361 ASSERT_OK_AND_ASSIGN(
362 rlwe::Polynomial<TypeParam> expected_ntt,
363 plaintext_ntt.Mul(to_absorb_ntt, context->GetModulusParams()));
364 std::vector<typename TypeParam::Int> expected =
365 rlwe::RemoveError<TypeParam>(
366 expected_ntt.InverseNtt(context->GetNttParams(),
367 context->GetModulusParams()),
368 context->GetModulus(), context->GetT(),
369 context->GetModulusParams());
370
371 // Encrypt, absorb, and decrypt.
372 ASSERT_OK_AND_ASSIGN(auto encrypt,
373 this->Encrypt(key, plaintext, context.get()));
374 ASSERT_OK_AND_ASSIGN(auto ciphertext, encrypt* to_absorb_ntt);
375 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
376 rlwe::Decrypt<TypeParam>(key, ciphertext));
377
378 EXPECT_EQ(expected, decrypted);
379
380 // Check that the error is the product of an encryption and a plaintext.
381 EXPECT_EQ(ciphertext.Error(),
382 context->GetErrorParams()->B_encryption() *
383 context->GetErrorParams()->B_plaintext());
384 }
385 }
386 }
387
388 // Check that homomorphic absorption in place works.
TYPED_TEST(SymmetricRlweEncryptionTest,AbsorbInPlace)389 TYPED_TEST(SymmetricRlweEncryptionTest, AbsorbInPlace) {
390 for (const auto& params :
391 rlwe::testing::ContextParameters<TypeParam>::Value()) {
392 ASSERT_OK_AND_ASSIGN(auto context,
393 rlwe::RlweContext<TypeParam>::Create(params));
394 for (unsigned int i = 0; i < kTestingRounds; i++) {
395 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
396
397 // Create the initial plaintexts.
398 std::vector<typename TypeParam::Int> plaintext =
399 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
400 context->GetT());
401 ASSERT_OK_AND_ASSIGN(auto m_plaintext,
402 rlwe::testing::ConvertToMontgomery<TypeParam>(
403 plaintext, context->GetModulusParams()));
404 rlwe::Polynomial<TypeParam> plaintext_ntt =
405 rlwe::Polynomial<TypeParam>::ConvertToNtt(
406 m_plaintext, context->GetNttParams(),
407 context->GetModulusParams());
408 std::vector<typename TypeParam::Int> to_absorb =
409 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
410 context->GetT());
411 ASSERT_OK_AND_ASSIGN(auto m_to_absorb,
412 rlwe::testing::ConvertToMontgomery<TypeParam>(
413 to_absorb, context->GetModulusParams()));
414 rlwe::Polynomial<TypeParam> to_absorb_ntt =
415 rlwe::Polynomial<TypeParam>::ConvertToNtt(
416 m_to_absorb, context->GetNttParams(),
417 context->GetModulusParams());
418
419 // Create our expected value.
420 ASSERT_OK_AND_ASSIGN(
421 rlwe::Polynomial<TypeParam> expected_ntt,
422 plaintext_ntt.Mul(to_absorb_ntt, context->GetModulusParams()));
423 std::vector<typename TypeParam::Int> expected =
424 rlwe::RemoveError<TypeParam>(
425 expected_ntt.InverseNtt(context->GetNttParams(),
426 context->GetModulusParams()),
427 context->GetModulus(), context->GetT(),
428 context->GetModulusParams());
429
430 // Encrypt, absorb in place, and decrypt.
431 ASSERT_OK_AND_ASSIGN(auto ciphertext,
432 this->Encrypt(key, plaintext, context.get()));
433 ASSERT_OK(ciphertext.AbsorbInPlace(to_absorb_ntt));
434 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
435 rlwe::Decrypt<TypeParam>(key, ciphertext));
436
437 EXPECT_EQ(expected, decrypted);
438
439 // Check that the error is the product of an encryption and a plaintext.
440 EXPECT_EQ(ciphertext.Error(),
441 context->GetErrorParams()->B_encryption() *
442 context->GetErrorParams()->B_plaintext());
443 }
444 }
445 }
446
447 // Check that homomorphic absorption of a scalar works.
TYPED_TEST(SymmetricRlweEncryptionTest,AbsorbScalar)448 TYPED_TEST(SymmetricRlweEncryptionTest, AbsorbScalar) {
449 for (const auto& params :
450 rlwe::testing::ContextParameters<TypeParam>::Value()) {
451 ASSERT_OK_AND_ASSIGN(auto context,
452 rlwe::RlweContext<TypeParam>::Create(params));
453 unsigned int seed = 0;
454
455 for (unsigned int i = 0; i < kTestingRounds; i++) {
456 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
457
458 // Create the initial plaintexts.
459 std::vector<typename TypeParam::Int> plaintext =
460 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
461 context->GetT());
462 ASSERT_OK_AND_ASSIGN(auto m_plaintext,
463 rlwe::testing::ConvertToMontgomery<TypeParam>(
464 plaintext, context->GetModulusParams()));
465 rlwe::Polynomial<TypeParam> plaintext_ntt =
466 rlwe::Polynomial<TypeParam>::ConvertToNtt(
467 m_plaintext, context->GetNttParams(),
468 context->GetModulusParams());
469 ASSERT_OK_AND_ASSIGN(TypeParam to_absorb,
470 TypeParam::ImportInt(rand_r(&seed) % context->GetT(),
471 context->GetModulusParams()));
472
473 // Create our expected value.
474 ASSERT_OK_AND_ASSIGN(
475 rlwe::Polynomial<TypeParam> expected_ntt,
476 plaintext_ntt.Mul(to_absorb, context->GetModulusParams()));
477 std::vector<typename TypeParam::Int> expected =
478 rlwe::RemoveError<TypeParam>(
479 expected_ntt.InverseNtt(context->GetNttParams(),
480 context->GetModulusParams()),
481 context->GetModulus(), context->GetT(),
482 context->GetModulusParams());
483
484 // Encrypt, absorb, and decrypt.
485 ASSERT_OK_AND_ASSIGN(auto encrypt,
486 this->Encrypt(key, plaintext, context.get()));
487 ASSERT_OK_AND_ASSIGN(auto ciphertext, encrypt* to_absorb);
488 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
489 rlwe::Decrypt<TypeParam>(key, ciphertext));
490
491 EXPECT_EQ(expected, decrypted);
492 // Expect the error to grow multiplicatively.
493 EXPECT_EQ(ciphertext.Error(), context->GetErrorParams()->B_encryption() *
494 static_cast<double>(to_absorb.ExportInt(
495 context->GetModulusParams())));
496 }
497 }
498 }
499
500 // Check that homomorphic absorption of a scalar in place works.
TYPED_TEST(SymmetricRlweEncryptionTest,AbsorbScalarInPlace)501 TYPED_TEST(SymmetricRlweEncryptionTest, AbsorbScalarInPlace) {
502 for (const auto& params :
503 rlwe::testing::ContextParameters<TypeParam>::Value()) {
504 ASSERT_OK_AND_ASSIGN(auto context,
505 rlwe::RlweContext<TypeParam>::Create(params));
506 unsigned int seed = 0;
507
508 for (unsigned int i = 0; i < kTestingRounds; i++) {
509 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
510
511 // Create the initial plaintexts.
512 std::vector<typename TypeParam::Int> plaintext =
513 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
514 context->GetT());
515 ASSERT_OK_AND_ASSIGN(auto m_plaintext,
516 rlwe::testing::ConvertToMontgomery<TypeParam>(
517 plaintext, context->GetModulusParams()));
518 rlwe::Polynomial<TypeParam> plaintext_ntt =
519 rlwe::Polynomial<TypeParam>::ConvertToNtt(
520 m_plaintext, context->GetNttParams(),
521 context->GetModulusParams());
522 ASSERT_OK_AND_ASSIGN(TypeParam to_absorb,
523 TypeParam::ImportInt(rand_r(&seed) % context->GetT(),
524 context->GetModulusParams()));
525
526 // Create our expected value.
527 ASSERT_OK_AND_ASSIGN(
528 rlwe::Polynomial<TypeParam> expected_ntt,
529 plaintext_ntt.Mul(to_absorb, context->GetModulusParams()));
530 std::vector<typename TypeParam::Int> expected =
531 rlwe::RemoveError<TypeParam>(
532 expected_ntt.InverseNtt(context->GetNttParams(),
533 context->GetModulusParams()),
534 context->GetModulus(), context->GetT(),
535 context->GetModulusParams());
536
537 // Encrypt, absorb, and decrypt.
538 ASSERT_OK_AND_ASSIGN(auto ciphertext,
539 this->Encrypt(key, plaintext, context.get()));
540 ASSERT_OK(ciphertext.AbsorbInPlace(to_absorb));
541 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
542 rlwe::Decrypt<TypeParam>(key, ciphertext));
543
544 EXPECT_EQ(expected, decrypted);
545 // Expect the error to grow multiplicatively.
546 EXPECT_EQ(ciphertext.Error(), context->GetErrorParams()->B_encryption() *
547 static_cast<double>(to_absorb.ExportInt(
548 context->GetModulusParams())));
549 }
550 }
551 }
552
553 // Check that we cannot multiply with an empty ciphertext.
TYPED_TEST(SymmetricRlweEncryptionTest,EmptyCipherMultiplication)554 TYPED_TEST(SymmetricRlweEncryptionTest, EmptyCipherMultiplication) {
555 for (const auto& params :
556 rlwe::testing::ContextParameters<TypeParam>::Value()) {
557 ASSERT_OK_AND_ASSIGN(auto context,
558 rlwe::RlweContext<TypeParam>::Create(params));
559 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
560
561 // Create a plaintext
562 std::vector<typename TypeParam::Int> plaintext =
563 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
564 context->GetT());
565
566 // Encrypt, multiply
567 ASSERT_OK_AND_ASSIGN(auto ciphertext1,
568 this->Encrypt(key, plaintext, context.get()));
569
570 // empty cipher
571 std::vector<rlwe::Polynomial<TypeParam>> c;
572 rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext2(
573 c, 1, 0, context->GetModulusParams(), context->GetErrorParams());
574
575 EXPECT_THAT(
576 ciphertext1 * ciphertext2,
577 StatusIs(::absl::StatusCode::kInvalidArgument,
578 HasSubstr("Cannot multiply using an empty ciphertext.")));
579 EXPECT_THAT(
580 ciphertext2 * ciphertext1,
581 StatusIs(::absl::StatusCode::kInvalidArgument,
582 HasSubstr("Cannot multiply using an empty ciphertext.")));
583
584 c.push_back(rlwe::Polynomial<TypeParam>());
585 rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext3(
586 c, 1, 0, context->GetModulusParams(), context->GetErrorParams());
587 EXPECT_THAT(ciphertext1 * ciphertext3,
588 StatusIs(::absl::StatusCode::kInvalidArgument,
589 HasSubstr("Cannot multiply using an empty polynomial "
590 "in the ciphertext.")));
591
592 EXPECT_THAT(ciphertext3 * ciphertext1,
593 StatusIs(::absl::StatusCode::kInvalidArgument,
594 HasSubstr("Cannot multiply using an empty polynomial "
595 "in the ciphertext.")));
596 }
597 }
598
599 // Check that the scheme is multiplicatively homomorphic.
TYPED_TEST(SymmetricRlweEncryptionTest,MultiplicativelyHomomorphic)600 TYPED_TEST(SymmetricRlweEncryptionTest, MultiplicativelyHomomorphic) {
601 if (sizeof(TypeParam) > 2) { // No multiplicative homomorphism possible when
602 // TypeParam = Uint16
603 for (const auto& params :
604 rlwe::testing::ContextParameters<TypeParam>::Value()) {
605 ASSERT_OK_AND_ASSIGN(auto context,
606 rlwe::RlweContext<TypeParam>::Create(params));
607 for (int i = 0; i < kTestingRounds; i++) {
608 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
609
610 // Create the initial plaintexts.
611 std::vector<typename TypeParam::Int> plaintext1 =
612 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
613 context->GetT());
614 ASSERT_OK_AND_ASSIGN(auto mp1,
615 rlwe::testing::ConvertToMontgomery<TypeParam>(
616 plaintext1, context->GetModulusParams()));
617 rlwe::Polynomial<TypeParam> plaintext1_ntt =
618 rlwe::Polynomial<TypeParam>::ConvertToNtt(
619 mp1, context->GetNttParams(), context->GetModulusParams());
620 std::vector<typename TypeParam::Int> plaintext2 =
621 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
622 context->GetT());
623 ASSERT_OK_AND_ASSIGN(auto mp2,
624 rlwe::testing::ConvertToMontgomery<TypeParam>(
625 plaintext2, context->GetModulusParams()));
626 rlwe::Polynomial<TypeParam> plaintext2_ntt =
627 rlwe::Polynomial<TypeParam>::ConvertToNtt(
628 mp2, context->GetNttParams(), context->GetModulusParams());
629
630 // Encrypt, multiply, and decrypt.
631 ASSERT_OK_AND_ASSIGN(auto ciphertext1,
632 this->Encrypt(key, plaintext1, context.get()));
633 ASSERT_OK_AND_ASSIGN(auto ciphertext2,
634 this->Encrypt(key, plaintext2, context.get()));
635 ASSERT_OK_AND_ASSIGN(auto product, ciphertext1* ciphertext2);
636 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
637 rlwe::Decrypt<TypeParam>(key, product));
638
639 // Create the polynomial we expect.
640 ASSERT_OK_AND_ASSIGN(
641 rlwe::Polynomial<TypeParam> expected_ntt,
642 plaintext1_ntt.Mul(plaintext2_ntt, context->GetModulusParams()));
643 std::vector<typename TypeParam::Int> expected =
644 rlwe::RemoveError<TypeParam>(
645 expected_ntt.InverseNtt(context->GetNttParams(),
646 context->GetModulusParams()),
647 context->GetModulus(), context->GetT(),
648 context->GetModulusParams());
649
650 EXPECT_EQ(expected, decrypted);
651 // Expect that the error grows multiplicatively.
652 EXPECT_EQ(product.Error(), ciphertext1.Error() * ciphertext2.Error());
653 }
654 }
655 }
656 }
657
658 // Check that many homomorphic additions can be performed.
TYPED_TEST(SymmetricRlweEncryptionTest,ManyHomomorphicAdds)659 TYPED_TEST(SymmetricRlweEncryptionTest, ManyHomomorphicAdds) {
660 for (const auto& params :
661 rlwe::testing::ContextParameters<TypeParam>::Value()) {
662 ASSERT_OK_AND_ASSIGN(auto context,
663 rlwe::RlweContext<TypeParam>::Create(params));
664 // Sample a starting plaintext and ciphertext and create aggregators;
665 std::vector<typename TypeParam::Int> plaintext =
666 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
667 context->GetT());
668 std::vector<typename TypeParam::Int> plaintext_sum = plaintext;
669 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
670 ASSERT_OK_AND_ASSIGN(auto ciphertext_sum,
671 this->Encrypt(key, plaintext, context.get()));
672
673 // Sample a fresh plaintext.
674 plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
675 context->GetT());
676 ASSERT_OK_AND_ASSIGN(auto ciphertext,
677 this->Encrypt(key, plaintext, context.get()));
678
679 int num_adds = 50;
680 // Perform 50 homomorphic ciphertext additions with the fresh ciphertext.
681 for (int j = 0; j < num_adds; j++) {
682 // Add the new plaintext to the old plaintext.
683 for (unsigned int k = 0; k < context->GetN(); k++) {
684 plaintext_sum[k] += plaintext[k];
685 plaintext_sum[k] %= context->GetT();
686 }
687
688 // Add the new ciphertext to the old ciphertext.
689 ASSERT_OK_AND_ASSIGN(ciphertext_sum, ciphertext_sum + ciphertext);
690 }
691
692 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
693 rlwe::Decrypt<TypeParam>(key, ciphertext_sum));
694
695 // Ensure the values are the same.
696 EXPECT_EQ(plaintext_sum, decrypted);
697 // Expect that the ciphertext sum's error grows by the additively by the
698 // ciphertext's error.
699 EXPECT_GT(ciphertext_sum.Error(), num_adds * ciphertext.Error());
700 }
701 }
702
703 // Check that ciphertext deserialization cannot handle more than
704 // rlwe::kMaxNumCoeffs coefficients.
TYPED_TEST(SymmetricRlweEncryptionTest,ExceedMaxNumCoeffDeserializeCiphertext)705 TYPED_TEST(SymmetricRlweEncryptionTest,
706 ExceedMaxNumCoeffDeserializeCiphertext) {
707 for (const auto& params :
708 rlwe::testing::ContextParameters<TypeParam>::Value()) {
709 ASSERT_OK_AND_ASSIGN(auto context,
710 rlwe::RlweContext<TypeParam>::Create(params));
711
712 int num_coeffs = rlwe::kMaxNumCoeffs + 1;
713 std::vector<rlwe::Polynomial<TypeParam>> c;
714 for (int i = 0; i < num_coeffs; i++) {
715 c.push_back(rlwe::Polynomial<TypeParam>(1, context->GetModulusParams()));
716 }
717 rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext(
718 c, 1, 0, context->GetModulusParams(), context->GetErrorParams());
719 // Serialize and deserialize.
720 ASSERT_OK_AND_ASSIGN(rlwe::SerializedSymmetricRlweCiphertext serialized,
721 ciphertext.Serialize());
722
723 EXPECT_THAT(
724 rlwe::SymmetricRlweCiphertext<TypeParam>::Deserialize(
725 serialized, context->GetModulusParams(), context->GetErrorParams()),
726 StatusIs(::absl::StatusCode::kInvalidArgument,
727 HasSubstr(absl::StrCat(
728 "Number of coefficients, ", serialized.c_size(),
729 ", cannot be more than ", rlwe::kMaxNumCoeffs, "."))));
730 }
731 }
732
733 // Check that ciphertext serialization works.
TYPED_TEST(SymmetricRlweEncryptionTest,SerializeCiphertext)734 TYPED_TEST(SymmetricRlweEncryptionTest, SerializeCiphertext) {
735 for (const auto& params :
736 rlwe::testing::ContextParameters<TypeParam>::Value()) {
737 ASSERT_OK_AND_ASSIGN(auto context,
738 rlwe::RlweContext<TypeParam>::Create(params));
739 for (int i = 0; i < kTestingRounds; i++) {
740 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
741 std::vector<typename TypeParam::Int> plaintext =
742 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
743 context->GetT());
744 ASSERT_OK_AND_ASSIGN(auto ciphertext,
745 this->Encrypt(key, plaintext, context.get()));
746
747 // Serialize and deserialize.
748 ASSERT_OK_AND_ASSIGN(rlwe::SerializedSymmetricRlweCiphertext serialized,
749 ciphertext.Serialize());
750 ASSERT_OK_AND_ASSIGN(
751 auto deserialized,
752 rlwe::SymmetricRlweCiphertext<TypeParam>::Deserialize(
753 serialized, context->GetModulusParams(),
754 context->GetErrorParams()));
755
756 // Decrypt and check equality.
757 ASSERT_OK_AND_ASSIGN(
758 std::vector<typename TypeParam::Int> deserialized_plaintext,
759 rlwe::Decrypt<TypeParam>(key, deserialized));
760
761 EXPECT_EQ(plaintext, deserialized_plaintext);
762 // Check that the error stays the same.
763 EXPECT_EQ(deserialized.Error(), ciphertext.Error());
764 }
765 }
766 }
767
768 // Check that key serialization works.
TYPED_TEST(SymmetricRlweEncryptionTest,SerializeKey)769 TYPED_TEST(SymmetricRlweEncryptionTest, SerializeKey) {
770 for (const auto& params :
771 rlwe::testing::ContextParameters<TypeParam>::Value()) {
772 ASSERT_OK_AND_ASSIGN(auto context,
773 rlwe::RlweContext<TypeParam>::Create(params));
774 for (int i = 0; i < kTestingRounds; i++) {
775 ASSERT_OK_AND_ASSIGN(auto original_key, this->SampleKey(context.get()));
776 std::vector<typename TypeParam::Int> plaintext =
777 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
778 context->GetT());
779
780 // Serialize key, deserialize, and ensure the deserialized key is
781 // interoperable with the original key.
782 ASSERT_OK_AND_ASSIGN(rlwe::SerializedNttPolynomial serialized,
783 original_key.Serialize());
784 ASSERT_OK_AND_ASSIGN(
785 auto deserialized_key,
786 rlwe::SymmetricRlweKey<TypeParam>::Deserialize(
787 context->GetVariance(), context->GetLogT(), serialized,
788 context->GetModulusParams(), context->GetNttParams()));
789
790 // Test that a ciphertext encrypted with the original key decrypts under
791 // the deserialized key.
792 ASSERT_OK_AND_ASSIGN(
793 auto ekey1, this->Encrypt(original_key, plaintext, context.get()));
794 ASSERT_OK_AND_ASSIGN(auto dkey1,
795 rlwe::Decrypt<TypeParam>(deserialized_key, ekey1));
796 EXPECT_EQ(dkey1, plaintext);
797
798 // Test that a ciphertext encrypted with the deserialized key decrypts
799 // under the original key.
800 ASSERT_OK_AND_ASSIGN(auto ekey2, this->Encrypt(deserialized_key,
801 plaintext, context.get()));
802 ASSERT_OK_AND_ASSIGN(auto dkey2,
803 rlwe::Decrypt<TypeParam>(original_key, ekey2));
804 EXPECT_EQ(dkey2, plaintext);
805 }
806 }
807 }
808
809 // Try an ill-formed key modulus switching
TYPED_TEST(SymmetricRlweEncryptionTest,FailingKeyModulusReduction)810 TYPED_TEST(SymmetricRlweEncryptionTest, FailingKeyModulusReduction) {
811 for (const auto& params :
812 rlwe::testing::ContextParameters<TypeParam>::Value()) {
813 ASSERT_OK_AND_ASSIGN(auto context,
814 rlwe::RlweContext<TypeParam>::Create(params));
815 // p is the original modulus and q is the new modulus we want to switch to
816 // For modulus switching, p % t must be equal to q % t, where t is the
817 // plaintext modulus, and both need to be congruent to 1 mod 2n.
818 typename TypeParam::Int p = context->GetModulus();
819 typename TypeParam::Int q = p - (context->GetN() << 1);
820 EXPECT_NE(q % context->GetT(), p % context->GetT());
821
822 ASSERT_OK_AND_ASSIGN(auto context_q, rlwe::RlweContext<TypeParam>::Create(
823 {.modulus = q,
824 .log_n = params.log_n,
825 .log_t = params.log_t,
826 .variance = params.variance}));
827
828 ASSERT_OK_AND_ASSIGN(auto key_p, this->SampleKey(context.get()));
829 auto status = key_p.template SwitchModulus<TypeParam>(
830 context_q->GetModulusParams(), context_q->GetNttParams());
831 EXPECT_THAT(status, StatusIs(::absl::StatusCode::kInvalidArgument,
832 HasSubstr("p % t != q % t")));
833 }
834 }
835
836 // Try an ill-formed ciphertext modulus switching
TYPED_TEST(SymmetricRlweEncryptionTest,FailingCiphertextModulusReduction)837 TYPED_TEST(SymmetricRlweEncryptionTest, FailingCiphertextModulusReduction) {
838 for (const auto& params :
839 rlwe::testing::ContextParameters<TypeParam>::Value()) {
840 ASSERT_OK_AND_ASSIGN(auto context,
841 rlwe::RlweContext<TypeParam>::Create(params));
842 // p is the original modulus and q is the new modulus we want to switch to
843 // For modulus switching, p % t must be equal to q % t, where t is the
844 // plaintext modulus, and both need to be congruent to 1 mod 2n.
845 typename TypeParam::Int p = context->GetModulus();
846 typename TypeParam::Int q = p - (context->GetN() << 1);
847 EXPECT_NE(q % context->GetT(), p % context->GetT());
848
849 ASSERT_OK_AND_ASSIGN(auto context_q, rlwe::RlweContext<TypeParam>::Create(
850 {.modulus = q,
851 .log_n = params.log_n,
852 .log_t = params.log_t,
853 .variance = params.variance}));
854
855 ASSERT_OK_AND_ASSIGN(auto key_p, this->SampleKey(context.get()));
856 // sample ciphertext modulo p.
857 auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
858 context->GetT());
859 ASSERT_OK_AND_ASSIGN(auto ciphertext,
860 this->Encrypt(key_p, plaintext, context.get()));
861
862 auto status = ciphertext.template SwitchModulus<TypeParam>(
863 context->GetNttParams(), context_q->GetModulusParams(),
864 context_q->GetNttParams(), context_q->GetErrorParams(),
865 context->GetT());
866
867 EXPECT_THAT(status, StatusIs(::absl::StatusCode::kInvalidArgument,
868 HasSubstr("p % t != q % t")));
869 }
870 }
871
872 // Test modulus switching.
TYPED_TEST(SymmetricRlweEncryptionTest,ModulusReduction)873 TYPED_TEST(SymmetricRlweEncryptionTest, ModulusReduction) {
874 for (const auto& params :
875 rlwe::testing::ContextParametersModulusSwitching<TypeParam>::Value()) {
876 auto params1 = std::get<0>(params), params2 = std::get<1>(params);
877 ASSERT_OK_AND_ASSIGN(auto context1,
878 rlwe::RlweContext<TypeParam>::Create(params1));
879 ASSERT_OK_AND_ASSIGN(auto context2,
880 rlwe::RlweContext<TypeParam>::Create(params2));
881
882 for (int i = 0; i < kTestingRounds; i++) {
883 // Create a key.
884 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context1.get()));
885 ASSERT_OK_AND_ASSIGN(
886 auto key_switched,
887 key.template SwitchModulus<TypeParam>(context2->GetModulusParams(),
888 context2->GetNttParams()));
889
890 // Create a plaintext.
891 std::vector<typename TypeParam::Int> plaintext =
892 rlwe::testing::SamplePlaintext<TypeParam>(context1->GetN(),
893 context1->GetT());
894 ASSERT_OK_AND_ASSIGN(auto ciphertext,
895 this->Encrypt(key, plaintext, context1.get()));
896
897 // Switch moduli.
898 ASSERT_OK_AND_ASSIGN(
899 auto ciphertext_switched,
900 ciphertext.template SwitchModulus<TypeParam>(
901 context1->GetNttParams(), context2->GetModulusParams(),
902 context2->GetNttParams(), context2->GetErrorParams(),
903 context2->GetT()));
904
905 // Decrypt in the smaller modulus.
906 ASSERT_OK_AND_ASSIGN(
907 auto decrypted,
908 rlwe::Decrypt<TypeParam>(key_switched, ciphertext_switched));
909
910 EXPECT_EQ(plaintext, decrypted);
911 }
912 }
913 }
914
915 // Check that modulus switching reduces the error.
TYPED_TEST(SymmetricRlweEncryptionTest,ModulusSwitchingReducesLargeError)916 TYPED_TEST(SymmetricRlweEncryptionTest, ModulusSwitchingReducesLargeError) {
917 for (const auto& params :
918 rlwe::testing::ContextParametersModulusSwitching<TypeParam>::Value()) {
919 auto params1 = std::get<0>(params), params2 = std::get<1>(params);
920 ASSERT_OK_AND_ASSIGN(auto context1,
921 rlwe::RlweContext<TypeParam>::Create(params1));
922 ASSERT_OK_AND_ASSIGN(auto context2,
923 rlwe::RlweContext<TypeParam>::Create(params2));
924
925 for (int i = 0; i < kTestingRounds; i++) {
926 // Create a key.
927 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context1.get()));
928 ASSERT_OK_AND_ASSIGN(
929 auto key_switched,
930 key.template SwitchModulus<TypeParam>(context2->GetModulusParams(),
931 context2->GetNttParams()));
932
933 // Create a plaintext.
934 std::vector<typename TypeParam::Int> plaintext =
935 rlwe::testing::SamplePlaintext<TypeParam>(context1->GetN(),
936 context1->GetT());
937 ASSERT_OK_AND_ASSIGN(auto ciphertext,
938 this->Encrypt(key, plaintext, context1.get()));
939
940 // Square the ciphertext
941 ASSERT_OK_AND_ASSIGN(auto squared, ciphertext* ciphertext);
942
943 // Switch moduli.
944 ASSERT_OK_AND_ASSIGN(
945 auto squared_switched,
946 squared.template SwitchModulus<TypeParam>(
947 context1->GetNttParams(), context2->GetModulusParams(),
948 context2->GetNttParams(), context2->GetErrorParams(),
949 context2->GetT()));
950
951 // Decrypt
952 ASSERT_OK_AND_ASSIGN(auto squared_decrypted,
953 rlwe::Decrypt<TypeParam>(key, squared));
954 ASSERT_OK_AND_ASSIGN(
955 auto squared_switched_decrypted,
956 rlwe::Decrypt<TypeParam>(key_switched, squared_switched));
957
958 EXPECT_EQ(squared_decrypted, squared_switched_decrypted);
959
960 // Expect that the error reduces after a modulus switch when the error is
961 // large.
962 EXPECT_LT(squared_switched.Error(), squared.Error());
963 // But that the error doesn't reduce when the error is small.
964 EXPECT_GT(squared_switched.Error(), ciphertext.Error());
965 }
966 }
967 }
968
969 // Check that we cannot perform operations between ciphertexts encrypted under
970 // different powers of s.
TYPED_TEST(SymmetricRlweEncryptionTest,OperationsFailOnMismatchedPowersOfS)971 TYPED_TEST(SymmetricRlweEncryptionTest, OperationsFailOnMismatchedPowersOfS) {
972 for (const auto& params :
973 rlwe::testing::ContextParameters<TypeParam>::Value()) {
974 ASSERT_OK_AND_ASSIGN(auto context,
975 rlwe::RlweContext<TypeParam>::Create(params));
976 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
977
978 std::vector<typename TypeParam::Int> plaintext1 =
979 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
980 context->GetT());
981 ASSERT_OK_AND_ASSIGN(auto m1, rlwe::testing::ConvertToMontgomery<TypeParam>(
982 plaintext1, context->GetModulusParams()));
983 auto plaintext1_ntt = rlwe::Polynomial<TypeParam>::ConvertToNtt(
984 m1, context->GetNttParams(), context->GetModulusParams());
985 std::vector<typename TypeParam::Int> plaintext2 =
986 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
987 context->GetT());
988
989 auto ciphertext1 = rlwe::SymmetricRlweCiphertext<TypeParam>(
990 {plaintext1_ntt}, 1, context->GetErrorParams()->B_encryption(),
991 context->GetModulusParams(), context->GetErrorParams());
992 auto ciphertext2 = rlwe::SymmetricRlweCiphertext<TypeParam>(
993 {plaintext1_ntt}, 2, context->GetErrorParams()->B_encryption(),
994 context->GetModulusParams(), context->GetErrorParams());
995 EXPECT_THAT(ciphertext1 + ciphertext2,
996 StatusIs(::absl::StatusCode::kInvalidArgument,
997 HasSubstr("must be encrypted with the same key")));
998 EXPECT_THAT(ciphertext1 * ciphertext2,
999 StatusIs(::absl::StatusCode::kInvalidArgument,
1000 HasSubstr("must be encrypted with the same key")));
1001 }
1002 }
1003
1004 // Verifies that the power of S changes as expected in adds / mults.
TYPED_TEST(SymmetricRlweEncryptionTest,AddsAndMultPreservePowerOfS)1005 TYPED_TEST(SymmetricRlweEncryptionTest, AddsAndMultPreservePowerOfS) {
1006 for (const auto& params :
1007 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1008 ASSERT_OK_AND_ASSIGN(auto context,
1009 rlwe::RlweContext<TypeParam>::Create(params));
1010 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
1011
1012 std::vector<typename TypeParam::Int> plaintext1 =
1013 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1014 context->GetT());
1015 ASSERT_OK_AND_ASSIGN(auto m1, rlwe::testing::ConvertToMontgomery<TypeParam>(
1016 plaintext1, context->GetModulusParams()));
1017 auto plaintext1_ntt = rlwe::Polynomial<TypeParam>::ConvertToNtt(
1018 m1, context->GetNttParams(), context->GetModulusParams());
1019 std::vector<typename TypeParam::Int> plaintext2 =
1020 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1021 context->GetT());
1022
1023 auto ciphertext1 = rlwe::SymmetricRlweCiphertext<TypeParam>(
1024 {plaintext1_ntt}, 2, context->GetErrorParams()->B_encryption(),
1025 context->GetModulusParams(), context->GetErrorParams());
1026 auto ciphertext2 = rlwe::SymmetricRlweCiphertext<TypeParam>(
1027 {plaintext1_ntt}, 2, context->GetErrorParams()->B_encryption(),
1028 context->GetModulusParams(), context->GetErrorParams());
1029
1030 EXPECT_EQ(ciphertext1.PowerOfS(), 2);
1031 EXPECT_EQ(ciphertext2.PowerOfS(), 2);
1032 ASSERT_OK_AND_ASSIGN(auto sum, ciphertext1 + ciphertext2);
1033 EXPECT_EQ(sum.PowerOfS(), 2);
1034 ASSERT_OK_AND_ASSIGN(auto prod, ciphertext1* ciphertext2);
1035 EXPECT_EQ(prod.PowerOfS(), 2);
1036 }
1037 }
1038
1039 // Check that substitutions of the form 2^k + 1 work.
TYPED_TEST(SymmetricRlweEncryptionTest,Substitutes)1040 TYPED_TEST(SymmetricRlweEncryptionTest, Substitutes) {
1041 for (const auto& params :
1042 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1043 ASSERT_OK_AND_ASSIGN(auto context,
1044 rlwe::RlweContext<TypeParam>::Create(params));
1045 for (int k = 1; k < context->GetLogN(); k++) {
1046 int substitution_power = (1 << k) + 1;
1047 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
1048 auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(
1049 context->GetN(), context->GetT());
1050
1051 // Create the expected polynomial output by substituting the plaintext.
1052 ASSERT_OK_AND_ASSIGN(auto m_plaintext,
1053 rlwe::testing::ConvertToMontgomery<TypeParam>(
1054 plaintext, context->GetModulusParams()));
1055 auto plaintext_ntt = rlwe::Polynomial<TypeParam>::ConvertToNtt(
1056 m_plaintext, context->GetNttParams(), context->GetModulusParams());
1057 ASSERT_OK_AND_ASSIGN(
1058 auto expected_ntt,
1059 plaintext_ntt.Substitute(substitution_power, context->GetNttParams(),
1060 context->GetModulusParams()));
1061 std::vector<typename TypeParam::Int> expected =
1062 rlwe::RemoveError<TypeParam>(
1063 expected_ntt.InverseNtt(context->GetNttParams(),
1064 context->GetModulusParams()),
1065 context->GetModulus(), context->GetT(),
1066 context->GetModulusParams());
1067
1068 // Encrypt and substitute the ciphertext. Decrypt with a substituted key.
1069 ASSERT_OK_AND_ASSIGN(auto ciphertext,
1070 this->Encrypt(key, plaintext, context.get()));
1071 ASSERT_OK_AND_ASSIGN(
1072 auto substituted,
1073 ciphertext.Substitute(substitution_power, context->GetNttParams()));
1074 ASSERT_OK_AND_ASSIGN(auto key_sub, key.Substitute(substitution_power));
1075 ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
1076 rlwe::Decrypt<TypeParam>(key_sub, substituted));
1077
1078 EXPECT_EQ(decrypted, expected);
1079 EXPECT_EQ(substituted.PowerOfS(), substitution_power);
1080 EXPECT_EQ(substituted.Error(), ciphertext.Error());
1081 }
1082 }
1083 }
1084
1085 // Check that substitution of 2 does not work.
TYPED_TEST(SymmetricRlweEncryptionTest,SubstitutionFailsOnEvenPower)1086 TYPED_TEST(SymmetricRlweEncryptionTest, SubstitutionFailsOnEvenPower) {
1087 for (const auto& params :
1088 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1089 ASSERT_OK_AND_ASSIGN(auto context,
1090 rlwe::RlweContext<TypeParam>::Create(params));
1091 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
1092 auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1093 context->GetT());
1094
1095 ASSERT_OK_AND_ASSIGN(auto enc,
1096 this->Encrypt(key, plaintext, context.get()));
1097 EXPECT_THAT(
1098 enc.Substitute(2, context->GetNttParams()),
1099 StatusIs(::absl::StatusCode::kInvalidArgument,
1100 HasSubstr("power must be a non-negative odd integer")));
1101 }
1102 }
1103
1104 // Check that the power of s updates after several substitutions.
TYPED_TEST(SymmetricRlweEncryptionTest,PowerOfSUpdatedAfterRepeatedSubs)1105 TYPED_TEST(SymmetricRlweEncryptionTest, PowerOfSUpdatedAfterRepeatedSubs) {
1106 for (const auto& params :
1107 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1108 ASSERT_OK_AND_ASSIGN(auto context,
1109 rlwe::RlweContext<TypeParam>::Create(params));
1110 int substitution_power = 5;
1111 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
1112 auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1113 context->GetT());
1114
1115 // Encrypt and substitute the ciphertext. Decrypt with a substituted key.
1116 ASSERT_OK_AND_ASSIGN(auto ciphertext1,
1117 this->Encrypt(key, plaintext, context.get()));
1118 ASSERT_OK_AND_ASSIGN(
1119 auto ciphertext2,
1120 ciphertext1.Substitute(substitution_power, context->GetNttParams()));
1121 ASSERT_OK_AND_ASSIGN(
1122 auto ciphertext3,
1123 ciphertext2.Substitute(substitution_power, context->GetNttParams()));
1124 EXPECT_EQ(ciphertext3.PowerOfS(),
1125 (substitution_power * substitution_power) % (2 * key.Len()));
1126 }
1127 }
1128
1129 // Check that operations can only be performed when powers of s match.
TYPED_TEST(SymmetricRlweEncryptionTest,PowersOfSMustMatchOnOperations)1130 TYPED_TEST(SymmetricRlweEncryptionTest, PowersOfSMustMatchOnOperations) {
1131 for (const auto& params :
1132 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1133 ASSERT_OK_AND_ASSIGN(auto context,
1134 rlwe::RlweContext<TypeParam>::Create(params));
1135 int substitution_power = 5;
1136 ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
1137
1138 std::vector<typename TypeParam::Int> plaintext1 =
1139 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1140 context->GetT());
1141 std::vector<typename TypeParam::Int> plaintext2 =
1142 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1143 context->GetT());
1144
1145 ASSERT_OK_AND_ASSIGN(auto ciphertext1,
1146 this->Encrypt(key, plaintext1, context.get()));
1147 ASSERT_OK_AND_ASSIGN(auto ciphertext2,
1148 this->Encrypt(key, plaintext2, context.get()));
1149 ASSERT_OK_AND_ASSIGN(
1150 auto ciphertext2_sub,
1151 ciphertext2.Substitute(substitution_power, context->GetNttParams()));
1152
1153 EXPECT_THAT(ciphertext1 + ciphertext2_sub,
1154 StatusIs(::absl::StatusCode::kInvalidArgument,
1155 HasSubstr("must be encrypted with the same key")));
1156 EXPECT_THAT(ciphertext1 * ciphertext2_sub,
1157 StatusIs(::absl::StatusCode::kInvalidArgument,
1158 HasSubstr("must be encrypted with the same key")));
1159 }
1160 }
1161
1162 // Check that the null key has value 0.
TYPED_TEST(SymmetricRlweEncryptionTest,NullKeyHasValueZero)1163 TYPED_TEST(SymmetricRlweEncryptionTest, NullKeyHasValueZero) {
1164 for (const auto& params :
1165 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1166 ASSERT_OK_AND_ASSIGN(auto context,
1167 rlwe::RlweContext<TypeParam>::Create(params));
1168 rlwe::Polynomial<TypeParam> zero(context->GetN(),
1169 context->GetModulusParams());
1170
1171 ASSERT_OK_AND_ASSIGN(
1172 auto null_key,
1173 rlwe::SymmetricRlweKey<TypeParam>::NullKey(
1174 context->GetLogN(), context->GetVariance(), context->GetLogT(),
1175 context->GetModulusParams(), context->GetNttParams()));
1176
1177 EXPECT_THAT(zero, Eq(null_key.Key()));
1178 }
1179 }
1180
1181 // Check the addition and subtraction of keys.
TYPED_TEST(SymmetricRlweEncryptionTest,AddAndSubKeys)1182 TYPED_TEST(SymmetricRlweEncryptionTest, AddAndSubKeys) {
1183 for (const auto& params :
1184 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1185 ASSERT_OK_AND_ASSIGN(auto context,
1186 rlwe::RlweContext<TypeParam>::Create(params));
1187 ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
1188 ASSERT_OK_AND_ASSIGN(auto key_2, this->SampleKey(context.get()));
1189
1190 ASSERT_OK_AND_ASSIGN(auto key_3, key_1.Add(key_2));
1191 ASSERT_OK_AND_ASSIGN(auto key_4, key_1.Sub(key_2));
1192
1193 ASSERT_OK_AND_ASSIGN(
1194 rlwe::Polynomial<TypeParam> poly_3,
1195 key_1.Key().Add(key_2.Key(), context->GetModulusParams()));
1196 ASSERT_OK_AND_ASSIGN(
1197 rlwe::Polynomial<TypeParam> poly_4,
1198 key_1.Key().Sub(key_2.Key(), context->GetModulusParams()));
1199
1200 EXPECT_THAT(key_3.Key(), Eq(poly_3));
1201 EXPECT_THAT(key_4.Key(), Eq(poly_4));
1202 }
1203 }
1204
1205 // Check that decryption works with added and subtracted keys.
TYPED_TEST(SymmetricRlweEncryptionTest,EncryptAndDecryptWithAddAndSubKeys)1206 TYPED_TEST(SymmetricRlweEncryptionTest, EncryptAndDecryptWithAddAndSubKeys) {
1207 for (const auto& params :
1208 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1209 ASSERT_OK_AND_ASSIGN(auto context,
1210 rlwe::RlweContext<TypeParam>::Create(params));
1211 ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
1212 ASSERT_OK_AND_ASSIGN(auto key_2, this->SampleKey(context.get()));
1213 ASSERT_OK_AND_ASSIGN(auto add_keys, key_1.Add(key_2));
1214 ASSERT_OK_AND_ASSIGN(auto sub_keys, key_1.Sub(key_2));
1215 std::vector<typename TypeParam::Int> plaintext =
1216 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1217 context->GetT());
1218
1219 ASSERT_OK_AND_ASSIGN(auto add_ciphertext,
1220 this->Encrypt(add_keys, plaintext, context.get()));
1221 ASSERT_OK_AND_ASSIGN(auto sub_ciphertext,
1222 this->Encrypt(sub_keys, plaintext, context.get()));
1223 ASSERT_OK_AND_ASSIGN(auto decrypted_add_ciphertext,
1224 rlwe::Decrypt(add_keys, add_ciphertext));
1225 ASSERT_OK_AND_ASSIGN(auto decrypted_sub_ciphertext,
1226 rlwe::Decrypt(sub_keys, sub_ciphertext));
1227
1228 EXPECT_EQ(plaintext, decrypted_add_ciphertext);
1229 EXPECT_EQ(plaintext, decrypted_sub_ciphertext);
1230 }
1231 }
1232
1233 // Check that the scheme is key homomorphic.
TYPED_TEST(SymmetricRlweEncryptionTest,IsKeyHomomorphic)1234 TYPED_TEST(SymmetricRlweEncryptionTest, IsKeyHomomorphic) {
1235 for (const auto& params :
1236 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1237 ASSERT_OK_AND_ASSIGN(auto context,
1238 rlwe::RlweContext<TypeParam>::Create(params));
1239 ASSERT_OK_AND_ASSIGN(auto prng_seed,
1240 rlwe::SingleThreadPrng::GenerateSeed());
1241 ASSERT_OK_AND_ASSIGN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
1242 // Generate the keys.
1243 ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
1244 ASSERT_OK_AND_ASSIGN(auto key_2, this->SampleKey(context.get()));
1245 // Generate the plaintexts.
1246 std::vector<typename TypeParam::Int> plaintext_1 =
1247 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1248 context->GetT());
1249 std::vector<typename TypeParam::Int> plaintext_2 =
1250 rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
1251 context->GetT());
1252 ASSERT_OK_AND_ASSIGN(auto plaintext_mont_1,
1253 rlwe::testing::ConvertToMontgomery<TypeParam>(
1254 plaintext_1, context->GetModulusParams()));
1255 ASSERT_OK_AND_ASSIGN(auto plaintext_mont_2,
1256 rlwe::testing::ConvertToMontgomery<TypeParam>(
1257 plaintext_2, context->GetModulusParams()));
1258 auto poly_1 = rlwe::Polynomial<TypeParam>::ConvertToNtt(
1259 plaintext_mont_1, context->GetNttParams(), context->GetModulusParams());
1260 auto poly_2 = rlwe::Polynomial<TypeParam>::ConvertToNtt(
1261 plaintext_mont_2, context->GetNttParams(), context->GetModulusParams());
1262 // Compute the expected plaintexts.
1263 std::vector<typename TypeParam::Int> add_plaintext = plaintext_1;
1264 std::vector<typename TypeParam::Int> sub_plaintext = plaintext_2;
1265 std::transform(
1266 plaintext_1.begin(), plaintext_1.end(), plaintext_2.begin(),
1267 add_plaintext.begin(),
1268 [&context = context](typename TypeParam::Int u,
1269 typename TypeParam::Int v) ->
1270 typename TypeParam::Int { return (u + v) % context->GetT(); });
1271 std::transform(plaintext_1.begin(), plaintext_1.end(), plaintext_2.begin(),
1272 sub_plaintext.begin(),
1273 [&context = context](typename TypeParam::Int u,
1274 typename TypeParam::Int v) ->
1275 typename TypeParam::Int {
1276 return (context->GetT() + u - v) % context->GetT();
1277 });
1278
1279 // Sample the "a" to be used in both ciphertexts.
1280 ASSERT_OK_AND_ASSIGN(auto a,
1281 rlwe::SamplePolynomialFromPrng<TypeParam>(
1282 key_1.Len(), prng.get(), key_1.ModulusParams()));
1283 // Encrypt with the same a and different keys
1284 ASSERT_OK_AND_ASSIGN(auto poly_ciphertext_1,
1285 rlwe::internal::Encrypt(key_1, poly_1, a, prng.get()));
1286 ASSERT_OK_AND_ASSIGN(auto poly_ciphertext_2,
1287 rlwe::internal::Encrypt(key_2, poly_2, a, prng.get()));
1288 // Add and Substract the ciphertexts
1289 ASSERT_OK_AND_ASSIGN(
1290 auto add_poly_ciphertext,
1291 poly_ciphertext_1.Add(poly_ciphertext_2, context->GetModulusParams()));
1292 ASSERT_OK_AND_ASSIGN(
1293 auto sub_poly_ciphertext,
1294 poly_ciphertext_1.Sub(poly_ciphertext_2, context->GetModulusParams()));
1295 // The resulting ciphertexts should be decryptable unded the added (resp.
1296 // substracted) keys.
1297 ASSERT_OK_AND_ASSIGN(auto add_keys, key_1.Add(key_2));
1298 ASSERT_OK_AND_ASSIGN(auto sub_keys, key_1.Sub(key_2));
1299 ASSERT_OK_AND_ASSIGN(
1300 auto decrypted_add_ciphertext,
1301 rlwe::Decrypt(
1302 add_keys,
1303 rlwe::SymmetricRlweCiphertext<TypeParam>(
1304 {add_poly_ciphertext, a.Negate(context->GetModulusParams())}, 1,
1305 context->GetErrorParams()->B_encryption(),
1306 context->GetModulusParams(), context->GetErrorParams())));
1307 ASSERT_OK_AND_ASSIGN(
1308 auto decrypted_sub_ciphertext,
1309 rlwe::Decrypt(
1310 sub_keys,
1311 rlwe::SymmetricRlweCiphertext<TypeParam>(
1312 {sub_poly_ciphertext, a.Negate(context->GetModulusParams())}, 1,
1313 context->GetErrorParams()->B_encryption(),
1314 context->GetModulusParams(), context->GetErrorParams())));
1315
1316 EXPECT_EQ(add_plaintext, decrypted_add_ciphertext);
1317 EXPECT_EQ(sub_plaintext, decrypted_sub_ciphertext);
1318 }
1319 }
1320
1321 // Check that incompatible key cannot be added or subtracted.
TYPED_TEST(SymmetricRlweEncryptionTest,CannotAddOrSubIncompatibleKeys)1322 TYPED_TEST(SymmetricRlweEncryptionTest, CannotAddOrSubIncompatibleKeys) {
1323 for (const auto& params :
1324 rlwe::testing::ContextParameters<TypeParam>::Value()) {
1325 ASSERT_OK_AND_ASSIGN(auto context,
1326 rlwe::RlweContext<TypeParam>::Create(params));
1327 ASSERT_OK_AND_ASSIGN(auto context_different_variance,
1328 rlwe::RlweContext<TypeParam>::Create(
1329 {.modulus = params.modulus,
1330 .log_n = params.log_n,
1331 .log_t = params.log_t,
1332 .variance = params.variance + 1}));
1333 ASSERT_OK_AND_ASSIGN(
1334 auto context_different_log_t,
1335 rlwe::RlweContext<TypeParam>::Create({.modulus = params.modulus,
1336 .log_n = params.log_n,
1337 .log_t = params.log_t + 1,
1338 .variance = params.variance}));
1339 ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
1340 ASSERT_OK_AND_ASSIGN(auto key_2,
1341 this->SampleKey(context_different_variance.get()));
1342 ASSERT_OK_AND_ASSIGN(auto key_3,
1343 this->SampleKey(context_different_log_t.get()));
1344
1345 EXPECT_THAT(
1346 key_1.Add(key_2),
1347 StatusIs(::absl::StatusCode::kInvalidArgument,
1348 HasSubstr("is different than the variance of this key")));
1349 EXPECT_THAT(
1350 key_1.Sub(key_2),
1351 StatusIs(::absl::StatusCode::kInvalidArgument,
1352 HasSubstr("is different than the variance of this key")));
1353 EXPECT_THAT(key_1.Add(key_3),
1354 StatusIs(::absl::StatusCode::kInvalidArgument,
1355 HasSubstr("is different than the log_t of this key")));
1356 EXPECT_THAT(key_1.Sub(key_3),
1357 StatusIs(::absl::StatusCode::kInvalidArgument,
1358 HasSubstr("is different than the log_t of this key")));
1359 }
1360 }
1361
1362 } // namespace
1363