Paper 2024/1317

MAESTRO: Multi-party AES using Lookup Tables

Abstract

Secure multi-party computation (MPC) enables multiple distrusting parties to jointly compute a function while keeping their inputs private. Computing the AES block cipher in MPC, where the key and/or the input are secret-shared among the parties is important for various applications, particularly threshold cryptography. In this work, we propose a family of dedicated, high-performance MPC protocols to compute the non-linear S-box part of AES in the honest majority setting. Our protocols come in both semi-honest and maliciously secure variants. The core technique is a combination of lookup table protocols based on random one-hot vectors and the decomposition of finite field inversion in $GF(2^8)$ into multiplications and inversion in the smaller field $GF(2^4)$, taking inspiration from ideas used for hardware implementations of AES. We also apply and improve the analysis of a batch verification technique for checking inner products with logarithmic communication. This allows us to obtain malicious security with almost no communication overhead, and we use it to obtain new, secure table lookup protocols with only $O(\sqrt{N})$ communication for a table of size $N$, which may be useful in other applications. Our protocols have different trade-offs, such as having a similar round complexity as previous state-of-the-art but $37\%$ lower bandwidth costs, or having $27\%$ fewer rounds and $16\%$ lower bandwidth costs. An experimental evaluation in various network conditions using three party replicated secret sharing shows improvements in throughput between $23\%$ and $27\%$ in the semi-honest setting. For malicious security, we improve throughput by $46\%$ and $270\%$ in LAN and by up to $453\%$ in WAN due to a new multiplication verification protocol.