Paper 2025/096

Simultaneous-Message and Succinct Secure Computation

Elette Boyle, NTT Research, Reichman University
Abhishek Jain, NTT Research, Johns Hopkins University
Sacha Servan-Schreiber, Massachusetts Institute of Technology
Akshayaram Srinivasan, University of Toronto
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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2025
Keywords
secure computationmpcsuccinct communicationtrapdoor hashcorrelationintractablerate-1fhelweobfuscation
Contact author(s)
elette boyle @ ntt-research com
abhishek jain @ ntt-research com
3s @ mit edu
akshayaram @ cs toronto edu
History
2025-02-24: last of 3 revisions
2025-01-21: received
See all versions
Short URL
https://ia.cr/2025/096
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/096,
      author = {Elette Boyle and Abhishek Jain and Sacha Servan-Schreiber and Akshayaram Srinivasan},
      title = {Simultaneous-Message and Succinct Secure Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/096},
      year = {2025},
      url = {https://eprint.iacr.org/2025/096}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.