DOCSEARCHbyAlgolia
Submit Docs

Lattigo

repository·main·Indexed 23 days ago

https://github.com/tuneinsight/lattigo

A high-performance, pure Go library for lattice-based homomorphic encryption (HE) and multiparty homomorphic encryption (MHE). It supports various schemes including BFV, BGV, and CKKS, and is designed for distributed systems. The library provides primitives for single-party HE and MHE-MPC protocols, including N-out-of-N and t-out-of-N threshold schemes based on Ring-Learning-with-Errors (RLWE).

Tokens
5.4K
Snippets
3
Records
30
Agent score
81%

What's inside Lattigo

  1. Overview of Multiparty Homomorphic Encryption (MHE) in Lattigo

    main

    The multiparty package implements Multiparty Homomorphic Encryption (MHE) primitives based on Ring-Learning-with-Errors (RLWE). It provides two core threshold schemes:

    1. $N\text{-out-of-}N$-threshold scheme: Requires collaboration from all $N$ parties to perform secret-key operations (like decryption).
    2. $t\text{-out-of-}N$-threshold scheme: Allows any group of at least $t$ parties to perform secret-key operations, providing better liveness guarantees if some parties are unavailable.

    Key Characteristics:

    • Local Operations Only: The package implements the local steps of the MHE-MPC protocol but does not provide a network-layer protocol implementation. You are responsible for the communication between parties.
    • Serialization: All relevant types implement encoding.BinaryMarshaller, encoding.BinaryUnmarshaller, io.WriterTo, and io.ReaderFrom for easy transmission over a network.
    • Scheme-Specific Functionality: Packages like multiparty/mpbgv and multiparty/mpckks provide threshold versions of BGV and CKKS cryptosystems, including features like interactive bootstrapping.
    • Protocol Basis: The implementation follows the MHE-MPC protocol described in Mouchet et al. (2021).

  2. Use the unified BGV package for BGV and BFV schemes

    main

    The bgv package provides a unified RNS-accelerated implementation that covers both the Brakerski-Fan-Vercauteren (BFV) and Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic encryption schemes.

    This unified approach is possible because BFV and BGV are indistinguishable (up to a plaintext scaling factor of $T^{-1} \pmod Q$) when the plaintext modulus $T$ is coprime to the ciphertext modulus $Q$.

    Key capabilities include:

    • SIMD modular arithmetic: Perform operations on encrypted vectors or integers simultaneously.
    • Dual-style tensoring: Supports both BGV-style tensoring (noise growth proportional to current noise) and BFV-style tensoring (noise growth invariant to current noise).

  3. Lattigo: Overview and Core Capabilities

    main

    Lattigo is a Go module providing full-RNS Ring-Learning-With-Errors (RLWE) based homomorphic encryption primitives and Multiparty-Homomorphic-Encryption-based secure protocols. It is designed for distributed systems and microservices architectures, offering a pure Go implementation that supports cross-platform builds and WASM compilation for browser clients.

    Key features include:

    • Optimized arithmetic for power-of-two cyclotomic rings.
    • Implementation of BFV, BGV, and CKKS schemes (including multiparty versions).
    • Support for RGSW, external product, and LMKCDEY blind rotations.
    • Advanced RLWE-based primitives, key-generation, and scheme-agnostic implementations.

  4. Understand the Lattigo Package Hierarchy

    main

    Lattigo is organized into a strictly hierarchical, linear dependency chain. Understanding this hierarchy is essential for navigating the library from low-level arithmetic to high-level circuits:

    • lattigo/ring: The foundation. Provides modular arithmetic for polynomials in the RNS basis (RNS basis extension, rescaling, NTT, and sampling).
    • lattigo/core: Builds on ring. Implements core cryptographic functionalities like rlwe (generic RLWE-based encryption, decryption, and key-switching) and rgsw (Full-RNS Ring-GSW).
    • lattigo/schemes: Implements specific RLWE-based schemes:
      • bfv: Scale-invariant scheme providing modular arithmetic over integers.
      • bgv: Generalization of BFV/BGV providing modular arithmetic over integers.
      • ckks: Provides fixed-point approximate arithmetic over complex or real numbers.
    • lattigo/circuits: High-level homomorphic circuits for bgv and ckks (e.g., linear transformations, polynomial evaluation, comparison, bootstrapping, and DFT).
    • lattigo/multiparty: Implements multiparty (threshold) key-generation and interactive ciphertext bootstrapping (e.g., mpckks, mpbgv).
    • lattigo/utils: Generic utilities including bignum, buffer, factorization, sampling, and structs.

  5. Understand the MHE-MPC Protocol models and phases

    main

    The Multiparty Homomorphic Encryption (MHE-MPC) protocol allows $N$ input parties to compute a joint function over private encrypted inputs and provide the result to a receiver.

    Execution Phases

    The protocol consists of two main phases:

    1. Setup Phase: Prepares the cryptographic material required for computation.

      • Secret Keys Generation
      • Optional: Threshold Secret-Key Generation (if using $t < N$ threshold)
      • Collective Public Encryption-Key Generation
      • Collective Public Evaluation-Key Generation (includes Relinearization-Keys, Galois-Keys, and Generic Evaluation-Keys)

    2. Evaluation Phase: Performs the actual computation.

      • Input (Encryption)
      • Circuit Evaluation
      • Output phase (Decryption), which involves Collective Key-Switching followed by Local Decryption.

    System Models

    • Peer-to-peer vs Cloud-assisted: Parties can run the protocol directly or use a third-party server (considered an adversary).
    • Internal vs External Receivers: An internal receiver is one of the input parties. An external receiver is a third party that does not need to be online during the setup phase.
    • Anytrust vs Full-threshold: By default, the protocol is "anytrust" ($N$-out-of-$N$ threshold), but it can be configured for $t$-out-of-$N$ threshold access structures.
    • Adversary Model: The current implementation is secure against passive adversaries. Active security (requiring proofs of correct share computation) is not currently implemented.

  6. Understand the CKKS scheme variants

    main

    The ckks package implements an RNS-accelerated version of the CKKS scheme. You can choose between two variants using the RingType field in the Parameter struct:

    1. Standard Variant (ring.Standard): Encrypts vectors of complex numbers. It supports packing up to $N/2$ plaintext complex values into a single ciphertext. All moduli in the chain must be congruent to $1 \pmod{2N}$, where $N$ is the ring degree.
    2. Conjugate-Invariant Variant (ring.ConjugateInvariant): Encrypts vectors of real numbers. It supports packing up to $N$ plaintext real values into a single ciphertext. All moduli in the chain must be congruent to $1 \pmod{4N}$.

  7. How BFV scale-invariance is implemented

    main

    When the scale-invariant flag is set to true in a BGV evaluator, the implementation automatically replaces standard BGV multiplication and rescaling functions with their scale-invariant BFV alternatives. The following Evaluator methods are swapped under the hood:

    • Evaluator.Mul
    • Evaluator.MulNew
    • Evaluator.MulRelin
    • Evaluator.MulRelinNew
    • Evaluator.Rescale

  8. Configure CKKS security parameters

    main

    To ensure a security level of 128 bits (for a secret key with uniform ternary distribution), your parameters should follow the tuples of (log2(N), log2(Q), sigma) defined by the Homomorphic Encryption Standards group.

    As long as your total modulus $Q$ is equal to or below the specified values for a given $N$, the scheme maintains at least 128 bits of security:

    log2(N)log2(Q)sigma
    121093.2
    132183.2
    144383.2
    158813.2

    Note on Sparse Keys: Lattigo uses fully-entropic ternary keys by default. If you modify the key distribution to use sparse keys (low Hamming weight), you must re-evaluate the security parameters as they may be lower than standard CKKS parameters.

  9. How the $t\text{-out-of-}N$-Threshold Scheme works

    main

    The $t\text{-out-of-}N$ scheme uses Shamir Secret Sharing to allow any $t$ out of $N$ parties to reconstruct the secret key. This is useful for liveness when $N$ is large.

    The Mechanism:

    1. Re-sharing: The scheme is implemented as an extension of the $N\text{-out-of-}N$ scheme. Parties first perform a re-sharing of their $N\text{-out-of-}N$ secret-key shares using Shamir Secret Sharing.
    2. Private Exchange: This requires a round of private, pairwise message exchanges where parties send Shamir shares to one another to compute their $t\text{-out-of-}N$ shares.
    3. Combiner Step: Before performing a secret-key operation, parties use a Combiner to transform their Shamir shares into additive shares for the specific set of $t$ participating parties.
    4. Execution: Once transformed, the parties use the standard $N\text{-out-of-}N$ protocols, but treating the $t$ participants as the full set.

  10. Implement a Common Random String (CRS) for Multiparty Protocols

    main
    Multiparty protocols in Lattigo require access to common uniformly random polynomials (CRP) sampled from a Common Random String (CRS). To implement this, use the multiparty.CRS interface. A common way to satisfy this requirement is by using the utils.KeyedPRNG type, ensuring all participating parties use the same key to generate the same random string.

  11. Use the BFV scheme via the BGV package

    main

    In Lattigo, the BFV (Brakerski-Fan-Vercauteren) scheme is implemented as a unified variant within the bgv package. To use BFV instead of BGV, you must instantiate a BGV evaluator and set the optional scale-invariant parameter to true.

    Important Requirement: For correctness and security (IND-CPA), the plaintext modulus ($T$) must be coprime with the ciphertext modulus ($Q$). If $T$ divides $Q$, the scheme is not secure and the inverse $T^{-1} \pmod Q$ will not be defined.

  12. How the $N\text{-out-of-}N$-Threshold Scheme works

    main

    The $N\text{-out-of-}N$ scheme distributes a secret key $s$ among $N$ parties by splitting it into additive shares such that $s = \sum_{i=1}^{N} s_i$. Each party $i$ holds a share $s_i$.

    How it works:

    • Linearity: Because RLWE operations are (almost) linear, parties can compute their part of a function $F(a, s)$ locally as $h_i = F(a, s_i) = as_i + e_i$.
    • Aggregation: The final result is obtained by aggregating the shares: $h = \sum_{i=1}^{N} h_i$.
    • Security: Secret-key shares $s_i$ are sampled locally and never disclosed, meaning no trusted dealer or private channels are required for the initial setup.
    • Re-encryption: The threshold decryption protocol can be generalized into a re-encryption protocol to transform ciphertexts towards a known public key.