Paper 2016/578

Key-alternating Ciphers and Key-length Extension: Exact Bounds and Multi-user Security

Viet Tung Hoang and Stefano Tessaro

Abstract

The best existing bounds on the concrete security of key-alternating ciphers (Chen and Steinberger, EUROCRYPT '14) are only asymptotically tight, and the quantitative gap with the best existing attacks remains numerically substantial for concrete parameters. Here, we prove exact bounds on the security of key-alternating ciphers and extend them to XOR cascades, the most efficient construction for key-length extension. Our bounds essentially match, for any possible query regime, the advantage achieved by the best existing attack. Our treatment also extends to the multi-user regime. We show that the multi-user security of key-alternating ciphers and XOR cascades is very close to the single-user case, i.e., given enough rounds, it does not substantially decrease as the number of users increases. On the way, we also provide the first explicit treatment of multi-user security for key-length extension, which is particularly relevant given the significant security loss of block ciphers (even if ideal) in the multi-user setting. The common denominator behind our results are new techniques for information-theoretic indistinguishability proofs that both extend and refine existing proof techniques like the H-coefficient method.

Note: A proceeding version of this paper appears in CRYPTO 2016.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2016
Keywords
Symmetric cryptographyblock ciphersprovable securitytightnessmulti-user security
Contact author(s)
hviettung @ gmail com
History
2017-03-08: last of 4 revisions
2016-06-03: received
See all versions
Short URL
https://ia.cr/2016/578
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/578,
      author = {Viet Tung Hoang and Stefano Tessaro},
      title = {Key-alternating Ciphers and Key-length Extension: Exact Bounds and Multi-user Security},
      howpublished = {Cryptology ePrint Archive, Paper 2016/578},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/578}},
      url = {https://eprint.iacr.org/2016/578}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.