We obtain the first construction of this primitive from an assumption that is not known to support general homomorphic operations.
In the first step, we construct a two-round MPC protocol in the silent pre-processing model (Boyle et al., Crypto 2019). Specifically, the parties engage in a computationally inexpensive setup procedure that generates some correlated random strings. Then, the parties commit to their inputs. Finally, each party sends a message depending on the function to be computed, and these messages can be decoded to obtain the output. Crucially, the complexity of the pre-processing phase and the input commitment phase do not grow with the size of the circuit to be computed. We call this multiparty silent NISC, generalizing the notion of two-party silent NISC of Boyle et al. (CCS 2019). We provide a construction of multiparty silent NISC from LPN in the random oracle model.
In the second step, we give a transformation that removes the pre-processing phase and use of random oracle from the previous protocol. This transformation additionally adds (unbounded) reusability of the first round message, giving the first construction of reusable two-round MPC from the LPN assumption. This step makes novel use of randomized encoding of circuits (Applebaum et al., FOCS 2004) and a variant of the ``tree of MPC messages" technique of Ananth et al. and Bartusek et al. (TCC 2020).
Category / Keywords: cryptographic protocols / MPC, LPN Date: received 9 Mar 2021 Contact author: bartusek james at gmail com,sanjamg@berkeley edu,akshayaram srinivasan@tifr res in,yinuo@berkeley edu Available format(s): PDF | BibTeX Citation Version: 20210311:184245 (All versions of this report) Short URL: ia.cr/2021/316