International Association
for Cryptologic Research

Recent advances in block-cipher theory deliver security analyses in

models where one or more underlying components (e.g., a function or

a permutation) are {\\em ideal} (i.e., randomly chosen). This paper

addresses the question of finding {\\em new} constructions achieving

the highest possible security level under minimal assumptions in

such ideal models.

We present a new block-cipher construction, derived from the

Swap-or-Not construction by Hoang et al. (CRYPTO \'12). With $n$-bit

block length, our construction is a secure pseudorandom permutation

(PRP) against attackers making $2^{n - O(\\log n)}$ block-cipher

queries, and $2^{n - O(1)}$ queries to the underlying component

(which has itself domain size roughly $n$). This security level is

nearly optimal. So far, only key-alternating ciphers have been known

to achieve comparable security levels using $O(n)$ independent

random permutations. In contrast, here we only assume that a {\\em

single} {\\em function} or {\\em permutation} is available, while

achieving similar efficiency.

Our second contribution is a generic method to enhance a block

cipher, initially only secure as a PRP, to achieve related-key

security with comparable quantitative security.