bgv

package
v6.0.0-...-cdc8096 Latest Latest
Warning

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

 Go to latest Published: Mar 7, 2023 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Overview

Package bgv implements a RNS-accelerated BGV homomorphic encryption scheme. It provides modular arithmetic over the integers.

Index

Constants

View Source 
const (
	DefaultNTTFlag = true
)
View Source 
const GaloisGen uint64 = ring.GaloisGen

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

Variables

View Source 
var (
	// PN12QP109 is a set of default parameters with logN=12 and logQP=109
	PN12QP109 = ParametersLiteral{
		LogN: 12,
		Q:    []uint64{0x7ffffec001, 0x8000016001},
		P:    []uint64{0x40002001},
		T:    65537,
	}
	// PN13QP218 is a set of default parameters with logN=13 and logQP=218
	PN13QP218 = ParametersLiteral{
		LogN: 13,
		Q:    []uint64{0x3fffffffef8001, 0x4000000011c001, 0x40000000120001},
		P:    []uint64{0x7ffffffffb4001},
		T:    65537,
	}

	// PN14QP438 is a set of default parameters with logN=14 and logQP=438
	PN14QP438 = ParametersLiteral{
		LogN: 14,
		Q: []uint64{0x100000000060001, 0x80000000068001, 0x80000000080001,
			0x3fffffffef8001, 0x40000000120001, 0x3fffffffeb8001},
		P: []uint64{0x80000000130001, 0x7fffffffe90001},
		T: 65537,
	}

	// PN15QP880 is a set of default parameters with logN=15 and logQP=880
	PN15QP880 = ParametersLiteral{
		LogN: 15,
		Q: []uint64{0x7ffffffffe70001, 0x7ffffffffe10001, 0x7ffffffffcc0001,
			0x400000000270001, 0x400000000350001, 0x400000000360001,
			0x3ffffffffc10001, 0x3ffffffffbe0001, 0x3ffffffffbd0001,
			0x4000000004d0001, 0x400000000570001, 0x400000000660001},
		P: []uint64{0xffffffffffc0001, 0x10000000001d0001, 0x10000000006e0001},
		T: 65537,
	}

	// PN12QP101pq is a set of default (post quantum) parameters with logN=12 and logQP=101
	PN12QP101pq = ParametersLiteral{
		LogN: 12,
		Q:    []uint64{0x800004001, 0x800008001},
		P:    []uint64{0x80014001},
		T:    65537,
	}

	// PN13QP202pq is a set of default (post quantum) parameters with logN=13 and logQP=202
	PN13QP202pq = ParametersLiteral{
		LogN: 13,
		Q:    []uint64{0x7fffffffe0001, 0x7fffffffcc001, 0x3ffffffffc001},
		P:    []uint64{0x4000000024001},
		T:    65537,
	}

	// PN14QP411pq is a set of default (post quantum) parameters with logN=14 and logQP=411
	PN14QP411pq = ParametersLiteral{
		LogN: 14,
		Q:    []uint64{0x7fffffffff18001, 0x8000000000f8001, 0x7ffffffffeb8001, 0x800000000158001, 0x7ffffffffe70001},
		P:    []uint64{0x7ffffffffe10001, 0x400000000068001},
		T:    65537,
	}

	// PN15QP827pq is a set of default (post quantum) parameters with logN=15 and logQP=827
	PN15QP827pq = ParametersLiteral{
		LogN: 15,
		Q: []uint64{0x7ffffffffe70001, 0x7ffffffffe10001, 0x7ffffffffcc0001, 0x7ffffffffba0001, 0x8000000004a0001,
			0x7ffffffffb00001, 0x800000000890001, 0x8000000009d0001, 0x7ffffffff630001, 0x800000000a70001,
			0x7ffffffff510001},
		P: []uint64{0x800000000b80001, 0x800000000bb0001, 0xffffffffffc0001},
		T: 65537,
	}
)
View Source 
var DefaultParams = []ParametersLiteral{PN12QP109, PN13QP218, PN14QP438, PN15QP880}

DefaultParams is a set of default BGV parameters ensuring 128 bit security in the classic setting.

View Source 
var DefaultPostQuantumParams = []ParametersLiteral{PN12QP101pq, PN13QP202pq, PN14QP411pq, PN15QP827pq}

DefaultPostQuantumParams is a set of default BGV parameters ensuring 128 bit security in the post-quantum setting.

Functions

func BsgsIndex 

func BsgsIndex(el interface{}, slots, N1 int) (index map[int][]int, rotN1, rotN2 []int)

BsgsIndex returns the index map and needed rotation for the BSGS matrix-vector multiplication algorithm.

func FindBestBSGSSplit 

func FindBestBSGSSplit(diagMatrix interface{}, maxN int, maxRatio float64) (minN int)

FindBestBSGSSplit finds the best N1*N2 = N for the baby-step giant-step algorithm for matrix multiplication.

func NewCiphertext 

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

func NewDecryptor 

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

func NewEncryptor 

func NewEncryptor(params Parameters, key interface{}) rlwe.Encryptor

func NewKeyGenerator 

func NewKeyGenerator(params Parameters) rlwe.KeyGenerator

func NewPRNGEncryptor 

func NewPRNGEncryptor(params Parameters, key *rlwe.SecretKey) rlwe.PRNGEncryptor

func NewPlaintext 

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

Types

type Encoder 

type Encoder interface {
	Encode(values interface{}, pt *rlwe.Plaintext)
	EncodeNew(values interface{}, level int, scale rlwe.Scale) (pt *rlwe.Plaintext)
	EncodeCoeffs(values []uint64, pt *rlwe.Plaintext)
	EncodeCoeffsNew(values []uint64, level int, scale rlwe.Scale) (pt *rlwe.Plaintext)

	RingT2Q(level int, pT, pQ *ring.Poly)
	RingQ2T(level int, pQ, pT *ring.Poly)

	ScaleUp(level int, pIn, pOut *ring.Poly)
	ScaleDown(level int, pIn, pOut *ring.Poly)

	EncodeRingT(values interface{}, scale rlwe.Scale, pT *ring.Poly)
	DecodeRingT(pT *ring.Poly, scale rlwe.Scale, values interface{})

	DecodeUint(pt *rlwe.Plaintext, values []uint64)
	DecodeInt(pt *rlwe.Plaintext, values []int64)
	DecodeUintNew(pt *rlwe.Plaintext) (values []uint64)
	DecodeIntNew(pt *rlwe.Plaintext) (values []int64)
	DecodeCoeffs(pt *rlwe.Plaintext, values []uint64)
	DecodeCoeffsNew(pt *rlwe.Plaintext) (values []uint64)

	ShallowCopy() Encoder
}

Encoder is an interface for plaintext encoding and decoding operations. It provides methods to embed []uint64 and []int64 types into plaintext polynomials and the inverse operations.

func NewEncoder 

func NewEncoder(params Parameters) Encoder

NewEncoder creates a new encoder from the provided parameters.

type Evaluator 

type Evaluator interface {

	// Add, Sub, Neg ct-ct & ct-pt
	Add(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext)
	AddNew(ctIn *rlwe.Ciphertext, op1 rlwe.Operand) (ctOut *rlwe.Ciphertext)
	Sub(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext)
	SubNew(ctIn *rlwe.Ciphertext, op1 rlwe.Operand) (ctOut *rlwe.Ciphertext)
	Neg(ctIn *rlwe.Ciphertext, ctOut *rlwe.Ciphertext)
	NegNew(ctIn *rlwe.Ciphertext) (ctOut *rlwe.Ciphertext)

	// Add, Mul ct-const
	AddScalar(ctIn *rlwe.Ciphertext, scalar uint64, ctOut *rlwe.Ciphertext)
	AddScalarNew(ctIn *rlwe.Ciphertext, scalar uint64) (ctOut *rlwe.Ciphertext)
	MulScalar(ctIn *rlwe.Ciphertext, scalar uint64, ctOut *rlwe.Ciphertext)
	MulScalarNew(ctIn *rlwe.Ciphertext, scalar uint64) (ctOut *rlwe.Ciphertext)
	MulScalarThenAdd(ctIn *rlwe.Ciphertext, scalar uint64, ctOut *rlwe.Ciphertext)

	// Mul ct-ct & ct-pt
	MulNew(ctIn *rlwe.Ciphertext, op1 rlwe.Operand) (ctOut *rlwe.Ciphertext)
	Mul(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext)
	MulRelinNew(ctIn *rlwe.Ciphertext, op1 rlwe.Operand) (ctOut *rlwe.Ciphertext)
	MulRelin(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext)

	// MulThenAdd ct-ct & ct-pt
	MulThenAdd(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext)
	MulRelinThenAdd(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext)

	// Degree Management
	RelinearizeNew(ctIn *rlwe.Ciphertext) (ctOut *rlwe.Ciphertext)
	Relinearize(ctIn *rlwe.Ciphertext, ctOut *rlwe.Ciphertext)

	// Error and Level management
	Rescale(ctIn, ctOut *rlwe.Ciphertext) (err error)
	DropLevelNew(ctIn *rlwe.Ciphertext, levels int) (ctOut *rlwe.Ciphertext)
	DropLevel(ctIn *rlwe.Ciphertext, levels int)

	// Column & Rows rotations
	RotateColumnsNew(ctIn *rlwe.Ciphertext, k int) (ctOut *rlwe.Ciphertext)
	RotateColumns(ctIn *rlwe.Ciphertext, k int, ctOut *rlwe.Ciphertext)
	RotateRows(ctIn *rlwe.Ciphertext, ctOut *rlwe.Ciphertext)
	RotateRowsNew(ctIn *rlwe.Ciphertext) (ctOut *rlwe.Ciphertext)

	//Polynomial Evaluation
	EvaluatePoly(input interface{}, pol *Polynomial, targetScale rlwe.Scale) (ctOut *rlwe.Ciphertext, err error)
	EvaluatePolyVector(input interface{}, pols []*Polynomial, encoder Encoder, slotIndex map[int][]int, targetScale rlwe.Scale) (ctOut *rlwe.Ciphertext, err error)

	// TODO
	LinearTransformNew(ctIn *rlwe.Ciphertext, linearTransform interface{}) (ctOut []*rlwe.Ciphertext)
	LinearTransform(ctIn *rlwe.Ciphertext, linearTransform interface{}, ctOut []*rlwe.Ciphertext)
	MultiplyByDiagMatrix(ctIn *rlwe.Ciphertext, matrix LinearTransform, c2DecompQP []ringqp.Poly, ctOut *rlwe.Ciphertext)
	MultiplyByDiagMatrixBSGS(ctIn *rlwe.Ciphertext, matrix LinearTransform, c2DecompQP []ringqp.Poly, ctOut *rlwe.Ciphertext)
	InnerSum(ctIn *rlwe.Ciphertext, batch, n int, ctOut *rlwe.Ciphertext)
	Replicate(ctIn *rlwe.Ciphertext, batch, n int, ctOut *rlwe.Ciphertext)

	// Key-Switching
	SwitchKeysNew(ctIn *rlwe.Ciphertext, swk *rlwe.SwitchingKey) (ctOut *rlwe.Ciphertext)
	SwitchKeys(ctIn *rlwe.Ciphertext, swk *rlwe.SwitchingKey, ctOut *rlwe.Ciphertext)
	Automorphism(ctIn *rlwe.Ciphertext, galEl uint64, ctOut *rlwe.Ciphertext)
	AutomorphismHoisted(level int, ctIn *rlwe.Ciphertext, c1DecompQP []ringqp.Poly, galEl uint64, ctOut *rlwe.Ciphertext)
	RotateHoistedLazyNew(level int, rotations []int, c0 *ring.Poly, c2DecompQP []ringqp.Poly) (cOut map[int]rlwe.CiphertextQP)
	Merge(ctIn map[int]*rlwe.Ciphertext) (ctOut *rlwe.Ciphertext)

	// Others
	CheckBinary(op0, op1, opOut rlwe.Operand, opOutMinDegree int) (degree, level int)
	CheckUnary(op0, opOut rlwe.Operand) (degree, level int)
	GetRLWEEvaluator() *rlwe.Evaluator
	BuffQ() [3]*ring.Poly
	ShallowCopy() Evaluator
	WithKey(rlwe.EvaluationKey) Evaluator
}

Evaluator is an interface implementing the public methods of the eval.

func NewEvaluator 

func NewEvaluator(params Parameters, evaluationKey rlwe.EvaluationKey) Evaluator

NewEvaluator creates a new Evaluator, that can be used to do homomorphic operations on ciphertexts and/or plaintexts. It stores a memory buffer and ciphertexts that will be used for intermediate values.

type LinearTransform 

type LinearTransform struct {
	LogSlots int
	N1       int                 // N1 is the number of inner loops of the baby-step giant-step algorithm used in the evaluation (if N1 == 0, BSGS is not used).
	Level    int                 // Level is the level at which the matrix is encoded (can be circuit dependent)
	Scale    rlwe.Scale          // Scale is the scale at which the matrix is encoded (can be circuit dependent)
	Vec      map[int]ringqp.Poly // Vec is the matrix, in diagonal form, where each entry of vec is an indexed non-zero diagonal.
}

LinearTransform is a type for linear transformations on ciphertexts. It stores a plaintext matrix in diagonal form and can be evaluated on a ciphertext by using the evaluator.LinearTransform method.

func GenLinearTransform 

func GenLinearTransform(ecd Encoder, dMat map[int][]uint64, level int, scale rlwe.Scale) LinearTransform

GenLinearTransform allocates and encodes a new LinearTransform struct from the linear transforms' matrix in diagonal form `value`. values.(type) can be either map[int][]complex128 or map[int][]float64. The user must ensure that 1 <= len([]complex128\[]float64) <= 2^logSlots < 2^logN. It can then be evaluated on a ciphertext using evaluator.LinearTransform. Evaluation will use the naive approach (single hoisting and no baby-step giant-step). This method is faster if there is only a few non-zero diagonals but uses more keys.

func GenLinearTransformBSGS 

func GenLinearTransformBSGS(ecd Encoder, dMat map[int][]uint64, level int, scale rlwe.Scale, BSGSRatio float64) (LT LinearTransform)

GenLinearTransformBSGS allocates and encodes a new LinearTransform struct from the linear transforms' matrix in diagonal form `value` for evaluation with a baby-step giant-step approach. values.(type) can be either map[int][]complex128 or map[int][]float64. The user must ensure that 1 <= len([]complex128\[]float64) <= 2^logSlots < 2^logN. LinearTransform types can be be evaluated on a ciphertext using evaluator.LinearTransform. Evaluation will use the optimized approach (double hoisting and baby-step giant-step). This method is faster if there is more than a few non-zero diagonals. BSGSRatio is the maximum ratio between the inner and outer loop of the baby-step giant-step algorithm used in evaluator.LinearTransform. The optimal BSGSRatio value is between 4 and 16 depending on the sparsity of the matrix.

func NewLinearTransform 

func NewLinearTransform(params Parameters, nonZeroDiags []int, level int, BSGSRatio float64) LinearTransform

NewLinearTransform allocates a new LinearTransform with zero plaintexts at the specified level. If BSGSRatio == 0, the LinearTransform is set to not use the BSGS approach. Method will panic if BSGSRatio < 0.

func (*LinearTransform) Encode 

func (LT *LinearTransform) Encode(ecd Encoder, dMat map[int][]uint64, scale rlwe.Scale)

Encode encodes on a pre-allocated LinearTransform the linear transforms' matrix in diagonal form `value`. values.(type) can be either map[int][]complex128 or map[int][]float64. The user must ensure that 1 <= len([]complex128\[]float64) <= 2^logSlots < 2^logN. It can then be evaluated on a ciphertext using evaluator.LinearTransform. Evaluation will use the naive approach (single hoisting and no baby-step giant-step). This method is faster if there is only a few non-zero diagonals but uses more keys.

func (*LinearTransform) Rotations 

func (LT *LinearTransform) Rotations() (rotations []int)

Rotations returns the list of rotations needed for the evaluation of the linear transform.

type Parameters 

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

Parameters represents a parameter set for the BGV cryptosystem. Its fields are private and immutable. See ParametersLiteral for user-specified parameters.

func NewParameters 

func NewParameters(rlweParams rlwe.Parameters, t uint64) (p Parameters, err error)

NewParameters instantiate a set of BGV parameters from the generic RLWE parameters and the BGV-specific ones. It returns the empty parameters Parameters{} and a non-nil error if the specified parameters are invalid.

func NewParametersFromLiteral 

func NewParametersFromLiteral(pl ParametersLiteral) (Parameters, error)

NewParametersFromLiteral instantiate a set of BGV parameters from a ParametersLiteral specification. It returns the empty parameters Parameters{} and a non-nil error if the specified parameters are invalid.

See `rlwe.NewParametersFromLiteral` for default values of the optional fields.

func (Parameters) CopyNew deprecated 

func (p Parameters) CopyNew() Parameters

CopyNew makes a deep copy of the receiver and returns it.

Deprecated: Parameter is now a read-only struct, except for the UnmarshalBinary method: deep copying should only be required to save a Parameter struct before calling its UnmarshalBinary method and it will be deprecated when transitioning to a immutable serialization interface.

func (Parameters) Equals 

func (p Parameters) Equals(other Parameters) bool

Equals compares two sets of parameters for equality.

func (Parameters) LogT 

func (p Parameters) LogT() int

LogT returns log2(plaintext coefficient modulus).

func (Parameters) MarshalBinary 

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

MarshalBinary returns a []byte representation of the parameter set.

func (Parameters) MarshalBinarySize 

func (p Parameters) MarshalBinarySize() int

MarshalBinarySize returns the length of the []byte encoding of the receiver.

func (Parameters) MarshalJSON 

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

MarshalJSON returns a JSON representation of this parameter set. See `Marshal` from the `encoding/json` package.

func (Parameters) ParametersLiteral 

func (p Parameters) ParametersLiteral() ParametersLiteral

ParametersLiteral returns the ParametersLiteral of the target Parameters.

func (Parameters) RingT 

func (p Parameters) RingT() *ring.Ring

RingT returns a pointer to the plaintext ring.

func (Parameters) T 

func (p Parameters) T() uint64

T returns the plaintext coefficient modulus t.

func (*Parameters) UnmarshalBinary 

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

UnmarshalBinary decodes a []byte into a parameter set struct.

func (*Parameters) UnmarshalJSON 

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

UnmarshalJSON reads a JSON representation of a parameter set into the receiver Parameter. See `Unmarshal` from the `encoding/json` package.

type ParametersLiteral 

type ParametersLiteral struct {
	LogN     int
	Q        []uint64
	P        []uint64
	LogQ     []int `json:",omitempty"`
	LogP     []int `json:",omitempty"`
	Pow2Base int
	Sigma    float64
	H        int
	T        uint64 // Plaintext modulus
}

ParametersLiteral is a literal representation of BGV parameters. It has public fields and is used to express unchecked user-defined parameters literally into Go programs. The NewParametersFromLiteral function is used to generate the actual checked parameters from the literal representation.

Users must set the polynomial degree (LogN) and the coefficient modulus, by either setting the Q and P fields to the desired moduli chain, or by setting the LogQ and LogP fields to the desired moduli sizes. Users must also specify the coefficient modulus in plaintext-space (T).

Optionally, users may specify the error variance (Sigma) and secrets' density (H). If left unset, standard default values for these field are substituted at parameter creation (see NewParametersFromLiteral).

func (ParametersLiteral) RLWEParameters 

func (p ParametersLiteral) RLWEParameters() rlwe.ParametersLiteral

RLWEParameters returns the rlwe.ParametersLiteral from the target bfv.ParametersLiteral.

type Polynomial 

type Polynomial struct {
	MaxDeg int
	Coeffs []uint64
	Lead   bool
}

Polynomial is a struct storing the coefficients of a plaintext polynomial that then can be evaluated on the ciphertext.

func NewPoly 

func NewPoly(coeffs []uint64) (p *Polynomial)

NewPoly creates a new Poly from the input coefficients.

func (*Polynomial) Degree 

func (p *Polynomial) Degree() int

Degree returns the degree of the polynomial.

func (*Polynomial) Depth 

func (p *Polynomial) Depth() int

Depth returns the depth needed to evaluate the polynomial.

type PowerBasis 

type PowerBasis struct {
	Value map[int]*rlwe.Ciphertext
}

PowerBasis is a struct storing powers of a ciphertext.

func NewPowerBasis 

func NewPowerBasis(ct *rlwe.Ciphertext) (p *PowerBasis)

NewPowerBasis creates a new PowerBasis.

func (*PowerBasis) GenPower 

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

GenPower generates the n-th power of the power basis, as well as all the necessary intermediate powers if they are not yet present.

func (*PowerBasis) MarshalBinary 

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

MarshalBinary encodes the target on a slice of bytes.

func (*PowerBasis) UnmarshalBinary 

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

UnmarshalBinary decodes a slice of bytes on the target.

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.