Meeting in the Middle: A Co-Design Paradigm for FHE and AI Inference

1. Problem Statement

The deployment of large neural network models as cloud services creates a fundamental conflict between utility and privacy:

• The Privacy Gap: Users must transmit sensitive inputs (often in plaintext), and providers must execute proprietary model weights in environments vulnerable to software bugs and side-channel attacks.
• Limitations of Current Solutions:
  • Trusted Execution Environments (TEEs): While widely used, TEEs suffer from side-channel vulnerabilities (e.g., memory bus interposition), require trust in hardware manufacturers, and offer no cryptographic guarantees to users.
  • Generic Fully Homomorphic Encryption (FHE): While FHE offers strong cryptographic guarantees, applying "off-the-shelf" generic FHE to AI inference is currently impractical. Evaluating even modest transformer models requires millions of non-linear and structural operations, which are catastrophically expensive under standard FHE parameters due to noise growth and computational overhead.

2. Core Methodology: The "Meet in the Middle" Co-Design Paradigm

The authors argue that the solution lies not in optimizing one side (either the cryptosystem or the model) in isolation, but in a joint co-design approach. They leverage the observation that AI inference is structurally predictable:

• Circuit topology is fixed.
• Tensor shapes are known at compile time.
• Value distributions are bounded.
• There is no data-dependent branching.

This predictability allows for mutual specialization along two complementary axes:

Axis A: Specializing FHE for Inference

Instead of designing FHE for generic computation, the authors propose tailoring cryptographic primitives to the static nature of AI workloads:

• Offline Optimization: Since the circuit topology is known beforehand, aggressive optimizations (impossible in dynamic generic FHE) can be precomputed.
• Tailored Parameters: Co-designing the plaintext modulus, scaling strategy, and encoding to meet precision requirements while strictly controlling noise growth and circuit depth.
• Optimized Packing: Utilizing SIMD-style packing (in ring-based schemes like BFV/BGV/CKKS) to align ciphertext slots with the model's matrix multiplication structure. This drastically reduces the need for expensive cryptographic rotations and key switching.
• Static Bootstrapping: Instead of invoking bootstrapping (noise management) dynamically, the authors propose precomputing an optimal, static schedule based on the known architecture to globally minimize the total number of bootstrapping operations.

Axis B: Constraining Inference for FHE

The AI community must redesign neural architectures to be "FHE-friendly":

• FHE-Aware Neural Architecture Search (NAS): Modifying NAS to treat multiplicative depth and rotation count as primary objectives alongside accuracy. This guides the search toward shallow, wide layers and penalizes operations with high polynomial degrees.
• Reimagining Non-Linearities: Standard activations like ReLU and GeLU are non-polynomial and expensive to approximate homomorphically. The authors propose:
  • Training models with native low-degree polynomial activations.
  • Developing high-accuracy polynomial approximations for non-linear functions (e.g., Softmax).
• Quantization Aware Training (QAT): Targeting FHE parameters directly during training so the network learns to operate natively within the constraints of the plaintext modulus.
• Structured Sparsity: Enforcing block-structured sparsity patterns that align with SIMD packing strategies, allowing entire operations to be physically skipped during homomorphic evaluation rather than just zeroing out weights.

3. Key Contributions

• Unified Framing: The paper introduces a novel "meet in the middle" framework that unifies cryptographic constraints and model architecture constraints, moving beyond isolated research efforts.
• Static Optimization Strategy: Proposes shifting from dynamic, on-the-fly noise management to static, precomputed optimization schedules for bootstrapping and packing.
• FHE-Native NAS: Defines a new paradigm for Neural Architecture Search that prioritizes cryptographic efficiency (depth, rotation count) alongside accuracy.
• Proof of Concept (Softmax): The authors derived an experimental approximation for the Softmax function over a bounded logit range.
  • Result: The homomorphic evaluation of this approximation was faster than a straightforward scalar plaintext Rust implementation on the same CPU (excluding key generation, encryption/decryption, and communication overhead).
  • Accuracy: The approximation showed an error rate below 0.5%.

4. Results and Evidence

While the paper is a position paper outlining a paradigm rather than a full system deployment, it provides specific evidence of feasibility:

• Performance: The microbenchmark on the Softmax function demonstrates that with the right approximation and co-design, homomorphic evaluation can outperform naive plaintext implementations for specific components.
• Feasibility of Adaptation: The authors cite literature suggesting that ML models have high tolerance for quantization, pruning, and perturbations, supporting the viability of aggressive adaptation via QAT.
• Error Bounds: The proposed Softmax approximation maintains high accuracy (<0.5% error), suggesting that the loss introduced by polynomial approximation is manageable for practical inference.

5. Significance

This paper is significant because it challenges the prevailing assumption that FHE is too slow for modern AI.

• Paradigm Shift: It moves the field from "How do we make FHE faster?" to "How do we design AI to fit FHE?" and vice versa.
• Practical Privacy: By demonstrating that a co-design approach can yield efficient, cryptographically secure inference, it offers a viable path to deploying sensitive AI models without relying on the trust assumptions of TEEs.
• Future Research Direction: It sets a clear agenda for researchers to develop FHE-specific NAS tools, polynomial activation functions, and static optimization compilers, potentially unlocking the commercial viability of private AI inference.