Paper 2015/868

Optimally Secure Block Ciphers from Ideal Primitives

Stefano Tessaro

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
Keywords
block ciphersfoundationsrelated-key security
Contact author(s)
tessaro @ cs ucsb edu
History
2015-09-08: revised
2015-09-08: received
See all versions
Short URL
https://ia.cr/2015/868
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/868,
      author = {Stefano Tessaro},
      title = {Optimally Secure Block Ciphers from Ideal Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2015/868},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/868}},
      url = {https://eprint.iacr.org/2015/868}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.