Cryptology ePrint Archive: Report 2016/876

How to Build Fully Secure Tweakable Blockciphers from Classical Blockciphers

Lei Wang and Jian Guo and Guoyan Zhang and Jingyuan Zhao and Dawu Gu

Abstract: This paper focuses on building a tweakable blockcipher from a classical blockcipher whose input and output wires all have a size of $n$ bits. The main goal is to achieve full $2^n$ security. Such a tweakable blockcipher was proposed by Mennink at FSE'15, and it is also the only tweakable blockcipher so far that claimed full $2^n$ security to our best knowledge. However, we find a key-recovery attack on Mennink's proposal (in the proceeding version) with a complexity of about $2^{n/2}$ adversarial queries. The attack well demonstrates that Mennink's proposal has at most $2^{n/2}$ security, and therefore invalidates its security claim. In this paper, we study a construction of tweakable blockciphers denoted as $\tilde{\mathbb E}[s]$ that is built on $s$ invocations of a blockcipher and additional simple XOR operations. As proven in previous work, at least two invocations of blockcipher with linear mixing are necessary to possibly bypass the birthday-bound barrier of $2^{n/2}$ security, we carry out an investigation on the instances of $\tilde{\mathbb E}[s]$ with $s \ge 2$, and find $32$ highly efficient tweakable blockciphers $\widetilde{E1}$, $\widetilde{E2}$, $\ldots$, $\widetilde{E32}$ that achieve $2^n$ provable security. Each of these tweakable blockciphers uses two invocations of a blockcipher, one of which uses a tweak-dependent key generated by XORing the tweak to the key (or to a secret subkey derived from the key). We point out the provable security of these tweakable blockciphers is obtained in the ideal blockcipher model due to the usage of the tweak-dependent key.

Category / Keywords: tweakable blockcipher, full security, ideal blockcipher, tweak-dependent key

Original Publication (in the same form): IACR-ASIACRYPT-2016

Date: received 6 Sep 2016, last revised 13 Sep 2016

Contact author: wanglei_hb at sjtu edu cn, guojian@ntu edu sg, guoyanzhang@sdu edu cn, jingyuanzhao@live com, wanglei@cs sjtu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20160914:033013 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]