Notions and relations for RKA-secure permutation and function families

The theory of designing block ciphers is mature, having seen signi¯cant progress since the early 1990s for over two decades, especially during the AES devel- opment e®ort. Nevertheless, interesting directions exist, in particular in the study of the provable security of block ciphers along similar veins as public-key primitives, i.e. the notion of pseudorandomness (PRP) and indistinguishability (IND). Furthermore, recent cryptanalytic progress has shown that block ciphers well designed against known cryptanalysis techniques including related-key attacks (RKA) may turn out to be less secure against related-key attacks than expected. The notion of provable security of block ciphers against related-key attacks was initiated by Bellare and Kohno, and sub- sequently treated by Lucks. Concrete block cipher constructions were proposed therein with provable security guarantees. In this paper, we are interested in the security no- tions for RKA-secure block ciphers.