Paper 2018/783

Short Variable Length Domain Extenders With Beyond Birthday Bound Security

Yu Long Chen, Bart Mennink, and Mridul Nandi

Abstract

Length doublers are cryptographic functions that transform an n-bit cryptographic primitive into an efficient and secure cipher that length-preservingly encrypts strings of length in [n,2n-1]. All currently known constructions are only proven secure up to the birthday bound, and for all but one construction this bound is known to be tight. We consider the remaining candidate, LDT by Chen et al.(ToSC 2017(3)), and prove that it achieves beyond the birthday bound security for the domain [n,3n/2). We generalize the construction to multiple rounds and demonstrate that by adding one more encryption layer to LDT, beyond the birthday bound security can be achieved for all strings of length in [n,2n-1]: security up to around 2^{2n/3} for the encryption of strings close to n and security up to around 2^{n} for strings of length close to 2n. The security analysis of both schemes is performed in a modular manner through the introduction and analysis of a new concept called ``harmonic permutation primitives.''

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2018
Keywords
provable security
Contact author(s)
yulong chen @ kuleuven be
b mennink @ cs ru nl
mridul nandi @ gmail com
History
2018-09-01: received
Short URL
https://ia.cr/2018/783
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/783,
      author = {Yu Long Chen and Bart Mennink and Mridul Nandi},
      title = {Short Variable Length Domain Extenders With Beyond Birthday Bound Security},
      howpublished = {Cryptology ePrint Archive, Paper 2018/783},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/783}},
      url = {https://eprint.iacr.org/2018/783}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.