Related-Key Secure Blockwise Universal Permutations and Non-linear SPNs

At CRYPTO 2018, Cogliati et al. initiated provable treatments of Substitution-Permutation Networks (SPNs), one of the most popular approaches to construct modern blockciphers. We extend their treatments to the related-key setting. Concretely, we consider (field) addition-induced related-key attacks ( \(\oplus \) -RKAs), formalize \(\oplus \) -related-key (super) blockwise universal permutations, and provide constructions using field multiplications. We then prove that the 1-round SPN model of Cogliati et al. built upon our \(\oplus \) -related-key (super) blockwise universal permutations is secure against \(\oplus \) -RKAs, up to the birthday bound. This gives theoretical support for constructing \(\oplus \) -RKA secure enciphering schemes from keyless permutations in the idealized SPN model.