Sampling in OpenFHE

OpenFHE library offers various methods for sampling from discrete Gaussian distribution. The methods are implemented in both DiscreteGaussianGenerator and DiscreteGaussianGeneratorGeneric classes, which have their specific uses. All of the samplers discussed have been tested in GLITCH Discrete Gaussian Testing Suite and no problems/abnormalities have been found.

Samplers in DiscreteGaussianGenerator

The class DiscreteGaussianGenerator is the main class for homomorphic encryption and includes the implementations of rejection sampling, Karney’s method and Peikert’s inversion method.

  • Rejection Sampling: Rejection sampling is defined in section 4.1 of the paper Trapdoors for Hard Lattices and New Cryptographic Constructions. It is used in the methods GenerateInteger(double mean, double stddev, size_t n, const IntType &modulus) and GenerateInteger(double mean, double stddev, size_t n). Rejection sampling can be used for any arbitrary center and distribution parameter without any precomputations. However, it has high rejection rate and is vulnerable to timing attacks. It is currently not used by any cryptographic protocols in OpenFHE.

  • Karney’s Method: Karney’s method is defined as Algorithm D in the paper Sampling exactly from the normal distribution, which is an improved sampling method, based on rejection sampling. It is used in the method GenerateIntegerKarney. Like the rejection sampling, it can be used for arbitrary center and distribution parameter without any precomputations. It has a smaller rejection rate than the traditional sampling but it may still be prone to timing attacks.

  • Peikert’s Inversion Method: Peikert’s inversion method discussed in section 4.1 of the paper An Efficient and Parallel Gaussian Sampler for Lattices and summarized in section 3.2.2 of Sampling from discrete Gaussians for lattice-based cryptography on a constrained device. It requires CDF tables of probabilities centered around single center to be kept in memory, which are pre calculated in the constructor. Peikert’s inversion algorithm is used in the methods GenerateInt, GenerateIntVector, GenerateVector and GenerateInteger(const IntType& modulus). These methods are not prone to timing attacks but they are usable for single center, single deviation only. It should be also noted that the memory requirement grows with the distribution parameter, therefore it is advised to use it with smaller deviations.

Since DiscreteGaussianGenerator contains both rejection based & precomputation-based sampling algorithms, a different constructor must be called based on the desired algorithm to be used. If Peikert’s method is desired, then the object must be constructed with a distribution parameter whereas using rejection or Karney’s method does not require such constraint. (Refer to How to Use Sampling Methods section for example code) The std parameter in the constructor is only used by Peikert’s method.

Samplers in DiscreteGaussianGeneratorGeneric

The class DiscreteGaussianGeneratorGeneric is the constant-time generic sampler developed by UCSD, and it contains the definitions for this new sampling method and base samplers required for it.

  • Peikert’s Inversion Method: Peikert’s inversion method is the same one defined in DiscreteGaussianGenerator, and it’s used in base samplers only. It is called from a BaseSampler object created with “PEIKERT” parameter by invoking GenerateInteger method.

  • Knuth-Yao Sampling: Knuth-Yao’s method for sampling integers was summarized in section 5 of Sampling from discrete Gaussians for lattice-based cryptography on a constrained device. It requires the calculation of probability matrix and then the Discrete Distribution Generating trees, which is handled in constructor. In order to use this method, it is required to call it from a BaseSampler object created with “KNUTH_YAO” parameter by invoking GenerateInteger method. Just like Peikert’s inversion method, it is usable for single center, single deviation only while having a memory requirement proportional to distribution parameter.

  • Generic Constant Time Sampling: The new generic sampler developed by UCSD was discussed in the paper Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time. It combines a set of base samplers centered around various means and a single distribution parameter to sample from arbitrary centers and distribution parameters. The parameter selection is discussed in detail in header file, but in general the sampler requires a set of base samplers given as parameters and few precomputations, which are handled in construction phase. This method can be called by creating a DiscreteGaussianGeneratorGeneric object and invoking GenerateInteger method. It is not vulnerable to timing attacks.

How to Use Sampling Methods

Rejection Sampling

1/*Create the generator object, std is not important as we choose it arbitrarily during sampling*/
2DiscreteGaussianGenerator dggRejection;
3/*First parameter is the mean, second one is the distribution parameter and third one is the ring dimension.*/
4int64_t number = dggRejection.GenerateInteger(0,4,1024);

Karney’s Method

1/*Create the generator object, std is not important as we choose it arbitrarily during sampling*/
2DiscreteGaussianGenerator dggKarney;
3/*First parameter is the mean, second one is the distribution parameter*/
4int64_t number = dggKarney.GenerateIntegerKarney(0,4);

Peikert’s Inversion Method (As defined in DiscreteGaussianGenerator)

1/*Create the generator object, the parameter is the distribution parameter*/
2DiscreteGaussianGenerator dggPeikert(4);
3/*This will create a single number*/
4int64_t number = dggPeikert.GenerateInt();

Peikert’s Inversion Method (As defined in DiscreteGaussianGeneratorGeneric)

 1/*Create a bit generator that will feed the random bits*/
 2BitGenerator* bg = new BitGenerator();
 3
 4/*Mean and distribution parameter*/
 5double std= 4;
 6double mean = 0;
 7
 8/*Create the sampler object*/
 9BaseSampler peikert_sampler(mean,std,bg,PEIKERT);
10
11/*Generate Integer */
12int64_t number = peikert_sampler.GenerateInteger();

Knuth-Yao’s Method (As defined in DiscreteGaussianGeneratorGeneric)

 1/*Create a bit generator that will feed the random bits*/
 2BitGenerator* bg = new BitGenerator();
 3
 4/*Mean and distribution parameter*/
 5double std= 4;
 6double mean = 0;
 7
 8/*Create the sampler object*/
 9BaseSampler ky_sampler(mean,std,bg,KNUTH_YAO);
10
11/*Generate Integer */
12int64_t number = ky_sampler.GenerateInteger();

Generic Sampler

 1/*Create a bit generator that will feed the random bits*/
 2BitGenerator* bg = new BitGenerator();
 3
 4/*Distribution parameter of the base samplers, distribution parameter of the actual distribution, number of base samplers, mean of the actual distribution*/
 5double stdBase = 34;
 6double std = (1<<22);
 7int CENTER_COUNT = 1024
 8double mean = 0;
 9
10/*Initialize base samplers*/
11BaseSampler **peikert_samplers;
12for(int i=0;i<CENTER_COUNT;i++){
13    double center = ((double)i/(double)CENTER_COUNT);
14    peikert_samplers[i]=new BaseSampler((double)center,stdBase,bg,PEIKERT);
15}
16
17/*Create the sampler object*/
18int base = std::log2(CENTER_COUNT);
19DiscreteGaussianGeneratorGeneric dggGeneric(peikert_samplers,stdBase,base,SMOOTHING_PARAMETER);
20
21/*Generate Integer */
22int64_t number = dggGeneric.GenerateInteger(mean,std);