Paper 2023/513

Sublinear Secure Computation from New Assumptions

Elette Boyle, Reichman University, NTT Research
Geoffroy Couteau, Université Paris Cité, CNRS, IRIF
Pierre Meyer, Reichman University, Université Paris Cité, CNRS, IRIF

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function. For certain functions, such as Private Information Retrieval (PIR), this question extends to even sublinearity in the input size. We develop new techniques expanding the set of computational assumptions for sublinear communication in both settings: 1) [Circuit size] We present sublinear-communication protocols for secure evaluation of general layered circuits, given any 2-round rate-1 batch oblivious transfer (OT) protocol with a particular ``decomposability'' property. In particular, this condition can be shown to hold for the recent batch OT protocols of (Brakerski et al. Eurocrypt 2022), in turn yielding a new sublinear secure computation feasibility result: from Quadratic Residuosity (QR) together with polynomial-noise-rate Learning Parity with Noise (LPN). Our approach constitutes a departure from existing paths toward sublinear secure computation, all based on fully homomorphic encryption or homomorphic secret sharing. 2) [Input size.] We construct single-server PIR based on the Computational Diffie-Hellman (CDH) assumption, with polylogarithmic communication in the database input size $n$. Previous constructions from CDH required communication $\Omega(n)$. In hindsight, our construction comprises of a relatively simple combination of existing tools from the literature.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in TCC 2022
FoundationsPrivate Information RetrievalSecure Multiparty Computation
Contact author(s)
eboyle @ alum mit edu
couteau @ irif fr
pierre meyer @ irif fr
2023-04-10: approved
2023-04-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Geoffroy Couteau and Pierre Meyer},
      title = {Sublinear Secure Computation from New Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/513},
      year = {2023},
      doi = {10.1007/978-3-031-22365-5_5},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.