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.
Category / Keywords: secret-key cryptography / block ciphers, foundations, related-key security Original Publication (with major differences): IACR-ASIACRYPT-2015 Date: received 7 Sep 2015, last revised 8 Sep 2015 Contact author: tessaro at cs ucsb edu Available format(s): PDF | BibTeX Citation Version: 20150908:061643 (All versions of this report) Short URL: ia.cr/2015/868 Discussion forum: Show discussion | Start new discussion