bgv

package
v5.0.2 Latest Latest
Warning

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

 Go to latest Published: Nov 28, 2023 License: Apache-2.0 Imports: 9 Imported by: 7

README

BGV

The BGV package provides a unified RNS-accelerated variant of the Brakerski-Fan-Vercauteren (BFV) scale invariant homomorphic encryption scheme and Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption scheme. It enables SIMD modular arithmetic over encrypted vectors or integers.

Implementation Notes

The proposed implementation provides all the functionalities of the BFV and BGV schemes under a unified scheme. This is enabled by the equivalence between the LSB and MSB encoding when T is coprime to Q (Appendix A of https://eprint.iacr.org/2013/372).

Intuition

The textbook BGV scheme encodes the plaintext in the LSB and the encryption is done by scaling the error by $T$:

\textsf{Encrypt}_{s}(\textsf{Encode}(m)) = [-as + m + Te, a]_{Q_{\ell}}

where $Q_{\ell} = \prod_{i=0}^{L} q_{i}$ in the RNS variant of the scheme.

The decoding process is then carried out by taking the decrypted plaintext $[m + Te]{Q{\ell}}$ modulo $T$ which vanishes the error.

We observe that the only non-linear part of the BGV scheme is its modulus switching operation and that this operation is identical to a CKKS-style rescaling (quantization of the ciphertext by $\frac{1}{q_{\ell}}$) with a pre- and post-processing:

  1. Multiply the ciphertext by $T^{-1}\mod Q_{\ell}$ (switch from LSB to MSB encoding)
T^{-1} \cdot [-as + m + eT, a]_{Q_{\ell}}\rightarrow[-bs + mT^{-1} + e, b]_{Q_{\ell}}
  1. Apply the Full-RNS CKKS-style rescaling (division by $q_{\ell} = Q_{\ell}/Q_{\ell-1}$):
\lfloor q_{\ell}^{-1}\cdot[-bs + mT^{-1} + e, b]_{Q_{\ell}}\rceil\rightarrow[-cs + mq_{\ell}^{-1}T^{-1} + \lfloor e/q_{\ell}\rfloor + e_{\textsf{round}}, c]_{Q_{\ell-1}}
  1. Multiply the ciphertext by $T \mod Q_{\ell-1}$ (switch from MSB to LSB encoding)
T\cdot[-cs + mq_{\ell}^{-1}T^{-1} + \lfloor e/q_{\ell}\rceil + e_{\textsf{round}}, c]_{Q_{\ell-1}}\rightarrow[-ds + mq_{\ell}^{-1} + T(\lfloor e/q_{\ell}\rceil + e_{\textsf{round}}), d]_{Q_{\ell-1}}

The process returns a new ciphertext modulo $Q_{\ell-1}$ where the error has been quantized by $q_{\ell}$ and the message multiplied by a factor of $q_{\ell}^{-1} \mod T$.

Since the modulus switch is the only non-linear part of the BGV scheme, we can move steps 1) and 2) to the encoding and decoding steps respectively, i.e. instead of scaling the error during the encryption by $T$ we scale the plaintext by $T^{-1}\mod Q_{\ell}$ during the encoding.

The tensoring operations have to be slightly modified to take into account the additional multiples of $T^{-1}$ (but this can be done for free when operands are switched in the Montgomery domain).

Functionalities

The above change enables an implementation of the BGV scheme with an MSB encoding, which is essentially the BFV scheme. In other words, if $T$ is coprime with $Q$ then the BFV and BGV encoding (and thus scheme) are indistinguishable up to a plaintext scaling factor of $T^{-1}\mod Q$.

This unified scheme can also be seen as a variant of the BGV scheme with two tensoring operations:

  • The BGV-style tensoring with a noise growth proportional to the current noise,
  • The BFV-style tensoring with a noise growth invariant to the current noise.

References

  1. Practical Bootstrapping in Quasilinear Time (https://eprint.iacr.org/2013/372)
  2. A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes (https://eprint.iacr.org/2016/510)
  3. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme (https://eprint.iacr.org/2018/117)

Documentation

Overview

Package bgv implements a unified RNS-accelerated version of the Fan-Vercauteren version of the Brakerski's scale invariant homomorphic encryption scheme (BFV) and Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption scheme. It provides modular arithmetic over the integers.

Index

Constants

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).

View Source 
const (
	NTTFlag = true
)

Variables

View Source 
var (
	// ExampleParameters128BitLogN14LogQP438 is an example parameters set with logN=14, logQP=438
	// and a 16-bit plaintext modulus, offering 128-bit of security.
	ExampleParameters128BitLogN14LogQP438 = ParametersLiteral{
		LogN: 14,
		Q: []uint64{0x10000048001, 0x20008001, 0x1ffc8001,
			0x20040001, 0x1ffc0001, 0x1ffb0001,
			0x20068001, 0x1ff60001, 0x200b0001,
			0x200d0001, 0x1ff18001, 0x200f8001},
		P:                []uint64{0x10000140001, 0x7ffffb0001},
		PlaintextModulus: 0x10001,
	}
)

Functions

func MulScaleInvariant 

func MulScaleInvariant(params Parameters, a, b rlwe.Scale, level int) (c rlwe.Scale)

MulScaleInvariant returns c = a * b / (-Q[level] mod PlaintextModulus), where a, b are the input scale, level the level at which the operation is carried out and and c is the new scale after performing the invariant tensoring (BFV-style).

func NewCiphertext 

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

NewCiphertext allocates a new rlwe.Ciphertext.

inputs:

  • params: an rlwe.ParameterProvider interface
  • degree: the degree of the ciphertext
  • level: the level of the Ciphertext

output: a newly allocated rlwe.Ciphertext of the specified degree and level.

func NewDecryptor 

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

NewDecryptor instantiates a new rlwe.Decryptor.

inputs:

  • params: an rlwe.ParameterProvider interface
  • key: *rlwe.SecretKey

output: an rlwe.Decryptor instantiated with the provided key.

func NewEncryptor 

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

NewEncryptor instantiates a new rlwe.Encryptor.

inputs:

  • params: an rlwe.ParameterProvider interface
  • key: *rlwe.SecretKey or *rlwe.PublicKey

output: an rlwe.Encryptor instantiated with the provided key.

func NewKeyGenerator 

func NewKeyGenerator(params Parameters) *rlwe.KeyGenerator

NewKeyGenerator instantiates a new rlwe.KeyGenerator.

inputs:

  • params: an rlwe.ParameterProvider interface

output: an rlwe.KeyGenerator.

func NewPlaintext 

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

NewPlaintext allocates a new rlwe.Plaintext.

inputs:

  • params: an rlwe.ParameterProvider interface
  • level: the level of the plaintext

output: a newly allocated rlwe.Plaintext at the specified level.

Note: the user can update the field `MetaData` to set a specific scaling factor, plaintext dimensions (if applicable) or encoding domain, before encoding values on the created plaintext.

Types

type Encoder 

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

Encoder is a structure that stores the parameters to encode values on a plaintext in a SIMD (Single-Instruction Multiple-Data) fashion.

func NewEncoder 

func NewEncoder(parameters Parameters) *Encoder

NewEncoder creates a new Encoder from the provided parameters.

func (Encoder) Decode 

func (ecd Encoder) Decode(pt *rlwe.Plaintext, values IntegerSlice) (err error)

Decode decodes a plaintext on an IntegerSlice mod PlaintextModulus of size at most N, where N is the smallest value satisfying PlaintextModulus = 1 mod 2N.

func (Encoder) DecodeRingT 

func (ecd Encoder) DecodeRingT(pT ring.Poly, scale rlwe.Scale, values IntegerSlice) (err error)

DecodeRingT decodes a polynomial pT with coefficients modulo the plaintext modulu PlaintextModulus on an InterSlice at the given scale.

func (Encoder) Embed 

func (ecd Encoder) Embed(values IntegerSlice, scaleUp bool, metadata *rlwe.MetaData, polyOut interface{}) (err error)

Embed is a generic method to encode an IntegerSlice on ringqp.Poly or *ring.Poly. If scaleUp is true, then the values will to be multiplied by PlaintextModulus^{-1} mod Q after being encoded on the polynomial. Encoding is done according to the metadata. Accepted polyOut.(type) are a ringqp.Poly and *ring.Poly

func (Encoder) Encode 

func (ecd Encoder) Encode(values IntegerSlice, pt *rlwe.Plaintext) (err error)

Encode encodes an IntegerSlice of size at most N, where N is the smallest value satisfying PlaintextModulus = 1 mod 2N, on a pre-allocated plaintext.

func (Encoder) EncodeRingT 

func (ecd Encoder) EncodeRingT(values IntegerSlice, scale rlwe.Scale, pT ring.Poly) (err error)

EncodeRingT encodes an IntegerSlice at the given scale on a polynomial pT with coefficients modulo the plaintext modulus PlaintextModulus.

func (Encoder) GetRLWEParameters 

func (ecd Encoder) GetRLWEParameters() *rlwe.Parameters

GetRLWEParameters returns the underlying rlwe.Parameters of the target object.

func (Encoder) RingQ2T 

func (ecd Encoder) RingQ2T(level int, scaleDown bool, pQ, pT ring.Poly)

RingQ2T takes pQ in base Q[level] and writes it in base PlaintextModulus on pT. If scaleUp is true, the values of pQ are multiplied by PlaintextModulus mod Q[level] before being converted into the base PlaintextModulus.

func (Encoder) RingT2Q 

func (ecd Encoder) RingT2Q(level int, scaleUp bool, pT, pQ ring.Poly)

RingT2Q takes pT in base PlaintextModulus and writes it in base Q[level] on pQ. If scaleUp is true, multiplies the values of pQ by PlaintextModulus^{-1} mod Q[level].

func (Encoder) ShallowCopy 

func (ecd Encoder) ShallowCopy() *Encoder

ShallowCopy returns a lightweight copy of the target object that can be used concurrently with the original object.

type Evaluator 

type Evaluator struct {
	*rlwe.Evaluator
	*Encoder
	// contains filtered or unexported fields
}

Evaluator is a struct that holds the necessary elements to perform the homomorphic operations between ciphertexts and/or plaintexts. It also holds a memory buffer used to store intermediate computations.

func NewEvaluator 

func NewEvaluator(parameters Parameters, evk rlwe.EvaluationKeySet) *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.

func (Evaluator) Add 

func (eval Evaluator) Add(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

Add adds op1 to op0 and returns the result in opOut. inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly] and the scales of op0, op1 and opOut do not match, then a scale matching operation will be automatically carried out to ensure that addition is performed between operands of the same scale. This scale matching operation will increase the noise by a small factor. For this reason it is preferable to ensure that all operands are already at the same scale when calling this method.

func (Evaluator) AddNew 

func (eval Evaluator) AddNew(op0 *rlwe.Ciphertext, op1 rlwe.Operand) (opOut *rlwe.Ciphertext, err error)

AddNew adds op1 to op0 and returns the result on a new *rlwe.Ciphertext opOut. inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)

If op1 is an rlwe.ElementInterface[ring.Poly] and the scales of op0 and op1 not match, then a scale matching operation will be automatically carried out to ensure that addition is performed between operands of the same scale. This scale matching operation will increase the noise by a small factor. For this reason it is preferable to ensure that all operands are already at the same scale when calling this method.

func (Evaluator) ApplyEvaluationKeyNew 

func (eval Evaluator) ApplyEvaluationKeyNew(op0 *rlwe.Ciphertext, evk *rlwe.EvaluationKey) (opOut *rlwe.Ciphertext, err error)

ApplyEvaluationKeyNew re-encrypts op0 under a different key and returns the result in a new opOut. It requires a EvaluationKey, which is computed from the key under which the Ciphertext is currently encrypted, and the key under which the Ciphertext will be re-encrypted. The procedure will return an error if either op0.Degree() or opOut.Degree() != 1.

func (Evaluator) BuffQ 

func (eval Evaluator) BuffQ() [3]ring.Poly

BuffQ returns a pointer to the internal memory buffer buffQ.

func (Evaluator) DropLevel 

func (eval Evaluator) DropLevel(op0 *rlwe.Ciphertext, levels int)

DropLevel reduces the level of op0 by levels. No rescaling is applied during this procedure.

func (Evaluator) GetParameters 

func (eval Evaluator) GetParameters() *Parameters

GetParameters returns a pointer to the underlying bgv.Parameters.

func (Evaluator) GetRLWEParameters 

func (eval Evaluator) GetRLWEParameters() *rlwe.Parameters

func (Evaluator) MatchScalesAndLevel 

func (eval Evaluator) MatchScalesAndLevel(ct0, opOut *rlwe.Ciphertext)

MatchScalesAndLevel updates the both input ciphertexts to ensures that their scale matches. To do so it computes t0 * a = opOut * b such that:

  • ct0.Scale * a = opOut.Scale: make the scales match.
  • gcd(a, PlaintextModulus) == gcd(b, PlaintextModulus) == 1: ensure that the new scale is not a zero divisor if PlaintextModulus is not prime.
  • |a+b| is minimal: minimize the added noise by the procedure.

func (Evaluator) Mul 

func (eval Evaluator) Mul(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

Mul multiplies op0 with op1 without relinearization and using standard tensoring (BGV/CKKS-style), and returns the result in opOut. This tensoring increases the noise by a multiplicative factor of the plaintext and noise norms of the operands and will usually require to be followed by a rescaling operation to avoid an exponential growth of the noise from subsequent multiplications. The procedure will return an error if either op0 or op1 are have a degree higher than 1. The procedure will return an error if opOut.Degree != op0.Degree + op1.Degree.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the level of opOut will be updated to min(op0.Level(), op1.Level())
  • the scale of opOut will be updated to op0.Scale * op1.Scale

func (Evaluator) MulNew 

func (eval Evaluator) MulNew(op0 *rlwe.Ciphertext, op1 rlwe.Operand) (opOut *rlwe.Ciphertext, err error)

MulNew multiplies op0 with op1 without relinearization and using standard tensoring (BGV/CKKS-style), and returns the result in a new *rlwe.Ciphertext opOut. This tensoring increases the noise by a multiplicative factor of the plaintext and noise norms of the operands and will usually require to be followed by a rescaling operation to avoid an exponential growth of the noise from subsequent multiplications. The procedure will return an error if either op0 or op1 are have a degree higher than 1.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the degree of opOut will be op0.Degree() + op1.Degree()
  • the level of opOut will be to min(op0.Level(), op1.Level())
  • the scale of opOut will be to op0.Scale * op1.Scale

func (Evaluator) MulRelin 

func (eval Evaluator) MulRelin(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

MulRelin multiplies op0 with op1 with relinearization and using standard tensoring (BGV/CKKS-style), and returns the result in opOut. This tensoring increases the noise by a multiplicative factor of the plaintext and noise norms of the operands and will usually require to be followed by a rescaling operation to avoid an exponential growth of the noise from subsequent multiplications. The procedure will return an error if either op0.Degree or op1.Degree > 1. The procedure will return an error if opOut.Degree != op0.Degree + op1.Degree. The procedure will return an error if the evaluator was not created with an relinearization key.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the level of opOut will be updated to min(op0.Level(), op1.Level())
  • the scale of opOut will be updated to op0.Scale * op1.Scale

func (Evaluator) MulRelinNew 

func (eval Evaluator) MulRelinNew(op0 *rlwe.Ciphertext, op1 rlwe.Operand) (opOut *rlwe.Ciphertext, err error)

MulRelinNew multiplies op0 with op1 with relinearization and and using standard tensoring (BGV/CKKS-style), returns the result in a new *rlwe.Ciphertext opOut. This tensoring increases the noise by a multiplicative factor of the plaintext and noise norms of the operands and will usually require to be followed by a rescaling operation to avoid an exponential growth of the noise from subsequent multiplications. The procedure will return an error if either op0.Degree or op1.Degree > 1. The procedure will return an error if the evaluator was not created with an relinearization key.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the level of opOut will be to min(op0.Level(), op1.Level())
  • the scale of opOut will be to op0.Scale * op1.Scale

func (Evaluator) MulRelinScaleInvariant 

func (eval Evaluator) MulRelinScaleInvariant(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

MulRelinScaleInvariant multiplies op0 with op1 with relinearization and using scale invariant tensoring (BFV-style), and returns the result in opOut. This tensoring increases the noise by a constant factor regardless of the current noise, thus no rescaling is required with subsequent multiplications if they are performed with the invariant tensoring procedure. Rescaling can still be useful to reduce the size of the ciphertext, once the noise is higher than the prime that will be used for the rescaling or to ensure that the noise is minimal before using the regular tensoring. The procedure will return an error if either op0.Degree or op1.Degree > 1. The procedure will return an error if the evaluator was not created with an relinearization key.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the level of opOut will be updated to min(op0.Level(), op1.Level())
  • the scale of opOut will be to op0.Scale * op1.Scale * (-Q mod PlaintextModulus)^{-1} mod PlaintextModulus

func (Evaluator) MulRelinScaleInvariantNew 

func (eval Evaluator) MulRelinScaleInvariantNew(op0 *rlwe.Ciphertext, op1 rlwe.Operand) (opOut *rlwe.Ciphertext, err error)

MulRelinScaleInvariantNew multiplies op0 with op1 with relinearization and using scale invariant tensoring (BFV-style), and returns the result in a new *rlwe.Ciphertext opOut. This tensoring increases the noise by a constant factor regardless of the current noise, thus no rescaling is required with subsequent multiplications if they are performed with the invariant tensoring procedure. Rescaling can still be useful to reduce the size of the ciphertext, once the noise is higher than the prime that will be used for the rescaling or to ensure that the noise is minimal before using the regular tensoring. The procedure will return an error if either op0.Degree or op1.Degree > 1. The procedure will return an error if the evaluator was not created with an relinearization key.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the level of opOut will be to min(op0.Level(), op1.Level())
  • the scale of opOut will be to op0.Scale * op1.Scale * (-Q mod PlaintextModulus)^{-1} mod PlaintextModulus

func (Evaluator) MulRelinThenAdd 

func (eval Evaluator) MulRelinThenAdd(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

MulRelinThenAdd multiplies op0 with op1 using standard tensoring and with relinearization, and adds the result on opOut. The procedure will return an error if either op0.Degree() or op1.Degree() > 1. The procedure will return an error if either op0 == opOut or op1 == opOut.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly] and opOut.Scale != op1.Scale * op0.Scale, then a scale matching operation will be automatically carried out to ensure that addition is performed between operands of the same scale. This scale matching operation will increase the noise by a small factor. For this reason it is preferable to ensure that opOut.Scale == op1.Scale * op0.Scale when calling this method.

func (Evaluator) MulScaleInvariant 

func (eval Evaluator) MulScaleInvariant(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

MulScaleInvariant multiplies op0 with op1 without relinearization and using scale invariant tensoring (BFV-style), and returns the result in opOut. This tensoring increases the noise by a constant factor regardless of the current noise, thus no rescaling is required with subsequent multiplications if they are performed with the invariant tensoring procedure. Rescaling can still be useful to reduce the size of the ciphertext, once the noise is higher than the prime that will be used for the rescaling or to ensure that the noise is minimal before using the regular tensoring. The procedure will return an error if either op0.Degree or op1.Degree > 1. The procedure will return an error if the evaluator was not created with an relinearization key.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the level of opOut will be updated to min(op0.Level(), op1.Level())
  • the scale of opOut will be to op0.Scale * op1.Scale * (-Q mod T)^{-1} mod T

func (Evaluator) MulScaleInvariantNew 

func (eval Evaluator) MulScaleInvariantNew(op0 *rlwe.Ciphertext, op1 rlwe.Operand) (opOut *rlwe.Ciphertext, err error)

MulScaleInvariantNew multiplies op0 with op1 without relinearization and using scale invariant tensoring (BFV-style), and returns the result in a new *rlwe.Ciphertext opOut. This tensoring increases the noise by a constant factor regardless of the current noise, thus no rescaling is required with subsequent multiplications if they are performed with the invariant tensoring procedure. Rescaling can still be useful to reduce the size of the ciphertext, once the noise is higher than the prime that will be used for the rescaling or to ensure that the noise is minimal before using the regular tensoring. The procedure will return an error if either op0.Degree or op1.Degree > 1. The procedure will return an error if the evaluator was not created with an relinearization key.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)

If op1 is an rlwe.ElementInterface[ring.Poly]:

  • the level of opOut will be to min(op0.Level(), op1.Level())
  • the scale of opOut will be to op0.Scale * op1.Scale * (-Q mod PlaintextModulus)^{-1} mod PlaintextModulus

func (Evaluator) MulThenAdd 

func (eval Evaluator) MulThenAdd(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

MulThenAdd multiplies op0 with op1 using standard tensoring and without relinearization, and adds the result on opOut. The procedure will return an error if either op0.Degree() or op1.Degree() > 1. The procedure will return an error if either op0 == opOut or op1 == opOut.

inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly] and opOut.Scale != op1.Scale * op0.Scale, then a scale matching operation will be automatically carried out to ensure that addition is performed between operands of the same scale. This scale matching operation will increase the noise by a small factor. For this reason it is preferable to ensure that opOut.Scale == op1.Scale * op0.Scale when calling this method.

func (Evaluator) RelinearizeNew 

func (eval Evaluator) RelinearizeNew(op0 *rlwe.Ciphertext) (opOut *rlwe.Ciphertext, err error)

RelinearizeNew applies the relinearization procedure on op0 and returns the result in a new opOut.

func (Evaluator) Rescale 

func (eval Evaluator) Rescale(op0, opOut *rlwe.Ciphertext) (err error)

Rescale divides (rounded) op0 by the last prime of the moduli chain and returns the result on opOut. This procedure divides the noise by the last prime of the moduli chain while preserving the MSB-plaintext bits. The procedure will return an error if:

  • op0.Level() == 0 (the input ciphertext is already at the last prime)
  • opOut.Level() < op0.Level() - 1 (not enough space to store the result)

The scale of opOut will be updated to op0.Scale * qi^{-1} mod PlaintextModulus where qi is the prime consumed by the rescaling operation.

func (Evaluator) RotateColumns 

func (eval Evaluator) RotateColumns(op0 *rlwe.Ciphertext, k int, opOut *rlwe.Ciphertext) (err error)

RotateColumns rotates the columns of op0 by k positions to the left and returns the result in opOut. The procedure will return an error if the corresponding Galois key has not been generated and attributed to the evaluator. The procedure will return an error if either op0.Degree() or opOut.Degree() != 1.

func (Evaluator) RotateColumnsNew 

func (eval Evaluator) RotateColumnsNew(op0 *rlwe.Ciphertext, k int) (opOut *rlwe.Ciphertext, err error)

RotateColumnsNew rotates the columns of op0 by k positions to the left, and returns the result in a newly created element. The procedure will return an error if the corresponding Galois key has not been generated and attributed to the evaluator. The procedure will return an error if op0.Degree() != 1.

func (Evaluator) RotateHoistedLazyNew 

func (eval Evaluator) RotateHoistedLazyNew(level int, rotations []int, op0 *rlwe.Ciphertext, c2DecompQP []ringqp.Poly) (opOut map[int]*rlwe.Element[ringqp.Poly], err error)

RotateHoistedLazyNew applies a series of rotations on the same ciphertext and returns each different rotation in a map indexed by the rotation. Results are not rescaled by P.

func (Evaluator) RotateRows 

func (eval Evaluator) RotateRows(op0, opOut *rlwe.Ciphertext) (err error)

RotateRows swaps the rows of op0 and returns the result in op1. The procedure will return an error if the corresponding Galois key has not been generated and attributed to the evaluator. The procedure will return an error if either op0.Degree() or op1.Degree() != 1.

func (Evaluator) RotateRowsNew 

func (eval Evaluator) RotateRowsNew(op0 *rlwe.Ciphertext) (opOut *rlwe.Ciphertext, err error)

RotateRowsNew swaps the rows of op0 and returns the result in a new opOut. The procedure will return an error if the corresponding Galois key has not been generated and attributed to the evaluator. The procedure will return an error if op0.Degree() != 1.

func (Evaluator) ShallowCopy 

func (eval Evaluator) ShallowCopy() *Evaluator

ShallowCopy creates a shallow copy of this Evaluator in which the read-only data-structures are shared with the receiver.

func (Evaluator) Sub 

func (eval Evaluator) Sub(op0 *rlwe.Ciphertext, op1 rlwe.Operand, opOut *rlwe.Ciphertext) (err error)

Sub subtracts op1 to op0 and returns the result in opOut. inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)
  • opOut: an *rlwe.Ciphertext

If op1 is an rlwe.ElementInterface[ring.Poly] and the scales of op0, op1 and opOut do not match, then a scale matching operation will be automatically carried out to ensure that the subtraction is performed between operands of the same scale. This scale matching operation will increase the noise by a small factor. For this reason it is preferable to ensure that all operands are already at the same scale when calling this method.

func (Evaluator) SubNew 

func (eval Evaluator) SubNew(op0 *rlwe.Ciphertext, op1 rlwe.Operand) (opOut *rlwe.Ciphertext, err error)

SubNew subtracts op1 to op0 and returns the result in a new *rlwe.Ciphertext opOut. inputs:

  • op0: an *rlwe.Ciphertext
  • op1:
  • rlwe.ElementInterface[ring.Poly]
  • *big.Int, uint64, int64, int
  • []uint64 or []int64 (of size at most N where N is the smallest integer satisfying PlaintextModulus = 1 mod 2N)

If op1 is an rlwe.ElementInterface[ring.Poly] and the scales of op0, op1 and opOut do not match, then a scale matching operation will be automatically carried out to ensure that the subtraction is performed between operands of the same scale. This scale matching operation will increase the noise by a small factor. For this reason it is preferable to ensure that all operands are already at the same scale when calling this method.

func (Evaluator) WithKey 

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

WithKey creates a shallow copy of this Evaluator in which the read-only data-structures are shared with the receiver but the EvaluationKey is evaluationKey.

type Integer 

type Integer interface {
	int64 | uint64
}

type IntegerSlice 

type IntegerSlice interface {
}

IntegerSlice is an empty interface whose goal is to indicate that the expected input should be []Integer. See Integer for information on the type constraint.

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. See the ParametersLiteral type for more details on the BGV parameters.

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 and other details on the BGV parameters.

func (Parameters) Equal 

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

Equal compares two sets of parameters for equality.

func (Parameters) GaloisElementForColRotation 

func (p Parameters) GaloisElementForColRotation(k int) uint64

GaloisElementForColRotation returns the Galois element for generating the automorphism phi(k): X -> X^{5^k mod 2N} mod (X^{N} + 1), which acts as a column-wise cyclic rotation by k position to the left on batched plaintexts.

Example: Recall that batched plaintexts are 2xN/2 matrices, thus given the following plaintext matrix:

[a, b, c, d][e, f, g, h]

a rotation by k=3 will change the plaintext to:

[d, a, b, d][h, e, f, g]

Providing a negative k will change direction of the cyclic rotation do the right.

func (Parameters) GaloisElementForRowRotation 

func (p Parameters) GaloisElementForRowRotation() uint64

GaloisElementForRowRotation returns the Galois element for generating the automorphism X -> X^{-1 mod NthRoot} mod (X^{N} + 1). This automorphism acts as a swapping the rows of the plaintext algebra when the plaintext is batched.

Example: Recall that batched plaintexts are 2xN/2 matrices, thus given the following plaintext matrix:

[a, b, c, d][e, f, g, h]

a row rotation will change the plaintext to:

[e, f, g, h][a, b, c, d]

func (Parameters) GaloisElementsForExpand 

func (p Parameters) GaloisElementsForExpand(logN int) []uint64

GaloisElementsForExpand returns the list of Galois elements required to perform the `Expand` operation with parameter `logN`.

func (Parameters) GaloisElementsForInnerSum 

func (p Parameters) GaloisElementsForInnerSum(batch, n int) (galEls []uint64)

GaloisElementsForInnerSum returns the list of Galois elements necessary to apply the method `InnerSum` operation with parameters `batch` and `n`.

func (Parameters) GaloisElementsForPack 

func (p Parameters) GaloisElementsForPack(logN int) []uint64

GaloisElementsForPack returns the list of Galois elements required to perform the `Pack` operation.

func (Parameters) GaloisElementsForReplicate 

func (p Parameters) GaloisElementsForReplicate(batch, n int) (galEls []uint64)

GaloisElementsForReplicate returns the list of Galois elements necessary to perform the `Replicate` operation with parameters `batch` and `n`.

func (Parameters) GaloisElementsForTrace 

func (p Parameters) GaloisElementsForTrace(logN int) []uint64

GaloisElementsForTrace returns the list of Galois elements requored for the for the `Trace` operation. Trace maps X -> sum((-1)^i * X^{i*n+1}) for 2^{LogN} <= i < N.

func (Parameters) GetRLWEParameters 

func (p Parameters) GetRLWEParameters() *rlwe.Parameters

GetRLWEParameters returns a pointer to the underlying RLWE parameters.

func (Parameters) LogMaxDimensions 

func (p Parameters) LogMaxDimensions() ring.Dimensions

LogMaxDimensions returns the log2 of maximum dimension of the matrix that can be SIMD packed in a single plaintext polynomial.

func (Parameters) LogMaxSlots 

func (p Parameters) LogMaxSlots() int

LogMaxSlots returns the total number of entries (`slots`) that a plaintext can store. This value is obtained by summing all log dimensions from LogDimensions.

func (Parameters) LogT 

func (p Parameters) LogT() float64

LogT returns log2(plaintext coefficient modulus).

func (Parameters) MarshalBinary 

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

MarshalBinary returns a []byte representation of the parameter set. The representation corresponds to the JSON representation obtained from MarshalJSON.

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) MaxDimensions 

func (p Parameters) MaxDimensions() ring.Dimensions

MaxDimensions returns the maximum dimension of the matrix that can be SIMD packed in a single plaintext polynomial.

func (Parameters) MaxSlots 

func (p Parameters) MaxSlots() int

MaxSlots returns the total number of entries (`slots`) that a plaintext can store. This value is obtained by multiplying all dimensions from MaxDimensions.

func (Parameters) ParametersLiteral 

func (p Parameters) ParametersLiteral() ParametersLiteral

ParametersLiteral returns the ParametersLiteral of the target Parameters.

func (Parameters) PlaintextModulus 

func (p Parameters) PlaintextModulus() uint64

PlaintextModulus returns the plaintext coefficient modulus t.

func (Parameters) RingQMul 

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

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

func (Parameters) RingT 

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

RingT returns a pointer to the plaintext ring.

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
	LogNthRoot       int
	Q                []uint64
	P                []uint64
	LogQ             []int `json:",omitempty"`
	LogP             []int `json:",omitempty"`
	Xe               ring.DistributionParameters
	Xs               ring.DistributionParameters
	PlaintextModulus 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). This modulus must be an NTT-friendly prime in the plaintext space: it must be equal to 1 modulo 2n where n is the plaintext ring degree (i.e., the plaintext space has n slots).

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) GetRLWEParametersLiteral 

func (p ParametersLiteral) GetRLWEParametersLiteral() rlwe.ParametersLiteral

GetRLWEParametersLiteral returns the rlwe.ParametersLiteral from the target bgv.ParametersLiteral. See the ParametersLiteral type for details on the BGV parameters.

func (*ParametersLiteral) UnmarshalJSON 

func (p *ParametersLiteral) UnmarshalJSON(b []byte) (err error)

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.