An arbitrary width pseudorandom permutation seems like a very versatile secret-key cryptographic building block. It allows for trivial (nonce-misuse-resistant!) authenticated encryption, among other things.
Are there any known constructions that are considered secure? Are any of those efficient in practice?
AEZ by Hoang, Krovetz and Rogaway looks like just what you're asking for – if it's secure.
Pros:
Cons:
The usual problems of AES on machines without hardware support for it.
I don't know how much analysis it's gotten. It was a CAESAR candidate but didn't win, unfortunately.
They don't seem to have a security proof of the form "if you can break this then you can break AES-something-something". Instead they start with a construction called AEZ[AES] with 2.5 AES encryptions per 128 bits that they can prove secure, then they replace 10-round AES with 4-round Rijndael on the grounds that all of the data is still going through 12 Rijndael rounds in total. It's probably fine, but it doesn't automatically benefit from the tons of analysis that's gone into AES.
There's XXTEA, whose block size is an arbitrary multiple of 64 bits, but it's broken. There's the Hasty Pudding Cipher, an AES candidate, but it was not selected to be one of the AES finalists and has received relatively little attention.
Built out of a stream cipher (short key $\mapsto$ long output stream) and hash function (long message $\mapsto$ short hash), there are BEAR, LION, and LIONESS. But you probably won't break any speed records with an authenticated encryption scheme built out of one of those, rather than out of the stream cipher and hash function directly.
