sample_error.h 3.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
  1. /*
  2. * Copyright 2019 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. #ifndef RLWE_SAMPLE_ERROR_H_
  16. #define RLWE_SAMPLE_ERROR_H_
  17. #include <cstdint>
  18. #include <vector>
  19. #include "absl/strings/str_cat.h"
  20. #include "bits_util.h"
  21. #include "constants.h"
  22. #include "error_params.h"
  23. #include "prng/prng.h"
  24. #include "status_macros.h"
  25. #include "statusor.h"
  26. namespace rlwe {
  27. // Samples a vector of coefficients from the centered binomial distribution
  28. // with the specified variance. The RLWE proofs rely on
  29. // sampling keys and error values from a discrete Gaussian distribution, but
  30. // the NewHope paper [1] indicates that a centered binomial distribution is
  31. // indistinguishable and is far more efficient, without being susceptible to
  32. // timing attacks.
  33. //
  34. // [1] "Post-quantum key exchange -- a new hope", Erdem Alkim, Leo Ducas, Thomas
  35. // Poppelmann, Peter Schwabe, USENIX Security Sumposium.
  36. //
  37. // All values sampled are multiplied by scalar.
  38. template <typename ModularInt>
  39. static rlwe::StatusOr<std::vector<ModularInt>> SampleFromErrorDistribution(
  40. unsigned int num_coeffs, Uint64 variance, SecurePrng* prng,
  41. const typename ModularInt::Params* modulus_params) {
  42. if (variance > kMaxVariance) {
  43. return absl::InvalidArgumentError(absl::StrCat(
  44. "The variance, ", variance, ", must be at most ", kMaxVariance, "."));
  45. }
  46. auto zero = ModularInt::ImportZero(modulus_params);
  47. std::vector<ModularInt> coeffs(num_coeffs, zero);
  48. // Sample from the centered binomial distribution. To do so, we sample k pairs
  49. // of bits (a, b), where k = 2 * variance. The sample of the binomial
  50. // distribution is the sum of the differences between each pair of bits.
  51. Uint64 k;
  52. typename ModularInt::Int coefficient;
  53. for (int i = 0; i < num_coeffs; i++) {
  54. coefficient = modulus_params->modulus;
  55. k = variance << 1;
  56. while (k > 0) {
  57. if (k >= 64) {
  58. // Use 64 bits of randomness
  59. RLWE_ASSIGN_OR_RETURN(auto r64, prng->Rand64());
  60. coefficient += rlwe::internal::CountOnes64(r64);
  61. RLWE_ASSIGN_OR_RETURN(r64, prng->Rand64());
  62. coefficient -= rlwe::internal::CountOnes64(r64);
  63. k -= 64;
  64. } else if (k >= 8) {
  65. // Use 8 bits of randomness
  66. RLWE_ASSIGN_OR_RETURN(auto r8, prng->Rand8());
  67. coefficient += rlwe::internal::CountOnesInByte(r8);
  68. RLWE_ASSIGN_OR_RETURN(r8, prng->Rand8());
  69. coefficient -= rlwe::internal::CountOnesInByte(r8);
  70. k -= 8;
  71. } else {
  72. Uint8 mask = (1 << k) - 1;
  73. RLWE_ASSIGN_OR_RETURN(auto r8, prng->Rand8());
  74. coefficient += rlwe::internal::CountOnesInByte(r8 & mask);
  75. RLWE_ASSIGN_OR_RETURN(r8, prng->Rand8());
  76. coefficient -= rlwe::internal::CountOnesInByte(r8 & mask);
  77. break; // all k remaining pairs have been sampled.
  78. }
  79. }
  80. // coefficient is in the interval [modulus - 2k, modulus + 2k]. We reduce
  81. // it in [0, modulus). Since ModularInt::Int is unsigned, we create a mask
  82. // equal to 0xFF...FF when coefficient >= modulus, and equal to 0 otherwise.
  83. typename ModularInt::Int mask = -(coefficient >= modulus_params->modulus);
  84. coefficient -= mask & modulus_params->modulus;
  85. RLWE_ASSIGN_OR_RETURN(coeffs[i],
  86. ModularInt::ImportInt(coefficient, modulus_params));
  87. }
  88. return coeffs;
  89. }
  90. } // namespace rlwe
  91. #endif // RLWE_SAMPLE_ERROR_H_