Lattigo v5.0.2

• Fixed bfv.Evaluator.ShallowCopy() that wasn't shallowcopying the basis extender, which would result in correctness error when using multiple shallowcopied evaluators concurrently and the scale invariant tensoring (BFV-style multiplication).

Lattigo v5.0.1

• Fixed panics in lattigo/ring benchmarks
• Uniformized benchmarks in lattigo/schemes
• Added benchmarks in lattigo/he/hebin, lattigo/he/heint and lattigo/he/hefloat

Lattigo v5.0.0

Release Overview

The following sections give an overview of the main changes brought by the v5. This list is not exhaustive and we recommend taking a look at the CHANGELOG.md for the full list of changes.

Reorganization of the Library

The library has been fully reorganized to provide a better user experience tailored around plaintext spaces and functionalities rather than schemes. The new organization of the packages is as follows, from highest to lowest level:

• he: The highest level package, intended to be the user-facing part of the library for most applications. It contains three sub-packages which provide homomorphic encryption functionalities based on the plaintext domain:
  • hefloat: Homomorphic encryption with fixed-point approximate encrypted arithmetic over the real or complex numbers. This package is intended to be used for encrypted arithmetic with floating point numbers and is implemented as a wrapper over the schemes/ckks package, with additional functionalities.
    • bootstrapping: Bootstrapping for fixed-point approximate arithmetic over the real and complex numbers.
  • heint: Homomorphic encryption for modular encrypted arithmetic over the integers. This package is intended to be used for encrypted arithmetic over integers and is implemented as wrapper of the schemes/bgv package, with additional functionalities.
  • hebin: Homomorphic encryption for binary arithmetic. It currently implements blind rotations (a.k.a Lookup Tables) (previously rgsw/lut).
• mhe: This package implements scheme-agnostic RLWE-based multiparty key-generation and proxy re-encryption (previously drlwe).
  • mhefloat: Homomorphic decryption from RLWE to Linear-Secret-Sharing-Shares (LSSS) and homomorphic re-encryption from LSSS to RLWE, as well as interactive bootstrapping for he/hefloat (previously dckks).
  • mheint: Homomorphic decryption from RLWE to Linear-Secret-Sharing-Shares (LSSS) and homomorphic re-encryption from LSSS to RLWE, as well as interactive bootstrapping for he/heint (previously dbfv and dbgv).
• schemes: This package regroups all the homomorphic encryption schemes implemented in the library, which are the backend of the he package. It currently contains the following schemes:
  • bgv: A Full-RNS generalization of the Brakerski-Fan-Vercauteren scale-invariant (BFV) and Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption schemes.
  • bfv: A Full-RNS variant of the Brakerski-Fan-Vercauteren scale-invariant homomorphic encryption scheme. This scheme is instantiated via a wrapper of the bgv scheme.
  • ckks: A Full-RNS variant of the Homomorphic Encryption for Arithmetic for Approximate Numbers (HEAAN, a.k.a. CKKS) scheme.
• core : This package implements the core homomorphic cryptographic functionalities of the library which are common to all the RLWE and LWE schemes.
  • rlwe: A package that implements the generic cryptographic functionalities and operations that are common to all RLWE-based homomorphic encryption schemes.
  • rgsw: A package that provides support for Ring-GSW encryption and the external product.
• ring: A package implementing arithmetic for power-of-two cyclotomic rings.
• utils: A package implementing various utility functions, secure sampling, serialization, and linear algebra.

Modular Implementation of High Level Functionalities

The package lattigo/he provides scheme agnostic interfaces for basic encoding, homomorphic operations and generic implementations for higher level operations such as polynomial evaluation and linear transformations. These are used to implement scheme specific functionalities in he/hebin, he/heint and he/hefloat in a way that enables user to easily provide custom implementations of sub-routines (e.g. adding concurrency).

API Reduction & Uniformization

The bfv, bgv and ckks encoders and evaluators have had their API reduced, simplified and uniformized across schemes. This enables the definition of scheme-agnostic interfaces in the he package. The API reduction mostly consolidates redundant methods into a single one. For example, the ckks.Evaluator used to have the methods

• MultByConst(ctIn *rlwe.Ciphertext, constant interface{}, ctOut *rlwe.Ciphertext)
• MultByGaussianInteger(ctIn *rlwe.Ciphertext, cReal, cImag interface{}, ctOut *rlwe.Ciphertext)
• MultByi(ctIn *rlwe.Ciphertext, ctOut *rlwe.Ciphertext)
• DivByi(ctIn *rlwe.Ciphertext, ctOut *rlwe.Ciphertext)
• Mul/MulRelin(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext).

These have been consolidated into the single method Mul/MulRelin(ctIn *rlwe.Ciphertext, op1 rlwe.Operand, ctOut *rlwe.Ciphertext).

This change renders scheme-specific interfaces such as bgv.Encoder or ckks.Evaluator obsolete, so they have been removed. Their functionality is now covered by the scheme-agnostic interfaces he.Encoder and he.Evaluator.

Improved Cryptographic Parameterization

The previous implementation did only allow a ternary distribution for the secret, and a Gaussian distribution for the error. We have removed this restriction and it is now possible to use custom distributions for the secret and error, as long as they satisfy the ring.DistributionParameters interface. Available distributions are ring.DiscreteGaussian, ring.Ternary, and ring.Uniform.

Additionally, the sampling and related interfaces have been improved. Notably, the interface ring.Sampler has been added and it is possible to instantiate a sampler directly from a ring.DistributionParameters.

Finally, the ring.GaussianSampler has been extended to support large-norm Gaussian sampling, enabling proper smudging.

Improvements to the ring.Ring Object

The ring.Ring object was previously a single struct storing all the pre-computed constants (e.g. NTT Tables) as double slices, indexed by their respective prime. This required a large struct that was difficult to re-slice and didn't represent well the underlying mathematical object of an RNS decomposed large ring. The new ring.Ring object is now much closer to the mathematical definition and is composed of ring.SubRing, one per prime. These ring.SubRing define all the pre-computed constants for their respective prime and they operate on slices modulo this prime.

Improved Plaintext/Ciphertext Structs & Metadata

Plaintext and ciphertexts are now wrappers of the rlwe.Element generic type, which contains a pointer to the rlwe.MetaData struct. This struct comprises the fields rlwe.CiphertextMetaData and rlwe.PlaintextMetaData, which contain metadata about the state of the ciphertext and plaintext.

Hybrid BFV/BGV Scheme

The implementation of the BGV scheme has been entirely rewritten to provide a unified variant of the BFV and BGV schemes. The proposed implementation provides all the functionalities of the BFV and BGV schemes under a unified framework. This is enabled by the equivalence between the LSB and MSB encodings when the plaintext modulus $t$ is coprime with the ciphertext modulus $Q$. In other words, if $t$ is coprime with $Q$, then the BFV and BGV schemes are indistinguishable up to a factor of $t^{-1} \mod Q$.

In this hybrid implementation, the BGV plaintext is scaled by $t^{-1} \mod Q$ (MSB encoding) instead of the error being scaled by $t$ (LSB encoding). This approach enables an implementation that behaves exactly like both schemes in terms of noise growth and performance depending on which multiplication is used: the regular tensoring (BGV/CKKS) or the scale-invariant tensoring (BFV).

For backwards compatibility, the standalone implementation of the BFV scheme still exists, but it is now instantiated as a wrapper of the new hybrid BGV scheme which essentially restricts the multiplication to only the scale invariant tensoring. The functionalities and noise growth are identical to the original BFV implementation, except that the plaintext modulus must be coprime with the ciphertext modulus.

High-Precision Approximate Homomorphic Encryption & Advanced Arithmetic

The implementation of the CKKS scheme now supports a scaling factor of up to 120 bits, enabling high precision fixed-point approximate arithmetic. Additionally the following advanced arithmetic operations have been improved/added in the package he/hefloat:

• Polynomial Evaluation
• Linear Transformations
• Homomorphic Encoding/Decoding
• Homomorphic Modular Reduction
• Full domain division
• Composite Minimax Polynomial Evaluation
• Sign and Step piece-wise functions
• Min/Max

Improvements to the Bootstrapping for Approximate Homomorphic Encryption

The generic interface he.Bootstrapper[CiphertextType any] has been added to the package he, enabling easy plug-and-play black-box bootstrapping in any implementation defining the bootstrapping via this interface.

The usability and range of parameterization of the bootstrapping for fixed-point approximate homomorphic encryption over real and complex numbers has been substantially improved:

• Decorrelation between the bootstrapping parameters (parameters used during the bootstrapping) and the residual parameters (parameters outside of the bootstrapping). The user only needs to provide the residual parameters and the parameterization of the bootstrapping, and the constructor will do the rest, managing these parameters without exposing them directly to the user.
• Support for the Conjugate-Invariant ring.
• Support for batch-bootstrapping of ciphertexts of lower degree and/or with sparse packing with automatic repacking/unpacking.
• High parameterization granularity of 16 tunable parameters.
• Full support of META-BTS, providing arbitrary precision iterated bootstrapping by reserving only one additional sm...

Lattigo v4.1.0

Merge pull request #298 from tuneinsight/v4.1.0

v4.1.0

Lattigo v4.0.0

• Added BGV/DBGV schemes.
• ALL: added default parameters for LogN=11 and LogN=10.
• RING: prime generation no longer skips the first candidate.
• RING: reworked marshalling of ring.Poly object. The new available methods are:
  • ring.Poly now has a .Buff 1-dimensional slice which is the only heavy allocation of a ring.Poly. The .Coeffs 2-dimensional slice is a re-slicing of .Buff.
  • GetDataLen64 and GetDataLen32: gets the length in bytes of an encoded ring.Poly object.
  • WriteTo64 and WriteTo32: encodes a ring.Poly object on a pre-allocated slice of bytes.
  • WriteCoeffsTo64 and WriteCoeffsTo32: encodes a slice of coefficients on a pre-allocated slice of bytes.
  • DecodeCoeffs64 and DecodeCoeffs32: decodes a slice of bytes on a slice of coefficients.
  • DecodePoly64 and DecodePoly32: decodes a slice of bytes on a pre-allocated ring.Poly object.
• RING: renamed ring.Poly.Degree() to ring.Poly.N() for consistency.
• RING: removed ring.Poly.LenModuli() deprecated method.
• RING: changed ring.NewPoly to take the level as argument instead of the number of moduli, for consistency.
• RLWE: added several types of ciphertexts:
  • rlwe.CiphertextQP represents a ciphertext that is encrypted in the extended ring R_QP.
  • rlwe.GadgetCiphertext represents an encryption in the extended ring R_QP of a plaintext that is decomposed in the CRT and power-of-two basis (e.g., plublic switching keys).
• RLWE: changed representation of rlwe.PublicKey types which are now stored in Montgomerry form, consistently with all other key types.
• RLWE: changed rlwe.SwitchingKey type to use rlwe.GadgetCiphertext internally.
• RLWE: generalized rlwe.KeySwitcher into rlwe.Evaluator, which provides new functionalities:
  • DecomposeNTT: decomposes a polynomial modulo the special RNS basis and extends its basis from Q to QP.
  • DecomposeSingleNTT: decomposes a polynomial modulo a single power of the special RNS basis and extends its basis from Q to QP.
  • ExpandRLWE: extracts each coefficient of a RLWE sample to the degree-0 coefficient of multiple RLWE samples.
  • MergeRLWE: merges the degree-0 coefficient of multiple RLWE samples into a single RLWE sample.
  • GadgetProduct: evaluates ring.Poly x gadget.Ciphertext -> RLWE, where gadget.Ciphertext is a matrix of RLWE samples encrypting scaled plaintext by the special RNS basis and a modulus P.
  • GadgetProductNoModDown: evaluates ring.Poly x gadget.Ciphertext -> RLWE but without the division by P (the result is given mod QP).
  • GadgetProductSinglePAndBitDecompNoModDown: evaluates ring.Poly x gadget.Ciphertext -> RLWE, where gadget.Ciphertext is a matrix of RLWE samples encrypting scaled plaintext by the special RNS basis along with a base-2 basis and an optional prime P.
  • Relinearize: reduces the degree of a rlwe.Ciphertext to one by homomorphically evaluating the decryption of the higher-degree terms.
  • KeySwitch: homomorphically re-encrypts a rlwe.Ciphertext under a new secret.
  • KeyswitchHoisted: homomorphically re-encrypts a rlwe.Ciphertext under a series of new secrets, returning a new ciphertext for each secret.
  • KeyswitchHoistedNoModDown: homomorphically re-encrypts a rlwe.Ciphertext under a series of new secrets, returning a new ciphertext for each secret, but without the division by P (the result is given mod QP).
  • Automorphism: homomorphically evaluates the map X -> X^k.
  • AutomorphismHoisted: homomorphically evaluates multiple maps of the type X -> X^k, returning a new ciphertext for each map.
  • AutomorphismHoistedNoModDown: homomorphically evaluates multiple maps of the type X -> X^k, returning a new ciphertext for each map, but without the division by P (result is given mod QP).
  • Trace: homomorphically evaluates the map X -> sum((-1)^i * X^{i*n+1}) for n <= i < N.
  • ExternalProduct: evaluates rlwe.Ciphertext x rgsw.Ciphertext -> rlwe.Ciphertext.
• RLWE: re-enabled bit-decomposition, on top of RNS decomposition, for the inner-product between rlwe.Ciphertext and gadget.Ciphertext.
  • This functionality can be enabled by setting Pow2Base to the desired power of two basis.
  • This functionality can be used in conjunction with the RNS hybrid decomposition (with a modulus P) only when P is composed of a single prime.
  • This functionality is disabled if Pow2Base is set to zero (default value).
• RLWE: enabled instantiation of rlwe.Parameters without the modulus P.
• RLWE: revamped the rlwe.Encryptor interface and implementing structs:
  • Added the .EncryptZero method to generate encryptions of zeros.
  • The .Encrypt and .EncryptZero now accept ct interface{} as their ciphertext argument and determine the type of encryption to be performed according to the runtime type of ct.
• RLWE: added the PRNGEncryptor type, which supports secret-key encryption from a user-specified PRNG.
• RLWE: rlwe.KeyGenerator now uses an rlwe.Encryptor internally, to generate secret keys, encryption keys and evaluation keys.
• RLWE: extracted the rlwe/ringqp sub-package which provides the ringqp.Ring and ringqp.Poly types to respectively replace the former types rlwe.RingQP and rlwe.PolyQP.
• DRLWE: added the Thresholdizer and Combiner types for t-out-of-N-threshold schemes through Shamir secret-sharing.
• DRLWE: added a README.md providing package overview and usage instructions.
• DRLWE: removed the obsolete CollectivePublicKeyGenerator, RelinearizationKeyGenerator, RotationKeyGenerator, PublicKeySwitchingProtocol and KeySwitchingProtocol interfaces.
• DRLWE: renamed AggregateShare methods to AggregateShares.
• RGSW: added package rgsw, which provides a partial implementation of the RLWE-based RGSW encryption scheme. This incluides:
  • rgsw.Encryptor and the rgsw.Ciphertext types.
  • rgsw.Evaluator to support the external product RLWE x RGSW -> RLWE.
  • rgsw/lut sub-package that provides evaluation of Look-Up-Tables (LUT) on rlwe.Ciphertext types.
• BFV: renamed Encoder.DecodeRingT to Encoder.SwitchToRingT to better reflect the purpose of the method.
• CKKS: fixed MulAndAdd correctness for non-identical inputs.
• CKKS: added advanced.EncodingMatrixLiteral.RepackImag2Real optional field to repack the imaginary part into the right n real slots.
• CKKS: Trace now only takes as input the logSlots of the encrypted plaintext.
• CKKS: replaced the public variable .Scale with .scale, it can now be accessed with .Scale() and set to a new value with .SetScale().
• CKKS: renamed the methods ScalingFactor and SetScalingFactor of the interface Operand to Scale and SetScale respectively.
• CKKS/bootstrapping: renamed method Bootstrapp to Bootstrap.
• BFV/CKKS: key-switching functionalities (such as rotations, relinearization and key-switching) are now all based on the rlwe.Evaluator.
• BFV/CKKS: the parameters now are based on the sub-type rlwe.Parameters.
• BFV/CKKS: removed deprecated methods EncryptFromCRP and EncryptFromCRPNew, users should now use the PRNGEncryptor interface.
• BFV/CKKS: fixed a panic happening during the benchmark testing.
• DBFV/DCKKS: removed the dbfv/dckks.CKGProtocol, dbfv/dckks.RKGProtocol and dbfv/dckks.RTGProtocol types. Users should use the corresponding drlwe types instead.
• DBFV/DCKKS: MaskedTransformFunc is now a struct and takes as additional input to the linear transform two Boolean flags to parameterize if the decoding/encoding process must be done before/after the linear transform.
• DBFV/DCKKS: refresh and maskedTransform protocols now allow the user to specify the output parameters, enabling parameter switching.
• DCKKS: fixed dckks.RefreshProtocol correctness when the output scale is different from the input scale.
• Examples: added examples/ckks/advanced/lut, which is an example that performs homomorphic decoding -> LUT -> homomorphic encoding on a ckks.Ciphertext.
• Examples: removed examples/ckks/advanced/rlwe_lwe_bridge_LHHMQ20, which is replaced by examples/ckks/advanced/lut.
• Examples: removed examples/rlwe/lwe_bridge since the code of this example is now part of rlwe.Evaluator and showcased in examples/ckks/advanced/lut.
• CI: revamped Makefile to no longer require github.com/dedis/coding and integrated linting/vet checks.

Lattigo v3.0.5

• CKKS: Baby-Step Giant-Step Polynomial Evaluation Algorithm (BSGSPEA):
  • Added PolynomialBasis, a struct to generate powers of monomials. This struct can be marshalled.
  • Renamed former PolynomialBasis enumerated type to BasisType.
  • EvaluatePoly and EvaluatePolyVector now both accept pre-computed PolynomialBasis as input in addition to Ciphertext.
  • Fixed correctness error and panic when a non-relinearized ciphertext and a plaintext were given to Mul and MulAndAdd.
  • Fixed automatic-scale matching in BSGS that wasn't reliably ensuring that scales between two ciphertext to be added was the same.
  • Improved BSGSPEA with lazy relinearization and lazy rescaling.
  • Overall the precision of the BSGSPEA is greatly improved and its complexity is reduced. This also improves the precision of the bootstrapping.

Lattigo v3.0.4

• CKKS: updated the bootstrapping circuit to use the key-encapsulation mechanism of Bootstrapping for Approximate Homomorphic Encryption with Negligible Failure-Probability by Using Sparse-Secret Encapsulation. The previous bootstrapping circuit can be run by setting EphemeralSecretDensity=0.
• BFV: added the Evaluator.Rescale and Evaluator.RescaleTo methods to switch BFV ciphertexts to lower levels.
• BFV: all Evaluator methods on ciphertext support all arithmetic operations at lower levels, but require that operands are at the same level.
• BFV: the plaintext modulus T can now equal to the level-zero modulus Q[0] (i.e., be a factor of the ciphertext modulus Q).
• BFV: added the methods NewCiphertextLvl, NewPlaintextLvl, NewPlaintextMulLvl, Evaluator.AddScalar and Evaluator.MulScalarAndAdd.
• BFV: merged []uint64 and []int64 plaintext encoding methods (e.g. EncodeUint and EncodeInt are replaced by Encode) and added the respective [...]New methods.
• BFV: added the methods EvaluatePoly and EvaluatePolyVector for homomorphic polynomial evaluation.
• BFV/RING: moved RNSScaler from ring to bfv.
• RING: removed deprecated SimpleScaler.

Lattigo v3.0.2

• Fixed sparse ternary sampler to properly sample on non-zero poly.

Lattigo v3.0.1

Changelog

• RLWE/CKKS/BFV: added the H field and HammingWeight method in parameters-related structs, to specify distribution of all secrets in the schemes.
• RLWE/DRLWE: all secrets in the ternary distribution are now sampled with a fixed hamming weight, according to the parameters.
• CKKS: encoder is now about 3.5x faster (without taking the NTT into account).

Lattigo v3.0.0

Changelog

• RING: renamed FastBasisExtender to BasisExtender.
• RING: .PolyToBigint[...](*) now take as input gap which defines the multiples of X^{i*gap} to reconstruct.
• RLWE: removed FastEncryptor. Encryption without rescaling by P is now automatically used by Encryptor if no P is specified in the parameters.
• RLWE: NewAdditiveShareBigint now takes as input the size of the share.
• RLWE/CKKS/BFV: added .ShallowCopy(), .WithKey() (shallow copy with new key) to Encryptor and Decryptor.
• BFV/CKKS: added .ShallowCopy() to Encoder and EncoderBigComplex (only CKKS).
• DRLWE/DCKKS/DBFV: added .ShallowCopy() to all protocols.
• DLRWE/DCKKS/DBFV: protocols drlwe.CKSProtocol and drlwe.PCKSProtocol and sub-protocols based on these two protocols now only take a polynomial as input for the share generation instead of the full ciphertext.
• DRLWE/DCKKS/DBFV: uniformized API of share generation and aggregation to .GenShare(*) and .AggregateShare(*).