Paper 2026/214

Cavern: Efficient Honest-Majority Maliciously Secure $(2+1)$-PC for $\mathbb{Z}_{2^n}$ via DPF

Abstract

We introduce Cavern, a new maliciously secure $(2+1)$-PC protocol for efficient piecewise polynomial (i.e., spline) evaluation on additively secret shared inputs over the ring $\mathbb{Z}_{2^n}$ in the preprocessing model, where parties obtain input-independent correlated randomness in an offline phase, which they then use to run an efficient protocol in the input-dependent online phase. This $(2+1)$ party structure can alternatively be instantiated between two parties with the aid of a (possibly untrusted) dealer. At the technical level, we introduce a new primitive called verifiable incremental distributed point function (VIDPF) and build on a novel combination of the VIDPF and authenticated secret sharing, providing an efficient method to detect the malicious behavior of the dealer or one of the parties. We implement and benchmark our protocol against the state-of-the-art semi-honest protocol Grotto (CCS 2023), and the trusted-dealer-based maliciously secure 2PC protocol Shark (S&P 2025). The results indicate that Cavern only imposes a constant factor overhead on the top of Grotto and Shark, while providing stronger security guarantees.