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.

  • $\begingroup$ How were the shares of the key generated by $P_2$ and $P_3$? Does $P_1$ want to participate in the evaulation of AES or are only the other two involved in that? $\endgroup$
    – mikeazo
    Jul 30 '18 at 16:39
  • $\begingroup$ I do not know, I am trying to understand how it works. I believe $P_2$ and $P_3$ can both generate a share of AES key, that will be used in protocol, and will be kept secret by both parties. $P_1$ would like to ask for example to encrypt some data using the AES key but other parties should not be aware of clear-text that is going to be encrypted. I am trying to understand the fundamentals, including what parts in protocol represents AES key or its shares and how it is used to provide result back to $P_1$. $\endgroup$ Jul 30 '18 at 17:26
  • $\begingroup$ I can explain to you how AES was implemented in the SPDZ engine although it's not clear that this is what you want from the question. Can you clarify it a bit? $\endgroup$
    – Dragos
    Aug 2 '18 at 17:35
  • $\begingroup$ I would like to see the real world explanation. What is exchanged, how are AES key combined in protocol, who will generate what values, etc. I think that the offline protocol just prepares some values and online works with real data to produce result. I would like to see how the party will get the result of encryption for example without revealing the clear text. $\endgroup$ Aug 2 '18 at 19:53
  • $\begingroup$ 'Real world explanation' is a bit vague. I guess you refer to explaining what was the process behind this chunk of code: github.com/bristolcrypto/SPDZ-2/blob/master/Programs/Source/… $\endgroup$
    – Dragos
    Aug 2 '18 at 21:26

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.