AES S-Box implementation: from a byte-by-byte to 2-bytes-by-2bytes? The S-Box in AES encryption is a byte substitution step. Is it possible to perform the substitution 2 bytes at a time, rather than 1 byte? What are the challenges/trade-offs involved?
First of all without any context going from a byte-by-byte substitution to a 2-bytes-by-2-bytes does not means anything as it is S-box implementation dependent.



I. Using Lookup tables (Boooooo!)

Example:
one could implement bit-by-bit $\neg$ as a lookup table:

neg[0] = 1
neg[1] = 0


And then go to a 2-bit-by-2-bit $\neg$ as such: 

neg[00] = 11
neg[01] = 10
neg[10] = 01
neg[11] = 00


This will effectively compute the requested result but as you can already see the space required is stupidly huge as it increases by with the square of the width of the S-box...

In the other hand one could also implement the $\neg$ using the assembly instruction, which allows to process at least 8 bitwise $\neg$ at the same time !

In other word: FORGET ABOUT TABLE LOOKUPS.



II. Using Computations (Meh)

For AES it is the same, you can either use a Sbox[x] look up or you can compute that value using the formula provided in the specifications (requiring an inverse over $\operatorname{GF}(2)[X]$). 

Also the advantage of such implementation is that you are less likely to be sensible to cache-timing attacks. You can then try to replicate these computations on multiple bytes at the same time.



III. Using Bit-slicing (Yeah!)

In order to go further than a 2-bytes-by-2-bytes substitution, you can have look at the AES hardware implementation. You will see gates and paths. You can replicate this circuit using normal instruction in a software.

in other word for a $\oplus$ gate:

     +-----+
x ---|     |
     | XOR |--- z 
y ---|     |
     +-----+


can be seen as : $\texttt{0000000x} \oplus \texttt{0000000y} \to \texttt{0000000z}$

Wait this is actually worse! you are doing one bit per instruction, this is going to be super slow!

Well you probably noticed that you have 7 bits left empty. And because you want to process multiple S-box (bytes) in parallel, all the hardware operations on each bytes will be the same. So we can take a bit of each of the 8 bytes and compute the gate on them:

For 8 bytes:
$a = \texttt{a}_0\texttt{a}_1\texttt{a}_2\texttt{a}_3\texttt{a}_4\texttt{a}_5\texttt{a}_6\texttt{a}_7\\
b =\texttt{b}_0\texttt{b}_1\texttt{b}_2\texttt{b}_3\texttt{b}_4\texttt{b}_5\texttt{b}_6\texttt{b}_7\\
c = \texttt{c}_0\texttt{c}_1\texttt{c}_2\texttt{c}_3\texttt{c}_4\texttt{c}_5\texttt{c}_6\texttt{c}_7\\
d = \texttt{d}_0\texttt{d}_1\texttt{d}_2\texttt{d}_3\texttt{d}_4\texttt{d}_5\texttt{d}_6\texttt{d}_7\\
e = \texttt{e}_0\texttt{e}_1\texttt{e}_2\texttt{e}_3\texttt{e}_4\texttt{e}_5\texttt{e}_6\texttt{e}_7\\
f = \texttt{f}_0\texttt{f}_1\texttt{f}_2\texttt{f}_3\texttt{f}_4\texttt{f}_5\texttt{f}_6\texttt{f}_7\\
g = \texttt{g}_0\texttt{g}_1\texttt{g}_2\texttt{g}_3\texttt{g}_4\texttt{g}_5\texttt{g}_6\texttt{g}_7\\
h = \texttt{h}_0\texttt{h}_1\texttt{h}_2\texttt{h}_3\texttt{h}_4\texttt{h}_5\texttt{h}_6\texttt{h}_7$

We can construct the following 8 bytes:

$bit_0 = \texttt{a}_0\texttt{b}_0\texttt{c}_0\texttt{d}_0\texttt{e}_0\texttt{f}_0\texttt{g}_0\texttt{h}_0\\
bit_1 = \texttt{a}_1\texttt{b}_1\texttt{c}_1\texttt{d}_1\texttt{e}_1\texttt{f}_1\texttt{g}_1\texttt{h}_1\\
bit_2 = \texttt{a}_2\texttt{b}_2\texttt{c}_2\texttt{d}_2\texttt{e}_2\texttt{f}_2\texttt{g}_2\texttt{h}_2\\
bit_3 = \texttt{a}_3\texttt{b}_3\texttt{c}_3\texttt{d}_3\texttt{e}_3\texttt{f}_3\texttt{g}_3\texttt{h}_3\\
bit_4 = \texttt{a}_4\texttt{b}_4\texttt{c}_4\texttt{d}_4\texttt{e}_4\texttt{f}_4\texttt{g}_4\texttt{h}_4\\
bit_5 = \texttt{a}_5\texttt{b}_5\texttt{c}_5\texttt{d}_5\texttt{e}_5\texttt{f}_5\texttt{g}_5\texttt{h}_5\\
bit_6 = \texttt{a}_6\texttt{b}_6\texttt{c}_6\texttt{d}_6\texttt{e}_6\texttt{f}_6\texttt{g}_6\texttt{h}_6\\
bit_7 = \texttt{a}_7\texttt{b}_7\texttt{c}_7\texttt{d}_7\texttt{e}_7\texttt{f}_7\texttt{g}_7\texttt{h}_7\\$

Notice that each byte $bit_\alpha$ contains only a the $\alpha$ bit of $a,b,c,d,e,f,g,h$.

Then we can replicate our gates operations as seen above on these $bit_\alpha$. Once the computations are done, all we need to do is rearrange back the bits in their respective bytes.

Remark: By doing so and extending this technique one can compute 8, 32, 64 or 128 AES S-box at the same time!

This technique is called bit-slicing.

Those are the 3 mains way to implement AES (a bit more to read here).



Now for your second question: 


  What are the challenges/trade-offs involved?


Those are: Memory/Rom Space, Time of execution, complexity of implementation (meaning that it is also easy to screw up...)