Paper 2019/1095

Secure Computation with Preprocessing via Function Secret Sharing

Elette Boyle, Niv Gilboa, and Yuval Ishai


We propose a simple and powerful new approach for secure computation with input-independent preprocessing, building on the general tool of function secret sharing (FSS) and its efficient instantiations. Using this approach, we can make efficient use of correlated randomness to compute any type of gate, as long as a function class naturally corresponding to this gate admits an efficient FSS scheme. Our approach can be viewed as a generalization of the "TinyTable" protocol of Damgard et al. (Crypto 2017), where our generalized variant uses FSS to achieve exponential efficiency improvement for useful types of gates. By instantiating this general approach with efficient PRG-based FSS schemes of Boyle et al. (Eurocrypt 2015, CCS 2016), we can implement useful nonlinear gates for equality tests, integer comparison, bit-decomposition and more with optimal online communication and with a relatively small amount of correlated randomness. We also provide a unified and simplified view of several existing protocols in the preprocessing model via the FSS framework. Our positive results provide a useful tool for secure computation tasks that involve secure integer comparisons or conversions between arithmetic and binary representations. These arise in the contexts of approximating real-valued functions, machine-learning classification, and more. Finally, we study the necessity of the FSS machinery that we employ, in the simple context of secure string equality testing. First, we show that any "online-optimal" secure equality protocol implies an FSS scheme for point functions, which in turn implies one-way functions. Then, we show that information-theoretic secure equality protocols with relaxed optimality requirements would follow from the existence of big families of "matching vectors." This suggests that proving strong lower bounds on the efficiency of such protocols would be difficult.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2019
Secure computationcorrelated randomnessfunction secret sharing
Contact author(s)
eboyle @ alum mit edu
2020-05-02: last of 2 revisions
2019-09-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Niv Gilboa and Yuval Ishai},
      title = {Secure Computation with Preprocessing via Function Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1095},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.