ring

package
v0.0.0-...-e525fad Latest Latest
Warning

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

 Go to latest Published: Aug 10, 2023 License: Apache-2.0 Imports: 12 Imported by: 0

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 (
	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 GaloisGen uint64 = 5

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).

Variables

View Source 
var DefaultParams = []Parameters{
	{12, Qi60[len(Qi60)-2:], Pi60[len(Pi60)-2:]},
	{13, Qi60[len(Qi60)-4:], Pi60[len(Pi60)-4:]},
	{14, Qi60[len(Qi60)-7:], Pi60[len(Pi60)-7:]},
	{15, Qi60[len(Qi60)-14:], Pi60[len(Pi60)-14:]},
	{16, Qi60[len(Qi60)-29:], Pi60[len(Pi60)-29:]},
}

DefaultParams is a struct storing default test parameters of the Qi and Pi moduli for the package Ring.

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 AddScalarNoModAndMulScalarMontgomeryVec 

func AddScalarNoModAndMulScalarMontgomeryVec(p1, p2 []uint64, scalar0, scalarMont1, qi, mredParams uint64)

AddScalarNoModAndMulScalarMontgomeryVec returns p3 = (scalarMont0+p2)*scalarMont1 mod qi.

func AddScalarNoModAndNegTwoQiNoModVec 

func AddScalarNoModAndNegTwoQiNoModVec(p1, p2 []uint64, scalar, qi uint64)

AddScalarNoModAndNegTwoQiNoModVec returns p2 = 2*qi - p1 + scalar.

func AddScalarNoModVec 

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

AddScalarNoModVec returns p2 = p1 + scalar.

func AddScalarVec 

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

AddScalarVec returns p2 = p1 + scalar mod qi.

func AddVec 

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

AddVec returns p3 = p1 + p2 mod qi.

func AddVecNoMod 

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

AddVecNoMod returns p3 = p1 + p2.

func AddVecNoModAndMulScalarMontgomeryVec 

func AddVecNoModAndMulScalarMontgomeryVec(p1, p2, p3 []uint64, scalarMont, qi, mredParams uint64)

AddVecNoModAndMulScalarMontgomeryVec returns p3 = (p1+p2)*scalarMont mod qi.

func BRed 

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

BRed computes x*y mod q.

func BRedAdd 

func BRedAdd(a, q uint64, u []uint64) (r uint64)

BRedAdd computes a mod q.

func BRedAddConstant 

func BRedAddConstant(x, q uint64, u []uint64) uint64

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

func BRedConstant 

func BRedConstant(x, y, q uint64, u []uint64) (r uint64)

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

func BRedParams 

func BRedParams(q uint64) (params []uint64)

BRedParams computes the parameters for the BRed algorithm. Returns ((2^128)/q)/(2^64) and (2^128)/q mod 2^64.

func CRed 

func CRed(a, q uint64) uint64

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

func Copy 

func Copy(p0, p1 *Poly)

Copy copies the coefficients of p0 on p1 within the given Ring. It requires p1 to be at least as big p0. Expects the degree of both polynomials to be identical. Transfers the IsNTT and IsMForm flags.

func CopyLvl 

func CopyLvl(level int, p0, p1 *Poly)

CopyLvl copies the coefficients of p0 on p1 within the given Ring. Copies for up to level+1 moduli. Expects the degree of both polynomials to be identical. Transfers the IsNTT and IsMForm flags.

func CopyValues 

func CopyValues(p0, p1 *Poly)

CopyValues copies the coefficients of p0 on p1 within the given Ring. It requires p1 to be at least as big p0. Expects the degree of both polynomials to be identical. Does not transfer the IsNTT and IsMForm flags.

func CopyValuesLvl 

func CopyValuesLvl(level int, p0, p1 *Poly)

CopyValuesLvl copies the values of p0 on p1, up to level+1 moduli.

func Cos 

func Cos(x *big.Float) (cosx *big.Float)

Cos implements the arbitrary precision computation of Cos(x) Iterative process with an error of ~10^{−0.60206*k} after k iterations. ref: Johansson, B. Tomas, An elementary algorithm to evaluate trigonometric functions to high precision, 2018

func DecodeCoeffs32 

func DecodeCoeffs32(pointer int, coeffs []uint64, data []byte) (int, error)

DecodeCoeffs32 converts a byte array to a matrix of coefficients. Assumes that each coefficient is encoded on 4 bytes.

func DecodeCoeffs64 

func DecodeCoeffs64(pointer int, coeffs []uint64, data []byte) (int, error)

DecodeCoeffs64 converts a byte array to a matrix of coefficients. Assumes that each coefficient is encoded on 8 bytes.

func DivRound 

func DivRound(a, b, i *big.Int)

DivRound sets the target i to round(a/b).

func EvalPolyModP 

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

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

func GenGaloisParams 

func GenGaloisParams(n, gen uint64) (galElRotCol []uint64)

GenGaloisParams generates the generators for the Galois endomorphisms.

func GenerateNTTPrimes 

func GenerateNTTPrimes(logQ, NthRoot, n int) (primes []uint64)

GenerateNTTPrimes generates n NthRoot NTT friendly primes given logQ = size of the primes. It will return all the appropriate primes, up to the number of n, with the best available deviation from the base power of 2 for the given n.

func GenerateNTTPrimesP 

func GenerateNTTPrimesP(logP, NthRoot, n int) (primes []uint64)

GenerateNTTPrimesP generates "levels" different NthRoot NTT-friendly primes starting from 2**LogP and downward. Special case were primes close to 2^{LogP} but with a smaller bit-size than LogP are sought.

func GenerateNTTPrimesQ 

func GenerateNTTPrimesQ(logQ, NthRoot, levels int) (primes []uint64)

GenerateNTTPrimesQ generates "levels" different NthRoot NTT-friendly primes starting from 2**LogQ and alternating between upward and downward.

func GetDataLen64 

func GetDataLen64(N, Level int, WithMetadata bool) (cnt int)

GetDataLen64 returns the number of bytes a polynomial of N coefficients with Level+1 moduli will take when converted to a slice of bytes. Assumes that each coefficient will be encoded on 8 bytes. It can take into account meta data if necessary.

func GetPolyDataLen32 

func GetPolyDataLen32(N, Level int, WithMetadata bool) (cnt int)

GetPolyDataLen32 returns the number of bytes a polynomial of N coefficients with Level+1 moduli will take when converted to a slice of bytes. Assumes that each coefficient will be encoded on 4 bytes. It can take into account meta data if necessary.

func InvMForm 

func InvMForm(a, q, qInv uint64) (r uint64)

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

func InvMFormConstant 

func InvMFormConstant(a, q, qInv uint64) (r uint64)

InvMFormConstant 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 InvMFormVec 

func InvMFormVec(p1, p2 []uint64, qi, mredParams uint64)

InvMFormVec returns p2 = p1 * (2^64)^-1 mod qi.

func InvNTT 

func InvNTT(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTT computes the InvNTT transformation on the input coefficients using the input parameters.

func InvNTTConjugateInvariant 

func InvNTTConjugateInvariant(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTTConjugateInvariant computes the InvNTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func InvNTTConjugateInvariantLazy 

func InvNTTConjugateInvariantLazy(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTTConjugateInvariantLazy computes the InvNTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with output values in the range [0, 2q-1].

func InvNTTLazy 

func InvNTTLazy(coeffsIn, coeffsOut []uint64, N int, nttPsiInv []uint64, nttNInv, Q, QInv uint64)

InvNTTLazy computes the InvNTT transformation on the input coefficients using the input parameters with output values in the range [0, 2q-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, u []uint64) (r uint64)

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

func MFormConstant 

func MFormConstant(a, q uint64, u []uint64) (r uint64)

MFormConstant 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 MFormConstantVec 

func MFormConstantVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

MFormConstantVec returns p2 = p1 * 2^64 mod qi with result in the range [0, 2q-1]

func MFormVec 

func MFormVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

MFormVec returns p2 = p1 * 2^64 mod qi.

func MRed 

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

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

func MRedConstant 

func MRedConstant(x, y, q, qInv uint64) (r uint64)

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

func MRedParams 

func MRedParams(q uint64) (qInv uint64)

MRedParams computes the parameter qInv = (q^-1) mod 2^64, required for MRed.

func MapSmallDimensionToLargerDimensionNTT 

func MapSmallDimensionToLargerDimensionNTT(polSmall, polLarge *Poly)

MapSmallDimensionToLargerDimensionNTT maps Y = X^{N/n} -> X directly in the NTT domain

func MaskVec 

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

MaskVec returns p2 = (p1>>w) & mask

func Min 

func Min(x, y int) int

Min returns the minimum between to int

func ModExp 

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

ModExp performs the modular exponentiation x^e mod p, x and p are required to be at most 64 bits to avoid an overflow.

func ModUpExact 

func ModUpExact(p1, p2 [][]uint64, ringQ, ringP *Ring, params ModupParams)

ModUpExact takes p1 mod Q and switches its basis to P, returning the result on p2. Caution, returns the values in [0, 2q-1]

func ModVec 

func ModVec(p1, p2 []uint64, m uint64, bredParams []uint64)

ModVec returns p2 = p1 mod m.

func ModexpMontgomery 

func ModexpMontgomery(x uint64, e int, q, qInv uint64, bredParams []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 MulByPow2Vec 

func MulByPow2Vec(p1, p2 []uint64, pow2 int, qi, mredParams uint64)

MulByPow2Vec returns p2 = p1 * 2^pow2 mod qi.

func MulCoeffsAndAddNoModVec 

func MulCoeffsAndAddNoModVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsAndAddNoModVec returns p3 = p3 + (p1*p2 mod qi).

func MulCoeffsAndAddVec 

func MulCoeffsAndAddVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsAndAddVec returns p3 = p3 + (p1*p2) mod qi.

func MulCoeffsConstantVec 

func MulCoeffsConstantVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsConstantVec returns p3 = p1*p2 mod qi with output coefficients in range [0, 2qi-1].

func MulCoeffsMontgomeryAndAddNoModVec 

func MulCoeffsMontgomeryAndAddNoModVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndAddNoModVec returns p3 = p3 + (p1*p2 mod qi).

func MulCoeffsMontgomeryAndAddVec 

func MulCoeffsMontgomeryAndAddVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndAddVec returns p3 = p3 + (p1*p2) mod qi.

func MulCoeffsMontgomeryAndSubNoMod 

func MulCoeffsMontgomeryAndSubNoMod(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndSubNoMod returns p3 = p3 - p1*p2 mod qi with output coefficients in range [0, 2qi-2].

func MulCoeffsMontgomeryAndSubVec 

func MulCoeffsMontgomeryAndSubVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryAndSubVec returns p3 = p3 - p1*p2 mod qi.

func MulCoeffsMontgomeryConstantAndAddNoModVec 

func MulCoeffsMontgomeryConstantAndAddNoModVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantAndAddNoModVec returns p3 = p3 + p1*p2 mod qi with output coefficients in range [0, 3qi-2].

func MulCoeffsMontgomeryConstantAndNeg 

func MulCoeffsMontgomeryConstantAndNeg(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantAndNeg returns p3 = - p1*p2 mod qi with output coefficients in range [0, 2qi-2].

func MulCoeffsMontgomeryConstantAndSubNoMod 

func MulCoeffsMontgomeryConstantAndSubNoMod(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantAndSubNoMod returns p3 = p3 - p1*p2 mod qi with output coefficients in range [0, 3qi-2].

func MulCoeffsMontgomeryConstantVec 

func MulCoeffsMontgomeryConstantVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryConstantVec returns p3 = p1*p2 mod qi with output coefficients in range [0, 2qi-1].

func MulCoeffsMontgomeryVec 

func MulCoeffsMontgomeryVec(p1, p2, p3 []uint64, qi, mredParams uint64)

MulCoeffsMontgomeryVec returns p3 = p1*p2 mod qi.

func MulCoeffsNoModAndAddNoModVec 

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

MulCoeffsNoModAndAddNoModVec returns p3 += p1*p2.

func MulCoeffsNoModVec 

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

MulCoeffsNoModVec returns p3 = p1*p2.

func MulCoeffsVec 

func MulCoeffsVec(p1, p2, p3 []uint64, qi uint64, bredParams []uint64)

MulCoeffsVec returns p3 = p1*p2 mod qi.

func MulScalarMontgomeryAndAddScalarVec 

func MulScalarMontgomeryAndAddScalarVec(p1, p2 []uint64, scalar0, scalarMont1, qi, mredParams uint64)

MulScalarMontgomeryAndAddScalarVec returns p2 = scalar + p1*scalarMont mod qi.

func MulScalarMontgomeryAndAddVec 

func MulScalarMontgomeryAndAddVec(p1, p2 []uint64, scalarMont, qi, mredParams uint64)

MulScalarMontgomeryAndAddVec returns p2 = p2 + p1*scalarMont mod qi.

func MulScalarMontgomeryConstantVec 

func MulScalarMontgomeryConstantVec(p1, p2 []uint64, scalarMont, qi, mredParams uint64)

MulScalarMontgomeryConstantVec returns p2 = p1*scalarMont mod qi with output coefficients in range [0, 2qi-1].

func MulScalarMontgomeryVec 

func MulScalarMontgomeryVec(p1, p2 []uint64, scalarMont, qi, mredParams uint64)

MulScalarMontgomeryVec returns p2 = p1*scalarMont mod qi.

func NTT 

func NTT(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, mredParams uint64, bredParams []uint64)

NTT computes the NTT on the input coefficients using the input parameters.

func NTTConjugateInvariant 

func NTTConjugateInvariant(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, QInv uint64, bredParams []uint64)

NTTConjugateInvariant computes the NTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1).

func NTTConjugateInvariantLazy 

func NTTConjugateInvariantLazy(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, QInv uint64, bredParams []uint64)

NTTConjugateInvariantLazy computes the NTT in the closed sub-ring Z[X + X^-1]/(X^2N +1) of Z[X]/(X^2N+1) with output values in the range [0, 2q-1].

func NTTLazy 

func NTTLazy(coeffsIn, coeffsOut []uint64, N int, nttPsi []uint64, Q, QInv uint64, bredParams []uint64)

NTTLazy computes the NTT on the input coefficients using the input parameters with output values in the range [0, 2q-1].

func NegVec 

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

NegVec returns p2 = -p1 mod qi.

func NewFloat 

func NewFloat(x float64, logPrecision int) (y *big.Float)

NewFloat creates a new big.Float element with "logPrecision" bits of precision

func NewInt 

func NewInt(v int64) *big.Int

NewInt creates a new Int with a given int64 value.

func NewIntFromString 

func NewIntFromString(s string) *big.Int

NewIntFromString creates a new Int from a string. A prefix of "0x" or "0X" selects base 16; the "0" prefix selects base 8, and a "0b" or "0B" prefix selects base 2. Otherwise, the selected base is 10.

func NewUint 

func NewUint(v uint64) *big.Int

NewUint creates a new Int with a given uint64 value.

func NextNTTPrime 

func NextNTTPrime(q uint64, NthRoot int) (qNext uint64, err error)

NextNTTPrime returns the next NthRoot NTT prime after q. The input q must be itself an NTT prime for the given NthRoot.

func PadDefaultRingToConjuateInvariant 

func PadDefaultRingToConjuateInvariant(p1 *Poly, ringQ *Ring, p2 *Poly)

PadDefaultRingToConjuateInvariant converts a polynomial in Z[X]/(X^N +1) to a polynomial in Z[X+X^-1]/(X^2N+1). Conversion will check the .IsNTT flag of the polynomial p1.

func PowerOf2 

func PowerOf2(x uint64, n int, q, qInv uint64) (r uint64)

PowerOf2 returns (x*2^n)%q where x is in Montgomery form

func PreviousNTTPrime 

func PreviousNTTPrime(q uint64, NthRoot int) (qPrev uint64, err error)

PreviousNTTPrime returns the previous NthRoot NTT prime after q. The input q must be itself an NTT prime for the given NthRoot.

func RandInt 

func RandInt(max *big.Int) (n *big.Int)

RandInt generates a random Int in [0, max-1].

func RandUniform 

func RandUniform(prng utils.PRNG, v uint64, mask uint64) (randomInt uint64)

RandUniform samples a uniform randomInt variable in the range [0, mask] until randomInt is in the range [0, v-1]. mask needs to be of the form 2^n -1.

func ReduceConstantVec 

func ReduceConstantVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

ReduceConstantVec returns p2 = p1 mod qi with output coefficients range [0, 2qi-1].

func ReduceVec 

func ReduceVec(p1, p2 []uint64, qi uint64, bredParams []uint64)

ReduceVec returns p2 = p1 mod qi.

func SubScalarVec 

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

SubScalarVec returns p2 = p1 - scalar mod qi.

func SubVec 

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

SubVec returns p3 = p1 - p2 mod qi.

func SubVecAndMulScalarMontgomeryTwoQiVec 

func SubVecAndMulScalarMontgomeryTwoQiVec(p1, p2, p3 []uint64, scalarMont, qi, mredParams uint64)

SubVecAndMulScalarMontgomeryTwoQiVec returns p3 = (p1 + twoqi - p2) * scalarMont mod qi.

func SubVecNomod 

func SubVecNomod(p1, p2, p3 []uint64, qi uint64)

SubVecNomod returns p3 = p1 + qi - p2.

func WriteCoeffsTo32 

func WriteCoeffsTo32(pointer int, coeffs []uint64, data []byte) (int, error)

WriteCoeffsTo32 converts a matrix of coefficients to a byte array, using 4 bytes per coefficient.

func WriteCoeffsTo64 

func WriteCoeffsTo64(pointer int, coeffs []uint64, data []byte) (int, error)

WriteCoeffsTo64 converts a matrix of coefficients to a byte array, using 8 bytes per coefficient.

func ZeroVec 

func ZeroVec(p1 []uint64)

ZeroVec sets all values of p1 to zero.

Types

type BasisExtender 

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

BasisExtender stores the necessary parameters for RNS basis extension. The used algorithm is from https://eprint.iacr.org/2018/117.pdf.

func NewBasisExtender 

func NewBasisExtender(ringQ, ringP *Ring) *BasisExtender

NewBasisExtender creates a new BasisExtender, enabling RNS basis extension from Q to P and P to Q.

func (*BasisExtender) ModDownQPtoP 

func (be *BasisExtender) ModDownQPtoP(levelQ, levelP int, p1Q, p1P, p2P *Poly)

ModDownQPtoP reduces the basis of a polynomial. Given a polynomial with coefficients in basis {Q0,Q1....QlevelQ} and {P0,P1...PlevelP}, it reduces its basis from {Q0,Q1....QlevelQ} and {P0,P1...PlevelP} to {P0,P1...PlevelP} and does a floored integer division of the result by Q.

func (*BasisExtender) ModDownQPtoQ 

func (be *BasisExtender) ModDownQPtoQ(levelQ, levelP int, p1Q, p1P, p2Q *Poly)

ModDownQPtoQ reduces the basis of a polynomial. Given a polynomial with coefficients in basis {Q0,Q1....Qlevel} and {P0,P1...Pj}, it reduces its basis from {Q0,Q1....Qlevel} and {P0,P1...Pj} to {Q0,Q1....Qlevel} and does a rounded integer division of the result by P.

func (*BasisExtender) ModDownQPtoQNTT 

func (be *BasisExtender) ModDownQPtoQNTT(levelQ, levelP int, p1Q, p1P, p2Q *Poly)

ModDownQPtoQNTT reduces the basis of a polynomial. Given a polynomial with coefficients in basis {Q0,Q1....Qi} and {P0,P1...Pj}, it reduces its basis from {Q0,Q1....Qi} and {P0,P1...Pj} to {Q0,Q1....Qi} and does a rounded integer division of the result by P. Inputs must be in the NTT domain.

func (*BasisExtender) ModUpPtoQ 

func (be *BasisExtender) ModUpPtoQ(levelP, levelQ int, polP, polQ *Poly)

ModUpPtoQ extends the RNS basis of a polynomial from P to PQ. Given a polynomial with coefficients in basis {P0,P1....Plevel}, it extends its basis from {P0,P1....Plevel} to {Q0,Q1...Qj}

func (*BasisExtender) ModUpQtoP 

func (be *BasisExtender) ModUpQtoP(levelQ, levelP int, polQ, polP *Poly)

ModUpQtoP extends the RNS basis of a polynomial from Q to QP. Given a polynomial with coefficients in basis {Q0,Q1....Qlevel}, it extends its basis from {Q0,Q1....Qlevel} to {Q0,Q1....Qlevel,P0,P1...Pj}

func (*BasisExtender) ShallowCopy 

func (be *BasisExtender) ShallowCopy() *BasisExtender

ShallowCopy creates a shallow copy of this basis extender in which the read-only data-structures are shared with the receiver.

type Complex 

type Complex [2]*big.Float

Complex is a type for arbitrary precision complex number

func NewComplex 

func NewComplex(a, b *big.Float) (c *Complex)

NewComplex creates a new arbitrary precision complex number

func (*Complex) Add 

func (c *Complex) Add(a, b *Complex)

Add adds two arbitrary precision complex numbers together

func (*Complex) Copy 

func (c *Complex) Copy() *Complex

Copy returns a new copy of the target arbitrary precision complex number

func (*Complex) Float64 

func (c *Complex) Float64() complex128

Float64 returns the arbitrary precision complex number as a complex128

func (*Complex) Imag 

func (c *Complex) Imag() *big.Float

Imag returns the imaginary part as a big.Float

func (*Complex) Real 

func (c *Complex) Real() *big.Float

Real returns the real part as a big.Float

func (*Complex) Set 

func (c *Complex) Set(a *Complex)

Set sets a arbitrary precision complex number

func (*Complex) Sub 

func (c *Complex) Sub(a, b *Complex)

Sub subtracts two arbitrary precision complex numbers together

type ComplexMultiplier 

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

ComplexMultiplier is a struct for the multiplication or division of two arbitrary precision complex numbers

func NewComplexMultiplier 

func NewComplexMultiplier() (cEval *ComplexMultiplier)

NewComplexMultiplier creates a new ComplexMultiplier

func (*ComplexMultiplier) Div 

func (cEval *ComplexMultiplier) Div(a, b, c *Complex)

Div divides two arbitrary precision complex numbers together

func (*ComplexMultiplier) Mul 

func (cEval *ComplexMultiplier) Mul(a, b, c *Complex)

Mul multiplies two arbitrary precision complex numbers together

type Decomposer 

type Decomposer struct {
	// 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(ringQ, ringP *Ring) (decomposer *Decomposer)

NewDecomposer creates a new Decomposer.

func (*Decomposer) DecomposeAndSplit 

func (decomposer *Decomposer) DecomposeAndSplit(levelQ, levelP, nbPi, decompRNS int, p0Q, p1Q, p1P *Poly)

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

type GaussianSampler 

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

GaussianSampler keeps the state of a truncated Gaussian polynomial sampler.

func NewGaussianSampler 

func NewGaussianSampler(prng utils.PRNG, baseRing *Ring, sigma float64, bound int) *GaussianSampler

NewGaussianSampler creates a new instance of GaussianSampler from a PRNG, a ring definition and the truncated Gaussian distribution parameters. Sigma is the desired standard deviation and bound is the maximum coefficient norm in absolute value.

func (*GaussianSampler) Read 

func (gaussianSampler *GaussianSampler) Read(pol *Poly)

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

func (*GaussianSampler) ReadAndAddFromDistLvl 

func (gaussianSampler *GaussianSampler) ReadAndAddFromDistLvl(level int, pol *Poly, ring *Ring, sigma float64, bound int)

ReadAndAddFromDistLvl samples a truncated Gaussian polynomial at the given level in the provided ring, standard deviation and bound and adds it on "pol".

func (*GaussianSampler) ReadAndAddLvl 

func (gaussianSampler *GaussianSampler) ReadAndAddLvl(level int, pol *Poly)

ReadAndAddLvl 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) ReadFromDistLvl 

func (gaussianSampler *GaussianSampler) ReadFromDistLvl(level int, pol *Poly, ring *Ring, sigma float64, bound int)

ReadFromDistLvl samples a truncated Gaussian polynomial at the given level in the provided ring, standard deviation and bound.

func (*GaussianSampler) ReadLvl 

func (gaussianSampler *GaussianSampler) ReadLvl(level int, pol *Poly)

ReadLvl samples a truncated Gaussian polynomial at the provided level, in the default ring, standard deviation and bound.

func (*GaussianSampler) ReadLvlNew 

func (gaussianSampler *GaussianSampler) ReadLvlNew(level int) (pol *Poly)

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

func (*GaussianSampler) ReadNew 

func (gaussianSampler *GaussianSampler) ReadNew() (pol *Poly)

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

type ModupParams 

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

ModupParams stores the necessary parameters for RNS basis extension.

func GenModUpParams 

func GenModUpParams(Q, P []uint64) ModupParams

GenModUpParams generates the ModupParams for basis extension from Q to P and P to Q.

type NumberTheoreticTransformer 

type NumberTheoreticTransformer interface {
	Forward(r *Ring, p1, p2 *Poly)
	ForwardLvl(r *Ring, level int, p1, p2 *Poly)
	ForwardLazy(r *Ring, p1, p2 *Poly)
	ForwardLazyLvl(r *Ring, level int, p1, p2 *Poly)
	Backward(r *Ring, p1, p2 *Poly)
	BackwardLvl(r *Ring, level int, p1, p2 *Poly)
	BackwardLazy(r *Ring, p1, p2 *Poly)
	BackwardLazyLvl(r *Ring, level int, p1, p2 *Poly)
	ForwardVec(r *Ring, level int, p1, p2 []uint64)
	ForwardLazyVec(r *Ring, level int, p1, p2 []uint64)
	BackwardVec(r *Ring, level int, p1, p2 []uint64)
	BackwardLazyVec(r *Ring, level int, p1, p2 []uint64)
}

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

type NumberTheoreticTransformerConjugateInvariant 

type NumberTheoreticTransformerConjugateInvariant struct {
}

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(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazy 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazy(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazyLvl 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLazyLvl writes the backward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) BackwardLazyVec 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLazyVec(r *Ring, level int, p1, p2 []uint64)

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

func (NumberTheoreticTransformerConjugateInvariant) BackwardLvl 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLvl writes the backward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerConjugateInvariant) BackwardVec 

func (rntt NumberTheoreticTransformerConjugateInvariant) BackwardVec(r *Ring, level int, p1, p2 []uint64)

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

func (NumberTheoreticTransformerConjugateInvariant) Forward 

func (rntt NumberTheoreticTransformerConjugateInvariant) Forward(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazy 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazy(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazyLvl 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLazyLvl writes the forward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerConjugateInvariant) ForwardLazyVec 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLazyVec(r *Ring, level int, p1, p2 []uint64)

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

func (NumberTheoreticTransformerConjugateInvariant) ForwardLvl 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLvl writes the forward NTT in Z[X+X^-1]/(X^2N+1) on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerConjugateInvariant) ForwardVec 

func (rntt NumberTheoreticTransformerConjugateInvariant) ForwardVec(r *Ring, level int, p1, p2 []uint64)

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

type NumberTheoreticTransformerStandard 

type NumberTheoreticTransformerStandard struct {
}

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

func (NumberTheoreticTransformerStandard) Backward 

func (rntt NumberTheoreticTransformerStandard) Backward(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerStandard) BackwardLazy 

func (rntt NumberTheoreticTransformerStandard) BackwardLazy(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerStandard) BackwardLazyLvl 

func (rntt NumberTheoreticTransformerStandard) BackwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLazyLvl writes the backward NTT in Z[X]/(X^N+1) on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) BackwardLazyVec 

func (rntt NumberTheoreticTransformerStandard) BackwardLazyVec(r *Ring, level int, p1, p2 []uint64)

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

func (NumberTheoreticTransformerStandard) BackwardLvl 

func (rntt NumberTheoreticTransformerStandard) BackwardLvl(r *Ring, level int, p1, p2 *Poly)

BackwardLvl writes the backward NTT in Z[X]/(X^N+1) on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerStandard) BackwardVec 

func (rntt NumberTheoreticTransformerStandard) BackwardVec(r *Ring, level int, p1, p2 []uint64)

BackwardVec writes the backward NTT in Z[X]/(X^N+1) of the i-th level of p1 on the i-th level of p2.

func (NumberTheoreticTransformerStandard) Forward 

func (rntt NumberTheoreticTransformerStandard) Forward(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerStandard) ForwardLazy 

func (rntt NumberTheoreticTransformerStandard) ForwardLazy(r *Ring, p1, p2 *Poly)

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

func (NumberTheoreticTransformerStandard) ForwardLazyLvl 

func (rntt NumberTheoreticTransformerStandard) ForwardLazyLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLazyLvl writes the forward NTT in Z[X]/(X^N+1) of p1 on p2. Only computes the NTT for the first level+1 moduli and returns values in the range [0, 2q-1].

func (NumberTheoreticTransformerStandard) ForwardLazyVec 

func (rntt NumberTheoreticTransformerStandard) ForwardLazyVec(r *Ring, level int, p1, p2 []uint64)

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

func (NumberTheoreticTransformerStandard) ForwardLvl 

func (rntt NumberTheoreticTransformerStandard) ForwardLvl(r *Ring, level int, p1, p2 *Poly)

ForwardLvl writes the forward NTT in Z[X]/(X^N+1) of p1 on p2. Only computes the NTT for the first level+1 moduli.

func (NumberTheoreticTransformerStandard) ForwardVec 

func (rntt NumberTheoreticTransformerStandard) ForwardVec(r *Ring, level int, p1, p2 []uint64)

ForwardVec writes the forward NTT in Z[X]/(X^N+1) of the i-th level of p1 on the i-th level of p2.

type Parameters 

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

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

type Poly 

type Poly struct {
	Coeffs  [][]uint64 // Dimension-2 slice of coefficients (re-slice of Buff)
	Buff    []uint64   // Dimension-1 slice of coefficient
	IsNTT   bool
	IsMForm bool
}

Poly is the structure that contains the coefficients of a polynomial.

func NewPoly 

func NewPoly(N, Level int) (pol *Poly)

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

func (*Poly) Copy 

func (pol *Poly) Copy(p1 *Poly)

Copy copies the coefficients of p1 on the target polynomial. Onyl copies minLevel(pol, p1) levels. Transfers the IsNTT and IsMForm flags.

func (*Poly) CopyNew 

func (pol *Poly) CopyNew() (p1 *Poly)

CopyNew creates an exact copy of the target polynomial.

func (*Poly) CopyValues 

func (pol *Poly) CopyValues(p1 *Poly)

CopyValues copies the coefficients of p1 on the target polynomial. Onyl copies minLevel(pol, p1) levels. Expects the degree of both polynomials to be identical. Does not transfer the IsNTT and IsMForm flags.

func (*Poly) DecodePoly32 

func (pol *Poly) DecodePoly32(data []byte) (pointer int, err error)

DecodePoly32 decodes a slice of bytes in the target polynomial returns the number of bytes decoded. The method will first try to write on the buffer. If this step fails, either because the buffer isn't allocated or because it is of the wrong size, the method will allocate the correct buffer. Assumes that each coefficient is encoded on 8 bytes.

func (*Poly) DecodePoly64 

func (pol *Poly) DecodePoly64(data []byte) (pointer int, err error)

DecodePoly64 decodes a slice of bytes in the target polynomial and returns the number of bytes decoded. The method will first try to write on the buffer. If this step fails, either because the buffer isn't allocated or because it is of the wrong size, the method will allocate the correct buffer. Assumes that each coefficient is encoded on 8 bytes.

func (*Poly) Equals 

func (pol *Poly) Equals(other *Poly) bool

Equals returns true if the receiver Poly is equal to the provided other Poly. This function checks for strict equality between the polynomial coefficients (i.e., it does not consider congruence as equality within the ring like `Ring.Equals` does). Will not check if IsNTT and IsMForm flags are equal

func (*Poly) GetDataLen32 

func (pol *Poly) GetDataLen32(WithMetadata bool) (cnt int)

GetDataLen32 returns the number of bytes the polynomial will take when written to data. Assumes that each coefficient is encoded on 4 bytes. It can take into account meta data if necessary.

func (*Poly) GetDataLen64 

func (pol *Poly) GetDataLen64(WithMetadata bool) (cnt int)

GetDataLen64 returns the number of bytes the polynomial will take when written to data. Assumes that each coefficient takes 8 bytes. It can take into account meta data if necessary.

func (*Poly) Level 

func (pol *Poly) Level() int

Level returns the current number of moduli minus 1.

func (*Poly) MarshalBinary 

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

MarshalBinary encodes the target polynomial on a slice of bytes. Encodes each coefficient on 8 bytes.

func (*Poly) N 

func (pol *Poly) N() int

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

func (*Poly) Resize 

func (pol *Poly) 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 (*Poly) UnmarshalBinary 

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

UnmarshalBinary decodes a slice of byte on the target polynomial. Assumes each coefficient is encoded on 8 bytes.

func (*Poly) WriteTo32 

func (pol *Poly) WriteTo32(data []byte) (int, error)

WriteTo32 writes the given poly to the data array. Encodes each coefficient on 4 bytes. It returns the number of written bytes, and the corresponding error, if it occurred.

func (*Poly) WriteTo64 

func (pol *Poly) WriteTo64(data []byte) (int, error)

WriteTo64 writes the given poly to the data array, using 8 bytes per coefficient. It returns the number of written bytes, and the corresponding error, if it occurred.

func (*Poly) Zero 

func (pol *Poly) Zero()

Zero sets all coefficients of the target polynomial to 0.

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

	// Moduli
	Modulus []uint64

	// 2^bit_length(Qi) - 1
	Mask []uint64

	// Indicates whether NTT can be used with the current ring.
	AllowsNTT bool

	// Product of the Moduli for each level
	ModulusAtLevel []*big.Int

	// Fast reduction parameters
	BredParams [][]uint64
	MredParams []uint64

	RescaleParams [][]uint64

	//NTT Parameters
	NthRoot    uint64
	PsiMont    []uint64 //2N-th primitive root in Montgomery form
	PsiInvMont []uint64 //2N-th inverse primitive root in Montgomery form

	NttPsi    [][]uint64 //powers of the inverse of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	NttPsiInv [][]uint64 //powers of the inverse of the 2N-th primitive root in Montgomery form (in bit-reversed order)
	NttNInv   []uint64   //[N^-1] mod Qi in Montgomery form
}

Ring is a structure that keeps all the variables required to operate on a polynomial represented in this ring.

func NewRing 

func NewRing(N int, Moduli []uint64) (r *Ring, err error)

NewRing creates a new RNS Ring 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 NewRingConjugateInvariant 

func NewRingConjugateInvariant(N int, Moduli []uint64) (r *Ring, err error)

NewRingConjugateInvariant 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 NewRingFromType 

func NewRingFromType(N int, Moduli []uint64, ringType Type) (r *Ring, err error)

NewRingFromType 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 NewRingWithCustomNTT 

func NewRingWithCustomNTT(N int, Moduli []uint64, ntt NumberTheoreticTransformer, NthRoot int) (r *Ring, err error)

NewRingWithCustomNTT creates a new RNS Ring with degree N and coefficient moduli Moduli with user-defined NTT transform and primitive Nth root of unity. Moduli 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 (*Ring) Add 

func (r *Ring) Add(p1, p2, p3 *Poly)

Add adds p1 to p2 coefficient-wise and writes the result on p3.

func (*Ring) AddLvl 

func (r *Ring) AddLvl(level int, p1, p2, p3 *Poly)

AddLvl adds p1 to p2 coefficient-wise for the moduli from q_0 up to q_level and writes the result on p3.

func (*Ring) AddNoMod 

func (r *Ring) AddNoMod(p1, p2, p3 *Poly)

AddNoMod adds p1 to p2 coefficient-wise without modular reduction and writes the result on p3.

func (*Ring) AddNoModLvl 

func (r *Ring) AddNoModLvl(level int, p1, p2, p3 *Poly)

AddNoModLvl adds p1 to p2 coefficient-wise without modular reduction for the moduli from q_0 up to q_level and writes the result on p3.

func (*Ring) AddScalar 

func (r *Ring) AddScalar(p1 *Poly, scalar uint64, p2 *Poly)

AddScalar adds a scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) AddScalarBigint 

func (r *Ring) AddScalarBigint(p1 *Poly, scalar *big.Int, p2 *Poly)

AddScalarBigint adds a big.Int scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) AddScalarBigintLvl 

func (r *Ring) AddScalarBigintLvl(level int, p1 *Poly, scalar *big.Int, p2 *Poly)

AddScalarBigintLvl adds a big.Int scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) AddScalarLvl 

func (r *Ring) AddScalarLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

AddScalarLvl adds a scalar to each coefficient of p1 and writes the result on p2.

func (*Ring) BitReverse 

func (r *Ring) BitReverse(p1, p2 *Poly)

BitReverse applies a bit reverse permutation on the coefficients of p1 and writes the result on p2. In can safely be used for in-place permutation.

func (*Ring) ConjugateInvariantRing 

func (r *Ring) ConjugateInvariantRing() (*Ring, error)

ConjugateInvariantRing returns the conjugate invariant ring of the receiver ring. 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 (*Ring) DivFloorByLastModulusLvl 

func (r *Ring) DivFloorByLastModulusLvl(level int, p0, p1 *Poly)

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

func (*Ring) DivFloorByLastModulusManyLvl 

func (r *Ring) DivFloorByLastModulusManyLvl(level, nbRescales int, p0, buff, p1 *Poly)

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

func (*Ring) DivFloorByLastModulusManyNTTLvl 

func (r *Ring) DivFloorByLastModulusManyNTTLvl(level, nbRescales int, p0, buff, p1 *Poly)

DivFloorByLastModulusManyNTTLvl 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 (*Ring) DivFloorByLastModulusNTTLvl 

func (r *Ring) DivFloorByLastModulusNTTLvl(level int, p0, buff, p1 *Poly)

DivFloorByLastModulusNTTLvl 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 (*Ring) DivRoundByLastModulusLvl 

func (r *Ring) DivRoundByLastModulusLvl(level int, p0, p1 *Poly)

DivRoundByLastModulusLvl 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 (*Ring) DivRoundByLastModulusManyLvl 

func (r *Ring) DivRoundByLastModulusManyLvl(level, nbRescales int, p0, buff, p1 *Poly)

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

func (*Ring) DivRoundByLastModulusManyNTTLvl 

func (r *Ring) DivRoundByLastModulusManyNTTLvl(level, nbRescales int, p0, buff, p1 *Poly)

DivRoundByLastModulusManyNTTLvl 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 (*Ring) DivRoundByLastModulusNTTLvl 

func (r *Ring) DivRoundByLastModulusNTTLvl(level int, p0, buff, p1 *Poly)

DivRoundByLastModulusNTTLvl 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 (*Ring) Equal 

func (r *Ring) Equal(p1, p2 *Poly) bool

Equal checks if p1 = p2 in the given Ring.

func (*Ring) EqualLvl 

func (r *Ring) EqualLvl(level int, p1, p2 *Poly) bool

EqualLvl checks if p1 = p2 in the given Ring, up to a given level.

func (*Ring) EvalPolyScalar 

func (r *Ring) EvalPolyScalar(pol []*Poly, scalar uint64, pOut *Poly)

EvalPolyScalar evaluate the polynomial pol at pk and writes the result in p3

func (*Ring) FoldStandardToConjugateInvariant 

func (r *Ring) FoldStandardToConjugateInvariant(level int, polyStandard *Poly, permuteNTTIndexInv []uint64, polyConjugateInvariant *Poly)

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

func (*Ring) InvMForm 

func (r *Ring) InvMForm(p1, p2 *Poly)

InvMForm switches back p1 from the Montgomery domain to the conventional domain and writes the result on p2.

func (*Ring) InvMFormLvl 

func (r *Ring) InvMFormLvl(level int, p1, p2 *Poly)

InvMFormLvl switches back p1 from the Montgomery domain to the conventional domain and writes the result on p2.

func (*Ring) InvNTT 

func (r *Ring) InvNTT(p1, p2 *Poly)

InvNTT computes the inverse-NTT of p1 and returns the result on p2.

func (*Ring) InvNTTLazy 

func (r *Ring) InvNTTLazy(p1, p2 *Poly)

InvNTTLazy computes the inverse-NTT of p1 and returns the result on p2. Output values are in the range [0, 2q-1]

func (*Ring) InvNTTLazyLvl 

func (r *Ring) InvNTTLazyLvl(level int, p1, p2 *Poly)

InvNTTLazyLvl computes the inverse-NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials. Output values are in the range [0, 2q-1]

func (*Ring) InvNTTLvl 

func (r *Ring) InvNTTLvl(level int, p1, p2 *Poly)

InvNTTLvl computes the inverse-NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials.

func (*Ring) InvNTTSingle 

func (r *Ring) InvNTTSingle(level int, p1, p2 []uint64)

InvNTTSingle computes the InvNTT of p1 and returns the result on p2. The level-th moduli of the ring InvNTT params are used. Only computes the InvNTT for the i-th level.

func (*Ring) InvNTTSingleLazy 

func (r *Ring) InvNTTSingleLazy(level int, p1, p2 []uint64)

InvNTTSingleLazy computes the InvNTT of p1 and returns the result on p2. The level-th moduli of the ring InvNTT params are used. Output values are in the range [0, 2q-1]

func (*Ring) Inverse 

func (r *Ring) 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 (*Ring) Log2OfInnerSum 

func (r *Ring) Log2OfInnerSum(level int, poly *Poly) (logSum int)

Log2OfInnerSum returns the bit-size of the sum of all the coefficients (in absolute value) of a Poly.

func (*Ring) MForm 

func (r *Ring) MForm(p1, p2 *Poly)

MForm switches p1 to the Montgomery domain and writes the result on p2.

func (*Ring) MFormConstantLvl 

func (r *Ring) MFormConstantLvl(level int, p1, p2 *Poly)

MFormConstantLvl switches p1 to the Montgomery domain for the moduli from q_0 up to q_level and writes the result on p2. Result is in the range [0, 2q-1]

func (*Ring) MFormLvl 

func (r *Ring) MFormLvl(level int, p1, p2 *Poly)

MFormLvl switches p1 to the Montgomery domain for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MarshalBinary 

func (r *Ring) MarshalBinary() ([]byte, error)

MarshalBinary encodes the target ring on a slice of bytes.

func (*Ring) Mod 

func (r *Ring) Mod(p1 *Poly, m uint64, p2 *Poly)

Mod applies a modular reduction by m on the coefficients of p1 and writes the result on p2.

func (*Ring) ModLvl 

func (r *Ring) ModLvl(level int, p1 *Poly, m uint64, p2 *Poly)

ModLvl applies a modular reduction by m on the coefficients of p1 and writes the result on p2.

func (*Ring) MulByPow2 

func (r *Ring) MulByPow2(p1 *Poly, pow2 int, p2 *Poly)

MulByPow2 multiplies p1 by 2^pow2 and writes the result on p2.

func (*Ring) MulByPow2Lvl 

func (r *Ring) MulByPow2Lvl(level int, p1 *Poly, pow2 int, p2 *Poly)

MulByPow2Lvl multiplies p1 by 2^pow2 for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MulByPow2New 

func (r *Ring) MulByPow2New(p1 *Poly, pow2 int) (p2 *Poly)

MulByPow2New multiplies p1 by 2^pow2 and returns the result in a new polynomial p2.

func (*Ring) MulByVectorMontgomery 

func (r *Ring) MulByVectorMontgomery(p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomery multiplies p1 by a vector of uint64 coefficients and writes the result on p2.

func (*Ring) MulByVectorMontgomeryAndAddNoMod 

func (r *Ring) MulByVectorMontgomeryAndAddNoMod(p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomeryAndAddNoMod multiplies p1 by a vector of uint64 coefficients and adds the result on p2 without modular reduction.

func (*Ring) MulByVectorMontgomeryAndAddNoModLvl 

func (r *Ring) MulByVectorMontgomeryAndAddNoModLvl(level int, p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomeryAndAddNoModLvl multiplies p1 by a vector of uint64 coefficients and adds the result on p2 without modular reduction.

func (*Ring) MulByVectorMontgomeryLvl 

func (r *Ring) MulByVectorMontgomeryLvl(level int, p1 *Poly, vector []uint64, p2 *Poly)

MulByVectorMontgomeryLvl multiplies p1 by a vector of uint64 coefficients and writes the result on p2.

func (*Ring) MulCoeffs 

func (r *Ring) MulCoeffs(p1, p2, p3 *Poly)

MulCoeffs multiplies p1 by p2 coefficient-wise, performs a Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsAndAdd 

func (r *Ring) MulCoeffsAndAdd(p1, p2, p3 *Poly)

MulCoeffsAndAdd multiplies p1 by p2 coefficient-wise with a Barret modular reduction and adds the result to p3.

func (*Ring) MulCoeffsAndAddLvl 

func (r *Ring) MulCoeffsAndAddLvl(level int, p1, p2, p3 *Poly)

MulCoeffsAndAddLvl multiplies p1 by p2 coefficient-wise with a Barret modular reduction and adds the result to p3.

func (*Ring) MulCoeffsAndAddNoMod 

func (r *Ring) MulCoeffsAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsAndAddNoMod multiplies p1 by p2 coefficient-wise with a Barrett modular reduction and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsAndAddNoModLvl 

func (r *Ring) MulCoeffsAndAddNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsAndAddNoModLvl multiplies p1 by p2 coefficient-wise with a Barrett modular reduction and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsConstant 

func (r *Ring) MulCoeffsConstant(p1, p2, p3 *Poly)

MulCoeffsConstant multiplies p1 by p2 coefficient-wise with a constant-time Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsConstantLvl 

func (r *Ring) MulCoeffsConstantLvl(level int, p1, p2, p3 *Poly)

MulCoeffsConstantLvl multiplies p1 by p2 coefficient-wise with a constant-time Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsLvl 

func (r *Ring) MulCoeffsLvl(level int, p1, p2, p3 *Poly)

MulCoeffsLvl multiplies p1 by p2 coefficient-wise, performs a Barrett modular reduction and writes the result on p3.

func (*Ring) MulCoeffsMontgomery 

func (r *Ring) MulCoeffsMontgomery(p1, p2, p3 *Poly)

MulCoeffsMontgomery multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and returns the result on p3.

func (*Ring) MulCoeffsMontgomeryAndAdd 

func (r *Ring) MulCoeffsMontgomeryAndAdd(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAdd multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and adds the result to p3.

func (*Ring) MulCoeffsMontgomeryAndAddLvl 

func (r *Ring) MulCoeffsMontgomeryAndAddLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAddLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and adds the result to p3.

func (*Ring) MulCoeffsMontgomeryAndAddNoMod 

func (r *Ring) MulCoeffsMontgomeryAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAddNoMod multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryAndAddNoModLvl 

func (r *Ring) MulCoeffsMontgomeryAndAddNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAddNoModLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and adds the result to p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryAndSub 

func (r *Ring) MulCoeffsMontgomeryAndSub(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSub multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3.

func (*Ring) MulCoeffsMontgomeryAndSubLvl 

func (r *Ring) MulCoeffsMontgomeryAndSubLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSubLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3.

func (*Ring) MulCoeffsMontgomeryAndSubNoMod 

func (r *Ring) MulCoeffsMontgomeryAndSubNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSubNoMod multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryAndSubNoModLvl 

func (r *Ring) MulCoeffsMontgomeryAndSubNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSubNoModLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3 without modular reduction.

func (*Ring) MulCoeffsMontgomeryConstant 

func (r *Ring) MulCoeffsMontgomeryConstant(p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstant multiplies p1 by p2 coefficient-wise with a constant-time Montgomery modular reduction and writes the result on p3.

func (*Ring) MulCoeffsMontgomeryConstantAndAddNoMod 

func (r *Ring) MulCoeffsMontgomeryConstantAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndAddNoMod multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and adds the result to p3 without modular reduction. Return values in [0, 3q-1]

func (*Ring) MulCoeffsMontgomeryConstantAndAddNoModLvl 

func (r *Ring) MulCoeffsMontgomeryConstantAndAddNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndAddNoModLvl multiplies p1 by p2 coefficient-wise with a constant-time Montgomery modular reduction for the moduli from q_0 up to q_level and adds the result to p3 without modular reduction. Return values in [0, 3q-1]

func (*Ring) MulCoeffsMontgomeryConstantAndNegLvl 

func (r *Ring) MulCoeffsMontgomeryConstantAndNegLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndNegLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and returns the negative result on p3.

func (*Ring) MulCoeffsMontgomeryConstantAndSubNoModLvl 

func (r *Ring) MulCoeffsMontgomeryConstantAndSubNoModLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantAndSubNoModLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction and subtracts the result from p3 without modular reduction. Return values in [0, 3q-1]

func (*Ring) MulCoeffsMontgomeryConstantLvl 

func (r *Ring) MulCoeffsMontgomeryConstantLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryConstantLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and returns the result on p3.

func (*Ring) MulCoeffsMontgomeryLvl 

func (r *Ring) MulCoeffsMontgomeryLvl(level int, p1, p2, p3 *Poly)

MulCoeffsMontgomeryLvl multiplies p1 by p2 coefficient-wise with a Montgomery modular reduction for the moduli from q_0 up to q_level and returns the result on p3.

func (*Ring) MulRNSScalar 

func (r *Ring) MulRNSScalar(s1, s2, sout RNSScalar)

MulRNSScalar multiplies s1 and s2 and stores the result in sout.

func (*Ring) MulRNSScalarMontgomery 

func (r *Ring) MulRNSScalarMontgomery(p *Poly, scalar RNSScalar, pOut *Poly)

MulRNSScalarMontgomery multiplies p with a scalar value expressed in the RNS representation. It assumes the scalar to be decomposed in the RNS basis of the ring r and its coefficients to be in Montgomery form.

func (*Ring) MulRNSScalarMontgomeryLvl 

func (r *Ring) MulRNSScalarMontgomeryLvl(level int, p *Poly, scalar RNSScalar, pOut *Poly)

MulRNSScalarMontgomeryLvl multiplies p with a scalar value expressed in the CRT decomposition at a given level. It assumes the scalar decomposition to be in Montgomery form.

func (*Ring) MulScalar 

func (r *Ring) MulScalar(p1 *Poly, scalar uint64, p2 *Poly)

MulScalar multiplies each coefficient of p1 by a scalar and writes the result on p2.

func (*Ring) MulScalarAndAdd 

func (r *Ring) MulScalarAndAdd(p1 *Poly, scalar uint64, p2 *Poly)

MulScalarAndAdd multiplies each coefficient of p1 by a scalar and adds the result on p2.

func (*Ring) MulScalarAndAddLvl 

func (r *Ring) MulScalarAndAddLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

MulScalarAndAddLvl multiplies each coefficient of p1 by a scalar for the moduli from q_0 up to q_level and adds the result on p2.

func (*Ring) MulScalarAndSub 

func (r *Ring) MulScalarAndSub(p1 *Poly, scalar uint64, p2 *Poly)

MulScalarAndSub multiplies each coefficient of p1 by a scalar and subtracts the result on p2.

func (*Ring) MulScalarAndSubLvl 

func (r *Ring) MulScalarAndSubLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

MulScalarAndSubLvl multiplies each coefficient of p1 by a scalar for the moduli from q_0 up to q_level and subtracts the result on p2.

func (*Ring) MulScalarBigint 

func (r *Ring) MulScalarBigint(p1 *Poly, scalar *big.Int, p2 *Poly)

MulScalarBigint multiplies each coefficient of p1 by a big.Int scalar and writes the result on p2.

func (*Ring) MulScalarBigintLvl 

func (r *Ring) MulScalarBigintLvl(level int, p1 *Poly, scalar *big.Int, p2 *Poly)

MulScalarBigintLvl multiplies each coefficient of p1 by a big.Int scalar for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MulScalarLvl 

func (r *Ring) MulScalarLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

MulScalarLvl multiplies each coefficient of p1 by a scalar for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) MultByMonomial 

func (r *Ring) MultByMonomial(p1 *Poly, monomialDeg int, p2 *Poly)

MultByMonomial multiplies p1 by x^monomialDeg and writes the result on p2.

func (*Ring) MultByMonomialNew 

func (r *Ring) MultByMonomialNew(p1 *Poly, monomialDeg int) (p2 *Poly)

MultByMonomialNew multiplies p1 by x^monomialDeg and writes the result on a new polynomial p2.

func (*Ring) NTT 

func (r *Ring) NTT(p1, p2 *Poly)

NTT computes the NTT of p1 and returns the result on p2.

func (*Ring) NTTLazy 

func (r *Ring) NTTLazy(p1, p2 *Poly)

NTTLazy computes the NTT of p1 and returns the result on p2. Output values are in the range [0, 2q-1]

func (*Ring) NTTLazyLvl 

func (r *Ring) NTTLazyLvl(level int, p1, p2 *Poly)

NTTLazyLvl computes the NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials. Output values are in the range [0, 2q-1]

func (*Ring) NTTLvl 

func (r *Ring) NTTLvl(level int, p1, p2 *Poly)

NTTLvl computes the NTT of p1 and returns the result on p2. The value level defines the number of moduli of the input polynomials.

func (*Ring) NTTSingle 

func (r *Ring) NTTSingle(level int, p1, p2 []uint64)

NTTSingle computes the NTT of p1 and returns the result on p2. The level-th moduli of the ring NTT params are used.

func (*Ring) NTTSingleLazy 

func (r *Ring) NTTSingleLazy(level int, p1, p2 []uint64)

NTTSingleLazy computes the NTT of p1 and returns the result on p2. The level-th moduli of the ring NTT params are used. Output values are in the range [0, 2q-1]

func (*Ring) Neg 

func (r *Ring) Neg(p1, p2 *Poly)

Neg sets all coefficients of p1 to their additive inverse and writes the result on p2.

func (*Ring) NegLvl 

func (r *Ring) NegLvl(level int, p1, p2 *Poly)

NegLvl sets the coefficients of p1 to their additive inverse for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) NewPoly 

func (r *Ring) NewPoly() *Poly

NewPoly creates a new polynomial with all coefficients set to 0.

func (*Ring) NewPolyLvl 

func (r *Ring) NewPolyLvl(level int) *Poly

NewPolyLvl creates a new polynomial with all coefficients set to 0.

func (*Ring) NewRNSScalar 

func (r *Ring) NewRNSScalar() RNSScalar

NewRNSScalar creates a new Scalar value.

func (*Ring) NewRNSScalarFromUInt64 

func (r *Ring) NewRNSScalarFromUInt64(v uint64) RNSScalar

NewRNSScalarFromUInt64 creates a new Scalar initialized with value v.

func (*Ring) Permute 

func (r *Ring) Permute(polIn *Poly, gen uint64, polOut *Poly)

Permute applies the Galois transform on a polynomial outside of the NTT domain. It maps the coefficients x^i to x^(gen*i). It must be noted that the result cannot be in-place.

func (*Ring) PermuteLvl 

func (r *Ring) PermuteLvl(level int, polIn *Poly, gen uint64, polOut *Poly)

PermuteLvl applies the Galois transform on a polynomial outside of the NTT domain. It maps the coefficients x^i to x^(gen*i). It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTT 

func (r *Ring) PermuteNTT(polIn *Poly, gen uint64, polOut *Poly)

PermuteNTT applies the Galois transform on a polynomial in the NTT domain. It maps the coefficients x^i to x^(gen*i) It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTTIndex 

func (r *Ring) PermuteNTTIndex(galEl uint64) (index []uint64)

PermuteNTTIndex computes the index table for PermuteNTT.

func (*Ring) PermuteNTTLvl 

func (r *Ring) PermuteNTTLvl(level int, polIn *Poly, gen uint64, polOut *Poly)

PermuteNTTLvl applies the Galois transform on a polynomial in the NTT domain, up to a given level. It maps the coefficients x^i to x^(gen*i) It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTTWithIndexAndAddNoModLvl 

func (r *Ring) PermuteNTTWithIndexAndAddNoModLvl(level int, polIn *Poly, index []uint64, polOut *Poly)

PermuteNTTWithIndexAndAddNoModLvl applies the Galois transform on a polynomial in the NTT domain, up to a given level, and adds the result to the output polynomial without modular reduction. It maps the coefficients x^i to x^(gen*i) using the PermuteNTTIndex table. It must be noted that the result cannot be in-place.

func (*Ring) PermuteNTTWithIndexLvl 

func (r *Ring) PermuteNTTWithIndexLvl(level int, polIn *Poly, index []uint64, polOut *Poly)

PermuteNTTWithIndexLvl applies the Galois transform on a polynomial in the NTT domain, up to a given level. It maps the coefficients x^i to x^(gen*i) using the PermuteNTTIndex table. It must be noted that the result cannot be in-place.

func (*Ring) PolyToBigint 

func (r *Ring) PolyToBigint(p1 *Poly, 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 (*Ring) PolyToBigintCenteredLvl 

func (r *Ring) PolyToBigintCenteredLvl(level int, p1 *Poly, gap int, coeffsBigint []*big.Int)

PolyToBigintCenteredLvl 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 (*Ring) PolyToBigintLvl 

func (r *Ring) PolyToBigintLvl(level int, p1 *Poly, gap int, coeffsBigint []*big.Int)

PolyToBigintLvl 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 (*Ring) PolyToString 

func (r *Ring) PolyToString(p1 *Poly) []string

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

func (*Ring) Reduce 

func (r *Ring) Reduce(p1, p2 *Poly)

Reduce applies a modular reduction on the coefficients of p1 and writes the result on p2.

func (*Ring) ReduceConstant 

func (r *Ring) ReduceConstant(p1, p2 *Poly)

ReduceConstant applies a modular reduction on the coefficients of p1 and writes the result on p2. Return values in [0, 2q-1]

func (*Ring) ReduceConstantLvl 

func (r *Ring) ReduceConstantLvl(level int, p1, p2 *Poly)

ReduceConstantLvl applies a modular reduction on the coefficients of p1 for the moduli from q_0 up to q_level and writes the result on p2. Return values in [0, 2q-1]

func (*Ring) ReduceLvl 

func (r *Ring) ReduceLvl(level int, p1, p2 *Poly)

ReduceLvl applies a modular reduction on the coefficients of p1 for the moduli from q_0 up to q_level and writes the result on p2.

func (*Ring) SetCoefficientsBigint 

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

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

func (*Ring) SetCoefficientsBigintLvl 

func (r *Ring) SetCoefficientsBigintLvl(level int, coeffs []*big.Int, p1 *Poly)

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

func (*Ring) SetCoefficientsInt64 

func (r *Ring) SetCoefficientsInt64(coeffs []int64, p1 *Poly)

SetCoefficientsInt64 sets the coefficients of p1 from an int64 array.

func (*Ring) SetCoefficientsString 

func (r *Ring) SetCoefficientsString(coeffs []string, p1 *Poly)

SetCoefficientsString parses an array of string as Int variables, and sets the coefficients of p1 with these Int variables.

func (*Ring) SetCoefficientsUint64 

func (r *Ring) SetCoefficientsUint64(coeffs []uint64, p1 *Poly)

SetCoefficientsUint64 sets the coefficients of p1 from an uint64 array.

func (*Ring) Shift 

func (r *Ring) Shift(p1 *Poly, k int, p2 *Poly)

Shift circularly shifts the coefficients of the polynomial p1 by k positions to the left and writes the result on p2.

func (*Ring) StandardRing 

func (r *Ring) StandardRing() (*Ring, error)

StandardRing returns the standard ring of the receiver ring. 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 (*Ring) Sub 

func (r *Ring) Sub(p1, p2, p3 *Poly)

Sub subtracts p2 to p1 coefficient-wise and writes the result on p3.

func (*Ring) SubLvl 

func (r *Ring) SubLvl(level int, p1, p2, p3 *Poly)

SubLvl subtracts p2 to p1 coefficient-wise and writes the result on p3.

func (*Ring) SubNoMod 

func (r *Ring) SubNoMod(p1, p2, p3 *Poly)

SubNoMod subtracts p2 to p1 coefficient-wise without modular reduction and returns the result on p3.

func (*Ring) SubNoModLvl 

func (r *Ring) SubNoModLvl(level int, p1, p2, p3 *Poly)

SubNoModLvl subtracts p2 to p1 coefficient-wise without modular reduction for the moduli from q_0 up to q_level and writes the result on p3.

func (*Ring) SubRNSScalar 

func (r *Ring) SubRNSScalar(s1, s2, sout RNSScalar)

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

func (*Ring) SubScalar 

func (r *Ring) SubScalar(p1 *Poly, scalar uint64, p2 *Poly)

SubScalar subtracts a scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) SubScalarBigint 

func (r *Ring) SubScalarBigint(p1 *Poly, scalar *big.Int, p2 *Poly)

SubScalarBigint subtracts a big.Int scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) SubScalarBigintLvl 

func (r *Ring) SubScalarBigintLvl(level int, p1 *Poly, scalar *big.Int, p2 *Poly)

SubScalarBigintLvl subtracts a big.Int scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) SubScalarLvl 

func (r *Ring) SubScalarLvl(level int, p1 *Poly, scalar uint64, p2 *Poly)

SubScalarLvl subtracts a scalar from each coefficient of p1 and writes the result on p2.

func (*Ring) Type 

func (r *Ring) Type() Type

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

func (*Ring) UnfoldConjugateInvariantToStandard 

func (r *Ring) UnfoldConjugateInvariantToStandard(level int, polyConjugateInvariant, polyStd *Poly)

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(polyStd). Requires that polyStd and polyConjugateInvariant share the same moduli.

func (*Ring) UnmarshalBinary 

func (r *Ring) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes a slice of bytes on the target Ring.

type Sampler 

type Sampler interface {
	Read(pOut *Poly)
}

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.

type TernarySampler 

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

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

func NewTernarySampler 

func NewTernarySampler(prng utils.PRNG, baseRing *Ring, p float64, montgomery bool) *TernarySampler

NewTernarySampler creates a new instance of TernarySampler from a PRNG, the ring definition and the distribution parameters: p is the probability of a coefficient being 0, (1-p)/2 is the probability of 1 and -1. If "montgomery" is set to true, polynomials read from this sampler are in Montgomery form.

func NewTernarySamplerWithHammingWeight 

func NewTernarySamplerWithHammingWeight(prng utils.PRNG, baseRing *Ring, hw int, montgomery bool) *TernarySampler

NewTernarySamplerWithHammingWeight creates a new instance of a fixed-hamming-weight TernarySampler from a PRNG, the ring definition and the desired hamming weight for the output polynomials. If "montgomery" is set to true, polynomials read from this sampler are in Montgomery form.

func (*TernarySampler) Read 

func (ts *TernarySampler) Read(pol *Poly)

Read samples a polynomial into pol.

func (*TernarySampler) ReadLvl 

func (ts *TernarySampler) ReadLvl(lvl int, pol *Poly)

ReadLvl samples a polynomial into pol at the speciefied level.

func (*TernarySampler) ReadLvlNew 

func (ts *TernarySampler) ReadLvlNew(lvl int) (pol *Poly)

ReadLvlNew allocates and samples a polynomial at the speficied level.

func (*TernarySampler) ReadNew 

func (ts *TernarySampler) ReadNew() (pol *Poly)

ReadNew allocates and samples a polynomial at the max level.

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 UniformSampler 

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

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

func NewUniformSampler 

func NewUniformSampler(prng utils.PRNG, baseRing *Ring) *UniformSampler

NewUniformSampler creates a new instance of UniformSampler from a PRNG and ring definition.

func (*UniformSampler) Read 

func (uniformSampler *UniformSampler) Read(Pol *Poly)

Read generates a new polynomial with coefficients following a uniform distribution over [0, Qi-1].

func (*UniformSampler) ReadLvl 

func (uniformSampler *UniformSampler) ReadLvl(level int, Pol *Poly)

ReadLvl generates a new polynomial with coefficients following a uniform distribution over [0, Qi-1].

func (*UniformSampler) ReadLvlNew 

func (uniformSampler *UniformSampler) ReadLvlNew(level int) (Pol *Poly)

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

func (*UniformSampler) ReadNew 

func (uniformSampler *UniformSampler) ReadNew() (Pol *Poly)

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

func (*UniformSampler) WithPRNG 

func (uniformSampler *UniformSampler) WithPRNG(prng utils.PRNG) *UniformSampler

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.