Satellite and aerial imagery of sensitive sites, such as borders, military installations, or private land, often has to be analyzed by a cloud service whose model the image owner cannot inspect, and which the owner does not trust with the pixels. Fully homomorphic encryption (FHE) lets a server compute on encrypted data and return an encrypted answer that only the client can read. Its cost is the obstacle. Encrypted inference runs three to six orders of magnitude slower than plaintext, and the most expensive part is long chains of multiplications. Semantic change detection, the task of labeling each pixel with a "from-to" land-cover transition such as vegetation to building, looks like a poor fit. Strong change models process two high-resolution images jointly through deep, asymmetric, attention-heavy networks, and every new pair of dates repeats that work.
We propose to restructure the problem so that the expensive encrypted computation is done once per image rather than once per pair. A server runs a polynomial-only encoder on each encrypted acquisition and keeps the encrypted per-location embedding. Change between any two dates is then scored by a learned bilinear head: one ciphertext-by-ciphertext multiplication followed by plaintext-weighted sums. This is the cheapest possible interaction between two encrypted feature maps. It is also the natural shape of from-to classification, because the transition classes are the Cartesian product of per-date classes. The bilinear head contains classical post-classification comparison as its rank-one special case, so it has a clear baseline and a clear dial between "compare two independent segmentations" and "learn the interaction."
Core Claim
A rank-$r$ bilinear transition head on independently computed per-date embeddings recovers most of the accuracy advantage that jointly trained bitemporal change models hold over post-classification comparison. It does so at a multiplicative depth of one beyond the encoder. Under FHE, this makes the amortized cost of each additional date comparison nearly free. Concretely, for embeddings $e_1, e_2 \in \mathbb{R}^d$ at a location from dates $T_1, T_2$, the score for transition $i \to j$ is
$$ s_{ij} = \sum_{k=1}^{r} (u_{ik}^\top e_1)(v_{jk}^\top e_2) + a_i^\top e_1 + b_j^\top e_2 , $$
where $u_{ik}, v_{jk}, a_i, b_j$ are plaintext weights held by the server, $i, j$ range over the $N$ land-cover classes, and $r$ is the interaction rank. The linear projections cost only plaintext multiplications. The only ciphertext-ciphertext product is $(u^\top e_1)(v^\top e_2)$. The client decrypts the $N^2$ scores per location (36 for SECOND's six classes) and takes the argmax locally, which avoids an encrypted comparison.
If $r=1$ and $u, v$ are tied to each date's class-logit directions, $s_{ij}$ becomes a product of per-date class scores, which is post-classification comparison. Larger $r$ lets the model learn which co-occurring feature patterns indicate real change, as opposed to seasonal or sensor noise.
Relation to Prior Work
The motivation comes from two findings in the change literature. First, learned change heads clearly beat post-classification comparison: Change is Everywhere reports more than 10% IoU over that baseline on LEVIR-CD. Second, change can be learned from unpaired single images. ChangeStar and ChangeStar2 do this through single-temporal supervision (STAR), which builds synthetic change labels by pairing unrelated images and XOR-ing their masks, and ChangeStar2 reaches 85.4% F1 on LEVIR-CD. STAR shows that per-image representations carry most of what change needs. Its ChangeMixin modules, however, still fuse the two images through convolutional stacks, which are deep in encrypted terms.
We reuse STAR's training recipe and its temporal-symmetry idea, which says that swapping the two dates should reverse the change. The change is that the fusion becomes a single bilinear step. Joint architectures such as Asymmetric Siamese Networks (pyramids that treat the two dates differently), CAT (a coarse-to-fine tree over transition classes with learned routing), and CorrFusionNet (correlation-weighted fusion with $L_2$ distances) set the accuracy ceiling. All three rely on routing, absolute differences, distances, or deep cross-temporal attention, which are either non-polynomial or high-depth. We do not try to encrypt them. We use them as the targets the separable model must approach.
On the encryption side, CryptoNets established square activations and slot packing. SAFENet showed that blanket polynomial replacement hurts accuracy, especially in early layers. HEMET showed the "depth trap": FLOP-light mobile networks get slower under encryption because they stack layers. HEMET also folds normalization and polynomial coefficients into the weights, a technique we reuse. HEMET constrains our encoder design directly. The 1.4M-parameter ShuffleNet backbone that makes ChangeStar2 efficient in plaintext is exactly the deep, thin shape that HEMET warns against, so our encoder will be shallow and wide.
PolyNeXt supplies the polynomial building blocks: Hadamard-product MLPs and convolutions, plus polynomial attention. It reaches 50.6 mIoU on ADE20K segmentation, but it was profiled only in plaintext and never on bitemporal input. Secure Semantic Communication With Homomorphic Encryption is the closest existing combination of encryption and semantic features. It shows that features survive encryption in a low-resolution reconstruction and classification pipeline, but it has no temporal comparison. As far as the file shows, no one has run change detection under FHE, and no one has used the separable structure of from-to classes to amortize encrypted cost.
Research Program
The work has three parts.
The first is a plaintext study of separability. We train STAR-style encoders with the bilinear head at ranks $r \in \{1, 4, 16, 64\}$, with ordinary activations, on SECOND, DynamicEarthNet, and LEVIR-CD. This asks how much of the joint-model advantage survives when interaction is restricted to a single bilinear step. Nothing about encryption is involved yet, and if this step fails, the project stops here honestly.
The second is polynomialization. We rebuild the encoder from PolyNeXt-style blocks under an explicit multiplicative-depth budget, swept from 6 to 12 levels beyond input packing. HEMET's block-wise depth-versus-width search chooses the shape, and coefficient merging is applied. We measure how much accuracy each depth level buys.
The third is encrypted execution. We run the encoder and head in an approximate-arithmetic FHE scheme (CKKS) without bootstrapping, the costly operation that resets encryption noise. Inputs are tiles cropped from SECOND and DynamicEarthNet. The encrypted embeddings are stored server-side as an archive, and every new acquisition is compared against the archive with only the head. We report multiplicative depth, ciphertext bytes uploaded and stored, single-tile latency, and amortized latency per compared pair as a function of the number of dates $T$.
The amortization argument has a known shape. A joint model costs $O(P)$ encoder passes for $P$ compared pairs. The separable model costs $O(T)$ encoder passes plus $P$ head evaluations. For consecutive-month comparisons ($P = T-1$) this is only about a 2× saving. For all-pairs or archive-versus-new queries ($P$ up to $T(T-1)/2$), the saving grows linearly in $T$. We will report both regimes rather than only the favorable one.
Baselines
The naive reference point is encrypted post-classification comparison. The same polynomial encoder is fine-tuned as a per-date segmenter, the client decrypts the per-date class maps, and the from-to label is formed by pairing the two argmaxes. It has identical encrypted cost to our method minus the head, so it isolates whether learned interaction is worth one extra level. It runs on the same encoder weights initialization, data, and tuning budget. Beating it means a statistically clear gain in SeK on SECOND and in the semantic-change score on DynamicEarthNet. The proposal is only worth pursuing if the gain is a substantial fraction of the more-than-10% IoU margin that Change is Everywhere reports for learned heads over this kind of comparison on LEVIR-CD.
The strongest plaintext accuracy baselines are ASN and CAT on SECOND. ASN reports 69.1 mIoU and 15.5 SeK with standard testing. CAT reports 67.74% $F_{\text{overall}}$ and 63.64% $F_{\text{types}}$. On DynamicEarthNet, the dataset paper reports 37.9% mIoU for supervised monthly training, with binary-change scores around 10–11% and semantic-change scores of 25–28%. On LEVIR-CD, ChangeStar2 reports 85.4% F1. We quote these numbers as published and also retrain one joint model ourselves under our tile crops so the comparison uses matched inputs and an equal number of training epochs. We do not expect to beat these models in accuracy. The bar is to land within a stated gap, which we target at no more than half of their margin over post-classification comparison, at a fraction of their encrypted cost.
The strongest encrypted competitor does not exist in the literature. No reported result was found on Lacuna for change detection under FHE. We therefore build one: a joint Siamese polynomial network that fuses the two dates by squared feature difference, the low-degree replacement for absolute difference, at matched total depth and parameter count. It is run per pair with no archive reuse. Beating it means equal or better accuracy at lower amortized latency once $T \geq 3$. For scale, the only full-model encrypted latency in the file is HE-Transformer at 548.87 seconds and about 56 GB of traffic for one small medical image, from A Systematic Comparison of Encrypted Machine Learning Solutions. We cite this as context, not as a matched baseline.
The key ablation sweeps the rank $r$ from 1 (post-classification comparison) upward. Untying $u, v$ from the class directions separates "learned interaction" from "more parameters." Removing the temporal-symmetry loss tests whether the STAR recipe matters once fusion is this shallow.
Why not just…?
Why not just run CAT or ChangeStar2 inside a hardware enclave? A trusted enclave ran a convolutional model in 0.14 seconds where FHE took over nine minutes (A Systematic Comparison). For many users that settles the question, and we say so. Our setting is the one where hardware trust is unacceptable because of side channels or a vendor's root of trust, and where only a cryptographic guarantee is acceptable. The proposal does not claim to beat enclaves on speed. It claims to make the cryptographic option less far behind.
Why not use interactive multi-party computation, which evaluates ReLU natively? CrypTen ran the same model in 0.25 seconds. Multi-party computation needs a round trip per nonlinear layer, though, and SecureNets identifies client latency as the bottleneck of interactive schemes. For ground stations on slow links, or archives queried asynchronously, a single-round protocol matters. We will report the number of rounds and bytes for both protocols, but we will not benchmark multi-party computation latency ourselves. This remains a real alternative for well-connected clients.
Why not just do encrypted per-date segmentation and compare classes on the client? This is the most serious threat, because it has the same amortization property for free. It is our naive baseline, and the rank sweep settles it directly. If $r>1$ does not clearly beat $r=1$ in SeK and in binary-change scores on DynamicEarthNet, where post-classification comparison should suffer most because only about 5% of pixels change and per-date errors compound, then the bilinear head adds nothing. In that case the right recommendation is encrypted segmentation plus client-side comparison, and we will report exactly that.
Why not take CAT and replace every activation with $x^2$? SAFENet shows that wholesale replacement destroys accuracy in early layers, and PolyNeXt needed special stabilizers just to train polynomial backbones. CAT's routing and pyramids add depth on top of that, and HEMET's depth trap says that depth dominates encrypted latency. The squared-difference joint baseline above is the fair, depth-matched version of this idea, and it is the version we test.
Decisive Checks
Three results decide the project. First, on SECOND and DynamicEarthNet in plaintext, the bilinear head must recover at least half the gap between rank-one comparison and the retrained joint model. If it does not, separability fails and the encryption work is moot. Second, after polynomialization within a 12-level budget, accuracy must stay within a few SeK points of the plaintext separable model. Third, under CKKS without bootstrapping, the separable model's amortized per-pair latency must fall below the depth-matched joint encrypted baseline at $T \geq 3$, with the crossover measured on DynamicEarthNet's monthly sequences. Any one failing is a publishable negative result, and stating these thresholds in advance keeps us from having to argue around them.
References
- Change is Everywhere: Single-Temporal Supervised Object Change Detection in Remote Sensing Imagery
- Single-Temporal Supervised Learning for Universal Remote Sensing Change Detection
- Asymmetric Siamese Networks for Semantic Change Detection
- CAT: a coarse-to-fine attention tree for semantic change detection
- Multi-Temporal Scene Classification and Scene Change Detection With Correlation Based Fusion
- CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy
- SAFENet: A Secure, Accurate and Fast Neural Network Inference
- HEMET: A Homomorphic-Encryption-Friendly Privacy-Preserving Mobile Neural Network Architecture
- Secure Semantic Communication With Homomorphic Encryption
- DynamicEarthNet: Daily Multi-Spectral Satellite Dataset for Semantic Change Segmentation
- A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification
- SecureNets: Secure Inference of Deep Neural Networks on an Untrusted Cloud