Cryptology ePrint Archive: Report 2017/474

Insuperability of the Standard Versus Ideal Model Gap for Tweakable Blockcipher Security

Bart Mennink

Abstract: Two types of tweakable blockciphers based on classical blockciphers have been presented over the last years: non-tweak-rekeyable and tweak-rekeyable, depending on whether the tweak may influence the key input to the underlying blockcipher. In the former direction, the best possible security is conjectured to be $2^{\sigma n/(\sigma+1)}$, where $n$ is the size of the blockcipher and $\sigma$ is the number of blockcipher calls. In the latter direction, Mennink and Wang et al. presented optimally secure schemes, but only in the ideal cipher model. We investigate the possibility to construct a tweak-rekeyable cipher that achieves optimal security in the standard cipher model. As a first step, we note that all standard-model security results in literature implicitly rely on a generic standard-to-ideal transformation, that replaces all keyed blockcipher calls by random secret permutations, at the cost of the security of the blockcipher. Then, we prove that if this proof technique is adopted, tweak-rekeying will not help in achieving optimal security: if $2^{\sigma n/(\sigma+1)}$ is the best one can get without tweak-rekeying, optimal $2^n$ provable security with tweak-rekeying is impossible.

Category / Keywords: Optimal security, standard model, ideal model, impossibility, tweakable blockciphers

Original Publication (in the same form): IACR-CRYPTO-2017

Date: received 26 May 2017, last revised 28 May 2017

Contact author: b mennink at cs ru nl

Available format(s): PDF | BibTeX Citation

Version: 20170528:232220 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]