AES encryption using MPC SPDZ protocol

Question

I'm reading the article about SPDZ protocol for secure multiparty computation (and also improvements for offline phase like MASCOT).

However I'm thinking about practical application of SPDZ for AES encryption/decryption.

I have the following assumptions: There are 3 parties $P_1, P_2, P_3$ from which $P_2, P_3$ each has a share to compute AES encryption/decryption, so no party should have knowledge of the whole clear-text AES key. Party $P_1$ has a clear-text, which should be encrypted, and do not want to share its value either.

I believe that I understand the setup correctly. Now, using the SPDZ, there is an offline preparation protocol which should distribute across parties shared secret key $[[\alpha]]$, triples $(\langle a \rangle, \langle b \rangle, \langle c \rangle)$, and pairs of random values $\langle r \rangle$, $[[r]]$. These are distributed to all parties using public key $pk$ and verified using $\Pi_{ZKPoPK}$.

Then in online protocol parties share their inputs $x_i$. And SPDZ can perform addition and multiplication on circuit using shared secrets.

How can the AES encryption/decryption computation be done in MPC? What is the secret AES key and how can the key be shared between 2 parties and have a different party join in the protocol with the plaintext? Should parties $P_2,P_3$ share the key using SPDZ and then party $P_3$ will use its share to see the real clear-text and cipher-text?

I would like to know it from practical point of view, there are many theoretical articles, I do not understand how to implement it in real world.

Answer 1

Ok, so the question is how is AES implemented within SPDZ. I'm going to explain the big picture and then whoever is interested in details should check out the original paper here or the code here.

Let's start with the setup: running the AES algorithm requires a 128-bit key $k$ and a 128-bit message $m$. In the generic SPDZ setting $k$ and $m$ are going to be additive shared across the $n$ parties: $k=\bigoplus_{i=1}^n k_i, m=\bigoplus_{i=1}^n m_i$. Namely no one knows the key or the message but they can reconstruct $k$ and $m$ if all parties broadcast their shares.

In your case $P_1$ sends random shares of $m_2, m_3$ to $P_2$ and $P_3$ and fixes $m_1 = m \oplus m_2 \oplus m_3$. Then $P_1$ can set its $k$ share as $k_1 = 0$ since the other parties $P_2, P_3$ can reconstruct the key using $k_2$ and $k_3$.

Next question that comes in mind is in which field must the shares live in. Since the cleartext computation of AES is performed on blocks of size $8$ the authors choose to have $k$ and $m$ split into $\frac{128}{8}$ blocks of $8$ bits. Now parse each share $k_i,m_i$ as $16$ blocks of $8$ bits each where each block lives in $\mathbb{F}_{2^{40}}$.

It's good to keep in mind that on secret data $[x]$:

• Linear operations: $z = [x] \oplus [y]$ or $z = [x] \cdot y$ are for free - just local additions or multiplications by scalars.

• Multiplications: $[z] = [x] \cdot [y]$ require special pre-processing data as Beaver triples and involves some data sent around between the parties.

Assume there is an embedding $f$ which converts $x \in \mathbb{F}_{2^8}$ to the same element $x$ but in a different field: $\mathbb{F}_{2^{40}}$. Similar for $f^{-1} : \mathbb{F}_{2^{40}} \mapsto \mathbb{F}_{2^8}$. If we have an embedded key and a message: $[f(k)], [f(m)]$ the AES algorithm in MPC looks like this:

• ShiftRows, MixColumns, AddRoundKey come for free since they involve additions or multiplications by public scalars - check wiki.
• SubBytes where we do $\mathsf{SBox}(x)$ involves first extracting the embedded bits from $\mathbb{F}_{2^{40}}$ by applying $[y] = f^{-1}([x])$, perform $[y^{2^k}]$ by bit-decomposing and shifting bits and then apply the embedding again on $f([y^{2^k}])$ to be able to multiply the squares in $\mathbb{F}_{2^{40}}$.

More details on: given a shared input $[x]$ how can we compute a share of $[\mathsf{Sbox}(x)]$? One can expand the Sbox in polynomial form and compute $[x] \mapsto [x^{254}]$ using Section 4.2 in the paper. To perform $[x] \mapsto [x^2]$ we can bit-decompose $[x]$ and then just move secret bits around to obtain the squaring $[x^2]$ - think how squaring happens in a characteristic two field.

All nice and neat: we can perform squarings (almost) for free by doing a bit-decomposition. Now the troublesome part comes when we need to multiply squarings according to section 4.2 such as $[x^2] \cdot [x^4]$. This is where the embedding $f$ comes into play to allow us to multiply $\mathbb{F}_{2^8}$ elements inside a bigger field $\mathbb{F}_{2^{40}}$.

You might ask: What's the magic that tells us how to construct an embedding $f$? Well, basically just a bit-decomposition and some bit shuffling.

I have skipped some details but I hope you get the gist: embed data to multiply stuff in a larger field, invert the embedding to obtain cheap squarings (or any bit-wise manipulation easier). The implementation uses the approach I told you here with some extra optimizations for switching back and forth between embeddings.