ring

package
v0.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 31, 2024 License: Apache-2.0, BSD-3-Clause, ISC, + 1 more Imports: 17 Imported by: 0

README

References

  1. Faster arithmetic for number-theoretic transforms (https://arxiv.org/abs/1205.2926)
  2. Speeding up the Number Theoretic Transform for Faster Ideal Lattice-Based Cryptography (https://eprint.iacr.org/2016/504)
  3. Post-quantum key exchange - a new hope (https://eprint.iacr.org/2015/1092)

Documentation

Overview

Package ring implements RNS-accelerated modular arithmetic operations for polynomials, including: RNS basis extension; RNS rescaling; number theoretic transform (NTT); uniform, Gaussian and ternary sampling.

Index

Constants

View Source 
const (
	// GaloisGen is an integer of order N/2 modulo M that spans Z_M with the integer -1.
	// The j-th ring automorphism takes the root zeta to zeta^(5j).
	GaloisGen uint64 = 5

	// MinimumRingDegreeForLoopUnrolledOperations is the minimum ring degree required to
	// safely perform loop-unrolled operations
	MinimumRingDegreeForLoopUnrolledOperations = 8
)
View Source 
const (
	Standard           = Type(0) // Z[X]/(X^N + 1) (Default)
	ConjugateInvariant = Type(1) // Z[X+X^-1]/(X^2N + 1)
)

RingStandard and RingConjugateInvariant are two types of Rings.

View Source 
const (
	// MinimumRingDegreeForLoopUnrolledNTT is the minimum ring degree
	// necessary for memory safe loop unrolling
	MinimumRingDegreeForLoopUnrolledNTT = 16
)

Variables

View Source 
var Pi60 = []uint64{0x1ffffffff6c80001, 0x1ffffffff6140001, 0x1ffffffff5f40001, 0x1ffffffff5700001,
	0x1ffffffff4bc0001, 0x1ffffffff4380001, 0x1ffffffff3240001, 0x1ffffffff2dc0001,
	0x1ffffffff1a40001, 0x1ffffffff11c0001, 0x1ffffffff0fc0001, 0x1ffffffff0d80001,
	0x1ffffffff0c80001, 0x1ffffffff08c0001, 0x1fffffffefd00001, 0x1fffffffef9c0001,
	0x1fffffffef600001, 0x1fffffffeef40001, 0x1fffffffeed40001, 0x1fffffffeed00001,
	0x1fffffffeebc0001, 0x1fffffffed540001, 0x1fffffffed440001, 0x1fffffffed2c0001,
	0x1fffffffed200001, 0x1fffffffec940001, 0x1fffffffec6c0001, 0x1fffffffebe80001,
	0x1fffffffebac0001, 0x1fffffffeba40001, 0x1fffffffeb4c0001, 0x1fffffffeb280001}

Pi60 are the next [32:64] 61-bit close to 2^{62} NTT-friendly primes for N up to 2^{17}

View Source 
var Qi60 = []uint64{0x1fffffffffe00001, 0x1fffffffffc80001, 0x1fffffffffb40001, 0x1fffffffff500001,
	0x1fffffffff380001, 0x1fffffffff000001, 0x1ffffffffef00001, 0x1ffffffffee80001,
	0x1ffffffffeb40001, 0x1ffffffffe780001, 0x1ffffffffe600001, 0x1ffffffffe4c0001,
	0x1ffffffffdf40001, 0x1ffffffffdac0001, 0x1ffffffffda40001, 0x1ffffffffc680001,
	0x1ffffffffc000001, 0x1ffffffffb880001, 0x1ffffffffb7c0001, 0x1ffffffffb300001,
	0x1ffffffffb1c0001, 0x1ffffffffadc0001, 0x1ffffffffa400001, 0x1ffffffffa140001,
	0x1ffffffff9d80001, 0x1ffffffff9140001, 0x1ffffffff8ac0001, 0x1ffffffff8a80001,
	0x1ffffffff81c0001, 0x1ffffffff7800001, 0x1ffffffff7680001, 0x1ffffffff7080001}

Qi60 are the first [0:32] 61-bit close to 2^{62} NTT-friendly primes for N up to 2^{17}

Functions

func AddLazyVec 

func AddLazyVec(p1, p2, p3 []uint64)

AddLazyVec evaluates p3 = p1 + p2. p1, p2, p3 must be of the same size. This funcion is constant time.

func AddScalarLazyThenNegateTwoModulusLazyVec 

func AddScalarLazyThenNegateTwoModulusLazyVec(p1 []uint64, scalar uint64, p2 []uint64, modulus uint64)

AddScalarLazyThenNegateTwoModulusLazyVec evaluates p2 = scalar + 2*modulus - p1. p1, p2, p3 must be of the same size. This function is constant time.

func AddScalarLazyVec 

func AddScalarLazyVec(p1 []uint64, scalar uint64, p2 []uint64)

AddScalarLazyVec evaluates p2 = p1 + scalar. p1, p2, p3 must be of the same size. This function is constant time.

func AddScalarThenMulScalarMontgomeryReduceVec 

func AddScalarThenMulScalarMontgomeryReduceVec(p1 []uint64, scalar0, scalarMont1 uint64, p2 []uint64, modulus, mredconstant uint64)

AddScalarThenMulScalarMontgomeryReduceVec evaluates p3 = (p1+scalar0) * scalarMont1 * 2^{64}^{-1} % modulus (with Montgomery reduction). p2 is ensured to be in the range [0, 2*modulus-1]. p1, p2 must be of the same size.

func AddScalarVec 

func AddScalarVec(p1 []uint64, scalar uint64, p2 []uint64, modulus uint64)

AddScalarVec evaluates p2 = p1 + scalar - modulus if p2 >= modulus. p1, p2 must be of the same size.

func AddThenMulScalarMontgomeryReduce 

func AddThenMulScalarMontgomeryReduce(p1, p2 []uint64, scalarMont uint64, p3 []uint64, modulus, mredconstant uint64)

AddThenMulScalarMontgomeryReduce evaluates p3 = (p1 + p2) * scalar * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func AddVec 

func AddVec(p1, p2, p3 []uint64, modulus uint64)

AddVec evaluates p3 = p1 + p2 - modulus if p3 >= modulus. p1, p2, p3 must be of the same size.

func AutomorphismNTTIndex 

func AutomorphismNTTIndex(N int, NthRoot, GalEl uint64) (index []uint64, err error)

AutomorphismNTTIndex computes the look-up table for the automorphism X^{i} -> X^{i*k mod NthRoot}.

func BRed 

func BRed(x, y, q uint64, breconstant [2]uint64) (r uint64)

BRed computes x*y mod q.

func BRedAdd 

func BRedAdd(a, q uint64, breconstant [2]uint64) (r uint64)

BRedAdd computes a mod q.

func BRedAddLazy 

func BRedAddLazy(x, q uint64, breconstant [2]uint64) uint64

BRedAddLazy computes a mod q in constant time. The result is between 0 and 2*q-1.

func BRedLazy 

func BRedLazy(x, y, q uint64, breconstant [2]uint64) (r uint64)

BRedLazy computes x*y mod q in constant time. The result is between 0 and 2*q-1.

func BarrettReduceLazyVec 

func BarrettReduceLazyVec(p1, p2 []uint64, modulus uint64, bredconstant [2]uint64)

BarrettReduceLazyVec evaluates p2 = p1 % modulus with Barrett reduction. p2 is ensured to be in the range [0, 2*modulus-1]. p1, p2 must be of the same size. This funcion is constant time.

func BarrettReduceVec 

func BarrettReduceVec(p1, p2 []uint64, modulus uint64, bredconstant [2]uint64)

BarrettReduceVec evaluates p2 = p1 % modulus with Barret reduction. p2 is ensured to be in the range [0, modulus-1]. p1, p2 must be of the same size.

func CRed 

func CRed(a, q uint64) uint64

CRed reduce returns a mod q where a is between 0 and 2*q-1.

func CenterModU64Vec 

func CenterModU64Vec(p1 []uint64, w uint64, p2 []uint64)

CenterModU64Vec evaluates p2 = p1 - w if p1 >= (w>>1) % 2^{64} p1, p2 must be of the same size.

func CheckFactors 

func CheckFactors(m uint64, factors []uint64) (err error)

CheckFactors checks that the given list of factors contains all the unique primes of m.

func CheckPrimitiveRoot 

func CheckPrimitiveRoot(g, q uint64, factors []uint64) (err error)

CheckPrimitiveRoot checks that g is a valid primitive root mod q, given the factors of q-1.

func DecomposeSigned 

func DecomposeSigned(i int, p1, carry, p2 []uint64, w, modulus uint64)

DecomposeSigned returns the i-th signed digit base 2^{w} of p1 on p2.

The method will read the carry of the i-1-th iteration and write the carry on the i-th iteration on the operand "carry".

p2 is ensured to be in the range [-2^{w-1}, 2^{w-1}[, with E[p2] = -0.5 and Var[p2] = 2^{w}/12.

p1, carry, p2 must be of the same size.

This function is constant time except for a single condition on i.

func DecomposeSignedBalanced 

func DecomposeSignedBalanced(i int, p1, carry, p2 []uint64, w, modulus uint64)

DecomposeSignedBalanced returns the i-th signed digit base 2^{w} of p1 on p2

The method will read the carry of the i-1-th iteration and write the carry on the i-th iteration on the operand "carry".

p2 is ensured to be in the range [-2^{w-1}, 2^{w-1}], with E[p2] = 0 and Var[p2] = 2^{w}/12.

p1, carry, p2 must be of the same size.

func DecomposeUnsigned 

func DecomposeUnsigned(i int, p1, p2 []uint64, w, modulus uint64)

DecomposeUnsigned returns the i-th unsigned digit base 2^{w} of p1 on p2.

p2 is ensured to be in the range [0, 2^{w}-1[, with E[p2] = 2^{w}-1 and Var[p2] = 2^{w}/12.

p1, carry, p2 must be of the same size.

This function is constant time.

func EvalPolyModP 

func EvalPolyModP(x uint64, poly []uint64, p uint64) (y uint64)

EvalPolyModP evaluates y = sum poly[i] * x^{i} mod p.

func ExtendBasisSmallNorm 

func ExtendBasisSmallNorm(Q uint64, P Poly, pQ, pP RNSPoly)

ExtendBasisSmallNorm extends a small-norm polynomial pQ in R_Q to pP in R_P. User must ensure that len(P) <= pP.Level()+1

func GetBRedConstant 

func GetBRedConstant(q uint64) (breconstant [2]uint64)

GetBRedConstant returns the breconstant for the BRed algorithm. Returns ((2^128)/q)/(2^64) and (2^128)/q mod 2^64.

func GetMRedConstant 

func GetMRedConstant(q uint64) (mredconstant uint64)

GetMRedConstant returns the constant mredconstant = (q^-1) mod 2^64 required for MRed.

func HenselLift 

func HenselLift(psi, m uint64, P uint64, k int) uint64

HenselLift returns (psi + a * P)^{m} = 1 mod P^{k} given psi^{m} = 1 mod P.

func IMForm 

func IMForm(a, q, mredconstant uint64) (r uint64)

IMForm switches a from the Montgomery domain back to the standard domain by computing a*(1/2^64) mod q.

func IMFormLazy 

func IMFormLazy(a, q, mredconstant uint64) (r uint64)

IMFormLazy switches a from the Montgomery domain back to the standard domain by computing a*(1/2^64) mod q in constant time. The result is between 0 and 2*q-1.

func IMFormVec 

func IMFormVec(p1, p2 []uint64, modulus, mredconstant uint64)

IMFormVec evaluates p2 = p1 * (2^{64})^{-1} % modulus (with Montgomery reduction). p2 is ensured to be in the range [0, 2*modulus-1]. p1, p2 must be of the same size.

func INTTConjugateInvariant 

func INTTConjugateInvariant(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTConjugateInvariant evaluates p2 = INTT(p1) in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func INTTConjugateInvariantLazy 

func INTTConjugateInvariantLazy(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTConjugateInvariantLazy evaluates p2 = INTT(p1) in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with p2 in the range [0, 2*modulus-1].

func INTTStandard 

func INTTStandard(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTStandard computes the backward NTT in the given Ring.

func INTTStandardLazy 

func INTTStandardLazy(p1, p2 []uint64, N int, NInv, Q, MRedConstant uint64, roots []uint64)

INTTStandardLazy backward NTT in the given Ring with p2 in [0, 2*modulus-1].

func IsPrime 

func IsPrime(x uint64) bool

IsPrime applies the Baillie-PSW, which is 100% accurate for numbers bellow 2^64.

func MForm 

func MForm(a, q uint64, bredconstant [2]uint64) (r uint64)

MForm switches a to the Montgomery domain by computing a*2^64 mod q.

func MFormLazy 

func MFormLazy(a, q uint64, bredconstant [2]uint64) (r uint64)

MFormLazy switches a to the Montgomery domain by computing a*2^64 mod q in constant time. The result is between 0 and 2*q-1.

func MFormLazyVec 

func MFormLazyVec(p1, p2 []uint64, modulus uint64, bredconstant [2]uint64)

MFormLazyVec evaluates p2 = p1 * 2^{64} % modulus (with Barrett reduction). p2 is ensured to be in the range [0, 2*modulus-1]. p1, p2 must be of the same size. This function is constant time.

func MFormVec 

func MFormVec(p1, p2 []uint64, modulus uint64, bredconstant [2]uint64)

MFormVec evaluates p2 = p1 * 2^{64} % modulus (with Barrett reduction). p2 is ensured to be in the range [0, modulus-1]. p1, p2 must be of the same size.

func MRed 

func MRed(x, y, q, mredconstant uint64) (r uint64)

MRed computes x * y * (1/2^64) mod q.

func MRedLazy 

func MRedLazy(x, y, q, mredconstant uint64) (r uint64)

MRedLazy computes x * y * (1/2^64) mod q in constant time. The result is between 0 and 2*q-1.

func MaskThenAddVec 

func MaskThenAddVec(p1 []uint64, w int, mask uint64, p2 []uint64)

MaskThenAddVec evaluates p2 += (p1>>w) & mask. p1, p2, p3 must be of the same size. This function is constant time.

func MaskVec 

func MaskVec(p1 []uint64, w int, mask uint64, p2 []uint64)

MaskVec evaluates p2 = (p1>>w) & mask. p1, p2, p3 must be of the same size. This function is constant time.

func Min 

func Min(x, y int) int

Min returns the minimum between to int

func ModExp 

func ModExp(x, e, q uint64) (y uint64)

ModExp return y = x^e mod q, x and p are required to be at most 64 bits to avoid an overflow.

func ModExpMontgomery 

func ModExpMontgomery(x, e, q, mrc uint64, bredconstant [2]uint64) (result uint64)

ModExpMontgomery performs the modular exponentiation x^e mod p, where x is in Montgomery form, and returns x^e in Montgomery form.

func ModExpPow2 

func ModExpPow2(x, e, p uint64) (result uint64)

ModExpPow2 performs the modular exponentiation x^e mod p, where p is a power of two, x and p are required to be at most 64 bits to avoid an overflow.

func ModUpExact 

func ModUpExact(rQ, rP RNSRing, p1, p2 RNSPoly, MUC ModUpConstants)

ModUpExact takes p1 mod Q and switches its basis to P, returning the result on p2. Caution: values are not centered and returned values are in [0, 2P-1].

func MulBarrettReduceLazyVec 

func MulBarrettReduceLazyVec(p1, p2, p3 []uint64, modulus uint64, bredconstant [2]uint64)

MulBarrettReduceLazyVec evaluates p3 = p1 * p2 % modulus. p3 is ensured to be in the range [0, 2*modulus-1]. p1, p2, p3 must be of the same size. This funcion is constant time.

func MulBarrettReduceThenAddLazyVec 

func MulBarrettReduceThenAddLazyVec(p1, p2, p3 []uint64, modulus uint64, bredconstant [2]uint64)

MulBarrettReduceThenAddLazyVec evaluates p3 += p1 * p2 % modulus (with Barrett reduction). p3 is ensured to be in the range [0, 2*modulus-1] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size. This funcion is constant time.

func MulBarrettReduceThenAddVec 

func MulBarrettReduceThenAddVec(p1, p2, p3 []uint64, modulus uint64, bredconstant [2]uint64)

MulBarrettReduceThenAddVec evaluates p3 += p1 * p2 % modulus (Barrett reduction) - modulus if p3 >= modulus. p3 is ensured to be in the range [0, modulus-1] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func MulBarrettReduceVec 

func MulBarrettReduceVec(p1, p2, p3 []uint64, modulus uint64, bredconstant [2]uint64)

MulBarrettReduceVec evaluates p3 = p1 * p2 % modulus with Barrett reduction. p3 is ensured to be in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func MulMontgomeryReduceLazyThenAddLazyVec 

func MulMontgomeryReduceLazyThenAddLazyVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceLazyThenAddLazyVec evaluates p3 += p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, 3*modulus-2] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size. This function is constant time.

func MulMontgomeryReduceLazyThenNegLazyVec 

func MulMontgomeryReduceLazyThenNegLazyVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceLazyThenNegLazyVec evaluates p3 = 2*modulus - p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, 2*modulus-1]. p1, p2, p3 must be of the same size. This function is constant time.

func MulMontgomeryReduceLazyThenSubLazyVec 

func MulMontgomeryReduceLazyThenSubLazyVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceLazyThenSubLazyVec evaluates p3 += modulus - p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, 3*modulus-1] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size. This function is constant time.

func MulMontgomeryReduceLazyVec 

func MulMontgomeryReduceLazyVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceLazyVec evaluates p3 = p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, 2*modulus-1]. p1, p2, p3 must be of the same size. This function is constant time.

func MulMontgomeryReduceThenAddLazyVec 

func MulMontgomeryReduceThenAddLazyVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceThenAddLazyVec evaluates p3 += p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, 2*modulus-1] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func MulMontgomeryReduceThenAddVec 

func MulMontgomeryReduceThenAddVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceThenAddVec evaluates p3 += p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction) - modulus if p3 >= modulus. p3 is ensured to be in the range [0, modulus-1] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func MulMontgomeryReduceThenSubLazyVec 

func MulMontgomeryReduceThenSubLazyVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceThenSubLazyVec evaluates p3 += modulus - p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, 2*modulus-1] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func MulMontgomeryReduceThenSubVec 

func MulMontgomeryReduceThenSubVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceThenSubVec evaluates p3 = p3 + modulus - p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction) - modulus if p3 >= modulus. p3 is ensured to be in the range [0, modulus-1] if p3 was already in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func MulMontgomeryReduceVec 

func MulMontgomeryReduceVec(p1, p2, p3 []uint64, modulus, mredconstant uint64)

MulMontgomeryReduceVec evaluates p3 = p1 * p2 * 2^{64}^{-1} % modulus (with Montgomery reduction). p3 is ensured to be in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func MulScalarMontgomeryReduceLazyVec 

func MulScalarMontgomeryReduceLazyVec(p1 []uint64, scalarMont uint64, p2 []uint64, modulus, mredconstant uint64)

MulScalarMontgomeryReduceLazyVec evaluates p2 = p1 * scalarMont (with Montgomery reduction). p2 is ensure to be in the range [0, 2*modulus-1]. p1, p2 must be of the same size. This function is constant time.

func MulScalarMontgomeryReduceThenAddScalarVec 

func MulScalarMontgomeryReduceThenAddScalarVec(p1 []uint64, scalar0, scalarMont1 uint64, p2 []uint64, modulus, mredconstant uint64)

MulScalarMontgomeryReduceThenAddScalarVec evaluates p2 = p1 * scalarMont * 2^{64}^{-1} + scalar0 (with Montgomery reduction) - modulus if p2 >= modulus. p2 is ensure to be in the range [0, modulus-1] if p2 was already in the range [0, modulus-1]. p1, p2 must be of the same size.

func MulScalarMontgomeryReduceThenAddVec 

func MulScalarMontgomeryReduceThenAddVec(p1 []uint64, scalarMont uint64, p2 []uint64, modulus, mredconstant uint64)

MulScalarMontgomeryReduceThenAddVec evaluates p2 += p1 * scalarMont (with Montgomery reduction) - modulus if p2 >= modulus. p2 is ensure to be in the range [0, modulus-1] if p2 was already in the range [0, modulus-1]. p1, p2 must be of the same size.

func MulScalarMontgomeryReduceVec 

func MulScalarMontgomeryReduceVec(p1 []uint64, scalarMont uint64, p2 []uint64, modulus, mredconstant uint64)

MulScalarMontgomeryReduceVec evaluates p2 = p1 * scalarMont (with Montgomery reduction). p2 is ensure to be in the range [0, modulus-1]. p1, p2 must be of the same size.

func MulThenAddLazyVec 

func MulThenAddLazyVec(p1, p2, p3 []uint64)

MulThenAddLazyVec evaluates p3 += p1 * p2. p1, p2, p3 must be of the same size. This funcion is constant time.

func MulVec 

func MulVec(p1, p2, p3 []uint64)

MulVec evaluates p3 = p1 * p2. p1, p2, p3 must be of the same size. This funcion is constant time.

func NTTConjugateInvariant 

func NTTConjugateInvariant(p1, p2 []uint64, N int, Q, MRedConstant uint64, BRedConstant [2]uint64, roots []uint64)

NTTConjugateInvariant evaluates p2 = NTT(p1) in the sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func NTTConjugateInvariantLazy 

func NTTConjugateInvariantLazy(p1, p2 []uint64, N int, Q, MRedConstant uint64, roots []uint64)

NTTConjugateInvariantLazy evaluates p2 = NTT(p1) in the sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with p2 in the range [0, 2*modulus-1].

func NTTStandard 

func NTTStandard(p1, p2 []uint64, N int, Q, MRedConstant uint64, BRedConstant [2]uint64, roots []uint64)

NTTStandard computes the forward NTT in the given Ring.

func NTTStandardLazy 

func NTTStandardLazy(p1, p2 []uint64, N int, Q, MRedConstant uint64, roots []uint64)

NTTStandardLazy computes the forward NTT in the given Ring with p2 in [0, 2*modulus-1].

func NegVec 

func NegVec(p1, p2 []uint64, modulus uint64)

NegVec evaluates p2 = modulus - p1. p1, p2, p3 must be of the same size. This funcion is constant time.

func OneVec 

func OneVec(p1 []uint64)

OneVec evaluates p1 = 1. This function is constant time.

func PolyToBigintCentered 

func PolyToBigintCentered(rQ, rP RNSRing, pQ RNSPoly, pP *RNSPoly, gap int, values []big.Int)

PolyToBigintCentered reconstructs [p]_{QP} and returns the result in an array of Int. Coefficients are centered around QP/2 gap defines coefficients X^{i*gap} that will be reconstructed. For example, if gap = 1, then all coefficients are reconstructed, while if gap = 2 then only coefficients X^{2*i} are reconstructed.

func PrimitiveRoot 

func PrimitiveRoot(q uint64, factors []uint64) (uint64, []uint64, error)

PrimitiveRoot computes the smallest primitive root of the given prime q The unique factors of q-1 can be given to speed up the search for the root.

func RShiftVec 

func RShiftVec(p1 []uint64, w int, p2 []uint64)

RShiftVec evaluates p2 = p1>>w. p1, p2, p3 must be of the same size. This function is constant time.

func ReconstructModP 

func ReconstructModP(p1 RNSPoly, p2 Poly, rQ RNSRing, rP *Ring, MUC ModUpConstants)

ReconstructModP takes p1 mod Q and switches its basis to P, returning the result on p2. Caution: values are not centered and returned values are in [0, 2P-1].

func SubLazyVec 

func SubLazyVec(p1, p2, p3 []uint64, modulus uint64)

SubLazyVec evaluates p3 = p1 + modulus - p2. p1, p2, p3 must be of the same size. This funcion is constant time.

func SubScalarVec 

func SubScalarVec(p1 []uint64, scalar uint64, p2 []uint64, modulus uint64)

SubScalarVec evaluates p2 = p1 + modulus - scalar. p1, p2 must be of the same size.

func SubToModulusThenMulScalarMontgomeryReduceVec 

func SubToModulusThenMulScalarMontgomeryReduceVec(p1, p2 []uint64, scalarMont uint64, p3 []uint64, modulus, mredconstant uint64)

SubToModulusThenMulScalarMontgomeryReduceVec evaluates p3 = (2*modulus - p2 + p1) * scalarMont * (2^{64})^{-1} (with Montgomery reduction). p3 is ensured to be in the range [0, modulus-1]. p1, p2, p3 must be of the same size.

func SubVec 

func SubVec(p1, p2, p3 []uint64, modulus uint64)

SubVec evaluates p3 = p1 + modulus - p2 - modulus if (p1 + modulus - p2) >= modulus. p1, p2, p3 must be of the same size.

func ZeroVec 

func ZeroVec(p1 []uint64)

ZeroVec evaluates p1 = 0. This function is constant time.

Types

type Decomposer 

type Decomposer struct {
	ModUpConstants [][][]ModUpConstants
	// contains filtered or unexported fields
}

Decomposer is a structure that stores the parameters of the arbitrary decomposer. This decomposer takes a p(x)_Q (in basis Q) and returns p(x) mod qi in basis QP, where qi = prod(Q_i) for 0<=i<=L, where L is the number of factors in P.

func NewDecomposer 

func NewDecomposer(rQ, rP RNSRing) (decomposer *Decomposer)

NewDecomposer creates a new Decomposer.

func (*Decomposer) DecomposeAndSplit 

func (decomposer *Decomposer) DecomposeAndSplit(LevelQ, LevelP, BaseRNSDecompositionVectorSize int, p0Q, p1Q, p1P RNSPoly)

DecomposeAndSplit decomposes a polynomial p(x) in basis Q, reduces it modulo qi, and returns the result in basis QP separately.

type Dimensions 

type Dimensions struct {
	Rows, Cols int
}

type DiscreteGaussian 

type DiscreteGaussian struct {
	Sigma float64
	Bound float64
}

DiscreteGaussian represents the parameters of a discrete Gaussian distribution with standard deviation Sigma and bounds [-Bound, Bound].

func (DiscreteGaussian) BinarySize 

func (d DiscreteGaussian) BinarySize() int

func (DiscreteGaussian) Equal 

func (d DiscreteGaussian) Equal(other DistributionParameters) bool

func (DiscreteGaussian) MarshalBinary 

func (d DiscreteGaussian) MarshalBinary() (p []byte, err error)

func (*DiscreteGaussian) ReadFrom 

func (d *DiscreteGaussian) ReadFrom(r io.Reader) (n int64, err error)

func (*DiscreteGaussian) UnmarshalBinary 

func (d *DiscreteGaussian) UnmarshalBinary(p []byte) (err error)

func (DiscreteGaussian) WriteTo 

func (d DiscreteGaussian) WriteTo(w io.Writer) (n int64, err error)

type DistributionParameters 

type DistributionParameters interface {
	Equal(DistributionParameters) bool

	BinarySize() int
	encoding.BinaryMarshaler
	encoding.BinaryUnmarshaler
	io.WriterTo
	io.ReaderFrom
	// contains filtered or unexported methods
}

DistributionParameters is an interface for distribution parameters in the ring. There are three implementation of this interface:

  • DiscreteGaussian for sampling polynomials with discretized gaussian coefficient of given standard deviation and bound.
  • Ternary for sampling polynomials with coefficients in [-1, 1].
  • Uniform for sampling polynomial with uniformly random coefficients in the ring.

func DistributionParametersFromMap 

func DistributionParametersFromMap(distDef map[string]interface{}) (DistributionParameters, error)

func DistributionParametersFromReader 

func DistributionParametersFromReader(r io.Reader) (distribution DistributionParameters, n int64, err error)

type GaussianSampler 

type GaussianSampler struct {
	*sampling.Source
	Xe     DiscreteGaussian
	Moduli []uint64
}

GaussianSampler keeps the state of a truncated Gaussian polynomial sampler.

func NewGaussianSampler 

func NewGaussianSampler(source *sampling.Source, moduli []uint64, Xe DiscreteGaussian) (g *GaussianSampler)

NewGaussianSampler creates a new instance of GaussianSampler from a sampling.Source, a moduli chain and a DiscreteGaussian distribution parameter.

func (GaussianSampler) AtLevel 

func (g GaussianSampler) AtLevel(level int) Sampler

AtLevel returns an instance of the target GaussianSampler that operates at the target level. This instance is not thread safe and cannot be used concurrently to the base instance.

func (GaussianSampler) GetSource 

func (g GaussianSampler) GetSource() *sampling.Source

GetSource returns the underlying sampling.Source used by the sampler.

func (*GaussianSampler) Read 

func (g *GaussianSampler) Read(pol RNSPoly)

Read samples a truncated Gaussian polynomial on "pol" at the maximum level in the default ring, standard deviation and bound.

func (*GaussianSampler) ReadAndAdd 

func (g *GaussianSampler) ReadAndAdd(pol RNSPoly)

ReadAndAdd samples a truncated Gaussian polynomial at the given level for the receiver's default standard deviation and bound and adds it on "pol".

func (*GaussianSampler) ReadNew 

func (g *GaussianSampler) ReadNew(N int) (pol RNSPoly)

ReadNew samples a new truncated Gaussian polynomial at the maximum level in the default ring, standard deviation and bound.

func (GaussianSampler) WithSource 

func (g GaussianSampler) WithSource(source *sampling.Source) Sampler

WithSource returns an instance of the underlying sampler with a new sampling.Source. It can be used concurrently with the original sampler.

type Interpolator 

type Interpolator struct {
	// contains filtered or unexported fields
}

Interpolator is a struct storing the necessary buffer and pre-computation for polynomial interpolation with coefficient in finite fields.

func NewInterpolator 

func NewInterpolator(degree int, T uint64) (itp *Interpolator, err error)

NewInterpolator creates a new Interpolator. Returns an error if T is not prime or not congruent to 1 mod 2N, where N is the next power of two greater than degree+1.

func (*Interpolator) Interpolate 

func (itp *Interpolator) Interpolate(roots []uint64) (coeffs Poly)

Interpolate takes a list of roots the coefficients of P(roots) = 0 mod T.

func (*Interpolator) Lagrange 

func (itp *Interpolator) Lagrange(x, y []uint64) (coeffs []uint64, err error)

Lagrange takes as input (x, y) and returns P(xi) = yi mod T.

type Matrix 

type Matrix struct {
	Q structs.Matrix[RNSPoly]
	P structs.Matrix[RNSPoly]
}

Matrix is a struct storing a matrix of polynomials modulo in basis Q and P.

func NewMatrix 

func NewMatrix(N, LevelQ, LevelP int, dims []int) (m *Matrix)

NewMatrix allocates a new ring.Matrix.

func (*Matrix) Aggregate 

func (m *Matrix) Aggregate(rQ, rP RNSRing, a, b *Matrix) (err error)

Aggregate sets the receiver to a + b. The method returns an error if operands do not match the receiver LevelQ(), LevelP(), Dims().

func (Matrix) BinarySize 

func (m Matrix) BinarySize() (size int)

BinarySize returns the serialized size of the object in bytes.

func (*Matrix) BufferSize 

func (m *Matrix) BufferSize(N, LevelQ, LevelP int, dims []int) (size int)

BufferSize returns the minimum buffer size to instantiate the receiver through [FromBuffer].

func (Matrix) Clone 

func (m Matrix) Clone() *Matrix

Clone returns a deep copy of the receiver.

func (Matrix) ConcatPtoQ 

func (m Matrix) ConcatPtoQ(n int) *Matrix

ConcatPtoQ returns an instance of the receiver where the modulus Q is increased to Q[:] + P[:n] and the modulus P reduced to P[n:]. n must be a positive integer 0 <= n <= m.LevelP()+1. Backing arrays are shared.

func (Matrix) ConcatQtoP 

func (m Matrix) ConcatQtoP(n int) *Matrix

ConcatQtoP returns an instance of the receiver where the modulus Q is reduced to Q[:n] and the modulus P increased to Q[n:] + P[:]. n must be a positive integer 0 <= n < m.LevelQ()+1. Backing arrays are shared.

func (*Matrix) Copy 

func (m *Matrix) Copy(other *Matrix)

Copy copies the input on the receiver.

func (Matrix) Dims 

func (m Matrix) Dims() (dims []int)

Dims returns the dimension of the receiver.

func (Matrix) Equal 

func (m Matrix) Equal(other *Matrix) bool

Equal performs a deep equal between the operand and the receiver.

func (*Matrix) FromBuffer 

func (m *Matrix) FromBuffer(N, LevelQ, LevelP int, dims []int, buf []uint64) *Matrix

FromBuffer assigns new backing array to the receiver. Method panics if len(buf) is too small. Minimum backing array size can be obtained with [BufferSize].

func (Matrix) Level 

func (m Matrix) Level() int

Level returns the level of the modulus Q of the receiver.

func (Matrix) LevelP 

func (m Matrix) LevelP() int

LevelP returns the level of the modulus P of the receiver.

func (Matrix) LevelQ 

func (m Matrix) LevelQ() int

LevelQ returns the level of the modulus Q of the receiver.

func (Matrix) LogN 

func (m Matrix) LogN() int

LogN returns the base 2 logarithm of the receiver ring degree.

func (Matrix) MarshalBinary 

func (m Matrix) MarshalBinary() (p []byte, err error)

MarshalBinary encodes the object into a binary form on a newly allocated slice of bytes.

func (Matrix) N 

func (m Matrix) N() int

N returns the receiver ring degree.

func (Matrix) Randomize 

func (m Matrix) Randomize(rQ, rP RNSRing, source *sampling.Source)

Randomize overwrites the coefficients of the receiver with uniformly random coefficients modulo QP.

func (*Matrix) ReadFrom 

func (m *Matrix) ReadFrom(r io.Reader) (n int64, err error)

ReadFrom reads on the object from an io.Writer. It implements the io.ReaderFrom interface.

Unless r implements the buffer.Reader interface (see see lattigo/utils/buffer/reader.go), it will be wrapped into a bufio.Reader. Since this requires allocation, it is preferable to pass a buffer.Reader directly:

  • When reading multiple values from a io.Reader, it is preferable to first first wrap io.Reader in a pre-allocated bufio.Reader.
  • When reading from a var b []byte, it is preferable to pass a buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

func (*Matrix) UnmarshalBinary 

func (m *Matrix) UnmarshalBinary(p []byte) (err error)

UnmarshalBinary decodes a slice of bytes generated by MarshalBinary or WriteTo on the object.

func (Matrix) WriteTo 

func (m Matrix) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes the object on an io.Writer. It implements the io.WriterTo interface, and will write exactly object.BinarySize() bytes on w.

Unless w implements the buffer.Writer interface (see lattigo/utils/buffer/writer.go), it will be wrapped into a bufio.Writer. Since this requires allocations, it is preferable to pass a buffer.Writer directly:

  • When writing multiple times to a io.Writer, it is preferable to first wrap the io.Writer in a pre-allocated bufio.Writer.
  • When writing to a pre-allocated var b []byte, it is preferable to pass buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

type ModUpConstants 

type ModUpConstants struct {
	// contains filtered or unexported fields
}

ModUpConstants stores the necessary parameters for RNS basis extension.

type NTTFriendlyPrimesGenerator 

type NTTFriendlyPrimesGenerator struct {
	Size                           float64
	NextPrime, PrevPrime, NthRoot  uint64
	CheckNextPrime, CheckPrevPrime bool
}

NTTFriendlyPrimesGenerator is a struct used to generate NTT friendly primes.

func NewNTTFriendlyPrimesGenerator 

func NewNTTFriendlyPrimesGenerator(BitSize, NthRoot uint64) NTTFriendlyPrimesGenerator

NewNTTFriendlyPrimesGenerator instantiates a new NTTFriendlyPrimesGenerator. Primes generated are of the form 2^{BitSize} +/- k * {NthRoot} + 1.

func (*NTTFriendlyPrimesGenerator) NextAlternatingPrime 

func (n *NTTFriendlyPrimesGenerator) NextAlternatingPrime() (uint64, error)

NextAlternatingPrime returns the next prime of the form 2^{BitSize} +/- k * {NthRoot} + 1.

func (*NTTFriendlyPrimesGenerator) NextAlternatingPrimes 

func (n *NTTFriendlyPrimesGenerator) NextAlternatingPrimes(k int) (primes []uint64, err error)

NextAlternatingPrimes returns the next k primes of the form 2^{BitSize} +/- k * {NthRoot} + 1.

func (*NTTFriendlyPrimesGenerator) NextDownstreamPrime 

func (n *NTTFriendlyPrimesGenerator) NextDownstreamPrime() (uint64, error)

NextDownstreamPrime returns the next prime of the form 2^{BitSize} - k * {NthRoot} + 1.

func (*NTTFriendlyPrimesGenerator) NextDownstreamPrimes 

func (n *NTTFriendlyPrimesGenerator) NextDownstreamPrimes(k int) (primes []uint64, err error)

NextDownstreamPrimes returns the next k primes of the form 2^{BitSize} - k * {NthRoot} + 1.

func (*NTTFriendlyPrimesGenerator) NextUpstreamPrime 

func (n *NTTFriendlyPrimesGenerator) NextUpstreamPrime() (uint64, error)

NextUpstreamPrime returns the next prime of the form 2^{BitSize} + k * {NthRoot} + 1.

func (*NTTFriendlyPrimesGenerator) NextUpstreamPrimes 

func (n *NTTFriendlyPrimesGenerator) NextUpstreamPrimes(k int) (primes []uint64, err error)

NextUpstreamPrimes returns the next k primes of the form 2^{BitSize} + k * {NthRoot} + 1.

type NTTTable 

type NTTTable struct {
	NthRoot       uint64   // Nthroot used for the NTT
	PrimitiveRoot uint64   // 2N-th primitive root
	RootsForward  []uint64 //powers of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	RootsBackward []uint64 //powers of the inverse of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	NInv          uint64   //[N^-1] mod Modulus in Montgomery form
}

NTTTable store all the constants that are specifically tied to the NTT.

type NumberTheoreticTransformer 

type NumberTheoreticTransformer interface {
	Forward(p1, p2 []uint64)
	ForwardLazy(p1, p2 []uint64)
	Backward(p1, p2 []uint64)
	BackwardLazy(p1, p2 []uint64)
}

NumberTheoreticTransformer is an interface to provide flexibility on what type of NTT is used by the struct Ring.

func NewNumberTheoreticTransformerConjugateInvariant 

func NewNumberTheoreticTransformerConjugateInvariant(r *Ring, n int) NumberTheoreticTransformer

func NewNumberTheoreticTransformerStandard 

func NewNumberTheoreticTransformerStandard(r *Ring, n int) NumberTheoreticTransformer

type NumberTheoreticTransformerConjugateInvariant 

type NumberTheoreticTransformerConjugateInvariant struct {
	// contains filtered or unexported fields
}

NumberTheoreticTransformerConjugateInvariant computes the NTT in the ring Z[X+X^-1]/(X^2N+1). Z[X+X^-1]/(X^2N+1) is a closed sub-ring of Z[X]/(X^2N+1). Note that the input polynomial only needs to be size N since the right half does not provide any additional information. See "Approximate Homomorphic Encryption over the Conjugate-invariant Ring", https://eprint.iacr.org/2018/952. The implemented approach is more efficient than the one proposed in the referenced work. It avoids the linear map Z[X + X^-1]/(X^2N + 1) <-> Z[X]/(X^N - 1) by instead directly computing the left half of the NTT of Z[X + X^-1]/(X^2N + 1) since the right half provides no additional information, which allows to (re)use nega-cyclic NTT.

func (NumberTheoreticTransformerConjugateInvariant) Backward 

func (rntt NumberTheoreticTransformerConjugateInvariant) Backward(p1, p2 []uint64)

Backward writes the backward NTT in Z[X+X^-1]/(X^2N+1) of p1 on p2.

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazy 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazy(p1, p2 []uint64)

BackwardLazy writes the backward NTT in Z[X+X^-1]/(X^2N+1) of p1 on p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) Forward 

func (rntt NumberTheoreticTransformerConjugateInvariant) Forward(p1, p2 []uint64)

Forward writes the forward NTT in Z[X+X^-1]/(X^2N+1) of p1 on p2.

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazy 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazy(p1, p2 []uint64)

ForwardLazy writes the forward NTT in Z[X+X^-1]/(X^2N+1) of p1 on p2. Returns values in the range [0, 2q-1].

type NumberTheoreticTransformerStandard 

type NumberTheoreticTransformerStandard struct {
	// contains filtered or unexported fields
}

NumberTheoreticTransformerStandard computes the standard nega-cyclic NTT in the ring Z[X]/(X^N+1).

func (NumberTheoreticTransformerStandard) Backward 

func (rntt NumberTheoreticTransformerStandard) Backward(p1, p2 []uint64)

Backward writes the backward NTT in Z[X]/(X^N+1) of p1 on p2.

func (NumberTheoreticTransformerStandard) BackwardLazy 

func (rntt NumberTheoreticTransformerStandard) BackwardLazy(p1, p2 []uint64)

BackwardLazy writes the backward NTT in Z[X]/(X^N+1) p1 on p2. Returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) Forward 

func (rntt NumberTheoreticTransformerStandard) Forward(p1, p2 []uint64)

Forward writes the forward NTT in Z[X]/(X^N+1) of p1 on p2.

func (NumberTheoreticTransformerStandard) ForwardLazy 

func (rntt NumberTheoreticTransformerStandard) ForwardLazy(p1, p2 []uint64)

ForwardLazy writes the forward NTT in Z[X]/(X^N+1) of p1 on p2. Returns values in the range [0, 2q-1].

type Parameters 

type Parameters struct {
	// contains filtered or unexported fields
}

Parameters is a struct storing test parameters for the package Ring.

type Point 

type Point struct {
	Q RNSPoly
	P RNSPoly
}

Point is a struct storing a polynomial in basis Q and P.

func NewPoint 

func NewPoint(N, LevelQ, LevelP int) (p *Point)

NewPoint allocates a new Point.

func NewPointAtLevelFromPoly 

func NewPointAtLevelFromPoly(LevelQ, LevelP int, pQ, pP RNSPoly) (*Point, error)

func (*Point) Aggregate 

func (p *Point) Aggregate(rQ, rP RNSRing, a, b *Point) (err error)

Aggregate sets the receiver to a + b. The method returns an error if operands do not match the receiver LevelQ(), LevelP().

func (*Point) AsVector 

func (p *Point) AsVector() *Vector

AsVector wraps the receiver in an Vector.

func (Point) BinarySize 

func (p Point) BinarySize() (size int)

BinarySize returns the serialized size of the object in bytes.

func (*Point) BufferSize 

func (p *Point) BufferSize(N, LevelQ, LevelP int) int

BufferSize returns the minimum buffer size to instantiate the receiver through [FromBuffer].

func (Point) Clone 

func (p Point) Clone() (clone *Point)

Clone returns a deep copy of the receiver.

func (Point) ConcatPtoQ 

func (p Point) ConcatPtoQ(n int) *Point

ConcatPtoQ returns an instance of the receiver where the modulus Q is increased to Q[:] + P[:n] and the modulus P reduced to P[n:]. n must be a positive integer 0 <= n <= p.LevelP()+1. Backing arrays are shared.

func (Point) ConcatQtoP 

func (p Point) ConcatQtoP(n int) *Point

ConcatQtoP returns an instance of the receiver where the modulus Q is reduced to Q[:n] and the modulus P increased to Q[n:] + P[:]. n must be a positive integer 0 < n < p.LevelQ()+1. Backing arrays are shared.

func (Point) Equal 

func (p Point) Equal(other *Point) (equal bool)

Equal performs a deep equal.

func (*Point) FromBuffer 

func (p *Point) FromBuffer(N, LevelQ, LevelP int, buf []uint64) *Point

FromBuffer assigns new backing array to the receiver. Method panics if len(buf) is too small. Minimum backing array size can be obtained with [BufferSize].

func (Point) Level 

func (p Point) Level() int

Level returns the level of the modulus Q of the receiver.

func (Point) LevelP 

func (p Point) LevelP() int

LevelP returns the level of the modulus P of the receiver.

func (Point) LevelQ 

func (p Point) LevelQ() int

LevelQ returns the level of the modulus Q of the receiver.

func (Point) LogN 

func (p Point) LogN() int

LogN returns base two logarithm of the ring degree of the receiver.

func (Point) MarshalBinary 

func (p Point) MarshalBinary() (data []byte, err error)

MarshalBinary encodes the object into a binary form on a newly allocated slice of bytes.

func (Point) N 

func (p Point) N() int

N returns the ring degree of the receiver.

func (Point) Randomize 

func (p Point) Randomize(rQ, rP RNSRing, source *sampling.Source)

Randomize overwrites the coefficients of the receiver with uniformly random coefficients modulo QP.

func (*Point) ReadFrom 

func (p *Point) ReadFrom(r io.Reader) (n int64, err error)

ReadFrom reads on the object from an io.Writer. It implements the io.ReaderFrom interface.

Unless r implements the buffer.Reader interface (see see lattigo/utils/buffer/reader.go), it will be wrapped into a bufio.Reader. Since this requires allocation, it is preferable to pass a buffer.Reader directly:

  • When reading multiple values from a io.Reader, it is preferable to first first wrap io.Reader in a pre-allocated bufio.Reader.
  • When reading from a var b []byte, it is preferable to pass a buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

func (*Point) ResizeP 

func (p *Point) ResizeP(LevelP int)

ResizeP resizes the field Q of the receiver.

func (*Point) ResizeQ 

func (p *Point) ResizeQ(LevelQ int)

ResizeQ resizes the field Q of the receiver.

func (*Point) UnmarshalBinary 

func (p *Point) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary decodes a slice of bytes generated by MarshalBinary or WriteTo on the object.

func (Point) WriteTo 

func (p Point) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes the object on an io.Writer. It implements the io.WriterTo interface, and will write exactly object.BinarySize() bytes on w.

Unless w implements the buffer.Writer interface (see lattigo/utils/buffer/writer.go), it will be wrapped into a bufio.Writer. Since this requires allocations, it is preferable to pass a buffer.Writer directly:

  • When writing multiple times to a io.Writer, it is preferable to first wrap the io.Writer in a pre-allocated bufio.Writer.
  • When writing to a pre-allocated var b []byte, it is preferable to pass buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

type Poly 

type Poly []uint64

Poly is a structure storing the coefficients of a polynomial.

func NewPoly 

func NewPoly(N int) (p Poly)

NewPoly allocates a new Poly of N coefficients.

func (Poly) BinarySize 

func (p Poly) BinarySize() (size int)

BinarySize returns the serialized size of the object in bytes.

func (Poly) BufferSize 

func (p Poly) BufferSize(N int) int

BufferSize returns the minimum buffer size to instantiate the receiver through [FromBuffer].

func (Poly) Clone 

func (p Poly) Clone() *Poly

Clone returns a deep copy of the receiver.

func (*Poly) Copy 

func (p *Poly) Copy(other *Poly)

Copy copies the coefficients of on the receiver.

func (Poly) Equal 

func (p Poly) Equal(other *Poly) bool

Equal performs a deep equal.

func (*Poly) FromBuffer 

func (p *Poly) FromBuffer(N int, buf []uint64)

FromBuffer assigns new backing array to the receiver.

func (Poly) MarshalBinary 

func (p Poly) MarshalBinary() (data []byte, err error)

MarshalBinary encodes the object into a binary form on a newly allocated slice of bytes.

func (Poly) N 

func (p Poly) N() int

N returns the number of coefficients of the Poly.

func (*Poly) ReadFrom 

func (p *Poly) ReadFrom(r io.Reader) (n int64, err error)

ReadFrom reads on the object from an io.Writer. It implements the io.ReaderFrom interface.

Unless r implements the buffer.Reader interface (see see lattigo/utils/buffer/reader.go), it will be wrapped into a bufio.Reader. Since this requires allocation, it is preferable to pass a buffer.Reader directly:

  • When reading multiple values from a io.Reader, it is preferable to first first wrap io.Reader in a pre-allocated bufio.Reader.
  • When reading from a var b []byte, it is preferable to pass a buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

func (*Poly) UnmarshalBinary 

func (p *Poly) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary decodes a slice of bytes generated by MarshalBinary or WriteTo on the object.

func (Poly) WriteTo 

func (p Poly) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes the object on an io.Writer. It implements the io.WriterTo interface, and will write exactly object.BinarySize() bytes on w.

Unless w implements the buffer.Writer interface (see lattigo/utils/buffer/writer.go), it will be wrapped into a bufio.Writer. Since this requires allocations, it is preferable to pass a buffer.Writer directly:

  • When writing multiple times to a io.Writer, it is preferable to first wrap the io.Writer in a pre-allocated bufio.Writer.
  • When writing to a pre-allocated var b []byte, it is preferable to pass buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

type RNSPoly 

type RNSPoly []Poly

RNSPoly is the structure that contains the coefficients of an RNS polynomial. Coefficients are stored as a matrix backed by an 1D array.

func NewRNSPoly 

func NewRNSPoly(N, Level int) (p RNSPoly)

NewRNSPoly creates a new polynomial with N coefficients set to zero and Level+1 moduli.

func (RNSPoly) At 

func (p RNSPoly) At(i int) Poly

At returns the i-th row of the receiver.

func (RNSPoly) BinarySize 

func (p RNSPoly) BinarySize() (size int)

BinarySize returns the serialized size of the object in bytes.

func (*RNSPoly) BufferSize 

func (p *RNSPoly) BufferSize(N, Level int) int

BufferSize returns the minimum buffer size to instantiate the receiver through [FromBuffer].

func (RNSPoly) Clone 

func (p RNSPoly) Clone() *RNSPoly

func (*RNSPoly) Copy 

func (p *RNSPoly) Copy(p1 *RNSPoly)

Copy copies the coefficients of p1 on the target polynomial. This method does nothing if the underlying arrays are the same. This method will resize the target polynomial to the level of the input polynomial.

func (*RNSPoly) CopyLvl 

func (p *RNSPoly) CopyLvl(level int, p1 *RNSPoly)

CopyLvl copies the coefficients of p1 on the target polynomial. This method does nothing if the underlying arrays are the same. Expects the degree of both polynomials to be identical.

func (RNSPoly) Equal 

func (p RNSPoly) Equal(other *RNSPoly) bool

func (*RNSPoly) FromBuffer 

func (p *RNSPoly) FromBuffer(N, Level int, buf []uint64)

FromBuffer assigns new backing array to the receiver.

func (RNSPoly) Level 

func (p RNSPoly) Level() int

Level returns the current number of moduli minus 1.

func (RNSPoly) LogN 

func (p RNSPoly) LogN() int

LogN returns the base two logarithm of the number of coefficients of the polynomial.

func (RNSPoly) MarshalBinary 

func (p RNSPoly) MarshalBinary() (data []byte, err error)

MarshalBinary encodes the object into a binary form on a newly allocated slice of bytes.

func (RNSPoly) N 

func (p RNSPoly) N() int

N returns the number of coefficients of the polynomial, which equals the degree of the Ring cyclotomic polynomial.

func (RNSPoly) Ones 

func (p RNSPoly) Ones()

Ones sets all coefficients of the target polynomial to 1.

func (*RNSPoly) ReadFrom 

func (p *RNSPoly) ReadFrom(r io.Reader) (n int64, err error)

ReadFrom reads on the object from an io.Writer. It implements the io.ReaderFrom interface.

Unless r implements the buffer.Reader interface (see see lattigo/utils/buffer/reader.go), it will be wrapped into a bufio.Reader. Since this requires allocation, it is preferable to pass a buffer.Reader directly:

  • When reading multiple values from a io.Reader, it is preferable to first first wrap io.Reader in a pre-allocated bufio.Reader.
  • When reading from a var b []byte, it is preferable to pass a buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

func (*RNSPoly) Resize 

func (p *RNSPoly) Resize(level int)

Resize resizes the level of the target polynomial to the provided level. If the provided level is larger than the current level, then allocates zero coefficients, otherwise dereferences the coefficients above the provided level.

func (*RNSPoly) UnmarshalBinary 

func (p *RNSPoly) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary decodes a slice of bytes generated by MarshalBinary or WriteTo on the object.

func (RNSPoly) WriteTo 

func (p RNSPoly) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes the object on an io.Writer. It implements the io.WriterTo interface, and will write exactly object.BinarySize() bytes on w.

Unless w implements the buffer.Writer interface (see lattigo/utils/buffer/writer.go), it will be wrapped into a bufio.Writer. Since this requires allocations, it is preferable to pass a buffer.Writer directly:

  • When writing multiple times to a io.Writer, it is preferable to first wrap the io.Writer in a pre-allocated bufio.Writer.
  • When writing to a pre-allocated var b []byte, it is preferable to pass buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

func (RNSPoly) Zero 

func (p RNSPoly) Zero()

Zero sets all coefficients of the target polynomial to 0.

type RNSRing 

type RNSRing []*Ring

RNSRing is a struct regrouping a set o

func NewRNSRing 

func NewRNSRing(N int, Moduli []uint64) (r RNSRing, err error)

NewRNSRing creates a new RNSRing with degree N and coefficient moduli Moduli with Standard NTT. N must be a power of two larger than 8. Moduli should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo 2*N. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func NewRNSRingConjugateInvariant 

func NewRNSRingConjugateInvariant(N int, Moduli []uint64) (r RNSRing, err error)

NewRNSRingConjugateInvariant creates a new RNS Ring with degree N and coefficient moduli Moduli with Conjugate Invariant NTT. N must be a power of two larger than 8. Moduli should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo 4*N. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func NewRNSRingFromRings 

func NewRNSRingFromRings(rings []*Ring) (r RNSRing, err error)

NewRNSRingFromRings returns a new Ring instantiated with the provided Rings. All Rings must have the same ring degree.

func NewRNSRingFromType 

func NewRNSRingFromType(N int, Moduli []uint64, ringType Type) (r RNSRing, err error)

NewRNSRingFromType creates a new RNS Ring with degree N and coefficient moduli Moduli for which the type of NTT is determined by the ringType argument. If ringType==Standard, the ring is instantiated with standard NTT with the Nth root of unity 2*N. If ringType==ConjugateInvariant, the ring is instantiated with a ConjugateInvariant NTT with Nth root of unity 4*N. N must be a power of two larger than 8. Moduli should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo the root of unity. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func NewRNSRingWithCustomNTT 

func NewRNSRingWithCustomNTT(N int, ModuliChain []uint64, ntt func(*Ring, int) NumberTheoreticTransformer, NthRoot int) (r RNSRing, err error)

NewRNSRingWithCustomNTT creates a new RNS Ring with degree N and coefficient moduli Moduli with user-defined NTT transform and primitive Nth root of unity. ModuliChain should be a non-empty []uint64 with distinct prime elements. All moduli must also be equal to 1 modulo the root of unity. N must be a power of two larger than 8. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func (RNSRing) Add 

func (r RNSRing) Add(p1, p2, p3 RNSPoly)

Add evaluates p3 = p1 + p2 coefficient-wise in the ring.

func (RNSRing) AddDoubleRNSScalar 

func (r RNSRing) AddDoubleRNSScalar(p1 RNSPoly, scalar0, scalar1 RNSScalar, p2 RNSPoly)

AddDoubleRNSScalar evaluates p2 = p1[:N/2] + scalar0 || p1[N/2] + scalar1 coefficient-wise in the ring, with the scalar values expressed in the CRT decomposition at a given level.

func (RNSRing) AddLazy 

func (r RNSRing) AddLazy(p1, p2, p3 RNSPoly)

AddLazy evaluates p3 = p1 + p2 coefficient-wise in the ring, with p3 in [0, 2*modulus-1].

func (RNSRing) AddModuli 

func (r RNSRing) AddModuli(moduli []uint64) (rNew RNSRing, err error)

AddModuli returns an instance of the receiver with an additional modulus.

func (RNSRing) AddScalar 

func (r RNSRing) AddScalar(p1 RNSPoly, scalar uint64, p2 RNSPoly)

AddScalar evaluates p2 = p1 + scalar coefficient-wise in the ring.

func (RNSRing) AddScalarBigint 

func (r RNSRing) AddScalarBigint(p1 RNSPoly, scalar *big.Int, p2 RNSPoly)

AddScalarBigint evaluates p2 = p1 + scalar coefficient-wise in the ring.

func (RNSRing) AtLevel 

func (r RNSRing) AtLevel(level int) RNSRing

AtLevel returns an instance of the target ring that operates at the target level. This instance is thread safe and can be use concurrently with the base ring.

func (RNSRing) Automorphism 

func (r RNSRing) Automorphism(polIn RNSPoly, gen uint64, polOut RNSPoly)

Automorphism applies the automorphism X^{i} -> X^{i*gen} on a polynomial outside of the NTT domain. It must be noted that the result cannot be in-place.

func (RNSRing) AutomorphismNTT 

func (r RNSRing) AutomorphismNTT(polIn RNSPoly, gen uint64, polOut RNSPoly)

AutomorphismNTT applies the automorphism X^{i} -> X^{i*gen} on a polynomial in the NTT domain. It must be noted that the result cannot be in-place.

func (RNSRing) AutomorphismNTTWithIndex 

func (r RNSRing) AutomorphismNTTWithIndex(polIn RNSPoly, index []uint64, polOut RNSPoly)

AutomorphismNTTWithIndex applies the automorphism X^{i} -> X^{i*gen} on a polynomial in the NTT domain. `index` is the lookup table storing the mapping of the automorphism. It must be noted that the result cannot be in-place.

func (RNSRing) AutomorphismNTTWithIndexThenAddLazy 

func (r RNSRing) AutomorphismNTTWithIndexThenAddLazy(polIn RNSPoly, index []uint64, polOut RNSPoly)

AutomorphismNTTWithIndexThenAddLazy applies the automorphism X^{i} -> X^{i*gen} on a polynomial in the NTT domain . `index` is the lookup table storing the mapping of the automorphism. The result of the automorphism is added on polOut.

func (RNSRing) BRedConstants 

func (r RNSRing) BRedConstants() (BRC [][2]uint64)

BRedConstants returns the concatenation of the Barrett constants of the target ring.

func (RNSRing) Concat 

func (r RNSRing) Concat(other RNSRing) (rnew RNSRing)

Concat concatenates other to the receiver producing a new extended RNSRing.

func (RNSRing) ConjugateInvariant 

func (r RNSRing) ConjugateInvariant() (cr RNSRing, err error)

ConjugateInvariant returns the conjugate invariant ring of the receiver RNSRing. If `r.Type()==ConjugateInvariant`, then the method returns the receiver. if `r.Type()==Standard`, then the method returns a ring with ring degree N/2. The returned Ring is a shallow copy of the receiver.

func (RNSRing) DivFloorByLastModulus 

func (r RNSRing) DivFloorByLastModulus(p0, p1 RNSPoly)

DivFloorByLastModulus divides (floored) the polynomial by its last modulus. Output poly level must be equal or one less than input level.

func (RNSRing) DivFloorByLastModulusMany 

func (r RNSRing) DivFloorByLastModulusMany(nbRescales int, p0, buff, p1 RNSPoly)

DivFloorByLastModulusMany divides (floored) sequentially nbRescales times the polynomial by its last modulus. Output poly level must be equal or nbRescales less than input level.

func (RNSRing) DivFloorByLastModulusManyNTT 

func (r RNSRing) DivFloorByLastModulusManyNTT(nbRescales int, p0, buff, p1 RNSPoly)

DivFloorByLastModulusManyNTT divides (floored) sequentially nbRescales times the polynomial by its last modulus. Input must be in the NTT domain. Output poly level must be equal or nbRescales less than input level.

func (RNSRing) DivFloorByLastModulusNTT 

func (r RNSRing) DivFloorByLastModulusNTT(p0, buff, p1 RNSPoly)

DivFloorByLastModulusNTT divides (floored) the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or one less than input level.

func (RNSRing) DivRoundByLastModulus 

func (r RNSRing) DivRoundByLastModulus(p0, p1 RNSPoly)

DivRoundByLastModulus divides (rounded) the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or one less than input level.

func (RNSRing) DivRoundByLastModulusMany 

func (r RNSRing) DivRoundByLastModulusMany(nbRescales int, p0, buff, p1 RNSPoly)

DivRoundByLastModulusMany divides (rounded) sequentially nbRescales times the polynomial by its last modulus. Output poly level must be equal or nbRescales less than input level.

func (RNSRing) DivRoundByLastModulusManyNTT 

func (r RNSRing) DivRoundByLastModulusManyNTT(nbRescales int, p0, buff, p1 RNSPoly)

DivRoundByLastModulusManyNTT divides (rounded) sequentially nbRescales times the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or nbRescales less than input level.

func (RNSRing) DivRoundByLastModulusNTT 

func (r RNSRing) DivRoundByLastModulusNTT(p0, buff, p1 RNSPoly)

DivRoundByLastModulusNTT divides (rounded) the polynomial by its last modulus. The input must be in the NTT domain. Output poly level must be equal or one less than input level.

func (RNSRing) Equal 

func (r RNSRing) Equal(p1, p2 RNSPoly) bool

Equal checks if p1 = p2 in the given Ring.

func (RNSRing) EvalPolyScalar 

func (r RNSRing) EvalPolyScalar(p1 []RNSPoly, scalar uint64, p2 RNSPoly)

EvalPolyScalar evaluate p2 = p1(scalar) coefficient-wise in the ring.

func (RNSRing) FoldStandardToConjugateInvariant 

func (r RNSRing) FoldStandardToConjugateInvariant(polyStandard RNSPoly, permuteNTTIndexInv []uint64, polyConjugateInvariant RNSPoly)

FoldStandardToConjugateInvariant folds [X]/(X^N+1) to [X+X^-1]/(X^N+1) in compressed form (N/2 coefficients). Requires degree(polyConjugateInvariant) = 2*degree(polyStandard). Requires that polyStandard and polyConjugateInvariant share the same moduli.

func (RNSRing) GenNTTTables 

func (r RNSRing) GenNTTTables(primitiveRoots []uint64, factors [][]uint64) (err error)

GenNTTTables checks that N has been correctly initialized, and checks that each modulus is a prime congruent to 1 mod 2N (i.e. NTT-friendly). Then, it computes the variables required for the NTT. The purpose of ValidateParameters is to validate that the moduli allow the NTT, and to compute the NTT parameters.

func (RNSRing) IMForm 

func (r RNSRing) IMForm(p1, p2 RNSPoly)

IMForm evaluates p2 = p1 * 2^64 coefficient-wise in the ring.

func (RNSRing) INTT 

func (r RNSRing) INTT(p1, p2 RNSPoly)

INTT evaluates p2 = INTT(p1).

func (RNSRing) INTTLazy 

func (r RNSRing) INTTLazy(p1, p2 RNSPoly)

INTTLazy evaluates p2 = INTT(p1) with p2 in [0, 2*modulus-1].

func (RNSRing) Inverse 

func (r RNSRing) Inverse(a RNSScalar)

Inverse computes the modular inverse of a scalar a expressed in a CRT decomposition. The inversion is done in-place and assumes that a is in Montgomery form.

func (RNSRing) Level 

func (r RNSRing) Level() int

Level returns the level of the current ring.

func (RNSRing) LogModuli 

func (r RNSRing) LogModuli() (logmod float64)

LogModuli returns the size of the extended modulus P in bits

func (RNSRing) LogN 

func (r RNSRing) LogN() int

LogN returns log2(ring degree).

func (RNSRing) MForm 

func (r RNSRing) MForm(p1, p2 RNSPoly)

MForm evaluates p2 = p1 * (2^64)^-1 coefficient-wise in the ring.

func (RNSRing) MFormLazy 

func (r RNSRing) MFormLazy(p1, p2 RNSPoly)

MFormLazy evaluates p2 = p1 * (2^64)^-1 coefficient-wise in the ring with p2 in [0, 2*modulus-1].

func (RNSRing) MFormRNSScalar 

func (r RNSRing) MFormRNSScalar(s1, s2 RNSScalar)

MFormRNSScalar switches an RNS scalar to the Montgomery domain. s2 = s1<<64 mod Q

func (RNSRing) MRedConstants 

func (r RNSRing) MRedConstants() (MRC []uint64)

MRedConstants returns the concatenation of the Montgomery constants of the target ring.

func (RNSRing) MarshalBinary 

func (r RNSRing) MarshalBinary() (data []byte, err error)

MarshalBinary encodes the object into a binary form on a newly allocated slice of bytes.

func (RNSRing) MarshalJSON 

func (r RNSRing) MarshalJSON() (data []byte, err error)

MarshalJSON encodes the object into a binary form on a newly allocated slice of bytes with the json codec.

func (RNSRing) MaxLevel 

func (r RNSRing) MaxLevel() int

MaxLevel returns the maximum level allowed by the ring (#NbModuli -1).

func (RNSRing) ModDown 

func (r RNSRing) ModDown(other RNSRing, p1Q, p1P, buffQ, buffP, p2Q RNSPoly)

ModDown takes p1QP = [p1Q, p1P] an RNSPoly of the RNSRing r and other and stores on p2Q its value divided by the moduli of the RNSRing other. Division is centered and rounded.

func (RNSRing) ModDownConstants 

func (r RNSRing) ModDownConstants(other RNSRing) (constants []uint64)

func (RNSRing) ModDownNTT 

func (r RNSRing) ModDownNTT(other RNSRing, p1Q, p1P, buffQ, buffP, p2Q RNSPoly)

ModDownNTT takes p1QP = [p1Q, p1P] an RNSPoly of the RNSRing r and other and stores on p2Q its value divided by the moduli of the RNSRing other. Inputs are expected to be in the NTT domain, and output is given in the NTT domain. Division is centered and rounded.

func (RNSRing) ModUp 

func (r RNSRing) ModUp(other RNSRing, pQ, buffQ, pP RNSPoly)

ModUp takes pQ an RNSPoly of the RNSRing r and stores on pP its representation in the RNSRing other.

func (RNSRing) ModUpConstants 

func (r RNSRing) ModUpConstants(other RNSRing) ModUpConstants

ModUpConstants generates the ModUpConstants for basis extension from the receiver ring to the other ring.

func (RNSRing) ModuliChain 

func (r RNSRing) ModuliChain() (moduli []uint64)

ModuliChain returns the list of primes in the modulus chain.

func (RNSRing) ModuliChainLength 

func (r RNSRing) ModuliChainLength() int

ModuliChainLength returns the number of primes in the RNS basis of the ring.

func (RNSRing) Modulus 

func (r RNSRing) Modulus() (modulus *big.Int)

Modulus returns the full modulus. The internal level of the ring is taken into account.

func (RNSRing) MulByVectorMontgomery 

func (r RNSRing) MulByVectorMontgomery(p1 RNSPoly, vector []uint64, p2 RNSPoly)

MulByVectorMontgomery evaluates p2 = p1 * vector coefficient-wise in the ring.

func (RNSRing) MulByVectorMontgomeryThenAddLazy 

func (r RNSRing) MulByVectorMontgomeryThenAddLazy(p1 RNSPoly, vector []uint64, p2 RNSPoly)

MulByVectorMontgomeryThenAddLazy evaluates p2 = p2 + p1 * vector coefficient-wise in the ring.

func (RNSRing) MulCoeffsBarrett 

func (r RNSRing) MulCoeffsBarrett(p1, p2, p3 RNSPoly)

MulCoeffsBarrett evaluates p3 = p1 * p2 coefficient-wise in the ring, with Barrett reduction.

func (RNSRing) MulCoeffsBarrettLazy 

func (r RNSRing) MulCoeffsBarrettLazy(p1, p2, p3 RNSPoly)

MulCoeffsBarrettLazy evaluates p3 = p1 * p2 coefficient-wise in the ring, with Barrett reduction, with p3 in [0, 2*modulus-1].

func (RNSRing) MulCoeffsBarrettThenAdd 

func (r RNSRing) MulCoeffsBarrettThenAdd(p1, p2, p3 RNSPoly)

MulCoeffsBarrettThenAdd evaluates p3 = p3 + p1 * p2 coefficient-wise in the ring, with Barrett reduction.

func (RNSRing) MulCoeffsBarrettThenAddLazy 

func (r RNSRing) MulCoeffsBarrettThenAddLazy(p1, p2, p3 RNSPoly)

MulCoeffsBarrettThenAddLazy evaluates p3 = p1 * p2 coefficient-wise in the ring, with Barrett reduction, with p3 in [0, 2*modulus-1].

func (RNSRing) MulCoeffsMontgomery 

func (r RNSRing) MulCoeffsMontgomery(p1, p2, p3 RNSPoly)

MulCoeffsMontgomery evaluates p3 = p1 * p2 coefficient-wise in the ring, with Montgomery reduction.

func (RNSRing) MulCoeffsMontgomeryLazy 

func (r RNSRing) MulCoeffsMontgomeryLazy(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryLazy evaluates p3 = p1 * p2 coefficient-wise in the ring, with Montgomery reduction, with p3 in [0, 2*modulus-1].

func (RNSRing) MulCoeffsMontgomeryLazyThenAddLazy 

func (r RNSRing) MulCoeffsMontgomeryLazyThenAddLazy(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryLazyThenAddLazy evaluates p3 = p3 + p1 * p2 coefficient-wise in the ring, with Montgomery reduction, with p3 in [0, 3*modulus-2].

func (RNSRing) MulCoeffsMontgomeryLazyThenNeg 

func (r RNSRing) MulCoeffsMontgomeryLazyThenNeg(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryLazyThenNeg evaluates p3 = -p1 * p2 coefficient-wise in the ring, with Montgomery reduction, with p3 in [0, 2*modulus-1].

func (RNSRing) MulCoeffsMontgomeryLazyThenSubLazy 

func (r RNSRing) MulCoeffsMontgomeryLazyThenSubLazy(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryLazyThenSubLazy evaluates p3 = p3 - p1 * p2 coefficient-wise in the ring, with Montgomery reduction, with p3 in [0, 3*modulus-2].

func (RNSRing) MulCoeffsMontgomeryThenAdd 

func (r RNSRing) MulCoeffsMontgomeryThenAdd(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryThenAdd evaluates p3 = p3 + p1 * p2 coefficient-wise in the ring, with Montgomery reduction, with p3 in [0, 2*modulus-1].

func (RNSRing) MulCoeffsMontgomeryThenAddLazy 

func (r RNSRing) MulCoeffsMontgomeryThenAddLazy(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryThenAddLazy evaluates p3 = p3 + p1 * p2 coefficient-wise in the ring, with Montgomery reduction, with p3 in [0, 2*modulus-1].

func (RNSRing) MulCoeffsMontgomeryThenSub 

func (r RNSRing) MulCoeffsMontgomeryThenSub(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryThenSub evaluates p3 = p3 - p1 * p2 coefficient-wise in the ring, with Montgomery reduction.

func (RNSRing) MulCoeffsMontgomeryThenSubLazy 

func (r RNSRing) MulCoeffsMontgomeryThenSubLazy(p1, p2, p3 RNSPoly)

MulCoeffsMontgomeryThenSubLazy evaluates p3 = p3 - p1 * p2 coefficient-wise in the ring, with Montgomery reduction, with p3 in [0, 2*modulus-1].

func (RNSRing) MulDoubleRNSScalar 

func (r RNSRing) MulDoubleRNSScalar(p1 RNSPoly, scalar0, scalar1 RNSScalar, p2 RNSPoly)

MulDoubleRNSScalar evaluates p2 = p1[:N/2] * scalar0 || p1[N/2] * scalar1 coefficient-wise in the ring, with the scalar values expressed in the CRT decomposition at a given level.

func (RNSRing) MulDoubleRNSScalarThenAdd 

func (r RNSRing) MulDoubleRNSScalarThenAdd(p1 RNSPoly, scalar0, scalar1 RNSScalar, p2 RNSPoly)

MulDoubleRNSScalarThenAdd evaluates p2 = p2 + p1[:N/2] * scalar0 || p1[N/2] * scalar1 coefficient-wise in the ring, with the scalar values expressed in the CRT decomposition at a given level.

func (RNSRing) MulRNSScalar 

func (r RNSRing) MulRNSScalar(s1, s2, sout RNSScalar)

MulRNSScalar multiplies s1 and s2 and stores the result in sout. Multiplication is operated with Montgomery.

func (RNSRing) MulRNSScalarMontgomery 

func (r RNSRing) MulRNSScalarMontgomery(p1 RNSPoly, scalar RNSScalar, p2 RNSPoly)

MulRNSScalarMontgomery evaluates p2 = p1 * scalar coefficient-wise in the ring, with a scalar value expressed in the CRT decomposition at a given level. It assumes the scalar decomposition to be in Montgomery form.

func (RNSRing) MulScalar 

func (r RNSRing) MulScalar(p1 RNSPoly, scalar uint64, p2 RNSPoly)

MulScalar evaluates p2 = p1 * scalar coefficient-wise in the ring.

func (RNSRing) MulScalarBigint 

func (r RNSRing) MulScalarBigint(p1 RNSPoly, scalar *big.Int, p2 RNSPoly)

MulScalarBigint evaluates p2 = p1 * scalar coefficient-wise in the ring.

func (RNSRing) MulScalarBigintThenAdd 

func (r RNSRing) MulScalarBigintThenAdd(p1 RNSPoly, scalar *big.Int, p2 RNSPoly)

MulScalarBigintThenAdd evaluates p2 = p1 * scalar coefficient-wise in the ring.

func (RNSRing) MulScalarThenAdd 

func (r RNSRing) MulScalarThenAdd(p1 RNSPoly, scalar uint64, p2 RNSPoly)

MulScalarThenAdd evaluates p2 = p2 + p1 * scalar coefficient-wise in the ring.

func (RNSRing) MulScalarThenSub 

func (r RNSRing) MulScalarThenSub(p1 RNSPoly, scalar uint64, p2 RNSPoly)

MulScalarThenSub evaluates p2 = p2 - p1 * scalar coefficient-wise in the ring.

func (RNSRing) MultByMonomial 

func (r RNSRing) MultByMonomial(p1 RNSPoly, k int, p2 RNSPoly)

MultByMonomial evaluates p2 = p1 * X^k coefficient-wise in the ring.

func (RNSRing) N 

func (r RNSRing) N() int

N returns the ring degree.

func (RNSRing) NTT 

func (r RNSRing) NTT(p1, p2 RNSPoly)

NTT evaluates p2 = NTT(P1).

func (RNSRing) NTTLazy 

func (r RNSRing) NTTLazy(p1, p2 RNSPoly)

NTTLazy evaluates p2 = NTT(p1) with p2 in [0, 2*modulus-1].

func (RNSRing) Neg 

func (r RNSRing) Neg(p1, p2 RNSPoly)

Neg evaluates p2 = -p1 coefficient-wise in the ring.

func (RNSRing) NegRNSScalar 

func (r RNSRing) NegRNSScalar(s1, s2 RNSScalar)

NegRNSScalar evaluates s2 = -s1.

func (RNSRing) NewMonomialXi 

func (r RNSRing) NewMonomialXi(i int) (p RNSPoly)

NewMonomialXi returns a polynomial X^{i}.

func (RNSRing) NewRNSPoly 

func (r RNSRing) NewRNSPoly() RNSPoly

NewRNSPoly creates a new RNSPoly with all coefficients set to 0.

func (RNSRing) NewRNSScalar 

func (r RNSRing) NewRNSScalar() RNSScalar

NewRNSScalar creates a new Scalar value.

func (RNSRing) NewRNSScalarFromBigint 

func (r RNSRing) NewRNSScalarFromBigint(v *big.Int) (rns RNSScalar)

NewRNSScalarFromBigint creates a new Scalar initialized with value v.

func (RNSRing) NewRNSScalarFromUInt64 

func (r RNSRing) NewRNSScalarFromUInt64(v uint64) (rns RNSScalar)

NewRNSScalarFromUInt64 creates a new Scalar initialized with value v.

func (RNSRing) NthRoot 

func (r RNSRing) NthRoot() uint64

NthRoot returns the multiplicative order of the primitive root.

func (RNSRing) OverflowMargin 

func (r RNSRing) OverflowMargin() int

OverflowMargin returns the overflow margin of the ring.

func (RNSRing) PadDefaultRingToConjugateInvariant 

func (r RNSRing) PadDefaultRingToConjugateInvariant(polyStandard RNSPoly, IsNTT bool, polyConjugateInvariant RNSPoly)

PadDefaultRingToConjugateInvariant converts a polynomial in Z[X]/(X^N +1) to a polynomial in Z[X+X^-1]/(X^2N+1).

func (RNSRing) PolyToBigint 

func (r RNSRing) PolyToBigint(p1 RNSPoly, gap int, coeffsBigint []big.Int)

PolyToBigint reconstructs p1 and returns the result in an array of Int. gap defines coefficients X^{i*gap} that will be reconstructed. For example, if gap = 1, then all coefficients are reconstructed, while if gap = 2 then only coefficients X^{2*i} are reconstructed.

func (RNSRing) PolyToBigintCentered 

func (r RNSRing) PolyToBigintCentered(p1 RNSPoly, gap int, values []big.Int)

PolyToBigintCentered reconstructs p1 and returns the result in an array of Int. Coefficients are centered around Q/2 gap defines coefficients X^{i*gap} that will be reconstructed. For example, if gap = 1, then all coefficients are reconstructed, while if gap = 2 then only coefficients X^{2*i} are reconstructed.

func (RNSRing) PolyToString 

func (r RNSRing) PolyToString(p1 RNSPoly) []string

PolyToString reconstructs p1 and returns the result in an array of string.

func (RNSRing) Reduce 

func (r RNSRing) Reduce(p1, p2 RNSPoly)

Reduce evaluates p2 = p1 coefficient-wise mod modulus in the ring.

func (RNSRing) ReduceLazy 

func (r RNSRing) ReduceLazy(p1, p2 RNSPoly)

ReduceLazy evaluates p2 = p1 coefficient-wise mod modulus in the ring, with p2 in [0, 2*modulus-1].

func (RNSRing) RescaleConstants 

func (r RNSRing) RescaleConstants() (out []uint64)

RescaleConstants returns the rescaling constants for a given level.

func (RNSRing) SetCoefficientsBigint 

func (r RNSRing) SetCoefficientsBigint(coeffs []big.Int, p1 RNSPoly)

SetCoefficientsBigint sets the coefficients of p1 from an array of Int variables.

func (RNSRing) Shift 

func (r RNSRing) Shift(p1 RNSPoly, k int, p2 RNSPoly)

Shift evaluates p2 = p2<<<k coefficient-wise in the ring.

func (RNSRing) Standard 

func (r RNSRing) Standard() (sr RNSRing, err error)

Standard returns the standard ring of the receiver RNSRing. If `r.Type()==Standard`, then the method returns the receiver. if `r.Type()==ConjugateInvariant`, then the method returns a ring with ring degree 2N. The returned Ring is a shallow copy of the receiver.

func (RNSRing) Stats 

func (r RNSRing) Stats(poly RNSPoly) [2]float64

Stats returns base 2 logarithm of the standard deviation and the mean of the coefficients of the polynomial.

func (RNSRing) Sub 

func (r RNSRing) Sub(p1, p2, p3 RNSPoly)

Sub evaluates p3 = p1 - p2 coefficient-wise in the ring.

func (RNSRing) SubDoubleRNSScalar 

func (r RNSRing) SubDoubleRNSScalar(p1 RNSPoly, scalar0, scalar1 RNSScalar, p2 RNSPoly)

SubDoubleRNSScalar evaluates p2 = p1[:N/2] - scalar0 || p1[N/2] - scalar1 coefficient-wise in the ring, with the scalar values expressed in the CRT decomposition at a given level.

func (RNSRing) SubLazy 

func (r RNSRing) SubLazy(p1, p2, p3 RNSPoly)

SubLazy evaluates p3 = p1 - p2 coefficient-wise in the ring, with p3 in [0, 2*modulus-1].

func (RNSRing) SubRNSScalar 

func (r RNSRing) SubRNSScalar(s1, s2, sout RNSScalar)

SubRNSScalar subtracts s2 to s1 and stores the result in sout.

func (RNSRing) SubScalar 

func (r RNSRing) SubScalar(p1 RNSPoly, scalar uint64, p2 RNSPoly)

SubScalar evaluates p2 = p1 - scalar coefficient-wise in the ring.

func (RNSRing) SubScalarBigint 

func (r RNSRing) SubScalarBigint(p1 RNSPoly, scalar *big.Int, p2 RNSPoly)

SubScalarBigint evaluates p2 = p1 - scalar coefficient-wise in the ring.

func (RNSRing) SwitchRingDegree 

func (r RNSRing) SwitchRingDegree(p0, p1 RNSPoly)

SwitchRingDegree changes the ring degree of p0 to the one of p1. Maps Y^{N/n} -> X^{N} or X^{N} -> Y^{N/n}. Inputs are expected to not be in the NTT domain.

func (RNSRing) SwitchRingDegreeNTT 

func (r RNSRing) SwitchRingDegreeNTT(p0 RNSPoly, buff []uint64, p1 RNSPoly)

SwitchRingDegreeNTT changes the ring degree of p0 to the one of p1. Maps Y^{N/n} -> X^{N} or X^{N} -> Y^{N/n}. Inputs are expected to be in the NTT domain.

func (RNSRing) Type 

func (r RNSRing) Type() Type

Type returns the Type of the first Ring which might be either `Standard` or `ConjugateInvariant`.

func (RNSRing) UnfoldConjugateInvariantToStandard 

func (r RNSRing) UnfoldConjugateInvariantToStandard(polyConjugateInvariant, polyStandard RNSPoly)

UnfoldConjugateInvariantToStandard maps the compressed representation (N/2 coefficients) of Z_Q[X+X^-1]/(X^2N + 1) to full representation in Z_Q[X]/(X^2N+1). Requires degree(polyConjugateInvariant) = 2*degree(polyStandard). Requires that polyStandard and polyConjugateInvariant share the same moduli.

func (*RNSRing) UnmarshalBinary 

func (r *RNSRing) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary decodes a slice of bytes generated by MarshalBinary or MarshalJSON on the object.

func (*RNSRing) UnmarshalJSON 

func (r *RNSRing) UnmarshalJSON(data []byte) (err error)

UnmarshalJSON decodes a slice of bytes generated by MarshalJSON or MarshalBinary on the object.

type RNSScalar 

type RNSScalar []uint64

RNSScalar represents a scalar value in the Ring (i.e., a degree-0 polynomial) in RNS form.

type Ring 

type Ring struct {
	NumberTheoreticTransformer

	// Polynomial nb.Coefficients
	N int

	BaseModulus uint64

	BaseModulusPower int

	// BaseModulus^BaseModulusPower
	Modulus uint64

	// Unique factors of Modulus-1
	Factors []uint64

	// 2^bit_length(Modulus) - 1
	Mask uint64

	// Fast reduction constants
	BRedConstant [2]uint64 // Barrett Reduction
	MRedConstant uint64    // Montgomery Reduction

	*NTTTable // NTT related constants
}

Ring is a struct storing precomputation for fast modular reduction and NTT for a given modulus.

func NewRing 

func NewRing(N int, Modulus uint64, ModulusPower int) (s *Ring, err error)

NewRing creates a new Ring with the standard NTT. NTT constants still need to be generated using .GenNTTConstants(NthRoot uint64).

func NewRingWithCustomNTT 

func NewRingWithCustomNTT(N int, Modulus uint64, ModulusPower int, ntt func(*Ring, int) NumberTheoreticTransformer, NthRoot int) (r *Ring, err error)

NewRingWithCustomNTT creates a new Ring with degree N and modulus Modulus with user-defined NumberTheoreticTransformer and primitive Nth root of unity. An error is returned with a nil *Ring in the case of non NTT-enabling parameters.

func (Ring) Add 

func (r Ring) Add(p1, p2, p3 []uint64)

Add evaluates p3 = p1 + p2 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) AddLazy 

func (r Ring) AddLazy(p1, p2, p3 []uint64)

AddLazy evaluates p3 = p1 + p2. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) AddLazyThenMulScalarMontgomery 

func (r Ring) AddLazyThenMulScalarMontgomery(p1, p2 []uint64, scalarMont uint64, p3 []uint64)

AddLazyThenMulScalarMontgomery evaluates p3 = (p1+p2)*scalarMont (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) AddScalar 

func (r Ring) AddScalar(p1 []uint64, scalar uint64, p2 []uint64)

AddScalar evaluates p2 = p1 + scalar (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) AddScalarLazy 

func (r Ring) AddScalarLazy(p1 []uint64, scalar uint64, p2 []uint64)

AddScalarLazy evaluates p2 = p1 + scalar. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) AddScalarLazyThenMulScalarMontgomery 

func (r Ring) AddScalarLazyThenMulScalarMontgomery(p1 []uint64, scalar0, scalarMont1 uint64, p2 []uint64)

AddScalarLazyThenMulScalarMontgomery evaluates p3 = (scalarMont0+p2)*scalarMont1 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) AddScalarLazyThenNegTwoModulusLazy 

func (r Ring) AddScalarLazyThenNegTwoModulusLazy(p1 []uint64, scalar uint64, p2 []uint64)

AddScalarLazyThenNegTwoModulusLazy evaluates p2 = 2*modulus - p1 + scalar. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) CenterModU64 

func (r Ring) CenterModU64(p1 []uint64, p2 []uint64)

CenterModU64 evaluates p2 = center(p1, w) % 2^{64} Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) DecomposeSigned 

func (r Ring) DecomposeSigned(j int, pw2 uint64, in, carry, out []uint64)

func (Ring) DecomposeSignedBalanced 

func (r Ring) DecomposeSignedBalanced(j int, pw2 uint64, in, carry, out []uint64)

func (Ring) DecomposeUnsigned 

func (r Ring) DecomposeUnsigned(j int, pw2 uint64, in, out []uint64)

func (*Ring) GenNTTTable 

func (r *Ring) GenNTTTable() (err error)

GenNTTTable generates the NTT tables for the target Ring. The fields `PrimitiveRoot` and `Factors` can be set manually to bypass the search for the primitive root (which requires to factor Modulus-1) and speedup the generation of the constants.

func (Ring) IMForm 

func (r Ring) IMForm(p1, p2 []uint64)

IMForm evaluates p2 = p1 * (2^64)^-1 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) INTT 

func (r Ring) INTT(p1, p2 []uint64)

INTT evaluates p2 = INTT(p1).

func (Ring) INTTLazy 

func (r Ring) INTTLazy(p1, p2 []uint64)

INTTLazy evaluates p2 = INTT(p1) with p2 in [0, 2*modulus-1].

func (Ring) LogN 

func (r Ring) LogN() int

func (Ring) MForm 

func (r Ring) MForm(p1, p2 []uint64)

MForm evaluates p2 = p1 * 2^64 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MFormLazy 

func (r Ring) MFormLazy(p1, p2 []uint64)

MFormLazy evaluates p2 = p1 * 2^64 (mod modulus) with p2 in the range [0, 2*modulus-1]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsBarrett 

func (r Ring) MulCoeffsBarrett(p1, p2, p3 []uint64)

MulCoeffsBarrett evaluates p3 = p1*p2 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsBarrettLazy 

func (r Ring) MulCoeffsBarrettLazy(p1, p2, p3 []uint64)

MulCoeffsBarrettLazy evaluates p3 = p1*p2 (mod modulus) with p3 in [0, 2*modulus-1]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsBarrettThenAdd 

func (r Ring) MulCoeffsBarrettThenAdd(p1, p2, p3 []uint64)

MulCoeffsBarrettThenAdd evaluates p3 = p3 + (p1*p2) (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsBarrettThenAddLazy 

func (r Ring) MulCoeffsBarrettThenAddLazy(p1, p2, p3 []uint64)

MulCoeffsBarrettThenAddLazy evaluates p3 = p3 + p1*p2 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsLazy 

func (r Ring) MulCoeffsLazy(p1, p2, p3 []uint64)

MulCoeffsLazy evaluates p3 = p1*p2. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsLazyThenAddLazy 

func (r Ring) MulCoeffsLazyThenAddLazy(p1, p2, p3 []uint64)

MulCoeffsLazyThenAddLazy evaluates p3 = p3 + p1*p2. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomery 

func (r Ring) MulCoeffsMontgomery(p1, p2, p3 []uint64)

MulCoeffsMontgomery evaluates p3 = p1*p2 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryLazy 

func (r Ring) MulCoeffsMontgomeryLazy(p1, p2, p3 []uint64)

MulCoeffsMontgomeryLazy evaluates p3 = p1*p2 (mod modulus) with p3 in range [0, 2*modulus-1]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryLazyThenAddLazy 

func (r Ring) MulCoeffsMontgomeryLazyThenAddLazy(p1, p2, p3 []uint64)

MulCoeffsMontgomeryLazyThenAddLazy evaluates p3 = p3 + p1*p2 (mod modulus) with p3 in range [0, 3modulus-2]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryLazyThenNeg 

func (r Ring) MulCoeffsMontgomeryLazyThenNeg(p1, p2, p3 []uint64)

MulCoeffsMontgomeryLazyThenNeg evaluates p3 = - p1*p2 (mod modulus) with p3 in range [0, 2*modulus-2]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryLazyThenSubLazy 

func (r Ring) MulCoeffsMontgomeryLazyThenSubLazy(p1, p2, p3 []uint64)

MulCoeffsMontgomeryLazyThenSubLazy evaluates p3 = p3 - p1*p2 (mod modulus) with p3 in range [0, 3*modulus-2]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryThenAdd 

func (r Ring) MulCoeffsMontgomeryThenAdd(p1, p2, p3 []uint64)

MulCoeffsMontgomeryThenAdd evaluates p3 = p3 + (p1*p2) (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryThenAddLazy 

func (r Ring) MulCoeffsMontgomeryThenAddLazy(p1, p2, p3 []uint64)

MulCoeffsMontgomeryThenAddLazy evaluates p3 = p3 + (p1*p2 (mod modulus)). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryThenSub 

func (r Ring) MulCoeffsMontgomeryThenSub(p1, p2, p3 []uint64)

MulCoeffsMontgomeryThenSub evaluates p3 = p3 - p1*p2 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulCoeffsMontgomeryThenSubLazy 

func (r Ring) MulCoeffsMontgomeryThenSubLazy(p1, p2, p3 []uint64)

MulCoeffsMontgomeryThenSubLazy evaluates p3 = p3 - p1*p2 (mod modulus) with p3 in range [0, 2*modulus-2]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulScalar 

func (r Ring) MulScalar(p1 []uint64, scalar uint64, p2 []uint64)

MulScalar evaluates p2 = p1*scalar (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulScalarMontgomery 

func (r Ring) MulScalarMontgomery(p1 []uint64, scalarMont uint64, p2 []uint64)

MulScalarMontgomery evaluates p2 = p1*scalarMont (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulScalarMontgomeryLazy 

func (r Ring) MulScalarMontgomeryLazy(p1 []uint64, scalarMont uint64, p2 []uint64)

MulScalarMontgomeryLazy evaluates p2 = p1*scalarMont (mod modulus) with p2 in range [0, 2*modulus-1]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulScalarMontgomeryThenAdd 

func (r Ring) MulScalarMontgomeryThenAdd(p1 []uint64, scalarMont uint64, p2 []uint64)

MulScalarMontgomeryThenAdd evaluates p2 = p2 + p1*scalarMont (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) MulScalarMontgomeryThenAddScalar 

func (r Ring) MulScalarMontgomeryThenAddScalar(p1 []uint64, scalar0, scalarMont1 uint64, p2 []uint64)

MulScalarMontgomeryThenAddScalar evaluates p2 = scalar + p1*scalarMont (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) NTT 

func (r Ring) NTT(p1, p2 []uint64)

NTT evaluates p2 = NTT(p1).

func (Ring) NTTLazy 

func (r Ring) NTTLazy(p1, p2 []uint64)

NTTLazy evaluates p2 = NTT(p1) with p2 in [0, 2*modulus-1].

func (Ring) Neg 

func (r Ring) Neg(p1, p2 []uint64)

Neg evaluates p2 = -p1 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) NewPoly 

func (r Ring) NewPoly() Poly

func (Ring) Phi 

func (r Ring) Phi() (phi uint64)

Phi returns Phi(BaseModulus^BaseModulusPower)

func (Ring) Reduce 

func (r Ring) Reduce(p1, p2 []uint64)

Reduce evaluates p2 = p1 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) ReduceLazy 

func (r Ring) ReduceLazy(p1, p2 []uint64)

ReduceLazy evaluates p2 = p1 (mod modulus) with p2 in range [0, 2*modulus-1]. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) SetCoefficientsBigint 

func (r Ring) SetCoefficientsBigint(coeffs []big.Int, p1 []uint64)

SetCoefficientsBigint sets the coefficients of p1 from an array of Int variables.

func (Ring) Stats 

func (r Ring) Stats(poly Poly) [2]float64

Stats returns base 2 logarithm of the standard deviation and the mean of the coefficients of the polynomial.

func (Ring) Sub 

func (r Ring) Sub(p1, p2, p3 []uint64)

Sub evaluates p3 = p1 - p2 (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) SubLazy 

func (r Ring) SubLazy(p1, p2, p3 []uint64)

SubLazy evaluates p3 = p1 - p2. Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) SubScalar 

func (r Ring) SubScalar(p1 []uint64, scalar uint64, p2 []uint64)

SubScalar evaluates p2 = p1 - scalar (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) SubScalarBigint 

func (r Ring) SubScalarBigint(p1 []uint64, scalar *big.Int, p2 []uint64)

SubScalarBigint evaluates p2 = p1 - scalar (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) SubThenMulScalarMontgomeryTwoModulus 

func (r Ring) SubThenMulScalarMontgomeryTwoModulus(p1, p2 []uint64, scalarMont uint64, p3 []uint64)

SubThenMulScalarMontgomeryTwoModulus evaluates p3 = (p1 + twomodulus - p2) * scalarMont (mod modulus). Iteration is done with respect to len(p1). All input must have a size which is a multiple of 8.

func (Ring) Type 

func (r Ring) Type() Type

Type returns the Type of Ring which might be either `Standard` or `ConjugateInvariant`.

type Sampler 

type Sampler interface {
	GetSource() *sampling.Source
	Read(pol RNSPoly)
	ReadNew(N int) (pol RNSPoly)
	ReadAndAdd(pol RNSPoly)
	AtLevel(level int) Sampler
	WithSource(source *sampling.Source) Sampler
}

Sampler is an interface for random polynomial samplers. It has a single Read method which takes as argument the polynomial to be populated according to the Sampler's distribution.

func NewSampler 

func NewSampler(source *sampling.Source, moduli []uint64, X DistributionParameters) (Sampler, error)

NewSampler instantiates a new Sampler interface from the provided rand.Source, modulic chain and DistributionParameters.

type Ternary 

type Ternary struct {
	P float64
	H int
}

Ternary represent the parameters of a distribution with coefficients in [-1, 0, 1]. Only one of its field must be set to a non-zero value:

  • If P is set, each coefficient in the polynomial is sampled in [-1, 0, 1] with probabilities [0.5*P, 1-P, 0.5*P].
  • if H is set, the coefficients are sampled uniformly in the set of ternary polynomials with H non-zero coefficients (i.e., of hamming weight H).

func (Ternary) BinarySize 

func (d Ternary) BinarySize() int

func (Ternary) Equal 

func (d Ternary) Equal(other DistributionParameters) bool

func (Ternary) MarshalBinary 

func (d Ternary) MarshalBinary() (p []byte, err error)

func (*Ternary) ReadFrom 

func (d *Ternary) ReadFrom(r io.Reader) (n int64, err error)

func (*Ternary) UnmarshalBinary 

func (d *Ternary) UnmarshalBinary(p []byte) (err error)

func (Ternary) WriteTo 

func (d Ternary) WriteTo(w io.Writer) (n int64, err error)

type TernarySampler 

type TernarySampler struct {
	Moduli []uint64
	*sampling.Source
	// contains filtered or unexported fields
}

TernarySampler keeps the state of a polynomial sampler in the ternary distribution.

func NewTernarySampler 

func NewTernarySampler(source *sampling.Source, moduli []uint64, X Ternary) (s *TernarySampler, err error)

NewTernarySampler creates a new instance of TernarySampler from a sampling.Source, a moduli chain and and a ternary distribution parameters (see type Ternary).

func (TernarySampler) AtLevel 

func (s TernarySampler) AtLevel(level int) Sampler

AtLevel returns an instance of the target TernarySampler to sample at the given level. The returned sampler cannot be used concurrently to the original sampler.

func (TernarySampler) GetSource 

func (s TernarySampler) GetSource() *sampling.Source

GetSource returns the underlying sampling.Source used by the sampler.

func (*TernarySampler) Read 

func (s *TernarySampler) Read(pol RNSPoly)

Read samples a polynomial into pol.

func (*TernarySampler) ReadAndAdd 

func (s *TernarySampler) ReadAndAdd(pol RNSPoly)

func (*TernarySampler) ReadNew 

func (s *TernarySampler) ReadNew(N int) (pol RNSPoly)

ReadNew allocates and samples a polynomial at the max level.

func (TernarySampler) WithSource 

func (s TernarySampler) WithSource(source *sampling.Source) Sampler

WithSource returns an instance of the underlying sampler with a new sampling.Source. It can be used concurrently with the original sampler.

type Type 

type Type int

Type is the type of ring used by the cryptographic scheme

func (Type) MarshalJSON 

func (rt Type) MarshalJSON() ([]byte, error)

MarshalJSON marshals the receiver Type into a JSON []byte

func (Type) String 

func (rt Type) String() string

String returns the string representation of the ring Type

func (*Type) UnmarshalJSON 

func (rt *Type) UnmarshalJSON(b []byte) error

UnmarshalJSON reads a JSON byte slice into the receiver Type

type Uniform 

type Uniform struct{}

Uniform represents the parameters of a uniform distribution i.e., with coefficients uniformly distributed in the given ring.

func (Uniform) BinarySize 

func (d Uniform) BinarySize() int

func (Uniform) Equal 

func (d Uniform) Equal(other DistributionParameters) bool

func (Uniform) MarshalBinary 

func (d Uniform) MarshalBinary() (p []byte, err error)

func (*Uniform) ReadFrom 

func (d *Uniform) ReadFrom(r io.Reader) (n int64, err error)

func (*Uniform) UnmarshalBinary 

func (d *Uniform) UnmarshalBinary(p []byte) (err error)

func (Uniform) WriteTo 

func (d Uniform) WriteTo(w io.Writer) (n int64, err error)

type UniformSampler 

type UniformSampler struct {
	Moduli []uint64
	*sampling.Source
}

UniformSampler wraps a util.PRNG and represents the state of a sampler of uniform polynomials.

func NewUniformSampler 

func NewUniformSampler(source *sampling.Source, moduli []uint64) (u *UniformSampler)

NewUniformSampler creates a new instance of UniformSampler from a sampling.Source and a list of moduli.

func (UniformSampler) AtLevel 

func (u UniformSampler) AtLevel(level int) Sampler

AtLevel returns an instance of the target UniformSampler to sample at the given level. The returned sampler cannot be used concurrently to the original sampler.

func (UniformSampler) GetSource 

func (u UniformSampler) GetSource() *sampling.Source

GetSource returns the underlying sampling.Source used by the sampler.

func (*UniformSampler) Read 

func (u *UniformSampler) Read(pol RNSPoly)

func (*UniformSampler) ReadAndAdd 

func (u *UniformSampler) ReadAndAdd(pol RNSPoly)

func (*UniformSampler) ReadNew 

func (u *UniformSampler) ReadNew(N int) (pol RNSPoly)

ReadNew generates a new polynomial with coefficients following a uniform distribution over [0, Qi-1]. Polynomial is created at the max level.

func (UniformSampler) WithSource 

func (u UniformSampler) WithSource(source *sampling.Source) Sampler

WithSource returns an instance of the underlying sampler with a new sampling.Source. It can be used concurrently with the original sampler.

type Vector 

type Vector struct {
	Q structs.Vector[RNSPoly]
	P structs.Vector[RNSPoly]
}

Vector is a struct storing a vector of ring.RNSPoly in basis Q and P.

func NewVector 

func NewVector(N, LevelQ, LevelP, size int) (v *Vector)

NewVector allocates a new ring.Vector.

func NewVectorAtLevelFromPoly 

func NewVectorAtLevelFromPoly(LevelQ, LevelP int, pQ, pP []RNSPoly) (*Vector, error)

func (*Vector) Aggregate 

func (v *Vector) Aggregate(rQ, rP RNSRing, a, b *Vector) (err error)

Aggregate sets the receiver to a + b. The method returns an error if operands do not match the receiver LevelQ(), LevelP(), Size().

func (*Vector) AsPoint 

func (v *Vector) AsPoint() *Point

AsPoint wraps the receiver in an Point.

func (Vector) BinarySize 

func (v Vector) BinarySize() (size int)

BinarySize returns the serialized size of the object in bytes.

func (*Vector) BufferSize 

func (v *Vector) BufferSize(N, LevelQ, LevelP, size int) int

BufferSize returns the minimum buffer size to instantiate the receiver through [FromBuffer].

func (Vector) Clone 

func (v Vector) Clone() (clone *Vector)

Clone returns a new Point which is a deep copy of the receiver.

func (*Vector) ConcatPtoQ 

func (v *Vector) ConcatPtoQ(n int) *Vector

ConcatPtoQ returns an instance of the receiver where the modulus Q is increased to Q[:] + P[:n] and the modulus P reduced to P[n:]. n must be a positive integer 0 <= n <= v.LevelP()+1. Backing arrays are shared.

func (Vector) ConcatQtoP 

func (v Vector) ConcatQtoP(n int) *Vector

ConcatQtoP returns an instance of the receiver where the modulus Q is reduced to Q[:n] and the modulus P increased to Q[n:] + P[:]. n must be a positive integer 0 <= n < v.LevelQ()+1.

func (*Vector) Copy 

func (v *Vector) Copy(other *Vector)

Copy copies the input on the receiver.

func (Vector) Equal 

func (v Vector) Equal(other *Vector) (equal bool)

func (*Vector) FromBuffer 

func (v *Vector) FromBuffer(N, LevelQ, LevelP, size int, buf []uint64) *Vector

FromBuffer assigns new backing array to the receiver. Method panics if len(buf) is too small. Minimum backing array size can be obtained with [BufferSize].

func (Vector) Level 

func (v Vector) Level() int

Level returns the level of the modulus Q of the receiver.

func (Vector) LevelP 

func (v Vector) LevelP() int

LevelP returns the level of the modulus P of the receiver.

func (Vector) LevelQ 

func (v Vector) LevelQ() int

LevelQ returns the level of the modulus Q of the receiver.

func (Vector) LogN 

func (v Vector) LogN() int

LogN returns the base 2 logarithm of the ring degree of the receiver.

func (Vector) MarshalBinary 

func (v Vector) MarshalBinary() (p []byte, err error)

MarshalBinary encodes the object into a binary form on a newly allocated slice of bytes.

func (Vector) N 

func (v Vector) N() int

N returns the ring degree of the receiver.

func (Vector) Randomize 

func (v Vector) Randomize(rQ, rP RNSRing, source *sampling.Source)

Randomize overwrites the coefficients of the receiver with uniformly random coefficients modulo QP.

func (*Vector) ReadFrom 

func (v *Vector) ReadFrom(r io.Reader) (n int64, err error)

ReadFrom reads on the object from an io.Writer. It implements the io.ReaderFrom interface.

Unless r implements the buffer.Reader interface (see see lattigo/utils/buffer/reader.go), it will be wrapped into a bufio.Reader. Since this requires allocation, it is preferable to pass a buffer.Reader directly:

  • When reading multiple values from a io.Reader, it is preferable to first first wrap io.Reader in a pre-allocated bufio.Reader.
  • When reading from a var b []byte, it is preferable to pass a buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

func (*Vector) ResizeP 

func (v *Vector) ResizeP(LevelP int)

ResizeP resizes the field P of the target element.

func (*Vector) ResizeQ 

func (v *Vector) ResizeQ(LevelQ int)

ResizeQ resizes the field Q of the target element.

func (*Vector) ResizeSize 

func (v *Vector) ResizeSize(size int)

func (Vector) Size 

func (v Vector) Size() int

Size returns the size of the receiver.

func (*Vector) UnmarshalBinary 

func (v *Vector) UnmarshalBinary(p []byte) (err error)

UnmarshalBinary decodes a slice of bytes generated by MarshalBinary or WriteTo on the object.

func (Vector) WriteTo 

func (v Vector) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes the object on an io.Writer. It implements the io.WriterTo interface, and will write exactly object.BinarySize() bytes on w.

Unless w implements the buffer.Writer interface (see lattigo/utils/buffer/writer.go), it will be wrapped into a bufio.Writer. Since this requires allocations, it is preferable to pass a buffer.Writer directly:

  • When writing multiple times to a io.Writer, it is preferable to first wrap the io.Writer in a pre-allocated bufio.Writer.
  • When writing to a pre-allocated var b []byte, it is preferable to pass buffer.NewBuffer(b) as w (see lattigo/utils/buffer/buffer.go).

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.