Constant-Depth Encrypted Sliding-Window Max for Sensor Fleets

Many organizations would like an untrusted cloud server to keep running statistics over thousands of sensor streams, such as "the highest vibration reading on each turbine sensor over the last 1,024 ticks." They also do not want that server to see a single reading. Homomorphic encryption makes this possible in principle. It is a family of schemes in which the server computes directly on encrypted numbers. The cost is high. Every multiplication adds "noise" to a ciphertext, and once the accumulated noise reaches a fixed limit, the ciphertext must be refreshed by bootstrapping, an expensive procedure that removes the noise. Taking a maximum is especially costly, because a comparison has to be approximated by a high-degree polynomial. That uses many levels of the noise allowance at once.

The plaintext streaming literature has a good tool for windowed maxima. It keeps a tree of partial results so that old readings can be removed from the window without recomputing everything. Under encryption, however, each tree level stacks another comparison onto the noise. We propose to reorganize the window so that bootstrapping never sits on the path that produces each tick's answer. Most partial results in a first-in-first-out window stop changing once they are complete. These can be refreshed once, in the background, and then reused for many ticks. The work that must happen at each tick shrinks to a single encrypted comparison on already-refreshed inputs. Each ciphertext also carries one reading from each of thousands of different sensors, so the per-sensor cost is divided by the number of slots.

Core Claim

Two steps together turn encrypted sliding-window maxima into a deadline-bounded streaming operator.

The first step is packing across streams. An edge gateway encrypts, at every tick, one vector whose slot $i$ holds sensor $i$'s reading. Homomorphic encryption supports SIMD packing (many independent values in one ciphertext, all operated on at once), so this gives a full batch at every tick without waiting to accumulate data and without rotations, the slow operations that move values between slots.

The second step is a chunked window layout. All operations whose noise grows over time are moved to background workers that refresh results which will not change again.

Critical path. The answer for each tick costs one comparison circuit of depth $d$. Depth here means the number of multiplication levels the circuit uses up.

Background cost. The background work averages about one bootstrap per ciphertext per tick, independent of the window length $n$.

Recomputing the window from scratch, or running the plaintext tree directly on ciphertexts, instead puts about $\log_2 n$ comparisons in sequence on the critical path. For $n = 1024$ that is roughly ten.

This differs from the closest encrypted streaming work in three ways.

Against oblivious LTL monitoring. Oblivious Online Monitoring for Safety LTL Specification via Fully Homomorphic Encryption runs a temporal-logic automaton over encrypted bits. It bootstraps sequentially after each transition and takes about 24 seconds per data point. It handles a single binary stream and computes no numeric window aggregates.

Against encrypted bandits. Encrypted Linear Contextual Bandit keeps a cumulative encrypted regression with no window eviction. It took over 20 hours for 130 steps.

Against plaintext incremental aggregation. General Incremental Sliding-Window Aggregation supplies the plaintext idea of reusing partial aggregates for non-invertible operators like Max. It achieves $O(m + m\log(n/m))$ updates and up to 10x over recomputation at $n=1024$. It never considers noise depth. We keep its reuse principle but change the shape of the structure so that depth, not operation count, is what is minimized.

The scope is deliberately narrow. Sums, averages and variances do not need any of this. The gateway can send encrypted $x$ and $x^2$, and the server adds the newest reading and subtracts the expiring one. Those operations only add noise and need no bootstrapping. We include that path as a reference and focus the contribution on the non-invertible aggregates (Max, Min, and threshold alerts built on them) where the difficulty actually lies.

Research Program

Window layout. Split the window of $n$ ticks into chunks of $b$ ticks. Call the elements of the chunk currently being filled the prefix $P$, and the older completed elements still inside the window the stable region.

When a chunk completes at time $\tau$, the left edge of the window will move through the next $b$ positions before the following chunk completes. Background workers therefore precompute, for each of those $b$ left edges, the encrypted max over the range from that left edge to $\tau$. They bootstrap each of these $b$ suffix results once.

Per-tick work. At each tick the critical path does two things. It updates the running prefix max $P_t$ with one comparison, and it emits $\max(S_{\text{left}(t)}, P_t)$, where $S$ is the precomputed suffix result for the current left edge. Every $k$ ticks the prefix ciphertext would exhaust its levels, with $k = \lfloor L/d \rfloor$ and $L$ the levels available after a bootstrap. To avoid stalling, it is refreshed in the background with double buffering. The amortized background load per packed ciphertext is

$$ B \approx 1 + \frac{1}{k}\ \text{bootstraps per tick}, \qquad \text{background combines} = O\!\left(b + \tfrac{n}{b}\right)\ \text{per } b \text{ ticks}. $$

The first term counts the $b$ suffix refreshes spread over $b$ ticks. The second counts the work of building the suffix results from per-chunk maxima. Choosing $b \approx \sqrt{n}$ balances the combine work.

Deadline condition. The operator keeps up if two things hold. Each tick's critical path must finish within the tick interval. The background workers on the remaining cores must also clear $B$ bootstraps per tick before their results are needed $b$ ticks later.

Remaining design questions. First, we will use CKKS, a scheme for approximate arithmetic on real numbers, with a composite polynomial approximation of sign/max. We will measure how the comparison's depth $d$ trades off against max error on bounded sensor ranges. Second, slots of missing sensors are filled with a sentinel at the bottom of the range, with an encrypted validity mask, so a tick never waits for its slowest sensor. Third, we will extend the operator to a server-held, secret threshold alert that compares each encrypted window max to the threshold. This mirrors the two-sided confidentiality of oblivious monitoring. Fourth, we will measure how the background workers scale across cores as packed ciphertexts and evaluation keys saturate memory bandwidth. The file flags this as unknown: StreamBox relies on NUMA-aware memory placement for plaintext, while FlexMem characterizes homomorphic encryption as memory-bandwidth-bound.

Regime. The deployment we target has a thin edge gateway, comparable to the ROCK64-class boards used in the oblivious monitoring paper, that only encrypts. The server holds window state for $10^4$ to $10^5$ sensors and may hold proprietary thresholds.

Baselines

Naive plaintext reference. A plaintext sliding-window max computed with the incremental aggregator from General Incremental Sliding-Window Aggregation, on the same hardware and the same window sizes. It gives the speed floor and the exact answers used to score encrypted error. A gateway-side variant runs the same code on a ROCK64-class board. It tests whether outsourcing is needed at all, by checking whether the gateway can hold $n \times$ sensors of state at the tick rate.

Naive encrypted recompute. Recompute the encrypted max over the whole window every tick with a balanced comparison tree. It uses the same cross-stream packing, comparison polynomial and parameters, bootstraps whenever levels run out, and uses all cores. This is what a homomorphic-encryption practitioner would build first.

Encrypted incremental tree (key ablation). The binary partial-aggregate tree of General Incremental Sliding-Window Aggregation ported directly onto ciphertexts. It is given the same lazy bootstrapping and the same core count, so its only difference from our design is the shape of the structure and whether refreshes sit on the critical path. This is the strongest competitor, because it already avoids full recomputation.

Second ablation. Our chunked layout with all bootstraps done synchronously at each tick. It isolates the value of moving refreshes into the background from the value of the layout itself.

Additive reference. The subtract-on-evict sum/variance path. It shows the gap between invertible and non-invertible aggregates.

Prior encrypted streaming system. For context we cite Oblivious Online Monitoring. It reports processing individual simglucose data points in approximately 24 seconds or less, on a single binary-signal stream. That is a different computation, so it is context rather than a head-to-head comparison.

No reported result was found on Lacuna for encrypted sliding-window Max under any scheme.

Fairness and success criterion. All encrypted variants share the same parameter set, security level, tuning budget for $b$ and comparison degree, data, and machine. Beating the encrypted tree means two things at matched max error. The per-tick critical-path latency must be lower by roughly the factor $\log_2 n$ that the depth argument predicts. The operator must also sustain more sensor-ticks per second without the background queue of pending bootstraps growing.

Why not just…?

Why not just let the gateway compute the window max itself? This is the most serious threat. If the gateway can hold the state, encryption buys nothing beyond hiding the threshold. The first experiment measures exactly where a ROCK64-class gateway runs out of memory or tick budget on the turbine-fleet workload. The proposal is only justified above that point, or when the alert logic must stay secret from the data owner. If the gateway suffices at realistic fleet sizes, we will report that and narrow the claim to the secret-threshold setting.

Why not just pack each sensor's history into the slots of one ciphertext? Time-in-slots packing makes every window aggregate a sequence of rotations. The file identifies rotations as the dominant cost of cross-slot operations. It also leaves slots empty when there are few streams. We include it as a variant on the Pingmesh workload, where the number of IP pairs varies. This will show the crossover point: below some number of streams, rotations may win.

Why not use differential privacy or a hardware enclave instead? Differentially Private Stream Processing at Scale reaches 20 GB/s, but its server sees raw records. Enclaves, as discussed in Security, Performance and Energy Implications of Hardware-assisted Memory Protection Mechanisms on Event-based Streaming Systems, suffer paging when window state outgrows protected memory and leak access patterns. These alternatives answer a weaker threat model. We state that as a scope choice rather than claiming encryption dominates them.

Why not just distribute the encrypted work across a cluster? At the ciphertext sizes reported in CryptoNets, 367.5 MB for 4,096 inputs, moving state between machines is costly. The multicore scaling experiment will show whether a single node saturates before the background-bootstrap condition fails. Only then would scale-out be worth its network cost.

Proposed Experiments

Workloads. - Turbine fleet. The simulated fleet of 100 units × 1,000 sensors from Scalable Architecture for Anomaly Detection and Visualization in Power Generating Assets gives 100,000 streams, packed into about a dozen ciphertexts per tick. Its plaintext cluster ingested 399,000 samples/s. - Network latency. The Pingmesh netmon trace from StreamBox (88M records), with one slot per IP pair, tests sparse and irregular arrivals. - Blood glucose. simglucose places the system next to oblivious monitoring on the medical alert task.

Metrics. For window sizes from 64 to 4,096 and core counts from 1 to the full machine, we report:

  • critical-path latency per tick;
  • sustained sensor-ticks per second;
  • bootstraps per sensor-tick;
  • max error relative to the plaintext answer;
  • false alert rate of the secret-threshold extension;
  • peak memory;
  • the length of the background bootstrap queue over a long run (hours of simulated ticks).

Decisive checks. The central check is that critical-path latency stays flat in $n$ for our layout, while it grows roughly as $\log_2 n$ for the encrypted tree. Background bootstraps per tick should stay near $1 + 1/k$, independent of $n$, and the queue should stay bounded. Max error should match the tree's at equal comparison degree. The multicore curve will locate where memory bandwidth, rather than arithmetic, caps throughput.

If latency in our layout grows with $n$, or the queue drifts upward at realistic tick rates, the background-refresh idea fails. We would then report the deadline boundary it does reach.