PALISADE Lattice Crypto Library  1.11.9
A lattice crypto library for software engineers by software engineers.
discretegaussiangeneratorgeneric.h
1 // @file discretegaussiangenerator.h This code provides generation of gaussian
2 // distributions of discrete values. Discrete uniform generator relies on the
3 // built-in C++ generator for 32-bit unsigned integers defined in <random>.
4 // @author TPOC: contact@palisade-crypto.org
5 //
6 // @copyright Copyright (c) 2019, New Jersey Institute of Technology (NJIT)
7 // All rights reserved.
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions are met:
10 // 1. Redistributions of source code must retain the above copyright notice,
11 // this list of conditions and the following disclaimer.
12 // 2. Redistributions in binary form must reproduce the above copyright notice,
13 // this list of conditions and the following disclaimer in the documentation
14 // and/or other materials provided with the distribution. THIS SOFTWARE IS
15 // PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
16 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
17 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
18 // EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
19 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 
26 /*This is the header file for the Generic Sampler used for various Discrete
27  * Gaussian Sampling applications. This class implements the generic sampler by
28  * UCSD discussed in the https://eprint.iacr.org/2017/259.pdf and it is heavily
29  * based on Michael Walter's original code. Along the sides of the
30  * implementation there are also two different "base samplers", which are used
31  * for the generic sampler or can be used on their own depending on the
32  * requirements of needed application.
33  *
34  * The first base sampler uses Peikert's inversion method, discussed in
35  * section 4.1 of https://eprint.iacr.org/2010/088.pdf and summarized in
36  * section 3.2.2 of
37  * https://link.springer.com/content/pdf/10.1007%2Fs00200-014-0218-3.pdf.
38  * Peikert's method requires precomputation of CDF tables around a specific
39  * center and the table must be kept during the sampling process. Hence,
40  * Peikert's method works best if the DESIRED STANDARD DEVIATION IS SMALL and
41  * THE MEAN OF THE DISTRIBUTION IS FIXED, as each new center will require a new
42  * set of precomputations.
43  *
44  * Second base sampler is the Knuth-Yao Sampler discussed in section 5 of
45  * https://link.springer.com/content/pdf/10.1007%2Fs00200-014-0218-3.pdf .
46  * Similar to Peikert's, Knuth-Yao precomputes the PDF's of the numbers based on
47  * standard deviation and the center, which is used during the sampling process.
48  * Therefore like Peikert's method, Knuth-Yao works best method works best if
49  * the DESIRED STANDARD DEVIATION IS SMALL and THE MEAN OF THE DISTRIBUTION IS
50  * FIXED, as each new center will require a new set of precomputations, just
51  * like Peikert's inversion method.
52  *
53  * The "generic sampler" on the other hand, works independent from standard
54  * deviation of the distribution. It combines an array of previously discussed
55  * base samplers centered around 0 to (2^b-1) / 2^b through convolution. The
56  * tables of base samplers however, must be precomputed beforehand; but they do
57  * not need to be recalculated at any time of the sampling process. It is USABLE
58  * FOR ANY STANDARD DEVIATION AND MEAN, just like Karney's method defined in
59  * discretegaussiangenerator.h, needs only one single precomputation and is not
60  * prone to timing attacks unlike Karney. Karney's method, however, is faster
61  * than the generic sampler.
62  *
63  * PARAMETER SELECTION FOR GENERIC SAMPLER
64  *
65  * The selection of parameters change the run time/memory usage/precision of the
66  * generic sampler. The triple trade off between these parameters are defined in
67  * the equation k = (PRECISION - FLIPS) / LOG_BASE. k denotes the level of
68  * precision of the generic sampler. Higher the k is, higher the precision of
69  * the generic sampler but higher the run time. PRECISION denotes the number of
70  * decimal bits in the center of the distribution. Since we are using 'double'
71  * for mean, it is fixed to 53 by definition. FLIPS denote the number of
72  * Bernoulli flips used to approximate the bits used in combination of base
73  * sampler. Higher the number of flips, larger the number of bits approximated
74  * rather than calculated which means smaller run times. Generic sampler
75  * requires a set of base samplers centered around 0/2^b to (2^b-1)/2^b;
76  * LOG_BASE denotes b in this equation. Higher the LOG_BASE is, more base
77  * samplers required which requires additional memory; but at the same time
78  * smaller run times.
79  *
80  * The base samplers used in generic sampler requires varying centers between
81  * 0/2^b and (2^b-1)/(2^b) with the same standard deviation. The standard
82  * deviation required for base samplers must satisfy SIGMA>=4*SQRT(2)*N, where
83  * sigma is the standard deviation of the base sampler and N is the smoothing
84  * parameter
85  *
86  *
87  *
88  * */
89 
90 #ifndef LBCRYPTO_MATH_DISCRETEGAUSSIANGENERATORGENERIC_H_
91 #define LBCRYPTO_MATH_DISCRETEGAUSSIANGENERATORGENERIC_H_
92 
93 #define MAX_LEVELS 4
94 
95 #include <math.h>
96 #include <memory>
97 #include <random>
98 #include <vector>
99 
100 #include "math/backend.h"
101 #include "math/distributiongenerator.h"
102 #include "math/nbtheory.h"
103 
104 namespace lbcrypto {
105 
106 enum BaseSamplerType { KNUTH_YAO = 0, PEIKERT = 1 };
107 
108 class DiscreteGaussianGeneratorGeneric;
109 class BaseSampler;
110 class SamplerCombiner;
111 class BitGenerator;
112 
113 /*
114  * @brief Class implementation to generate random bit. This is created for
115  * centralizing the random bit pools by the samplers.
116  */
118  public:
119  BitGenerator() {}
120  /*
121  * @brief Method for generating a random bit
122  * @return A random bit
123  */
124  short Generate() {
125  if (counter % 31 == 0) {
126  sequence = (PseudoRandomNumberGenerator::GetPRNG())();
127  sequence = sequence << 1;
128  counter = 0;
129  }
130  short bit = (sequence >> (31 - counter)) & 1;
131  counter++;
132  return bit;
133  }
134  ~BitGenerator() {}
135 
136  private:
137  uint32_t sequence = 0;
138  char counter = 0;
139 };
140 /*
141  * @brief Class definiton for base samplers with precomputation that is used for
142  * UCSD generic sampler
143  */
144 class BaseSampler {
145  public:
146  /*
147  * @brief Constructor
148  * @param mean Mean of the distribution
149  * @param std Standard deviation of the distribution
150  * @param generator Pointer to the bit generator that the sampler will use the
151  * random bits from
152  * @param bType Type of the base sampler
153  */
154  BaseSampler(double mean, double std, BitGenerator* generator,
155  BaseSamplerType bType);
156  BaseSampler() {}
157  /*
158  * @brief Method for generating integer from the base sampler
159  * @return A random integer from the distribution
160  */
161  virtual int64_t GenerateInteger();
162  /*
163  * @brief Destroyer for the base sampler
164  */
165  virtual ~BaseSampler() {
166  /*if (DDGColumn != nullptr) {
167  delete[] DDGColumn;
168  }*/
169  }
170  /*
171  * @brief Method for generating a random bit from the bit generator within
172  * @return A random bit
173  */
174  short RandomBit() { return bg->Generate(); }
175 
176  private:
177  // all parameters are set as int because it is assumed that they are used for
178  // generating "small" polynomials only
179  double b_a;
180 
184  int64_t b_mean;
185 
189  float b_std;
190 
194  BitGenerator* bg;
198  BaseSamplerType b_type;
199 
200  int fin;
201 
202  std::vector<std::vector<short>> DDGTree;
203 
204  // short *DDGColumn = nullptr;
205 
210  std::vector<uint32_t> hammingWeights;
214  int32_t b_matrixSize;
215 
219  int32_t firstNonZero;
220 
221  int32_t endIndex;
222 
223  std::vector<double> m_vals;
230  usint FindInVector(const std::vector<double>& S, double search) const;
235  void GenerateDDGTree(const std::vector<uint64_t>& probMatrix);
241  void Initialize(double mean);
242 
250  void GenerateProbMatrix(double stddev, double mean);
255  int64_t GenerateIntegerKnuthYao();
259  int64_t GenerateIntegerPeikert() const;
260 };
261 /*
262  * @brief Class for combining samples from two base samplers, which is used for
263  * UCSD generic sampling
264  */
265 class SamplerCombiner : public BaseSampler {
266  public:
274  SamplerCombiner(BaseSampler* s1, BaseSampler* s2, int64_t z1, int64_t z2)
275  : sampler1(s1), sampler2(s1), x1(z1), x2(z2) {}
280  int64_t GenerateInteger() {
281  return x1 * sampler1->GenerateInteger() + x2 * sampler2->GenerateInteger();
282  }
287 
288  private:
289  // Samplers to be combined
290  BaseSampler *sampler1, *sampler2;
291  // Coefficients that are used for combining
292  int64_t x1, x2;
293 };
294 
299  : public DistributionGenerator<BigVector> {
300  public:
309  DiscreteGaussianGeneratorGeneric(BaseSampler** samplers, const double std,
310  const int b, double N);
311 
319  int64_t GenerateInteger(double mean, double std);
320  int64_t GenerateInteger() { return base_samplers[0]->GenerateInteger(); }
325 
326  private:
331  int64_t flipAndRound(double center);
336  int64_t SampleC(int64_t center);
337 
338  BaseSampler* wide_sampler;
339  BaseSampler** base_samplers;
340  BaseSampler* combiners[MAX_LEVELS];
341  long double wide_variance, sampler_variance;
342  double x, c, ci;
343  int k, log_base;
344  uint64_t mask;
351  short extractBit(int64_t number, int n) { return (number >> n) & 1; }
352 };
353 
354 } // namespace lbcrypto
355 #endif // LBCRYPTO_MATH_DISCRETEGAUSSIANGENERATORGENERIC_H_
Definition: discretegaussiangeneratorgeneric.h:144
Definition: discretegaussiangeneratorgeneric.h:117
Definition: stl_allocator.h:124
~SamplerCombiner()
Destructor.
Definition: discretegaussiangeneratorgeneric.h:286
Abstract class describing generator requirements.
Definition: distributiongenerator.h:188
The class for Generic Discrete Gaussion Distribution generator.
Definition: discretegaussiangeneratorgeneric.h:298
SamplerCombiner(BaseSampler *s1, BaseSampler *s2, int64_t z1, int64_t z2)
Constructor.
Definition: discretegaussiangeneratorgeneric.h:274
Definition: discretegaussiangeneratorgeneric.h:265
int64_t GenerateInteger()
Return the combined value for two samplers with given coefficients.
Definition: discretegaussiangeneratorgeneric.h:280
Definition: binfhecontext.h:36