Paper 2025/096

Simultaneous-Message and Succinct Secure Computation

Abstract

We put forth and instantiate a new primitive we call simultaneous-message and succinct (SMS) secure computation. An SMS scheme enables a minimal communication pattern for secure computation in the following scenario: Alice has a large private input X, Bob has a small private input y, and Charlie wants to learn $$ for some public function $$. Given a common reference string (CRS) setup phase, an SMS scheme for a function f is instantiated with two parties holding inputs $$ and $$, and has the following structure: - The parties simultaneously exchange a single message. - Communication is succinct, scaling sublinearly in the size of $$ and the output $$. - Without further interaction, the parties can locally derive additive secret shares of $$. Indeed, Alice and Bob simultaneously send each other a message using the CRS and their private inputs. Using the transcript and their private state, the parties locally derive additive secret shares of $$, which they can send to Charlie. As such, an SMS scheme incurs a communication cost to Charlie that is only twice that of the function output length. Importantly, the size of Alice’s message does not grow with the size of her input $$, and both Alice’s and Bob’s first-round messages grow sublinearly in the size of the output. Additionally, Alice’s or Bob’s view provides no information about the other party’s input besides the output of $$, even if colluding with Charlie. We obtain the following results: - Assuming Learning With Errors (LWE), we build an SMS scheme supporting evaluation of depth-$$ circuits, where Alice's message is of size $$· poly(λ, d), Bob's message is of size $$ · poly(λ, d), and λ is the security parameter. We can further extend this to support all functions by assuming the circular security of LWE. - Assuming sub-exponentially secure indistinguishability obfuscation, in conjunction with other standard assumptions, we build an SMS scheme supporting arbitrary polynomial-sized batch functions of the form $$, for $$. The size of Alice's and Bob's messages in this construction is poly(λ) and poly(λ, |f|, log L), respectively. We show that SMS schemes have several immediate applications. An SMS scheme gives: - A direct construction of trapdoor hash functions (TDH) (Döttling et al., Crypto'19) for the same class of functions as the one supported by the SMS scheme. - A simple and generic compiler for obtaining compact, rate-1 fully homomorphic encryption (FHE) from any non-compact FHE scheme. - A simple and generic compiler for obtaining correlation-intractable (CI) hash functions that are secure against all efficiently-searchable relations. In turn, under the LWE assumption, we obtain the first construction of TDH for all functions and generic approaches for obtaining rate-1 FHE and CI hashing. We also show that our iO-based construction gives an alternative approach for two-round secure computation with communication succinctness in the output length (Hubáček and Wichs, ITCS'15).

Note: Added publication information.