Improving the Efficiency of AES Protocols in Multi-Party Computation

The AES is a standardized symmetric block cipher, whose efficiency has been studied widely. This has resulted in very efficient software and hardware implementations of AES, which allow for the encryption of millions of blocks per second. However, AES was not designed with Multi-Party Computation in mind. Though there are many real-world applications of MPC requiring block ciphers, standard ciphers such as AES are far from being efficient for real-world applications of MPC. In this paper, we study how to improve the efficiency of AES modes of operation in the actively secure MPC setting with dishonest majority with precomputation as put forward by SPDZ and its variants. We propose two new protocols. The first one is aimed at improving the efficiency of the Sbox computation, the only non-linear layer in the AES. In particular, we use an (equally secure) inverse Sbox computation instead of the standard forward Sbox. The second protocol improves on the overall AES computation by optimizing the off-line phase and computing special (Beaver)-tuples specifically designed to improve the performance of the Sbox AES computation. Our proposals, result in an overall improvement of 3.33. The on-line phase of the protocols is fully implemented using the MP-SPDZ framework.