hefloat

package
v5.0.0-...-72ea290 Latest Latest
Warning

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

 Go to latest Published: Dec 15, 2023 License: Apache-2.0 Imports: 14 Imported by: 0

README

References

  1. Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison (https://ieeexplore.ieee.org/abstract/document/9517029)

Documentation

Overview

Package hefloat implements Homomorphic Encryption with fixed-point approximate arithmetic over the complex or real numbers.

Index

Constants

View Source 
const (
	HomomorphicEncode = DFTType(0) // Homomorphic Encoding (IDFT)
	HomomorphicDecode = DFTType(1) // Homomorphic Decoding (DFT)
)

HomomorphicEncode (IDFT) and HomomorphicDecode (DFT) are two available linear transformations for homomorphic encoding and decoding.

View Source 
const (
	// Standard: designates the regular DFT.
	// Example: [a+bi, c+di] -> DFT([a+bi, c+di])
	Standard = DFTFormat(0)
	// SplitRealAndImag: HomomorphicEncode will return the real and
	// imaginary part into separate ciphertexts, both as real vectors.
	// Example: [a+bi, c+di] -> DFT([a, c]) and DFT([b, d])
	SplitRealAndImag = DFTFormat(1)
	// RepackImagAsReal: behaves the same as SplitRealAndImag except that
	// if the ciphertext is sparsely packed (at most N/4 slots), HomomorphicEncode
	// will repacks the real part into the left N/2 slots and the imaginary part
	// into the right N/2 slots. HomomorphicDecode must be specified with the same
	// format for correctness.
	// Example: [a+bi, 0, c+di, 0] -> [DFT([a, b]), DFT([b, d])]
	RepackImagAsReal = DFTFormat(2)
)
View Source 
const (
	CosDiscrete   = Mod1Type(0) // Special approximation (Han and Ki) of pow((1/2pi), 1/2^r) * cos(2pi(x-0.25)/2^r); this method requires a minimum degree of 2*(K-1).
	SinContinuous = Mod1Type(1) // Standard Chebyshev approximation of (1/2pi) * sin(2pix) on the full interval
	CosContinuous = Mod1Type(2) // Standard Chebyshev approximation of pow((1/2pi), 1/2^r) * cos(2pi(x-0.25)/2^r) on the full interval
)

Sin and Cos are the two proposed functions for Mod1Type. These trigonometric functions offer a good approximation of the function x mod 1 when the values are close to the origin.

Variables

View Source 
var CoeffsSignX2Cheby = []string{"0", "1.125", "0", "-0.125"}

CoeffsSignX2Cheby (from https://eprint.iacr.org/2019/1234.pdf) are the coefficients of 1.5*x - 0.5*x^3 in Chebyshev basis. Evaluating this polynomial on values already close to -1, or 1 ~doubles the number of of correct digits. For example, if x = -0.9993209 then p(x) = -0.999999308 This polynomial can be composed after the minimax composite polynomial to double the output precision (up to the scheme precision) each time it is evaluated.

View Source 
var CoeffsSignX4Cheby = []string{"0", "1.1962890625", "0", "-0.2392578125", "0", "0.0478515625", "0", "-0.0048828125"}

CoeffsSignX4Cheby (from https://eprint.iacr.org/2019/1234.pdf) are the coefficients of 35/16 * x - 35/16 * x^3 + 21/16 * x^5 - 5/16 * x^7 in Chebyshev basis. Evaluating this polynomial on values already close to -1, or 1 ~quadruples the number of of correct digits. For example, if x = -0.9993209 then p(x) = -0.9999999999990705 This polynomial can be composed after the minimax composite polynomial to quadruple the output precision (up to the scheme precision) each time it is evaluated.

View Source 
var DefaultMinimaxCompositePolynomialForSign = [][]string{
	{"0", "0.6371462957672043333", "0", "-0.2138032460610765328", "0", "0.1300439303835664499", "0", "-0.0948842756566191044", "0", "0.0760417811618939909", "0", "-0.0647714820920817557", "0", "0.0577904411211959048", "0", "-0.5275634328386103792"},
	{"0", "0.6371463830322414578", "0", "-0.2138032749880402509", "0", "0.1300439475440832118", "0", "-0.0948842877009570762", "0", "0.0760417903036533484", "0", "-0.0647714893343788749", "0", "0.0577904470018789283", "0", "-0.5275633669027163690"},
	{"0", "0.6371474873319408921", "0", "-0.2138036410457105809", "0", "0.1300441647026617059", "0", "-0.0948844401165889295", "0", "0.0760419059884502454", "0", "-0.0647715809823254389", "0", "0.0577905214191996406", "0", "-0.5275625325136631842"},
	{"0", "0.6370469776996076431", "0", "-0.2134526779726600620", "0", "0.1294300181775238920", "0", "-0.0939692999460324791", "0", "0.0747629355709698798", "0", "-0.0630298319949635571", "0", "0.0554299627688379896", "0", "-0.0504549111784642023", "0", "0.5242368268605847996"},
	{"0", "0.6371925153898374380", "0", "-0.2127272333844484291", "0", "0.1280350175397897124", "0", "-0.0918861831051024970", "0", "0.0719237384158242601", "0", "-0.0593247422790627989", "0", "0.0506973946536399213", "0", "-0.0444605229007162961", "0", "0.0397788020190944552", "0", "-0.0361705584687241925", "0", "0.0333397971860406254", "0", "-0.0310960060432036761", "0", "0.0293126335952747929", "0", "-0.0279042579223662982", "0", "0.0268135229627401517", "0", "-0.5128179323757194002"},
	{"0", "0.6484328404896112084", "0", "-0.2164688471885406655", "0", "0.1302737771018761402", "0", "-0.0934786176742356885", "0", "0.0731553324133884104", "0", "-0.0603252338481440981", "0", "0.0515366139595849853", "0", "-0.0451803385226980999", "0", "0.0404062758116036740", "0", "-0.0367241775307736352", "0", "0.0338327393147257876", "0", "-0.0315379870551266008", "0", "0.0297110181467332488", "0", "-0.0282647625290482803", "0", "0.0271406820054187399", "0", "-0.5041440308249296747"},
	{"0", "0.8988231150519633581", "0", "-0.2996064625122592138", "0", "0.1797645789317822353", "0", "-0.1284080039344265678", "0", "0.0998837306152582349", "0", "-0.0817422066647773587", "0", "0.0691963884439569899", "0", "-0.0600136111161848355", "0", "0.0530132660795356506", "0", "-0.0475133961913746909", "0", "0.0430936248086665091", "0", "-0.0394819050695222720", "0", "0.0364958013826412785", "0", "-0.0340100990129699835", "0", "0.0319381346687564699", "0", "-0.3095637759472512887"},
	{"0", "1.2654405107323937767", "0", "-0.4015427502443620045", "0", "0.2182109348265640036", "0", "-0.1341692540177466882", "0", "0.0852282854825304735", "0", "-0.0539043807248265057", "0", "0.0332611560159092728", "0", "-0.0197419082926337129", "0", "0.0111368708758574529", "0", "-0.0058990205011466309", "0", "0.0028925861201479251", "0", "-0.0012889673944941461", "0", "0.0005081425552893727", "0", "-0.0001696330470066833", "0", "0.0000440808328172753", "0", "-0.0000071549240608255"},
	CoeffsSignX4Cheby,
}

DefaultMinimaxCompositePolynomialForSign is an example of composite minimax polynomial for the sign function that is able to distinguish between value with a delta of up to 2^{-alpha=30}, tolerates a scheme error of 2^{-35} and outputs a binary value (-1, or 1) of up to 20x4 bits of precision.

It was computed with GenMinimaxCompositePolynomialForSign(256, 30, 35, []int{15, 15, 15, 17, 31, 31, 31, 31}) which outputs a minimax composite polynomial of precision 21.926741, which is further composed with CoeffsSignX4Cheby to bring it to ~80bits of precision.

Functions

func EncodeLinearTransformation 

func EncodeLinearTransformation[T Float](ecd *Encoder, diagonals Diagonals[T], allocated LinearTransformation) (err error)

EncodeLinearTransformation is a method used to encode EncodeLinearTransformation and a wrapper of he.EncodeLinearTransformation. See he.EncodeLinearTransformation for the documentation.

func GaloisElementsForLinearTransformation 

func GaloisElementsForLinearTransformation(params rlwe.ParameterProvider, lt LinearTransformationParameters) (galEls []uint64)

GaloisElementsForLinearTransformation returns the list of Galois elements required to evaluate the linear transformation.

func GenMinimaxCompositePolynomial 

func GenMinimaxCompositePolynomial(prec uint, logalpha, logerr int, deg []int, f func(*big.Float) *big.Float) (coeffs [][]*big.Float)

GenMinimaxCompositePolynomial generates the minimax composite polynomial P(x) = pk(x) o pk-1(x) o ... o p1(x) o p0(x) for the provided function in the interval in their interval [min-err, -2^{-alpha}] U [2^{-alpha}, max+err] where alpha is the desired distinguishing precision between two values and err an upperbound on the scheme error.

The user must provide the following inputs:

  • prec: the bit precision of the big.Float values used by the algorithm to compute the polynomials. This will impact the speed of the algorithm. A too low precision can prevent convergence or induce a slope zero during the zero finding. A sign that the precision is too low is when the iteration continue without the error getting smaller.
  • logalpha: log2(alpha)
  • logerr: log2(err), the upperbound on the scheme precision. Usually this value should be smaller or equal to logalpha. Correctly setting this value is mandatory for correctness, because if x is outside of the interval (i.e. smaller than -1-e or greater than 1+e), then the values will explode during the evaluation. Note that it is not required to apply change of interval [-1, 1] -> [-1-e, 1+e] because the function to evaluate is the sign (i.e. it will evaluate to the same value).
  • deg: the degree of each polynomial, ordered as follow [deg(p0(x)), deg(p1(x)), ..., deg(pk(x))]. It is highly recommended that deg(p0) <= deg(p1) <= ... <= deg(pk) for optimal approximation.

The polynomials are returned in the Chebyshev basis and pre-scaled for the interval [-1, 1] (no further scaling is required on the ciphertext).

Be aware that finding the minimax polynomials can take a while (in the order of minutes for high precision when using large degree polynomials).

The function will print information about each step of the computation in real time so that it can be monitored.

The underlying algorithm use the multi-interval Remez algorithm of https://eprint.iacr.org/2020/834.pdf.

func GenMinimaxCompositePolynomialForSign 

func GenMinimaxCompositePolynomialForSign(prec uint, logalpha, logerr int, deg []int)

GenMinimaxCompositePolynomialForSign generates the minimax composite polynomial P(x) = pk(x) o pk-1(x) o ... o p1(x) o p0(x) of the sign function in their interval [min-err, -2^{-alpha}] U [2^{-alpha}, max+err] where alpha is the desired distinguishing precision between two values and err an upperbound on the scheme error.

The sign function is defined as: -1 if -1 <= x < 0, 0 if x = 0, 1 if 0 < x <= 1.

See GenMinimaxCompositePolynomial for information about how to instantiate and parameterize each input value of the algorithm.

func GetPrecisionStats 

func GetPrecisionStats(params Parameters, encoder *Encoder, decryptor *rlwe.Decryptor, want, have interface{}, logprec float64, computeDCF bool) (prec ckks.PrecisionStats)

func NewCiphertext 

func NewCiphertext(params Parameters, degree, level int) *rlwe.Ciphertext

func NewDecryptor 

func NewDecryptor(params Parameters, key *rlwe.SecretKey) *rlwe.Decryptor

func NewEncryptor 

func NewEncryptor(params Parameters, key rlwe.EncryptionKey) *rlwe.Encryptor

func NewKeyGenerator 

func NewKeyGenerator(params Parameters) *rlwe.KeyGenerator

func NewPlaintext 

func NewPlaintext(params Parameters, level int) *rlwe.Plaintext

func NewPowerBasis 

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

NewPowerBasis is a wrapper of NewPolynomialBasis. This function creates a new powerBasis from the input ciphertext. The input ciphertext is treated as the base monomial X used to generate the other powers X^{n}.

func PrettyPrintCoefficients 

func PrettyPrintCoefficients(decimals int, coeffs []*big.Float, odd, even, first bool)

PrettyPrintCoefficients prints the coefficients formatted. If odd = true, even coefficients are zeroed. If even = true, odd coefficients are zeroed.

func VerifyTestVectors 

func VerifyTestVectors(params Parameters, encoder *Encoder, decryptor *rlwe.Decryptor, valuesWant, valuesHave interface{}, log2MinPrec int, logprec float64, printPrecisionStats bool, t *testing.T)

Types

type CoefficientGetter 

type CoefficientGetter struct {
	Values []*bignum.Complex
}

CoefficientGetter is a struct that implements the he.CoefficientGetter[*bignum.Complex] interface.

func (CoefficientGetter) GetSingleCoefficient 

func (c CoefficientGetter) GetSingleCoefficient(pol he.Polynomial, k int) (value *bignum.Complex)

GetSingleCoefficient returns the k-th coefficient of Polynomial as the type *bignum.Complex.

func (CoefficientGetter) GetVectorCoefficient 

func (c CoefficientGetter) GetVectorCoefficient(pol he.PolynomialVector, k int) (values []*bignum.Complex)

GetVectorCoefficient return a slice []*bignum.Complex containing the k-th coefficient of each polynomial of PolynomialVector indexed by its Mapping. See PolynomialVector for additional information about the Mapping.

func (CoefficientGetter) ShallowCopy 

func (c CoefficientGetter) ShallowCopy() he.CoefficientGetter[*bignum.Complex]

ShallowCopy returns a thread-safe copy of the original CoefficientGetter.

type ComparisonEvaluator 

type ComparisonEvaluator struct {
	MinimaxCompositePolynomialEvaluator
	MinimaxCompositeSignPolynomial MinimaxCompositePolynomial
}

ComparisonEvaluator is an evaluator providing an API for homomorphic comparisons. All fields of this struct are public, enabling custom instantiations.

func NewComparisonEvaluator 

func NewComparisonEvaluator(params Parameters, eval EvaluatorForMinimaxCompositePolynomial, bootstrapper he.Bootstrapper[rlwe.Ciphertext], signPoly ...MinimaxCompositePolynomial) *ComparisonEvaluator

NewComparisonEvaluator instantiates a new ComparisonEvaluator. The default hefloat.Evaluator is compliant with the EvaluatorForMinimaxCompositePolynomial interface. The field he.Bootstrapper[rlwe.Ciphertext] can be nil if the parameters have enough level to support the computation.

Giving a MinimaxCompositePolynomial is optional, but it is highly recommended to provide one that is optimized for the circuit requiring the comparisons as this polynomial will define the internal precision of all computations performed by this evaluator.

The MinimaxCompositePolynomial must be a composite minimax approximation of the sign function: f(x) = 1 if x > 0, -1 if x < 0, else 0, in the interval [-1, 1]. Such composite polynomial can be obtained with the function GenMinimaxCompositePolynomialForSign.

If no MinimaxCompositePolynomial is given, then it will use by default the variable DefaultMinimaxCompositePolynomialForSign. See the doc of DefaultMinimaxCompositePolynomialForSign for additional information about the performance of this approximation.

This method is allocation free if a MinimaxCompositePolynomial is given.

func (ComparisonEvaluator) Max 

func (eval ComparisonEvaluator) Max(op0, op1 *rlwe.Ciphertext) (max *rlwe.Ciphertext, err error)

Max returns the smooth maximum of op0 and op1, which is defined as: op0 * x + op1 * (1-x) where x = step(diff = op0-op1). Use must ensure that:

  • op0 + op1 is in the interval [-1, 1].
  • op0.Scale = op1.Scale.

This method ensures that max.Scale = params.DefaultScale.

func (ComparisonEvaluator) Min 

func (eval ComparisonEvaluator) Min(op0, op1 *rlwe.Ciphertext) (min *rlwe.Ciphertext, err error)

Min returns the smooth min of op0 and op1, which is defined as: op0 * (1-x) + op1 * x where x = step(diff = op0-op1) Use must ensure that:

  • op0 + op1 is in the interval [-1, 1].
  • op0.Scale = op1.Scale.

This method ensures that min.Scale = params.DefaultScale.

func (ComparisonEvaluator) Sign 

func (eval ComparisonEvaluator) Sign(op0 *rlwe.Ciphertext) (sign *rlwe.Ciphertext, err error)

Sign evaluates f(x) = 1 if x > 0, -1 if x < 0, else 0. This will ensure that sign.Scale = params.DefaultScale().

func (ComparisonEvaluator) Step 

func (eval ComparisonEvaluator) Step(op0 *rlwe.Ciphertext) (step *rlwe.Ciphertext, err error)

Step evaluates f(x) = 1 if x > 0, 0 if x < 0, else 0.5 (i.e. (sign+1)/2). This will ensure that step.Scale = params.DefaultScale().

type DFTEvaluator 

type DFTEvaluator struct {
	EvaluatorForDFT
	*LinearTransformationEvaluator
	// contains filtered or unexported fields
}

DFTEvaluator is an evaluator providing an API for homomorphic DFT. All fields of this struct are public, enabling custom instantiations.

func NewDFTEvaluator 

func NewDFTEvaluator(params Parameters, eval EvaluatorForDFT) *DFTEvaluator

NewDFTEvaluator instantiates a new DFTEvaluator. The default hefloat.Evaluator is compliant to the EvaluatorForDFT interface.

func (*DFTEvaluator) CoeffsToSlots 

func (eval *DFTEvaluator) CoeffsToSlots(ctIn *rlwe.Ciphertext, ctsMatrices DFTMatrix, ctReal, ctImag *rlwe.Ciphertext) (err error)

CoeffsToSlots applies the homomorphic encoding and returns the results on the provided ciphertexts. Homomorphically encodes a complex vector vReal + i*vImag of size n on a real vector of size 2n. If the packing is sparse (n < N/2), then returns ctReal = Ecd(vReal || vImag) and ctImag = nil. If the packing is dense (n == N/2), then returns ctReal = Ecd(vReal) and ctImag = Ecd(vImag).

func (*DFTEvaluator) CoeffsToSlotsNew 

func (eval *DFTEvaluator) CoeffsToSlotsNew(ctIn *rlwe.Ciphertext, ctsMatrices DFTMatrix) (ctReal, ctImag *rlwe.Ciphertext, err error)

CoeffsToSlotsNew applies the homomorphic encoding and returns the result on new ciphertexts. Homomorphically encodes a complex vector vReal + i*vImag. Given n = current number of slots and N/2 max number of slots (half the ring degree): If the packing is sparse (n < N/2), then returns ctReal = Ecd(vReal || vImag) and ctImag = nil. If the packing is dense (n == N/2), then returns ctReal = Ecd(vReal) and ctImag = Ecd(vImag).

func (*DFTEvaluator) SlotsToCoeffs 

func (eval *DFTEvaluator) SlotsToCoeffs(ctReal, ctImag *rlwe.Ciphertext, stcMatrices DFTMatrix, opOut *rlwe.Ciphertext) (err error)

SlotsToCoeffs applies the homomorphic decoding and returns the result on the provided ciphertext. Homomorphically decodes a real vector of size 2n on a complex vector vReal + i*vImag of size n. If the packing is sparse (n < N/2) then ctReal = Ecd(vReal || vImag) and ctImag = nil. If the packing is dense (n == N/2), then ctReal = Ecd(vReal) and ctImag = Ecd(vImag).

func (*DFTEvaluator) SlotsToCoeffsNew 

func (eval *DFTEvaluator) SlotsToCoeffsNew(ctReal, ctImag *rlwe.Ciphertext, stcMatrices DFTMatrix) (opOut *rlwe.Ciphertext, err error)

SlotsToCoeffsNew applies the homomorphic decoding and returns the result on a new ciphertext. Homomorphically decodes a real vector of size 2n on a complex vector vReal + i*vImag of size n. If the packing is sparse (n < N/2) then ctReal = Ecd(vReal || vImag) and ctImag = nil. If the packing is dense (n == N/2), then ctReal = Ecd(vReal) and ctImag = Ecd(vImag).

type DFTFormat 

type DFTFormat int

DFTFormat is a type used to distinguish between the different input/output formats of the Homomorphic DFT.

type DFTMatrix 

type DFTMatrix struct {
	DFTMatrixLiteral
	Matrices []LinearTransformation
}

DFTMatrix is a struct storing the factorized IDFT, DFT matrices, which are used to homomorphically encode and decode a ciphertext respectively.

func NewDFTMatrixFromLiteral 

func NewDFTMatrixFromLiteral(params Parameters, d DFTMatrixLiteral, encoder *Encoder) (DFTMatrix, error)

NewDFTMatrixFromLiteral generates the factorized DFT/IDFT matrices for the homomorphic encoding/decoding.

type DFTMatrixLiteral 

type DFTMatrixLiteral struct {
	// Mandatory
	Type       DFTType
	LogSlots   int
	LevelStart int
	Levels     []int
	// Optional
	Format       DFTFormat  // Default: standard.
	Scaling      *big.Float // Default 1.0.
	BitReversed  bool       // Default: False.
	LogBSGSRatio int        // Default: 0.
}

DFTMatrixLiteral is a struct storing the parameters to generate the factorized DFT/IDFT matrices. This struct has mandatory and optional fields.

Mandatory:

  • Type: HomomorphicEncode (a.k.a. CoeffsToSlots) or HomomorphicDecode (a.k.a. SlotsToCoeffs)
  • LogSlots: log2(slots)
  • LevelStart: starting level of the linear transformation
  • Levels: depth of the linear transform (i.e. the degree of factorization of the encoding matrix)

Optional:

  • Format: which post-processing (if any) to apply to the DFT.
  • Scaling: constant by which the matrix is multiplied
  • BitReversed: if true, then applies the transformation bit-reversed and expects bit-reversed inputs
  • LogBSGSRatio: log2 of the ratio between the inner and outer loop of the baby-step giant-step algorithm

func (DFTMatrixLiteral) Depth 

func (d DFTMatrixLiteral) Depth(actual bool) (depth int)

Depth returns the number of levels allocated to the linear transform. If actual == true then returns the number of moduli consumed, else returns the factorization depth.

func (DFTMatrixLiteral) GaloisElements 

func (d DFTMatrixLiteral) GaloisElements(params Parameters) (galEls []uint64)

GaloisElements returns the list of rotations performed during the CoeffsToSlot operation.

func (DFTMatrixLiteral) GenMatrices 

func (d DFTMatrixLiteral) GenMatrices(LogN int, prec uint) (plainVector []Diagonals[*bignum.Complex])

GenMatrices returns the ordered list of factors of the non-zero diagonals of the IDFT (encoding) or DFT (decoding) matrix.

func (DFTMatrixLiteral) MarshalBinary 

func (d DFTMatrixLiteral) MarshalBinary() (data []byte, err error)

MarshalBinary returns a JSON representation of the the target DFTMatrixLiteral on a slice of bytes. See `Marshal` from the `encoding/json` package.

func (*DFTMatrixLiteral) UnmarshalBinary 

func (d *DFTMatrixLiteral) UnmarshalBinary(data []byte) error

UnmarshalBinary reads a JSON representation on the target DFTMatrixLiteral struct. See `Unmarshal` from the `encoding/json` package.

type DFTType 

type DFTType int

DFTType is a type used to distinguish between different discrete Fourier transformations.

type Diagonals 

type Diagonals[T Float] he.Diagonals[T]

Diagonals is a wrapper of he.Diagonals. See he.Diagonals for the documentation.

func (Diagonals[T]) DiagonalsIndexList 

func (m Diagonals[T]) DiagonalsIndexList() (indexes []int)

DiagonalsIndexList returns the list of the non-zero diagonals of the square matrix. A non zero diagonals is a diagonal with a least one non-zero element.

type Encoder 

type Encoder struct {
	ckks.Encoder
}

func NewEncoder 

func NewEncoder(params Parameters, prec ...uint) *Encoder

func (Encoder) ShallowCopy 

func (ecd Encoder) ShallowCopy() *Encoder

type Evaluator 

type Evaluator struct {
	ckks.Evaluator
}

func NewEvaluator 

func NewEvaluator(params Parameters, evk rlwe.EvaluationKeySet) *Evaluator

func (Evaluator) GetParameters 

func (eval Evaluator) GetParameters() *Parameters

func (Evaluator) ShallowCopy 

func (eval Evaluator) ShallowCopy() *Evaluator

func (Evaluator) WithKey 

func (eval Evaluator) WithKey(evk rlwe.EvaluationKeySet) *Evaluator

type EvaluatorForDFT 

type EvaluatorForDFT interface {
	rlwe.ParameterProvider
	he.EvaluatorForLinearTransformation
	Add(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)
	Sub(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)
	Mul(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)
	Conjugate(op0 *rlwe.Ciphertext, opOut *rlwe.Ciphertext) (err error)
	Rotate(op0 *rlwe.Ciphertext, k int, opOut *rlwe.Ciphertext) (err error)
	Rescale(op0 *rlwe.Ciphertext, opOut *rlwe.Ciphertext) (err error)
}

EvaluatorForDFT is an interface defining the set of methods required to instantiate a DFTEvaluator. The default hefloat.Evaluator is compliant to this interface.

type EvaluatorForInverse 

type EvaluatorForInverse interface {
	EvaluatorForMinimaxCompositePolynomial
	SetScale(ct *rlwe.Ciphertext, scale rlwe.Scale) (err error)
}

EvaluatorForInverse defines a set of common and scheme agnostic methods that are necessary to instantiate an InverseEvaluator. The default hefloat.Evaluator is compliant to this interface.

type EvaluatorForMinimaxCompositePolynomial 

type EvaluatorForMinimaxCompositePolynomial interface {
	he.Evaluator
	ConjugateNew(ct *rlwe.Ciphertext) (ctConj *rlwe.Ciphertext, err error)
}

EvaluatorForMinimaxCompositePolynomial defines a set of common and scheme agnostic method that are necessary to instantiate a MinimaxCompositePolynomialEvaluator.

type EvaluatorForMod1 

type EvaluatorForMod1 interface {
	he.Evaluator
	DropLevel(*rlwe.Ciphertext, int)
	GetParameters() *Parameters
}

EvaluatorForMod1 defines a set of common and scheme agnostic methods that are necessary to instantiate a Mod1Evaluator. The default hefloat.Evaluator is compliant to this interface.

type Float 

type Float interface {
	ckks.Float
}

type InverseEvaluator 

type InverseEvaluator struct {
	EvaluatorForInverse
	*MinimaxCompositePolynomialEvaluator
	he.Bootstrapper[rlwe.Ciphertext]
	Parameters Parameters
}

InverseEvaluator is an evaluator used to evaluate the inverses of ciphertexts. All fields of this struct are public, enabling custom instantiations.

func NewInverseEvaluator 

func NewInverseEvaluator(params Parameters, eval EvaluatorForInverse, btp he.Bootstrapper[rlwe.Ciphertext]) InverseEvaluator

NewInverseEvaluator instantiates a new InverseEvaluator. The default hefloat.Evaluator is compliant to the EvaluatorForInverse interface. The field he.Bootstrapper[rlwe.Ciphertext] can be nil if the parameters have enough levels to support the computation. This method is allocation free.

func (InverseEvaluator) EvaluateFullDomainNew 

func (eval InverseEvaluator) EvaluateFullDomainNew(ct *rlwe.Ciphertext, log2min, log2max float64, signMinimaxPoly ...MinimaxCompositePolynomial) (cInv *rlwe.Ciphertext, err error)

EvaluateFullDomainNew computes 1/x for x in [-2^{log2max}, -2^{log2min}] U [2^{log2min}, 2^{log2max}].

  1. Reduce the interval from [-max, -min] U [min, max] to [-1, -min] U [min, 1] by computing an approximate inverse c such that |c * x| <= 1. For |x| > 1, c tends to 1/x while for |x| < c tends to 1. This is done by using the work Efficient Homomorphic Evaluation on Large Intervals (https://eprint.iacr.org/2022/280.pdf).
  2. Compute |c * x| = sign(x * c) * (x * c), this is required for the next step, which can only accept positive values.
  3. Compute y' = 1/(|c * x|) with the iterative Goldschmidt division algorithm.
  4. Compute y = y' * c * sign(x * c)

The user can provide a minimax composite polynomial (signMinimaxPoly) for the sign function in the interval [-1-e, -2^{log2min}] U [2^{log2min}, 1+e] (where e is an upperbound on the scheme error). If no such polynomial is provided, then the DefaultMinimaxCompositePolynomialForSign is used by default. Note that the precision of the output of sign(x * c) does not impact the circuit precision since this value ends up being both at the numerator and denominator, thus cancelling itself.

func (InverseEvaluator) EvaluateNegativeDomainNew 

func (eval InverseEvaluator) EvaluateNegativeDomainNew(ct *rlwe.Ciphertext, log2min, log2max float64) (cInv *rlwe.Ciphertext, err error)

EvaluateNegativeDomainNew computes 1/x for x in [-2^{log2max}, -2^{log2min}].

  1. Reduce the interval from [-max, -min] to [-1, -min] by computing an approximate inverse c such that |c * x| <= 1. For |x| > 1, c tends to 1/x while for |x| < c tends to 1. This is done by using the work Efficient Homomorphic Evaluation on Large Intervals (https://eprint.iacr.org/2022/280.pdf).
  2. Compute y' = 1/(c * x) with the iterative Goldschmidt division algorithm.
  3. Compute y = y' * c

func (InverseEvaluator) EvaluatePositiveDomainNew 

func (eval InverseEvaluator) EvaluatePositiveDomainNew(ct *rlwe.Ciphertext, log2min, log2max float64) (cInv *rlwe.Ciphertext, err error)

EvaluatePositiveDomainNew computes 1/x for x in [2^{log2min}, 2^{log2max}].

  1. Reduce the interval from [min, max] to [min, 1] by computing an approximate inverse c such that |c * x| <= 1. For |x| > 1, c tends to 1/x while for |x| < c tends to 1. This is done by using the work Efficient Homomorphic Evaluation on Large Intervals (https://eprint.iacr.org/2022/280.pdf).
  2. Compute y' = 1/(c * x) with the iterative Goldschmidt division algorithm.
  3. Compute y = y' * c

func (InverseEvaluator) GoldschmidtDivisionNew 

func (eval InverseEvaluator) GoldschmidtDivisionNew(ct *rlwe.Ciphertext, log2min float64) (ctInv *rlwe.Ciphertext, err error)

GoldschmidtDivisionNew homomorphically computes 1/x in the domain [0, 2]. input: ct: Enc(x) with values in the interval [0+2^{-log2min}, 2-2^{-log2min}]. output: Enc(1/x - e), where |e| <= (1-x)^2^(#iterations+1) -> the bit-precision doubles after each iteration. This method automatically estimates how many iterations are needed to achieve the optimal precision, which is derived from the plaintext scale. This method will return an error if the input ciphertext does not have enough remaining level and if the InverseEvaluator was instantiated with no bootstrapper. This method will return an error if something goes wrong with the bootstrapping or the rescaling operations.

func (InverseEvaluator) IntervalNormalization 

func (eval InverseEvaluator) IntervalNormalization(ct *rlwe.Ciphertext, log2Max float64, btp he.Bootstrapper[rlwe.Ciphertext]) (ctNorm, ctNormFac *rlwe.Ciphertext, err error)

IntervalNormalization applies a modified version of Algorithm 2 of Efficient Homomorphic Evaluation on Large Intervals (https://eprint.iacr.org/2022/280) to normalize the interval from [-max, max] to [-1, 1]. Also returns the encrypted normalization factor.

The original algorithm of https://eprint.iacr.org/2022/280 works by successive evaluation of a function that compresses values greater than some threshold to this threshold and let values smaller than the threshold untouched (mostly). The process is iterated, each time reducing the threshold by a pre-defined factor L. We can modify the algorithm to keep track of the compression factor so that we can get back the original values (before the compression) afterward.

Given ct with values [-max, max], the method will compute y such that ct * y has values in [-1, 1]. The normalization factor is independant to each slot:

  • values smaller than 1 will have a normalization factor that tends to 1
  • values greater than 1 will have a normalization factor that tends to 1/x

type LinearTransformation 

type LinearTransformation he.LinearTransformation

LinearTransformation is a wrapper of he.LinearTransformation. See he.LinearTransformation for the documentation.

func NewLinearTransformation 

func NewLinearTransformation(params rlwe.ParameterProvider, lt LinearTransformationParameters) LinearTransformation

NewLinearTransformation instantiates a new LinearTransformation and is a wrapper of he.LinearTransformation. See he.LinearTransformation for the documentation.

func (LinearTransformation) GaloisElements 

func (lt LinearTransformation) GaloisElements(params rlwe.ParameterProvider) []uint64

GaloisElements returns the list of Galois elements required to evaluate the linear transformation.

type LinearTransformationEvaluator 

type LinearTransformationEvaluator struct {
	he.EvaluatorForLinearTransformation
	he.EvaluatorForDiagonalMatrix
}

LinearTransformationEvaluator is an evaluator providing an API to evaluate linear transformations on rlwe.Ciphertexts. All fields of this struct are public, enabling custom instantiations.

func NewLinearTransformationEvaluator 

func NewLinearTransformationEvaluator(eval he.EvaluatorForLinearTransformation) (linTransEval *LinearTransformationEvaluator)

NewLinearTransformationEvaluator instantiates a new LinearTransformationEvaluator from a circuit.EvaluatorForLinearTransformation. The default hefloat.Evaluator is compliant to the he.EvaluatorForLinearTransformation interface. This method is allocation free.

func (LinearTransformationEvaluator) Evaluate 

func (eval LinearTransformationEvaluator) Evaluate(ctIn *rlwe.Ciphertext, linearTransformation LinearTransformation, opOut *rlwe.Ciphertext) (err error)

Evaluate takes as input a ciphertext ctIn, a linear transformation M and evaluates opOut: M(ctIn).

func (LinearTransformationEvaluator) EvaluateMany 

func (eval LinearTransformationEvaluator) EvaluateMany(ctIn *rlwe.Ciphertext, linearTransformations []LinearTransformation, opOut []*rlwe.Ciphertext) (err error)

EvaluateMany takes as input a ciphertext ctIn, a list of linear transformations [M0, M1, M2, ...] and a list of pre-allocated receiver opOut and evaluates opOut: [M0(ctIn), M1(ctIn), M2(ctIn), ...]

func (LinearTransformationEvaluator) EvaluateManyNew 

func (eval LinearTransformationEvaluator) EvaluateManyNew(ctIn *rlwe.Ciphertext, linearTransformations []LinearTransformation) (opOut []*rlwe.Ciphertext, err error)

EvaluateManyNew takes as input a ciphertext ctIn and a list of linear transformations [M0, M1, M2, ...] and returns opOut:[M0(ctIn), M1(ctIn), M2(ctInt), ...].

func (LinearTransformationEvaluator) EvaluateNew 

func (eval LinearTransformationEvaluator) EvaluateNew(ctIn *rlwe.Ciphertext, linearTransformation LinearTransformation) (opOut *rlwe.Ciphertext, err error)

EvaluateNew takes as input a ciphertext ctIn and a linear transformation M and evaluate and returns opOut: M(ctIn).

func (LinearTransformationEvaluator) EvaluateSequential 

func (eval LinearTransformationEvaluator) EvaluateSequential(ctIn *rlwe.Ciphertext, linearTransformations []LinearTransformation, opOut *rlwe.Ciphertext) (err error)

EvaluateSequential takes as input a ciphertext ctIn and a list of linear transformations [M0, M1, M2, ...] and returns opOut:...M2(M1(M0(ctIn))

func (LinearTransformationEvaluator) EvaluateSequentialNew 

func (eval LinearTransformationEvaluator) EvaluateSequentialNew(ctIn *rlwe.Ciphertext, linearTransformations []LinearTransformation) (opOut *rlwe.Ciphertext, err error)

EvaluateSequentialNew takes as input a ciphertext ctIn and a list of linear transformations [M0, M1, M2, ...] and returns opOut:...M2(M1(M0(ctIn))

type LinearTransformationParameters 

type LinearTransformationParameters he.LinearTransformationParameters

LinearTransformationParameters is a wrapper of he.LinearTransformationParameters. See he.LinearTransformationParameters for the documentation.

type MinimaxCompositePolynomial 

type MinimaxCompositePolynomial []bignum.Polynomial

MinimaxCompositePolynomial is a struct storing P(x) = pk(x) o pk-1(x) o ... o p1(x) o p0(x).

func NewMinimaxCompositePolynomial 

func NewMinimaxCompositePolynomial(coeffsStr [][]string) MinimaxCompositePolynomial

NewMinimaxCompositePolynomial creates a new MinimaxCompositePolynomial from a list of coefficients. Coefficients are expected to be given in the Chebyshev basis.

func (MinimaxCompositePolynomial) Evaluate 

func (mcp MinimaxCompositePolynomial) Evaluate(x interface{}) (y *bignum.Complex)

func (MinimaxCompositePolynomial) MaxDepth 

func (mcp MinimaxCompositePolynomial) MaxDepth() (depth int)

type MinimaxCompositePolynomialEvaluator 

type MinimaxCompositePolynomialEvaluator struct {
	EvaluatorForMinimaxCompositePolynomial
	PolynomialEvaluator
	he.Bootstrapper[rlwe.Ciphertext]
	Parameters Parameters
}

MinimaxCompositePolynomialEvaluator is an evaluator used to evaluate composite polynomials on ciphertexts. All fields of this struct are publics, enabling custom instantiations.

func NewMinimaxCompositePolynomialEvaluator 

func NewMinimaxCompositePolynomialEvaluator(params Parameters, eval EvaluatorForMinimaxCompositePolynomial, bootstrapper he.Bootstrapper[rlwe.Ciphertext]) *MinimaxCompositePolynomialEvaluator

NewMinimaxCompositePolynomialEvaluator instantiates a new MinimaxCompositePolynomialEvaluator. The default hefloat.Evaluator is compliant to the EvaluatorForMinimaxCompositePolynomial interface. This method is allocation free.

func (MinimaxCompositePolynomialEvaluator) Evaluate 

func (eval MinimaxCompositePolynomialEvaluator) Evaluate(ct *rlwe.Ciphertext, mcp MinimaxCompositePolynomial) (res *rlwe.Ciphertext, err error)

Evaluate evaluates the provided MinimaxCompositePolynomial on the input ciphertext.

type Mod1Evaluator 

type Mod1Evaluator struct {
	EvaluatorForMod1
	PolynomialEvaluator *PolynomialEvaluator
	Mod1Parameters      Mod1Parameters
}

Mod1Evaluator is an evaluator providing an API for homomorphic evaluations of scaled x mod 1. All fields of this struct are public, enabling custom instantiations.

func NewMod1Evaluator 

func NewMod1Evaluator(eval EvaluatorForMod1, evalPoly *PolynomialEvaluator, Mod1Parameters Mod1Parameters) *Mod1Evaluator

NewMod1Evaluator instantiates a new Mod1Evaluator evaluator. The default hefloat.Evaluator is compliant to the EvaluatorForMod1 interface. This method is allocation free.

func (Mod1Evaluator) EvaluateNew 

func (eval Mod1Evaluator) EvaluateNew(ct *rlwe.Ciphertext) (*rlwe.Ciphertext, error)

EvaluateNew applies a homomorphic mod Q on a vector scaled by Delta, scaled down to mod 1 :

  1. Delta * (Q/Delta * I(X) + m(X)) (Delta = scaling factor, I(X) integer poly, m(X) message)
  2. Delta * (I(X) + Delta/Q * m(X)) (divide by Q/Delta)
  3. Delta * (Delta/Q * m(X)) (x mod 1)
  4. Delta * (m(X)) (multiply back by Q/Delta)

Since Q is not a power of two, but Delta is, then does an approximate division by the closest power of two to Q instead. Hence, it assumes that the input plaintext is already scaled by the correcting factor Q/2^{round(log(Q))}.

!! Assumes that the input is normalized by 1/K for K the range of the approximation.

Scaling back error correction by 2^{round(log(Q))}/Q afterward is included in the polynomial

type Mod1Parameters 

type Mod1Parameters struct {
	LogDefaultScale int      // log2 of the default scaling factor
	Mod1Type        Mod1Type // type of approximation for the f: x mod 1 function
	LogMessageRatio int      // Log2 of the ratio between Q0 and m, i.e. Q[0]/|m|
	// contains filtered or unexported fields
}

Mod1Parameters is a struct storing the parameters and polynomials approximating the function x mod Q[0] (the first prime of the moduli chain).

func NewMod1ParametersFromLiteral 

func NewMod1ParametersFromLiteral(params Parameters, evm Mod1ParametersLiteral) (Mod1Parameters, error)

NewMod1ParametersFromLiteral generates an Mod1Parameters struct from the Mod1ParametersLiteral struct. The Mod1Parameters struct is to instantiates a Mod1Evaluator, which homomorphically evaluates x mod 1.

func (Mod1Parameters) K 

func (evp Mod1Parameters) K() float64

K return the sine approximation range.

func (Mod1Parameters) LevelStart 

func (evp Mod1Parameters) LevelStart() int

LevelStart returns the starting level of the x mod 1.

func (Mod1Parameters) MessageRatio 

func (evp Mod1Parameters) MessageRatio() float64

MessageRatio returns the pre-set ratio Q[0]/|m|.

func (Mod1Parameters) QDiff 

func (evp Mod1Parameters) QDiff() float64

QDiff return Q[0]/ClosetPow2 This is the error introduced by the approximate division by Q[0].

func (Mod1Parameters) ScFac 

func (evp Mod1Parameters) ScFac() float64

ScFac returns 1/2^r where r is the number of double angle evaluation.

func (Mod1Parameters) ScalingFactor 

func (evp Mod1Parameters) ScalingFactor() rlwe.Scale

ScalingFactor returns scaling factor used during the x mod 1.

type Mod1ParametersLiteral 

type Mod1ParametersLiteral struct {
	LevelStart      int      // Starting level of x mod 1
	LogScale        int      // Log2 of the scaling factor used during x mod 1
	Mod1Type        Mod1Type // Chose between [Sin(2*pi*x)] or [cos(2*pi*x/r) with double angle formula]
	Scaling         float64  // Value by which the output is scaled by
	LogMessageRatio int      // Log2 of the ratio between Q0 and m, i.e. Q[0]/|m|
	K               int      // K parameter (interpolation in the range -K to K)
	Mod1Degree      int      // Degree of f: x mod 1
	DoubleAngle     int      // Number of rescale and double angle formula (only applies for cos and is ignored if sin is used)
	Mod1InvDegree   int      // Degree of f^-1: (x mod 1)^-1
}

Mod1ParametersLiteral a struct for the parameters of the mod 1 procedure. The x mod 1 procedure goal is to homomorphically evaluate a modular reduction by Q[0] (the first prime of the moduli chain) on the encrypted plaintext. This struct is consumed by `NewMod1ParametersLiteralFromLiteral` to generate the `Mod1ParametersLiteral` struct, which notably stores the coefficient of the polynomial approximating the function x mod Q[0].

func (Mod1ParametersLiteral) Depth 

func (evm Mod1ParametersLiteral) Depth() (depth int)

Depth returns the depth required to evaluate x mod 1.

func (Mod1ParametersLiteral) MarshalBinary 

func (evm Mod1ParametersLiteral) MarshalBinary() (data []byte, err error)

MarshalBinary returns a JSON representation of the the target Mod1ParametersLiteral struct on a slice of bytes. See `Marshal` from the `encoding/json` package.

func (*Mod1ParametersLiteral) UnmarshalBinary 

func (evm *Mod1ParametersLiteral) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary reads a JSON representation on the target Mod1ParametersLiteral struct. See `Unmarshal` from the `encoding/json` package.

type Mod1Type 

type Mod1Type uint64

Mod1Type is the type of function/approximation used to evaluate x mod 1.

type Parameters 

type Parameters struct {
	ckks.Parameters
}

func NewParametersFromLiteral 

func NewParametersFromLiteral(paramsLit ParametersLiteral) (Parameters, error)

func (Parameters) Equal 

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

func (Parameters) MarshalBinary 

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

func (Parameters) MarshalJSON 

func (p Parameters) MarshalJSON() (d []byte, err error)

func (*Parameters) UnmarshalBinary 

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

func (*Parameters) UnmarshalJSON 

func (p *Parameters) UnmarshalJSON(d []byte) (err error)

type ParametersLiteral 

type ParametersLiteral ckks.ParametersLiteral

type Polynomial 

type Polynomial he.Polynomial

Polynomial is a type wrapping the type he.Polynomial.

func NewPolynomial 

func NewPolynomial(poly bignum.Polynomial) Polynomial

NewPolynomial creates a new Polynomial from a bignum.Polynomial.

type PolynomialEvaluator 

type PolynomialEvaluator struct {
	Parameters Parameters
	he.EvaluatorForPolynomial
}

PolynomialEvaluator is a wrapper of the he.PolynomialEvaluator. All fields of this struct are public, enabling custom instantiations.

func NewPolynomialEvaluator 

func NewPolynomialEvaluator(params Parameters, eval he.Evaluator) *PolynomialEvaluator

NewPolynomialEvaluator instantiates a new PolynomialEvaluator from a circuit.Evaluator. The default hefloat.Evaluator is compliant to the circuit.Evaluator interface. This method is allocation free.

func (PolynomialEvaluator) Evaluate 

func (eval PolynomialEvaluator) Evaluate(ct *rlwe.Ciphertext, p interface{}, targetScale rlwe.Scale) (opOut *rlwe.Ciphertext, err error)

Evaluate evaluates a polynomial on the input Ciphertext in ceil(log2(deg+1)) levels. Returns an error if the input ciphertext does not have enough levels to carry out the full polynomial evaluation. Returns an error if something is wrong with the scale.

If the polynomial is given in Chebyshev basis, then the user must apply change of basis ct' = scale * ct + offset before the polynomial evaluation to ensure correctness. The values `scale` and `offet` can be obtained from the polynomial with the method .ChangeOfBasis().

pol: a *bignum.Polynomial, *Polynomial or *PolynomialVector targetScale: the desired output scale. This value shouldn't differ too much from the original ciphertext scale. It can for example be used to correct small deviations in the ciphertext scale and reset it to the default scale.

func (PolynomialEvaluator) EvaluateFromPowerBasis 

func (eval PolynomialEvaluator) EvaluateFromPowerBasis(pb he.PowerBasis, p interface{}, targetScale rlwe.Scale) (opOut *rlwe.Ciphertext, err error)

EvaluateFromPowerBasis evaluates a polynomial using the provided PowerBasis, holding pre-computed powers of X. This method is the same as Evaluate except that the encrypted input is a PowerBasis. See Evaluate for additional information.

type PolynomialVector 

type PolynomialVector he.PolynomialVector

PolynomialVector is a type wrapping the type he.PolynomialVector.

func NewPolynomialVector 

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

NewPolynomialVector creates a new PolynomialVector from a list of bignum.Polynomial and a mapping map[poly_index][slots_index] which stores which polynomial has to be evaluated on which slot. Slots that are not referenced in this mapping will be evaluated to zero. User must ensure that a same slot is not referenced twice.

func (PolynomialVector) ChangeOfBasis 

func (p PolynomialVector) ChangeOfBasis(slots int) (scalar, constant []*big.Float)

func (PolynomialVector) Depth 

func (p PolynomialVector) Depth() int

Depth returns the depth of the target PolynomialVector.

Source Files

View all Source files

Directories

Path Synopsis
Package bootstrapping implements bootstrapping for fixed-point encrypted approximate homomorphic encryption over the complex/real numbers.
 Package bootstrapping implements bootstrapping for fixed-point encrypted approximate homomorphic encryption over the complex/real numbers.
Package cosine method is the Go implementation of the polynomial-approximation algorithm by Han and Ki in
 Package cosine method is the Go implementation of the polynomial-approximation algorithm by Han and Ki in

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.