FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Yuhan Ma 1 2 Yong Li 1 Stefan Schmid 2
arXiv:2606.09551v1 [cs.CR] 8 Jun 2026
Abstract
but the input is not: private prompts, confidential embeddings, medical notes, and proprietary features (Mohassel & Zhang, 2017). Two-server secure inference protects these inputs by having the client secret-share (Shamir, 1979) its input between non-colluding servers that run MPC (Rathee et al., 2020; Gupta et al., 2024; Kei & Chow, 2025).
Two-server secure inference allows a client to query a hosted large language model (LLM) without revealing prompts or embeddings. Recent GPU systems based on function secret sharing (FSS) make linear layers efficient, but fixed-point nonlinearities and helper operations remain a bottleneck because each operator is typically implemented as a bespoke protocol with its own comparisons, wrap-around corrections, and preprocessing material. We present FuseFSS, a compiler that replaces per-operator protocol design with a single compilation pipeline. For each scalar fixedpoint operator, a compact specification lists its interval partition, low-degree arithmetic pieces, and required predicate bits. The compiler emits two batched FSS evaluations on the public masked value: one packed comparison that returns all predicate bits, and one vector interval lookup that returns the active coefficients and constants. Compared to the current state-of-the-art FSS-based GPU secure inference, FuseFSS preserves accuracy while achieving a 1.24×–1.50× end-to-end speedup and reducing online communication by 9%–16% on BERT and GPT-style models; preprocessing is also lighter, with 14%–23% lower key-generation time and 20%–24% smaller keys.
We study secure transformer inference in the preprocessing model. An offline phase produces input-independent correlated randomness (e.g., Beaver triples (Beaver, 1991)) and FSS keys, while the online phase evaluates the model on secret shares with low latency (Boyle et al., 2015). Recent GPU implementations show this approach can scale to transformer models (Gupta et al., 2024; Jawalkar et al., 2024; Kei & Chow, 2025). What Remains Hard. In GPU-accelerated secure inference, linear layers can be made fast. The dominant remaining costs come from elementwise nonlinearities and rescaling in fixed-point arithmetic over R = Z2n (Keller, 2020; Wagh, 2022). This fixed-point view is standard in MPC because ring arithmetic is cheap, while real-valued nonlinearities must be approximated and rescaled. These operators require comparisons and piece selection under modulo-2n wrap-around. In the masked-wire paradigm used by Sigma and related FSS-based systems (Gupta et al., 2024; Kei & Chow, 2025), parties reveal a public masked value x̂ = x + rin mod 2n and evaluate predicates on x̂. Predicates must be rewritten under masking and require mask-derived carry and wrap information that must remain secret-shared. Today, high performance relies on bespoke per-operator pipelines. This per-operator approach is brittle: it complicates correctness arguments, duplicates keygeneration logic, and makes it difficult to add new operators without introducing subtle wrap-around or signedness bugs.
1. Introduction Large language models are increasingly deployed as hosted services (Brown et al., 2020). Privacy-preserving inference is an active topic, with approaches based on homomorphic encryption and secure multi-party computation (MPC) for models from early CNNs to modern Transformers/LLMs (Gilad-Bachrach et al., 2016; Vaswani et al., 2017; Wu et al., 2024). In many applications, the model is public,
Our Approach. We present FuseFSS, a compiler that replaces per-operator protocol engineering with a uniform, GPU-friendly structure. FuseFSS is guided by a simple observation: across common fixed-point nonlinearities, the data-dependent part is largely the same. Each operator can be viewed as selecting a region using a small set of predicate bits and then applying a low-degree arithmetic form with a small number of constants. FuseFSS captures this pattern with an operator specification, a typed description of an
1 Huawei Heisenberg Research Center, Huawei Technologies Düsseldorf GmbH, Düsseldorf, Germany 2 Technische Universität Berlin, Berlin, Germany. Correspondence to: Yong Li <[email protected]>.
Proceedings of the 43 rd International Conference on Machine Learning, Seoul, South Korea. PMLR 306, 2026. Copyright 2026 by the author(s).
1
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
elementwise fixed-point operator. An operator specification provides an interval partition over canonical representatives of Z2n , a low-degree polynomial per interval for arithmetic outputs, and Boolean helper bits expressed as predicate circuits. Given an operator specification and preprocessing masks, FuseFSS compiles each operator instance into a uniform protocol built from two standard FSS evaluations on the public x̂. A single packed-comparison evaluation returns XOR shares of all predicate bits needed by the operator, and a single vector interval lookup returns additive shares of the active coefficients and constants. The remaining work is a fixed share-based post-processing circuit using standard preprocessing primitives such as Beaver multiplication, Boolean AND, and bit-to-arithmetic conversion.
across operators. Organization. Section 2 reviews related works and contrasts FuseFSS with prior secure inference systems. Section 3 defines the setting, masking, and the backend primitives. Section 4 defines operator specifications and the compilation procedure. Section 5 describes how we package compiled gates for batching and proves correctness and security. Section 6 reports experimental results.
2. Related Work Secure Inference with Secret Sharing. A common starting point for privacy-preserving inference is preprocessingbased MPC over secret shares, where an offline phase produces correlated randomness such as Beaver triples and the online phase minimizes interaction and bandwidth (Beaver, 1991; Mohassel & Zhang, 2017). This approach scales well for large linear layers, but modern transformer inference still stresses it because the model repeatedly invokes fixed-point scalar operators such as rescaling, smooth activations, exponentials, reciprocals, and normalization. These operators introduce comparisons and piece selection under Z2n wrap around, and they tend to dominate both interaction rounds and preprocessing material in end-to-end deployments.
Security and Leakage. FuseFSS follows masked-wire semantics as in prior two-server FSS inference: it uses fresh independent masks per wire and never reuses a mask across different tensor elements. To prevent mask leakage through key size or public instance shape, meaning any size parameters visible from the protocol, such as the number and bit-widths of comparisons and the interval-lookup dimensions, FuseFSS enforces mask-independent shapes. The number and bit-widths of emitted comparisons and the interval-lookup shape depend only on the public operator specification and fixed-point metadata, not on sampled masks.
Private Transformer Inference Systems. A rapidly growing line of work studies end-to-end secure inference for transformer models and LLMs under two-party or dealerbased settings. This direction spans both HE-style polynomial formulations and MPC-style runtimes (Chandran et al., 2019); recent work also explores polynomialized Transformer operators or quantization-aware secure inference pipelines (Gilad-Bachrach et al., 2016; Zimerman et al., 2024; Wu et al., 2024), complementing our systems-focused compiler for fixed-point scalar kernels. IRON (Hao et al., 2022) initiated private inference on transformers and developed specialized protocols for transformer-specific components such as softmax, GELU, and layer normalization. Later systems such as BOLT (Pang et al., 2024) and BumbleBee (Lu et al., 2025) further reduce communication and optimize nonlinear computations. These systems demonstrate that secure transformer inference can be practical, but they also highlight a recurring limitation that motivates our work: high performance typically relies on designing and validating a separate protocol pipeline for each operator, which makes extensibility and correctness under fixed-point wrap-around difficult.
Results. We evaluate FuseFSS against Sigma (Gupta et al., 2024), the state-of-the-art FSS-based secure inference baseline. FuseFSS matches model accuracy and improves end-toend performance by 1.24×–1.50×, while reducing online communication by 9%–16% for BERT and GPT-style models (Devlin et al., 2019; Radford et al., 2019). FuseFSS also reduces preprocessing overhead: key-generation time decreases by 14%–23%, and key size shrinks by 20%–24%. Contributions. • The state-of-the-art FSS-based secure inference performance. FuseFSS improves end-to-end latency and preprocessing cost over state-of-the-art FSS-based GPU secure inference baselines, while matching model accuracy on BERT and GPT. • A practical compiler target for fixed-point nonlinear and rescaling operators. We show that a wide range of fixed-point scalar operators can be expressed by a single operator specification format and executed using the same two FSS calls plus uniform share-based post-processing. • Mask-aware compilation with security. FuseFSS derives mask-correct predicate evaluation from public masked inputs and enforces mask-independent public shapes, enabling a single correctness and semi-honest security proof with explicit shape leakage that applies
GPU Acceleration and Function Secret Sharing. GPU acceleration has become central for reducing latency and for making secure inference competitive at practical model sizes. FSS and its distributed point function (DPF) and distributed comparison function (DCF) instantiations of2
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
3.2. Ring Arithmetic and Fixed Point
fer an attractive trade-off by reducing communication and interaction for structured predicates and lookups (Boyle et al., 2015; 2016; 2019; 2021). Sigma shows that combining FSS with GPU execution enables efficient end-toend transformer inference at scale and develops optimized building blocks for core fixed-point operators and normalization (Gupta et al., 2024). SHAFT further explores transformer specific optimizations, especially for softmax style computation, by improving numerical stability and reducing interaction in key subroutines (Kei & Chow, 2025). Beyond the semi-honest setting, SHARK studies actively secure inference using FSS (Gupta et al., 2025). Despite these advances, existing high-performance GPU systems still require substantial per-operator protocol engineering to handle mask correct predicate rewriting, wrap-around corner cases, and the interaction between bit logic and fixed-point arithmetic. FuseFSS targets this exact gap by compiling a structured operator description into a constant number of standard FSS calls plus uniform share-based post-processing.
We compute over R = Z2n . For x ∈ R, let rep(x) ∈ {0, . . . , 2n − 1} denote its canonical representative. Unsigned comparisons interpret each element by rep(x). Signed values use two’s complement; the most significant bit (MSB) is MSB(x) := I[rep(x)≥2n−1 ] . We write I[E] ∈ {0, 1} for the indicator of a predicate/event E. A real x̃ with f fractional bits is encoded as x = ⌊2f x̃⌉ ∈ R, where ⌊·⌉ denotes rounding to the nearest integer with a fixed tie-breaking rule. Fixed-point rescaling is implemented via explicit truncation and arithmetic right shift (ARS) primitives; for signed values, ARS denotes a two’scomplement right shift with sign extension (Catrina & Saxena, 2010). 3.3. Typed Sharing Domains We use two base types and corresponding sharing domains (Demmler et al., 2015):
3. Setting and Preliminaries
• Arithmetic type An : values in R = Z2n , represented as additive shares JxK = (x0 , x1 ) with x = x0 +x1 mod 2n . • Bit type B: bits in {0, 1}, represented as XOR shares ⟨b⟩ = (b0 , b1 ) with b = b0 ⊕ b1 .
3.1. Threat Model and Preprocessing We consider two-party computation between parties P0 , P1 in the standard preprocessing model, corresponding to the common “two non-colluding servers” setting (Damgård et al., 2012). A client may provide inputs as secret shares to P0 , P1 ; the online protocol is run by P0 , P1 . We assume semi-honest corruption of at most one party. The transformer architecture and model parameters are public unless stated otherwise; the client inputs and intermediate activations are secret. Our contribution concerns scalar nonlinearities and helper operations given arithmetic shares of their inputs, and composes with either public-weight or secret-shared linear layers.
We optionally attach fixed-point metadata to arithmetic wires; this metadata is part of the gate signature and determines which predicates and corrections are required, while cryptographic operations are performed in R. Mixed-Domain Conversions. When a bit gates ring arithmetic, we use a standard preprocessing-based bit-toarithmetic conversion (B2A) that maps an XOR-sharing ⟨b⟩ to additive shares of the embedded ring element b ∈ {0, 1} ⊂ R (Mohassel & Rindal, 2018; Patra et al., 2021). Conversely, when a ring element must be converted to a bit, we use a standard preprocessing-based arithmetic-tobit conversion (A2B). We treat these as black-box secure subprotocols and count their uses in complexity statements.
The protocol has two phases. The offline preprocessing phase produces correlated randomness and FSS keys. The online phase evaluates the model on secret shares. We assume a conceptual dealer for preprocessing and focus on online costs and the size/time of preprocessing material. All preprocessing material is one-time: each gate instance consumes fresh masks/keys/triples per inference execution.
3.4. Standard Preprocessing Subprotocols We use standard preprocessing-based multiplication over R via Beaver triples and standard Boolean-AND correlation for XOR-shared bits (Beaver, 1991). XOR and NOT on XOR shares are local. We treat these subprotocols as black boxes and count their invocations in our complexity statements.
Wire-Level Masking. Following FSS-based systems, we treat each scalar wire (tensor element) as a distinct gate instance. Preprocessing samples an independent uniform input mask rin (and an independent output mask rout when used) per wire. Mask reuse across different wires is disallowed: if two wires shared the same rin , then the public masked openings would satisfy x̂(1) − x̂(2) = x(1) − x(2) and would leak a relation between secret activations. Our implementation therefore generates masks per wire.
3.5. Masked-Wire Invariant and Conversions For FSS-based nonlinear evaluation, the offline preprocessing samples a uniform mask rin ← R and distributes Jrin K. In the online phase, parties may reveal the public masked value x̂ = x + rin mod 2n . Since rin is uniform and 3
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
independent of x, x̂ is uniform over R and informationtheoretically independent of x. Consequently, any additional leakage about rin (including via key sizes or maskdependent instance shapes) must be avoided; our compiler enforces mask-independent public shapes and keeps all mask-derived bits secret-shared.
specified by: 1. A full partition with integer boundaries 0 = α0 < α1 < · · · < αm = 2n and intervals Ii = [αi , αi+1 ) over canonical representatives. The boundary αm = 2n is a sentinel: the predicate I[x<αm ] is identically 1 and is never emitted as a backend comparison. 2. For each Ii , a vector of degree-≤ d polynomials Pi (x) ∈ R[x]r (evaluated in R), where d is a global (descriptorlevel) degree bound. 3. For each Ii , a vector of Boolean formulas Bi (x) ∈ {0, 1}ℓ built from primitive predicates with integer constant parameters: Cβ (x) = I[x<β] and Dγ,f (x) = I[(x mod 2f )<γ] . Here β ∈ {0, . . . , 2n }, f ∈ {1, . . . , n}, and γ ∈ {0, . . . , 2f }. MSB(·) tests, and connectives ¬, ∧, ∨, ⊕ (with semantics in Z2 ). Sentinel cases are constants: C0 (x) ≡ 0, C2n (x) ≡ 1, and similarly D0,f (x) ≡ 0, D2f ,f (x) ≡ 1.
We use the standard masked opening routine, shown in Protocol 1 and 2 in Appendix C: to reveal x̂ = x + rin , each party locally adds its mask share and the parties reconstruct the sum; given public x̂, parties locally recover additive shares of x = x̂ − rin by subtracting their mask shares. 3.6. Backend Interface: Two Standard FSS Primitives Our compiler relies on two standard FSS primitive families that are already available in modern DPF/DCF-style systems (Gilboa & Ishai, 2014; Boyle et al., 2016; 2021). For each primitive family, preprocessing generates one key per party, and online evaluation is local on a public input. We allow explicit leakage of public shapes, such as the number and bit-widths of emitted comparisons and the payload dimension of a lookup, but the compiler enforces that these shapes do not depend on sampled masks.
The induced function is F (x) = (Pi (x), Bi (x)) for the unique i with x ∈ Ii . 4.2. Scope: Operator Specifications and Compatible Scalar Gates Scalar Gates vs. Vector Blocks. Operator specifications (Definition 4.1) are an intermediate representation (IR) for scalar (Demmler et al., 2021), elementwise fixed-point operators over R = Z2n . A scalar gate consumes one masked wire x̂ and outputs a constant-size tuple of arithmetic values in R together with Boolean helper bits. This captures the elementwise nonlinearities and fixed-point helpers dominating secure transformer inference (activations, nExp, reciprocal/rsqrt, and rescaling such as truncation and ARS).
Public Views. For any k ≤ n and constant c ∈ Z2k , define viewk,c (u) := ((u mod 2k ) + c) mod 2k . Here u mod 2k denotes rep(u) mod 2k , namely the low k bits of the canonical representative. Since the masked wire u = x̂ is public, each party computes such views locally. Packed Comparisons. Given a list of queries (kt , ct , θt ), evaluation returns XOR shares of I[viewk ,c (u)<θt ] for all t. t t This covers full-width comparisons, low-bit predicates, and MSB tests through shifts and thresholds.
In contrast, vector-level operations that mix coordinates, such as reductions max and sum, sorting or top-k, and attention sparsification with data-dependent routing, are not univariate scalar maps and are handled by standard MPC subprotocols at the circuit/directed acyclic graph (DAG) level (Juvekar et al., 2018).
Vector Interval Lookup. Given boundaries 0 = α0 < · · · < αM = 2n and payload vectors vi ∈ Rp , evaluation returns additive shares of the unique vi⋆ such that u ∈ [αi⋆ , αi⋆ +1 ). We use this lookup to fetch all coefficients and per-interval constants for a scalar operator in one call. Appendix I gives a library-agnostic formalization of these two primitives.
Specification-Compatible Scalar Primitives. Not every fixed-point primitive is a polynomial in R (e.g., truncation/ARS involves dropping bits). We therefore separate the operator specification from a fixed post-processing circuit.
4. Operator Specifications and Mask-Aware Compilation
Definition 4.2 (Specification-compatible scalar gate). A ′ ′ typed scalar gate G : An → Arn × Bℓ is specificationcompatible if there exist an operator specification F : An → Arn × Bℓ and a deterministic post-processing circuit Φ such that the following holds for every gate instance (i.e., every preprocessing mask choice). For every rin ∈ R, let x̂ = (x+ rin ) mod 2n be the public masked input, and let κ = κ(rin ) denote any mask-derived secret-shared instance constants required by compilation, for example carry bits that depend
4.1. Operator Specifications Definition 4.1 (Operator specification). Fix n ≥ 1 and let R = Z2n . A typed operator specification has signature F : An → Arn × Bℓ , optionally annotated with fixed-point metadata (fractional bits, signedness) for the arithmetic input/output wires. It is 4
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
only on rin and descriptor constants. Then for all x ∈ R, G(x) = Φ F (x), κ, x, x̂, pub ,
A Useful Corollary: Masked Interval Indicators Cancel the I[x̂<r] Term. Combining Lemma D.1 with Lemma 4.3, the indicator I[x∈Ii ] can be expressed using only comparisons to shifted boundaries in x̂-space:
where pub denotes any additional public parameters available at evaluation time, such as bit-widths, scaling metadata, and approximation parameters. In evaluation, parties can supply Φ with additive shares JxK of the unmasked input (either the original gate input shares or derived locally from (x̂, Jrin K) via Protocol 2); this does not introduce any additional communication or leakage beyond the masked opening x̂. The circuit Φ may use ring additions, a bounded number of Beaver-triple multiplications, Boolean XOR/NOT/AND on XOR-shares, and mixed-domain conversions (B2A/A2B) when a bit gates arithmetic.
I[x∈Ii ] = I[x̂<(αi+1 +r) mod 2n ] ⊕ I[x̂<(αi +r) mod 2n ] ⊕ wi+1 ⊕ wi . where wt = I[r+αt ≥2n ] are preprocessing-time carry bits (kept secret-shared for t ∈ {1, . . . , m−1}; note w0 = 0 and wm = 1 are public constants since α0 = 0 and αm = 2n ). This reduces the number of primitive masked comparisons needed for piece selection.
Composing Vector Blocks. Transformer blocks are expressed as DAGs that compose: (i) linear operations over R on arithmetic shares (matmul, add, sum reductions), (ii) comparison-based reductions (e.g., max via a comparison tree), and (iii) elementwise specification-compatible gates (e.g., nExp, reciprocal/rsqrt). Appendix G gives concrete decompositions for Softmax and LayerNorm.
MSB and Signed Predicates. MSB(x) can be expressed via an unsigned threshold test (e.g., MSB(x) = ¬I[x<2n−1 ] ), and signed comparisons reduce to unsigned comparisons after a fixed constant shift of the canonical representative. The corresponding masked rewrites follow by applying Lemma 4.3 to the shifted comparisons; see Appendix J.3 for full derivations (including MSB(x + c)).
Helper Bits and Boolean Normalization. Boolean outputs of F are first-class typed results and may feed later computation. To avoid data-dependent control flow, we express interval indicators as I[x∈[αi ,αi+1 )] = I[x<αi+1 ] ⊕ I[x<αi ] and use them to normalize piecewise Boolean outputs into a single global Boolean circuit. Lemmas D.1 and D.2 are deferred to Appendix D.
4.4. Compiling One Operator Gate with Two FSS Calls Gate Instances. An operator specification is type-level and public. A gate instance fixes preprocessing masks and therefore fixes the (secret) instance parameters used by backend primitive instances (shifted thresholds, translated boundaries, payloads) while revealing only their public shapes. Lemma 4.4 (Interval translation under masking). Let I = [α, β) ⊆ [0, 2n ) be an interval over canonical representatives and let x̂ = x + r mod 2n . Then the image of I under x 7→ x̂ is the cyclic interval [α + r, β + r) mod 2n , which is either a standard interval or the union of two standard intervals. Across a full partition, at most one interval wraps around 0 after translation (and none wraps when the wrap point hits a boundary). Hence an m-interval operator specification partition induces at most m + 1 standard intervals in x̂-space.
4.3. Mask-Aware Rewriting Under Public Masking Let x̂ = x + r mod 2n with uniform r sampled in preprocessing. We rewrite predicates on x into Boolean formulas over comparisons on public x̂, with secret mask-derived constants derived from r. All equalities below are over {0, 1} with ⊕ denoting XOR. Any mask-derived wrap/carry bit is kept secret-shared: revealing such a bit would leak information about r and therefore about x given x̂. Lemma 4.3 (Masked rewrite for unsigned comparison). Let N = 2n and interpret R = Z2n by canonical representatives in {0, . . . , N − 1}. Fix an integer threshold β ∈ {0, 1, . . . , N } and a mask r ∈ R. Let x̂ = (x + r) mod N , θ = (r + β) mod N , and let w = I[r+β≥N ] denote the carry bit of the integer addition r + β. Assume preprocessing provides an XOR-sharing ⟨w⟩ (equivalently, w is a secret-shared constant). Then for all x ∈ R,
Compilation Sketch. Given an operator specification and a per-wire mask rin , the compiler (i) translates boundaries into x̂-space and pads the partition to a fixed interval count M , (ii) rewrites all primitive predicates under masking into comparisons on the public x̂ plus secret-shared carry bits, (iii) collects all comparison atoms in a fixed descriptordetermined order to form one packed comparison instance, and (iv) packages all per-interval coefficients/constants into one interval lookup instance. The padding in (i) enforces mask-independent public instance shapes (and therefore mask-independent key lengths), avoiding leakage about rin through shape. Full pseudocode appears in Appendix F (Protocol 3).
I[x<β] = I[x̂<θ] ⊕ I[x̂<r] ⊕ w, where all comparisons are under the canonical order on {0, . . . , N − 1}. Low-bit Predicates. An analogous rewrite holds for I[(x mod 2f )<γ] ; see Lemma E.1 in Appendix E. 5
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Payload Structure. For degree-d and r arithmetic outputs, the coefficient payload includes r(d + 1) ring elements (padding lower-degree polynomials with leading zeros if needed). To support fused post-processing (e.g., truncation/ARS corrections), we allow Πcoeff to additionally return a small number of per-interval constants; the payload length is p = r(d + 1) + paux .
active cost is captured by G∧ Boolean AND gates (on XOR shares) and Gmix mixed-domain uses, plus any use of secret-shared instance constants κ (which require no interaction to consume). All remaining interaction is confined to the standard openings required by Beaver/AND/B2A subprotocols.
Lemma 4.5 (Compiler correctness). Let F : An → Arn ×Bℓ be a well-formed typed operator specification descriptor with partition (αi )m i=0 and per-piece data (Pi , Bi ). Let preprocessing sample a uniform mask rin ∈ R and provide additive shares Jrin K, as well as any mask-derived secret-shared instance constants required by the masked rewrite rules (e.g., carry bits in Lemmas 4.3–E.1). Let (Πpred , Πcoeff ) be the packed comparison and interval lookup instances produced by Protocol 3 for (F, rin ). Then for every x ∈ R and x̂ = x + rin mod 2n , the online evaluation procedure (open x̂, evaluate Πpred and Πcoeff on x̂, derive shares of x locally, evaluate Horner and the normalized Boolean circuit) outputs shares (JyK, ⟨z⟩) that reconstruct to F (x) = (y, z).
Proof sketch. Πpred returns XOR-shares of all masked comparisons required by the rewritten predicate circuit (including those used to form interval indicators). Πcoeff returns additive shares of the active polynomial coefficients (and any per-interval constants) without revealing the active interval. Parties locally derive additive shares of x = x̂ − rin and evaluate the selected polynomials via Horner’s rule using Beaver triples. Finally, they evaluate the normalized Boolean circuit over XOR shares using XOR/NOT locally and AND/B2A when needed, and apply Φ. 4.6. Security in the Semi-Honest Preprocessing Model Leakage. A compiled gate instance induces public shape parameters: the number of comparison queries T (and their bit-width multiset {kt }) in the packed comparison instance, and the interval count M and payload dimension p in the interval lookup instance. We model this as an explicit leakage function Lshape . Depending on the backend instantiation, the public interval lookup shape may be described either by an explicit interval count M (boundary representation) or by a dense table bit-width k (DPF-LUT representation); we subsume such parameters in Lshape . In addition, the online protocol reveals public masked openings (e.g., x̂ = x + rin and optional masked outputs), which are information-theoretically independent of secrets under fresh uniform masks; we include them in the public transcript. All mask-derived constants (e.g., carry bits) remain secretshared and are treated as part of preprocessing material.
Moreover, for any specification-compatible scalar gate G with G(x) = Φ(F (x), κ, x, x̂, pub) (Definition 4.2), the same compiled instances together with the fixed share-based evaluation of Φ reconstruct to G(x). 4.5. Two-Call Evaluation Theorem Theorem 4.6 (Two-call evaluation for specification-compatible scalar gates). Assume a backend implementing the two primitive families in Section 3.6: packed comparison with queries of the form I[viewk,c (u)<θ] and interval lookup for vector payload lookup on u ∈ R. Then any scalar gate instance (and, more generally, any specification-compatible scalar gate in Definition 4.2) can be evaluated from a public masked input x̂ using: 1. At most two non-interactive backend interface evaluations on x̂: one packed comparison evaluation producing XOR-shares of all masked comparison atoms needed by the compiler (possibly at multiple bit-widths k via the public view operator viewk,c ), and one interval lookup evaluation producing additive shares of the active coefficient/constant payload. Either call may be omitted if the compiled instance does not require it. 2. O(r · d) ring multiplications (implemented via Beaver triples) for batched Horner evaluation of r degree-d polynomials on secret shares of x = x̂ − rin (Protocol 2), plus an additional MΦ ring multiplications (via Beaver triples) performed by the fixed post-processing circuit Φ. Here MΦ depends only on the gate type and public parameters (often a small constant, e.g., a constant number of refinement steps). 3. A fixed post-processing circuit Φ whose remaining inter-
Ideal Functionality. Fix a gate type τ with ideal scalar functionality Gτ (x) = Φτ (Fτ (x), κ, x, x̂, pub) (Definition 4.2). The ideal execution for one gate instance samples fresh masks and correlated randomness as in preprocessing, reveals Lshape and the public masked openings, and returns to each party additive/XOR shares of the gate outputs consistent with Gτ (x). Theorem 4.7 (Semi-honest security with leakage (gate level)). Assume: (i) the packed-comparison primitive and the vector interval-lookup primitive satisfy standard singlekey FSS security with explicit shape leakage, as discussed in Section 3.6; and (ii) the preprocessing-based subprotocols used in post-processing, including Beaver multiplication over R, Boolean AND over Z2 , and any invoked B2A conversions, are semi-honest secure. Then for any compiled gate instance, the real-world view of a semi-honest adversary 6
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
the corresponding FSS keys and correlated randomness. The dealer may also publish the public shape parameters of the two FSS instances, which we treat as explicit leakage.
corrupting either party is computationally indistinguishable from the view produced by a PPT simulator given only that party’s input share, its output shares, the explicit shape leakage, and the public masked openings.
5.3. Online Evaluation Proof Sketch. The simulator samples masked openings uniformly (matching the real distribution under fresh masks), uses the backend interface simulator(s) to generate indistinguishable keys and local outputs for the adversary’s party given Lshape , and simulates Beaver/AND/B2A openings using their standard simulators. A full hybrid proof is given in Appendix M.
Given an arithmetic-shared input JxK:
1. Materialize the public masked value x̂ = x + rin by a batched opening (Protocol 1). 2. Evaluate packed comparisons when needed to obtain XOR-shares of all primitive predicate bits required by the compiler. 3. Evaluate interval lookup when needed to obtain additive shares of the active coefficient and constant payload. 4. Locally derive additive shares of x = x̂−rin (Protocol 2) and evaluate the post-processing circuit Φ.
5. Compiled Gate Modules The compilation procedure in Section 4 turns each scalar operator into a small protocol with a fixed structure: open the public masked input x̂ = x + rin mod 2n , evaluate (when needed) one packed-comparison instance and one vector interval-lookup instance on x̂, and then run a shared post-processing circuit on secret shares. For engineering and batching, we package the resulting protocol into a compiled gate module. A compiled gate module is the unit that the transformer runtime invokes repeatedly across layers and tensors.
Optionally, if a consumer requires a masked public output, parties open ŷ = y + rout using fresh output masks. 5.4. Correctness and Security Correctness follows from Lemma 4.5, and semi-honest security with explicit shape leakage follows from Theorem 4.7 by standard composition.
6. Evaluation
5.1. Gate Interface
6.1. Experimental Setup
A gate type is specified by: (i) an operator specification (descriptor) F : An → Arn ×Bℓ , and (ii) a fixed deterministic post-processing circuit ′ ′ Φ : Arn × Bℓ × K × An × Pub → Arn × Bℓ ,
We evaluate FuseFSS in the standard two-server preprocessing model, reporting online latency/communication and preprocessing cost (key-generation time and key size) per inference. All experiments run with 2× RTX PRO 6000 Blackwell Workstation Edition GPUs (one GPU per party), 2× EPYC 9654 CPUs, and CUDA 13.0.
where K is the type of any mask-derived secret-shared instance constants, such as carry bits in masked predicate rewrites, An is the secret-shared unmasked input x, and Pub denotes public values at evaluation time, e.g., x̂ and fixedpoint metadata. A gate instance is one invocation of the gate on one scalar wire, together with its instance constants.
To quantify latency sensitivity, we also report projected online latency under a LAN/WAN model (LAN: 1 GB/s, 0.5 ms; WAN: 400 MB/s, 4 ms).
5.2. Preprocessing
Baselines. We compare against Sigma (Gupta et al., 2024), the state-of-the-art FSS-based secure inference baseline. FuseFSS is implemented as a drop-in replacement for Sigma’s hand-written nonlinear protocols (Ba et al., 2016; Ramachandran et al., 2017), so end-to-end deltas are attributable to our compilation strategy. We cite SHAFT (Kei & Chow, 2025) as an orthogonal reference point for private transformer inference and attempted to run SHAFT on GPT in our environment, but the provided script failed due to a device mismatch. Other systems such as BOLT (Pang et al., 2024) and BumbleBee (Lu et al., 2025) target different protocol families and hardware (CPU 2PC/HE or SPU) and are not directly comparable in our two-server GPU FSS setting; Appendix B.5 reports our best-effort baseline attempts and
For each gate instance, preprocessing provides to each party: • mask shares Jrin K and, when needed, output mask shares Jrout K, • any mask-derived secret-shared instance constants required by compilation, • FSS keys for the packed-comparison and interval-lookup instances emitted by the compiler, and • correlated randomness for post-processing, including Beaver triples for ring multiplications, Boolean AND correlation, and any invoked B2A conversions. A conceptual dealer samples masks, derives the instance constants, runs compilation for the descriptor, and generates 7
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing Table 1. End-to-end two-server inference (sequence length 128, batch size 1). Online time (ms)
Comm (GB)
Keygen (s)
Key size (GB)
Model
Sigma
FuseFSS
↓ (%)
Sigma
FuseFSS
Sigma
FuseFSS
Sigma
FuseFSS
BERT-tiny-128 BERT-base-128 BERT-large-128 GPT-2-128 GPT-Neo-128
63.90 1613.80 4034.50 1423.90 6326.20
42.60 1149.50 2997.90 1072.70 5115.80
33.3 28.8 25.7 24.7 19.1
0.021 1.062 2.833 0.885 4.326
0.018 0.891 2.376 0.777 3.917
0.07 1.32 3.21 1.20 5.42
0.06 1.08 2.48 0.99 4.35
0.350 18.076 48.799 15.346 81.805
0.268 13.678 37.075 11.920 65.729
Table 2. Sequence-length sweep for BERT-base (batch size 1). Seq
Sigma time (ms)
FuseFSS time (ms)
↓ (%)
Sigma comm (GB)
FuseFSS comm (GB)
32 64 128 256 512
642.30 947.40 1613.80 2991.50 7694.70
545.50 696.00 1149.50 2152.40 5324.10
15.1 26.5 28.8 28.0 30.8
0.199 0.441 1.062 2.842 8.553
0.179 0.388 0.891 2.242 6.325
explains their comparability limitations.
Table 3. Seq=128 softmax substep breakdown. The compiled path consists of nExp and reciprocal; the total softmax includes smaller steps not shown.
Metrics. We report: (i) online latency and online communication; (ii) key generation time and key size for one inference execution. Unless explicitly stated, reported numbers correspond to sequence length 128 and batch size 1. Each configuration is run five times; we discard the first as warmup and report the median of the remaining four runs.
Model
Substep
BERT-base BERT-base BERT-base GPT-2 GPT-2 GPT-2
Compiled path Max-reduction Total softmax Compiled path Max-reduction Total softmax
Sigma
FuseFSS
Speedup
223 93 356 132 68 228
49 77 160 28 56 102
4.50 1.20 2.22 4.70 1.20 2.24
6.2. End-to-End Transformer Inference Table 1 reports end-to-end two-server inference costs for BERT/GPT models. Across all tested models, FuseFSS reduces online latency by 19–33% and online communication by 9–16%, while also reducing preprocessing key size by 20–24% and key-generation time by 14–23%. Under the LAN/WAN model above, BERT-base-128 corresponds to 3.99/3.36 s (LAN) and 11.12/9.94 s (WAN) for Sigma/FuseFSS, and BERT-large-128 to 10.18/8.45 s (LAN) and 26.58/23.39 s (WAN).
6.4. Attribution and Scope The end-to-end gains come from the scalar nonlinear/helper path that FuseFSS compiles, not from optimizing every Transformer subprotocol. Table 3 shows that, in softmax, the compiled nExp+reciprocal path accounts for 58–63% of Sigma’s softmax time and is accelerated by 4.5×–4.7×. Once this path is compressed, max-reduction becomes the dominant residual softmax cost; improving vector reductions is therefore complementary to FuseFSS rather than part of the operator-specification IR. The full time breakdown in Appendix B.2 shows the same pattern at the model level: on BERT-base-128, GELU+Softmax+LayerNorm explain 92.7% of the end-to-end latency reduction, and on GPT-2-128 they explain nearly all of it. Appendix B further reports accuracy, GPT-2 scaling up to 512 tokens, LLaMA-family 7B/8B runs, activation microbenchmarks, and baseline notes.
To reconcile gate-level speedups with end-to-end gains, on BERT-base-128 the accelerated nonlinear/helper blocks account for 56% of Sigma’s online time and 54% of its online communication, dropping to 42% and 45% under FuseFSS (Appendix B.2). Appendix B.5 discusses best-effort runs for other private-transformer systems and explains why we keep Sigma as the like-for-like GPU FSS baseline. 6.3. Scaling with Sequence Length For BERT-base, FuseFSS maintains gains as sequence length increases from 32 to 512 (Table 2). For lengths 64– 512, FuseFSS achieves a 1.36×–1.45× speedup, while online communication savings increase with sequence length.
7. Conclusion Fixed-point scalar nonlinearities and rescaling helpers remain a primary bottleneck in two-server secure inference. 8
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
We presented FuseFSS, a compiler that replaces per-operator protocol engineering with a uniform compilation pipeline. FuseFSS represents each elementwise fixed-point operator using a typed operator specification, and compiles each gate instance into the same two-call structure on the public masked wire: one packed comparison for predicate extraction and one vector interval lookup for coefficient and constant retrieval. Compared with Sigma, FuseFSS improves end-to-end online inference performance and reduces preprocessing material while preserving model quality.
Boyle, E., Gilboa, N., and Ishai, Y. Function secret sharing. In Annual international conference on the theory and applications of cryptographic techniques (EUROCRYPT), pp. 337–367. Springer, 2015. Boyle, E., Gilboa, N., and Ishai, Y. Function secret sharing: Improvements and extensions. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security (CCS), pp. 1292–1303, 2016. Boyle, E., Gilboa, N., and Ishai, Y. Secure computation with preprocessing via function secret sharing. In Theory of Cryptography Conference (TCC), pp. 341–371. Springer, 2019.
Discussion. FuseFSS targets the scalar nonlinear and helper kernels that dominate MPC inference costs; vector reductions remain outside the operator-specification IR and must be handled by standard MPC subprotocols and circuit-level composition. Finally, our security analysis focuses on the semi-honest preprocessing model with two noncolluding servers; extending the same approach to stronger adversarial models is an important next step.
Boyle, E., Chandran, N., Gilboa, N., Gupta, D., Ishai, Y., Kumar, N., and Rathee, M. Function secret sharing for mixed-mode and fixed-point secure computation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pp. 871–900. Springer, 2021.
Acknowledgements Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in Neural Information Processing Systems (NeurIPS), 33:1877–1901, 2020.
We thank the anonymous reviewers for their thoughtful feedback.
Impact Statement This work aims to advance privacy-preserving machine learning by reducing the cost and engineering complexity of two-server secure inference for transformer models. Our techniques can support deployment settings where users or organizations require strong confidentiality for prompts, embeddings, and intermediate activations (e.g., healthcare, finance, and enterprise workloads).
Catrina, O. and Saxena, A. Secure computation with fixedpoint numbers. In International Conference on Financial Cryptography and Data Security (FC), pp. 35–50. Springer, 2010. Chandran, N., Gupta, D., Rastogi, A., Sharma, R., and Tripathi, S. EzPC: Programmable and efficient secure twoparty computation for machine learning. In 2019 IEEE European Symposium on Security and Privacy (EuroSP), pp. 496–511. IEEE, 2019.
At the same time, more efficient private inference could make it easier to access powerful models without revealing inputs to a service provider, which may complicate monitoring and abuse prevention that rely on visibility into user queries.
Damgård, I., Pastro, V., Smart, N., and Zakarias, S. Multiparty computation from somewhat homomorphic encryption. In Annual cryptology conference (CRYPTO), pp. 643–662. Springer, 2012.
A deployment can partially mitigate this tension by applying authenticated access control, rate limiting, and output-side auditing at authorized service endpoints where final logits or predictions are intentionally revealed, rather than inspecting private prompts during secure computation.
Demmler, D., Schneider, T., and Zohner, M. ABY - A framework for efficient mixed-protocol secure two-party computation. In Network and Distributed System Security Symposium (NDSS), 2015.
References Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
Demmler, D., Katzenbeisser, S., Schneider, T., Schuster, T., and Weinert, C. Improved circuit compilation for hybrid MPC via compiler intermediate representation. In Proceedings of the 18th International Conference on Security and Cryptography (SECRYPT), pp. 444–451, 2021.
Beaver, D. Efficient multiparty protocols using circuit randomization. In Annual international cryptology conference (CRYPTO), pp. 420–432. Springer, 1991. 9
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), pp. 4171–4186, 2019.
Mohassel, P. and Rindal, P. ABY3: A mixed protocol framework for machine learning. In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security (CCS), pp. 35–52, 2018. Mohassel, P. and Zhang, Y. SecureML: A system for scalable privacy-preserving machine learning. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 19–38. IEEE, 2017.
Gilad-Bachrach, R., Dowlin, N., Laine, K., Lauter, K., Naehrig, M., and Wernsing, J. CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy. In International Conference on Machine Learning (ICML), pp. 201–210. PMLR, 2016.
Pang, Q., Zhu, J., Möllering, H., Zheng, W., and Schneider, T. BOLT: Privacy-preserving, accurate and efficient inference for transformers. In 2024 IEEE Symposium on Security and Privacy (SP), pp. 4753–4771. IEEE, 2024.
Gilboa, N. and Ishai, Y. Distributed point functions and their applications. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pp. 640–658. Springer, 2014.
Patra, A., Schneider, T., Suresh, A., and Yalame, H. ABY2.0: Improved mixed-protocol secure two-party computation. In 30th USENIX Security Symposium (USENIX Security), pp. 2165–2182, 2021.
Gupta, K., Jawalkar, N., Mukherjee, A., Chandran, N., Gupta, D., Panwar, A., and Sharma, R. SIGMA: Secure GPT inference with function secret sharing. Proceedings on Privacy Enhancing Technologies (PoPETs), 2024(4): 61–79, 2024.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language models are unsupervised multitask learners. OpenAI, 2019. URL https://cdn. openai.com/better-language-models/ language_models_are_unsupervised_ multitask_learners.pdf.
Gupta, K., Chandran, N., Gupta, D., Katz, J., and Sharma, R. SHARK: Actively secure inference using function secret sharing. In 2025 IEEE Symposium on Security and Privacy (SP), pp. 2472–2490. IEEE, 2025.
Ramachandran, P., Zoph, B., and Le, Q. V. Searching for activation functions. arXiv preprint arXiv:1710.05941, 2017.
Hao, M., Li, H., Chen, H., Xing, P., Xu, G., and Zhang, T. Iron: Private inference on transformers. Advances in Neural Information Processing Systems (NeurIPS), 35: 15718–15731, 2022.
Rathee, D., Rathee, M., Kumar, N., Chandran, N., Gupta, D., Rastogi, A., and Sharma, R. CrypTFlow2: Practical 2party secure inference. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 325–342, 2020.
Jawalkar, N., Gupta, K., Basu, A., Chandran, N., Gupta, D., and Sharma, R. Orca: FSS-based secure training and inference with GPUs. In 2024 IEEE Symposium on Security and Privacy (SP), pp. 597–616. IEEE, 2024.
Shamir, A. How to share a secret. Communications of the ACM, 22(11):612–613, 1979. doi: 10.1145/359168. 359176.
Juvekar, C., Vaikuntanathan, V., and Chandrakasan, A. GAZELLE: A low latency framework for secure neural network inference. In 27th USENIX Security Symposium (USENIX Security), pp. 1651–1669, 2018.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Kei, A. Y. L. and Chow, S. S. M. SHAFT: Secure, handy, accurate, and fast transformer inference. In Network and Distributed System Security Symposium (NDSS), 2025.
Wagh, S. Pika: Secure computation using function secret sharing over rings. Proceedings on Privacy Enhancing Technologies (PoPETs), 2022(4):351–377, 2022.
Keller, M. MP-SPDZ: A versatile framework for multi-party computation. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS), pp. 1575–1590, 2020.
Wu, H., Fang, W., Zheng, Y., Ma, J., Tan, J., and Wang, L. Ditto: Quantization-aware secure inference of transformers upon MPC. In Proceedings of the 41st International Conference on Machine Learning (ICML), volume 235 of Proceedings of Machine Learning Research, pp. 53346– 53365. PMLR, 2024.
Lu, W.-j., Huang, Z., Gu, Z., Li, J., Liu, J., Hong, C., Ren, K., Wei, T., and Chen, W. BumbleBee: Secure Two-party Inference Framework for Large Transformers. In Network and Distributed System Security Symposium (NDSS), 2025. 10
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Zimerman, I., Baruch, M., Drucker, N., Ezov, G., Soceanu, O., and Wolf, L. Converting transformers to polynomial form for secure inference over homomorphic encryption. In Proceedings of the 41st International Conference on Machine Learning (ICML), volume 235 of Proceedings of Machine Learning Research, pp. 62803–62814. PMLR, 2024.
11
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
A. Appendix Overview This appendix is organized as follows. Appendix B reports additional experiments. Appendix C collects standard masking routines, and Appendices D and E provide supporting lemmas for interval indicators, Boolean normalization, and low-bit masked rewrites. Appendix F gives the full compilation protocol. Appendix G clarifies the scope of operator specifications and how vector-level blocks are composed from standard MPC reductions and elementwise gates. Appendix H consolidates the typing discipline and a minimal typed specification language. Appendix I restates the backend interface primitives and formalizes mask-independent public shapes via padding. Appendices J, K, and L provide detailed correctness proofs. Appendix M gives a semi-honest security statement with explicit leakage and its proof. Appendix N provides a fully worked example of an operator specification and post-processing circuit (F, Φ). Finally, Appendix O summarizes the per-gate complexity accounting.
B. Additional Evaluation Results This appendix provides complementary evidence for the claims in Section 6: (i) accuracy under the fixed-point semantics used by secure inference, (ii) end-to-end attribution tables and additional sequence/model scaling results, (iii) gate-level microbenchmarks that isolate FuseFSS’s compiled nonlinear activation kernels, (iv) ablations that attribute performance to specific design choices (mask-independent shapes and program reuse), and (v) best-effort baseline attempts for BOLT, BumbleBee, and SHAFT with implementation notes on why results are not directly comparable. B.1. Accuracy We verify that FuseFSS preserves model quality under the fixed-point arithmetic (including truncation/rounding) used by secure inference. We compare floating-point PyTorch inference with FuseFSS running the same models under our MPC-style fixed-point semantics. Table 4 shows that FuseFSS closely matches PyTorch across GLUE and LAMBADA. Table 4. Accuracy under fixed-point semantics, where ∆ = (FuseFSS−PyTorch). Model
Task
PyTorch
FuseFSS
∆
BERT-tiny
SST-2 MRPC QNLI
80.39 76.37 85.69
80.39 76.96 86.23
+0.00 +0.59 +0.54
BERT-base
SST-2 CoLA MRPC QNLI
89.33 83.43 88.73 91.55
89.33 83.45 88.48 91.67
+0.00 +0.02 -0.25 +0.12
BERT-large
SST-2 CoLA MRPC QNLI
92.55 85.52 87.74 92.49
92.50 85.57 87.50 92.66
-0.05 +0.05 -0.24 +0.17
GPT-2 GPT-Neo
LAMBADA LAMBADA
60.59 75.46
60.90 75.57
+0.31 +0.11
B.2. End-to-End Attribution and Extended Scaling End-to-End Breakdown. To attribute end-to-end improvements to FuseFSS’s compilation of nonlinear blocks, Tables 5 and 6 decompose the online cost into: (i) total send/recv time and total computation time (excluding send/recv), and (ii) the communication volume, together with the portions attributable to key blocks (softmax, GELU, layer normalization, and truncation for time). We project online latency under a network with one-way bandwidth BW and round-trip latency RTT as 2 · Bcomm + R · RTT. (1) Tproj = Tcomp + BW Here Tcomp is the computation time excluding send/recv, estimated as Tcomp := Ttotal − Tsend/recv . Bcomm is the per-party online communication volume, as reported by the Comm (GB) / Total comm (GB) columns in our tables. We multiply by 2 to account for both directions (send and recv) under a symmetric-link assumption. R is the number 12
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
of interactive synchronization rounds in the online protocol. Our rounds count uses the actual number of rounds counted in the evaluation. Table 5. Seq=128 breakdown of online time. Model
Variant
Comm time (ms)
Comp time (ms)
Softmax (ms)
GELU (ms)
LayerNorm (ms)
Truncate (ms)
BERT-tiny BERT-tiny BERT-base BERT-base BERT-large BERT-large GPT-2 GPT-2 GPT-Neo GPT-Neo
Sigma FuseFSS Sigma FuseFSS Sigma FuseFSS Sigma FuseFSS Sigma FuseFSS
6.3 5.6 316.2 129.0 645.5 417.2 204.9 119.7 801.7 523.6
57.6 37.0 1297.5 1020.4 3388.9 2580.7 1219.0 953.0 5524.5 4592.2
16.4 9.8 356.1 160.4 785.8 399.3 228.5 101.8 442.8 252.7
4.2 1.6 211.9 42.5 516.6 118.8 197.0 40.4 921.5 232.8
14.2 7.6 145.8 80.3 309.4 205.2 151.8 83.5 518.6 323.2
5.1 4.5 193.6 203.6 601.0 504.4 221.8 181.4 1081.2 1010.2
Table 6. Seq=128 breakdown of online communication. Model
Variant
Total comm (GB)
Softmax comm (GB)
GELU comm (GB)
LayerNorm comm (GB)
BERT-tiny BERT-tiny BERT-base BERT-base BERT-large BERT-large GPT-2 GPT-2 GPT-Neo GPT-Neo
Sigma FuseFSS Sigma FuseFSS Sigma FuseFSS Sigma FuseFSS Sigma FuseFSS
0.021 0.018 1.062 0.891 2.833 2.376 0.885 0.777 4.326 3.917
0.005 0.003 0.278 0.149 0.742 0.399 0.141 0.076 0.383 0.207
0.003 0.003 0.171 0.129 0.456 0.343 0.171 0.129 0.931 0.698
0.002 0.002 0.119 0.119 0.319 0.318 0.119 0.119 0.649 0.649
Section 6.4 gives the per-substep softmax profile that isolates the compiled helper path from max-reduction. The cache ablation in Table 10 accounts for only 9.486 ms of initialization overhead on BERT-base, far below the 464.3 ms end-to-end gain in Table 1; the dominant savings therefore come from the compiled nonlinear/helper path rather than program reuse alone. Longer Contexts and Larger Models. To complement Table 2 (BERT-base), Table 7 evaluates GPT-2 up to 512 tokens and Table 8 reports end-to-end LLaMA-family runs. Table 7. Sequence-length sweep for GPT-2 (batch size 1). Seq
Sigma time (ms)
FuseFSS time (ms)
↓ (%)
Sigma comm (GB)
FuseFSS comm (GB)
128 256 512
1423.90 2650.00 5630.10
1072.70 1795.10 3944.00
24.7 32.3 29.9
0.885 2.129 5.693
0.777 1.786 4.491
Table 8. End-to-end LLaMA-family results. Key size reports total offline material; these runs use host-side key buffers and streaming. Model
Seq
Sigma (ms)
FuseFSS (ms)
Speedup
Sigma Key (GB)
FuseFSS Key (GB)
Sigma Keygen (s)
FuseFSS Keygen (s)
Keygen Speedup
LLaMA-7B LLaMA-7B LLaMA-7B LLaMA-3.1-8B LLaMA-3.1-8B LLaMA-3.1-8B
16 32 64 16 32 64
6053 7651 10 919 6517 8504 12 478
5567 6512 8927 6213 7683 10 623
1.09 1.17 1.22 1.05 1.11 1.17
71.63 95.74 146.10 86.78 116.31 175.37
68.95 90.17 134.19 83.09 108.74 160.04
4.31 4.78 6.38 4.57 5.47 7.27
3.93 4.17 5.09 4.30 5.06 6.58
1.10 1.15 1.25 1.06 1.08 1.11
B.3. Gate Microbench: Compiled Activations To isolate the effect of FuseFSS on nonlinearities, we microbenchmark compiled activation gates at L=128. Each gate corresponds to one activation invocation on its full tensor (e.g., GELU/SiLU on a (128, dff ) MLP intermediate). For 13
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
BERT-base and GPT-2, dff =3072; for BERT-large, dff =4096; and for LLaMA-7B SiLU, dff =11008. We report per-gate online evaluation time and online communication, together with the preprocessing key material size. To ensure a fair comparison, FuseFSS compiles the same fixed-point operator specifications used by Sigma, so speedups do not come from using coarser approximations. Figure 1 shows that FuseFSS achieves consistent communication savings (≈24%) and substantial per-gate speedups (1.64– 2.46×). FuseFSS also shrinks per-gate key material by 4.96–6.25×. These gate-level gains are larger than the end-to-end improvements in Table 1, because end-to-end inference is dominated by linear layers and attention whose costs are largely shared by both systems; Appendix B.2 quantifies the fraction of end-to-end time/communication attributable to nonlinear blocks. FuseFSS
Sigma Online comm per gate (MB)
Online time per gate (ms)
Sigma
60
40
20
0
FuseFSS
60
40
20
0 BERT-base (GELU)
BERT-large (GELU)
GPT-2 (GELU)
LLaMA-7B (SiLU)
BERT-base (GELU)
BERT-large (GELU)
Key material per gate (MB)
Sigma
GPT-2 (GELU)
LLaMA-7B (SiLU)
FuseFSS
1000 800 600 400 200 0 BERT-base (GELU)
BERT-large (GELU)
GPT-2 (GELU)
LLaMA-7B (SiLU)
Figure 1. Gate-level activation microbench at L=128.
B.4. Ablation: Cost of Mask-Independent Shapes and Reuse We quantify two implementation choices required by FuseFSS’s leakage model and runtime design: (i) padding compiled backend instances to a mask-independent public shape, and (ii) caching the compiled gate program across transformer layers. All numbers in this subsection come from an internal gate microbenchmark that isolates program initialization (instantiation/dispatch setup of the compiled GPU program) and online gate evaluation time; it does not include end-to-end transformer components nor LAN/WAN projection. We benchmark a representative GELU compiled gate in a BERT-base setting. Mask-Independent Public Shapes via Padding. Padding is required by our leakage model: otherwise, mask-dependent instance shapes (e.g., the number of emitted predicate queries) would reveal information about the secret mask and therefore about the secret input given the public masked opening x̂. FuseFSS pads both the predicate query list and the translated lookup partition to fixed public shapes. Table 9 quantifies the overhead on a representative BERT-base GELU gate. Enforcing fixed shapes increases per-gate evaluation time from 0.264 ms to 1.014 ms, and increases the compiled gate instance description size from 2,464 B to 2,848 B. The LUT payload is unchanged; the increase comes from padding the predicate list (384 B → 768 B). The runtime overhead is larger than the key-size increase because evaluation scales with the number of predicate queries and becomes GPU memory/dispatch dominated for this small gate. Table 9. Padding overhead for mask-independent public shapes. Variant mask-dependent shape fixed-shape (FuseFSS)
Per-gate time (ms)
Instance size (B)
Pred / LUT (B)
0.264 1.014
2,464 2,848
384 / 2,080 768 / 2,080
14
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Program Reuse Across Layers. FuseFSS compiles each gate type once and reuses the resulting GPU program across layers. This does not reuse preprocessing masks or keys: each layer still consumes fresh masks/keys. Table 10 shows that instantiating the program per layer incurs 10.389 ms total initialization overhead on BERT-base (12 GELU calls), while the online evaluation time is unchanged. Table 10. Ablation: caching the compiled gate program amortizes initialization across BERT-base layers. Variant
# prog. inits
Total init (ms)
Total eval (ms)
1 12
0.903 10.389
12.161 12.184
cached (reuse one program) no cache (instantiate per layer)
B.5. Best-Effort Baseline Attempts: BOLT and BumbleBee We mainly focus on Sigma because it matches our threat model and execution regime (GPU-accelerated FSS-based inference). To increase transparency about other systems discussed in Section 2, we also attempted to run BOLT (Pang et al., 2024) and BumbleBee (Lu et al., 2025) in our environment and align the sequence length to 128 when possible. These results are not directly comparable to FuseFSS/Sigma because (i) the protocol family and threat model differ (2PC+HE or SPU-based 2PC vs. two-server FSS preprocessing), and (ii) the available execution hardware differs (CPU-only vs. GPU). We therefore report them only as best-effort outcomes and implementation notes. BumbleBee provides a GPU path only when a CUDA-enabled JAX/SPU backend is available; in our setup, secure (SPU) GPU compilation was unstable, while plaintext JAX execution was functional. BOLT is CPU-only in our setup and uses an HE-based protocol stack, so a like-for-like GPU comparison is not currently possible. For SHAFT (Kei & Chow, 2025), we treat it as an orthogonal system rather than a direct baseline. SHAFT contributes constant-round softmax and a GELU approximation inside a secret-sharing backend, whereas FuseFSS compiles compatible scalar nonlinear/helper operators in a two-server preprocessing regime. We attempted a GPT-2 SHAFT run in our environment, but its CUDA support was incompatible with our device, so we keep Sigma as the primary like-for-like GPU FSS baseline and do not claim a head-to-head SHAFT comparison. Table 11. Best-effort baseline attempts in our environment (batch size 1). System
Protocol family
Hardware
Model/task
Seq
Outcome
BOLT BumbleBee BumbleBee BumbleBee BumbleBee BumbleBee
2PC+HE 2PC (SPU) 2PC (SPU) plaintext plaintext 2PC (SPU)
CPU-only CPU-only CPU-only GPU GPU GPU
BERT BERT GPT-2 BERT GPT-2 BERT/GPT-2
128 128 128 128 128 128
295.44 s (P1) / 354.37 s (P2); 58.03 GB total comm. 289.84 s end-to-end; comm not exposed. 287.31 s end-to-end; comm not exposed. 3.29 s end-to-end. 40.61 s end-to-end. failed during SPU compilation due to an XLA HLO importer overflow under our JAX/XLA stack.
C. Masking Protocols These are standard routines for revealing a masked value x̂ = x + rin mod 2n and for locally deriving additive shares of x from a public x̂ (Protocol 1 and Protocol 2). Protocol 1 Shares → masked opening Require: JxK = (x0 , x1 ) and preprocessed Jrin K = (r0 , r1 ). Ensure: Public x̂ = x + rin mod 2n . 1: Each Pb computes x̂b ← xb + rb mod 2n . 2: Parties exchange x̂0 , x̂1 and reconstruct x̂ ← x̂0 + x̂1 mod 2n . 15
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Protocol 2 Masked → shares (local) Require: Public x̂ and Jrin K = (r0 , r1 ). Ensure: JxK such that x = x̂ − rin mod 2n . 1: P0 sets x0 ← (x̂ − r0 ) mod 2n ; P1 sets x1 ← (−r1 ) mod 2n (all in R).
D. Interval Indicators and Boolean Normalization The following lemmas justify our interval-indicator construction and Boolean normalization used in Section 4. Interval Indicators Without AND Gates. Because the partition boundaries are strictly increasing in the canonical order, interval membership can be expressed using only XOR of two comparisons (with the sentinel convention I[x<2n ] ≡ 1). Lemma D.1 (Interval indicator as XOR of comparisons). For boundaries αi < αi+1 and any x ∈ R, interpreted by its canonical representative in {0, . . . , 2n − 1}, I[x∈Ii ] = I[x<αi+1 ] ⊕ I[x<αi ] . Proof. If x < αi then also x < αi+1 , so the pair of bits (I[x<αi ] , I[x<αi+1 ] ) can only be (1, 1), (0, 1), or (0, 0). The XOR equals 1 exactly in the middle case x < αi+1 and x ≥ αi , i.e., x ∈ [αi , αi+1 ). Eliminating Piecewise Boolean Control Flow. Using Lemma D.1, piecewise Boolean outputs can be normalized into a single global Boolean circuit without revealing the active interval. Lemma D.2 (Boolean normalization by interval indicators). Let (Ii )m−1 i=0 be a full partition as in Definition 4.1. For each output bit index j ∈ {1, . . . , ℓ}, define the interval-indicator bit Ji (x) := I[x∈Ii ] and B (j) (x) =
m−1 M
(j) Ji (x) ∧ Bi (x) .
i=0 (j)
Then B (j) (x) = Bi⋆ (x) for the unique i⋆ with x ∈ Ii⋆ . Proof. Exactly one indicator I[x∈Ii ] equals 1 and all others equal 0. Thus the XOR of the AND-masked pieces selects the active piece without revealing i⋆ .
E. Low-Bit Predicate Rewrite The following lemma provides the masked rewrite identity for low-bit predicates used by truncation/ARS-style helpers. Lemma E.1 (Masked rewrite for low-bit predicate). Fix f ∈ [n] and let Nf = 2f . Fix an integer threshold γ ∈ {0, 1, . . . , Nf } and a mask r ∈ R. Let rf = rep(r) mod Nf and x̂f = rep(x̂) mod Nf , let θ = (rf + γ) mod Nf , and w = I[rf +γ≥Nf ] . Assume preprocessing provides an XOR-sharing ⟨w⟩. Then for all x ∈ R, I[(x mod 2f )<γ] = I[x̂f <θ] ⊕ I[x̂f <rf ] ⊕ w, where comparisons are under the canonical order on {0, . . . , Nf − 1}. Proof. Let xf := rep(x) mod Nf . Since 2f | 2n , we have x̂f = (xf + rf ) mod Nf . The statement follows by applying the same carry-bit argument as Lemma 4.3 over [0, Nf ), equivalently by instantiating Lemma 4.3 in Z2f .
F. Full Compilation Protocol Protocol 3 gives high-level pseudocode for compiling a scalar gate instance into the two backend primitive instances. 16
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Protocol 3 Compile a scalar gate instance to two backend primitive instances m−1 m−1 Require: Operator specification ({αi }m i=0 , {Pi }i=0 , {Bi }i=0 ) and preprocessing mask rin ∈ R. Ensure: Packed comparison instance Πpred and interval lookup instance Πcoeff . 1: N ← 2n {Well-formed integer boundaries 0 = α0 < · · · < αm = N imply m ≤ N .} 2: M ← min(m + 1, N ) {if m = N then M = N (padding to N +1 is impossible)} 3: r ← rep(rin ) ∈ {0, . . . , N − 1} {canonical representative} 4: (1) Lookup partition with mask-independent shape (target M intervals). 5: for i ← 0 to m − 1 do 6: si ← (αi + r) mod N {translated start of original interval Ii = [αi , αi+1 )} 7: end for 8: Let π be a permutation such that sπ(0) < sπ(1) < · · · < sπ(m−1) 9: βj ← sπ(j) for j = 0, . . . , m − 1 {sorted translated starts in [0, N )} 10: if β0 = 0 then {0 ∈ {si }, i.e., the wrap point hits an existing boundary; translated partition has m intervals} 11: B ← (0, β1 , . . . , βm−1 , N ) 12: ord ← (π(0), π(1), . . . , π(m − 1)) 13: if m < N then {pad by splitting one standard interval to reach M = m + 1} 14: Let j ⋆ be the smallest index such that Bj ⋆ +1 − Bj ⋆ ≥ 2 {exists since m < N } 15: δ ← Bj ⋆ + 1 {any integer with Bj ⋆ < δ < Bj ⋆ +1 works} 16: Insert δ into B at position j ⋆ +1 {split [Bj ⋆ , Bj ⋆ +1 )} 17: Insert a copy of ordj ⋆ into ord at position j ⋆ +1 {duplicate payload so both sub-intervals return identical data} 18: end if 19: else {β0 > 0, so 0 ∈ / {si }: exactly one translated interval wraps and is split at 0 (thus m < N and M = m + 1)} 20: B ← (0, β0 , β1 , . . . , βm−1 , N ) 21: ord ← (π(m − 1), π(0), π(1), . . . , π(m − 1)) {π(m − 1) duplicated for the two pieces [0, β0 ) and [βm−1 , N )} 22: end if {Now |B| = M +1 and |ord| = M . The public shape (M, p) is mask-independent; (B, ord) may depend on r but is embedded in secret keys.} 23: (2) Boolean normalization. 24: Normalize piecewise Boolean outputs via interval indicators (Lemma D.2). 25: (3) Mask rewrite. 26: Rewrite all primitive predicates under masking using Lemmas 4.3–E.1 and MSB/signed reductions via fixed public shifts. {Carry/wrap bits depending only on r are provided as secret-shared instance constants.} {Only descriptor-level sentinels are simplified: C0 ≡ 0, CN ≡ 1, D0,f ≡ 0, D2f ,f ≡ 1.} 27: (4) Fixed predicate query list. 28: Q ← collect all masked comparison atoms after rewriting in a fixed descriptor order. {No mask-dependent deduplication/elimination (e.g., do not drop atoms because a mask-derived θ happens to be 0).} {Canonicalize to I[viewk,c (x̂)<θ] per backend interface.} 29: (5) Build backend instances. 30: Build Πpred as a single packed comparison instance with query list Q. 31: for j ← 0 to M − 1 do 32: Set payload vj ← (coefficients/constants of Pordj , padded to degree d as needed) 33: end for 34: Build Πcoeff as an interval lookup instance with boundaries (B0 , . . . , BM ) and payloads (v0 , . . . , vM −1 ).
G. Scope of Operator Specifications and Composition of Vector Blocks This appendix complements Section 4.2 by clarifying the exact function class covered by operator specifications and illustrating how vector-level transformer blocks are expressed by composing standard MPC reductions with elementwise specification-compatible scalar gates (Definition 4.2). What Operator Specifications Cover. An operator specification (Definition 4.1) targets scalar maps on fixed-point words over R = Z2n : the input is one ring element and the output is a constant-size tuple of ring elements and bits. This naturally includes elementwise nonlinear activations implemented by piecewise low-degree polynomial approximations (e.g., ReLU and spline-approximated GeLU/SiLU), as well as range-reduced polynomial blocks used in practice (e.g., nExp). Many scalar fixed-point helper operations (e.g., truncation/ARS and wrap-/round-aware corrections) are not literal polynomials in R. In our framework they are handled as specification-compatible scalar gates (Definition 4.2): the operator 17
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
specification exposes the required predicate/helper bits and any piecewise polynomial components, while a fixed deterministic share-based post-processing circuit Φ implements the faithful fixed-point semantics using standard preprocessing (Beaver/AND/B2A/A2B). What Operator Specifications Do Not Cover. Operator specifications are not intended as an IR for vector reductions such as max over a vector, sorting, top-k, or attention sparsification with data-dependent routing. These operations are not univariate scalar functions and typically require interactive MPC subprotocols (e.g., comparison trees) whose structure depends on vector length. We treat them as separate, standard MPC components. How Softmax / Layer Norm Are Handled. Vector blocks are expressed as compositions of: (i) linear operations over additive shares (free additions and Beaver multiplications), (ii) comparison-based reductions (e.g., max-reduction via a comparison tree), and (iii) scalar specification-compatible gates (e.g., nExp and reciprocal / rsqrt). For example, a standard fixed-point softmax pipeline can be written as: 1. m ← maxi xi (comparison tree; not covered by operator specifications). 2. x′i ← xi − m (linear). 3. ei ← nExp(x′i ) (specification-compatible scalar gate). P 4. s ← i ei (linear). 5. t ← Recip(s) (specification-compatible scalar gate). 6. yi ← ei · t (Beaver multiplications). LayerNorm is similar: mean/variance reductions are linear, while reciprocal-square-root is a scalar specification-compatible gate. Our FuseFSS targets the scalar nonlinear operators and helper operations that dominate fixed-point secure transformer inference cost (either directly as operator specifications or via specification-compatible gates with fixed post-processing), while vector reductions are handled by standard MPC subprotocols and composed with scalar gates.
H. Typing Discipline and Typed Specification Language This appendix consolidates the typing discipline and the minimal typed expression language used for operator specifications and specification-compatible post-processing. Base Types and Sharing Domains.
Fix n ≥ 1 and let R = Z2n . We use two base value types: An := R = Z2n ,
B := {0, 1}.
Arithmetic wires have type An and are represented as additive shares JxK = (x0 , x1 ) with x = x0 + x1 mod 2n . Bit wires have type B and are represented as XOR shares ⟨b⟩ = (b0 , b1 ) with b = b0 ⊕ b1 . Embedding.
We use the canonical embedding ι : B ,→ An that maps 0, 1 ∈ B to the corresponding ring elements in R.
Primitive Predicates and Typing.
Primitive predicates are typed maps An → B: Cβ (x) = I[x<β] : An → B, Dγ,f (x) = I[(x mod 2f )<γ] : An → B, MSB(x + c) : An → B,
where β ∈ {0, . . . , 2n }, f ∈ {1, . . . , n}, γ ∈ {0, . . . , 2f }, and c ∈ R is a public constant. Boolean connectives ¬, ∧, ∨, ⊕ are operations on B (with ⊕ denoting XOR). 18
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Mixed-Domain Conversions.
Whenever a bit gates arithmetic computation, we use a standard secure conversion B2A : ⟨b⟩ 7→ Jι(b)K ∈ An ,
and whenever an arithmetic (secret-shared) value must be used as a bit, we use A2B : JxK 7→ ⟨b⟩
for a suitable extracted bit b.
Both are treated as standard preprocessing-based secure subprotocols; their invocations are counted in complexity statements. Operator Specification Signature.
A typed operator specification has signature F : An → Arn × Bℓ ,
optionally annotated with fixed-point metadata (fractional bits, signedness), which determines which primitive predicates and correction bits are required by faithful fixed-point semantics. The semantic definition of an operator specification (partition, per-interval polynomials and Boolean formulas) is given in Definition 4.1. Post-Processing Circuits and Instance Constants. A specification-compatible scalar gate G (Definition 4.2) is implemented as G(x) = Φ F (x), κ, x, x̂, pub , where x̂ = (x + rin ) mod 2n is the public masked input and κ = κ(rin ) denotes mask-derived instance constants (kept secret-shared). To make typing explicit, we view κ ∈ K := Aan × Bb , i.e., κ = (κA , κB ) consists of a ring elements (additively shared) and b bits (XOR-shared). The public parameter bundle pub may include bit-widths, scaling metadata, and approximation parameters. A Minimal Typed Expression Language Bit Expressions for Operator Specifications. Within an operator specification, each per-interval Boolean output is a bit expression over the input x: bspec ::= 0 | 1 | Cβ (x) | Dγ,f (x) | MSB(x + c) | ¬bspec | (bspec ⊕ bspec ) | (bspec ∧ bspec ) | (bspec ∨ bspec ). All such expressions have type B. Polynomial Expressions for Arithmetic Outputs. Each per-interval arithmetic output is a ring polynomial in the single variable x (evaluated in R): p ::= c | x | p + p | p − p | p · p, where c ∈ R is a descriptor constant. Each p has type An . Post-Processing Expressions. The post-processing circuit Φ may compute both arithmetic outputs and Boolean outputs from: (i) the arithmetic outputs yj ∈ An and Boolean outputs zj ∈ B of F (x), (ii) mask-derived instance constants κ = (κA , κB ), (iii) additive shares of the unmasked input x (e.g., derived locally from (x̂, Jrin K) via Protocol 2), and (iv) public values including x̂. We use two mutually-typed expression grammars: Bit expressions for Φ (type B): b ::= 0 | 1 | zj | κBt | A2B(e) | ¬b | (b ⊕ b) | (b ∧ b) | (b ∨ b). Arithmetic expressions for Φ (type An ): e ::= c | x | yj | κAt | x̂ | e + e | e − e | e · e | B2A(b), where c ∈ R may also include public constants derived from pub. 19
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Well-Formedness. An operator specification is well-formed if: (i) its boundaries are strictly increasing integers, (ii) each per-interval arithmetic output is a polynomial expression in R[x], and (iii) each Boolean output is a well-typed bit expression built from primitive predicates and connectives. A specification-compatible gate (F, Φ) is well-formed if: (i) Φ is fixed (descriptor-determined) and independent of the sampled mask beyond its access to (κ, x, x̂, pub) as inputs/parameters, and (ii) any use of a bit in arithmetic inside Φ occurs only via an explicit B2A(·) node, and any extraction of a bit from a secret-shared ring value occurs only via an explicit A2B(·) node.
I. Backend Interface This appendix formalizes a minimal interface sufficient for the compiler, while keeping the assumptions “implementationrealistic”. I.1. A Multi-View Packed Predicate Primitive Section 3.6 defines packed comparison as a single primitive family that evaluates a list of comparisons on the same public masked input x̂ ∈ R, where each query may use a different bit-width kt and an optional public shift ct through the public view operator viewk,c (·). This appendix restates that interface as a multi-view packed predicate primitive to make explicit that full-width comparisons, low-bit predicates, and shifted/signed predicates can all be handled within a single non-interactive primitive evaluation per gate instance. Definition I.1 (Multi-view packed predicate primitive). Fix n ≥ 1 and R = Z2n . A multi-view packed predicate primitive instance is specified by a list T Q = (kt , ct , θt ) t=1 , where 1 ≤ kt ≤ n, ct ∈ Z2kt is a public constant, and θt ∈ Z2kt is an instance parameter (possibly derived from preprocessing-time secrets such as masks). On input x̂ ∈ R, define the public view viewk,c (x̂) := (x̂ mod 2k ) + c mod 2k ∈ Z2k , and define the output bits T PredQ (x̂) := I[viewk ,c (x̂)<θt ] ∈ {0, 1}T . t t t=1 A backend provides protocols (Gen, Eval0 , Eval1 ) such that Gen(1λ , Q) → (k0 , k1 ) and on public x̂, each party outputs XOR-shares Evalb (kb , x̂) ∈ {0, 1}T whose XOR reconstructs to PredQ (x̂). Definition I.1 is an interface-level abstraction. It can be instantiated by existing DCF/DPF-style implementations by generating one comparison key per query (kt , ct , θt ) and concatenating/batching keys. Each party can locally compute the public views viewkt ,ct (x̂) and evaluate all comparison keys in a single batched routine (e.g., one GPU kernel launch). The security proofs in this paper only rely on standard single-key privacy of FSS primitives (with public shape leakage). I.2. Interval Lookup with Vector Payload We restate the interval-lookup primitive: given boundaries and payload vectors, on input x̂ ∈ R output additive shares of the payload for the unique interval containing x̂. Definition I.2 (Interval lookup with vector payload). Fix n ≥ 1 and R = Z2n . An interval-lookup instance is specified by boundaries 0 = α0 < · · · < αM = 2n and payload vectors vi ∈ Rp for i ∈ {0, . . . , M − 1}. On input x̂ ∈ R, let i⋆ be the unique index such that rep(x̂) ∈ [αi⋆ , αi⋆ +1 ) and define LUT(x̂) := vi⋆ ∈ Rp . A backend provides protocols (Gen, Eval0 , Eval1 ) such that Gen(1λ , ({αi }, {vi })) → (k0 , k1 ) and, on public x̂, each party outputs additive shares Evalb (kb , x̂) ∈ Rp that sum (in Rp ) to LUT(x̂). Fixed Shape Requirement. For our real/ideal security statement with a clean leakage function, we require that public shape parameters, the number of predicate outputs T , the number of intervals, and the payload dimension p, depend only on the operator specification (public) and not on preprocessing-time secrets (e.g., masks). This avoids “mask-dependent key length” leakage. In practice, this can be ensured by: (i) disabling deduplication that might depend on mask-derived 20
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
thresholds, and (ii) padding to a fixed worst-case interval count M := min(m+1, 2n ) (duplicating payloads only when m < 2n and a split does not actually occur). We formalize this below. Proposition I.3 (Mask-independent shape via padding). Fix an operator specification with m intervals and fixed predicate grammar size. There exists a compiler convention such that the emitted backend interface instances have public shape parameters (T, p, M ) that depend only on the operator specification (and fixed-point metadata), where T is the number of predicate outputs, p is the payload dimension, and M is the number of lookup intervals, and are independent of the sampled mask rin . Proof. The number of primitive predicates required by the compiler (before masking) is determined syntactically by the operator specification and metadata. Each such predicate is rewritten into a fixed number of masked comparison queries (two comparisons per Lemmas 4.3 and E.1), plus a constant number of MSB/signed-related comparisons. By not performing any deduplication that depends on mask-derived threshold values, we obtain a fixed T . For interval lookup, Lemma 4.4 shows the translated partition uses at most m + 1 standard intervals, and with integer boundaries it cannot exceed N = 2n intervals. We therefore fix the public lookup interval count as M := min(m + 1, N ). Let β0 denote the smallest translated start (Protocol 3). If β0 > 0 (equivalently 0 ∈ / {si }), then exactly one translated interval wraps and the translated partition has m + 1 standard intervals; we include 0 as a boundary and duplicate the wrapped interval’s payload on both sides of 0. If β0 = 0 (equivalently 0 ∈ {si }), then no interval wraps and the translated partition has only m standard intervals. If additionally m < N (so M = m + 1), then some standard interval has length at least 2; we insert a dummy split point δ strictly inside such an interval and duplicate its payload, yielding M intervals. If m = N , then M = N and no padding is needed (and padding is impossible). Thus M depends only on the public operator specification and n, and is independent of the sampled mask. Finally, the payload dimension p is fixed by the operator specification and metadata: for r arithmetic outputs and global degree bound d, the coefficient payload contributes r(d + 1) ring elements with descriptor-level padding of lower-degree polynomials, plus a fixed number paux of per-interval auxiliary constants required by Φ. Hence p is descriptor-determined and mask-independent.
J. Proofs for Boolean Normalization and Mask Rewriting J.1. Proof of Lemma D.2 We restate the key fact that interval indicators form a partition. Lemma J.1 (Interval indicators form a partition). Let 0 = α0 < · · · < αm = 2n and define Ji (x) = I[x<αi+1 ] ⊕ I[x<αi ]
for i ∈ {0, . . . , m − 1},
with the sentinel convention I[x<2n ] ≡ 1. Then for every x ∈ {0, . . . , 2n − 1}, exactly one Ji (x) = 1 and all others are 0. Proof. By definition of the partition, there exists a unique i⋆ such that αi⋆ ≤ x < αi⋆ +1 . Equivalently, I[x<αi⋆ ] = 0 and I[x<αi⋆ +1 ] = 1, hence Ji⋆ (x) = 1. For j < i⋆ , we have x ≥ αj+1 so I[x<αj+1 ] = 0 and Jj (x) = 0. For j > i⋆ , we have x < αj so I[x<αj ] = 1 and also I[x<αj+1 ] = 1, hence Jj (x) = 0. Lemma D.2 follows immediately: since exactly one indicator is 1, the XOR of the AND-masked pieces selects the active piece. J.2. Proof of Lemma 4.3 Proof. Let N = 2n and interpret x, r ∈ R by their canonical representatives in {0, . . . , N − 1}. Define the masked value x̂ = (x + r) mod N and the (cyclic) interval J := [r, r + β) mod N ⊆ ZN . Since addition by r is a rotation (a bijection) on ZN , we have x < β if and only if x̂ ∈ J. Write θ = (r + β) mod N and w = I[r+β≥N ] . If w = 0 then θ = r + β ≥ r and J = [r, θ) is a standard interval. For any u ∈ {0, . . . , N − 1}, I[u∈[r,θ)] = I[u<θ] ⊕ I[u<r] , 21
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
by a direct check of the three ranges u < r, r ≤ u < θ, and u ≥ θ. If w = 1 then θ = r + β − N (so θ < r unless β = N ) and J = [r, N ) ∪ [0, θ). For any u ∈ {0, . . . , N − 1}, I[u∈J] = I[u<θ] ⊕ I[u<r] ⊕ 1, by a direct check of the three ranges u < θ, θ ≤ u < r, and u ≥ r. Substituting u = x̂ gives I[x<β] = I[x̂<θ] ⊕ I[x̂<r] ⊕ w as claimed. J.3. Signed Comparisons and MSB(x + c) Under Masking We treat signed values in two’s complement: for N = 2n , the signed order corresponds to the cyclic order on ZN starting at 2n−1 . Let s := 2n−1 and define the public rotation operator viewn,s (u) := (u + s) mod N . Signed Comparison as an Unsigned Comparison After a Fixed Shift. Let β ∈ {0, . . . , N − 1} be a two’s-complement signed threshold represented in R. Define β ′ := (β + s) mod N . Then I[x<signed β] = I[viewn,s (x)<β ′ ] . Now suppose x̂ = (x + r) mod N is the public masked opening. Since viewn,s (x̂) = (viewn,s (x) + r) mod N , applying Lemma 4.3 yields I[x<signed β] = I[viewn,s (x̂)<θ] ⊕ I[viewn,s (x̂)<r] ⊕ w, where θ = (r + β ′ ) mod N and w = I[r+β ′ ≥N ] . MSB(x + c) as a Masked Unsigned Threshold Test.
For any constant c ∈ R,
MSB(x + c) = ¬ I[(x+c) mod N <s] . Let xc := viewn,c (x) = (x + c) mod N and x̂c := viewn,c (x̂). Applying Lemma 4.3 to I[xc <s] gives I[xc <s] = I[x̂c <θ1/2 ] ⊕ I[x̂c <r] ⊕ w1/2 , where θ1/2 = (r + s) mod N and w1/2 = I[r+s≥N ] . Therefore, MSB(x + c) = ¬ I[x̂c <θ1/2 ] ⊕ I[x̂c <r] ⊕ w1/2 . All comparisons above are of the backend-supported form I[viewk,c (u)<θ] on the public x̂.
K. Proof of the Interval Translation Lemma Lemma K.1 (Restatement of Lemma 4.4). Let N = 2n and fix r ∈ {0, . . . , N − 1}. For an interval I = [α, β) ⊆ [0, N ) and the map x̂ = (x + r) mod N , the image Tr (I) is the cyclic interval [α + r, β + r) mod N , which is either a single standard interval or a union of two standard intervals. Across a full partition 0 = α0 < · · · < αm = N , at most one interval splits after translation. Proof. The map Tr is a rotation on the circle ZN . The image of I = [α, β) is Tr (I) = {(x + r) mod N : x ∈ [α, β)} = [α + r, β + r) mod N. Write a := α + r and b := β + r (so 0 ≤ a < b < 2N ). There are three cases: (i) if b ≤ N , then Tr (I) = [a, b) is a standard interval; (ii) if a ≥ N , then both endpoints wrap and Tr (I) = [a − N, b − N ) is a standard interval; (iii) if a < N < b, then the image wraps around N and Tr (I) = [a, N ) ∪ [0, b − N ), a union of two standard intervals. For a full partition, the only way an interval splits is if the wrap point x0 := (N − r) mod N ∈ [0, N ) lies strictly inside that interval in x-space (equivalently, if 0 lies strictly inside its image in x̂-space). Since x0 is a single point and the intervals are disjoint, at most one interval contains it, hence at most one interval splits (and if x0 hits a boundary, no interval splits). 22
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
L. Correctness of Compilation and the Two-Call Theorem This section provides a full proof of Theorem 4.6. We first formalize the compiled evaluation procedure and then prove correctness and the stated complexity bound. L.1. Compiled Gate Evaluation Procedure Fix a typed operator specification F : An → Arn ×Bℓ with partition (αi )m i=0 and per-interval data (Pi , Bi ). Fix preprocessing mask rin ∈ R and define x̂ = x + rin mod 2n . The compiler emits: (i) a predicate primitive instance Πpred producing XOR-shares of all primitive masked comparisons required by the rewritten Boolean circuit, and (ii) an interval-lookup primitive instance Πcoeff producing additive shares of the active interval’s coefficient vector and auxiliary constants. Online evaluation on a shared input JxK proceeds as: 1. Materialize public x̂ by opening x̂ = x + rin (Protocol 1). 2. Run Πpred (if needed) to obtain XOR-shares of all required primitive masked comparisons on x̂ and its public views (low bits, shifts). 3. Run Πcoeff (if needed) to obtain additive shares of the active interval’s coefficient vector (and auxiliary constants). 4. Compute shares of x = x̂ − rin locally (Protocol 2). 5. Evaluate r degree-≤ d polynomials via Horner’s rule using Beaver triples to obtain JyK ∈ Rr .
6. Evaluate the normalized Boolean circuit (Lemma D.2) over XOR shares using AND correlation to obtain ⟨z⟩ ∈ Bℓ , and apply any deterministic post-processing Φ using B2A/A2B as needed.
L.2. Proof of Theorem 4.6 Theorem L.1 (Restatement of Theorem 4.6). Assume a backend provides: (i) a multi-view packed predicate primitive (Definition I.1), and (ii) an interval lookup primitive with vector payload. Then any scalar gate instance can be evaluated from a public masked input x̂ using at most two non-interactive backend interface evaluations, plus O(r · d) ring multiplications for Horner evaluation and the Boolean/mixed-domain costs stated in Theorem 4.6. Proof. We prove correctness and then the complexity bound. Step 1: Correct Interval-Dependent Coefficient Selection. Let the secret input be x ∈ R with canonical representative in [0, 2n ). Let i⋆ be the unique index such that x ∈ Ii⋆ = [αi⋆ , αi⋆ +1 ). By Lemma 4.4, the translated image of Ii⋆ under x̂ = x + rin mod 2n is either: (i) one standard interval in x̂-space, or (ii) two standard intervals when wrapping occurs. In compilation, if splitting occurs, the payload for the split interval is duplicated. Therefore, for the unique translated interval containing x̂, the interval-lookup primitive returns additive shares of exactly the coefficient vector associated with Ii⋆ . Step 2: Correct Predicate Values Under Masking. Consider any primitive predicate appearing in the predicate grammar. • For unsigned comparisons Cβ (x) = I[x<β] , Lemma 4.3 expresses Cβ (x) as an XOR of two masked comparisons on x̂ and a carry bit w that depends only on the preprocessing mask and constants. • For low-bit predicates Dγ,f (x) = I[(x mod 2f )<γ] , Lemma E.1 gives the analogous rewrite over Z2f . • MSB and signed predicates reduce to unsigned comparisons after fixed public shifts, and the corresponding masked rewrites follow by applying Lemma 4.3 to the shifted comparisons. The predicate primitive Πpred is constructed to output XOR-shares of all masked comparison atoms used in these rewrites (including comparisons against secret mask-derived thresholds such as rin and rin mod 2f ). Carry bits (which are constants independent of x) are provided as XOR-shared constants in preprocessing. Therefore, parties can locally compute XORshares of every primitive predicate value on x. 23
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Step 3: Eliminating Piecewise Boolean Control Flow. If the Boolean outputs of the operator specification are piecewise, Lemma D.2 rewrites them into a single global Boolean circuit using interval indicators Ji (x). Each Ji (x) is itself a Boolean circuit over comparisons of the form I[x<αi ] , hence can be computed correctly from the masked comparison atoms obtained in Step 2. Consequently, the normalized Boolean circuit evaluates to exactly the Boolean outputs of the operator specification, without revealing the active interval. Step 4: Correct Arithmetic Outputs via Horner Evaluation. Parties compute additive shares of x = x̂ − rin locally (Protocol 2). They hold additive shares of the correct coefficient vector for the active interval from Step 1. Evaluating each polynomial Pi⋆ ,j (x) of degree at most d by Horner’s rule uses at most d ring multiplications (exactly d if coefficients are padded to degree d and evaluated uniformly) and yields additive shares of Pi⋆ ,j (x) by standard Beaver multiplication correctness. This produces additive shares of the arithmetic outputs Pi⋆ (x). Step 5: Complexity Bound and “At Most Two” Primitive Evaluations. The protocol invokes at most one predicate primitive evaluation (Step 2) and at most one lookup primitive evaluation (Step 1), hence at most two non-interactive backend interface evaluations on the same public input x̂. Either call can be omitted in degenerate cases (no Boolean outputs/predicates or no interval-dependent coefficients). Horner evaluation uses r · d ring multiplications, hence O(r · d) Beaver triples. The Boolean circuit cost is captured by its number of AND gates G∧ and mixed-domain uses Gmix , as stated.
M. A Standard Real/Ideal Security Statement with Explicit Leakage This section introduces a standard real/ideal statement, including an explicit leakage function. Full proofs are given for the gate-level protocol; end-to-end transformer inference follows by standard composition. M.1. Leakage Function For a fixed gate type τ , define the public shape leakage Lshape (τ ) := (T, {kt }Tt=1 , M, p, #mults, #ANDs, #B2A/A2B), where: T and {kt } describe the multi-view predicate primitive shape, M and p describe the interval lookup shape, and the remaining counts describe how many standard preprocessed subprotocols are invoked in post-processing. By Proposition I.3, this leakage depends only on τ (public). The online protocol additionally reveals public masked wires such as x̂ and masked outputs ŷ; we treat these as explicit leakage: Lonline := (x̂, optional masked outputs). Since x̂ = x + rin with uniform rin , x̂ is uniform and information-theoretically independent of x. M.2. Ideal Functionality for a Scalar Gate Type (with Leakage) We define an ideal functionality FτL for a gate type τ that captures exactly what the real protocol reveals. Functionality FτL (Informal Description). On input shares from parties that reconstruct to x ∈ R, the functionality: (i) samples a uniform mask rin ← R, (ii) outputs x̂ = x + rin mod 2n to both parties as leakage, (iii) outputs additive/XOR shares of (y, z) = Gτ (x) to the parties, and (iv) outputs Lshape (τ ) as public leakage. This ideal world models exactly the fact that the protocol reveals masked values but keeps the unmasked x secret. M.3. Security of Subprotocols Assumed We assume standard semi-honest security for: • Beaver multiplication over R, 24
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
• Boolean AND over XOR shares (equivalently, multiplication over Z2 ), • B2A/A2B conversions (when used), • and backend primitive families, in the standard “one-key privacy” sense: a single party’s key (and all local evaluations on any polynomial number of inputs) leaks nothing about instance parameters beyond public shape. These are standard assumptions in the preprocessing MPC literature and in FSS-based secure inference systems. M.4. Proof of Semi-Honest Security for Compiled Scalar Gates Theorem M.1 (Gate-level semi-honest security). Fix a gate type τ and consider the compiled gate protocol for one instance. Under the assumptions in Appendix M.3, for each b ∈ {0, 1} there exists a PPT simulator Simb such that for any input distribution on x and any auxiliary input, the real view of a semi-honest adversary corrupting Pb is computationally indistinguishable from the simulator’s output given only: (the corrupted party’s input share, its output shares, Lshape (τ ), Lonline ). Equivalently, the protocol securely realizes FτL in the semi-honest preprocessing model. Proof. We construct Simb by composing simulators for each subprotocol. The simulator is additionally given the corrupted party’s output shares, which are part of the adversary’s view in both the real and ideal executions. Preprocessing Simulation. All preprocessing material (masks, backend interface keys, Beaver/AND/B2A correlations) is input-independent. Therefore, Simb samples the corrupted party’s preprocessing view from the correct distribution conditioned on Lshape (τ ) (which fixes public key shapes). This is feasible by the assumed security of backend primitive instances (keys reveal no instance parameters beyond shape) and by standard definitions of preprocessed correlations (Beaver/AND/B2A shares are uniformly random subject to correctness). Online Simulation: Masked Opening of x̂. In the real protocol, the transcript reveals x̂ = x + rin , which is uniform over R. In the ideal world, x̂ is provided by Lonline . The simulator programs the shares-to-masked opening messages consistently with this leaked x̂ (using the fact that the opened value is public and the honest party’s share message is not otherwise constrained). This is the standard simulation for openings of one-time pads. Online Simulation: Non-Interactive Backend Interface Evaluations. Backend interface evaluations are local: they produce no interaction transcript. The corrupted party’s internal state includes its local outputs, which are deterministic functions of its key and the public input x̂. Since backend interface keys are simulated or sampled to be indistinguishable from real keys of the same shape, the distribution of the corrupted party’s entire local evaluation behavior is indistinguishable. Online Simulation: Beaver/AND/B2A/A2B Subprotocols. All interaction beyond revealing masked wires occurs inside standard secure subprotocols: Beaver multiplications open masked differences (e, f ), Boolean AND opens Z2 -masked values, and B2A/A2B opens standard masked values. By the assumed semi-honest security of these subprotocols, their transcripts are simulatable given only their public openings and the corrupted party’s local inputs/outputs to those subprotocol calls. Since the overall functionality reveals only masked wires and the protocol does not reveal intermediate unmasked secrets, the simulator can invoke the corresponding subprotocol simulators to generate indistinguishable transcripts. Composition. Finally, the protocol is a sequential composition of the above components. Standard composition theorems for semi-honest secure protocols imply that the concatenation of the simulated views is indistinguishable from the real view, completing the proof. M.5. Security and Correctness for Compiled Gates Proof Sketch. Compiled gates instantiate the compiled gate protocol. They then apply a deterministic post-processing map Φτ using only secure share-based subprotocols. Correctness follows from Theorem 4.6 and the correctness of the post-processing circuit. Security follows from Theorem M.1 and sequential composition. Optional masked outputs satisfy ŷ = y + rout . They reveal no information about y since rout is fresh uniform. 25
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
N. Example: A Complete (F, Φ) Pair This appendix gives a fully concrete specification+post-processing example that can be read independently. The goal is: we pick the smallest operator that (i) has a genuine piecewise structure, (ii) produces at least one predicate bit, and (iii) uses a nontrivial post-processing circuit Φ. For simplicity we present a signed ReLU gate; real operators (e.g., spline-approximated GELU/SiLU) follow the same pattern with more intervals and higher-degree polynomials. Target Scalar Gate. Fix word size n and let R = Z2n . Interpret An as two’s-complement signed fixed-point with any number of fractional bits; the fractional metadata is irrelevant for this example because the map is homogeneous. Define the scalar gate GReLU : An → An × B, GReLU (x) = max(x, 0), MSB(x) , where MSB(x) = 1 iff x is negative in two’s complement. Operator Specification Fcoeff . Instead of directly outputting max(x, 0) as a polynomial piece, we show how to use Φ by having the operator specification output coefficients for an affine form. Let N = 2n and use the canonical representative rep(x) ∈ {0, . . . , N − 1}. Consider the partition 0 = α0 < α1 < α2 = N,
α1 = N/2,
which corresponds to non-negative vs. negative signed values. Thus I0 = [0, N/2) are non-negative representatives and I1 = [N/2, N ) are negative representatives. We define an operator specification Fcoeff : An → A2n × B with r = 2 arithmetic outputs, the affine coefficients a, b ∈ R and ℓ = 1 Boolean output (the sign bit z). All arithmetic pieces are degree-0 polynomials: P0 (x) = (a, b) = (1, 0),
P1 (x) = (a, b) = (0, 0).
For the Boolean output we use the primitive predicate MSB(x): B0 (x) = B1 (x) = MSB(x). In words: Fcoeff (x) returns the pair (a, b) such that a · x + b = max(x, 0), together with z = MSB(x). Post-Processing Circuit ΦReLU . Let ΦReLU take as input: (i) additive shares of (a, b) from Fcoeff (x), (ii) an XOR-sharing ⟨z⟩ of z = MSB(x), (iii) additive shares of x (derived from a public masked opening), and return (y, z) where y = a · x + b ∈ R. Concretely, ΦReLU uses one Beaver multiplication for a · x and then local addition of b. The Boolean output z is simply forwarded. Compiled to Two Backend Calls. Let preprocessing sample a uniform mask rin ∈ R and distribute Jrin K. Online evaluation will open the public masked value x̂ = x + rin mod N using Protocol 1. Interval lookup instance Πcoeff . There are m = 2 original intervals, so we allocate M = min(m + 1, N ) = 3 intervals after padding (Protocol 3). The translated starts are s0 = (α0 + rin ) mod N = rin ,
s1 = (α1 + rin ) mod N = (rin + N/2) mod N.
Sorting {s0 , s1 } yields (β0 , β1 ) and an order vector π. Following Protocol 3, we construct boundaries B = (B0 , . . . , BM ) and an index list ord ∈ {0, 1}M that may duplicate one payload so that the public lookup shape (M, p) is independent of the sampled mask. The payload dimension is p = 2 and each payload is vj = (aordj , bordj ) ∈ R2 . 26
FuseFSS: Efficient Secure LLM Inference with Function Secret Sharing
Evaluating Πcoeff on the public x̂ returns additive shares of the correct (a, b) without revealing the active interval. Packed-comparison instance Πpred . To compute z = MSB(x), we can use MSB(x) = ¬CN/2 (x), where Cβ (x) = I[x<β] . Applying Lemma 4.3 with β = N/2 yields CN/2 (x) = I[x̂<θ] ⊕ I[x̂<rin ] ⊕ w,
θ = (rin + N/2) mod N,
where w = I[rin +N/2≥N ] is a carry bit that depends only on the mask and is therefore provided as a secret-shared preprocessing constant. Thus the packed-comparison query list contains the two atoms I[x̂<θ] and I[x̂<rin ] (both width k = n). Parties locally combine these XOR-shared atoms with ⟨w⟩ to obtain ⟨CN/2 (x)⟩, and then locally negate to get ⟨z⟩ = ⟨MSB(x)⟩. End-to-End Online Evaluation. Given an input JxK, parties: (i) open x̂ = x + rin (Protocol 1); (ii) locally evaluate the two backend instances on x̂ to obtain ⟨z⟩ and J(a, b)K; (iii) locally derive JxK from x̂ and Jrin K (Protocol 2); (iv) run ΦReLU to compute JyK = a · x + b and output (JyK, ⟨z⟩). Remark: Extending to a Small GELU Example. To specify a spline-approximated GELU, one would keep the same structure but set r = 1 and choose m > 2 intervals with degree-d polynomials Pi (x). Then Πcoeff returns the active interval’s coefficient vector and the post-processing runs Horner evaluation (Theorem 4.6).
O. Complexity Accounting for a Compiled Gate Let T be the emitted number of primitive masked comparison atoms in Πpred after any specification-only syntactic deduplication and optional padding, so that T depends only on the public operator specification and metadata. Let M and p be the interval count and payload dimension of Πcoeff under the padding convention, where M := min(m + 1, 2n ) for an operator specification with m original intervals (Proposition I.3). Let MA be the number of ring multiplications (implemented via Beaver triples) performed in post-processing (Horner evaluation plus any extra multiplications in Φ; cf. Theorem 4.6), let MB be the number of Boolean ANDs, and let Gmix be the number of mixed-domain conversions. A compiled gate instance uses: • One packed-comparison primitive instance with output length T (or omitted if T = 0), • One interval-lookup primitive instance with (M, p) (or omitted if the arithmetic payload is interval-independent, e.g., the operator specification has a single interval), • MA Beaver multiplications over R, • MB preprocessed Boolean ANDs over Z2 , • Gmix mixed-domain conversions (B2A/A2B). This accounting is backend-agnostic: concrete preprocessing size/time follows by instantiating the primitive and preprocessing costs of the chosen backend interface and triple-generation mechanisms.
27