There are alternatives to an s box.  You might say that they are evolutionary extensions of the traditional s box.  But they are all very much more complex.

As you know, an s box is typically implemented as a RAM based look up table.  So for an 8 bit s box, there are 256 possible inputs and outputs, requiring 256 bytes of storage.  This is 2^8.  If you had a primitive that required a 16 bit s box, you'll need 2^16 or 65,536 lookup values.  So this would be suitable for a 16 bit processor. 

If you go wider, the memory required for a look up table becomes onerous for today's processors.  (You might manage a 24 bit lookup table, but processing 24 bit words on  32 bit processor is a PITA.)  You can opt for a (what I call) *active* s box.

Instead of a static lookup table, you perform a computation on the inputs to the active s box, and output a value determined in accordance with some formula you've devised.  It's usually some form of mini hash.  It allows s boxes of arbitrarily large width.  A good example is  *The Diffusion Layer (MR)* algorithm of the Whirlpool hash.  That's 256 bits wide and uses clever Galois field theory.  A passive s box would be impossible at this width.  That transformation matrix could easily be widened to 16 * 16 values creating a 512 bit s box and a Whirlpool block size of 2048 bits.  Or even more.

Another form of active s box can be implemented without the clever Galois mathematics using Pearson hashes.  An 8 bit hash output is generated per each pass over the input bits. Using a unique permutation table for byte means that the active s box can be extended to any size.  I've successfully used this for a 2048 bit box. The penalty is 256 permutation tables, but this is easily within the capacity of a small desktop /tablet.  The security of this technique may be acceptable when used in conjunction with a good permutation and key round functions.

You'll find that any reasonably secure algorithm can be used to compute the outputs of an active s box.  There's also [this][1] question regarding similar active s boxes.  The security of a primitive doesn't just come from an s box.  Indeed Keccak has no real s box but is ostensibly secure at the moment.  And a great deal of security comes from the number of rounds, not just the complexity of the rounds.  The upshot is that it doesn't have to be dead clever to be dead 'ard.  Skein follows this principle.


  [1]: https://crypto.stackexchange.com/questions/17975/math-to-replace-s-boxes-good-or-bad-idea