Normal sampler. More...

Data Structures
struct	cfe_normal

Typedefs
typedef struct cfe_normal	cfe_normal

Functions
void	cfe_normal_init (cfe_normal *s, mpf_t sigma, size_t n)

void	cfe_normal_free (cfe_normal *s)

void	cfe_normal_precomp_exp (cfe_normal *s)

bool	cfe_normal_is_exp_greater (cfe_normal *s, mpf_t y, mpz_t x)

void	cfe_taylor_exp (mpf_t res, mpz_t x, mpf_t alpha, size_t k, size_t n)

bool	cfe_bernoulli (mpz_t t, mpf_t k_square_inv)

void	cfe_mean (mpf_t res, cfe_vec *vec)

void	cfe_variance (mpf_t res, cfe_vec *vec)

Detailed Description

Normal sampler.

Typedef Documentation

◆ cfe_normal

typedef struct cfe_normal cfe_normal

normal samples random values from the Normal (Gaussian) probability distribution, centered on 0.

Function Documentation

◆ cfe_normal_init()

void cfe_normal_init	(	cfe_normal *	s,
		mpf_t	sigma,
		size_t	n
	)

Initializes an instance of cfe_normal sampler. It assumes mean = 0.

◆ cfe_normal_free()

void cfe_normal_free ( cfe_normal * s )

Frees the memory occupied by the struct members. It does not free memory occupied by the struct itself.

◆ cfe_normal_precomp_exp()

void cfe_normal_precomp_exp ( cfe_normal * s )

Precomputes the values of exp(-2^i / 2 * sigma^2) needed for sampling discrete Gauss distribution with standard deviation sigma to arbitrary precision. This is needed since such computations present one of the bottlenecks of the computation. Values are precomputed in the interval 0 <= i < sigma^2 * sqrt(n) since for greater i the results are negligible.

◆ cfe_normal_is_exp_greater()

bool cfe_normal_is_exp_greater	(	cfe_normal *	s,
		mpf_t	y,
		mpz_t	x
	)

Outputs if y > exp(-x/(2*sigma^2)) with minimal calculation of exp(-x/(2*sigma^2)) based on the precomputed values. Sigma is implicit in the precomputed values saved in s.

◆ cfe_taylor_exp()

void cfe_taylor_exp	(	mpf_t	res,
		mpz_t	x,
		mpf_t	alpha,
		size_t	k,
		size_t	n
	)

Approximates exp(-x/alpha) with taylor polynomial of degree k, precise at least up to 2^-n.

◆ cfe_bernoulli()

bool cfe_bernoulli	(	mpz_t	t,
		mpf_t	k_square_inv
	)

cfe_bernoulli returns true with probability proportional to 2^{-t/k^2}. A polynomial approximation is used to evaluate the exponential function. The implementation is based on paper: "FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers" by R. K. Zhao, R. Steinfeld, and A. Sakzad (https://eprint.iacr.org/2018/1234.pdf). See the above paper where it is argued that such a sampling achieves a relative error at most 2^{-45} with the chosen parameters.

Parameters

t	Value t in 2^{-t/k^2} determining the probability
k_square_inv	Value 1/k^2 in 2^{-t/k^2} determining the probability

Returns: Boolean value

◆ cfe_mean()

void cfe_mean	(	mpf_t	res,
		cfe_vec *	vec
	)

Calculates the mean of a vector of integers.

◆ cfe_variance()

void cfe_variance	(	mpf_t	res,
		cfe_vec *	vec
	)

Calculates the variance of a vector of integers.

Data Structures

Typedefs

Functions