GA Engine: High-Performance Geometric Algebra for Homomorphic Encryption

A production-candidate Rust framework for privacy-preserving computation, combining fully homomorphic encryption (CKKS/RLWE) with native Clifford geometric algebra support. Enables encrypted machine learning on geometric data with GPU acceleration (Metal, CUDA) achieving 2,002× speedup over baseline.

Overview

GA Engine implements Clifford FHE, a novel cryptographic scheme combining Ring Learning With Errors (RLWE) based fully homomorphic encryption with Clifford geometric algebra operations. This enables practical privacy-preserving machine learning on encrypted geometric data, a capability critical for medical imaging, autonomous systems, and secure spatial computing applications.

Key Research Finding: Clifford FHE achieves information-theoretic privacy against execution-trace attacks. While CKKS leaks input dimensions with 100% accuracy via rotation counts, Clifford FHE's fixed multiplication structure (64 structure constants, 8 non-zero per component) reveals zero information.

The framework achieves production-candidate performance through systematic optimization: from baseline reference implementation (V1) to hardware-accelerated backends featuring Metal and CUDA GPU support achieving 2,002× speedup, delivering sub-millisecond homomorphic additions and ~217ms ciphertext multiplications on NVIDIA RTX 4090 architecture.

---

Headline Results: CliffordPointNet

Privacy-preserving 3D point cloud classification with production-viable performance on encrypted data.

Performance Milestones (NVIDIA RTX 5090)

Configuration	Per Geometric Product	Security Level	Production Target
V3 CUDA N=1024	17.68ms	80-bit	Exceeds <50ms
V3 CUDA N=8192	45.41ms	128-bit post-quantum	Meets <50ms
V3 CPU N=1024	52.62ms	80-bit	Borderline
V3 CPU N=8192	304.79ms	128-bit post-quantum	Baseline

Accuracy Validation (40 test samples, 5 classes)

Metric	Result
Encrypted vs Plaintext Agreement	100.0% (40/40)
Accuracy Gap	0.0%
Max CKKS Error	0.004

Key Finding: Encryption introduces zero accuracy degradation. Every encrypted prediction exactly matches its plaintext counterpart.

GPU Speedups

N	CUDA vs CPU Speedup
1024	2.98×
8192	6.71×

What This Means

• Production-Ready: Both N=1024 and N=8192 configurations meet the <50ms target for practical applications
• Post-Quantum Secure: N=8192 provides 128-bit security against quantum attacks
• Zero Accuracy Loss: Homomorphic encryption preserves classification accuracy perfectly
• Batch Processing: 64-512 multivectors processed simultaneously via SIMD slot packing

---

Technical Achievements

Practical Homomorphic Division

The Problem: Division of encrypted values (computing Enc(a)/Enc(b) from two ciphertexts) has remained impractical in approximate arithmetic FHE. No major library (SEAL, HElib, OpenFHE, PALISADE) provides a practical ciphertext-ciphertext division primitive.

Our Solution: Newton-Raphson iteration with geometric algebra integration achieves:

Metric	Our Approach	Binary Circuits	Chebyshev (OpenFHE)
Depth	5-7 levels (constant)	448 levels (64-bit)	63 levels (10⁻⁹ precision)
Time (GPU)	1.2-5.1 seconds	~374 seconds (estimated)	1.7× slower
Accuracy	10⁻⁸ to 10⁻¹²	Exact	9× worse at same depth
Chained Divisions	10⁻¹¹ precision	Requires bootstrapping	Fails catastrophically

Key Results:

• 9× better accuracy than Chebyshev polynomial methods at the same depth budget
• 86% less depth than Chebyshev for production-grade precision (9 vs 63 levels)
• 16 million times more accurate for chained operations (Newton-Raphson: 3.6×10⁻⁶ error vs Chebyshev: 58% error)
• First demonstration of GPU-accelerated Newton-Raphson division integrated with full CKKS bootstrapping
• Unlimited division chains via bootstrap pipeline: Division → Bootstrap → Division → ...

Why Geometric Algebra Enables This: The multivector inversion formula M⁻¹ = M†/(M·M†) is the key insight:

• The reverse operation M† is O(1): a simple coefficient permutation with sign changes, requiring zero homomorphic computation
• For unit rotors (standard in graphics/robotics): inversion is FREE (0 multiplications)
• For general rotors: 4.2× fewer operations than matrix inversion
• Unified framework: one formula handles scalars, complex numbers, quaternions, vectors, and general multivectors

Applications Unlocked:

• Batch normalization and softmax in encrypted neural networks
• Vector normalization for encrypted geometry (2.1s on GPU)
• Encrypted rigid body dynamics with orientation updates
• Homomorphic deconvolution in signal processing

Cryptographic Innovation

• Clifford FHE: Native algebraic extension to CKKS with first-class geometric algebra support over Cl(3,0). Encodes the Clifford multiplication table through structure constants, enabling sparse parallel evaluation with only 8 non-zero terms per output component (vs 64 component multiplications with manual sign management)
• First GPU-accelerated Newton-Raphson division with CKKS bootstrapping: Enabling unbounded division chains for iterative algorithms on encrypted data
• ≥118-bit post-quantum security: Verified using Lattice Estimator against primal, dual, and hybrid attacks
• Production-grade RNS-CKKS foundation: Multi-prime modulus chain enabling deep computation circuits
• Full bootstrapping implementation (V3): Unlimited multiplication depth through homomorphic noise refresh
  • CUDA GPU: 11.69s bootstrap (6× faster than CPU, 100% GPU execution with relinearization)
  • Metal GPU: 71.37s bootstrap (100% GPU execution)
  • CPU: ~70s bootstrap (reference implementation)

Performance Engineering

Single Operation Performance (Geometric Product)

Backend	Hardware	Performance	Speedup	Throughput
V1 Baseline	Apple M3 Max CPU	11,420 ms	1×	0.09 ops/sec
V2 CPU (Rayon)	Apple M3 Max (14-core)	300 ms	38×	3.3 ops/sec
V2 Metal GPU	Apple M3 Max GPU	33 ms	346×	30.3 ops/sec
V2 CUDA GPU	NVIDIA RTX 4090	5.7 ms	2,002×	175 ops/sec

CUDA GPU Benchmark Results (NVIDIA RTX 4090)

Core Homomorphic Operations (N=4096, 4 primes):

Operation	Time	Throughput
Encode	0.029 ms	34,483 ops/sec
Encrypt	7.89 ms	127 ops/sec
Decrypt	3.47 ms	288 ops/sec
Add (ct+ct)	0.079 ms	12,658 ops/sec
Multiply (ct×ct)	286.35 ms	3.5 ops/sec
Rotate (1 slot)	6.5-6.8 ms	150 ops/sec

Homomorphic Division (Newton-Raphson, GPU-accelerated):

Ring Size	Time	Precision	Throughput
N=4096	1.24s	10⁻⁸	0.80 div/sec
N=8192	4.14s	10⁻¹²	0.24 div/sec

• Chained divisions: 4+ sequential divisions with 10⁻¹¹ precision
• Depth: Only 5-7 levels (vs 448 for binary circuits)
• CPU baseline: ~7 seconds → 5.6× GPU speedup

V4 Geometric Product (Packed Multivector Layout, NVIDIA RTX 4090):

Configuration	Time	Notes
N=1024 (quick)	0.588s	22× faster than CPU, 6.6× faster than Metal
N=8192 (full)	3.40s	Production parameters, 1024 MVs batched

Bootstrap Performance (V3 Full Bootstrap)

Backend	Hardware	Total Time	Speedup vs CPU	Status
V3 CPU	Apple M3 Max	~70s	1×	Reference
V3 Metal GPU	Apple M3 Max	71.37s	~1×	Production Stable
V3 CUDA GPU	NVIDIA RTX 4090	11.69s	6×	Production Stable

V3 CUDA GPU Bootstrap Breakdown (N=1024, 20 primes):

• CoeffToSlot: ~0.4s (linear transforms + rotations)
• EvalMod: ~11.3s (97% of total - polynomial sine approximation)
• SlotToCoeff: ~0.3s (inverse transforms)
• Throughput: ~5 bootstraps/minute
• Error: ~1e-3
• Full relinearization support
• 100% GPU execution (no CPU fallback)

Algorithmic Optimizations

1. Harvey Butterfly NTT: O(n log n) polynomial multiplication replacing O(n²) schoolbook method
2. RNS Modular Arithmetic: Chinese Remainder Theorem decomposition for 60-bit prime moduli
3. Barrett Reduction: Fast approximate modular reduction eliminating division operations
4. Galois Automorphism Optimization: Native slot rotation via key-switching for SIMD batching
5. Metal/CUDA GPU Acceleration: Unified memory architecture (Metal) and massively parallel execution (CUDA)
6. Russian Peasant Multiplication: GPU-safe 128-bit modular multiplication avoiding overflow

Machine Learning Capabilities

• 99% accuracy on encrypted 3D point cloud classification (sphere/cube/pyramid discrimination)
• Rotational equivariance by construction: Geometric algebra encoding eliminates need for data augmentation
• Deep neural network support: V3 bootstrapping enables unlimited circuit depth for complex models
• SIMD batching (in development): Slot packing for throughput multiplication

System Architecture

Six-Tier Implementation Strategy

V1: Reference Baseline

• Purpose: Correctness verification, academic reproducibility, performance baseline
• Status: Complete, stable, 31 unit tests passing
• Performance: 11.42s per homomorphic geometric product
• Characteristics: Straightforward implementation, comprehensive documentation, O(n²) algorithms

V2: Production Optimization

• Purpose: Practical deployment, multiple hardware backends, maximum single-operation performance
• Status: Complete with CPU/Metal/CUDA backends, 127 unit tests passing
• Performance: 5.7ms per operation (CUDA), 33ms (Metal), 300ms (CPU)
• Backends:
  • CPU with Rayon parallelization (14-core utilization)
  • Apple Metal GPU (unified memory, runtime shader compilation)
  • NVIDIA CUDA GPU (massively parallel execution, kernel caching)
• Optimizations: O(n log n) NTT, Barrett reduction, SIMD-ready Montgomery infrastructure

V3: Unlimited Depth Computing

• Purpose: Deep neural networks, complex circuits, production ML deployment
• Status: Complete and validated, 52/52 tests passing (100%)
• Performance:
  • CUDA GPU: 11.69s bootstrap (6× faster than CPU, NVIDIA RTX 4090)
  • Metal GPU: 71.37s bootstrap
  • CPU: ~70s bootstrap (reference)
• Architecture: V3 uses V2 backend (not backend-agnostic)
  • V3 provides bootstrap algorithms (CoeffToSlot, SlotToCoeff, EvalMod)
  • V2 provides low-level operations (NTT, rescaling, rotation, key switching)
  • GPU backends work with both V2 and V3
• Components:
  • Rotation keys (Galois automorphism key-switching)
  • Homomorphic rotation (verified correctness)
  • CoeffToSlot/SlotToCoeff (FFT-like transformations)
  • EvalMod (homomorphic modular reduction via BSGS polynomial evaluation)
  • Full bootstrap pipeline (ModRaise → CoeffToSlot → EvalMod → SlotToCoeff)
  • Relinearization keys (CUDA)

V4: Packed Multivector Layout

• Purpose: Memory-efficient geometric operations, SIMD slot packing for multivectors
• Status: Complete with Metal and CUDA GPU backends, validated with production tests
• Performance:
  • CUDA GPU (N=1024): 0.588s per packed geometric product (22× faster than CPU)
  • CUDA GPU (N=8192): 3.40s per packed geometric product (production parameters)
  • Metal GPU (N=1024): 3.89s per packed geometric product
• Architecture: V4 uses V2 backend (builds on V2 GPU infrastructure)
  • V4 provides packing/unpacking operations (slot-interleaved layout)
  • V2 GPU backends provide low-level operations (NTT, rotation, multiplication)
  • Single packed ciphertext holds all 8 Clifford algebra components
• Memory Efficiency: 8× reduction (1 packed ciphertext instead of 8 separate)
• Batch Processing: Pack up to N/8 multivectors per ciphertext for massive throughput
• Components:
  • Butterfly network for efficient packing (8 components → 1 ciphertext)
  • Unpacking via homomorphic rotations and masking
  • Geometric product on packed multivectors (per-prime GPU parallelization)
  • Compatible with V3 bootstrapping
• Trade-off: Higher latency for single operations but 1024× throughput for batched operations

V5: Privacy-Trace Collection and Analysis

• Purpose: Research framework for execution-trace privacy analysis.
• Status: Complete, ~10 tests passing
• Architecture: Standalone instrumentation layer (works with V2-V4, does NOT require V2)
• Components:
  • Execution trace collection (CPU and GPU backends)
  • Six attack implementations (dimension inference, task identification, operation count, trace length, sparsity inference, tenant linkability)
  • Information-theoretic analysis tools
• Key Finding: Clifford FHE wins 4 attacks, ties 2 vs CKKS
  • CKKS leaks 2.585 bits of dimension entropy (100% attack accuracy)
  • Clifford FHE leaks 0 bits (random-guessing accuracy: 16.7%)
• Use Case: Security research, privacy auditing, academic reproducibility

V6: parallel_lift GPU Acceleration

• Purpose: External GPU acceleration library for 25-552× speedup via optimized CRT operations
• Status: Stub crates by default (compiles without external dependency)
• Architecture: Uses parallel_lift repository (optional external dependency)
• Default Behavior: Uses stub crates that allow compilation but return errors at runtime
• Setup:

  # Clone parallel_lift repository
  git clone <parallel_lift_url> ../parallel_lift
  
  # Enable real parallel_lift
  ./scripts/enable_parallel_lift.sh
  
  # Build with V6 CUDA support
  cargo build --release --features v6-cuda
  
  # Revert to stubs (if needed)
  ./scripts/disable_parallel_lift.sh

• Components:
  • GPU gadget decomposition (25× speedup)
  • GPU batch reconstruction
  • GPU matrix-vector operations

Core Capabilities

Homomorphic Geometric Operations

All operations preserve mathematical structure under encryption with error <10⁻⁶:

Operation	Depth	Description	V1 Time	V2 CUDA Time	Speedup
Geometric Product	1	Fundamental Clifford product: a⊗b	11.42s	5.7ms	2,002×
Reverse	0	Grade involution: ~a	<1ms	<1ms	-
Inversion	5-9	Multivector inverse: M⁻¹ = M†/(M·M†)	N/A	1.2-5.1s	-
Rotation	2	Rotor-based rotation: R⊗v⊗~R	22.8s	11.4ms	2,000×
Wedge Product	2	Exterior product: a∧b = (a⊗b - b⊗a)/2	22.8s	11.4ms	2,000×
Inner Product	2	Contraction: a·b = (a⊗b + b⊗a)/2	22.8s	11.4ms	2,000×
Projection	3	Parallel component: proj_a(b)	34.3s	17.1ms	2,006×
Rejection	3	Orthogonal component: b - proj_a(b)	34.3s	17.1ms	2,006×

Mathematical Foundation: Operations preserve Clifford algebra Cl(3,0) structure:

• Basis: {1, e₁, e₂, e₃, e₁₂, e₁₃, e₂₃, e₁₂₃} (8 components)
• Multiplication table: 64 structure constants, only 8 non-zero per output component (sparse evaluation)
• Graded structure: scalar ⊕ vector ⊕ bivector ⊕ trivector

Cryptographic Security

Post-Quantum Security Level: ≥118 bits (NIST Level 1 equivalent)

Security Analysis (Lattice Estimator verification):

Parameters: N=1024, log₂(Q)=100-180, σ=3.2
Attack Complexity:
  • Primal uSVP: 2¹²⁰ operations
  • Dual attack: 2¹¹⁸ operations
  • Hybrid attack: 2¹¹⁹ operations
Conservative estimate: λ ≥ 118 bits

Cryptographic Basis:

• Ring-LWE hardness assumption over polynomial ring Z[x]/(x^1024 + 1)
• RNS-CKKS approximate homomorphic encryption
• IND-CPA security via game-hopping reduction
• Modulus chain: 3-30 primes (45-60 bits each) for depth management

Important: Research prototype. Not constant-time; requires security audit for production deployment.

Documentation

Document	Description
CliffordPointNet.md	Comprehensive guide: API reference, benchmark reproduction, shell scripts
CLIFFORD_FHE_VERSIONS.md	Complete technical history: V1→V2→V3→V4→V5 evolution, implementations, performance
ARCHITECTURE.md	System design, backend architecture, module organization
INSTALLATION.md	Setup guide, system requirements, platform-specific build instructions
TESTING_GUIDE.md	Comprehensive testing procedures and validation
BENCHMARKS.md	Performance benchmarks and optimization techniques
COMMANDS.md	Complete command reference for all builds, tests, and examples
FEATURE_FLAGS.md	Feature flag reference and build configuration patterns
docs/BENCHMARK_RESULTS.md	Detailed benchmark results with RTX 5090 GPU timings
docs/IMPLEMENTATION_PLAN.md	CliffordPointNet implementation plan and status

Quick Start

Installation

# Install Rust 1.75+
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

# Clone repository
git clone https://github.com/DataHubz/ga_engine.git
cd ga_engine

# Build with optimizations
cargo build --release --features v2

See INSTALLATION.md for GPU backend setup (Metal/CUDA).

Running Examples

# V2 CPU: Encrypted 3D classification (38× faster than V1)
cargo run --release --features v2 --example encrypted_3d_classification

# V2 CPU: Encrypted geometric product demo
cargo run --release --features v2 --example encrypted_geometric_product_demo

# V2 CUDA GPU: Maximum performance (2,002× faster than V1)
cargo test --release --features v2,v2-gpu-cuda --test test_geometric_operations_cuda -- --nocapture

# V3 CUDA GPU: Full bootstrap (100% GPU, 11.69s)
cargo run --release --features v2,v2-gpu-cuda,v3 --example test_cuda_bootstrap

# V3 Metal GPU: Full bootstrap (100% GPU, 71s)
cargo run --release --features v2,v2-gpu-metal,v3 --example test_metal_gpu_bootstrap_native

# V4 Metal GPU: Packed geometric product (8× memory reduction)
cargo test --release --features v4,v2-gpu-metal --test test_geometric_operations_v4 -- --nocapture

# V4 CUDA GPU: Packed geometric product (quick test, N=1024)
cargo run --release --features v4,v2-gpu-cuda --example bench_v4_cuda_geometric_quick

# Homomorphic Division examples
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda --example test_homomorphic_division
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda,v3 --example test_division_bootstrap_integration

# V5: Privacy attack analysis
cargo run --release --features v5 --example v5_privacy_attacks

# V5: Dimension inference attack only
cargo run --release --features v5 --example v5_dimension_attack

# V5: Execution trace collector
cargo run --release --features v5 --example v5_trace_collector

Running Benchmarks

# Full CUDA benchmark suite (all operations + bootstrap + division, ~30-60 min)
./scripts/run_cuda_benchmarks.sh full

# Quick CUDA benchmarks (basic verification, ~5-10 min)
./scripts/run_cuda_benchmarks.sh

# Individual CUDA benchmarks
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda --example bench_cuda_all_ops
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda,v3 --example bench_cuda_bootstrap
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda --example bench_division_cuda_gpu
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda,v4 --example bench_v4_cuda_geometric_quick

# Division benchmarks (Newton-Raphson vs Chebyshev comparison)
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda --example bench_nr_vs_chebyshev_division
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda --example bench_division_comprehensive
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda,v3 --example bench_division_with_bootstrap

# Metal GPU benchmarks (macOS)
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-metal --example bench_division_metal_gpu
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-metal,v4 --example bench_v4_geometric_product

# Vector normalization pipeline (uses division)
cargo run --release --no-default-features --features f64,nd,v2,v2-gpu-cuda --example bench_vector_normalization_pipeline

Running Tests

# V2: Complete test suite (127 tests, <1 second)
cargo test --lib --features v2

# V3: Bootstrap tests (52 tests, 100% passing)
cargo test --lib --features v2,v3 clifford_fhe_v3

# V4: Packed multivector tests (3 integration tests)
cargo test --test test_geometric_operations_v4 --features v4,v2-gpu-metal --no-default-features -- --nocapture

# V5: Privacy analysis tests (~10 tests)
cargo test --lib --features v5 clifford_fhe_v5

# All versions (V1 + V2 + V3 + V5 = ~223 tests)
cargo test --lib --features v1,v2,v3,v5

See TESTING_GUIDE.md for comprehensive testing instructions.

Applications

Privacy-Preserving 3D Classification

Problem: Medical imaging, autonomous vehicles, and secure CAD require classification of 3D spatial data without compromising privacy.

Solution: Clifford FHE enables encrypted neural network inference on geometric data.

Results:

• Accuracy: 99% on encrypted 3D point clouds (100 points/sample)
• Latency (NVIDIA RTX 4090):
  • Ciphertext addition: 0.079ms
  • Ciphertext multiplication: 286ms
  • Rotation: 6.5ms
  • With bootstrap: 11.69s refresh (V3 CUDA GPU)
• Error: <10⁻⁶ relative precision maintained throughout computation
• Privacy: Zero-knowledge inference; server never observes plaintext data or model weights

Dataset: Synthetic geometric shapes (spheres, cubes, pyramids) with rotational invariance.

Architecture: 3-layer geometric neural network (1→16→8→3 multivectors), 27 homomorphic geometric products.

Lattice Cryptanalysis

GA-Accelerated BKZ: Geometric algebra rotors for n-dimensional lattice reduction.

Achievements:

• Stable numerically-accurate Gram-Schmidt orthogonalization
• 100% test pass rate on challenging lattice problems
• Novel μ-coefficient computation using geometric algebra

Citation

If you use this software, please cite:

David William Silva. "Merits of Geometric Algebra Applied to Cryptography and Machine Learning." Philosophical Transactions of the Royal Society A, 2026.

A citable software archive is available on Zenodo (DOI added upon release).

Contact & Support

David William Silva — DataHubz LLC — dsilva@datahubz.com

For bug reports and feature requests, please use the issue tracker.

Acknowledgments

This research was funded by DataHubz LLC. The author thanks the geometric algebra and Rust communities for foundational tools and discussions.

License

Apache License 2.0 - See LICENSE file

Open Source Philosophy: All code released under permissive license to enable:

• Verification of academic claims and reproducibility
• Extension and improvement by research community
• Advancement of privacy-preserving machine learning

Project Status

Component	Status	Documentation
V1 Baseline	Complete	Full
V2 CPU Backend	Complete	Full
V2 Metal GPU	Complete	Full
V2 CUDA GPU	Complete	Full
V3 Bootstrap (CPU)	Complete	Full
V3 Bootstrap (Metal GPU)	Production Candidate	Full
V3 Bootstrap (CUDA GPU)	Production Candidate	Full
V4 Packed Layout (Metal GPU)	Complete	Full
V4 Packed Layout (CUDA GPU)	Production Candidate	Full
V5 Privacy Analysis	Complete	Full
V6 parallel_lift (Stubs)	Stub Crates	Full
V6 parallel_lift (Real)	Optional	Requires setup
Lattice Reduction	Complete	Full

Overall: Production-candidate framework with comprehensive testing and documentation.