Recommenders learn most from what users do, not what they say: clicks, skips, and how long someone lingers on a page. These passive logs are also some of the most sensitive data a service collects. Homomorphic encryption lets a server compute on data it cannot read. The obstacle is cost. Every multiplication on encrypted data adds noise, and once the noise budget is spent, the ciphertext must be refreshed by an expensive step called bootstrapping. A sequential model that updates its hidden state once per user action uses up that budget in proportion to the length of the history. This proposal argues that implicit profiling does not need depth that grows with history length. If every behavioral event is mapped to an embedding stored on the server, and the profile is just the sum of those embeddings, the encrypted profile can be updated one event at a time by encrypted addition, which adds almost no noise. Expressiveness is then restored with a single degree-2 interaction applied at query time. The whole pipeline, from event lookup to item scores, fits in about four multiplicative levels with no bootstrapping, whether the user has ten events or ten thousand.
The second idea concerns who needs the nonlinearity. In plaintext graph recommenders, highly active users and popular items benefit from nonlinear layers, while long-tail entities do better with purely linear propagation (Linear, or Non-Linear, That is the Question!). Under encryption, deciding per user whether to apply a nonlinear path normally costs an encrypted comparison. In our setting that decision is free, because the server already sees how many events a user has sent. It can route on that count in plaintext. The router therefore uses only metadata that has already leaked, and adds nothing to cryptographic cost or leakage.
Core Claim
A behavioral-stream recommender can be built so that its encrypted state is an additive sum. The only nonlinearity is one factored degree-2 term, similar to the pairwise interactions in a factorization machine. Such a model will close most of the accuracy gap to strong plaintext sequential recommenders on public implicit-feedback benchmarks. It runs under leveled CKKS (the approximate-arithmetic homomorphic scheme) at a constant multiplicative depth of about 4. Per-event update cost is independent of history length, and per-query latency is independent of history length as well. We further predict that the degree-2 term's benefit concentrates in high-activity users, as HMLET's centrality finding suggests. If so, a count-based plaintext router can skip the degree-2 cost for long-tail users with little loss.
Concretely, let $e_t \in \mathbb{R}^d$ be the server-held embedding of the event token at step $t$. A token combines the item ID with a discretized dwell-time bucket, following the idea of reading intent from session rhythm without content. Let $s = \frac{1}{n}\sum_{t=1}^{n} e_t$ be the profile after $n$ events, and $V$ the item embedding matrix. The model scores items as
$$ \text{score} = V\big[(W_1 s)\odot(W_2 s) + W_3 s\big]. $$
Here $W_1, W_2, W_3$ are plaintext server weights and $\odot$ is elementwise product. Expanding the product shows that it contains every pairwise interaction $(W_1 e_i)\odot(W_2 e_j)$ among the user's events, so co-occurrence structure within the history is captured despite the additive state. Each stage consumes one level. The encrypted lookup uses one level via digit decomposition; accumulation uses none; the projections use one; the Hadamard product uses one; and the plaintext scoring matrix uses one. The factor $1/n$ is folded into $W_1, W_2, W_3$ by the server, which knows $n$.
Relation to Prior Work
Two papers put private computation directly on recommendation-like problems, and they mark the gap. HE-LRM makes encrypted embedding lookups cheap. The client splits each feature index into base-$p$ digits before encryption, so a lookup into the server's decomposed tables costs a single multiplicative level. HE-LRM applies this to static tabular click-prediction features and reports 489 seconds per Criteo prediction on CPU. We reuse its lookup technique as a component. What HE-LRM leaves out, and we add, is a stream of lookups accumulated into a persistent profile. Homomorphically Encrypted Linear Contextual Bandit (HELBA) does maintain encrypted state over time. It must, however, approximate matrix inversion, square roots, and argmax with polynomials, and it needed over 20 hours for 130 steps at dimension 2. Our design deliberately contains no inversion, division, or encrypted comparison.
On the modeling side, PARS shows that browsing histories alone can supervise strong recommenders. It treats each history as a set of candidate labels that contains the true target, and reports AUC 0.9398 on YooChoose, 0.9718 on RetailRocket, and 0.8953 on Taobao. Conv4Rec models implicit and explicit feedback jointly with weight-shared 1×1 convolutions. Both methods motivate using behavior-only signals, and both set the plaintext accuracy we try to approach. Neither is designed for encrypted evaluation: PARS relies on a Transformer and iterative disambiguation.
PolyNeXt supplies the idea that Hadamard products of linear projections can replace activation functions without accuracy loss, reaching 83.9% ImageNet top-1. It also constrains us. Its depth-over-width stacking would multiply multiplicative depth, which is why we use exactly one such product. The HE-friendly architecture work motivates treating multiplicative depth as the cost to minimize. HEMET shows that depth drives encrypted latency. NASS shows that cost jumps sharply when parameter changes force a larger ring dimension. SAFENet shows that nonlinearity can be kept only where it matters. We take SAFENet's selectivity and apply it per user rather than per channel.
Finally, p²RAG avoids encrypted sorting through interactive two-server bisection. We avoid encrypted top-$k$ differently, by returning encrypted scores for decryption on the client. We state the cost of this plainly below.
Research Program
The client tokenizes each action locally into an item ID and a dwell bucket, then digit-decomposes and encrypts the token. The server performs the HE-LRM-style lookup and adds the result into the user's encrypted profile ciphertext. Recency matters for implicit signals, and a pure sum forgets order. To handle this, the server keeps a small fixed number of window profiles, for example the current session, the last day, and all history. It stores each event's encrypted lookup so that expired events can be subtracted when a window rolls over. The degree-2 head then takes the concatenated window profiles as input. Subtraction and addition are depth-free, so recency costs storage but no noise budget.
At query time, the server evaluates the head over a candidate set of items. SIMD packing, which places thousands of values in the slots of one ciphertext, lets the scoring matrix be applied as plaintext-ciphertext products. The server returns encrypted scores, and the client decrypts them and takes the top-$k$ locally. The router uses the plaintext event count $n$ to decide whether to evaluate the full degree-2 head or only the linear term $V W_3 s$. It is trained by sweeping an activity threshold on validation data.
Training happens in plaintext on public logs, with the same partial-label objective as PARS so that accuracy comparisons are like for like. Two extra constraints apply during training. Weights are regularized so that intermediate activations stay within a bounded range that CKKS parameters can hold. Gaussian noise matched to measured CKKS error is injected into activations, so the model is robust to approximate arithmetic.
Three limitations are part of the threat model, and each will be measured. First, the server learns the number and timing of a user's events; padding with dummy events is evaluated as an optional countermeasure. Second, the client learns scores for the whole candidate set, which leaks some model information. Third, candidate generation itself is out of scope and assumed to be done by a coarse non-personalized or on-device stage.
Baselines
The naive reference points are two. The first is an unencrypted server running the identical model on plaintext logs, which gives the accuracy ceiling for our architecture and shows exactly how much CKKS error costs. The second is a linear sum-pooling model, $\text{score} = V W_3 s$. This model is also constant-depth and cheaper by one level, so it is what a cryptographer would build first. It is trained with the same objective and the same hyperparameter search budget. Beating it requires a statistically significant gain in AUC and Recall, averaged over seeds, and we specifically predict the gain will appear in the top activity quartile.
The strongest plaintext competitor for accuracy is PARS, with reported AUC 0.9398 on YooChoose, 0.9718 on RetailRocket, and 0.8953 on Taobao under its own protocol. We will rerun it with its released settings on our data splits, alongside our model, under the same protocol. It is the strongest competitor because it extracts supervision from exactly the browsing-only signal we use. We do not expect to beat it. Success means retaining a large, pre-registered fraction of its AUC, with 95% as the target, at a small fraction of the cost of any encrypted Transformer. On MovieLens 25M we compare against Conv4Rec's reported Recall@100 of 0.5860.
The strongest encrypted-cost competitor is HE-LRM, which reports 489 s single-threaded CPU latency on Criteo and 24 s on UCI Heart Disease. We run it on the same hardware, in two configurations. In the naive one it re-encodes the whole history as features for each query. In the other we give it our accumulation trick with a linear head. That second configuration isolates the contribution of the degree-2 head. Beating HE-LRM means lower per-query latency at matched history length, and latency that stays flat as history grows.
There is no reported encrypted result on Lacuna for a sequential behavioral recommender. HELBA's 20-hour, 130-step, $d=2$ run is the only encrypted sequential reference point, and it is too small to compare against directly.
The key ablations are four. Removing the degree-2 term gives the linear model above. Removing the router means applying the degree-2 head to all users. Removing window profiles leaves a single all-history sum. Removing dwell buckets leaves item-only tokens, which tests whether rhythm information survives additive pooling.
Why not just…?
Why not just build the profile on the client's device and send only an encrypted profile vector? This is the most serious alternative, and it may win whenever the event encoder can be public and small. HE-LRM argues that providers will not ship large proprietary embedding tables to devices, and that devices cannot hold millions of item embeddings. That argument covers the embedding tables, but a distilled on-device encoder is not covered. We will therefore train a small public encoder, capped at a mobile-scale parameter budget, that produces $s$ on the device. The server then applies the same encrypted head to it. If this matches our server-table model's accuracy, the encrypted-lookup stage is unnecessary. The contribution then shrinks to the constant-depth head and the router, and we will report that result as such.
Why not just use a linear model, since it is even cheaper under encryption? HMLET reports that adding nonlinearity for central nodes improved NDCG@20 by 6.00% over purely linear LightGCN on Amazon-Book, which suggests the linear model underfits heavy users. That result comes from graph propagation, not from pooled sequences, so it motivates the question without settling it. The activity-stratified comparison between the degree-2 head and linear pooling does settle it. If the gap is negligible in every quartile, we recommend the linear model and drop the degree-2 claim.
Why not just run a polynomial Transformer with bootstrapping? PolyNeXt shows that polynomial attention can be accurate. Its stacked depth, however, and the depth dependence documented by HEMET and NASS, mean that every layer and every additional history step would add levels or bootstrapping. We will measure the plaintext accuracy of a PARS-style Transformer against our head. That gap is the maximum anyone could gain by paying bootstrapping costs, and we will set it beside measured per-level and per-bootstrap latencies.
Why not just add local differential privacy noise to the clicks? HELBA's analysis shows that local noise degrades learning, for example to $O(T^{3/4})$ regret against $\widetilde{O}(d\sqrt{T})$ without it. Implicit signals such as dwell buckets are already weak. We will include a baseline that perturbs event tokens with local differential privacy at several privacy levels and trains our same model, to show where on the utility curve it falls.
Proposed Experiments
The data are YooChoose, RetailRocket, and Taobao, following the PARS protocol, and MovieLens 25M, following the Conv4Rec protocol. Criteo is used only to calibrate cost against HE-LRM. Metrics are AUC, Recall@100, and NDCG@20, each reported overall and by activity quartile. Cryptographic metrics are per-event update latency, per-query latency, ciphertext and key sizes, and client-server bytes per query. We also measure rank agreement between encrypted and plaintext scores, as top-$k$ overlap and Kendall's tau.
Four checks are decisive. First, per-query latency must stay flat as history length varies from 10 to 1,000 events, while the naive HE-LRM configuration grows. Second, encrypted top-20 overlap with plaintext should stay above 0.95 at the chosen CKKS parameters with no bootstrapping. Third, the degree-2 head must beat linear pooling in the top activity quartile. Fourth, the count-based router should keep most of that gain while evaluating the degree-2 head for only a minority of users.
If the first two checks hold, a sequence-based encrypted recommender becomes practical without bootstrapping. The third and fourth checks determine whether the nonlinearity and the router actually earn their place.
References
- Linear, or Non-Linear, That is the Question!
- HE-LRM: Encrypted Deep Learning Recommendation Models using Fully Homomorphic Encryption
- Homomorphically Encrypted Linear Contextual Bandit
- PARS: Partial-Label-Learning-inspired Recommender Systems
- Conv4Rec: A 1-by-1 Convolutional Autoencoder for User Profiling Through Joint Analysis of Implicit and Explicit Feedback
- Activation-Free Backbones for Image Recognition: Polynomial Alternatives within MetaFormer-Style Vision Models
- HEMET: A Homomorphic-Encryption-Friendly Privacy-Preserving Mobile Neural Network Architecture
- NASS: Optimizing Secure Inference via Neural Architecture Search
- SAFENet: A Secure, Accurate and Fast Neural Network Inference
- $p^2$RAG: Privacy-Preserving RAG Service Supporting Arbitrary Top-$k$ Retrieval