Paper 2026/1697

Actively Secure Two-Party Function Secret Sharing with Dynamic Cross-Phase Verification

Abstract

Function secret sharing (FSS) gives two parties succinct keys whose local evaluations add up to a hidden function value. Removing the dealer is the natural next step for preprocessing-based secure computation, but malicious security then requires more than checking a finished key: the generation transcript, the function the key actually computes, and every released evaluation share must all be bound to one execution. We call this the cross-phase binding problem, and we solve it. We present VeriFSS, a dealer-free two-party FSS scheme with active security, proved in the standard simulation-based framework against one static malicious corruption. The construction rests on a two-plane key: the distributed generator produces a key for the paired function $x\mapsto(f_\theta(x),\Lambda f_\theta(x))$, where $\Lambda$ is a secret global authentication scalar. The second plane makes every local evaluation an authenticated sharing for free, which yields online report binding without vector commitments, extractable hashing, or per-point interaction. It also supplies the ingredient the audit was missing: we prove a moment-fidelity lemma showing that a corrupted party cannot misreport the full-domain moments of its own sealed key except with probability $3/|E|$ over the challenge set $E$, and a shape-identification lemma showing that three moment equations pin a point function down exactly, with error $2n/|E|$ over any field. The proof isolates the coefficient of the square monomial in the support polynomial and is therefore characteristic-free; in characteristic two an odd-size equal-weight support defeats the support equation on its own, and we show the position equation takes over. A discrete-derivative reduction carries both lemmas to comparison functions, and a Galois-ring variant covers fixed-point payloads over $\mathbb{Z}_{2^k}$ by a $2$-adic valuation argument, so no non-additive lift into a binary field is ever needed. Generation costs two rounds and five field elements per party per level; certification adds $O(n)$ elements with no dependence on the domain size, and a dynamic cross-domain aggregation certifies arbitrarily many heterogeneous instances under one challenge and a constant number of rounds. We then lift the general-purpose FSS gates of Boyle et al. (EUROCRYPT 2021): every gate that is a public affine post-processing of a constant number of DPF/DCF evaluations---interval containment, splines, ReLU, arithmetic shift, bit decomposition, zero test, table lookup---inherits active security at no additional online cost. We evaluate our construction using a C++ implementation that certifies keys over $\mathbb{F}_{p^2}$ ($p=2^{61}-1$) and $\mathrm{GF}(2^{128})$, realises the gate layer, and agrees bit‑for‑bit on every exported test vector. A certified DPF key at $n=16$ takes $5.7$ ms to generate and $3.3$ ms to certify. Certified DPF keys are $5.4\%$ larger than the semi-honest dealer-free baseline at $n=16$, and aggregated certification traffic converges to $1{,}282$ bytes per instance while the round count stays constant. Replaying the certified execution between two processes over TCP shows what that constancy is worth: at a $50$ ms round trip a session takes $1.15$ s, and the figure is unchanged whether one key or sixty-four are certified together, so wide-area certification of a whole preprocessing session is latency-bound by a single key. A campaign of $1{,}400$ injected generation deviations plus shape, moment and release forgeries is rejected without exception in six of seven deviation classes; the seventh is rejected in exactly the $105$ of $200$ trials in which the attacked index bit is one, which is a quantitatively exact confirmation of the single-bit selective-failure predicate that we model explicitly in the ideal functionality, matching the leakage profile of the best known actively secure distributed DPF.