Paper 2024/305

Single-Input Functionality against a Dishonest Majority: Practical and Round-Optimal

Abstract

In this work, we focus on Single-Input Functionality (SIF), which can be viewed as a special case of MPC. In a SIF, only one distinguished party called the dealer holds a private input. SIF allows the dealer to perform a computation task with other parties without revealing any additional information about the private input. SIF has diverse applications, including multiple-verifier zero-knowledge, and verifiable relation sharing. As our main contribution, we propose the first 1-round SIF protocol against a dishonest majority in the preprocessing model, which is highly efficient. The prior works either require at least 2-round online communication (Yang and Wang, Asiacrypt 2022; Baum et al., CCS 2022; Zhou et al., Euro SP 2024) or are only feasibility results (Lepinski et al., TCC 2005; Applebaum et al., Crypto 2022). We show the necessity of using the broadcast channels, by formally proving that 1-round SIF is impossible to achieve in the preprocessing model, if there are no broadcast channels available. We implement our protocol and conduct extensive experiments to illustrate the practical efficiency of our protocol. As our side product, we extend the subfield Vector Oblivious Linear Evaluation (sVOLE) into the multi-party setting, and propose a new primitive called multiple-verifier sVOLE, which may be of independent interest.

Note: In the version of June 30th, 2024, we add a new impossibility result, which is put in Section 5. More concretely, we prove that 1-round UC-secure SIF/VRS/MVZK protocol is impossible to achieve in the preprocessing model, if there are no broadcast channels available. Therefore, we show that broadcast channels are necessary for building 1-round SIF/VRS/MVZK protocol.