123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429 |
- // Copyright 2020 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
- //
- // http://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 "montgomery.h"
- #include "third_party/shell-encryption/base/shell_encryption_export.h"
- #include "third_party/shell-encryption/base/shell_encryption_export_template.h"
- #include "transcription.h"
- namespace rlwe {
- template <typename T>
- rlwe::StatusOr<std::unique_ptr<const MontgomeryIntParams<T>>>
- MontgomeryIntParams<T>::Create(Int modulus) {
- // Check that the modulus is smaller than max(Int) / 4.
- Int most_significant_bit = modulus >> (bitsize_int - 2);
- if (most_significant_bit != 0) {
- return absl::InvalidArgumentError(absl::StrCat(
- "The modulus should be less than 2^", (bitsize_int - 2), "."));
- }
- if ((modulus % 2) == 0) {
- return absl::InvalidArgumentError(
- absl::StrCat("The modulus should be odd."));
- }
- return absl::WrapUnique<const MontgomeryIntParams>(
- new MontgomeryIntParams(modulus));
- }
- // From Hacker's Delight.
- template <typename T>
- std::tuple<T, T> MontgomeryIntParams<T>::Inverses(BigInt modulus_bigint,
- BigInt r) {
- // Invariants
- // 1) sum = x * 2^w - y * modulus.
- // 2) sum is always a power of 2.
- // 3) modulus is odd.
- // 4) y is always even.
- // sum will decrease from 2^w to 2^0 = 1
- BigInt x = 1;
- BigInt y = 0;
- for (int i = bitsize_int; i > 0; i--) {
- // Ensure that x is even.
- if ((x & 1) == 1) {
- // If x is odd, make x even by adding modulus to x and changing the
- // value of y accordingly (y remains even).
- //
- // sum = x * 2^w - y * modulus
- // sum = (x + modulus) * 2^w - (y + 2^w) * modulus
- //
- // We can then divide the new values of x and y by 2 safely.
- x += modulus_bigint;
- y += r;
- }
- // Divide x and y by 2
- x >>= 1;
- y >>= 1;
- }
- // Return the inverses
- return std::make_tuple(static_cast<Int>(x), static_cast<Int>(y));
- }
- template <typename T>
- rlwe::StatusOr<MontgomeryInt<T>> MontgomeryInt<T>::ImportInt(
- Int n, const Params* params) {
- BigInt product = static_cast<BigInt>(params->r_mod_modulus_barrett) * n;
- Int result = static_cast<Int>(product >> Params::bitsize_int);
- result = n * params->r_mod_modulus - result * params->modulus;
- // The steps above produce an integer that is in the range [0, 2N).
- // We now reduce to the range [0, N).
- result -= (result >= params->modulus) ? params->modulus : 0;
- return MontgomeryInt(result);
- }
- template <typename T>
- MontgomeryInt<T> MontgomeryInt<T>::ImportZero(const Params* params) {
- return MontgomeryInt(params->Zero());
- }
- template <typename T>
- MontgomeryInt<T> MontgomeryInt<T>::ImportOne(const Params* params) {
- // 1 should be multiplied by r_mod_modulus; we load directly r_mod_modulus.
- return MontgomeryInt(static_cast<Int>(params->r_mod_modulus));
- }
- template <typename T>
- typename internal::BigInt<T>::value_type MontgomeryInt<T>::DivAndTruncate(
- BigInt dividend, BigInt divisor) {
- return dividend / divisor;
- }
- template <typename T>
- rlwe::StatusOr<std::string> MontgomeryInt<T>::Serialize(
- const Params* params) const {
- // Use transcription to transform all the LogModulus() bits of input into a
- // vector of unsigned char.
- RLWE_ASSIGN_OR_RETURN(
- auto v, (TranscribeBits<Int, Uint8>({this->n_}, params->log_modulus,
- params->log_modulus, 8)));
- // Return a string
- return std::string(std::make_move_iterator(v.begin()),
- std::make_move_iterator(v.end()));
- }
- template <typename T>
- rlwe::StatusOr<std::string> MontgomeryInt<T>::SerializeVector(
- const std::vector<MontgomeryInt>& coeffs, const Params* params) {
- if (coeffs.size() > kMaxNumCoeffs) {
- return absl::InvalidArgumentError(
- absl::StrCat("Number of coefficients, ", coeffs.size(),
- ", cannot be larger than ", kMaxNumCoeffs, "."));
- } else if (coeffs.empty()) {
- return absl::InvalidArgumentError("Cannot serialize an empty vector.");
- }
- // Bits required to represent modulus.
- int bit_size = params->log_modulus;
- // Extract the values
- std::vector<Int> coeffs_values;
- coeffs_values.reserve(coeffs.size());
- for (const auto& c : coeffs) {
- coeffs_values.push_back(c.n_);
- }
- // Use transcription to transform all the bit_size bits of input into a
- // vector of unsigned char.
- RLWE_ASSIGN_OR_RETURN(
- auto v,
- (TranscribeBits<Int, Uint8>(
- coeffs_values, coeffs_values.size() * bit_size, bit_size, 8)));
- // Return a string
- return std::string(std::make_move_iterator(v.begin()),
- std::make_move_iterator(v.end()));
- }
- template <typename T>
- rlwe::StatusOr<MontgomeryInt<T>> MontgomeryInt<T>::Deserialize(
- absl::string_view payload, const Params* params) {
- // Parse the string as unsigned char
- std::vector<Uint8> input(payload.begin(), payload.end());
- // Bits required to represent modulus.
- int bit_size = params->log_modulus;
- // Recover the coefficients from the input stream.
- RLWE_ASSIGN_OR_RETURN(auto coeffs_values, (TranscribeBits<Uint8, Int>(
- input, bit_size, 8, bit_size)));
- // There will be at least one coefficient in coeff_values because bit_size
- // is always expected to be positive.
- return MontgomeryInt(coeffs_values[0]);
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>>
- MontgomeryInt<T>::DeserializeVector(int num_coeffs,
- absl::string_view serialized,
- const Params* params) {
- if (num_coeffs < 0) {
- return absl::InvalidArgumentError(
- "Number of coefficients must be non-negative.");
- }
- if (num_coeffs > kMaxNumCoeffs) {
- return absl::InvalidArgumentError(
- absl::StrCat("Number of coefficients, ", num_coeffs, ", cannot be ",
- "larger than ", kMaxNumCoeffs, "."));
- }
- // Parse the string as unsigned char
- std::vector<Uint8> input(serialized.begin(), serialized.end());
- // Bits required to represent modulus.
- int bit_size = params->log_modulus;
- // Recover the coefficients from the input stream.
- RLWE_ASSIGN_OR_RETURN(
- auto coeffs_values,
- (TranscribeBits<Uint8, Int>(input, bit_size * num_coeffs, 8, bit_size)));
- // Check that the number of coefficients recovered is at least what is
- // expected.
- if (coeffs_values.size() < num_coeffs) {
- return absl::InvalidArgumentError("Given serialization is invalid.");
- }
- // Create a vector of Montgomery Int from the values.
- std::vector<MontgomeryInt> coeffs;
- coeffs.reserve(num_coeffs);
- for (int i = 0; i < num_coeffs; i++) {
- coeffs.push_back(MontgomeryInt(coeffs_values[i]));
- }
- return coeffs;
- }
- template <typename T>
- std::tuple<T, T> MontgomeryInt<T>::GetConstant(const Params* params) const {
- Int constant = ExportInt(params);
- Int constant_barrett = static_cast<Int>(
- (static_cast<BigInt>(constant) << params->bitsize_int) / params->modulus);
- return std::make_tuple(constant, constant_barrett);
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>> MontgomeryInt<T>::BatchAdd(
- const std::vector<MontgomeryInt>& in1,
- const std::vector<MontgomeryInt>& in2, const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(BatchAddInPlace(&out, in2, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchAddInPlace(
- std::vector<MontgomeryInt>* in1, const std::vector<MontgomeryInt>& in2,
- const Params* params) {
- // If the input vectors' sizes don't match, return an error.
- if (in1->size() != in2.size()) {
- return absl::InvalidArgumentError("Input vectors are not of same size");
- }
- int i = 0;
- // The remaining elements, if any, are added in place sequentially.
- for (; i < in1->size(); i++) {
- (*in1)[i].AddInPlace(in2[i], params);
- }
- return absl::OkStatus();
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>> MontgomeryInt<T>::BatchAdd(
- const std::vector<MontgomeryInt>& in1, const MontgomeryInt& in2,
- const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(BatchAddInPlace(&out, in2, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchAddInPlace(std::vector<MontgomeryInt>* in1,
- const MontgomeryInt& in2,
- const Params* params) {
- int i = 0;
- std::for_each(in1->begin() + i, in1->end(),
- [&in2 = in2, params](MontgomeryInt& coeff) {
- coeff.AddInPlace(in2, params);
- });
- return absl::OkStatus();
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>> MontgomeryInt<T>::BatchSub(
- const std::vector<MontgomeryInt>& in1,
- const std::vector<MontgomeryInt>& in2, const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(BatchSubInPlace(&out, in2, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchSubInPlace(
- std::vector<MontgomeryInt>* in1, const std::vector<MontgomeryInt>& in2,
- const Params* params) {
- // If the input vectors' sizes don't match, return an error.
- if (in1->size() != in2.size()) {
- return absl::InvalidArgumentError("Input vectors are not of same size");
- }
- int i = 0;
- for (; i < in1->size(); i++) {
- (*in1)[i].SubInPlace(in2[i], params);
- }
- return absl::OkStatus();
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>> MontgomeryInt<T>::BatchSub(
- const std::vector<MontgomeryInt>& in1, const MontgomeryInt& in2,
- const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(BatchSubInPlace(&out, in2, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchSubInPlace(std::vector<MontgomeryInt>* in1,
- const MontgomeryInt& in2,
- const Params* params) {
- int i = 0;
- std::for_each(in1->begin() + i, in1->end(),
- [&in2 = in2, params](MontgomeryInt& coeff) {
- coeff.SubInPlace(in2, params);
- });
- return absl::OkStatus();
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>>
- MontgomeryInt<T>::BatchMulConstant(const std::vector<MontgomeryInt>& in1,
- const std::vector<Int>& constant,
- const std::vector<Int>& constant_barrett,
- const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(
- BatchMulConstantInPlace(&out, constant, constant_barrett, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchMulConstantInPlace(
- std::vector<MontgomeryInt>* in1, const std::vector<Int>& constant,
- const std::vector<Int>& constant_barrett, const Params* params) {
- // If the input vectors' sizes don't match, return an error.
- if (in1->size() != constant.size() ||
- constant.size() != constant_barrett.size()) {
- return absl::InvalidArgumentError("Input vectors are not of same size");
- }
- int i = 0;
- for (; i < in1->size(); i++) {
- (*in1)[i].MulConstantInPlace(constant[i], constant_barrett[i], params);
- }
- return absl::OkStatus();
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>>
- MontgomeryInt<T>::BatchMulConstant(const std::vector<MontgomeryInt>& in1,
- const Int& constant,
- const Int& constant_barrett,
- const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(
- BatchMulConstantInPlace(&out, constant, constant_barrett, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchMulConstantInPlace(
- std::vector<MontgomeryInt>* in1, const Int& constant,
- const Int& constant_barrett, const Params* params) {
- int i = 0;
- for (; i < in1->size(); i++) {
- (*in1)[i].MulConstantInPlace(constant, constant_barrett, params);
- }
- return absl::OkStatus();
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>> MontgomeryInt<T>::BatchMul(
- const std::vector<MontgomeryInt>& in1,
- const std::vector<MontgomeryInt>& in2, const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(BatchMulInPlace(&out, in2, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchMulInPlace(
- std::vector<MontgomeryInt>* in1, const std::vector<MontgomeryInt>& in2,
- const Params* params) {
- // If the input vectors' sizes don't match, return an error.
- if (in1->size() != in2.size()) {
- return absl::InvalidArgumentError("Input vectors are not of same size");
- }
- int i = 0;
- for (; i < in1->size(); i++) {
- (*in1)[i].MulInPlace(in2[i], params);
- }
- return absl::OkStatus();
- }
- template <typename T>
- rlwe::StatusOr<std::vector<MontgomeryInt<T>>> MontgomeryInt<T>::BatchMul(
- const std::vector<MontgomeryInt>& in1, const MontgomeryInt& in2,
- const Params* params) {
- std::vector<MontgomeryInt> out = in1;
- RLWE_RETURN_IF_ERROR(BatchMulInPlace(&out, in2, params));
- return out;
- }
- template <typename T>
- absl::Status MontgomeryInt<T>::BatchMulInPlace(std::vector<MontgomeryInt>* in1,
- const MontgomeryInt& in2,
- const Params* params) {
- int i = 0;
- std::for_each(in1->begin() + i, in1->end(),
- [&in2 = in2, params](MontgomeryInt& coeff) {
- coeff.MulInPlace(in2, params);
- });
- return absl::OkStatus();
- }
- template <typename T>
- MontgomeryInt<T> MontgomeryInt<T>::ModExp(Int exponent,
- const Params* params) const {
- MontgomeryInt result = MontgomeryInt::ImportOne(params);
- MontgomeryInt base = *this;
- // Uses the bits of the exponent to gradually compute the result.
- // When bit k of the exponent is 1, the result is multiplied by
- // base^{2^k}.
- while (exponent > 0) {
- // If the current bit (bit k) is 1, multiply base^{2^k} into the result.
- if (exponent % 2 == 1) {
- result.MulInPlace(base, params);
- }
- // Update base from base^{2^k} to base^{2^{k+1}}.
- base.MulInPlace(base, params);
- exponent >>= 1;
- }
- return result;
- }
- template <typename T>
- MontgomeryInt<T> MontgomeryInt<T>::MultiplicativeInverse(
- const Params* params) const {
- return (*this).ModExp(static_cast<Int>(params->modulus - 2), params);
- }
- // Instantiations of MontgomeryInt and MontgomeryIntParams with specific
- // integral types.
- template struct EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryIntParams<Uint16>;
- template struct EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryIntParams<Uint32>;
- template struct EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryIntParams<Uint64>;
- template struct EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryIntParams<absl::uint128>;
- template class EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryInt<Uint16>;
- template class EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryInt<Uint32>;
- template class EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryInt<Uint64>;
- template class EXPORT_TEMPLATE_DEFINE(SHELL_ENCRYPTION_EXPORT) MontgomeryInt<absl::uint128>;
- } // namespace rlwe
|