TurboPack: Honest Majority MPC with Constant Online Communication

In this work we present a novel actively secure dishonest majority MPC protocol, SUPERPACK, whose efficiency improves as the number of honest parties increases. Concretely, let 0 < ϵ < 1/2 and consider an adversary that corrupts t < n(1 -ϵ) out of n parties. SUPERPACK requires 6/ϵ field elements of online communication per multiplication gate across all parties, assuming circuit-dependent preprocessing, and 10/ϵ assuming circuit-independent preprocessing. In contrast, most of the previous works such as SPDZ (Damgård et al, ESORICS 2013) and its derivatives perform the same regardless of whether there is only one honest party or a constant (non-majority) fraction of honest parties. A notable exception is due to Goyal et al (CRYPTO 2022), which achieves 58/ϵ + 96/ϵ 2 field elements assuming circuit-independent preprocessing. Our work improves this result substantially by a factor of at least 25 in the circuit-independent preprocessing model. Practically, we also compare our work with the best concretely efficient online protocol Turbospeedz (Ben-Efraim et al, ACNS 2019), which achieves 2(1 -ϵ)n field elements per multiplication gate among all parties. Our online protocol improves over Turbospeedz as n grows, and as ϵ approaches 1/2. For example, if there are 90% corruptions (ϵ = 0.1), with n = 50 our online protocol is 1.5× better than Turbospeedz and with n = 100 this factor is 3×, but for 70% corruptions (ϵ = 0.3) with n = 50 our online protocol is 3.5× better, and for n = 100 this factor is 7×. Our circuit-dependent preprocessing can be instantiated from OLE/VOLE. The amount of OLE/VOLE correlations required in our work is a factor of ≈ ϵn/2 smaller than these required by Le Mans (Rachuri and Scholl, CRYPTO 2022) leveraged to instantiate the preprocessing of Turbospeedz. Our dishonest majority protocol relies on packed secret-sharing and leverages ideas from the honest majority TURBOPACK (Escudero et al, CCS 2022) protocol to achieve concrete efficiency for any circuit topology, not only SIMD. We implement both SUPERPACK and Turbospeedz and verify with experimental results that our approach indeed leads to more competitive runtimes in distributed environments with a moderately large number of parties.