123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415 |
- /*
- * Copyright 2018 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 "galois_key.h"
- #include <gmock/gmock.h>
- #include <gtest/gtest.h>
- #include <google/protobuf/util/message_differencer.h>
- #include "constants.h"
- #include "montgomery.h"
- #include "ntt_parameters.h"
- #include "polynomial.h"
- #include "prng/integral_prng_types.h"
- #include "status_macros.h"
- #include "symmetric_encryption.h"
- #include "testing/protobuf_matchers.h"
- #include "testing/status_matchers.h"
- #include "testing/status_testing.h"
- #include "testing/testing_prng.h"
- #include "testing/testing_utils.h"
- namespace {
- using Uint64 = rlwe::Uint64;
- unsigned int seed = 0;
- // Set constants.
- const Uint64 kLogPlaintextModulus = 1;
- const Uint64 kPlaintextModulus = (1 << kLogPlaintextModulus) + 1;
- const Uint64 kLogDecompositionModulus = 2;
- const Uint64 kLargeLogDecompositionModulus = 31;
- // Useful typedefs.
- using uint_m = rlwe::MontgomeryInt<Uint64>;
- using Polynomial = rlwe::Polynomial<uint_m>;
- using Ciphertext = rlwe::SymmetricRlweCiphertext<uint_m>;
- using Key = rlwe::SymmetricRlweKey<uint_m>;
- using ::rlwe::testing::EqualsProto;
- using ::rlwe::testing::StatusIs;
- using ::testing::HasSubstr;
- // Test fixture.
- class GaloisKeyTest : public ::testing::Test {
- protected:
- void SetUp() override {
- ASSERT_OK_AND_ASSIGN(params59_, uint_m::Params::Create(rlwe::kModulus59));
- ASSERT_OK_AND_ASSIGN(auto ntt_params,
- rlwe::InitializeNttParameters<uint_m>(
- rlwe::testing::kLogCoeffs, params59_.get()));
- ntt_params_ = absl::make_unique<const rlwe::NttParameters<uint_m>>(
- std::move(ntt_params));
- ASSERT_OK_AND_ASSIGN(
- auto error_params,
- rlwe::ErrorParams<uint_m>::Create(rlwe::testing::kDefaultLogT,
- rlwe::testing::kDefaultVariance,
- params59_.get(), ntt_params_.get()));
- error_params_ =
- absl::make_unique<const rlwe::ErrorParams<uint_m>>(error_params);
- }
- // Sample a random key.
- rlwe::StatusOr<Key> SampleKey(
- Uint64 variance = rlwe::testing::kDefaultVariance,
- Uint64 log_t = kLogPlaintextModulus) {
- RLWE_ASSIGN_OR_RETURN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- RLWE_ASSIGN_OR_RETURN(auto prng, rlwe::SingleThreadPrng::Create(prng_seed));
- return Key::Sample(rlwe::testing::kLogCoeffs, variance, log_t,
- params59_.get(), ntt_params_.get(), prng.get());
- }
- // Convert a vector of integers to a vector of montgomery integers.
- rlwe::StatusOr<std::vector<uint_m>> ConvertToMontgomery(
- const std::vector<uint_m::Int>& coeffs, const uint_m::Params* params) {
- std::vector<uint_m> output(coeffs.size(), uint_m::ImportZero(params));
- for (unsigned int i = 0; i < output.size(); i++) {
- RLWE_ASSIGN_OR_RETURN(output[i], uint_m::ImportInt(coeffs[i], params));
- }
- return output;
- }
- // Sample a random plaintext.
- std::vector<uint_m::Int> SamplePlaintext(
- uint_m::Int t = kPlaintextModulus,
- Uint64 coeffs = rlwe::testing::kCoeffs) {
- std::vector<uint_m::Int> plaintext(coeffs);
- for (unsigned int i = 0; i < coeffs; i++) {
- plaintext[i] = rand_r(&seed) % t;
- }
- return plaintext;
- }
- // Encrypt a plaintext.
- rlwe::StatusOr<Ciphertext> Encrypt(
- const Key& key, const std::vector<uint_m::Int>& plaintext) {
- RLWE_ASSIGN_OR_RETURN(auto mp,
- ConvertToMontgomery(plaintext, params59_.get()));
- auto plaintext_ntt =
- Polynomial::ConvertToNtt(mp, ntt_params_.get(), params59_.get());
- 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<uint_m>(key, plaintext_ntt, error_params_.get(),
- prng.get());
- }
- std::unique_ptr<const uint_m::Params> params59_;
- std::unique_ptr<const rlwe::NttParameters<uint_m>> ntt_params_;
- std::unique_ptr<const rlwe::ErrorParams<uint_m>> error_params_;
- };
- TEST_F(GaloisKeyTest, GaloisKeyPowerOfSDoesNotMatchSubPower) {
- int substitution_power = 3;
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLargeLogDecompositionModulus));
- auto plaintext = SamplePlaintext(kPlaintextModulus);
- ASSERT_OK_AND_ASSIGN(auto ciphertext, Encrypt(key, plaintext));
- ASSERT_OK_AND_ASSIGN(
- auto subbed_ciphertext,
- ciphertext.Substitute(substitution_power + 2, ntt_params_.get()));
- EXPECT_THAT(
- galois_key.ApplyTo(subbed_ciphertext),
- StatusIs(::absl::StatusCode::kInvalidArgument,
- HasSubstr(absl::StrCat(
- "Ciphertext PowerOfS: ", subbed_ciphertext.PowerOfS(),
- " doesn't match the key substitution power: ",
- substitution_power))));
- }
- TEST_F(GaloisKeyTest, GaloisKeyUpdatesPowerOfS) {
- int substitution_power = 3;
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLargeLogDecompositionModulus));
- auto plaintext = SamplePlaintext(kPlaintextModulus);
- // Substituted ciphertext has substition_power PowerOfS.
- ASSERT_OK_AND_ASSIGN(auto ciphertext, Encrypt(key, plaintext));
- ASSERT_OK_AND_ASSIGN(
- auto subbed_ciphertext,
- ciphertext.Substitute(substitution_power, ntt_params_.get()));
- EXPECT_EQ(subbed_ciphertext.PowerOfS(), substitution_power);
- // PowerOfS transformed back to 1.
- ASSERT_OK_AND_ASSIGN(auto transformed_ciphertext,
- galois_key.ApplyTo(subbed_ciphertext));
- EXPECT_EQ(transformed_ciphertext.PowerOfS(), 1);
- }
- TEST_F(GaloisKeyTest, KeySwitchedCiphertextDecrypts) {
- int substitution_power = 3;
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLogDecompositionModulus));
- // Create the initial plaintexts.
- std::vector<uint_m::Int> plaintext = SamplePlaintext(kPlaintextModulus);
- // Create the expected polynomial output by substituting the plaintext.
- ASSERT_OK_AND_ASSIGN(auto mp1,
- ConvertToMontgomery(plaintext, params59_.get()));
- Polynomial plaintext_ntt =
- Polynomial::ConvertToNtt(mp1, ntt_params_.get(), params59_.get());
- ASSERT_OK_AND_ASSIGN(
- Polynomial expected_ntt,
- plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
- params59_.get()));
- std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
- expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
- params59_->modulus, kPlaintextModulus, params59_.get());
- // Encrypt and substitute the ciphertext. Decrypt with a substituted key.
- ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
- ASSERT_OK_AND_ASSIGN(
- auto ciphertext,
- intermediate.Substitute(substitution_power, ntt_params_.get()));
- ASSERT_OK_AND_ASSIGN(auto transformed_ciphertext,
- galois_key.ApplyTo(ciphertext));
- ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
- rlwe::Decrypt<uint_m>(key, transformed_ciphertext));
- EXPECT_EQ(decrypted, expected);
- }
- TEST_F(GaloisKeyTest, ComposingSubstitutions) {
- // Ensure that a ciphertext can be substituted by composing substitutions in
- // steps that have GaloisKeys.
- int substitution_power = 9;
- // Applying the substitution s -> s(x^3) twice will yield the substitution
- // power.
- int galois_power = 3;
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, galois_power,
- kLogDecompositionModulus));
- auto plaintext = SamplePlaintext(kPlaintextModulus);
- // Create the expected polynomial output by substituting the plaintext.
- ASSERT_OK_AND_ASSIGN(auto mp1,
- ConvertToMontgomery(plaintext, params59_.get()));
- Polynomial plaintext_ntt =
- Polynomial::ConvertToNtt(mp1, ntt_params_.get(), params59_.get());
- ASSERT_OK_AND_ASSIGN(
- Polynomial expected_ntt,
- plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
- params59_.get()));
- std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
- expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
- params59_->modulus, kPlaintextModulus, params59_.get());
- // Encrypt and substitute the ciphertext in steps using a single galois key.
- ASSERT_OK_AND_ASSIGN(auto ciphertext, Encrypt(key, plaintext));
- ASSERT_OK_AND_ASSIGN(auto sub_ciphertext,
- ciphertext.Substitute(galois_power, ntt_params_.get()));
- ASSERT_OK_AND_ASSIGN(auto ciphertext_power_3,
- galois_key.ApplyTo(sub_ciphertext));
- ASSERT_OK_AND_ASSIGN(
- auto sub_ciphertext_power_3,
- ciphertext_power_3.Substitute(galois_power, ntt_params_.get()));
- ASSERT_OK_AND_ASSIGN(auto ciphertext_power_9,
- galois_key.ApplyTo(sub_ciphertext_power_3));
- EXPECT_EQ(ciphertext_power_9.PowerOfS(), 1);
- ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
- rlwe::Decrypt<uint_m>(key, ciphertext_power_9));
- EXPECT_EQ(decrypted, expected);
- }
- TEST_F(GaloisKeyTest, LargeDecompositionModulus) {
- int substitution_power = 3;
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLargeLogDecompositionModulus));
- auto plaintext = SamplePlaintext(kPlaintextModulus);
- // Create the expected polynomial output by substituting the plaintext.
- ASSERT_OK_AND_ASSIGN(auto mp1,
- ConvertToMontgomery(plaintext, params59_.get()));
- Polynomial plaintext_ntt =
- Polynomial::ConvertToNtt(mp1, ntt_params_.get(), params59_.get());
- ASSERT_OK_AND_ASSIGN(
- Polynomial expected_ntt,
- plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
- params59_.get()));
- std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
- expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
- params59_->modulus, kPlaintextModulus, params59_.get());
- // Encrypt and substitute the ciphertext. Decrypt with a substituted key.
- ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
- ASSERT_OK_AND_ASSIGN(
- auto ciphertext,
- intermediate.Substitute(substitution_power, ntt_params_.get()));
- ASSERT_OK_AND_ASSIGN(auto transformed_ciphertext,
- galois_key.ApplyTo(ciphertext));
- ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
- rlwe::Decrypt<uint_m>(key, transformed_ciphertext));
- EXPECT_EQ(decrypted, expected);
- }
- TEST_F(GaloisKeyTest, CiphertextWithTooManyComponents) {
- int substitution_power = 3;
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLargeLogDecompositionModulus));
- auto plaintext = SamplePlaintext(kPlaintextModulus);
- ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
- ASSERT_OK_AND_ASSIGN(
- auto ciphertext,
- intermediate.Substitute(substitution_power, ntt_params_.get()));
- ASSERT_OK_AND_ASSIGN(auto product, ciphertext* ciphertext);
- EXPECT_THAT(galois_key.ApplyTo(product),
- StatusIs(::absl::StatusCode::kInvalidArgument,
- HasSubstr("RelinearizationKey not large enough")));
- }
- TEST_F(GaloisKeyTest, DeserializedKeySwitches) {
- int substitution_power = 3;
- auto plaintext = SamplePlaintext(kPlaintextModulus);
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLargeLogDecompositionModulus));
- // Serialize and deserialize.
- ASSERT_OK_AND_ASSIGN(auto serialized, galois_key.Serialize());
- ASSERT_OK_AND_ASSIGN(auto deserialized,
- rlwe::GaloisKey<uint_m>::Deserialize(
- serialized, params59_.get(), ntt_params_.get()));
- // Create the expected polynomial output by substituting the plaintext.
- ASSERT_OK_AND_ASSIGN(auto mp,
- ConvertToMontgomery(plaintext, params59_.get()));
- Polynomial plaintext_ntt =
- Polynomial::ConvertToNtt(mp, ntt_params_.get(), params59_.get());
- ASSERT_OK_AND_ASSIGN(
- Polynomial expected_ntt,
- plaintext_ntt.Substitute(substitution_power, ntt_params_.get(),
- params59_.get()));
- std::vector<uint_m::Int> expected = rlwe::RemoveError<uint_m>(
- expected_ntt.InverseNtt(ntt_params_.get(), params59_.get()),
- params59_->modulus, kPlaintextModulus, params59_.get());
- // Encrypt and substitute the ciphertext.
- ASSERT_OK_AND_ASSIGN(auto intermediate, Encrypt(key, plaintext));
- ASSERT_OK_AND_ASSIGN(
- auto ciphertext,
- intermediate.Substitute(substitution_power, ntt_params_.get()));
- // Key-switch with the original galois key.
- ASSERT_OK_AND_ASSIGN(auto key_switched_ciphertext,
- galois_key.ApplyTo(ciphertext));
- ASSERT_OK_AND_ASSIGN(std::vector<uint_m::Int> decrypted,
- rlwe::Decrypt<uint_m>(key, key_switched_ciphertext));
- // Key-switch with the deserialized galois key.
- ASSERT_OK_AND_ASSIGN(auto key_switched_ciphertext_deserialized,
- deserialized.ApplyTo(ciphertext));
- ASSERT_OK_AND_ASSIGN(
- std::vector<uint_m::Int> deserialized_decrypted,
- rlwe::Decrypt<uint_m>(key, key_switched_ciphertext_deserialized));
- EXPECT_EQ(deserialized_decrypted, expected);
- EXPECT_EQ(deserialized_decrypted, decrypted);
- }
- TEST_F(GaloisKeyTest, DeserializationFailsWithIncorrectModulus) {
- int substitution_power = 3;
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLargeLogDecompositionModulus));
- ASSERT_OK_AND_ASSIGN(auto params29, uint_m::Params::Create(rlwe::kModulus29));
- // Serialize and deserialize.
- ASSERT_OK_AND_ASSIGN(auto serialized, galois_key.Serialize());
- EXPECT_THAT(
- rlwe::GaloisKey<uint_m>::Deserialize(serialized, params29.get(),
- ntt_params_.get()),
- StatusIs(::absl::StatusCode::kInvalidArgument,
- HasSubstr(absl::StrCat(
- "Log decomposition modulus, ", kLargeLogDecompositionModulus,
- ", must be at most: ", params29->log_modulus, "."))));
- }
- TEST_F(GaloisKeyTest, SerializationsOfIdentialKeysEqual) {
- int substitution_power = 3;
- auto plaintext = SamplePlaintext(kPlaintextModulus);
- ASSERT_OK_AND_ASSIGN(auto key, SampleKey());
- ASSERT_OK_AND_ASSIGN(std::string prng_seed,
- rlwe::SingleThreadPrng::GenerateSeed());
- ASSERT_OK_AND_ASSIGN(auto galois_key, rlwe::GaloisKey<uint_m>::Create(
- key, prng_seed, substitution_power,
- kLargeLogDecompositionModulus));
- auto galois_key_copy = galois_key;
- // Serialize both matrices.
- ASSERT_OK_AND_ASSIGN(auto serialized, galois_key.Serialize());
- ASSERT_OK_AND_ASSIGN(auto serialized_copy, galois_key_copy.Serialize());
- // Check that two serializations of the same matrix are equal.
- EXPECT_EQ(serialized_copy.SerializeAsString(), serialized.SerializeAsString());
- }
- } // namespace
|