polynomial

package
v6.1.0 Latest Latest
Warning

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

 Go to latest Published: Oct 14, 2024 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

Package polynomial bundles generic parts of the homomorphic polynomial evaluation circuit.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func SplitDegree 

func SplitDegree(n int) (a, b int)

SplitDegree returns a * b = n such that |a-b| is minimized with a and/or b odd if possible.

Types

type BabyStep 

type BabyStep struct {
	Degree int
	Value  *rlwe.Ciphertext
}

BabyStep is a struct storing the result of a baby-step of the Paterson-Stockmeyer polynomial evaluation algorithm.

type CoefficientGetter 

type CoefficientGetter[T uint64 | *bignum.Complex] interface {
	// GetVectorCoefficient should return a slice []T containing the k-th coefficient
	// of each polynomial of PolynomialVector indexed by its Mapping.
	// See PolynomialVector for additional information about the Mapping.
	GetVectorCoefficient(pol PolynomialVector, k int) (values []T)
	// GetSingleCoefficient should return the k-th coefficient of Polynomial as the type T.
	GetSingleCoefficient(pol Polynomial, k int) (value T)
}

CoefficientGetter defines an interface to get the coefficients of a Polynomial.

type Evaluator 

type Evaluator[T uint64 | *bignum.Complex] struct {
	schemes.Evaluator
	CoefficientGetter[T]
}

func (Evaluator[T]) Evaluate 

func (eval Evaluator[T]) Evaluate(input interface{}, p interface{}, targetScale rlwe.Scale, levelsConsumedPerRescaling int, SimEval SimEvaluator) (opOut *rlwe.Ciphertext, err error)

Evaluate is a generic and scheme agnostic method to evaluate polynomials on rlwe.Ciphertexts.

func (Evaluator[T]) EvaluateBabyStep 

func (eval Evaluator[T]) EvaluateBabyStep(i int, poly PatersonStockmeyerPolynomialVector, pb PowerBasis) (ct *BabyStep, err error)

EvaluateBabyStep evaluates a baby-step of the PatersonStockmeyer polynomial evaluation algorithm, i.e. the inner-product between the precomputed powers [1, T, T^2, ..., T^{n-1}] and the coefficients [ci0, ci1, ci2, ..., ci{n-1}].

func (Evaluator[T]) EvaluateGianStep 

func (eval Evaluator[T]) EvaluateGianStep(i int, giantSteps []int, babySteps []*BabyStep, pb PowerBasis) (err error)

EvaluateGianStep evaluates a giant-step of the PatersonStockmeyer polynomial evaluation algorithm, which consists in combining the baby-steps <[1, T, T^2, ..., T^{n-1}], [ci0, ci1, ci2, ..., ci{n-1}]> together with powers T^{2^k}.

func (Evaluator[T]) EvaluateMonomial 

func (eval Evaluator[T]) EvaluateMonomial(a, b, xpow *rlwe.Ciphertext) (err error)

EvaluateMonomial evaluates a monomial of the form a + b * X^{pow} and writes the results in b.

func (Evaluator[T]) EvaluatePatersonStockmeyerPolynomialVector 

func (eval Evaluator[T]) EvaluatePatersonStockmeyerPolynomialVector(poly PatersonStockmeyerPolynomialVector, pb PowerBasis) (res *rlwe.Ciphertext, err error)

EvaluatePatersonStockmeyerPolynomialVector evaluates a pre-decomposed PatersonStockmeyerPolynomialVector on a pre-computed power basis [1, X^{1}, X^{2}, ..., X^{2^{n}}, X^{2^{n+1}}, ..., X^{2^{m}}]

func (Evaluator[T]) EvaluatePolynomialVectorFromPowerBasis 

func (eval Evaluator[T]) EvaluatePolynomialVectorFromPowerBasis(targetLevel int, pol PolynomialVector, pb PowerBasis, targetScale rlwe.Scale) (res *rlwe.Ciphertext, err error)

EvaluatePolynomialVectorFromPowerBasis evaluates P(ct) = sum c_i * ct^{i}.

type PatersonStockmeyerPolynomial 

type PatersonStockmeyerPolynomial struct {
	Degree int
	Base   int
	Level  int
	Scale  rlwe.Scale
	Value  []Polynomial
}

PatersonStockmeyerPolynomial is a struct that stores the Paterson Stockmeyer decomposition of a polynomial. The decomposition of P(X) is given as sum pi(X) * X^{2^{n}} where degree(pi(X)) =~ sqrt(degree(P(X)))

type PatersonStockmeyerPolynomialVector 

type PatersonStockmeyerPolynomialVector struct {
	Value   []PatersonStockmeyerPolynomial
	Mapping map[int][]int
}

PatersonStockmeyerPolynomialVector is a struct implementing the Paterson Stockmeyer decomposition of a PolynomialVector. See PatersonStockmeyerPolynomial for additional information.

type Polynomial 

type Polynomial struct {
	bignum.Polynomial
	MaxDeg int        // Always set to len(Coeffs)-1
	Lead   bool       // Always set to true
	Lazy   bool       // Flag for lazy-relinearization
	Level  int        // Metadata for BSGS polynomial evaluation
	Scale  rlwe.Scale // Metadata for BSGS polynomial evaluation
}

Polynomial is a struct for representing plaintext polynomials for their homomorphic evaluation in an encrypted point. The type wraps a bignum.Polynomial along with several evaluation- related parameters.

func NewPolynomial 

func NewPolynomial(poly bignum.Polynomial) Polynomial

NewPolynomial returns an instantiated Polynomial for the provided bignum.Polynomial.

func (Polynomial) Factorize 

func (p Polynomial) Factorize(n int) (pq, pr Polynomial)

Factorize factorizes p as X^{n} * pq + pr.

func (Polynomial) PatersonStockmeyerPolynomial 

func (p Polynomial) PatersonStockmeyerPolynomial(params rlwe.ParameterProvider, inputLevel int, inputScale, outputScale rlwe.Scale, eval SimEvaluator) PatersonStockmeyerPolynomial

PatersonStockmeyerPolynomial returns the Paterson Stockmeyer polynomial decomposition of the target polynomial. The decomposition is done with the power of two basis.

type PolynomialVector 

type PolynomialVector struct {
	Value   []Polynomial
	Mapping map[int][]int
}

PolynomialVector is a struct storing a set of polynomials and a mapping that indicates on which slot each polynomial has to be independently evaluated. For example, if we are given two polynomials P0(X) and P1(X) and the folling mapping: map[int][]int{0:[0, 1, 2], 1:[3, 4, 5]}, then the polynomial evaluation on a vector [a, b, c, d, e, f, g, h] will evaluate to [P0(a), P0(b), P0(c), P1(d), P1(e), P1(f), 0, 0]

func NewPolynomialVector 

func NewPolynomialVector(polys []bignum.Polynomial, mapping map[int][]int) (PolynomialVector, error)

NewPolynomialVector instantiates a new PolynomialVector from a set of bignum.Polynomial and a mapping indicating which polynomial has to be evaluated on which slot. For example, if we are given two polynomials P0(X) and P1(X) and the following mapping: map[int][]int{0:[0, 1, 2], 1:[3, 4, 5]}, then the polynomial evaluation on a vector [a, b, c, d, e, f, g, h] will evaluate to [P0(a), P0(b), P0(c), P1(d), P1(e), P1(f), 0, 0]

func (PolynomialVector) Factorize 

func (p PolynomialVector) Factorize(n int) (polyq, polyr PolynomialVector)

Factorize factorizes the underlying Polynomial vector p into p = polyq * X^{n} + polyr.

func (PolynomialVector) IsEven 

func (p PolynomialVector) IsEven() (even bool)

IsEven returns true if all underlying polynomials are even, i.e. all odd powers are zero.

func (PolynomialVector) IsOdd 

func (p PolynomialVector) IsOdd() (odd bool)

IsOdd returns true if all underlying polynomials are odd, i.e. all even powers are zero.

func (PolynomialVector) PatersonStockmeyerPolynomial 

func (p PolynomialVector) PatersonStockmeyerPolynomial(params rlwe.Parameters, inputLevel int, inputScale, outputScale rlwe.Scale, eval SimEvaluator) PatersonStockmeyerPolynomialVector

PatersonStockmeyerPolynomial returns the Paterson Stockmeyer polynomial decomposition of the target PolynomialVector. The decomposition is done with the power of two basis

type PowerBasis 

type PowerBasis struct {
	bignum.Basis
	Value structs.Map[int, rlwe.Ciphertext]
}

PowerBasis is a struct storing powers of a ciphertext.

func NewPowerBasis 

func NewPowerBasis(ct *rlwe.Ciphertext, basis bignum.Basis) (p PowerBasis)

NewPowerBasis creates a new PowerBasis. It takes as input a ciphertext and a basis type. The struct treats the input ciphertext as a monomial X and can be used to generates power of this monomial X^{n} in the given [BasisType].

func (PowerBasis) BinarySize 

func (p PowerBasis) BinarySize() (size int)

BinarySize returns the serialized size of the object in bytes.

func (*PowerBasis) GenPower 

func (p *PowerBasis) GenPower(n int, lazy bool, eval schemes.Evaluator) (err error)

GenPower recursively computes X^{n}. If lazy = true, the final X^{n} will not be relinearized. Previous non-relinearized X^{n} that are required to compute the target X^{n} are automatically relinearized.

func (PowerBasis) MarshalBinary 

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

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

func (*PowerBasis) ReadFrom 

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

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

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

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

func (*PowerBasis) UnmarshalBinary 

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

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

func (PowerBasis) WriteTo 

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

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

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

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

type SimEvaluator 

type SimEvaluator interface {
	MulNew(op0, op1 *SimOperand) *SimOperand
	Rescale(op0 *SimOperand)
	PolynomialDepth(degree int) int
	UpdateLevelAndScaleGiantStep(lead bool, tLevelOld int, tScaleOld, xPowScale rlwe.Scale) (tLevelNew int, tScaleNew rlwe.Scale)
	UpdateLevelAndScaleBabyStep(lead bool, tLevelOld int, tScaleOld rlwe.Scale) (tLevelNew int, tScaleNew rlwe.Scale)
}

SimEvaluator defines a set of method on SimOperands.

type SimOperand 

type SimOperand struct {
	Level int
	Scale rlwe.Scale
}

SimOperand is a dummy operand that only stores its level and scale.

type SimPowerBasis 

type SimPowerBasis map[int]*SimOperand

SimPowerBasis is a map storing powers of SimOperands indexed by their power.

func (SimPowerBasis) GenPower 

func (d SimPowerBasis) GenPower(params rlwe.ParameterProvider, n int, eval SimEvaluator)

GenPower populates the target SimPowerBasis with the nth power.

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.