We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for \(n=2t\!+\!1\) players of which t are corrupt, that achieve guaranteed output delivery (GOD), and operate in a single initial round of broadcast ( \(\textsf{BC} \) ), followed by steps of asynchronous peer-to-peer (P2P) messages. The power of closely related “hybrid networks” was studied in [Fitzi-Nielsen, Disc’09], [BHN, Podc’10] and [Patra-Ravi, IEEE Tr. Inf. Theory’18]. The interest of such protocols is that they go at the actual speed of the network, and security is preserved under arbitrary network conditions (past the initial \(\textsf{BC} \) ). We first consider a bare bulletin-board PKI setup, and leverage recent advances in multi-key homomorphic encryption [BJMS, Asiacrypt’20], to state the feasibility of honest majority MPC with GOD in a tight 1- \(\textsf{BC} \) -then-1 single step of asynchronous P2P messages. We then consider efficiency. The only protocols adaptable to such a network model and setup are [BJMS, Asiacrypt’20], which does not scale well for many players, and [GLS, Crypto’15], which does not support input delegation from external resource-constrained owners (such as IoT devices or smartphones), limiting its practical use. Our main contribution is a generic design that enables MPC in 1 \(\textsf{BC} \) -then-asynchronous P2P. It operates over ciphertexts encrypted under a (threshold) single-key encryption scheme, resulting in the smallest sizes expectable and efficient evaluation. It can be implemented from any homomorphic encryption scheme built from linear maps (e.g., \(\textsf{GSW} \) , \(\textsf{CL} \) , ...). Our main building block is the squishing of the verifiable input sharing (“Share”), in parallel with the distributed key generation ( \(\textsf{DKG} \) ) in the single \(\textsf{BC} \) , followed by threshold encryption (“Shrink”) in one asynchronous step. Interestingly, it can be compiled into the first constant-round YOSO protocol in 1 \(\textsf{BC} \) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Share&Shrink: Efficient and Delegatable MPC in One Broadcast then Asynchrony

  • Antoine Urban,
  • Matthieu Rambaud

摘要

We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for \(n=2t\!+\!1\) players of which t are corrupt, that achieve guaranteed output delivery (GOD), and operate in a single initial round of broadcast ( \(\textsf{BC} \) ), followed by steps of asynchronous peer-to-peer (P2P) messages. The power of closely related “hybrid networks” was studied in [Fitzi-Nielsen, Disc’09], [BHN, Podc’10] and [Patra-Ravi, IEEE Tr. Inf. Theory’18]. The interest of such protocols is that they go at the actual speed of the network, and security is preserved under arbitrary network conditions (past the initial \(\textsf{BC} \) ). We first consider a bare bulletin-board PKI setup, and leverage recent advances in multi-key homomorphic encryption [BJMS, Asiacrypt’20], to state the feasibility of honest majority MPC with GOD in a tight 1- \(\textsf{BC} \) -then-1 single step of asynchronous P2P messages. We then consider efficiency. The only protocols adaptable to such a network model and setup are [BJMS, Asiacrypt’20], which does not scale well for many players, and [GLS, Crypto’15], which does not support input delegation from external resource-constrained owners (such as IoT devices or smartphones), limiting its practical use. Our main contribution is a generic design that enables MPC in 1 \(\textsf{BC} \) -then-asynchronous P2P. It operates over ciphertexts encrypted under a (threshold) single-key encryption scheme, resulting in the smallest sizes expectable and efficient evaluation. It can be implemented from any homomorphic encryption scheme built from linear maps (e.g., \(\textsf{GSW} \) , \(\textsf{CL} \) , ...). Our main building block is the squishing of the verifiable input sharing (“Share”), in parallel with the distributed key generation ( \(\textsf{DKG} \) ) in the single \(\textsf{BC} \) , followed by threshold encryption (“Shrink”) in one asynchronous step. Interestingly, it can be compiled into the first constant-round YOSO protocol in 1 \(\textsf{BC} \) .