ring

package
v1.1.0 Latest Latest
Warning

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

 Go to latest Published: Oct 1, 2019 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Overview

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

Index

Constants

This section is empty.

Variables

View Source 
var Pi60 = []uint64{576460752308273153, 576460752315482113, 576460752319021057, 576460752319414273, 576460752321642497,
	576460752325705729, 576460752328327169, 576460752329113601, 576460752329506817, 576460752329900033,
	576460752331210753, 576460752337502209, 576460752340123649, 576460752342876161, 576460752347201537,
	576460752347332609, 576460752352837633, 576460752354017281, 576460752355065857, 576460752355459073,
	576460752358604801, 576460752364240897, 576460752368435201, 576460752371187713, 576460752373547009,
	576460752374333441, 576460752376692737, 576460752378003457, 576460752378396673, 576460752380755969,
	576460752381411329, 576460752386129921, 576460752395173889, 576460752395960321, 576460752396091393,
	576460752396484609, 576460752399106049, 576460752405135361, 576460752405921793, 576460752409722881,
	576460752410116097, 576460752411033601, 576460752412082177, 576460752416145409, 576460752416931841,
	576460752421257217, 576460752427548673, 576460752429514753, 576460752435281921, 576460752437248001,
	576460752438558721, 576460752441966593, 576460752449044481, 576460752451141633, 576460752451534849,
	576460752462938113, 576460752465952769, 576460752468705281, 576460752469491713, 576460752472375297,
	576460752473948161, 576460752475389953, 576460752480894977, 576460752483254273, 576460752484827137,
	576460752486793217, 576460752486924289, 576460752492691457, 576460752498589697, 576460752498720769,
	576460752499507201, 576460752504225793, 576460752505405441, 576460752507240449, 576460752507764737,
	576460752509206529, 576460752510124033, 576460752510779393, 576460752511959041, 576460752514449409,
	576460752516284417, 576460752519168001, 576460752520347649, 576460752520609793, 576460752522969089,
	576460752523100161, 576460752524279809, 576460752525852673, 576460752526245889, 576460752526508033,
	576460752532013057, 576460752545120257, 576460752550100993, 576460752551804929, 576460752567402497,
	576460752568975361, 576460752573431809, 576460752580902913, 576460752585490433, 576460752586407937}

First hundred (from 0x800000000000000 and upward) 60bit Primes allowing ǸTT for N = 65536

View Source 
var Qi60 = []uint64{1152921504606584833, 1152921504598720513, 1152921504592429057, 1152921504581419009, 1152921504580894721,
	1152921504578273281, 1152921504577748993, 1152921504577486849, 1152921504568836097, 1152921504565166081,
	1152921504563331073, 1152921504556515329, 1152921504555466753, 1152921504554156033, 1152921504552583169,
	1152921504542883841, 1152921504538951681, 1152921504537378817, 1152921504531873793, 1152921504521650177,
	1152921504509853697, 1152921504508280833, 1152921504506970113, 1152921504495697921, 1152921504491241473,
	1152921504488620033, 1152921504479444993, 1152921504470794241, 1152921504468172801, 1152921504462929921,
	1152921504462667777, 1152921504455589889, 1152921504447987713, 1152921504442482689, 1152921504436191233,
	1152921504427278337, 1152921504419414017, 1152921504409190401, 1152921504403947521, 1152921504396869633,
	1152921504395821057, 1152921504373014529, 1152921504369344513, 1152921504368558081, 1152921504364625921,
	1152921504362790913, 1152921504361218049, 1152921504353615873, 1152921504337887233, 1152921504337625089,
	1152921504321372161, 1152921504314032129, 1152921504303022081, 1152921504301449217, 1152921504288342017,
	1152921504287293441, 1152921504286769153, 1152921504282836993, 1152921504274972673, 1152921504266321921,
	1152921504256622593, 1152921504253739009, 1152921504245088257, 1152921504241942529, 1152921504240107521,
	1152921504239583233, 1152921504238010369, 1152921504234078209, 1152921504231718913, 1152921504230670337,
	1152921504227524609, 1152921504214417409, 1152921504207339521, 1152921504205504513, 1152921504204193793,
	1152921504190824449, 1152921504179552257, 1152921504177192961, 1152921504176668673, 1152921504174309377,
	1152921504172474369, 1152921504164872193, 1152921504162512897, 1152921504139706369, 1152921504134987777,
	1152921504132628481, 1152921504122142721, 1152921504120832001, 1152921504116899841, 1152921504105627649,
	1152921504101957633, 1152921504100384769, 1152921504096452609, 1152921504093306881, 1152921504078364673,
	1152921504067092481, 1152921504066306049, 1152921504057917441, 1152921504053723137, 1152921504050839553}

Last hundred (from 0xfffffffffffffff and downward) 60bit Primes allowing ǸTT for N = 65536

Functions

func BRed 

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

BRed compute a*b mod q for arbitrary a,b uint64. To be used when both a,b can not be pre-computed. However applying a montgomery transform on either a or b might be faster depending on the computation to do, especially if either a or b need to be multiplied with several other values.

func BRedAdd 

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

BRedAdd reduces a 64 bit integer by q. Assumes that x <= 64bits. Useful when several additions are performed before a modular reduction, as it is faster than applying a conditional reduction after each addition.

func BRedAddConstant 

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

BRedAddConstant is indentical to BReAdd, except it runs in constant time and returns a value in [0, 2q-1].

func BRedConstant 

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

BRedConstant is indentical to BRed, except it runs in constant time and returns a value in [0, 2q-1].

func BRedParams 

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

BRedParams computes the parameters required for the BRed with a radix of 2^128.

func Butterfly 

func Butterfly(U, V, Psi, Q, Qinv uint64) (X, Y uint64)

Buttefly computes X, Y = U + V*Psi, U - V*Psi mod Q.

func CRed 

func CRed(a, q uint64) uint64

CRed reduce returns a mod q, where a is required to be in the range [0, 2q-1].

func DecodeCoeffs 

func DecodeCoeffs(pointer, N, numberModuli uint64, coeffs [][]uint64, data []byte) (uint64, error)

DecodeCoeffs converts a byte array to a matrix of coefficients.

func DecodeCoeffsNew added in v1.1.0 

func DecodeCoeffsNew(pointer, N, numberModuli uint64, coeffs [][]uint64, data []byte) (uint64, error)

DecodeCoeffs converts a byte array to a matrix of coefficients.

func Float128ToUint53 

func Float128ToUint53(f Float128) uint64

Float128ToUint53 returns the uint64 value from 128-bit floating point object rounded down. To be used if the result of the computation is under 53 bits.

func Float128ToUint64 

func Float128ToUint64(f Float128) uint64

Float128ToUint64 reconstructs an uint64 integer from a Float128 that was imported with the Float128SetUint64() function. Isolates the integer part from the floatting point part, then adds the rounded floating point part to the integer part (this prevents occasional rounding errors when the second floating element is negative). The value need to be scaled by 1/4096 to be reconstructed correctly.

func GenerateNTTPrimes 

func GenerateNTTPrimes(N, start, n, bitLen uint64, sign bool) ([]uint64, error)

GenerateNTTPrimes generates "n" primes of bitlen "bitLen", stuited for NTT with "N", starting from the integer "start" (which must be 1 mod 2N) and increasing (true) / decreasing (false) order

func InvButterfly 

func InvButterfly(U, V, Psi, Q, Qinv uint64) (X, Y uint64)

InvButterfly computes X, Y = U + V, (U - V) * Psi mod Q.

func InvMForm 

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

InvMForm returns a*(1/2^64) mod q. It takes the input a in montgomery form mod q with a radix of 2^ 64and returns r which is the normal form of a mod q.

func InvMFormConstant 

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

InvMFormConstant is indentical to InvMForm, except that it runs in constant time and returns a value in [0, 2q-1].

func InvNTT 

func InvNTT(coeffs_in, coeffs_out []uint64, N uint64, nttPsiInv []uint64, nttNInv, Q, mredParams uint64)

InvNTT computes the InvNTT transformation on the input coefficients given the provided params.

func IsPrime 

func IsPrime(num uint64) bool

=========================== === MILLER-RABIN === =========================== IsPrime applies a Miller-Rabin test on the given uint64 variable, returning true if num is probably prime, else false.

func MForm 

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

MForm returns a*2^64 mod q. It take thes input a in conventional form and return r which is the the montgomery form of a of a mod q with a radix of 2^64.

func MFormConstant 

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

MFormConstant is identical to MForm, except that it runs in constant time and returns a value in [0, 2q-1] (it omits the conditional reduction).

func MRed 

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

MRed computes x * y * (1/2^64) mod q. Requires that at least one of the inputs is in montgomery form. If only one of the inputs is in montgomery form (ex : a pre-computed constant), the result will be in normal form. If both inputs are in montgomery form, then the result will be in montgomery form.

func MRedConstant 

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

MRedConstant is identical to MRed except it runs in constant time and returns a value in [0, 2q-1].

func MRedParams 

func MRedParams(q uint64) (qInv uint64)

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

func ModExp 

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

Modexp performes the modular exponentiation x^e mod p, x and p are required to be a most 64 bits to avoid an overflow.

func NTT 

func NTT(coeffs_in, coeffs_out []uint64, N uint64, nttPsi []uint64, Q, mredParams uint64, bredParams []uint64)

NTT computes the NTT transformation on the input coefficients given the provided params.

func PermuteNTT 

func 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) Careful, not inplace!

func PowerOf2 

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

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

func RandUniform 

func RandUniform(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 WriteCoeffsTo 

func WriteCoeffsTo(pointer, N, numberModuli uint64, coeffs [][]uint64, data []byte) (uint64, error)

WriteCoeffsTo converts a matrix of coefficients to a byte array.

Types

type BasisExtender 

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

BasisExtender is the structure keeping all the pre-computed constant required to apply a basis extendion of a polynomial in basis Q to a polynomial in basis Q + P Algorithm from https://eprint.iacr.org/2018/117.pdf

func NewBasisExtender 

func NewBasisExtender(contextQ, contextP *Context) (newParams *BasisExtender)

NewBasisExtender creates a new BasisExtender, that will be used to extend a polynomial in basis Q to a polynomial in basis Q + P.

func (*BasisExtender) ExtendBasis 

func (Parameters *BasisExtender) ExtendBasis(p1, p2 *Poly)

ExtendBasis extends the basis of a polynomial from Q to Q + P. Given a polynomial with coefficients in basis {Q0,Q1....Qi} Extends its basis from {Q0,Q1....Qi} to {Q0,Q1....Qi,P0,P1...Pj}

func (*BasisExtender) ExtendBasisApproximate 

func (Parameters *BasisExtender) ExtendBasisApproximate(p1, p2 *Poly)

ExtendBasisApproximate approximates the basis extension (returns the value + some multiple of Q (equal to the correction term v) in the basis QP) The algorithm is identical to the ExtendBasis, except it doesn't make use of the correction term v that removes the additional multiplie of Q introduced during the basis extension in the new basis P.

type ComplexScaler 

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

ComplexScaler is the structure holding the parameters for the complex scaling, which is the operation of reducing a polynomial in basis Q + P to a polynomial in basis Q while at the same time rescaling it by a factor t/Q. Algorithm from https://eprint.iacr.org/2018/117.pdf

func NewComplexScaler 

func NewComplexScaler(t uint64, contextQ, contextP *Context) (newParams *ComplexScaler)

NewComplexScaler creates a new ComplexScaler from t and the provided contexts.

func (*ComplexScaler) Scale 

func (parameters *ComplexScaler) Scale(p1, p2 *Poly)

Scale takes a polynomial in basis {Q0,Q1....Qi,P0,P1...Pj}, rescales it by a factor t/Q and returns the result in basis {Q0,Q1....Qi}.

type Context 

type Context struct {

	// Polynomial nb.Coefficients
	N uint64

	// Modulies
	Modulus []uint64

	// Product of the modulies
	ModulusBigint *Int

	// Parameters for the CRT reconstruction
	CrtReconstruction []*Int
	// contains filtered or unexported fields
}

Context is a structure keeping all the variable required to operate on a polynomial represented in this context. This include its moduli, crt reconstruction, modular reduction and ntt transformation.

func NewContext 

func NewContext() *Context

NewContext generates a new empty context.

func (*Context) AND 

func (context *Context) AND(p1 *Poly, m uint64, p2 *Poly)

AND applies a logical AND of m to the coefficients of p1, returning the result on p2.

func (*Context) Add 

func (context *Context) Add(p1, p2, p3 *Poly)

Add adds p1 to p2 coefficient wise and applies a modular reduction, returning the result on p3.

func (*Context) AddNoMod 

func (context *Context) AddNoMod(p1, p2, p3 *Poly)

AddNoMod adds p1 to p2 coefficient wise without modular reduction, returning the result on p3. The output range will be [0,2*Qi -1].

func (*Context) AddScalar 

func (context *Context) AddScalar(p1 *Poly, scalar uint64, p2 *Poly)

AddScalar adds to each coefficients of p1 a scalar and applies a modular reduction, returing the result on p2.

func (*Context) AllowsNTT added in v1.1.0 

func (context *Context) AllowsNTT() bool

AllowsNTT returns true if the context allows NTT, else false.

func (*Context) BitReverse 

func (context *Context) BitReverse(p1, p2 *Poly)

BitReverse applies a bit reverse permutation the coefficients of the input polynomial and returns the result on the receiver polynomial. Can safely be used for inplace permutation.

func (*Context) Copy 

func (context *Context) Copy(p0, p1 *Poly)

Copy copies the coefficients of p0 on p1 within the given context. Requiers p1 to be as big as the target context.

func (*Context) Equal 

func (context *Context) Equal(p1, p2 *Poly) bool

Equal checks if p1 = p2 in the given context.

func (*Context) Exp 

func (context *Context) Exp(p1 *Poly, e uint64, p2 *Poly)

Exp raises p1 to p1^e, returning the result on p2. TODO : implement montgomery ladder

func (*Context) GenNTTParams added in v1.1.0 

func (context *Context) GenNTTParams() error

GenNTTParams checks that N has beed correctly initialized, and checks that each moduli is a prime congruent to 1 mod 2N (i.e. allowing NTT). Then it computes the variables required for the NTT. ValidateParameters purpose is to validate that the moduli allow the NTT and compute the NTT parameters.

func (*Context) GetBredParams 

func (context *Context) GetBredParams() [][]uint64

GetBRedParams returns the Barret reduction parameters of the context.

func (*Context) GetCenteredCoefficients 

func (context *Context) GetCenteredCoefficients(p1 *Poly) [][]int64

GetCenteredCoefficients returns an array containing the coefficients of p1 centered arount each (-Qi/2, Qi/2].

func (*Context) GetMredParams 

func (context *Context) GetMredParams() []uint64

GetMredParams returns the Montgomery reduction parameters of the context.

func (*Context) GetNttNInv 

func (context *Context) GetNttNInv() []uint64

GetNttNInv returns 1/N mod each moduli.

func (*Context) GetNttPsi 

func (context *Context) GetNttPsi() [][]uint64

GetNttPsi returns the NTT parameters of the context.

func (*Context) GetNttPsiInv 

func (context *Context) GetNttPsiInv() [][]uint64

GetNttPsiInv returns the InvNTT parameters of the context.

func (*Context) GetPsi 

func (context *Context) GetPsi() []uint64

GetPsi returns the primitive root used to compute the NTT parameters of the context.

func (*Context) GetPsiInv 

func (context *Context) GetPsiInv() []uint64

GetPsi returns the primitive root used to compute the InvNTT parameters of the context.

func (*Context) InvMForm 

func (context *Context) InvMForm(p1, p2 *Poly)

MForm sets p1 in montgomeryform to its conventional form, returning the result on p2.

func (*Context) InvNTT 

func (context *Context) InvNTT(p1, p2 *Poly)

InvNTT performes the inverse NTT transformation on the CRT coefficients of a polynomial, based on the target context.

func (*Context) MForm 

func (context *Context) MForm(p1, p2 *Poly)

MForm sets p1 in conventional form to its montgomeryform, returning the result on p2.

func (*Context) MarshalBinary 

func (context *Context) MarshalBinary() ([]byte, error)

func (*Context) Merge 

func (context *Context) Merge(contextQ, contextP *Context) error

Merge merges two context by appending all the element from contextP to the elements of contextQ Will return an error if contextQ or contextP do not both agree on the flat allowsNTT. It however requires to re-compute the crt reconstruction parameters.

func (*Context) Mod 

func (context *Context) Mod(p1 *Poly, m uint64, p2 *Poly)

Mod applies a modular reduction by m over the coefficients of p1, returning the result on p2.

func (*Context) MulByPow2 

func (context *Context) MulByPow2(p1 *Poly, pow2 uint64, p2 *Poly)

MulByPow2 multiplies the input polynomial by 2^pow2 and returns the result on the receiver polynomial.

func (*Context) MulByPow2New 

func (context *Context) MulByPow2New(p1 *Poly, pow2 uint64) (p2 *Poly)

MulByPow2New multiplies the input polynomial by 2^pow2 and returns the result on a new polynomial.

func (*Context) MulByVectorMontgomery added in v1.1.0 

func (context *Context) MulByVectorMontgomery(p1 *Poly, vector []uint64, p2 *Poly)

MulByVector multiplies p1 by a vector of uint64 coefficients and returns the result on p2.

func (*Context) MulByVectorMontgomeryAndAddNoMod added in v1.1.0 

func (context *Context) MulByVectorMontgomeryAndAddNoMod(p1 *Poly, vector []uint64, p2 *Poly)

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

func (*Context) MulCoeffs 

func (context *Context) MulCoeffs(p1, p2, p3 *Poly)

MulCoeffs multiplies p1 by p2 coefficient wise with a Barrett modular reduction, returning the result on p3.

func (*Context) MulCoeffsAndAdd 

func (context *Context) MulCoeffsAndAdd(p1, p2, p3 *Poly)

MulCoeffsAndAdd multiplies p1 by p2 coefficient wise with a Barret modular reduction, adding the result to p3 with modular reduction.

func (*Context) MulCoeffsAndAddNoMod 

func (context *Context) MulCoeffsAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsAndAddNoMod multiplies p1 by p2 coefficient wise with a Barrett modular reduction, adding the result to p3 without modular reduction.

func (*Context) MulCoeffsConstant 

func (context *Context) MulCoeffsConstant(p1, p2, p3 *Poly)

MulcoeffsConstant multiplies p1 by p2 coefficient wise with a constant time Barrett modular reduction, returning the result on p3. The output range of the modular reduction is [0, 2*Qi -1].

func (*Context) MulCoeffsConstantMontgomery 

func (context *Context) MulCoeffsConstantMontgomery(p1, p2, p3 *Poly)

MulCoeffsConstantMontgomery multiplies p1 by p2 coefficient wise with a constant time Montgomery modular reduction, returning the result on p3. The output range of the modular reduction is [0, 2*Qi -1].

func (*Context) MulCoeffsMontgomery 

func (context *Context) MulCoeffsMontgomery(p1, p2, p3 *Poly)

MulCoeffsMontgomery multiplies p1 by p2 coefficient wise with a montgomery modular reduction, returning the result on p3. Expects p1 and/or p2 to be in montgomery form for correctness (see MRed).

func (*Context) MulCoeffsMontgomeryAndAdd 

func (context *Context) MulCoeffsMontgomeryAndAdd(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAdd multiplies p1 by p2 coefficient wise with a montgomery modular reduction, adding the result to p3. Expects p1 and/or p2 to be in montgomery form for correctness (see MRed).

func (*Context) MulCoeffsMontgomeryAndAddNoMod 

func (context *Context) MulCoeffsMontgomeryAndAddNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndAddNoMod multiplies p1 by p2 coefficient wise with a montgomery modular reduction, adding the result to p3 without modular reduction. Expects p1 and/or p2 to be in montgomery form for correctness (see MRed).

func (*Context) MulCoeffsMontgomeryAndSub 

func (context *Context) MulCoeffsMontgomeryAndSub(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSub multiplies p1 by p2 coefficient wise with a montgomery modular reduction, subtracting the result to p3 with modular reduction. Expects p1 and/or p2 to be in montgomery form for correctness (see MRed).

func (*Context) MulCoeffsMontgomeryAndSubNoMod 

func (context *Context) MulCoeffsMontgomeryAndSubNoMod(p1, p2, p3 *Poly)

MulCoeffsMontgomeryAndSubNoMod multiplies p1 by p2 coefficient wise with a montgomery modular reduction, subtracting the result to p3 without modular reduction. Expects p1 and/or p2 to be in montgomery form for correctness (see MRed).

func (*Context) MulPoly 

func (context *Context) MulPoly(p1, p2, p3 *Poly)

MulPoly multiplies p1 by p2 and returns the result on p3.

func (*Context) MulPolyMontgomery 

func (context *Context) MulPolyMontgomery(p1, p2, p3 *Poly)

MulPolyMontgomery multiplies p1 by p2 and returns the result on p3. Expect wither p1 or p2 to be in montgomery form for correctness.

func (*Context) MulPolyNaive 

func (context *Context) MulPolyNaive(p1, p2, p3 *Poly)

MulPolyNaive multiplies p1 by p2 with a naive convolution, returning the result on p3.

func (*Context) MulPolyNaiveMontgomery 

func (context *Context) MulPolyNaiveMontgomery(p1, p2, p3 *Poly)

MulPolyNaiveMontgomery multiplies p1 by p2 with a naive convolution, returning the result on p3. Much faster than MulPolyNaive.

func (*Context) MulScalar 

func (context *Context) MulScalar(p1 *Poly, scalar uint64, p2 *Poly)

MulScalar multiplies each coefficients of p1 by a scalar and applies a modular reduction, returning the result on p2.

func (*Context) MulScalarBigint 

func (context *Context) MulScalarBigint(p1 *Poly, scalar *Int, p2 *Poly)

MulScalarBigint multiplies each coefficients of p1 by an Int scalar and applies a modular reduction, returning the result on p2. To be used when the scalar is bigger than 64 bits.

func (*Context) MultByMonomial 

func (context *Context) MultByMonomial(p1 *Poly, monomialDeg uint64, p2 *Poly)

MultByMonomial multiplies the input polynomial by x^monomialDeg and returns the result on the receiver polynomial.

func (*Context) MultByMonomialNew 

func (context *Context) MultByMonomialNew(p1 *Poly, monomialDeg uint64) (p2 *Poly)

MultByMonomialNew multiplies the input polynomial by x^monomialDeg and returns the result on a new polynomial.

func (*Context) NTT 

func (context *Context) NTT(p1, p2 *Poly)

NTT performes the NTT transformation on the CRT coefficients a Polynomial, based on the target context.

func (*Context) Neg 

func (context *Context) Neg(p1, p2 *Poly)

Neg set all coefficient of p1 to there additive inverse, returning the result on p2.

func (*Context) NewKYSampler 

func (context *Context) NewKYSampler(sigma float64, bound int) *KYSampler

NewKYSampler creates a new KYSampler with sigma and bound that will be used to sample polynomial within the provided discret gaussian distribution.

func (*Context) NewPoly 

func (context *Context) NewPoly() *Poly

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

func (*Context) NewTernarySampler 

func (context *Context) NewTernarySampler() *TernarySampler

NewTernarySampler creates a new TernarySampler from the target context.

func (*Context) NewUniformPoly 

func (context *Context) NewUniformPoly() (Pol *Poly)

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

func (*Context) OR 

func (context *Context) OR(p1 *Poly, m uint64, p2 *Poly)

OR applies a logical OR of m to the coefficients of p1, returning the result on p2.

func (*Context) Permute 

func (context *Context) Permute(polIn *Poly, gen uint64, polOut *Poly)

Permute applies the galois transform on a polynonial outside of the NTT domain. It maps the coefficients x^i to x^(gen*i) Careful, not inplace!

func (*Context) PolyToBigint 

func (context *Context) PolyToBigint(p1 *Poly, coeffsBigint []*Int)

PolyToBigint reconstructs p1 and returns the result in an array of Int.

func (*Context) PolyToString 

func (context *Context) PolyToString(p1 *Poly) []string

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

func (*Context) Reduce 

func (context *Context) Reduce(p1, p2 *Poly)

Reduce applies a modular reduction over the coefficients of p1 returning the result on p2.

func (*Context) Rotate 

func (context *Context) Rotate(p1 *Poly, n uint64, p2 *Poly)

Rotate applies a Galoi Automorphism on p1 in NTT form, rotating the coefficients to the right by n, returning the result on p2. Requires the data to permuted in bitreversal order before applying NTT.

func (*Context) SetCoefficientsBigint 

func (context *Context) SetCoefficientsBigint(coeffs []*Int, p1 *Poly) error

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

func (*Context) SetCoefficientsInt64 

func (context *Context) SetCoefficientsInt64(coeffs []int64, p1 *Poly) error

SetCoefficientsInt64 sets the coefficients of p1 from an int64 array.

func (*Context) SetCoefficientsString 

func (context *Context) SetCoefficientsString(coeffs []string, p1 *Poly) error

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

func (*Context) SetCoefficientsUint64 

func (context *Context) SetCoefficientsUint64(coeffs []uint64, p1 *Poly) error

SetCoefficientsUint64 sets the coefficient of Pol from an uint64 array.

func (*Context) SetParameters 

func (context *Context) SetParameters(N uint64, Modulus []uint64) error

SetParameters initialize the parameters of an empty context with N and the provided moduli. Only checks that N is a power of 2 and computes all the variable that aren't used for the NTT.

func (*Context) Shift 

func (context *Context) Shift(p1 *Poly, n uint64, p2 *Poly)

Shift circulary shifts the coefficients of the polynomial p1 by n to the left and returns the result on the receiver polynomial.

func (*Context) Sub 

func (context *Context) Sub(p1, p2, p3 *Poly)

Sub subtract p2 to p1 coefficient wise and applies a modular reduction, returning the result on p3.

func (*Context) SubNoMod 

func (context *Context) SubNoMod(p1, p2, p3 *Poly)

SubNoMod subtract p2 to p1 coefficient wise without modular reduction, returning the result on p3. The output range will be [0,2*Qi -1].

func (*Context) SubScalar 

func (context *Context) SubScalar(p1 *Poly, scalar uint64, p2 *Poly)

SubScalar subtracts to each coefficients of p1 a scalar and applies a modular reduction, returing the result on p2.

func (*Context) UnMarshalBinary 

func (context *Context) UnMarshalBinary(data []byte) error

func (*Context) XOR 

func (context *Context) XOR(p1 *Poly, m uint64, p2 *Poly)

XOR applies a logical XOR of m to the coefficients of p1, returning the result on p2.

type Float128 

type Float128 [2]float64 // float128 represented by two float64s

Float128 represents a double-double floating point number with 106 bits of mantissa, or about 32 decimal digits. The zero value for a Float128 represents the value 0.

func Float128Add 

func Float128Add(a, b Float128) (f Float128)

Float128Add computes f = a + b

func Float128Div 

func Float128Div(a, b Float128) (f Float128)

Float128Div computes f = a / b

func Float128Mul 

func Float128Mul(a, b Float128) (f Float128)

Float128Mul computes f = a * b

func Float128SetInt64 

func Float128SetInt64(i int64) (result Float128)

Float128SetInt64 sets 128-bit floating point object from int64 Allows to import integers bigger than 53 bits and do computation with a result of up to 64 bits. However the variable will be scaled by a 1/4096 factor that has to be taked into account when doing computation. Unsafe to use for values below 2^64/4096 since it will set the first element to zero.

func Float128SetUint53 

func Float128SetUint53(i uint64) (result Float128)

Float128SetUint53 sets 128-bit floating point object from an uint64. To be used only if the integer is 53 or less bits and if the computation will stay under 54 bits.

func Float128SetUint64 

func Float128SetUint64(i uint64) (result Float128)

Float128SetUint64 sets 128-bit floating point object from uint64 Allows to import integers bigger than 53 bits and do computation with result of up to 64 bits. However the variable will be scaled by a 1/4096 factor that has to be taked into account when doing computation. Unsafe to use for values below 2^64/4096 since it will set the first element to zero.

func Float128SetZero 

func Float128SetZero() (result Float128)

Float128SetZero sets a 128-bit floating point object to 0.0

func Float128Sub 

func Float128Sub(a, b Float128) (f Float128)

Float128Sub computes f = a - b

type Int 

type Int struct {
	Value big.Int // Integer value, theoretically ranging from -infinite to +infinite
}

Int is a generic implementation of natural arithmetic on integers, built using Go's built-in "math/big.Int"

func Copy 

func Copy(v *Int) *Int

Copy creates a new Int wich is a copy of the input Int.

func NewInt 

func NewInt(v int64) *Int

NewInt creates a new Int with a given int64 value.

func NewIntFromString 

func NewIntFromString(s string) *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) *Int

NewInt creates a new Int with a given uint64 value.

func RandInt 

func RandInt(max *Int) *Int

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

func (*Int) Add 

func (i *Int) Add(a, b *Int) *Int

Add sets the target i to a + b.

func (*Int) And 

func (i *Int) And(a, b *Int) *Int

And sets the target i to a & b.

func (*Int) Bits 

func (i *Int) Bits() ([]uint, uint)

Bits returns the bit stream and bit length of i's absolute value. For example, 6=110, this function will return ([0, 1, 1], 3)

func (*Int) Center 

func (i *Int) Center(Q *Int) *Int

Center shifts r from [0, q) to (-q/2, q/2]

func (*Int) Compare 

func (i *Int) Compare(i2 *Int) int

Cmp compares i and i2 and returns: 

-1 if i <  i2
 0 if i == i2
+1 if i >  i2

func (*Int) Div 

func (i *Int) Div(a, b *Int) *Int

Div sets the target i to floor(a / b).

func (*Int) DivRound 

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

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

func (*Int) EqualTo 

func (i *Int) EqualTo(i2 *Int) bool

EqualTo judges if i and i2 have the same value.

func (*Int) Exp 

func (i *Int) Exp(a, b, m *Int) *Int

Exp sets the target i to a^b mod m

func (*Int) Float64 

func (i *Int) Float64() float64

Float64 returns the target as float64 with 53 bits of precision

func (*Int) Int64 

func (i *Int) Int64() int64

Int64 returns the low 63 bits of i as int64

func (*Int) Inv 

func (i *Int) Inv(a, m *Int) *Int

Inv sets the target i to a^-1 mod m.

func (*Int) IsPrime 

func (i *Int) IsPrime(n int) bool

IsPrime returns true if the target is probably prime, else false.

func (*Int) Lsh 

func (i *Int) Lsh(a *Int, m uint64) *Int

Lsh sets the target i to a << m.

func (*Int) Mod 

func (i *Int) Mod(a, m *Int) *Int

Mod sets the target i to a mod m.

func (*Int) Mul 

func (i *Int) Mul(a, b *Int) *Int

Mul sets the target i to a * b.

func (*Int) Neg 

func (i *Int) Neg(a, m *Int) *Int

Neg sets the target i to -a mod m.

func (*Int) Rsh 

func (i *Int) Rsh(a *Int, m uint64) *Int

Rsh sets the target i to a >> m.

func (*Int) SetBigInt 

func (i *Int) SetBigInt(v *Int)

SetBigInt sets Int i with bigint.Int

func (*Int) SetInt 

func (i *Int) SetInt(v int64)

SetInt sets Int i with value v

func (*Int) SetString 

func (i *Int) SetString(s string)

SetString sets the value of i 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 (*Int) SetUint 

func (i *Int) SetUint(v uint64)

SetInt sets Int i with value v

func (*Int) String 

func (i *Int) String() string

String returns the value of Int i in string

func (*Int) Sub 

func (i *Int) Sub(a, b *Int) *Int

Sub sets the target i to a - b.

func (*Int) Uint32 

func (i *Int) Uint32() uint32

Uint32 returns the low 32 bits of i as uint32

func (*Int) Uint64 

func (i *Int) Uint64() uint64

Uint64 returns the low 64 bits of i as uint64

type KYSampler 

type KYSampler struct {
	Matrix [][]uint8
	// contains filtered or unexported fields
}

KYSampler is the structure holding the parameters for the gaussian sampling.

func (*KYSampler) Sample 

func (kys *KYSampler) Sample(Pol *Poly)

SampleNew samples on the target polynomial coefficients with gaussian distribution given the target kys parameters.

func (*KYSampler) SampleNTT 

func (kys *KYSampler) SampleNTT(Pol *Poly)

SampleNew samples on the target polynomial coefficients with gaussian distribution given the target kys parameters,and applies the NTT.

func (*KYSampler) SampleNTTNew 

func (kys *KYSampler) SampleNTTNew() *Poly

SampleNTTNew samples a polynomial with gaussian distribution given the target kys context and apply the NTT.

func (*KYSampler) SampleNew 

func (kys *KYSampler) SampleNew() *Poly

SampleNew samples a new polynomial with gaussian distribution given the target kys parameters.

type Poly 

type Poly struct {
	Coeffs [][]uint64 //Coefficients in CRT representation
}

Poly is the structure containing the coefficients of a polynomial.

func (*Poly) Copy 

func (Pol *Poly) Copy(p1 *Poly)

Copy copies the coefficients of Pol on p1.

func (*Poly) CopyNew 

func (Pol *Poly) CopyNew() (p1 *Poly)

CopyNew creates a new polynomial p1 which is a copy of the target polynomial.

func (*Poly) GetCoefficients 

func (Pol *Poly) GetCoefficients() [][]uint64

GetCoefficients returns a double slice containing the coefficients of the polynomial.

func (*Poly) GetDegree 

func (Pol *Poly) GetDegree() int

GetDegree returns the number of coefficients (degree) of the polynomial.

func (*Poly) GetLenModuli added in v1.1.0 

func (Pol *Poly) GetLenModuli() int

GetLenModuli returns the number of modulies

func (*Poly) MarshalBinary 

func (Pol *Poly) MarshalBinary() ([]byte, error)

func (*Poly) SetCoefficients 

func (Pol *Poly) SetCoefficients(coeffs [][]uint64) error

SetCoefficients sets the coefficients of polynomial directly from a CRT format (double slice).

func (*Poly) UnMarshalBinary 

func (Pol *Poly) UnMarshalBinary(data []byte) (*Poly, error)

func (*Poly) Zero 

func (Pol *Poly) Zero()

Zero sets all coefficient of the target polynomial to 0.

type SimpleScaler 

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

SimpleScaler is the structure storing the parameters to reconstruct a polynomial, scale it by t/Q and return the results modulo t. Algorithm from https://eprint.iacr.org/2018/117.pdf

func NewSimpleScaler 

func NewSimpleScaler(t uint64, context *Context) (newParams *SimpleScaler)

NewSimpleScaler creates a new SimpleScaler from t (the modulus under which the reconstruction is returned) and context (the context in which the polynomial to reconstruct will be represented).

func (*SimpleScaler) Scale 

func (parameters *SimpleScaler) Scale(p1, p2 *Poly)

Scale returns the reconstruction of p1 scaled by a factor t/Q and mod t on the reciever p2.

type TernarySampler 

type TernarySampler struct {
	Matrix           [][]uint64
	MatrixMontgomery [][]uint64

	KYMatrix [][]uint8
	// contains filtered or unexported fields
}

TernarySampler is the structure holding the parameters for sampling polynomials of the form [-1, 0, 1].

func (*TernarySampler) Sample 

func (sampler *TernarySampler) Sample(p float64, pol *Poly) (err error)

func (*TernarySampler) SampleMontgomery 

func (sampler *TernarySampler) SampleMontgomery(p float64, pol *Poly) (err error)

func (*TernarySampler) SampleMontgomeryNTT 

func (sampler *TernarySampler) SampleMontgomeryNTT(p float64, pol *Poly) (err error)

SampleNTT samples coefficients with ternary distribution in the NTT domain and in montgomery form on the target polynomial.

func (*TernarySampler) SampleMontgomeryNTTNew 

func (sampler *TernarySampler) SampleMontgomeryNTTNew(p float64) (pol *Poly, err error)

SampleNTTNew samples a new polynomial with ternary distribution in the NTT domain and in montgomery form.

func (*TernarySampler) SampleMontgomeryNew 

func (sampler *TernarySampler) SampleMontgomeryNew(p float64) (pol *Poly, err error)

SampleMontgomeryNew samples a new polynomial with ternary distribution in montgomery form.

func (*TernarySampler) SampleNTT 

func (sampler *TernarySampler) SampleNTT(p float64, pol *Poly) (err error)

SampleNTT samples coefficients with ternary distribution in the NTT domain on the target polynomial.

func (*TernarySampler) SampleNTTNew 

func (sampler *TernarySampler) SampleNTTNew(p float64) (pol *Poly, err error)

SampleNTTNew samples a new polynomial with ternary distribution in the NTT domain.

func (*TernarySampler) SampleNew 

func (sampler *TernarySampler) SampleNew(p float64) (pol *Poly, err error)

SampleNew samples a new polynomial with ternary distribution.

func (*TernarySampler) SampleUniform added in v1.1.0 

func (sampler *TernarySampler) SampleUniform(pol *Poly)

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.