bgv.lattice_utils module

Useful functions for polynomials, e.g. for creating lattice based encryption schemes.

class bgv.lattice_utils.Polynomial(coefficients, q, n)

Bases: object

Represents polynomial $c_0 + c_1 x + c_2 x^2 + … + c_d x^d$ in a ring $R_q = mathbb{Z}_q[x]/(x^n + 1)$, where $q$ is a positive integer and $n$ is a power of 2.

__add__(other)

Add a Polynomial or integer scalar to this Polynomial.

Raises:

ValueError – When adding Polynomials that are defined over different rings.

Return type:

Polynomial

Returns:

Polynomial object that results from adding the inputs.

__eq__(other)

Compare this Polynomial with another object to determine (in)equality.

Parameters:

other (object) – Object to compare this Polynomial with.

Raises:

TypeError – If other object is not of the same type as this Polynomial.

Return type:

bool

Returns:

Boolean representation of (in)equality of both objects.

__hash__()

Compute a hash from this Polynomial instance.

Return type:

int

Returns:

Hash value.

__init__(coefficients, q, n)

Construct a new Polynomial $c_0 + c_1 x + c_2 x^2 + … + c_d x^d$, an element of the a ring $R_q = mathbb{Z}_q[x]/(x^n + 1)$. Coefficients are represented in the range $[-lfloor(q-1)/2rfloor, lceil(q-1)/2rceil]$.

Parameters:

• coefficients (list[int]) – Coefficients of the polynomial in order of increasing degree.

• q (int) – Positive integer modulus of the coefficients.

• n (int) – Power of 2, degree of ideal for quotient ring of which the polynomial is an element.

Raises:

ValueError – When list of coefficients is empty, q is smaller than 1 or given n is not a power of 2.

__mul__(other)

Multiply this Polynomial with another Polynomial or integer scalar.

Raises:

ValueError – When multiplying Polynomials that are defined over different rings.

Return type:

Polynomial

Returns:

Polynomial object that results from multiplying the inputs.

__neg__()

Negate Polynomial by negating its coefficients.

Return type:

Polynomial

Returns:

Polynomial object with negated coefficients.

__radd__(other)

Right add this Polynomial with another Polynomial or integer. Because this operation is commutative, we can just left add.

Return type:

Polynomial

Returns:

Polynomial object that results from adding the inputs.

__rmul__(other)

Right multiply this Polynomial with another Polynomial or integer scalar. Because this operation is commutative, we can just left multiply.

Return type:

Polynomial

Returns:

Polynomial object that results from multiplying the inputs.

__rsub__(other)

Subtract this Polynomial from another Polynomial or integer.

Return type:

Polynomial

Returns:

Polynomial object that results from subtracting the inputs.

__str__()

String representaton of Polynomial.

Return type:

str

Returns:

String representation of Polynomial and its ring.

__sub__(other)

Subtract another Polynomial or integer scalar from this Polynomial.

Raises:

ValueError – When subtracting Polynomials that are defined over different rings.

Return type:

Polynomial

Returns:

Polynomial object that results from subtracting the inputs.

deg()

Returns degree of the Polynomial.

Return type:

int

Returns:

Integer degree of Polynomial

static deserialize(obj, **_kwargs)

Deserialization function for Polynomial, which will be passed to the communication module.

Parameters:

• obj (dict[str, Any]) – serialized version of a Polynomial.

• **_kwargs (Any) – Optional extra keyword arguments.

Raises:

SerializationError – When communication library is not installed.

Return type:

Polynomial

Returns:

Deserialized Polynomial from the given dict.

serialize(**_kwargs)

Serialization function for Polynomial, which will be passed to the communication module.

Parameters:

**_kwargs (Any) – optional extra keyword arguments

Raises:

SerializationError – When communication library is not installed.

Return type:

dict[str, Any]

Returns:

serialized version of this Polynomial.

bgv.lattice_utils.gauss_rand_int_rejection_follath(standard_deviation, tailcut, center=0)

Generate a random integer from a discrete Gaussian distribution centered at $c in mathbb{R}$ with the given standard deviation $sigma in mathbb{R}_+}$ by rejection sampling. Note that standard deviation = $s / sqrt{2 pi}$, where $s$ is the Gaussian parameter of the distribution. The default center is at 0. Instead of sampling over $mathbb{Z}$, we sample over the range $[c - tailcut * s rceil, lfloor c + tailcut * s] cap mathbb{Z}$.

Following Algorithm 1 in Follath, J., GAUSSIAN SAMPLING IN LATTICE BASED CRYPTOGRAPHY https://www.sav.sk/journals/uploads/0212094402follat.pdf

Parameters:

• standard_deviation (float) – Standard deviation of the distribution.

• tailcut (float) – Tailcut of distribution.

• center (float) – Center of distribution, default is 0.

Raises:

ValueError – When given standard deviation or tailcut is nonpositive.

Return type:

int

Returns:

Random integer from a discrete Gaussian distribution.

bgv.lattice_utils.gauss_rand_int_rejection_karnay(standard_deviation, center=0)

Generate a random integer from a discrete Gaussian distribution centered at $c in mathbb{R}$ with the given standard deviation $sigma in mathbb{R}_+}$ by rejection sampling. The default center is at 0.

Following Algorithm D in Karnay, J., GAUSSIAN SAMPLING IN LATTICE BASED CRYPTOGRAPHY https://www.sav.sk/journals/uploads/0212094402follat.pdf This algorithm was recommended in the Homomorphic Encryption Standard (2018) by Albrecht et al. https://homomorphicencryption.org/standard/

Parameters:

• standard_deviation (float) – Standard deviation of the distribution.

• center (float) – Center of distribution, default is 0.

Raises:

ValueError – When given standard deviation is nonpositive.

Return type:

int

Returns:

Random integer from a discrete Gaussian distribution.

bgv.lattice_utils.gauss_rand_int_round(standard_deviation, center=0)

Generate a random integer from a discrete Gaussian distribution centered at $c in mathbb{R}$ with the given standard deviation $sigma in mathbb{R}_+}$ by rounding a sample from a continuous Gaussian distribution with the same paramaters. The default center is at 0.

Following the sampling steps in section 1.3 in Brakerski, Z. and Vaikuntanathan, V., Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages https://www.wisdom.weizmann.ac.il/~zvikab/localpapers/IdealHom.pdf

Parameters:

• standard_deviation (float) – Standard deviation of the distribution.

• center (float) – Center of distribution, default is 0.

Return type:

int

Returns:

Random integer from a discrete Gaussian distribution.

bgv.lattice_utils.gauss_rand_polynomial(q, n, standard_deviation, center=0)

Returns random polynomial over $R_q = mathbb{Z}_q[x]/(x^n + 1)$ by sampling coefficients from a discrete Gaussian distribution over $mathbb{Z}_q$ with the given center and standard deviation.

Parameters:

• q (int) – Modulus of the coefficients.

• n (int) – Degree of ideal for quotient ring of which the polynomial is an element.

• standard_deviation (float) – Standard deviation of the distribution.

• center (float) – Center of distribution, default is 0.

Return type:

Polynomial

Returns:

Polynomial object.

bgv.lattice_utils.half_exponential_bernouilli_deviate()

Generates a Bernouilli random value $H$ which is true with probability $1/sqrt{e}$.

Following Algorithm H in Karnay, J., GAUSSIAN SAMPLING IN LATTICE BASED CRYPTOGRAPHY https://www.sav.sk/journals/uploads/0212094402follat.pdf

Return type:

int

Returns:

Bernouilli random value $H$ which is true with probability $1/sqrt{e}$.

bgv.lattice_utils.ternary_rand_polynomial(q, n)

Returns uniformly random polynomial over $R_q = mathbb{Z}_q[x]/(x^n + 1)$ by sampling coefficients from the set ${-1,0,1}$.

Parameters:

• q (int) – Modulus of the coefficients.

• n (int) – Degree of ideal for quotient ring of which the polynomial is an element.

Return type:

Polynomial

Returns:

Polynomial object.

bgv.lattice_utils.unif_rand_polynomial(q, n)

Returns uniformly random polynomial over $R_q = mathbb{Z}_q[x]/(x^n + 1)$ by sampling coefficients uniformly randomly from $mathbb{Z}_q$.

Parameters:

• q (int) – Modulus of the coefficients.

• n (int) – Degree of ideal for quotient ring of which the polynomial is an element.

Return type:

Polynomial

Returns:

Polynomial object.

bgv.lattice_utils.uniform_deviate()

Generates a uniform random value $U$ from the open interval (0,1).

Following Karnay, J., GAUSSIAN SAMPLING IN LATTICE BASED CRYPTOGRAPHY https://www.sav.sk/journals/uploads/0212094402follat.pdf

Return type:

float

Returns:

Uniform random value $U$ from the open interval (0,1).