Shuffling is Not Enough: Breaking Permutation-Based Model Confidentiality in Hybrid FHE Inference

1 Introduction

• Hybrid FHE limits computation cost by evaluating linear layers homomorphically and letting the client decrypt and apply nonlinearities, but exposes intermediate outputs that can reveal weights.Permutation-based defenses try to address this exposure by shuffling outputs and treating decryption noise as local randomization.Source: §1 · p. 1
• Correct decryption bounds additive noise below γ/2, so rounding removes response-side randomness and leaves permutation as only a relabeling of the layer output.The attack applies to a broad class of schemes with chosen inputs and noisy, permuted responses on a known quantization lattice.Source: §1 · pp. 1–2
• For a d-input linear layer, d + 1 admissible queries recover a permutation-invariant summary exactly, enabling perfect distinction between models with different sorted spectrum multisets.In Safhire’s first round, the attack recovers the ordered family; its arbitrary chosen-input threat model makes the queries admissible.Source: §1 · p. 2
• Input DP compares neighboring inputs under a fixed model, whereas model confidentiality compares models under fixed queries; correctness-bounded noise also makes shuffle amplification’s local-DP premise unattainable.When admissible inputs produce outputs at least one lattice step apart in a coordinate, their noise-bounded supports are disjoint.Source: §1 · p. 2
• 5,712 direct queries recover all 21 linear layers of a Safhire-style ResNet-20 with zero error; exact per-layer recovery also holds on eight ImageNet-scale CNNs and ViT-B/16.The reported leakage supports fingerprinting, lineage attribution, and improved logit-based extraction; increasing noise enough to suppress the attack leaves no viable privacy/utility operating point.Source: §1 · p. 2

1.1 Related Work

• Classical extraction attacks typically need many queries because nonlinearities obscure linear layers, whereas this attack directly exposes sorted linear-layer snapshots.Carlini et al. use 218.5–221.5 queries on 4K–100K-parameter MLPs; the paper reports 5,712 queries for a 0.27M-parameter ResNet-20.Source: §1.1 · p. 2

2.1 Hybrid FHE Inference via Safhire

• Safhire’s plaintexts lie on a lattice with spacing γ = 1/p, and decryption is correct when noise remains below γ/2.This condition means decoded layer outputs are perturbed by less than half a known lattice step.Source: §2.1 · p. 3
• Hybrid FHE processes one linear layer per round: the server evaluates it homomorphically and permutes outputs, while the client decrypts, applies ReLU, and re-encrypts.The final layer is unshuffled for argmax access, and the client may submit arbitrary inputs without plaintext validation or well-formedness proofs.Source: §2.1 · p. 3

2.2 Shuffle Model of Differential Privacy

• Shuffle-model DP amplifies privacy when local randomizers satisfy local DP before a trusted shuffler permutes their messages.Permutation-based defenses treat FHE decryption noise as local randomization and the output permutation as the shuffler; the paper examines whether correctness-bounded noise meets that premise.Source: §2.2 · pp. 3–4

3.1 Permutation-Based Protection Schemes

• Definition 1 models a client that can issue chosen queries and observe permuted, noisy linear-layer responses; schemes with well-formedness proofs fall outside its scope.The definition is motivated by hybrid FHE but is not specific to FHE.Source: §3.1 · pp. 4–5
• With γ ≥ 2∆, d + 1 chosen queries exactly recover sort(b) and the sorted-spectrum multiset under bounded noise; this is query-tight when bias must also be recovered.In the first Safhire round, where the hidden input permutation is absent, the recovered spectra are ordered by queried column.Source: §3.1 · p. 5

3.2 Input DP and Model Confidentiality Are Orthogonal

• Input DP does not prevent perfect model distinguishability: d chosen queries identify which challenge model produced responses when their sorted-spectrum multisets differ.Input DP compares neighboring inputs under a fixed model, whereas model confidentiality compares different models under fixed queries.Source: §3.2 · p. 6

3.3 The Shuffle DP Premise Cannot Hold

• When neighboring inputs differ by at least one lattice step in a coordinate, correctness-bounded noise gives disjoint supports and forces δ0 ≥ 1, voiding shuffle amplification.In Safhire, arbitrary client inputs make the basis queries admissible, so changing shuffle size cannot restore the local-DP premise.Source: §3.3 · pp. 6–7

3.4 Noise/Utility Tradeoff

• Theorem 2 certifies attack success below a fingerprint-separation threshold, not safety above it; its 2.7(γ/2) bound is two to three orders of magnitude below the empirical transition.Increasing noise to suppress the attack trades decryption accuracy for defense.Source: §3.4 · pp. 7–8

4 Chosen-Input Attack

• Basis vectors are admissible chosen inputs in Safhire, and each round's basis queries probe the layer's columns despite the preceding input permutation.The input permutation remains fixed within a session, so the d queries collectively probe every column exactly once.Source: §4.1 · p. 8

4.1 Multi-Round Layers

• Within a session, d basis queries probe every column once; with independently resampled permutations, recovery instead takes O(d log d) queries with probability at least 1 − e^-c.On trained ResNet-20, no duplicate spectra occurred, and the widest layer's bound was approximately 5,400 queries for c=3.Source: §4.1 · pp. 8–9
• The recovered summary includes affine column norms and empirical column-value distributions, but generally cannot disentangle bias from weights.For bias-free layers, it gives exact weight multisets, column norms, and the Frobenius norm.Source: §4.1 · p. 9
• Recovered spectra support fingerprinting and lineage detection; suppressing those attacks requires noise at scales where inference utility collapses.The authors characterize the shuffle-DP guarantee as vacuous because its argument is formulated in the wrong direction and its local-DP premise fails under the correctness bound.Source: §4.1 · p. 9

4.2 Experimental Validation

• 5,712 direct queries suffice for the ResNet-20 evaluation, which covers 21 bias-free convolutional layers after batch-normalization folding.The query budget is the sum of d_l + 1 queries across the 21 layers.Source: §4.2 · p. 9
• 0 max recovery error across 21 ResNet-20 TFHE layers in both permutation regimes, eight ImageNet CNNs at three precisions, and 37 ViT-B/16 linear layers at p=256.The ResNet-20 transcript used 5,712 queries per regime; the ImageNet CNN results are from per-layer simulation.Source: §4.2 · p. 9, Table 1 · p. 10, Table 2 · p. 10

5 Practical Impact of Sorted Spectrum Leakage

• Permutation-invariant leakage includes column norms, per-column empirical distributions, and weight-value histograms, supporting fingerprinting, lineage detection, and extraction.Suppressing these attacks requires noise at a scale that materially degrades inference utility.Source: §5 · p. 10

5.1 Attribution: Fingerprinting and Lineage

• Sorted conv1 column-norm fingerprints perfectly separate all 190 ResNet-20 model pairs, and the round-then-sort adversary achieves Advmc = 1 using d basis queries.The fingerprint is invariant to column permutations, so multiset-level recovery suffices.Source: §5.1 · p. 10
• Separation ratios 26.7, 6.0, and 1.59 yield 15/15 correct lineage attributions and zero false positives; ImageNet shows an approximate 800:1 lineage-to-non-lineage distance ratio.The ImageNet comparison uses a fine-tuned ResNet-50 V1 child and a 25.5-million-parameter backbone.Source: §5.1 · p. 11

5.2 Distillation Ablation

• Adding recovered spectral priors raises student accuracy by up to 3.1 percentage points over the logit-only baseline, with Col-norms capturing most of the gain at large query budgets.Source: §5.2 · p. 11

5.3 The Privacy/Utility Dilemma

• Neither plotted model enters the attack-broken/utility-intact band; fingerprinting survives 100× noise but breaks down at noise levels of at least 1,000×.At 1,000× clipped-Gaussian noise, per-layer accuracy is 59.0% on ResNet-20 and 48.9% on ResNet-56.Source: §5.3 · pp. 11–12, Figure 1 · p. 12
• Across six tested bounded noise distributions, none reverses the attack/utility ordering; smoother noise can delay utility collapse by at most a constant factor.Source: §5.3 · p. 12
• No per-layer noise scale, architecture, or tested bounded distribution defeats the attack while preserving usable accuracy; averaging k repeats lowers recovery error by 1/k but raises query cost quadratically.At 1,000× noise, k = 5 lowers mean error from 0.92 to 0.38.Source: §5.3 · p. 12

6 Discussion

• The recovery theorem requires visible shuffled noisy linear outputs on a known quantization lattice and chosen-input queries; several related schemes violate one or more of these conditions.Safhire satisfies all three hypotheses, while STIP and Centaur, Fission, and PermLLM fall outside the stated scope for different reasons.Source: §6 · p. 12
• Secret linear transforms, function secret sharing, and fully server-side FHE are described as escape routes, with server-side FHE withholding intermediate decryptions at a bandwidth cost.GAZELLE, DELPHI, and CrypTFlow2 instantiate variants of the function-secret-sharing route.Source: §6 · p. 13
• Fresh per-query permutations still leave maximum recovery error at zero across all 21 layers, so refreshing permutations does not strengthen the scheme.Source: §6 · p. 13

A CIFAR-10 / ResNet-20 Experimental Details

• The 20 ResNet-20 checkpoints use SGD for 10 epochs with seeds 0–19 and yield mean test accuracy of 82.8%.Training uses learning rate 0.1, momentum 0.9, weight decay 10^-4, batch size 128, and MultiStepLR milestones at epochs 5 and 8.Source: A CIFAR-10 / ResNet-20 Experimental… · p. 14
• The recovered object is the folded affine pair (W′, b′) observed by the client; residual branches are probed separately.Batch normalization is folded into the preceding convolution using the deployment transform.Source: A CIFAR-10 / ResNet-20 Experimental… · p. 14

B Tightness of the Correctness Bound

• If Δ > γ/2, there exists noise with norm below Δ under which no deterministic lattice-valued algorithm recovers sort(W[:,i] + b) correctly.Source: B Tightness of the Correctness Bound · p. 14
• The proof chooses η* between γ/2 and min(γ, Δ), yielding the same observation from two distinct lattice-valued true values.Source: B Tightness of the Correctness Bound · p. 15
• Because sorting is deterministic, ambiguity between those true values carries over to the sorted spectrum, forcing any deterministic algorithm to err on at least one instance.Source: B Tightness of the Correctness Bound · pp. 14–15

• At m = 1,000, the deterministic envelope yields 10.0% accuracy for both ResNet-20 and ResNet-56, and no tested distribution reverses the damage ordering.Under Gaussian noise, accuracy is 59.0% for ResNet-20 and 48.9% for ResNet-56 at m = 1,000.Source: C Additional Experimental Validation · p. 15
• ImageNet-scale tests use torchvision IMAGENET1K V1 weights across eight CNNs and ViT-B/16; the ResNet-50 curve uses a fixed 500-image Imagenette-val subset.The subset contains 50 images per class, with random.seed(0); evaluation uses top-1 against real ImageNet-1K labels.Source: C Additional Experimental Validation · p. 15
• On a 97.7%-accurate MNIST MLP, round-then-sort exactly recovers each column’s sorted weight-plus-bias multiset in both layers.The experiment supports the bias case of Theorem 1; the bias cannot be separated from the recovered multiset.Source: C Additional Experimental Validation · p. 15

• The four variants range from logits-only Baseline to Full, which adds per-layer weight-value remapping to column norms.First uses conv1 sorted weights; Col-norms uses column norms across all 21 convolutional layers.Source: D Distillation Ablation · p. 15
• On ResNet-20, Full is strictly best at q ≤ 2,000; at q = 5,000, Col-norms scores 74.66 ± 0.50 versus Full’s 74.12 ± 0.97, while Col-norms matches or exceeds Full on ResNet-56 at both budgets.Source: D Distillation Ablation · p. 15
• At q = 5,000, the Scrambled control scores 74.02 ± 1.10, within one standard deviation of Col-norms, indicating the gain is largely structural.Scrambled substitutes column norms from an independently trained model to isolate structural from teacher-specific gains.Source: D Distillation Ablation · p. 15