error_params.h 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142
  1. /*
  2. * Copyright 2018 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. // The constants in this file represent an expected bound on the size of certain
  16. // NTT polynomials. The size is defined as the l-infinity norm over all
  17. // coefficients, in other words, the size of the largest coefficient. Each bound
  18. // is chosen to be 6 * sqrt(V), where V is the NTT coefficients' variance. Even
  19. // after union-bounding over all N coefficients, this provides a
  20. // high-probability bound for the l-infinity norm of the NTT polynomial.
  21. #ifndef RLWE_ERROR_H_
  22. #define RLWE_ERROR_H_
  23. #include <cmath>
  24. #include "montgomery.h"
  25. #include "ntt_parameters.h"
  26. #include "statusor.h"
  27. namespace rlwe {
  28. // A class that stores the error constants. This class only accurate computes
  29. // error when the plaintext modulus is sufficiently small (less than 64 bits).
  30. template <typename ModularInt>
  31. class ErrorParams {
  32. public:
  33. static rlwe::StatusOr<ErrorParams> Create(
  34. const int log_t, Uint64 variance,
  35. const typename ModularInt::Params* params,
  36. const rlwe::NttParameters<ModularInt>* ntt_params) {
  37. if (log_t > params->log_modulus - 1) {
  38. return absl::InvalidArgumentError(
  39. absl::StrCat("The value log_t, ", log_t,
  40. ", must be smaller than log_modulus - 1, ",
  41. params->log_modulus - 1, "."));
  42. }
  43. if (variance > kMaxVariance) {
  44. return absl::InvalidArgumentError(absl::StrCat(
  45. "The variance, ", variance, ", must be at most ", kMaxVariance, "."));
  46. }
  47. return ErrorParams(log_t, variance, params, ntt_params);
  48. }
  49. // Accessors for constants.
  50. double B_plaintext() const { return b_plaintext_; }
  51. double B_encryption() const { return b_encryption_; }
  52. double B_scale() const { return b_scale_; }
  53. // A polynomial consisting of error terms is added to the ciphertext during
  54. // relinearization. The noise of a ciphertext increases additively by the size
  55. // of the polynomial, which depends on the decomposition modulus of the
  56. // key-switching matrix.
  57. double B_relinearize(int log_decomposition_modulus) const {
  58. // The number of digits needed to represent integers mod modulus in base
  59. // decomposition modulus.
  60. int num_digits = (log_decomposition_modulus + log_modulus_ - 1) /
  61. log_decomposition_modulus;
  62. int decomposition_modulus = 1 << log_decomposition_modulus;
  63. return (8.0 / sqrt(3.0)) * ExportDoubleT() * num_digits * sigma_ *
  64. dimension_ * decomposition_modulus;
  65. }
  66. private:
  67. // Constructor to set up the params.
  68. ErrorParams(const int log_t, Uint64 variance,
  69. const typename ModularInt::Params* params,
  70. const rlwe::NttParameters<ModularInt>* ntt_params)
  71. : t_(params->One()) {
  72. t_ = (params->One() << log_t) + params->One();
  73. dimension_ = ntt_params->number_coeffs;
  74. sigma_ = sqrt(variance);
  75. log_modulus_ = params->log_modulus;
  76. // Set error constants.
  77. b_plaintext_ = B_plaintext(dimension_);
  78. b_encryption_ = B_encryption(dimension_, sigma_);
  79. b_scale_ = B_scale(dimension_);
  80. }
  81. // This represents the "size" of an NTT coefficient of a randomly sampled
  82. // plaintext polynomial. The ciphertext error grows multiplicatively by this
  83. // constant under an absorb. Assume the plaintext polynomial has coefficients
  84. // chosen uniformly at random from the range [0, t), where t is the plaintext
  85. // modulus. Then the variance of a coefficient is V = t ^ 2 / 12. In the NTT
  86. // domain, the variance is (dimension * t ^ 2 / 12).
  87. double B_plaintext(int dimension) {
  88. // Return 6 * sqrt(V) where V is the variance of a coefficient in the NTT
  89. // domain.
  90. return ExportDoubleT() * sqrt(3.0 * dimension);
  91. }
  92. // This represents the "size" of a freshly encrypted ciphertext with a secret
  93. // key and error sampled from a centered binomial distribution with the
  94. // specified variance. The error and message have size |m + et|. Like
  95. // B_plaintext, the variance of a coefficient of m is V = t ^ 2 / 12, and the
  96. // variance of a coefficient of e is sigma ^ 2. In the NTT domain we can bound
  97. // the coefficient's variance by (dimension * (t ^ 2 / 12 + t * sigma)). The
  98. // bound 6 * sqrt(V) is then t * sqrt(dimension) * (sqrt(3.0) + 6.0 * sigma).
  99. double B_encryption(int dimension, double sigma) {
  100. return ExportDoubleT() * sqrt(dimension) * (sqrt(3.0) + 6.0 * sigma);
  101. }
  102. // When modulus switching a ciphertext from a modulus q to a smaller modulus
  103. // p, the polynomial is scaled by (p / q) and a small rounding polynomial is
  104. // added so that the result is the closest integer polynomial with c' = c mod
  105. // t. The rounding polynomial's size contributes additively to the ciphertext
  106. // error, and its size is given by this constant.
  107. double B_scale(int dimension) {
  108. return ExportDoubleT() *
  109. (sqrt(3.0 * dimension) + 8.0 * dimension * sqrt(1 / 3.0));
  110. }
  111. // This returns the least 64 bits of t_. If t_ is much larger than 64 bits,
  112. // this will return inaccurate error estimates.
  113. double ExportDoubleT() const {
  114. return static_cast<double>(ModularInt::ExportUInt64(t_));
  115. }
  116. double b_plaintext_;
  117. double b_encryption_;
  118. double b_scale_;
  119. int log_modulus_;
  120. typename ModularInt::Int t_;
  121. int dimension_;
  122. double sigma_;
  123. };
  124. } // namespace rlwe
  125. #endif // RLWE_ERROR_H_