relinearization_key.h

/*
 * 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.
 */

#ifndef RLWE_RELINEARIZATION_KEY_H_
#define RLWE_RELINEARIZATION_KEY_H_

#include <cstdint>
#include <vector>

#include "sample_error.h"
#include "statusor.h"
#include "symmetric_encryption.h"

namespace rlwe {
// Represents a RelinearizationKey constructed from a symmetric-key. Applying a
// RelinearizationKey of order k to a ciphertext {m1}_s encrypting m1 with
// k components produces a ciphertext {m1}_s with 2 components encrypted with
// the same secret key s. This is one of two ways key-switching is used, the
// other being GaloisKeys.
//
// RelinearizationKeys are constructed based on the secret key. Two
// RelinearizationKeys that correspond to the same secret key, number of parts,
// and use the same decomposition modulus will not necessarily be equal. This is
// due to randomness that is sampled when the key is created. However, both will
// relinearize a ciphertext. This randomness is generated from a PRNG with a
// given prng_seed.
//
// This variant of key-switching is based on a decomposition modulo a general
// modulus T. We restrict this decomposition modulus T to be a power of 2, and
// log_2(T) generally ranges form 1 to log_2(q)/2. We treat T as a parameter to
// be optimized for. The matrix W is the sum of two matrices: (1) the first is
// the matrix A = [PowersofT(( s, ..., s^{k-1})) + t * e, 0], and (2) a matrix
// R which is perpendicular to (1, s). Note that A consists of "encryptions" of
// the PowersOfT (setting a = 0 in {as + et + m, -a}), and R basically consists
// of encryptions of 0 under (1,s). The sum of these two matrices yields
// essentially "encryptions" of the non-trivial powers of the length k secret
// key (s, s^2, ..., s^{k-1}) under the length 2 secret key (1,s).
//
// Details can be found in Appendix D.2 of https://eprint.iacr.org/2011/566.pdf
//
// Only MontgomeryInt types (Uint16, Uint32, Uint64, absl::uint128) are
// supported.

// The RelinearizationKey, which holds a vector of RelinearizationKeyParts of
// length (k - 1), where k is the number of parts of the ciphertext it applies
// to.
template <typename ModularInt>
class RelinearizationKey {
  using ModularIntParams = typename ModularInt::Params;

 public:
  // Initializes a RelinearizationKey based on a SymmetricRlweKey key that can
  // relinearize ciphertexts with at most num_parts components.
  // A positive log_decomposition_modulus corresponds to the decomposition
  // modulus T. The prng_seed is used to generate and encode the random entries
  // that form the bottom row of the matrix. For most RelinearizationKeys, the
  // substitution_power is 1. This corresponds to the power of x in the secret
  // key polynomial s(x^substitution_power) that the ciphertext is encrypted
  // with. This power changes when substitutions of the form x->x^k (Galois
  // automorphisms) have been applied to ciphertexts, yielding an encryption
  // with (1, s^k). In that case, we would use a relinearization key with
  // substition_power = k to return the ciphertext to be encrypted with (1,s).
  // See GaloisKey for an explicit wrapper around RelinearizationKey.
  static rlwe::StatusOr<RelinearizationKey> Create(
      const SymmetricRlweKey<ModularInt>& key, absl::string_view prng_seed,
      ssize_t num_parts, Uint64 log_decomposition_modulus,
      Uint64 substitution_power = 1);

  // Takes a SymmetricRlweCiphertext with at most num_parts components and
  // returns a 2 component SymmetricRlweCiphertext encoding the same message.
  // Returns an error when the number of components of ciphertext is larger than
  // the number of parts of the RelineraizationKey.
  rlwe::StatusOr<SymmetricRlweCiphertext<ModularInt>> ApplyTo(
      const SymmetricRlweCiphertext<ModularInt>& ciphertext) const;

  // Returns a SerializedRelinearizationKey containing a flattened
  // representation of the SerializedNttPolynomials in the key, the
  // log_decomposition_modulus, and the number of parts the key is comprised of.
  rlwe::StatusOr<SerializedRelinearizationKey> Serialize() const;

  // Requires that the number of NTT Polynomials in serialized is (num_parts) *
  // (2 * dimension) where dimension is the number of digits needed to represent
  // the modulus in base 2^{log_decomposition_modulus}. Crashes for non-valid
  // input parameters.
  static rlwe::StatusOr<RelinearizationKey> Deserialize(
      const SerializedRelinearizationKey& serialized,
      const ModularIntParams* modulus_params,
      const NttParameters<ModularInt>* ntt_params);

  // Substitution Power accessor.
  int SubstitutionPower() const { return substitution_power_; }

 private:
  // Represents part of the RelinearizationKey corresponding to a single
  // component of the secret key.
  class RelinearizationKeyPart {
   public:
    static rlwe::StatusOr<RelinearizationKeyPart> Create(
        const Polynomial<ModularInt>& key_power,
        const SymmetricRlweKey<ModularInt>& key,
        const Uint64 log_decomposition_modulus,
        const ModularInt& decomposition_modulus, int dimension,
        SecurePrng* prng, SecurePrng* prng_encryption);

    // For RelinearizationKeyPart i, this method takes the ith component of the
    // ciphertext and params, and applies the RelinearizationKeyPart matrix to
    // an expanded ciphertext component vector to produce a 2-component vector
    // of polynomials.
    rlwe::StatusOr<std::vector<Polynomial<ModularInt>>> ApplyPartTo(
        const Polynomial<ModularInt>& ciphertext_part,
        const ModularIntParams* modulus_params,
        const NttParameters<ModularInt>* ntt_params) const;

    // Creates a RelinearizationKeyPart out of a vector of Polynomials.
    static rlwe::StatusOr<RelinearizationKeyPart> Deserialize(
        const std::vector<SerializedNttPolynomial>& polynomials,
        Uint64 log_decomposition_modulus, SecurePrng* prng,
        const ModularIntParams* modulus_params,
        const NttParameters<ModularInt>* ntt_params);

    std::vector<Polynomial<ModularInt>> Matrix() const { return matrix_[0]; }

   private:
    RelinearizationKeyPart(
        std::vector<std::vector<Polynomial<ModularInt>>> matrix,
        Uint64 log_decomposition_modulus)
        : matrix_(std::move(matrix)),
          log_decomposition_modulus_(log_decomposition_modulus) {}

    std::vector<std::vector<Polynomial<ModularInt>>> matrix_;

    const Uint64 log_decomposition_modulus_;
  };

  // Creates an empty RelinearizationKey.
  RelinearizationKey(Uint64 log_decomposition_modulus,
                     const ModularInt& decomposition_modulus,
                     const ModularIntParams* params,
                     const NttParameters<ModularInt>* ntt_params)
      : log_decomposition_modulus_(log_decomposition_modulus),
        decomposition_modulus_(decomposition_modulus),
        substitution_power_(1),
        modulus_params_(params),
        ntt_params_(ntt_params) {}

  RelinearizationKey(const SymmetricRlweKey<ModularInt>& key,
                     absl::string_view prng_seed, ssize_t num_parts,
                     Uint64 log_decomposition_modulus,
                     Uint64 substitution_power,
                     ModularInt decomposition_modulus,
                     std::vector<RelinearizationKeyPart> relinearization_key);

  // Dimension of the relinearization key matrix.
  int dimension_;

  // Number of parts the key corresponds to.
  int num_parts_;

  const Uint64 log_decomposition_modulus_;

  ModularInt decomposition_modulus_;

  // Substitution power.
  int substitution_power_;

  // Modulus parameters. Does not take ownership.
  const ModularIntParams* modulus_params_;

  // NTT parameters. Does not take ownership.
  const NttParameters<ModularInt>* ntt_params_;

  // The key-switching matrix. Each component in the vector is a
  // RelinearizationKeyPart: a 2 by dimension_ matrix corresponding to a single
  // power of the key. In this way, a RelinearizationKey for a length k
  // ciphertext can be used to transform ciphertext with any number of parts up
  // to k by only using items 0 to k-1 of the relinearization_key_.
  std::vector<RelinearizationKeyPart> relinearization_key_;

  // Prng seed
  std::string prng_seed_;
};

}  // namespace rlwe

#endif  // RLWE_RELINEARIZATION_KEY_H_