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.

1. 1.

   See [16] for comparisons of various implementations.

2. 2.

   This approach has been implemented in the MP-SPDZ library, which we have used for our implementation.

3. 3.

   If stored, then it requires storage per player and the amount is equal to the amount transferred during the computation. If the protocol is “on-the-fly”, then no storage is required but the pre-computed data has to be available realtime and on request when needed. In practice, it is likely that storage will be required since the offline phase is much slower than the online phase.

4. 4.

   A more detailed explaination is given in Sect. 4.2.

5. 5.

   Excluding side-channel attacks attacks.

Authors and Affiliations

1. Robert Bosch LLC — Research and Technology Center, Pittsburgh, USA

   F. Betül Durak & Jorge Guajardo

Corresponding authors

Correspondence to F. Betül Durak or Jorge Guajardo .

Editors and Affiliations

1. University of Illinois at Urbana-Champaign, Urbana, IL, USA

   Nikita Borisov

2. KU Leuven, Leuven, Belgium

   Claudia Diaz

6 Appendix

1.1 6.1 \( \textsf {AES}\text {-}\mathsf{LT}\) with Masked Table [18]

In a table look-up based implementation of the AES standard, the table representing the Sbox is publicly available. Such look-ups happen securely by the key owner who knows all the internal states.^{Footnote 5} On the other hand, in MPC, the internal states as well as the secret key are secrets which are distributed among participants and therefore it is not possible to perform a table look-up based on secret state information. The idea in [18] is to generate a pair \(( x, \textsf {MaskedTable})\) such that \(x \oplus \textsf {MaskedTable} = \textsf {Sbox}\) in the offline phase and distribute it as secret shares to each participant: \(( \llbracket x \rrbracket , \llbracket \textsf {MaskedTable} \rrbracket )\). Therefore, in MPC, instead of looking up a public entry with a secret internal state, we look up a secret table with a (public) masked internal state. The \(\textsf {MaskedTable}\) generation is described in [18]. We observe that every single Sbox computation requires one pair \((\llbracket x \rrbracket , \llbracket \textsf {MaskedTable} \rrbracket )\). Thus, even though the online phase is a lot faster than other methods, it requires a lot more data to be communicated and stored from the offline phase. The online computations of a single Sbox in \( \textsf {AES}\text {-}\mathsf{LT}\) [18] is shown in Protocol 7.

Offline Phase. For 10 rounds and 16 bytes per round, Protocol 7 must prepare 160 \(\textsf {MaskedTable}\) for a block of AES requiring 48 KBytes of communication during the offline phase [18]. Communicating 160 tables for the online phase requires 410 KBytes per party.

Online Phase. The online phase requirements are as follows:

• Storage: the protocol needs one masked table per Sbox operation. Each table has 256 \( \mathsf {GF}(2^{40})\)-elements. Thus, to process one full AES block, 410 KBytes of storage are required per participant.

• Round trip: Per Sbox, we need one round trip of communication between players for a reveal. For the whole AES 160 rounds are required.

• Communication: Per Sbox, one reveal operation is performed, which requires 10 bytes of communication. Thus, 1600 bytes of communication needed in total for a full AES block.

1.2 6.2 Details of \(\textsf {BDEmbed}\)

In this section, we describe the bit decomposition of an embedded value in MP-SPDZ which is important to understand our optimization techniques given in 4.3. The following algorithm is used to compute \(\textsf {BDEmbed}\) of an embedded secret input \(\llbracket x \rrbracket \). This computation is run in Step 2 in Protocol 3. In total, Protocol 3 requires 13 rounds of communication. This is summarized in Table 4.

1. 1.

   Take a secret pair \((\langle a \rangle , \langle a' \rangle )\) where \(\langle a' \rangle \) is the output of \(\textsf {InverseBD}\)\(\textsf {Embedding}(a)\) computed during the offline phase.

2. 2.

   Compute \(\langle \bar{x} \rangle = \langle x \rangle + \langle a \rangle \) and reveal \(\bar{x}\).

3. 3.

   Compute the bits of the clear value \(\bar{x}\). Call it \(x'\).

4. 4.

   Compute \(\langle y' \rangle = x' + \langle a' \rangle \)

5. 5.

   Return \(\langle y \rangle \) which is the composition of \(\langle y' \rangle \).

1.3 6.3 Regarding The Embedding from \( \mathsf {GF}(2^8)\) to \( \mathsf {GF}(2^{40})\)

We further clarify the notation used in Sect. 4 and some aspects of the embedding used, originally introduced in [11]. As previously mentioned, given an element \(x \in \mathsf {GF}(2^8)\), one can map this to an element in \( \mathsf {GF}(2^{40}) \cong \mathsf {GF}((2^8)^5)\), using the irreducible polynomial \(Q(X) = X^{40} + X^{20} + X^{15} + X^{10} +1\). Thus, \(x \in \mathsf {GF}(2^8)\) gets mapped to the element \(X^5+1 \in \mathsf {GF}(2^{40})\). We observe the following equivalences:

It has been observed [11, 17] that this representation can be used to extract the \( \mathsf {GF}(2^8)\) element representation by extracting indeces that are a multiple of 5 in the corresponding \( \mathsf {GF}(2^{40})\) representation. In Sect. 4, we have abused notation and written \(\mathbf {0x20}_{16} = (0010\,0000)_2\) to mean \(X^5 \in \mathsf {GF}(2^{40})\) (as the 5th bit of \(\mathbf {0x20}_{16}\) is set to 1).

Reprints and permissions

© 2021 International Financial Cryptography Association

Policies and ethics