/*
* Copyright 2017 Google LLC.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* https://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "symmetric_encryption.h"
#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <random>
#include <vector>
#include <gmock/gmock.h>
#include <gtest/gtest.h>
#include "constants.h"
#include "context.h"
#include "montgomery.h"
#include "ntt_parameters.h"
#include "polynomial.h"
#include "prng/integral_prng_types.h"
#include "serialization.pb.h"
#include "status_macros.h"
#include "testing/parameters.h"
#include "testing/status_matchers.h"
#include "testing/status_testing.h"
#include "testing/testing_prng.h"
#include "testing/testing_utils.h"
namespace {
using ::rlwe::testing::StatusIs;
using ::testing::Eq;
using ::testing::HasSubstr;
// Set constants.
const int kTestingRounds = 10;
// Tests symmetric-key encryption scheme, including the following homomorphic
// operations: addition, scalar multiplication by a polynomial (absorb), and
// multiplication. Substitutions are implemented in
// testing/coefficient_polynomial_ciphertext.h, and SymmetricRlweKey::Substitute
// and SymmetricRlweCiphertext::PowersOfS() (updated on substitution calls) are
// further tested in testing/coefficient_polynomial_ciphertext_test.cc.
template <typename ModularInt>
class SymmetricRlweEncryptionTest : public ::testing::Test {
public:
// Sample a random key.
rlwe::StatusOr<rlwe::SymmetricRlweKey<ModularInt>> SampleKey(
const rlwe::RlweContext<ModularInt>* context) {
RLWE_ASSIGN_OR_RETURN(std::string prng_seed,
rlwe::SingleThreadPrng::GenerateSeed());
RLWE_ASSIGN_OR_RETURN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
return rlwe::SymmetricRlweKey<ModularInt>::Sample(
context->GetLogN(), context->GetVariance(), context->GetLogT(),
context->GetModulusParams(), context->GetNttParams(), prng.get());
}
// Encrypt a plaintext.
rlwe::StatusOr<rlwe::SymmetricRlweCiphertext<ModularInt>> Encrypt(
const rlwe::SymmetricRlweKey<ModularInt>& key,
const std::vector<typename ModularInt::Int>& plaintext,
const rlwe::RlweContext<ModularInt>* context) {
RLWE_ASSIGN_OR_RETURN(auto mont,
rlwe::testing::ConvertToMontgomery<ModularInt>(
plaintext, context->GetModulusParams()));
auto plaintext_ntt = rlwe::Polynomial<ModularInt>::ConvertToNtt(
mont, context->GetNttParams(), context->GetModulusParams());
RLWE_ASSIGN_OR_RETURN(std::string prng_seed,
rlwe::SingleThreadPrng::GenerateSeed());
RLWE_ASSIGN_OR_RETURN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
return rlwe::Encrypt<ModularInt>(key, plaintext_ntt,
context->GetErrorParams(), prng.get());
}
};
TYPED_TEST_SUITE(SymmetricRlweEncryptionTest, rlwe::testing::ModularIntTypes);
// Ensure that RemoveError works correctly on negative numbers for several
// different values of t.
TYPED_TEST(SymmetricRlweEncryptionTest, RemoveErrorNegative) {
unsigned int seed = 0;
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (int t = 2; t < 16; t++) {
for (int i = 0; i < kTestingRounds; i++) {
// Sample a plaintext in the range (modulus/2, modulus)
typename TypeParam::Int plaintext =
(rand_r(&seed) % (context->GetModulus() / 2)) +
context->GetModulus() / 2 + 1;
// Create a vector that exclusively contains the value "plaintext".
ASSERT_OK_AND_ASSIGN(
auto m_plaintext,
TypeParam::ImportInt(plaintext, context->GetModulusParams()));
std::vector<TypeParam> error_and_message(context->GetN(), m_plaintext);
auto result = rlwe::RemoveError<TypeParam>(error_and_message,
context->GetModulus(), t,
context->GetModulusParams());
// Compute the expected result using signed arithmetic. Derive its
// negative equivalent by subtracting out testing::kModulus and taking
// that negative value (mod t).
absl::int128 expected =
(static_cast<absl::int128>(plaintext) -
static_cast<absl::int128>(context->GetModulus())) %
t;
// Finally, turn any negative values into their positive equivalents
// (mod t).
if (expected < 0) {
expected += t;
}
for (unsigned int j = 0; j < context->GetN(); j++) {
EXPECT_EQ(expected, result[j]) << t << plaintext;
}
}
}
}
}
// Ensure that RemoveError works correctly on positive numbers for several
// different values of t.
TYPED_TEST(SymmetricRlweEncryptionTest, RemoveErrorPositive) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
unsigned int seed = 0;
for (int t = 2; t < 16; t++) {
for (int i = 0; i < kTestingRounds; i++) {
// Sample a plaintext in the range (0, modulus/2)
typename TypeParam::Int plaintext =
rand_r(&seed) % (context->GetModulus() / 2);
// Create a vector that exclusively contains the value "plaintext".
ASSERT_OK_AND_ASSIGN(
auto m_plaintext,
TypeParam::ImportInt(plaintext, context->GetModulusParams()));
std::vector<TypeParam> error_and_message(context->GetN(), m_plaintext);
auto result = rlwe::RemoveError<TypeParam>(error_and_message,
context->GetModulus(), t,
context->GetModulusParams());
for (unsigned int j = 0; j < context->GetN(); j++) {
EXPECT_EQ(plaintext % t, result[j]);
}
}
}
}
}
// Ensure that the encryption scheme can decrypt its own ciphertexts.
TYPED_TEST(SymmetricRlweEncryptionTest, CanDecrypt) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(
context->GetN(), context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto decrypted,
rlwe::Decrypt<TypeParam>(key, ciphertext));
EXPECT_EQ(plaintext, decrypted);
}
}
}
// Accessing out of bounds raises errors
TYPED_TEST(SymmetricRlweEncryptionTest, OutOfBoundsIndex) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK(ciphertext.Component(ciphertext.Len() - 1));
EXPECT_THAT(ciphertext.Component(ciphertext.Len()),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("Index out of range.")));
EXPECT_THAT(ciphertext.Component(-1),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("Index out of range.")));
}
}
// Check that the HE scheme is additively homomorphic.
TYPED_TEST(SymmetricRlweEncryptionTest, AdditivelyHomomorphic) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext1 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
std::vector<typename TypeParam::Int> plaintext2 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext1,
this->Encrypt(key, plaintext1, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext2,
this->Encrypt(key, plaintext2, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext_add, ciphertext1 + ciphertext2);
ASSERT_OK_AND_ASSIGN(auto ciphertext_sub, ciphertext1 - ciphertext2);
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted_add,
rlwe::Decrypt<TypeParam>(key, ciphertext_add));
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted_sub,
rlwe::Decrypt<TypeParam>(key, ciphertext_sub));
for (unsigned int j = 0; j < plaintext1.size(); j++) {
EXPECT_EQ((plaintext1[j] + plaintext2[j]) % context->GetT(),
decrypted_add[j]);
EXPECT_EQ(
(context->GetT() + plaintext1[j] - plaintext2[j]) % context->GetT(),
decrypted_sub[j]);
// Check that the error grows additively.
EXPECT_EQ(ciphertext_add.Error(),
ciphertext1.Error() + ciphertext2.Error());
EXPECT_EQ(ciphertext_sub.Error(),
ciphertext1.Error() + ciphertext2.Error());
}
}
}
}
// Check that homomorphic addition can be performed in place.
TYPED_TEST(SymmetricRlweEncryptionTest, AddHomomorphicallyInPlace) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext1 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
std::vector<typename TypeParam::Int> plaintext2 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext1_add,
this->Encrypt(key, plaintext1, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext1_sub,
this->Encrypt(key, plaintext1, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext2,
this->Encrypt(key, plaintext2, context.get()));
const double ciphertext1_add_error = ciphertext1_add.Error();
const double ciphertext1_sub_error = ciphertext1_sub.Error();
ASSERT_OK(ciphertext1_add.AddInPlace(ciphertext2));
ASSERT_OK(ciphertext1_sub.SubInPlace(ciphertext2));
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted1_add,
rlwe::Decrypt<TypeParam>(key, ciphertext1_add));
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted1_sub,
rlwe::Decrypt<TypeParam>(key, ciphertext1_sub));
for (unsigned int j = 0; j < plaintext1.size(); j++) {
EXPECT_EQ((plaintext1[j] + plaintext2[j]) % context->GetT(),
decrypted1_add[j]);
EXPECT_EQ(
(context->GetT() + plaintext1[j] - plaintext2[j]) % context->GetT(),
decrypted1_sub[j]);
// Check that the error grows additively.
EXPECT_EQ(ciphertext1_add.Error(),
ciphertext1_add_error + ciphertext2.Error());
EXPECT_EQ(ciphertext1_sub.Error(),
ciphertext1_sub_error + ciphertext2.Error());
}
}
}
}
// Check that homomorphic addition to a 0-ciphertext does not change the
// plaintext.
TYPED_TEST(SymmetricRlweEncryptionTest, AddToZero) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext1(
context->GetModulusParams(), context->GetErrorParams());
ASSERT_OK_AND_ASSIGN(auto ciphertext2,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext3, ciphertext1 + ciphertext2);
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key, ciphertext3));
EXPECT_EQ(plaintext, decrypted);
}
}
}
// Check that homomorphic absorption works.
TYPED_TEST(SymmetricRlweEncryptionTest, Absorb) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
// Create the initial plaintexts.
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m_plaintext,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> plaintext_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
m_plaintext, context->GetNttParams(),
context->GetModulusParams());
std::vector<typename TypeParam::Int> to_absorb =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m_to_absorb,
rlwe::testing::ConvertToMontgomery<TypeParam>(
to_absorb, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> to_absorb_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
m_to_absorb, context->GetNttParams(),
context->GetModulusParams());
// Create our expected value.
ASSERT_OK_AND_ASSIGN(
rlwe::Polynomial<TypeParam> expected_ntt,
plaintext_ntt.Mul(to_absorb_ntt, context->GetModulusParams()));
std::vector<typename TypeParam::Int> expected =
rlwe::RemoveError<TypeParam>(
expected_ntt.InverseNtt(context->GetNttParams(),
context->GetModulusParams()),
context->GetModulus(), context->GetT(),
context->GetModulusParams());
// Encrypt, absorb, and decrypt.
ASSERT_OK_AND_ASSIGN(auto encrypt,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext, encrypt* to_absorb_ntt);
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key, ciphertext));
EXPECT_EQ(expected, decrypted);
// Check that the error is the product of an encryption and a plaintext.
EXPECT_EQ(ciphertext.Error(),
context->GetErrorParams()->B_encryption() *
context->GetErrorParams()->B_plaintext());
}
}
}
// Check that homomorphic absorption in place works.
TYPED_TEST(SymmetricRlweEncryptionTest, AbsorbInPlace) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
// Create the initial plaintexts.
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m_plaintext,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> plaintext_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
m_plaintext, context->GetNttParams(),
context->GetModulusParams());
std::vector<typename TypeParam::Int> to_absorb =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m_to_absorb,
rlwe::testing::ConvertToMontgomery<TypeParam>(
to_absorb, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> to_absorb_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
m_to_absorb, context->GetNttParams(),
context->GetModulusParams());
// Create our expected value.
ASSERT_OK_AND_ASSIGN(
rlwe::Polynomial<TypeParam> expected_ntt,
plaintext_ntt.Mul(to_absorb_ntt, context->GetModulusParams()));
std::vector<typename TypeParam::Int> expected =
rlwe::RemoveError<TypeParam>(
expected_ntt.InverseNtt(context->GetNttParams(),
context->GetModulusParams()),
context->GetModulus(), context->GetT(),
context->GetModulusParams());
// Encrypt, absorb in place, and decrypt.
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK(ciphertext.AbsorbInPlace(to_absorb_ntt));
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key, ciphertext));
EXPECT_EQ(expected, decrypted);
// Check that the error is the product of an encryption and a plaintext.
EXPECT_EQ(ciphertext.Error(),
context->GetErrorParams()->B_encryption() *
context->GetErrorParams()->B_plaintext());
}
}
}
// Check that homomorphic absorption of a scalar works.
TYPED_TEST(SymmetricRlweEncryptionTest, AbsorbScalar) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
unsigned int seed = 0;
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
// Create the initial plaintexts.
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m_plaintext,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> plaintext_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
m_plaintext, context->GetNttParams(),
context->GetModulusParams());
ASSERT_OK_AND_ASSIGN(TypeParam to_absorb,
TypeParam::ImportInt(rand_r(&seed) % context->GetT(),
context->GetModulusParams()));
// Create our expected value.
ASSERT_OK_AND_ASSIGN(
rlwe::Polynomial<TypeParam> expected_ntt,
plaintext_ntt.Mul(to_absorb, context->GetModulusParams()));
std::vector<typename TypeParam::Int> expected =
rlwe::RemoveError<TypeParam>(
expected_ntt.InverseNtt(context->GetNttParams(),
context->GetModulusParams()),
context->GetModulus(), context->GetT(),
context->GetModulusParams());
// Encrypt, absorb, and decrypt.
ASSERT_OK_AND_ASSIGN(auto encrypt,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext, encrypt* to_absorb);
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key, ciphertext));
EXPECT_EQ(expected, decrypted);
// Expect the error to grow multiplicatively.
EXPECT_EQ(ciphertext.Error(), context->GetErrorParams()->B_encryption() *
static_cast<double>(to_absorb.ExportInt(
context->GetModulusParams())));
}
}
}
// Check that homomorphic absorption of a scalar in place works.
TYPED_TEST(SymmetricRlweEncryptionTest, AbsorbScalarInPlace) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
unsigned int seed = 0;
for (unsigned int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
// Create the initial plaintexts.
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m_plaintext,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> plaintext_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
m_plaintext, context->GetNttParams(),
context->GetModulusParams());
ASSERT_OK_AND_ASSIGN(TypeParam to_absorb,
TypeParam::ImportInt(rand_r(&seed) % context->GetT(),
context->GetModulusParams()));
// Create our expected value.
ASSERT_OK_AND_ASSIGN(
rlwe::Polynomial<TypeParam> expected_ntt,
plaintext_ntt.Mul(to_absorb, context->GetModulusParams()));
std::vector<typename TypeParam::Int> expected =
rlwe::RemoveError<TypeParam>(
expected_ntt.InverseNtt(context->GetNttParams(),
context->GetModulusParams()),
context->GetModulus(), context->GetT(),
context->GetModulusParams());
// Encrypt, absorb, and decrypt.
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK(ciphertext.AbsorbInPlace(to_absorb));
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key, ciphertext));
EXPECT_EQ(expected, decrypted);
// Expect the error to grow multiplicatively.
EXPECT_EQ(ciphertext.Error(), context->GetErrorParams()->B_encryption() *
static_cast<double>(to_absorb.ExportInt(
context->GetModulusParams())));
}
}
}
// Check that we cannot multiply with an empty ciphertext.
TYPED_TEST(SymmetricRlweEncryptionTest, EmptyCipherMultiplication) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
// Create a plaintext
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
// Encrypt, multiply
ASSERT_OK_AND_ASSIGN(auto ciphertext1,
this->Encrypt(key, plaintext, context.get()));
// empty cipher
std::vector<rlwe::Polynomial<TypeParam>> c;
rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext2(
c, 1, 0, context->GetModulusParams(), context->GetErrorParams());
EXPECT_THAT(
ciphertext1 * ciphertext2,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("Cannot multiply using an empty ciphertext.")));
EXPECT_THAT(
ciphertext2 * ciphertext1,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("Cannot multiply using an empty ciphertext.")));
c.push_back(rlwe::Polynomial<TypeParam>());
rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext3(
c, 1, 0, context->GetModulusParams(), context->GetErrorParams());
EXPECT_THAT(ciphertext1 * ciphertext3,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("Cannot multiply using an empty polynomial "
"in the ciphertext.")));
EXPECT_THAT(ciphertext3 * ciphertext1,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("Cannot multiply using an empty polynomial "
"in the ciphertext.")));
}
}
// Check that the scheme is multiplicatively homomorphic.
TYPED_TEST(SymmetricRlweEncryptionTest, MultiplicativelyHomomorphic) {
if (sizeof(TypeParam) > 2) { // No multiplicative homomorphism possible when
// TypeParam = Uint16
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
// Create the initial plaintexts.
std::vector<typename TypeParam::Int> plaintext1 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto mp1,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext1, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> plaintext1_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
mp1, context->GetNttParams(), context->GetModulusParams());
std::vector<typename TypeParam::Int> plaintext2 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto mp2,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext2, context->GetModulusParams()));
rlwe::Polynomial<TypeParam> plaintext2_ntt =
rlwe::Polynomial<TypeParam>::ConvertToNtt(
mp2, context->GetNttParams(), context->GetModulusParams());
// Encrypt, multiply, and decrypt.
ASSERT_OK_AND_ASSIGN(auto ciphertext1,
this->Encrypt(key, plaintext1, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext2,
this->Encrypt(key, plaintext2, context.get()));
ASSERT_OK_AND_ASSIGN(auto product, ciphertext1* ciphertext2);
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key, product));
// Create the polynomial we expect.
ASSERT_OK_AND_ASSIGN(
rlwe::Polynomial<TypeParam> expected_ntt,
plaintext1_ntt.Mul(plaintext2_ntt, context->GetModulusParams()));
std::vector<typename TypeParam::Int> expected =
rlwe::RemoveError<TypeParam>(
expected_ntt.InverseNtt(context->GetNttParams(),
context->GetModulusParams()),
context->GetModulus(), context->GetT(),
context->GetModulusParams());
EXPECT_EQ(expected, decrypted);
// Expect that the error grows multiplicatively.
EXPECT_EQ(product.Error(), ciphertext1.Error() * ciphertext2.Error());
}
}
}
}
// Check that many homomorphic additions can be performed.
TYPED_TEST(SymmetricRlweEncryptionTest, ManyHomomorphicAdds) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
// Sample a starting plaintext and ciphertext and create aggregators;
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
std::vector<typename TypeParam::Int> plaintext_sum = plaintext;
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext_sum,
this->Encrypt(key, plaintext, context.get()));
// Sample a fresh plaintext.
plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context.get()));
int num_adds = 50;
// Perform 50 homomorphic ciphertext additions with the fresh ciphertext.
for (int j = 0; j < num_adds; j++) {
// Add the new plaintext to the old plaintext.
for (unsigned int k = 0; k < context->GetN(); k++) {
plaintext_sum[k] += plaintext[k];
plaintext_sum[k] %= context->GetT();
}
// Add the new ciphertext to the old ciphertext.
ASSERT_OK_AND_ASSIGN(ciphertext_sum, ciphertext_sum + ciphertext);
}
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key, ciphertext_sum));
// Ensure the values are the same.
EXPECT_EQ(plaintext_sum, decrypted);
// Expect that the ciphertext sum's error grows by the additively by the
// ciphertext's error.
EXPECT_GT(ciphertext_sum.Error(), num_adds * ciphertext.Error());
}
}
// Check that ciphertext deserialization cannot handle more than
// rlwe::kMaxNumCoeffs coefficients.
TYPED_TEST(SymmetricRlweEncryptionTest,
ExceedMaxNumCoeffDeserializeCiphertext) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
int num_coeffs = rlwe::kMaxNumCoeffs + 1;
std::vector<rlwe::Polynomial<TypeParam>> c;
for (int i = 0; i < num_coeffs; i++) {
c.push_back(rlwe::Polynomial<TypeParam>(1, context->GetModulusParams()));
}
rlwe::SymmetricRlweCiphertext<TypeParam> ciphertext(
c, 1, 0, context->GetModulusParams(), context->GetErrorParams());
// Serialize and deserialize.
ASSERT_OK_AND_ASSIGN(rlwe::SerializedSymmetricRlweCiphertext serialized,
ciphertext.Serialize());
EXPECT_THAT(
rlwe::SymmetricRlweCiphertext<TypeParam>::Deserialize(
serialized, context->GetModulusParams(), context->GetErrorParams()),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr(absl::StrCat(
"Number of coefficients, ", serialized.c_size(),
", cannot be more than ", rlwe::kMaxNumCoeffs, "."))));
}
}
// Check that ciphertext serialization works.
TYPED_TEST(SymmetricRlweEncryptionTest, SerializeCiphertext) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context.get()));
// Serialize and deserialize.
ASSERT_OK_AND_ASSIGN(rlwe::SerializedSymmetricRlweCiphertext serialized,
ciphertext.Serialize());
ASSERT_OK_AND_ASSIGN(
auto deserialized,
rlwe::SymmetricRlweCiphertext<TypeParam>::Deserialize(
serialized, context->GetModulusParams(),
context->GetErrorParams()));
// Decrypt and check equality.
ASSERT_OK_AND_ASSIGN(
std::vector<typename TypeParam::Int> deserialized_plaintext,
rlwe::Decrypt<TypeParam>(key, deserialized));
EXPECT_EQ(plaintext, deserialized_plaintext);
// Check that the error stays the same.
EXPECT_EQ(deserialized.Error(), ciphertext.Error());
}
}
}
// Check that key serialization works.
TYPED_TEST(SymmetricRlweEncryptionTest, SerializeKey) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (int i = 0; i < kTestingRounds; i++) {
ASSERT_OK_AND_ASSIGN(auto original_key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
// Serialize key, deserialize, and ensure the deserialized key is
// interoperable with the original key.
ASSERT_OK_AND_ASSIGN(rlwe::SerializedNttPolynomial serialized,
original_key.Serialize());
ASSERT_OK_AND_ASSIGN(
auto deserialized_key,
rlwe::SymmetricRlweKey<TypeParam>::Deserialize(
context->GetVariance(), context->GetLogT(), serialized,
context->GetModulusParams(), context->GetNttParams()));
// Test that a ciphertext encrypted with the original key decrypts under
// the deserialized key.
ASSERT_OK_AND_ASSIGN(
auto ekey1, this->Encrypt(original_key, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto dkey1,
rlwe::Decrypt<TypeParam>(deserialized_key, ekey1));
EXPECT_EQ(dkey1, plaintext);
// Test that a ciphertext encrypted with the deserialized key decrypts
// under the original key.
ASSERT_OK_AND_ASSIGN(auto ekey2, this->Encrypt(deserialized_key,
plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto dkey2,
rlwe::Decrypt<TypeParam>(original_key, ekey2));
EXPECT_EQ(dkey2, plaintext);
}
}
}
// Try an ill-formed key modulus switching
TYPED_TEST(SymmetricRlweEncryptionTest, FailingKeyModulusReduction) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
// p is the original modulus and q is the new modulus we want to switch to
// For modulus switching, p % t must be equal to q % t, where t is the
// plaintext modulus, and both need to be congruent to 1 mod 2n.
typename TypeParam::Int p = context->GetModulus();
typename TypeParam::Int q = p - (context->GetN() << 1);
EXPECT_NE(q % context->GetT(), p % context->GetT());
ASSERT_OK_AND_ASSIGN(auto context_q, rlwe::RlweContext<TypeParam>::Create(
{.modulus = q,
.log_n = params.log_n,
.log_t = params.log_t,
.variance = params.variance}));
ASSERT_OK_AND_ASSIGN(auto key_p, this->SampleKey(context.get()));
auto status = key_p.template SwitchModulus<TypeParam>(
context_q->GetModulusParams(), context_q->GetNttParams());
EXPECT_THAT(status, StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("p % t != q % t")));
}
}
// Try an ill-formed ciphertext modulus switching
TYPED_TEST(SymmetricRlweEncryptionTest, FailingCiphertextModulusReduction) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
// p is the original modulus and q is the new modulus we want to switch to
// For modulus switching, p % t must be equal to q % t, where t is the
// plaintext modulus, and both need to be congruent to 1 mod 2n.
typename TypeParam::Int p = context->GetModulus();
typename TypeParam::Int q = p - (context->GetN() << 1);
EXPECT_NE(q % context->GetT(), p % context->GetT());
ASSERT_OK_AND_ASSIGN(auto context_q, rlwe::RlweContext<TypeParam>::Create(
{.modulus = q,
.log_n = params.log_n,
.log_t = params.log_t,
.variance = params.variance}));
ASSERT_OK_AND_ASSIGN(auto key_p, this->SampleKey(context.get()));
// sample ciphertext modulo p.
auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key_p, plaintext, context.get()));
auto status = ciphertext.template SwitchModulus<TypeParam>(
context->GetNttParams(), context_q->GetModulusParams(),
context_q->GetNttParams(), context_q->GetErrorParams(),
context->GetT());
EXPECT_THAT(status, StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("p % t != q % t")));
}
}
// Test modulus switching.
TYPED_TEST(SymmetricRlweEncryptionTest, ModulusReduction) {
for (const auto& params :
rlwe::testing::ContextParametersModulusSwitching<TypeParam>::Value()) {
auto params1 = std::get<0>(params), params2 = std::get<1>(params);
ASSERT_OK_AND_ASSIGN(auto context1,
rlwe::RlweContext<TypeParam>::Create(params1));
ASSERT_OK_AND_ASSIGN(auto context2,
rlwe::RlweContext<TypeParam>::Create(params2));
for (int i = 0; i < kTestingRounds; i++) {
// Create a key.
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context1.get()));
ASSERT_OK_AND_ASSIGN(
auto key_switched,
key.template SwitchModulus<TypeParam>(context2->GetModulusParams(),
context2->GetNttParams()));
// Create a plaintext.
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context1->GetN(),
context1->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context1.get()));
// Switch moduli.
ASSERT_OK_AND_ASSIGN(
auto ciphertext_switched,
ciphertext.template SwitchModulus<TypeParam>(
context1->GetNttParams(), context2->GetModulusParams(),
context2->GetNttParams(), context2->GetErrorParams(),
context2->GetT()));
// Decrypt in the smaller modulus.
ASSERT_OK_AND_ASSIGN(
auto decrypted,
rlwe::Decrypt<TypeParam>(key_switched, ciphertext_switched));
EXPECT_EQ(plaintext, decrypted);
}
}
}
// Check that modulus switching reduces the error.
TYPED_TEST(SymmetricRlweEncryptionTest, ModulusSwitchingReducesLargeError) {
for (const auto& params :
rlwe::testing::ContextParametersModulusSwitching<TypeParam>::Value()) {
auto params1 = std::get<0>(params), params2 = std::get<1>(params);
ASSERT_OK_AND_ASSIGN(auto context1,
rlwe::RlweContext<TypeParam>::Create(params1));
ASSERT_OK_AND_ASSIGN(auto context2,
rlwe::RlweContext<TypeParam>::Create(params2));
for (int i = 0; i < kTestingRounds; i++) {
// Create a key.
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context1.get()));
ASSERT_OK_AND_ASSIGN(
auto key_switched,
key.template SwitchModulus<TypeParam>(context2->GetModulusParams(),
context2->GetNttParams()));
// Create a plaintext.
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context1->GetN(),
context1->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context1.get()));
// Square the ciphertext
ASSERT_OK_AND_ASSIGN(auto squared, ciphertext* ciphertext);
// Switch moduli.
ASSERT_OK_AND_ASSIGN(
auto squared_switched,
squared.template SwitchModulus<TypeParam>(
context1->GetNttParams(), context2->GetModulusParams(),
context2->GetNttParams(), context2->GetErrorParams(),
context2->GetT()));
// Decrypt
ASSERT_OK_AND_ASSIGN(auto squared_decrypted,
rlwe::Decrypt<TypeParam>(key, squared));
ASSERT_OK_AND_ASSIGN(
auto squared_switched_decrypted,
rlwe::Decrypt<TypeParam>(key_switched, squared_switched));
EXPECT_EQ(squared_decrypted, squared_switched_decrypted);
// Expect that the error reduces after a modulus switch when the error is
// large.
EXPECT_LT(squared_switched.Error(), squared.Error());
// But that the error doesn't reduce when the error is small.
EXPECT_GT(squared_switched.Error(), ciphertext.Error());
}
}
}
// Check that we cannot perform operations between ciphertexts encrypted under
// different powers of s.
TYPED_TEST(SymmetricRlweEncryptionTest, OperationsFailOnMismatchedPowersOfS) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext1 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m1, rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext1, context->GetModulusParams()));
auto plaintext1_ntt = rlwe::Polynomial<TypeParam>::ConvertToNtt(
m1, context->GetNttParams(), context->GetModulusParams());
std::vector<typename TypeParam::Int> plaintext2 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
auto ciphertext1 = rlwe::SymmetricRlweCiphertext<TypeParam>(
{plaintext1_ntt}, 1, context->GetErrorParams()->B_encryption(),
context->GetModulusParams(), context->GetErrorParams());
auto ciphertext2 = rlwe::SymmetricRlweCiphertext<TypeParam>(
{plaintext1_ntt}, 2, context->GetErrorParams()->B_encryption(),
context->GetModulusParams(), context->GetErrorParams());
EXPECT_THAT(ciphertext1 + ciphertext2,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("must be encrypted with the same key")));
EXPECT_THAT(ciphertext1 * ciphertext2,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("must be encrypted with the same key")));
}
}
// Verifies that the power of S changes as expected in adds / mults.
TYPED_TEST(SymmetricRlweEncryptionTest, AddsAndMultPreservePowerOfS) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext1 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto m1, rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext1, context->GetModulusParams()));
auto plaintext1_ntt = rlwe::Polynomial<TypeParam>::ConvertToNtt(
m1, context->GetNttParams(), context->GetModulusParams());
std::vector<typename TypeParam::Int> plaintext2 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
auto ciphertext1 = rlwe::SymmetricRlweCiphertext<TypeParam>(
{plaintext1_ntt}, 2, context->GetErrorParams()->B_encryption(),
context->GetModulusParams(), context->GetErrorParams());
auto ciphertext2 = rlwe::SymmetricRlweCiphertext<TypeParam>(
{plaintext1_ntt}, 2, context->GetErrorParams()->B_encryption(),
context->GetModulusParams(), context->GetErrorParams());
EXPECT_EQ(ciphertext1.PowerOfS(), 2);
EXPECT_EQ(ciphertext2.PowerOfS(), 2);
ASSERT_OK_AND_ASSIGN(auto sum, ciphertext1 + ciphertext2);
EXPECT_EQ(sum.PowerOfS(), 2);
ASSERT_OK_AND_ASSIGN(auto prod, ciphertext1* ciphertext2);
EXPECT_EQ(prod.PowerOfS(), 2);
}
}
// Check that substitutions of the form 2^k + 1 work.
TYPED_TEST(SymmetricRlweEncryptionTest, Substitutes) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
for (int k = 1; k < context->GetLogN(); k++) {
int substitution_power = (1 << k) + 1;
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(
context->GetN(), context->GetT());
// Create the expected polynomial output by substituting the plaintext.
ASSERT_OK_AND_ASSIGN(auto m_plaintext,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext, context->GetModulusParams()));
auto plaintext_ntt = rlwe::Polynomial<TypeParam>::ConvertToNtt(
m_plaintext, context->GetNttParams(), context->GetModulusParams());
ASSERT_OK_AND_ASSIGN(
auto expected_ntt,
plaintext_ntt.Substitute(substitution_power, context->GetNttParams(),
context->GetModulusParams()));
std::vector<typename TypeParam::Int> expected =
rlwe::RemoveError<TypeParam>(
expected_ntt.InverseNtt(context->GetNttParams(),
context->GetModulusParams()),
context->GetModulus(), context->GetT(),
context->GetModulusParams());
// Encrypt and substitute the ciphertext. Decrypt with a substituted key.
ASSERT_OK_AND_ASSIGN(auto ciphertext,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(
auto substituted,
ciphertext.Substitute(substitution_power, context->GetNttParams()));
ASSERT_OK_AND_ASSIGN(auto key_sub, key.Substitute(substitution_power));
ASSERT_OK_AND_ASSIGN(std::vector<typename TypeParam::Int> decrypted,
rlwe::Decrypt<TypeParam>(key_sub, substituted));
EXPECT_EQ(decrypted, expected);
EXPECT_EQ(substituted.PowerOfS(), substitution_power);
EXPECT_EQ(substituted.Error(), ciphertext.Error());
}
}
}
// Check that substitution of 2 does not work.
TYPED_TEST(SymmetricRlweEncryptionTest, SubstitutionFailsOnEvenPower) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto enc,
this->Encrypt(key, plaintext, context.get()));
EXPECT_THAT(
enc.Substitute(2, context->GetNttParams()),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("power must be a non-negative odd integer")));
}
}
// Check that the power of s updates after several substitutions.
TYPED_TEST(SymmetricRlweEncryptionTest, PowerOfSUpdatedAfterRepeatedSubs) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
int substitution_power = 5;
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
auto plaintext = rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
// Encrypt and substitute the ciphertext. Decrypt with a substituted key.
ASSERT_OK_AND_ASSIGN(auto ciphertext1,
this->Encrypt(key, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(
auto ciphertext2,
ciphertext1.Substitute(substitution_power, context->GetNttParams()));
ASSERT_OK_AND_ASSIGN(
auto ciphertext3,
ciphertext2.Substitute(substitution_power, context->GetNttParams()));
EXPECT_EQ(ciphertext3.PowerOfS(),
(substitution_power * substitution_power) % (2 * key.Len()));
}
}
// Check that operations can only be performed when powers of s match.
TYPED_TEST(SymmetricRlweEncryptionTest, PowersOfSMustMatchOnOperations) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
int substitution_power = 5;
ASSERT_OK_AND_ASSIGN(auto key, this->SampleKey(context.get()));
std::vector<typename TypeParam::Int> plaintext1 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
std::vector<typename TypeParam::Int> plaintext2 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto ciphertext1,
this->Encrypt(key, plaintext1, context.get()));
ASSERT_OK_AND_ASSIGN(auto ciphertext2,
this->Encrypt(key, plaintext2, context.get()));
ASSERT_OK_AND_ASSIGN(
auto ciphertext2_sub,
ciphertext2.Substitute(substitution_power, context->GetNttParams()));
EXPECT_THAT(ciphertext1 + ciphertext2_sub,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("must be encrypted with the same key")));
EXPECT_THAT(ciphertext1 * ciphertext2_sub,
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("must be encrypted with the same key")));
}
}
// Check that the null key has value 0.
TYPED_TEST(SymmetricRlweEncryptionTest, NullKeyHasValueZero) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
rlwe::Polynomial<TypeParam> zero(context->GetN(),
context->GetModulusParams());
ASSERT_OK_AND_ASSIGN(
auto null_key,
rlwe::SymmetricRlweKey<TypeParam>::NullKey(
context->GetLogN(), context->GetVariance(), context->GetLogT(),
context->GetModulusParams(), context->GetNttParams()));
EXPECT_THAT(zero, Eq(null_key.Key()));
}
}
// Check the addition and subtraction of keys.
TYPED_TEST(SymmetricRlweEncryptionTest, AddAndSubKeys) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
ASSERT_OK_AND_ASSIGN(auto key_2, this->SampleKey(context.get()));
ASSERT_OK_AND_ASSIGN(auto key_3, key_1.Add(key_2));
ASSERT_OK_AND_ASSIGN(auto key_4, key_1.Sub(key_2));
ASSERT_OK_AND_ASSIGN(
rlwe::Polynomial<TypeParam> poly_3,
key_1.Key().Add(key_2.Key(), context->GetModulusParams()));
ASSERT_OK_AND_ASSIGN(
rlwe::Polynomial<TypeParam> poly_4,
key_1.Key().Sub(key_2.Key(), context->GetModulusParams()));
EXPECT_THAT(key_3.Key(), Eq(poly_3));
EXPECT_THAT(key_4.Key(), Eq(poly_4));
}
}
// Check that decryption works with added and subtracted keys.
TYPED_TEST(SymmetricRlweEncryptionTest, EncryptAndDecryptWithAddAndSubKeys) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
ASSERT_OK_AND_ASSIGN(auto key_2, this->SampleKey(context.get()));
ASSERT_OK_AND_ASSIGN(auto add_keys, key_1.Add(key_2));
ASSERT_OK_AND_ASSIGN(auto sub_keys, key_1.Sub(key_2));
std::vector<typename TypeParam::Int> plaintext =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto add_ciphertext,
this->Encrypt(add_keys, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto sub_ciphertext,
this->Encrypt(sub_keys, plaintext, context.get()));
ASSERT_OK_AND_ASSIGN(auto decrypted_add_ciphertext,
rlwe::Decrypt(add_keys, add_ciphertext));
ASSERT_OK_AND_ASSIGN(auto decrypted_sub_ciphertext,
rlwe::Decrypt(sub_keys, sub_ciphertext));
EXPECT_EQ(plaintext, decrypted_add_ciphertext);
EXPECT_EQ(plaintext, decrypted_sub_ciphertext);
}
}
// Check that the scheme is key homomorphic.
TYPED_TEST(SymmetricRlweEncryptionTest, IsKeyHomomorphic) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto prng_seed,
rlwe::SingleThreadPrng::GenerateSeed());
ASSERT_OK_AND_ASSIGN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
// Generate the keys.
ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
ASSERT_OK_AND_ASSIGN(auto key_2, this->SampleKey(context.get()));
// Generate the plaintexts.
std::vector<typename TypeParam::Int> plaintext_1 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
std::vector<typename TypeParam::Int> plaintext_2 =
rlwe::testing::SamplePlaintext<TypeParam>(context->GetN(),
context->GetT());
ASSERT_OK_AND_ASSIGN(auto plaintext_mont_1,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext_1, context->GetModulusParams()));
ASSERT_OK_AND_ASSIGN(auto plaintext_mont_2,
rlwe::testing::ConvertToMontgomery<TypeParam>(
plaintext_2, context->GetModulusParams()));
auto poly_1 = rlwe::Polynomial<TypeParam>::ConvertToNtt(
plaintext_mont_1, context->GetNttParams(), context->GetModulusParams());
auto poly_2 = rlwe::Polynomial<TypeParam>::ConvertToNtt(
plaintext_mont_2, context->GetNttParams(), context->GetModulusParams());
// Compute the expected plaintexts.
std::vector<typename TypeParam::Int> add_plaintext = plaintext_1;
std::vector<typename TypeParam::Int> sub_plaintext = plaintext_2;
std::transform(
plaintext_1.begin(), plaintext_1.end(), plaintext_2.begin(),
add_plaintext.begin(),
[&context = context](typename TypeParam::Int u,
typename TypeParam::Int v) ->
typename TypeParam::Int { return (u + v) % context->GetT(); });
std::transform(plaintext_1.begin(), plaintext_1.end(), plaintext_2.begin(),
sub_plaintext.begin(),
[&context = context](typename TypeParam::Int u,
typename TypeParam::Int v) ->
typename TypeParam::Int {
return (context->GetT() + u - v) % context->GetT();
});
// Sample the "a" to be used in both ciphertexts.
ASSERT_OK_AND_ASSIGN(auto a,
rlwe::SamplePolynomialFromPrng<TypeParam>(
key_1.Len(), prng.get(), key_1.ModulusParams()));
// Encrypt with the same a and different keys
ASSERT_OK_AND_ASSIGN(auto poly_ciphertext_1,
rlwe::internal::Encrypt(key_1, poly_1, a, prng.get()));
ASSERT_OK_AND_ASSIGN(auto poly_ciphertext_2,
rlwe::internal::Encrypt(key_2, poly_2, a, prng.get()));
// Add and Substract the ciphertexts
ASSERT_OK_AND_ASSIGN(
auto add_poly_ciphertext,
poly_ciphertext_1.Add(poly_ciphertext_2, context->GetModulusParams()));
ASSERT_OK_AND_ASSIGN(
auto sub_poly_ciphertext,
poly_ciphertext_1.Sub(poly_ciphertext_2, context->GetModulusParams()));
// The resulting ciphertexts should be decryptable unded the added (resp.
// substracted) keys.
ASSERT_OK_AND_ASSIGN(auto add_keys, key_1.Add(key_2));
ASSERT_OK_AND_ASSIGN(auto sub_keys, key_1.Sub(key_2));
ASSERT_OK_AND_ASSIGN(
auto decrypted_add_ciphertext,
rlwe::Decrypt(
add_keys,
rlwe::SymmetricRlweCiphertext<TypeParam>(
{add_poly_ciphertext, a.Negate(context->GetModulusParams())}, 1,
context->GetErrorParams()->B_encryption(),
context->GetModulusParams(), context->GetErrorParams())));
ASSERT_OK_AND_ASSIGN(
auto decrypted_sub_ciphertext,
rlwe::Decrypt(
sub_keys,
rlwe::SymmetricRlweCiphertext<TypeParam>(
{sub_poly_ciphertext, a.Negate(context->GetModulusParams())}, 1,
context->GetErrorParams()->B_encryption(),
context->GetModulusParams(), context->GetErrorParams())));
EXPECT_EQ(add_plaintext, decrypted_add_ciphertext);
EXPECT_EQ(sub_plaintext, decrypted_sub_ciphertext);
}
}
// Check that incompatible key cannot be added or subtracted.
TYPED_TEST(SymmetricRlweEncryptionTest, CannotAddOrSubIncompatibleKeys) {
for (const auto& params :
rlwe::testing::ContextParameters<TypeParam>::Value()) {
ASSERT_OK_AND_ASSIGN(auto context,
rlwe::RlweContext<TypeParam>::Create(params));
ASSERT_OK_AND_ASSIGN(auto context_different_variance,
rlwe::RlweContext<TypeParam>::Create(
{.modulus = params.modulus,
.log_n = params.log_n,
.log_t = params.log_t,
.variance = params.variance + 1}));
ASSERT_OK_AND_ASSIGN(
auto context_different_log_t,
rlwe::RlweContext<TypeParam>::Create({.modulus = params.modulus,
.log_n = params.log_n,
.log_t = params.log_t + 1,
.variance = params.variance}));
ASSERT_OK_AND_ASSIGN(auto key_1, this->SampleKey(context.get()));
ASSERT_OK_AND_ASSIGN(auto key_2,
this->SampleKey(context_different_variance.get()));
ASSERT_OK_AND_ASSIGN(auto key_3,
this->SampleKey(context_different_log_t.get()));
EXPECT_THAT(
key_1.Add(key_2),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("is different than the variance of this key")));
EXPECT_THAT(
key_1.Sub(key_2),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("is different than the variance of this key")));
EXPECT_THAT(key_1.Add(key_3),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("is different than the log_t of this key")));
EXPECT_THAT(key_1.Sub(key_3),
StatusIs(::absl::StatusCode::kInvalidArgument,
HasSubstr("is different than the log_t of this key")));
}
}
} // namespace
Codebase Browser
chromium