Lattigo v5.0.0

[Pro7ech]

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 made for 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 more close to the mathematical definition and is composed ring.SubRing, one per prime. These ring.SubRing define all the pre-computed constant for their respective prime and operate on slice modulo this prime.

Improved Plaintext/Ciphertext Structs & Metadata

Plaintext and ciphertexts are now wrapper 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 complex and real 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 small prime.

Examples for the bootstrapping can be found in examples/he/hefloat/bootstrapping.

Refactoring of the Evaluation-Keys

Up to v4 the evaluation keys were defined by the struct rlwe.SwitchingKey. Although applying an evaluation key on a ciphertext does indeed serves the purpose of public re-encryption, user feedback has shown that this naming approach can lead to confusion and lacks an intuitive hierarchy among the different objects which are derived from the rlwe.SwitchingKey struct (and does not provide a comprehensive mapping with the literature). This is notably caused by the fact that public re-encryption is hardly ever used to change the access structure of a ciphertext, but as a mean to ensure ciphertext compactness and decryption correctness during the different evaluation phases of a circuit.

To remedy to this issue, the struct rlwe.SwitchingKey has been renamed rlwe.EvaluationKey, and a comprehensive documentation on the generation, usage and all capabilities of this object, as well as code comments, have been added. Additionally, the method SwitchKeys has been renamed ApplyEvaluationKey.

The goal is to better convey that rlwe.EvaluationKey is a special type of public key that is used during the evaluation phase of a circuit, with different purposes (relinearization, automorphisms, etc...).

The struct rlwe.RotationKeySet has been removed. It is now replaced by the type rlwe.GaloisKey, which is a wrapper of rlwe.EvaluationKey and stores a single rlwe.EvaluationKey along with some meta data to help identify which automorphism it enables.

There is now a simple and much more intuitive hierarchy among rlwe.EvaluationKeys:

rlwe.EvaluationKey 
         |
         |-> rlwe.RelinearizationKey
         └-> rlwe.GaloisKey

To be able to manage multiple rlwe.EvaluationKeys, the rlwe.EvaluationKeySet interface has been added. The (bfv/bgv/ckks).Evaluator types are now using this interface to access evaluation keys when required, which enables the users to define their own loading/saving/persistence policies for rlwe.RelinearizationKey and rlwe.GaloisKeys. The rlwe.MemEvaluationKeySet struct was added as a simple, memory-backed implementation of the rlwe.EvaluationKeySet interface .

Additionally, it is now possible to generate evaluation keys with specific levels for the modulus Q and P, as well as specific power of two decomposition, by passing the optional struct rlwe.EvaluationKeyParameters to the key-generator. This also means that the power of two decomposition for the evaluation keys is not a field of the cryptographic parameters anymore.

Test Coverage and Consistency

Many tests and benchmarks located in the bfv, bgv and ckks packages were merely wrappers of methods of the package rlwe, and thus didn't serve any meaningful purpose. Additionally, many methods in the rlwe package where not fully tested or not tested at all.

To remedy to this issue, all tests and benchmarks in the bfv, bgv and ckks packages that were solely wrappers of a method located in rlwe have been removed. The test coverage of the rlwe package has been substantially increased by adding tests and expanding the range of parameters for which those methods are tested.

An example is the tests for automorphisms. These were tested in each of the schemes by checking that applying a specific automorphism on a ciphertext encrypting an encoded plaintext would result in a specific rotations in the plaintext decoded domain. Although such test does ensure the functionality full pipeline behaves as expected, it was making its debugging difficult by not being able to easily pin-point where the correctness error could come from.

Instead these kind of functionalities have been broken down in their elementary operations, testing each of them separately. Going back to the tests for the automorphisms, the rlwe package will now test that a Galois key is correctly generated, that the homomorphic automorphism applies the correct Galois automorphism on the polynomial coefficients and that it produces the expected noise; and the schemes will only test that an automorphism on an encoded plaintext results in the correct rotation on the decoded plaintext.

Finally, all relevant methods of rlwe now have a benchmark function and the noise bounds for the tests in the packages rlwe and mhe have been substantially improved.

Arbitrary Precision Arithmetic & Polynomial Interpolation

A new package utils/bignum has been added. It provides arbitrary precision arithmetic and polynomial interpolation (Chebyshev & Multi-Interval Remez) over the real and complex numbers.

New Algorithm For Blind Rotations

The CGGI algorithm has been replaced by LMKCDEY's algorithm, enabling faster blind-rotations, smaller keys and arbitrary key-distribution.

Improved Serialization

In addition to the previously available encoding.BinaryMarshaler and encoding.BinaryUnmarshaler interfaces, relevant Lattigo objects now implement the io.ReaderFrom and io.WriterTo interfaces to read/write object directly from/to io.Reader and io.Writer. Moreover, the new methods have been optimized for buffers that provide transient access to their internal buffer (through the buffer.Writer interface, see below).

This is supported by two new packages dedicated to serialization: utils/buffer and utils/structs. The package utils/buffer provides low-level custom methods to efficiently write and read slices on any writer or reader that also expose their internal buffer. The package utils/structs implements generic map, vector and matrix structs of any type, as well as their serialization.

How to Switch from V4 to V5

• lattigo/v4/ckks -> lattigo/v5/he/hefloat
• lattigo/v4/[bfv/bgv] -> lattigo/v5/he/heint
• lattigo/v4/rgsw/lut -> lattigo/v5/he/hebin
• lattigo/v4/drlwe -> lattigo/v5/mhe
• lattigo/v4/dckks -> lattigo/v5/mhe/mhefloat
• lattigo/v4/[dbfv/dbgv] -> lattigo/v5/mhe/mheint
• lattigo/v4/rlwe -> lattigo/v5/core/rlwe
• lattigo/v4/rgsw -> lattigo/v5/core/rgsw
• lattigo/v4/ring -> lattigo/v5/ring

If needed, the bfv, bgv and ckks stand-alone schemes are still available, although they are not intended to be the front-end of the library:

• lattigo/v4/ckks -> lattigo/v5/schemes/ckks
• lattigo/v4/bfv -> lattigo/v5/schemes/bfv
• lattigo/v4/bgv -> lattigo/v5/schemes/bgv

---

This discussion was created from the release Lattigo v5.0.0.