Label-Side Share Expansion in Private Segmentation Training

Training a segmentation model on pooled private images, such as scans from several hospitals, requires dense masks: one class label for every pixel. The usual cryptographic route for this kind of pooling is secure multi-party computation (MPC), in which two non-colluding servers each hold a random-looking "share" of every data point and train on the shares without seeing the data. Standard MPC stores each value as a 64-bit number per share, and the loss function usually needs labels in one-hot form. A pixel whose true content is $\log_2 K$ bits (for $K$ classes) therefore becomes $2 \times 64 \times K$ bits of shares. That is roughly 7,000× for Cityscapes' 19 classes and roughly 2,700× for ADE20K's 150. Computing on those shares also consumes per-pixel "correlated randomness", precomputed random values that make secure multiplications and comparisons cheap, and normally these are shipped over the network. Secret image sharing calls this bloat pixel expansion and treats it as the main obstacle to practical visual cryptography (The Review of Secret Image Sharing). In dense-label MPC the same problem shows up on the label side.

This proposal makes two claims. First, once the image backbone is a public model, label-side expansion rather than image-side computation dominates the cost of private segmentation training. A public backbone can come from formula-driven synthetic data, meaning procedurally generated images with exact masks and no privacy concerns. Second, the expansion can be cut by one to two orders of magnitude in two ways: labels are held in small boolean shares, and the per-pixel randomness needed to turn them into arithmetic losses is generated locally from short seeds by a pseudorandom correlation function (PCF), a primitive that stretches a tiny shared key into an unbounded stream of correlated randomness with no further communication.

Core Claim and Why the Obvious Idea Is Not It

The obvious combination of these three topics would use PCFs to generate secret-shared synthetic images and labels without interaction. On inspection that idea is empty. Formula-driven data such as SegRCDB's radial contours (SegRCDB) contain nothing private, so publishing the generator seed already gives every party the data for free. No cryptography is needed, and a reviewer would say so immediately.

Synthetic labels matter here for a different reason: they change where the privacy cost sits. SegRCDB shows that a backbone pre-trained only on formula images with grayscale, heavily occluded shapes transfers competitively. Its reported results are 43.85 mIoU (mean intersection-over-union) on ADE20K against 43.39 for COCO-Stuff pre-training, and 73.06 on Cityscapes against 71.00 for GTA5. Such a backbone is public, so each data owner can run it on its own images in plaintext and secret-share only low-resolution features, at 1/8 of full resolution. The labels stay full resolution and must be shared. The cryptographic budget then moves toward the label side, and at 1/8 feature stride label shares can outnumber feature shares in bits. The research question is how cheaply a secret-shared dense label map can be stored and consumed in secure training. That question is the pixel-expansion problem of secret image sharing, transplanted into MPC.

Research Program

The setting has several data owners, each with private images and full masks, and two non-colluding servers. Together they fine-tune a segmentation head on top of a frozen public backbone. Owners compute features locally and share them. Masks are shared in a label-aware encoding. We then measure and reduce the expansion ratio

$$ E = \frac{B_{\text{shares}} + B_{\text{prep}}}{H \cdot W \cdot \lceil \log_2 K \rceil}, $$

where $B_{\text{shares}}$ is the total number of bits of label shares stored or sent per image, $B_{\text{prep}}$ is the number of bits of label-related correlated randomness communicated per training pass, $H \times W$ is the mask resolution, and $K$ is the number of classes.

The work has three technical components, and each builds on a specific prior line.

The first is seed-compressed label shares. One server's share is a pseudorandom function (PRF) key, a short secret from which that server regenerates its entire share, so only the other server's share is full length. This is the Diffie–Hellman seed agreement used by GuardHFL for masks in federated classification. It is also the move by which Evolving Secret Sharing Made Short and Evolving secret sharing revisited beat information-theoretic share-size bounds under computational security. We reuse the technique unchanged. It is a baseline ingredient, not the contribution, and on its own it only halves storage.

The second is boolean-domain labels with silently generated conversion randomness. Each pixel's label is stored as $\lceil \log_2 K \rceil$ bits of boolean share rather than $K$ arithmetic words. The cross-entropy loss needs the one-hot label to multiply the arithmetic logits. That multiplication consumes one oblivious-transfer-style correlation per pixel per label bit (oblivious transfer is a two-party primitive in which one side learns one of two values and the other learns nothing). We generate these correlations with a PCF instead of a dealer or an interactive offline phase. The public-key silent OT and VOLE constructions of The Rise of Paillier remove the trusted dealer at the cost of heavy local algebra, and a PRF-based two-server variant in the style of Chameleon serves as the light option. Prior PCF work targets signatures (Two-Round Stateless Deterministic Two-Party Schnorr Signatures From PCFs) and generic triples. It does not target a workload where the number of correlations scales with image area, which is where silent generation pays off most.

The third is packing many pixels per ring element. Label bits live naturally in small rings. The degree-$D$ reverse multiplication-friendly embeddings of Escudero et al. pack several small-ring values into one extension-ring element for non-interactive correlation generation, with an extension-to-packed ratio of about 4.92 at $D=2$. We test whether packing label pixels this way further reduces local generation cost. Two caveats constrain the design. That construction is proven only against honest-but-curious servers. Its seed storage also grows with the number of parties through covering designs, so we restrict it to the two-server case.

The synthetic labels do two jobs in the program. SegRCDB-style generation supplies the public backbone. The same generator also supplies a controllable test workload, in which we vary instance count (SegRCDB's best setting is about 32 per image), boundary complexity, and resolution. This lets us check whether the measured expansion depends only on resolution and $K$, as the encoding predicts, or also on label structure.

Proposed Experiments

We fine-tune a lightweight decoder head securely on Cityscapes (19 classes) and ADE20K (150 classes), with Pascal VOC as a smaller sanity check. The backbone is pre-trained on public data and frozen, with two options: a SegRCDB-pretrained backbone and a COCO-Stuff-pretrained backbone. We report three kinds of numbers. Cost is the expansion ratio $E$, gigabytes communicated per epoch, and wall-clock time per epoch over a simulated 1 Gbps LAN and a 100 Mbps WAN. Accuracy is mIoU plus a boundary F-score. Local cost is PCF evaluation time per million pixels.

Correctness is checked by requiring that secure fine-tuning match plaintext fine-tuning of the same head to within 0.5 mIoU at equal steps. A larger gap would indicate fixed-point truncation error rather than an encoding effect.

Baselines

The naive reference point is textbook two-party arithmetic sharing. Masks are one-hot encoded as 64-bit words, both servers store full shares, and a trusted dealer streams all correlated randomness. This fixes the uncompressed $E$ at each resolution. It runs the same head, data, fixed-point format, and optimizer schedule as every other arm, and every arm must reach the same plaintext-matched mIoU.

The strongest existing competitor is PRF-seed masking in the GuardHFL style, which removes dealer traffic for linear masks by local seed expansion. On classification, GuardHFL reports a 4.4× to 75.6× runtime speedup over CrypTFlow2 and Cheetah, and a 70× reduction in ReLU communication relative to CaPC. We found no reported result on Lacuna for secure segmentation training communication or for label-side expansion. We will therefore implement GuardHFL-style seed masking on the same arithmetic one-hot labels, give it the same engineering effort as our method, and treat it as the bar. Beating it means at least a 10× lower $E$ on Cityscapes at full resolution, with mIoU within 0.5 of it and no more than a 2× increase in per-epoch wall-clock time in the LAN setting.

Accuracy reference points come from SegRCDB's reported plaintext results: 43.85 mIoU on ADE20K and 73.06 on Cityscapes, with COCO-Stuff pre-training at 43.39 on ADE20K. Those figures use full fine-tuning, while our setting uses a frozen backbone with a trained head. We will therefore rerun a plaintext frozen-backbone head as the actual accuracy ceiling rather than compare against the published numbers directly.

Three ablations isolate each ingredient. The first uses boolean labels with dealer-supplied conversion randomness, which separates the encoding gain from the PCF gain. The second uses arithmetic labels with PCF randomness, which separates the PCF gain from the encoding gain. The third toggles packing on and off, which isolates the embedding.

Why not just…?

Why not just downsample the masks to feature resolution and skip the problem? This is the most serious threat. At stride 8, downsampling cuts label pixels 64× with no cryptography at all. Boundaries degrade, though, and the degradation is expected to hurt most for thin classes such as Cityscapes poles and for high-instance-count scenes. The experiment compares boundary F-score and mIoU at matched communicated bytes across four arms: downsampled labels at strides 2, 4, and 8, and full-resolution labels under our encoding. If downsampling to stride 4 matches our full-resolution accuracy at equal bytes, the label encoding is not worth building. In that case we would report the negative result and keep only the silent-randomness component.

Why not just use a trusted dealer, as Chameleon does? Chameleon already distributes short seeds from a semi-trusted third party, and that approach is cheap. If a dealer is acceptable, the PRF variant of our method is essentially that approach. The public-key PCF of The Rise of Paillier matters only when no third party is trusted. We report both variants so that readers can see the price of removing the dealer, measured as local computation per million pixels. We do not claim a free win.

Why not just use federated averaging and never share labels at all? Federated training sends model updates rather than data and is far cheaper. It protects a different thing, though: updates leak information about the training data, and each client's local head is trained in the clear. We have no number in the file for federated segmentation to compare against. We therefore frame the proposal as serving deployments that require data-level secrecy, and we include plaintext federated head training only as an accuracy reference. Its cost is not comparable under the MPC threat model.

Why not just seed-share the labels and stop? Seed-sharing alone, with one party holding a key and the other holding a full share, leaves one full-width arithmetic share per pixel per class. The per-pixel conversion randomness remains as well. At most it halves $E$. Ablation arm two shows how much of the remaining gap the encoding and silent generation close.

Decisive Checks

The first check tests whether label-side cost matters at all. It measures the fraction of total secure-training communication attributable to labels under the naive baseline with a public backbone at feature stride 8. If that fraction is below roughly 30%, the premise fails and the program stops.

The second check is the matched-bytes comparison against downsampled labels on Cityscapes boundary F-score, which settles whether full-resolution private labels are worth their cost.

The third check tests the encoding's prediction that $E$ depends only on resolution and $K$. It varies instance count and occlusion on SegRCDB-generated masks while holding resolution fixed. If the prediction holds, measured $E$ should stay flat across those variations.