bfv

package
v2.2.0 Latest Latest
Warning

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

 Go to latest Published: Jul 15, 2021 License: Apache-2.0 Imports: 9 Imported by: 4

README

BFV

The BFV package is an RNS-accelerated implementation of the Fan-Vercauteren version of Brakerski's scale-invariant homomorphic encryption scheme. It provides modular arithmetic over the integers.

Brief description

This scheme can be used to do arithmetic over   equation.

The plaintext space and the ciphertext space share the same domain

,

with a power of 2.

The batch encoding of this scheme

maps an array of integers to a polynomial with the property:

,

where represents   ![equation](https://latex.codecogs.com/gif.latex?%24%5Codot%24)   a component-wise product,and   ![equation](https://latex.codecogs.com/gif.latex?%24%5Cotimes%24)   represents a nega-cyclic convolution.

Security parameters

equation: the ring dimension, which defines the degree of the cyclotomic polynomial, and the number of coefficients of the plaintext/ciphertext polynomials; it should always be a power of two. This parameter has an impact on both security and performance (security increases with N and performance decreases with N). It should be carefully chosen to suit the intended use of the scheme.

equation: the ciphertext modulus. In Lattigo, it is chosen to be the product of small coprime moduli equation that verify equation in order to enable both the RNS and NTT representation. The used moduli equation are chosen to be of size 50 to 60 bits for the best performance. This parameter has an impact on both security and performance (for a fixed equation, a larger equation implies both lower security and lower performance). It is closely related to equation and should be chosen carefully to suit the intended use of the scheme.

equation: the variance used for the error polynomials. This parameter is closely tied to the security of the scheme (a larger equation implies higher security).

Other parameters

equation: the extended ciphertext modulus. This modulus is used during the multiplication, and it has no impact on the security. It is also defined as the product of small coprime moduli equation and should be chosen such that equation by a small margin (~20 bits). This can be done by using one more small coprime modulus than equation.

equation: the plaintext modulus. This parameter defines the maximum value that a plaintext coefficient can take. If a computation leads to a higher value, this value will be reduced modulo the plaintext modulus. It can be initialized with any value, but in order to enable batching, it must be prime and verify equation. It has no impact on the security.

Choosing security parameters

The BFV scheme supports the standard recommended parameters chosen to offer a security of 128 bits for a secret key with uniform ternary distribution equation, according to the Homomorphic Encryption Standards group (https://homomorphicencryption.org/standard/).

Each set of parameters is defined by the tuple equation:

  • {12, 109, 3.2}
  • {13, 218, 3.2}
  • {14, 438, 3.2}
  • {15, 881, 3.2}

These parameter sets are hard-coded in the file params.go. By default the variance should always be set to 3.2 unless the user is perfectly aware of the security implications of changing this parameter.

Finally, it is worth noting that these security parameters are computed for fully entropic ternary keys (with probability distribution {1/3,1/3,1/3} for values {-1,0,1}). Lattigo uses this fully-entropic key configuration by default. It is possible, though, to generate keys with lower entropy, by modifying their distribution to {(1-p)/2, p, (1-p)/2}, for any p between 0 and 1, which for p>>1/3 can result in low Hamming weight keys (sparse keys). We recall that it has been shown that the security of sparse keys can be considerably lower than that of fully entropic keys, and the BFV security parameters should be re-evaluated if sparse keys are used.

Documentation

Overview

Package bfv implements a RNS-accelerated Fan-Vercauteren version of Brakerski's scale invariant homomorphic encryption scheme. It provides modular arithmetic over the integers.

Index

Constants

View Source 
const GaloisGen uint64 = 5

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,
		T:     65537,
		Q:     []uint64{0x7ffffec001, 0x8000016001},
		P:     []uint64{0x40002001},
		Sigma: rlwe.DefaultSigma,
	}
	// PN13QP218 is a set of default parameters with logN=13 and logQP=218
	PN13QP218 = ParametersLiteral{
		LogN:  13,
		T:     65537,
		Q:     []uint64{0x3fffffffef8001, 0x4000000011c001, 0x40000000120001},
		P:     []uint64{0x7ffffffffb4001},
		Sigma: rlwe.DefaultSigma,
	}

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

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

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

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

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

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

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

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

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

Functions

func GenLiftParams 

func GenLiftParams(ringQ *ring.Ring, t uint64) (deltaMont []uint64)

GenLiftParams generates the lifting parameters.

func NewKeyGenerator 

func NewKeyGenerator(params Parameters) rlwe.KeyGenerator

NewKeyGenerator creates a rlwe.KeyGenerator instance from the BFV parameters.

func NewPublicKey 

func NewPublicKey(params Parameters) (pk *rlwe.PublicKey)

NewPublicKey returns an allocated BFV public with zero values.

func NewRelinearizationKey added in v2.2.0 

func NewRelinearizationKey(params Parameters, maxRelinDegree int) *rlwe.RelinearizationKey

NewRelinearizationKey returns an allocated BFV public relinearization key with zero value for each degree in [2 < maxRelinDegree].

func NewRotationKeySet added in v2.2.0 

func NewRotationKeySet(params Parameters, galoisElements []uint64) *rlwe.RotationKeySet

NewRotationKeySet returns an allocated set of BFV public rotation keys with zero values for each galois element (i.e., for each supported rotation).

func NewSecretKey 

func NewSecretKey(params Parameters) (sk *rlwe.SecretKey)

NewSecretKey returns an allocated BFV secret key with zero values.

func NewSwitchingKey 

func NewSwitchingKey(params Parameters) *rlwe.SwitchingKey

NewSwitchingKey returns an allocated BFV public switching key with zero values.

Types

type Ciphertext 

type Ciphertext struct {
	*rlwe.Ciphertext
}

Ciphertext is a *ring.Poly array representing a polynomial of degree > 0 with coefficients in R_Q.

func NewCiphertext 

func NewCiphertext(params Parameters, degree int) (ciphertext *Ciphertext)

NewCiphertext creates a new ciphertext parameterized by degree, level and scale.

func NewCiphertextRandom 

func NewCiphertextRandom(prng utils.PRNG, params Parameters, degree int) (ciphertext *Ciphertext)

NewCiphertextRandom generates a new uniformly distributed ciphertext of degree, level and scale.

func (*Ciphertext) CopyNew added in v2.2.0 

func (ct *Ciphertext) CopyNew() *Ciphertext

CopyNew creates a deep copy of the receiver ciphertext and returns it.

func (*Ciphertext) GetDataLen 

func (ciphertext *Ciphertext) GetDataLen(WithMetaData bool) (dataLen int)

GetDataLen returns the length in bytes of the target Ciphertext.

func (*Ciphertext) MarshalBinary 

func (ciphertext *Ciphertext) MarshalBinary() (data []byte, err error)

MarshalBinary encodes a Ciphertext in a byte slice.

func (*Ciphertext) UnmarshalBinary 

func (ciphertext *Ciphertext) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary decodes a previously marshaled Ciphertext in the target Ciphertext.

type Decryptor 

type Decryptor interface {
	DecryptNew(ciphertext *Ciphertext) (plaintext *Plaintext)
	Decrypt(ciphertext *Ciphertext, plaintext *Plaintext)
}

Decryptor is an interface wrapping a rlwe.Decryptor.

func NewDecryptor 

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

NewDecryptor instantiates a Decryptor for the BFV scheme.

type Encoder 

type Encoder interface {
	EncodeUint(coeffs []uint64, pt *Plaintext)
	EncodeUintRingT(coeffs []uint64, pt *PlaintextRingT)
	EncodeUintMul(coeffs []uint64, pt *PlaintextMul)
	EncodeInt(coeffs []int64, pt *Plaintext)
	EncodeIntRingT(coeffs []int64, pt *PlaintextRingT)
	EncodeIntMul(coeffs []int64, pt *PlaintextMul)

	ScaleUp(*PlaintextRingT, *Plaintext)
	ScaleDown(pt *Plaintext, ptRt *PlaintextRingT)
	RingTToMul(ptRt *PlaintextRingT, ptmul *PlaintextMul)
	MulToRingT(pt *PlaintextMul, ptRt *PlaintextRingT)

	DecodeRingT(pt interface{}, ptRt *PlaintextRingT)
	DecodeUint(pt interface{}, coeffs []uint64)
	DecodeInt(pt interface{}, coeffs []int64)
	DecodeUintNew(pt interface{}) (coeffs []uint64)
	DecodeIntNew(pt interface{}) (coeffs []int64)
}

Encoder is an interface for plaintext encoding and decoding operations. It provides methods to embed []uint64 and []int64 types into the various plaintext types and the inverse operations. It also provides methodes to convert between the different plaintext types. The different plaintext types represent different embeddings of the message in the polynomial space. This relation is illustrated in The figure below:

[]uint64 --- Encoder.EncodeUintRingT(.) -┬-> PlaintextRingT -┬-> Encoder.ScaleUp(.) -----> Plaintext []uint64 --- Encoder.EncodeIntRingT(.) --┘ └-> Encoder.RingTToMul(.) ---> PlaintextMul

The different plaintext types have different efficiency-related caracteristics that we summarize in the Table below. For more information about the different plaintext types, see plaintext.go.

Relative efficiency of operation 

-----------------------------------------------------------------------

| | PlaintextRingT | Plaintext | PlaintextMul | 

-----------------------------------------------------------------------

| Encoding/Decoding | Faster | Slower | Slower | | Memory size | Smaller | Larger | Larger | | Ct-Pt Add / Sub | Slower | Faster | N/A | | Ct-Pt Mul | Faster | Slower | Much Faster | 

-----------------------------------------------------------------------

func NewEncoder 

func NewEncoder(params Parameters) Encoder

NewEncoder creates a new encoder from the provided parameters.

type Encryptor 

type Encryptor interface {
	Encrypt(plaintext *Plaintext, ciphertext *Ciphertext)
	EncryptNew(plaintext *Plaintext) *Ciphertext
	EncryptFromCRP(plaintext *Plaintext, crp *ring.Poly, ctOut *Ciphertext)
	EncryptFromCRPNew(plaintext *Plaintext, crp *ring.Poly) *Ciphertext
}

Encryptor an encryption interface for the BFV scheme.

func NewEncryptor added in v2.2.0 

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

NewEncryptor instantiates a new Encryptor for the BFV scheme. The key argument can be either a *rlwe.PublicKey or a *rlwe.SecretKey.

func NewFastEncryptor added in v2.2.0 

func NewFastEncryptor(params Parameters, key *rlwe.PublicKey) Encryptor

NewFastEncryptor instantiates a new Encryptor for the BFV scheme. This encryptor's Encrypt method first encrypts zero in Q and then adds the plaintext. This method is faster than the normal encryptor but result in a noisier ciphertext.

type Evaluator 

type Evaluator interface {
	Add(op0, op1 Operand, ctOut *Ciphertext)
	AddNew(op0, op1 Operand) (ctOut *Ciphertext)
	AddNoMod(op0, op1 Operand, ctOut *Ciphertext)
	AddNoModNew(op0, op1 Operand) (ctOut *Ciphertext)
	Sub(op0, op1 Operand, ctOut *Ciphertext)
	SubNew(op0, op1 Operand) (ctOut *Ciphertext)
	SubNoMod(op0, op1 Operand, ctOut *Ciphertext)
	SubNoModNew(op0, op1 Operand) (ctOut *Ciphertext)
	Neg(op Operand, ctOut *Ciphertext)
	NegNew(op Operand) (ctOut *Ciphertext)
	Reduce(op Operand, ctOut *Ciphertext)
	ReduceNew(op Operand) (ctOut *Ciphertext)
	MulScalar(op Operand, scalar uint64, ctOut *Ciphertext)
	MulScalarNew(op Operand, scalar uint64) (ctOut *Ciphertext)
	Mul(op0 *Ciphertext, op1 Operand, ctOut *Ciphertext)
	MulNew(op0 *Ciphertext, op1 Operand) (ctOut *Ciphertext)
	Relinearize(ct0 *Ciphertext, ctOut *Ciphertext)
	RelinearizeNew(ct0 *Ciphertext) (ctOut *Ciphertext)
	SwitchKeys(ct0 *Ciphertext, switchKey *rlwe.SwitchingKey, ctOut *Ciphertext)
	SwitchKeysNew(ct0 *Ciphertext, switchkey *rlwe.SwitchingKey) (ctOut *Ciphertext)
	RotateColumnsNew(ct0 *Ciphertext, k int) (ctOut *Ciphertext)
	RotateColumns(ct0 *Ciphertext, k int, ctOut *Ciphertext)
	RotateRows(ct0 *Ciphertext, ctOut *Ciphertext)
	RotateRowsNew(ct0 *Ciphertext) (ctOut *Ciphertext)
	InnerSum(ct0 *Ciphertext, ctOut *Ciphertext)
	ShallowCopy() Evaluator
	WithKey(rlwe.EvaluationKey) Evaluator
}

Evaluator is an interface implementing the public methodes 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 small pool of polynomials and ciphertexts that will be used for intermediate values.

func NewEvaluators added in v2.2.0 

func NewEvaluators(params Parameters, evaluationKey rlwe.EvaluationKey, n int) []Evaluator

NewEvaluators creates n evaluators sharing the same read-only data-structures.

type Operand 

type Operand interface {
	El() *rlwe.Ciphertext
	Degree() int
}

Operand is a common interface for Ciphertext and Plaintext.

type Parameters 

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

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

func NewParameters added in v2.2.0 

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

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

func NewParametersFromLiteral added in v2.2.0 

func NewParametersFromLiteral(pl ParametersLiteral) (Parameters, error)

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

func (Parameters) CopyNew added in v2.2.0 

func (p Parameters) CopyNew() Parameters

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

func (Parameters) Equals 

func (p Parameters) Equals(other Parameters) bool

Equals compares two sets of parameters for equality.

func (Parameters) MarshalBinary 

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

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

func (Parameters) MarshalBinarySize added in v2.2.0 

func (p Parameters) MarshalBinarySize() int

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

func (Parameters) MarshalJSON added in v2.2.0 

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

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

func (Parameters) RingQMul added in v2.2.0 

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

RingQMul returns a pointer to the ring of the extended basis for multiplication

func (Parameters) RingT added in v2.2.0 

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 added in v2.2.0 

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 added in v2.2.0 

type ParametersLiteral struct {
	LogN  int // Log Ring degree (power of 2)
	Q     []uint64
	P     []uint64
	LogQ  []int   `json:",omitempty"`
	LogP  []int   `json:",omitempty"`
	Sigma float64 // Gaussian sampling standard deviation
	T     uint64  // Plaintext modulus
}

ParametersLiteral is a literal representation of BFV 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.

type Plaintext 

type Plaintext struct {
	*rlwe.Plaintext
}

Plaintext is a Element with only one Poly. It represents a Plaintext element in R_q that is the result of scaling the corresponding element of R_t up by Q/t. This is a generic all-purpose type of plaintext: it will work with for all operations. It is however less compact than PlaintextRingT and will result in less efficient Ciphert-Plaintext multiplication than PlaintextMul. See bfv/encoder.go for more information on plaintext types.

func NewPlaintext 

func NewPlaintext(params Parameters) *Plaintext

NewPlaintext creates and allocates a new plaintext in RingQ (multiple moduli of Q). The plaintext will be in RingQ and scaled by Q/t. Slower encoding and larger plaintext size

type PlaintextMul added in v2.1.0 

type PlaintextMul Plaintext

PlaintextMul represents a plaintext element in R_q, in NTT and Montgomery form, but without scale up by Q/t. A PlaintextMul is a special-purpose plaintext for efficient Ciphertext-Plaintext multiplication. However, other operations on plaintexts are not supported. See bfv/encoder.go for more information on plaintext types.

func NewPlaintextMul added in v2.1.0 

func NewPlaintextMul(params Parameters) *PlaintextMul

NewPlaintextMul creates and allocates a new plaintext optimized for ciphertext x plaintext multiplication. The plaintext will be in the NTT and Montgomery domain of RingQ and not scaled by Q/t.

type PlaintextRingT added in v2.1.0 

type PlaintextRingT Plaintext

PlaintextRingT represents a plaintext element in R_t. This is the most compact representation of a plaintext, but performing operations have the extra-cost of performing the scaling up by Q/t. See bfv/encoder.go for more information on plaintext types.

func NewPlaintextRingT added in v2.1.0 

func NewPlaintextRingT(params Parameters) *PlaintextRingT

NewPlaintextRingT creates and allocates a new plaintext in RingT (single modulus T). The plaintext will be in RingT.

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.