lintrans

Documentation

Overview

Package lintrans bundles generic parts of the homomorphic linear transformation circuit.

Index

• func BSGSIndex(nonZeroDiags []int, slots, N1 int) (index map[int][]int, rotN1, rotN2 []int)
• func Encode[T any](encoder schemes.Encoder, diagonals Diagonals[T], ...) (err error)
• func FindBestBSGSRatio(nonZeroDiags []int, maxN int, logMaxRatio int) (minN int)
• func GaloisElements(params rlwe.ParameterProvider, diags []int, ...) (galEls []uint64)
• type Diagonals
  • func (m Diagonals[T]) At(i, slots int) ([]T, error)
  • func (m Diagonals[T]) DiagonalsIndexList() (indexes []int)
• type Evaluator
  • func (eval Evaluator) EvaluateMany(ctIn *rlwe.Ciphertext, linearTransformations []LinearTransformation, ...) (err error)
  • func (eval Evaluator) EvaluateSequential(ctIn *rlwe.Ciphertext, linearTransformations []LinearTransformation, ...) (err error)
  • func (eval Evaluator) MultiplyByDiagMatrix(ctIn *rlwe.Ciphertext, matrix LinearTransformation, BuffDecompQP []ringqp.Poly, ...) (err error)
  • func (eval Evaluator) MultiplyByDiagMatrixBSGS(ctIn *rlwe.Ciphertext, matrix LinearTransformation, ...) (err error)
  • func (eval Evaluator) PreRotatedCiphertextForDiagonalMatrixMultiplication(levelQ, levelP int, ctIn *rlwe.Ciphertext, BuffDecompQP []ringqp.Poly, ...) (err error)
• type LinearTransformation
  • func NewLinearTransformation(params rlwe.ParameterProvider, ltparams Parameters) LinearTransformation
  • func (lt LinearTransformation) BSGSIndex() (index map[int][]int, n1, n2 []int)
  • func (lt LinearTransformation) GaloisElements(params rlwe.ParameterProvider) (galEls []uint64)
• type Parameters

Functions

func BSGSIndex

func BSGSIndex(nonZeroDiags []int, 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 Encode

func Encode[T any](encoder schemes.Encoder, diagonals Diagonals[T], allocated LinearTransformation) (err error)

Encode encodes on a pre-allocated LinearTransformation a set of non-zero diagonals of a matrix representing a linear transformation.

func FindBestBSGSRatio

func FindBestBSGSRatio(nonZeroDiags []int, maxN int, logMaxRatio int) (minN int)

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

func GaloisElements

func GaloisElements(params rlwe.ParameterProvider, diags []int, slots, logBabyStepGianStepRatio int) (galEls []uint64)

GaloisElements returns the list of Galois elements needed for the evaluation of a linear transformation given the index of its non-zero diagonals, the number of slots in the plaintext and the LogBabyStepGiantStepRatio, see Parameters.

Types

type Diagonals

type Diagonals[T any] map[int][]T

func (Diagonals[T]) At

func (m Diagonals[T]) At(i, slots int) ([]T, error)

At returns the i-th non-zero diagonal. Method accepts negative values with the equivalency -i = n - i.

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 Evaluator

type Evaluator struct {
	schemes.Evaluator
}

func (Evaluator) EvaluateMany

func (eval Evaluator) 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 (Evaluator) EvaluateSequential

func (eval Evaluator) 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 evaluates opOut:...M2(M1(M0(ctIn))

func (Evaluator) MultiplyByDiagMatrix

func (eval Evaluator) MultiplyByDiagMatrix(ctIn *rlwe.Ciphertext, matrix LinearTransformation, BuffDecompQP []ringqp.Poly, opOut *rlwe.Ciphertext) (err error)

MultiplyByDiagMatrix multiplies the Ciphertext ctIn by the plaintext matrix and returns the result on the Ciphertext opOut. Memory buffers for the decomposed ciphertext BuffDecompQP, BuffDecompQP must be provided, those are list of poly of ringQ and ringP respectively, each of size params.Beta(). The naive approach is used (single hoisting and no baby-step giant-step), which is faster than MultiplyByDiagMatrixBSGS for matrix of only a few non-zero diagonals but uses more keys.

func (Evaluator) MultiplyByDiagMatrixBSGS

func (eval Evaluator) MultiplyByDiagMatrixBSGS(ctIn *rlwe.Ciphertext, matrix LinearTransformation, ctInPreRot map[int]*rlwe.Element[ringqp.Poly], opOut *rlwe.Ciphertext) (err error)

MultiplyByDiagMatrixBSGS multiplies the Ciphertext "ctIn" by the plaintext matrix "matrix" and returns the result on the Ciphertext "opOut". ctInPreRotated can be obtained with [PreRotatedCiphertextForDiagonalMatrixMultiplication]. The BSGS approach is used (double hoisting with baby-step giant-step), which is faster than MultiplyByDiagMatrix for matrix with more than a few non-zero diagonals and uses significantly less keys.

func (Evaluator) PreRotatedCiphertextForDiagonalMatrixMultiplication

func (eval Evaluator) PreRotatedCiphertextForDiagonalMatrixMultiplication(levelQ, levelP int, ctIn *rlwe.Ciphertext, BuffDecompQP []ringqp.Poly, rots []int, ctPreRot map[int]*rlwe.Element[ringqp.Poly]) (err error)

PreRotatedCiphertextForDiagonalMatrixMultiplication populates ctPreRot with the pre-rotated ciphertext for the rotations rots and deletes rotated ciphertexts that are not in rots.

type LinearTransformation

type LinearTransformation struct {
	*rlwe.MetaData
	LogBabyStepGiantStepRatio int
	N1                        int
	LevelQ                    int
	LevelP                    int
	Vec                       map[int]ringqp.Poly
}

LinearTransformation is a type for linear transformations on ciphertexts. It stores a plaintext matrix in diagonal form and can be evaluated on a ciphertext using a Evaluator.

func NewLinearTransformation

func NewLinearTransformation(params rlwe.ParameterProvider, ltparams Parameters) LinearTransformation

NewLinearTransformation allocates a new LinearTransformation with zero values according to the parameters specified by the Parameters.

func (LinearTransformation) BSGSIndex

func (lt LinearTransformation) BSGSIndex() (index map[int][]int, n1, n2 []int)

BSGSIndex returns the BSGSIndex of the target linear transformation.

func (LinearTransformation) GaloisElements

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

GaloisElements returns the list of Galois elements needed for the evaluation of the linear transformation.

type Parameters

type Parameters struct {
	// DiagonalsIndexList is 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.
	DiagonalsIndexList []int

	// LevelQ is the level at which to encode the linear transformation.
	LevelQ int

	// LevelP is the level of the auxliary prime used during the automorphisms
	// User must ensure that this value is the same as the one used to generate
	// the evaluation keys used to perform the automorphisms.
	LevelP int

	// Scale is the plaintext scale at which to encode the linear transformation.
	Scale rlwe.Scale

	// LogDimensions is the log2 dimensions of the matrix that can be SIMD packed
	// in a single plaintext polynomial.
	// This method is equivalent to params.PlaintextDimensions().
	// Note that the linear transformation is evaluated independently on each rows of
	// the SIMD packed matrix.
	LogDimensions ring.Dimensions

	// LogBabyStepGianStepRatio is the log2 of the ratio n1/n2 for n = n1 * n2 and
	// n is the dimension of the linear transformation. The number of Galois keys required
	// is minimized when this value is 0 but the overall complexity of the homomorphic evaluation
	// can be reduced by increasing the ratio (at the expanse of increasing the number of keys required).
	// If the value returned is negative, then the baby-step giant-step algorithm is not used
	// and the evaluation complexity (as well as the number of keys) becomes O(n) instead of O(sqrt(n)).
	LogBabyStepGiantStepRatio int
}

Parameters is a struct storing the parameterization of a linear transformation.

A homomorphic linear transformations on a ciphertext acts as evaluating:

Ciphertext([1 x n] vector) <- Ciphertext([1 x n] vector) x Plaintext([n x n] matrix)

where n is the number of plaintext slots.

The diagonal representation of a linear transformations is defined by first expressing the linear transformation through its nxn matrix and then traversing the matrix diagonally.

For example, the following nxn for n=4 matrix:

0 1 2 3 (diagonal index) | 1 2 3 0 | | 0 1 2 3 | | 3 0 1 2 | | 2 3 0 1 |

its diagonal traversal representation is comprised of 3 non-zero diagonals at indexes [0, 1, 2]: 0: [1, 1, 1, 1] 1: [2, 2, 2, 2] 2: [3, 3, 3, 3] 3: [0, 0, 0, 0] -> this diagonal is omitted as it is composed only of zero values.

Note that negative indexes can be used and will be interpreted modulo the matrix dimension.

The diagonal representation is well suited for two reasons:

1. It is the effective format used during the homomorphic evaluation.
2. It enables on average a more compact and efficient representation of linear transformations than their matrix representation by being able to only store the non-zero diagonals.

Finally, some metrics about the time and storage complexity of homomorphic linear transformations:

• Storage: #diagonals polynomials mod Q * P
• Evaluation: #diagonals multiplications and 2sqrt(#diagonals) ciphertexts rotations.