A hospital or photo service may want to store image records on a cloud server it does not trust, and later retrieve "all records of category X". The catch is that the categories are not fixed in advance: a model keeps finding new ones in unlabeled data as it arrives, and keeps changing its mind. It merges two tentative groups, splits one that was too broad, and lets old groups shift. Encrypted search systems were built for a fixed vocabulary of keywords. Their two dynamic guarantees are forward privacy (new records cannot be linked to earlier searches) and backward privacy (deleted records leave no trace in later searches). Both assume that a record's keyword never changes after insertion. Systems that discover categories over time break that assumption on every session.
We propose a simple fix with a measurable cost. Each record is encrypted once, under a small, permanent "micro-cluster" identifier. The micro-cluster is a fine-grained group produced by deliberately over-clustering. Discovered categories then exist only as a private mapping from category to a set of micro-clusters. Merges, splits and relabelings become edits to that small mapping and never touch the encrypted records. The open question this proposal answers is empirical and specific: how much discovery accuracy is lost by forbidding records from ever being reassigned below the micro-cluster level, and how much the server learns from the sets of micro-cluster tokens that searches reveal.
Core Claim
Several systems already discover categories by over-clustering and then merging. Freeze and Cluster (FAC) clusters features from a frozen pretrained vision transformer (an image model whose weights stop changing after base training), over-clusters, and merges. PromptCCD-U (PromptCCD) splits and merges Gaussian components. Grow-and-merge pipelines (Adaptive Discovering and Merging) do the same in stages.
In all of these, each category is in effect a union of finer groups. We claim that this structure is exactly what makes forward and backward privacy compatible with a changing taxonomy. If every category is a union of permanent micro-clusters, the encrypted index never needs re-encryption. Forward privacy reduces to the standard per-keyword guarantee of a counter-based scheme such as Diana (Bost et al.), and backward privacy for genuine deletions (for example, data-erasure requests) reduces to per-keyword backward privacy.
The cost moves to two places. The first is accuracy, because a micro-cluster that later turns out to straddle two true classes can never be cut. The second is a new "taxonomy leakage": the server sees which groups of micro-cluster tokens are searched together.
The approach also eases a known cryptographic bottleneck. Puncturable-encryption schemes like Janus degrade after a few hundred deletions per keyword (Bost et al.). A naive design deletes and re-inserts records on every merge, and so burns through that budget. Our design performs no deletions for taxonomy edits, and spreads real deletions across many fine-grained keywords.
The cost of a taxonomy edit makes the contrast concrete. If an edit affects categories containing $N$ records in total, delete-and-reinsert costs $O(N)$ encrypted updates. Each of those updates is visible to the server, so it also leaks the sizes of the affected categories. Our design costs $O(k)$ client-side map edits and zero server updates, where $k$ is the number of micro-clusters involved.
Research Program
The system has three parts.
The first part is the discovery model, run on the client or inside a trusted enclave. Following FAC, it uses a frozen backbone, which keeps micro-cluster centroids fixed in place. Each arriving image is assigned once to its nearest micro-cluster, or opens a new one. Category discovery then runs as merging and splitting over micro-cluster centroids only, never over individual records. This is a deliberate restriction relative to FAC, PromptCCD and the soft nearest-neighbour method of Zhao et al., all of which may re-cluster individual points freely.
The second part is the encrypted index. It is a forward-private dynamic scheme keyed by micro-cluster identifiers. We use a Diana-style per-keyword counter, as in RSPP and Bost et al., and add a backward-private deletion layer. One variant of that layer is software-only (Janus/Fides-style). The other is enclave-based, following SGX-SE2's in-enclave Bloom filter (Vo et al.).
The third part is the private category map. Searching for category $c$ issues tokens for its micro-cluster set $S(c)$. To limit leakage, each search is padded to a fixed number $m$ of tokens using dummy micro-clusters. A random subset of each category's real micro-clusters is optionally re-randomized each session, by re-keying the empty future counters, so that the co-search pattern carries less information about the taxonomy.
The analysis has two strands. On the security side, we write down the leakage function, which is standard forward and backward private leakage plus the multiset of padded token sets per search. We then measure what that leakage enables, using an honest-but-curious server that tries to recover the category partition from token co-occurrence across searches. On the learning side, the central variable is micro-cluster granularity. Finer groups are purer, so the accuracy loss from never reassigning records shrinks. They also mean more tokens per search, higher latency, more enclave state, and a richer co-search pattern. The deliverable is this tradeoff curve, plus the point at which accuracy matches unrestricted discovery.
Baselines
The naive reference point is plaintext FAC with no encryption at all. It sets the accuracy ceiling for the frozen-backbone family. On CUB-200 over four sessions, FAC reports 66.2% Last accuracy (81.2% Old, 59.6% New). On iNatIGCD, the strongest reported discovery result is 28.4% final discovery accuracy for the soft nearest-neighbour plus density-peak method of Zhao et al., against 27.9% for SimGCD+iCaRL. We rerun both on the same frozen DINO ViT with the same session splits and the same cluster-count estimation budget. Our method beats this reference if its Last accuracy stays within one point of plaintext FAC at a granularity whose search latency is practical.
The strongest competitor for the encrypted problem is delete-and-reinsert. It uses discovered category IDs directly as keywords in a forward and backward private scheme. On every merge, split or reassignment, it deletes the moved records from their old keyword and re-inserts them under the new one. We run it twice, once with Janus/Fides and once with SGX-SE2 (Vo et al.), each on identical discovery outputs, so that the only difference is how taxonomy edits are applied. We will not quote a reported figure for this pipeline: no reported result was found on Lacuna for any encrypted search scheme running over discovered categories. The cryptographic components themselves have reported numbers. SGX-SE2 searches 2x faster than Bunker-B with 25% of documents deleted, and Diana is up to 10x faster than Σοφος. To count as beating this baseline, our method must achieve lower server-visible updates per session and lower search latency, with strictly less leaked information about category sizes, at matched accuracy.
The ablation that isolates the key ingredient is the class-level alias map. It is our design with granularity set to one micro-cluster per discovered category, so merges become alias unions and no over-clustering happens. This handles merges without re-encryption, but must fall back to delete-and-reinsert on splits and reassignments. The gap between it and the full design measures what fine granularity buys.
Why not just…?
Why not just use discovered class IDs as keywords and re-encrypt on change? This is the delete-and-reinsert baseline. It is a real option if taxonomies rarely change. However, FAC-style merging and PromptCCD-U splitting edit the taxonomy every session. Each edit then costs work proportional to the number of records moved. It also reveals to the server, through visible update counts, how large the merged or split categories are. With Janus, deletions per keyword quickly exceed the few-hundred practical limit reported by Bost et al.. We will measure server-visible updates per session and Janus decryption time directly. If the taxonomy turns out to stabilize after the first session or two, this alternative wins, and we will report that.
Why not just put the whole category index in an SGX enclave? This is the strongest threat. If the enclave holds the category map and deletion filter, the server sees only enclave-mediated accesses. However, Vo et al. show that naive in-enclave state (SGX-SE1) hits paging cliffs at the 96MB enclave memory limit. Even SGX-SE2 needed a compact Bloom filter, 34MB for 11.8 million pairs. Re-labeling records inside the enclave still means rewriting per-record state on every merge. Our micro-cluster map fits easily in enclave memory precisely because it never stores per-record labels. The experiment therefore runs both designs inside the enclave and compares memory footprint and latency as the number of records grows. If enclave re-labeling stays under the memory limit at iNatIGCD scale, our software-only variant is the remaining contribution, and we will say so.
Why not just rely on feature summaries for privacy, as in ACIL or FRoST? ACIL stores feature autocorrelation matrices, and FRoST stores Gaussian class prototypes. Both argue that raw images cannot be reconstructed from these summaries. That protects training data from the model's owner, but it does nothing about a cloud host that stores records and answers searches. Neither method defines leakage. Neither prevents linking new records to past searches. ACIL additionally requires labels at every phase. This alternative targets a different threat, so it is not a competitor for the encrypted-search question.
Proposed Experiments
We evaluate on CUB-200 (4 sessions) and Tiny-ImageNet (10 sessions) using FAC's protocol. We add iNatIGCD as the stress test, because its geographic domain shift is where frozen features and permanent micro-cluster assignments are most likely to create impure groups. CIFAR-100 serves as a sanity check against the reported PromptCCD (64.17% continual accuracy) and FRoST (59.2% All accuracy) numbers. Learning metrics are Last/Old/New accuracy, final discovery accuracy, and forgetting. Systems metrics are search latency, tokens per search, server-visible updates per session, client or enclave state, and Janus decryption time per keyword. For leakage, we measure how accurately a server-side attacker recovers the category partition, scored by adjusted Rand index, from padded token co-occurrence over a realistic stream of searches.
The decisive checks are three.
First, we sweep micro-clusters per true class from 1 to roughly 20 and plot accuracy loss against plaintext FAC alongside latency and attacker recovery. The idea succeeds if some setting reaches within one point of plaintext accuracy at a modest token count. It fails if purity on iNatIGCD requires so many micro-clusters that padded searches become impractical.
Second, we compare server-visible updates per session against delete-and-reinsert. We expect a gap that grows with session count, because our method incurs no server updates for taxonomy edits.
Third, we test whether padding plus per-session re-keying drives partition recovery close to chance. If it does not, taxonomy leakage must be stated as an explicit, measured term in the scheme's security claim rather than hidden.
References
- Freeze and Cluster: A simple baseline for Rehearsal-Free Continual Category Discovery
- PromptCCD: Learning Gaussian Mixture Prompt Pool for Continual Category Discovery
- Adaptive Discovering and Merging for Incremental Novel Class Discovery
- Forward and Backward Private Searchable Encryption from Constrained Cryptographic Primitives
- Incremental Generalized Category Discovery
- RSPP: A reliable, searchable and privacy-preserving e-healthcare system for cloud-assisted body area networks
- Accelerating Forward and Backward Private Searchable Encryption Using Trusted Execution
- ACIL: Analytic Class-Incremental Learning with Absolute Memorization and Privacy Protection
- Class-Incremental Novel Class Discovery