🤖 machine learning

Public-Decay Homomorphic State Space Models for Private Sequence Inference

This paper introduces Public-Decay Homomorphic State Space Models (HSSMs), a novel architecture that achieves encrypted sequence inference with accuracy matching plaintext baselines while significantly reducing latency and computational depth compared to existing homomorphic attention mechanisms.

Original authors: Luis Brito

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Luis Brito

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you want to ask a secret question to a powerful AI assistant, but you are terrified that the assistant might peek at your question or your answer. To solve this, you put your question inside an unbreakable, magical glass box (this is Fully Homomorphic Encryption, or FHE). The assistant can perform calculations inside the box without ever opening it, and when they are done, they hand the box back to you. You open it, and there is your answer.

However, there's a catch: doing math inside these magical glass boxes is incredibly slow and exhausting. It's like trying to solve a complex puzzle while wearing thick, heavy oven mitts. Every time the AI tries to mix two pieces of data together, it has to do a massive amount of work.

This paper introduces a new way to build these "secret AI" brains, called Public-Decay Homomorphic State Space Models (HSSM). Here is how it works, using simple analogies:

The Problem: The "Heavy Lifting" Trap

In a standard secret AI (like a Transformer), every time the AI processes a new word in a sentence, it has to mix the new secret word with the old secret memory of the sentence.

The Old Way: Imagine you are carrying a heavy, locked safe (the memory) and you have to mix it with another heavy, locked safe (the new word). You have to lift both safes, mix them, and lock the result. Doing this for every word in a long story is exhausting and slow. The "weight" (computational cost) keeps piling up.

The Solution: The "Public Decay" Trick

The authors of this paper realized they could change the rules slightly to make the job easier. They proposed a new design where the "memory" doesn't need to be mixed with a new secret every time.

The New Way (HSSM): Imagine the AI has a memory safe that is slowly leaking air (decaying) on its own. This "leaking" is a public rule that everyone knows (it's not a secret).
- Instead of mixing two heavy locked safes, the AI just lets the old memory leak a little bit (which is easy because it's a public rule) and then adds a small, new secret note into the mix.
- The Analogy: Think of it like a bucket with a small hole. The water level (memory) naturally drops a little bit every second (public decay). You only have to pour in a small cup of new water (the new secret input) to keep it going. You don't have to lift the whole bucket and mix it with another bucket every time.

Why This Matters

By using this "leaking bucket" method, the AI avoids the most expensive, heavy-lifting math operations.

Speed: The paper tested this on real computers (specifically powerful NVIDIA L40S GPUs). They found that this new method was about 5 times faster than the previous best methods for processing full sentences.
Memory: Because the AI doesn't need to keep a massive, growing list of every single word it ever saw (like a traditional AI does), it uses much less computer memory. It's like keeping a single running note instead of a growing stack of papers.
Accuracy: Despite being faster and lighter, the AI still got the answers exactly right. On tests involving movie reviews (Rotten Tomatoes) and short sentences (SST-2), the secret AI got the same correct answers as a normal, non-secret AI.

What They Actually Did (and Didn't Do)

The researchers built a specific system where:

You (the Client): Do the hard work of turning your text into numbers, encrypting them, and putting them in the box.
The Server: Takes the box, runs the "leaking bucket" math, and hands the box back.
You (again): Open the box to see the result.

Important Limitations:

This paper does not claim to have solved the problem of reading raw text inside the box. The text still has to be turned into numbers before it goes into the box.
It does not claim to be a full, general-purpose chatbot (like a massive language model) yet. It is a specific tool for analyzing short sequences of data (like classifying if a review is positive or negative).
The "leaking" (decay) is a fixed, public rule. If the AI needed to change the leak rate based on a secret, the magic would break, and it would go back to being slow.

The Bottom Line

This paper proves that by changing how the AI "remembers" things—switching from "mixing two heavy secrets" to "letting a secret leak and adding a small drop"—we can make secret AI much faster and more practical. It's a clever engineering trick that keeps the privacy promise while removing the heavy burden of the math.

Technical Summary: Public-Decay Homomorphic State Space Models for Private Sequence Inference

1. Problem Formulation

The paper addresses the high computational cost of performing sequence inference under Fully Homomorphic Encryption (FHE). While FHE enables private inference where a client encrypts inputs and a server evaluates models on ciphertexts, standard sequence models face severe constraints. Operations routine in plaintext neural networks—such as non-polynomial activations, softmax, layer normalization, and context-wide attention—become first-order system constraints under FHE due to multiplicative depth, rotation costs, and ciphertext materialization.

Specifically, the paper identifies a bottleneck in encrypted selective recurrence. In a naive encrypted recurrent block (e.g., an encrypted GRU or LSTM), the state update typically involves multiplying an encrypted, input-dependent gate by an encrypted carried state ( $h_t = g_A(x_t) \cdot h_{t-1} + \dots$ ). This ciphertext-ciphertext multiplication consumes multiplicative depth at every time step, rapidly exhausting the available noise budget and necessitating expensive bootstrapping or refresh operations.

2. Methodology: Public-Decay HSSM

The authors propose Public-Decay Homomorphic State Space Models (HSSMs), a recurrent/state-space block designed to avoid ciphertext-ciphertext multiplication on the recurrent carry path.

Core Mechanism: The design fixes the recurrent decay coefficient ( $a$ ) to be public/plaintext. The state update equation is:
$h_t = a \cdot h_{t-1} + g(x_t) \cdot u(x_t)$
Here, $h_t$ is the encrypted state, $a$ is a public scalar, and $g(x_t)u(x_t)$ represents the local write path.
Depth Reduction: By making the carry term ( $a \cdot h_{t-1}$ ) a ciphertext-plaintext operation, the paper removes the multiplicative depth growth associated with the recurrent carry. The only ciphertext-ciphertext multiplication occurs in the local write path ( $g \cdot u$ ), which is bounded and local to the current step.
System Architecture:
- Client-Side: Handles tokenization, frozen fastText lookup, train-normalized random projection, clipping, encryption, decryption, and thresholding.
- Server-Side: Receives encrypted bounded projected features. It performs public affine projections, evaluates low-degree encrypted gate/write polynomials, performs the local write multiplication, and aggregates the state using the public decay.
- Constraints: The model parameters (weights, decay, projections) are public. The server observes metadata (sequence length, operation shapes) but not the encrypted data or secret keys.

3. Key Contributions

The paper makes four primary contributions:

Architectural Specification: Defines the minimal HSSM block with a public-decay invariant, explicitly separating client-side preprocessing from server-side homomorphic evaluation.
Symbolic Comparison: Contrasts HSSM against transformer-style encrypted inference and naive encrypted selective recurrence. It demonstrates that HSSM maintains a fixed-size encrypted state and avoids the multiplicative depth accumulation of naive recurrence.
Empirical Validation: Reports real FHE artifacts across OpenFHE (CPU) and FIDESlib (CUDA) backends. This includes matched level traces showing consistent noise behavior across backends and L40S GPU measurements.
Task Quality vs. Systems Cost: Separates task accuracy from system latency. It validates the approach using a repaired fastText workflow (avoiding "toy" features) and compares HSSM against HE-friendly polynomial attention mechanisms.

4. Experimental Results

The evaluation focuses on the Rotten Tomatoes and SST-2 sentiment analysis datasets using a bounded-feature interface (512 projected scalars per example).

Accuracy: The encrypted HSSM path exactly matches plaintext classifications, achieving 0.7505 accuracy on Rotten Tomatoes and 0.7420 on SST-2.
Latency and Efficiency:
- Against full-sequence polynomial attention, HSSM is approximately 5× faster (e.g., ~15ms vs. ~75ms for evaluation) while matching or exceeding task quality.
- Against cached final-token polynomial attention, HSSM shows 1.34–1.62× lower latency on longer contexts (T=16, 32) and maintains a smaller logical encrypted-state footprint.
Resource Usage:
- Memory: HSSM retains a single encrypted state ciphertext regardless of sequence length ( $T$ ), whereas polynomial attention requires $O(T)$ or $O(T^2)$ ciphertexts for caches and materialized scores. Stress tests show HSSM completing sequences up to $T=36$ on an L40S GPU, while materialized quadratic attention fails at $T=36$ due to out-of-memory errors.
- Depth: The projected HSSM succeeds under depth 8 / ring 32768, whereas the comparable encrypted Q/K/V attention block requires depth 10 / ring 65536 to succeed at the same sequence lengths.
Noise and Levels: Matched traces on OpenFHE and FIDESlib confirm that the expanded HSSM path finishes at final level 3 with a noise-scale degree of 2, without invoking bootstrapping for the bounded-feature workflow.

5. Significance and Claims

The paper claims that public-decay HSSM is a practical FHE co-design pattern for server-side encrypted sequence inference from bounded projected features.

Design Lever: The central contribution is the demonstration that replacing an encrypted input-dependent carry gate with a public/plaintext decay is a measurable lever to reduce encrypted carry-path pressure.
Scope of Claims: The authors are modest about the scope. They do not claim:
- Homomorphic tokenization or embedding lookups.
- Model-private weights (weights are public).
- Exact softmax, full transformer blocks, or production-scale language model serving.
- Security against malicious servers or side-channel attacks.
Conclusion: The results establish that for bounded-feature inference, public-decay HSSM offers a concrete trade-off: it achieves non-toy task utility with fixed-state encrypted computation, lower latency than full-sequence attention, and reduced logical state growth, all while operating within a manageable FHE depth budget without bootstrapping.