Lattice - Post-Quantum Cryptography Library

Lattice is a high-performance Go library implementing full-RNS Ring-Learning-With-Errors (RLWE) based homomorphic encryption primitives and multiparty protocols. It provides quantum-resistant cryptographic primitives that remain secure even in the presence of quantum computers.

Why Lattice-Based Cryptography?

The Quantum Threat

Traditional public-key cryptography (RSA, ECC) relies on mathematical problems that quantum computers can solve efficiently using algorithms like Shor's algorithm. As quantum computers become more powerful, these cryptographic systems become vulnerable. Lattice-based cryptography provides security based on problems that remain hard even for quantum computers.

Key Advantages

Quantum Resistance: Based on the hardness of lattice problems (Learning With Errors, Ring-LWE)
Homomorphic Properties: Enable computation on encrypted data without decryption
Efficiency: Competitive performance with classical cryptography
Versatility: Support for various cryptographic primitives (encryption, signatures, key exchange)
NIST Standardization: Multiple lattice-based schemes selected for NIST post-quantum standards

Core Features

High-Performance Implementation

Full-RNS Arithmetic: Optimized residue number system for efficient modular operations
Power-of-Two Cyclotomic Rings: Fast polynomial arithmetic using NTT
SIMD Optimizations: Vectorized operations for improved performance
Pure Go: Cross-platform compatibility including WASM compilation
Parallel Processing: Concurrent execution for multi-core systems

Supported Schemes

BFV/BGV (Exact Arithmetic)

Full-RNS implementation of scale-invariant homomorphic encryption
Modular arithmetic over integers
Perfect for applications requiring exact computation
Support for batching via Chinese Remainder Theorem

CKKS (Approximate Arithmetic)

Fixed-point approximate arithmetic over complex/real numbers
Ideal for machine learning and signal processing
Support for conjugate-invariant variant
Advanced bootstrapping capabilities

Multiparty Computation

Threshold key generation
Distributed decryption and re-encryption
Interactive bootstrapping with secret-shared keys
Secure multiparty protocols

Security Parameters:
- Ring dimension: N = 2^k (typically 2^12 to 2^17)
- Modulus: Q (product of primes)
- Error distribution: Discrete Gaussian
- Security level: 128, 192, or 256 bits

Ring-LWE (RLWE)

A structured variant of LWE using polynomial rings, providing better efficiency while maintaining security.

// Ring-LWE instance
type RLWECiphertext struct {
    c0 *ring.Poly  // a*s + m + e0
    c1 *ring.Poly  // a
}

Security Levels

Security Level	Classical Security	Quantum Security	Ring Dimension
128-bit	128 bits	64 bits	N ≥ 2^12
192-bit	192 bits	96 bits	N ≥ 2^14
256-bit	256 bits	128 bits	N ≥ 2^15

Parameter Selection

Parameters must balance security, performance, and functionality:

// Example: 128-bit security CKKS parameters
params := ckks.ParametersLiteral{
    LogN:            14,                    // Ring dimension 2^14
    LogQ:            []int{50, 40, 40, 40}, // Ciphertext modulus chain
    LogP:            []int{60},             // Key-switching modulus
    LogDefaultScale: 40,                    // Default scaling factor
    Sigma:           3.2,                    // Error standard deviation
}

API Reference

Core Package Structure

import (
    "github.com/luxfi/lattice/core/rlwe"
    "github.com/luxfi/lattice/schemes/ckks"
    "github.com/luxfi/lattice/schemes/bgv"
    "github.com/luxfi/lattice/multiparty"
)

Key Generation

// Generate keys for CKKS scheme
params, err := ckks.NewParametersFromLiteral(paramsLiteral)
kgen := rlwe.NewKeyGenerator(params)

// Secret key
sk := kgen.GenSecretKeyNew()

// Public key
pk := kgen.GenPublicKeyNew(sk)

// Evaluation keys (for homomorphic operations)
evk := rlwe.NewMemEvaluationKeySet(
    kgen.GenRelinearizationKeyNew(sk),     // For multiplication
    kgen.GenGaloisKeysNew(sk, galoisElems), // For rotations
)

Encryption and Decryption

// Create encoder and encryptor
encoder := ckks.NewEncoder(params)
encryptor := rlwe.NewEncryptor(params, pk)
decryptor := rlwe.NewDecryptor(params, sk)

// Encode and encrypt
values := []complex128{1.0, 2.0, 3.0, 4.0}
plaintext := ckks.NewPlaintext(params, params.MaxLevel())
encoder.Encode(values, plaintext)
ciphertext, err := encryptor.EncryptNew(plaintext)

// Decrypt and decode
plaintext = decryptor.DecryptNew(ciphertext)
result := encoder.Decode(plaintext, params.LogSlots())

Homomorphic Operations

evaluator := ckks.NewEvaluator(params, evk)

// Addition
ctSum, err := evaluator.AddNew(ct1, ct2)

// Multiplication
ctProd, err := evaluator.MulRelinNew(ct1, ct2)
evaluator.Rescale(ctProd, ctProd)

// Rotation
ctRot, err := evaluator.RotateNew(ct, 1)

// Complex conjugation
ctConj, err := evaluator.ConjugateNew(ct)

Multiparty Operations

// Threshold key generation
tkg := multiparty.NewTKGProtocol(params)
share := tkg.GenShare(sk)
pk := tkg.AggregateShares(shares)

// Collective decryption
tdp := multiparty.NewPCKSProtocol(params)
shareDecrypt := tdp.GenShare(sk, ct)
plaintext := tdp.AggregateShares(sharesDecrypt)

Performance Characteristics

Benchmarks

Performance on Intel Core i7-10700K @ 3.80GHz:

Operation	Time (ms)	Throughput	Memory
Key Generation	45	-	128 MB
Encryption	2.3	435 ops/s	8 MB
Decryption	1.8	555 ops/s	8 MB
Addition	0.05	20,000 ops/s	16 MB
Multiplication	25	40 ops/s	24 MB
Rotation	8	125 ops/s	16 MB
Bootstrapping	850	1.2 ops/s	512 MB

Optimization Techniques

Number Theoretic Transform (NTT)

Fast polynomial multiplication using FFT-like algorithm in finite fields:

Time Complexity: O(N log N) vs O(N²) for naive multiplication
Space Complexity: O(N)

RNS Decomposition

Decompose large modulus Q into smaller primes for parallel arithmetic:

Q = q₁ × q₂ × ... × qₗ
Operations mod Q → Operations mod qᵢ (parallel)

Lazy Reduction

Delay modular reductions to minimize computational overhead:

// Accumulate operations before reduction
for i := 0; i < batchSize; i++ {
    acc.Add(acc, values[i])
}
acc.Reduce() // Single reduction at the end

Memory Management

// Pre-allocate buffers for better performance
buffer := rlwe.NewCiphertext(params, degree, level)

// Reuse memory with in-place operations
evaluator.Add(ct1, ct2, ct1) // Result stored in ct1

// Manual garbage collection for large operations
runtime.GC()

Advanced Features

Bootstrapping

Enable unlimited homomorphic operations by refreshing ciphertext noise:

// Configure bootstrapping parameters
btpParams := bootstrapping.ParametersLiteral{
    LogN:    16,
    LogSlots: 15,
    H:       192,
    Sigma:   3.2,
    ...
}

// Create bootstrapper
btp, err := bootstrapping.NewBootstrapper(params, btpParams, evk)

// Bootstrap ciphertext
ctBootstrapped, err := btp.Bootstrap(ct)

Linear Transformations

Efficient matrix-vector multiplication on encrypted data:

// Define transformation matrix
matrix := [][]complex128{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9},
}

// Create linear transformation
linTransf := lintrans.NewLinearTransformation(params, matrix)

// Apply to ciphertext
ctResult, err := evaluator.LinearTransformation(ct, linTransf)

Polynomial Evaluation

Evaluate polynomials on encrypted values:

// Define polynomial coefficients
coeffs := []complex128{1.0, 2.0, 3.0} // 1 + 2x + 3x²

// Create polynomial evaluator
poly := polynomial.NewPolynomial(coeffs)

// Evaluate on ciphertext
ctResult, err := evaluator.Polynomial(ct, poly)

Security Best Practices

Parameter Validation

// Always validate parameters before use
if err := params.Validate(); err != nil {
    return fmt.Errorf("invalid parameters: %w", err)
}

Noise Management

// Monitor noise growth
noise := rlwe.NoiseLevel(ct, sk, params)
if noise > threshold {
    // Bootstrap or terminate computation
}

Key Management

Never reuse randomness
Securely delete keys after use
Use hardware security modules for production
Implement key rotation policies

Side-Channel Protection

Use constant-time implementations
Avoid data-dependent branches
Implement blinding techniques
Regular security audits

Migration Guide

From Classical Cryptography

// RSA/ECC replacement
// Before: RSA encryption
rsaCiphertext := rsa.Encrypt(publicKey, plaintext)

// After: Lattice encryption
latticeCiphertext := encryptor.EncryptNew(plaintext)

// Advantage: Quantum-resistant + homomorphic operations

From Other HE Libraries

// SEAL/HElib migration
// Key differences:
// - Pure Go vs C++
// - Full-RNS by default
// - Unified API across schemes
// - Native multiparty support

Getting Started

Installation

go get github.com/luxfi/lattice/v6

Basic Example

package main

import (
    "fmt"
    "github.com/luxfi/lattice/v6/core/rlwe"
    "github.com/luxfi/lattice/v6/schemes/ckks"
)

func main() {
    // Initialize parameters
    params, _ := ckks.NewParametersFromLiteral(
        ckks.ParametersLiteral{
            LogN: 14,
            LogQ: []int{50, 40, 40, 40},
            LogP: []int{60},
            LogDefaultScale: 40,
        },
    )

    // Generate keys
    kgen := rlwe.NewKeyGenerator(params)
    sk := kgen.GenSecretKeyNew()
    pk := kgen.GenPublicKeyNew(sk)

    // Create crypto objects
    encoder := ckks.NewEncoder(params)
    encryptor := rlwe.NewEncryptor(params, pk)
    decryptor := rlwe.NewDecryptor(params, sk)
    evaluator := ckks.NewEvaluator(params, nil)

    // Encrypt data
    values := []complex128{1, 2, 3, 4}
    pt := ckks.NewPlaintext(params, params.MaxLevel())
    encoder.Encode(values, pt)
    ct, _ := encryptor.EncryptNew(pt)

    // Perform homomorphic addition
    ctSum, _ := evaluator.AddNew(ct, ct)

    // Decrypt result
    ptResult := decryptor.DecryptNew(ctSum)
    result := encoder.Decode(ptResult, params.LogSlots())

    fmt.Println("Result:", result[:4])
    // Output: Result: [2, 4, 6, 8]
}

Next Steps

Tutorials: Step-by-step guides for common use cases
API Documentation: Complete API reference
Examples: Production-ready code examples
Benchmarks: Performance comparisons and optimization tips
Security Guide: Best practices for secure deployment

Support

GitHub Issues: github.com/luxfi/lattice/issues
Email: lattice@lux.network
Documentation: pkg.go.dev/github.com/luxfi/lattice/v6

Introduction to Lattice

On this page