Simultaneous-Message and Succinct Secure Computation: Reusable and Multiparty Protocols

Recently, Boyle, Jain, Servan-Schreiber, and Srinivasan (EUROCRYPT 2025) introduced the notion of simultaneous-message and succinct (SMS) secure computation. In an SMS protocol, after an initial sampling of a common reference string (CRS), two parties—Alice (with a large input) and Bob (with a small input)—can simultaneously exchange encodings of their private inputs and obtain additive shares of the output of a function evaluated over their inputs. The key requirement is succinctness: namely, the sizes of the CRS and each input encoding grow only polylogarithmically in the size of Alice's input and the function output. Boyle et al., and independently Abram, Malavolta, and Roy (STOC 2025), constructed SMS for all bounded-depth Boolean circuits from the plain learning with errors (LWE) assumption.

In this work, we extend the study of SMS along two new dimensions:

Reusable SMS: In this setting, the same input encodings can be reused to compute multiple functions.

Multiparty SMS: In the multiparty setting, we consider computations over one large input and multiple small inputs. Succinctness in this case means the size of the CRS and input encodings can grow with the total length of the small inputs (but polylogarithmically with the length of the long input and the size of the function output).

Assuming polynomial hardness of LWE (with a sub-exponential modulus-to-noise ratio), we construct reusable two-party SMS for all bounded-depth Boolean circuits with polylogarithmic communication. By additionally assuming indistinguishability obfuscation, we present a generic compiler from reusable two-party SMS to reusable multiparty SMS.

Our construction of reusable two-party SMS from LWE relies on a new "dual-use" technique where we reuse an LWE secret key between a lattice-based algebraic homomorphic MAC and a lattice-based homomorphic encryption scheme. This dual-use technique allows us to bootstrap a reusable SMS protocol for quadratic functions into one that supports arbitrary (bounded-depth) Boolean circuits. Along the way, we also show how to adapt a previous lattice-based algebraic homomorphic MAC based on ring LWE to obtain one based on the plain LWE assumption.