Arbitrary width pseudorandom permutation 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?
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.