Alternative block cipher design paradigms to SP-networks and Feistel-like ones?

Question

Before I familiarized myself with the type of cryptography that became popular with the rise of the information age, I was very much into what the community seems to call "classical" ciphers: Caesar shift ciphers, the Vigenère cipher, grilles, scytales, the Playfair cipher, the Enigma machine, and a few other techniques that might not qualify as ciphers. There were two kinds of ciphers, substitution and transposition (there was also a distinction between codes and ciphers). Still, I saw much more variety among cipher designs during that period of my life than after learning the classifications of information age algorithms used by modern cryptographers, like SP-networks and Feistel designs.

After understanding what a Feistel cipher—and all Feistel-like designs—is and what a substitution-permutation network is (before learning this one, I could actually see a little more variety), it seems like all I could up with were designs that fell into either category. Maybe three years ago, I discovered the ARX classification, and I figured that most ciphers that wound up in that those would always be Feistel-like ciphers. Later, I learned of Speck, which has a really unorthodox design (no swapping of the halves after each round). I didn't think of it as a different kind of structure until I saw that the CryptoLUX article on lightweight block ciphers lists it (ARX) as one. It also lists "generalized Feistel network" and "generalized Feistel structure", but I think those can be relabeled as "Feistel-like". And looking back on Speck, it seems like it cannot be classified as either a Feistel-like cipher or an SP-network.

So, my questions are:

• Are ARX block ciphers considered there own class of block cipher separate from SPNs and Feistel-like ones?
• Are there other schemes out there besides Feistel-like designs, SPNs, and ARX?

Answer 1

Are ARX block ciphers considered there own class of block cipher separate from SPNs and Feistel-like ones?

Generally speaking, yes. ARX ciphers typically only use simple CPU instructions (Addition, Rotation, and Xor) and are typically designed to ensure constant time execution as well as to facilitate efficient SIMD implementations.

The s-boxes and split state that are so prevalent among SPN and Feistel Networks generally aren't present in ARX designs. I'm sure if you wanted you could come up with/find an example of an ARX Feistel network or build an SP network from ARX instructions, but I'm not sure what advantages it would offer.

Are there other schemes out there besides Feistel-like designs, SPNs, and ARX? Or is there really nothing new under the sun?

Typically, the ARX/SPN/Feistel part of the algorithm is used to create a "pseudorandom permutation", and the pseudorandom permutation is then used as part of a cipher construction to provide encryption.

The basic cipher construction is the iterated key or Even-Mansour construction. AES can be modeled like this, as an interleaved application of a key addition layer with the pseudorandom permutation.

A more recent cipher construction that can be built from an arbitrary pseudorandom permutation is the sponge construction. Technically the duplex construction is a stream cipher, rather then a block cipher. I think that this is actually a key point: The presumption that a block cipher is the best way to encrypt is not necessarily true.

Permutation based

Permutation based constructions are usually more versatile, and often times offer an all-in-one solution (authenticated encryption, hashing, MACs); While you could construct all of the above via a block cipher, it is much more straightforward from an implementation perspective to use a permutation based construction like the sponge construction.

Homomorphic Ciphers

There exist "linear" secret key ciphers, like this one from Fully Homomorphic Encryption Over The Integers. Typically these sorts of ciphers are designed to facilitate homomorphic encryption and/or to instantiate public key cryptosystems. They are often times built from number-theoretic perspectives, and clearly do not resemble any of the other cipher categories (and you would not use them for the same reasons).