From everything I've seen, the security requirements of "true" RAE are exactly SPRP - that's certainly how Rogaway has framed it. To the best of my knowledge,

From everything I've seen, the security requirements of "true" RAE are exactly SPRP - that's certainly how Rogaway has framed it. To the best of my knowledge, that's why he designed AEZ under the encode-then-encipher paradigm - encode the plaintext with \tau trailing zero bits, then encipher it with (what is intended to be) a length-preserving SPRP. Being an SPRP, the inverse is also a PRP, and thus any adulteration of the ciphertext results in a pseudorandom decryption, preventing RUP (and causing the trailing zeroes to fail to validate). Constructing the SPRP then becomes the interesting part - a fascinating construction can be found in https://arxiv.org/abs/1310.4050 https://arxiv.org/abs/1310.4050 (which neither uses a block cipher entire, paying the cost of multiple invocations per block, _nor_ gives up on proofs - instead, it extends Cook's Elastic Cipher construction to arbitrary lengths, using the _round function_ directly, with security reductions to the original cipher the round function was taken from.)