Paper 2020/1321
Provably Quantum-Secure Tweakable Block Ciphers
Akinori Hosoyamada and Tetsu Iwata
Abstract
Recent results on quantum cryptanalysis show that some symmetric key schemes can be broken in polynomial time even if they are proven to be secure in the classical setting. Liskov, Rivest, and Wagner showed that secure tweakable block ciphers can be constructed from secure block ciphers in the classical setting. However, Kaplan et al.~showed that their scheme can be broken by polynomial time quantum superposition attacks, even if underlying block ciphers are quantum-secure. Since then, it remains open if there exists a mode of block ciphers to build quantum-secure tweakable block ciphers. This paper settles the problem in the reduction-based provable security paradigm. We show the first design of quantum-secure tweakable block ciphers based on quantum-secure block ciphers, and present a provable security bound. Our construction is simple, and when instantiated with a quantum-secure $n$-bit block cipher, it is secure against attacks that query arbitrary quantum superpositions of plaintexts and tweaks up to $O(2^{n/6})$ quantum queries. Our security proofs use the compressed oracle technique introduced by Zhandry. More precisely, we use an alternative formalization of the technique introduced by Hosoyamada and Iwata.
Note: minor revision
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in FSE 2022
- Keywords
- Provable securityQuantum securityTweakable block cipherCompressed oracle technique
- Contact author(s)
-
akinori hosoyamada bh @ hco ntt co jp
hosoyamada akinori @ nagoya-u jp
tetsu iwata @ nagoya-u jp - History
- 2021-03-12: revised
- 2020-10-23: received
- See all versions
- Short URL
- https://ia.cr/2020/1321
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1321,
author = {Akinori Hosoyamada and Tetsu Iwata},
title = {Provably Quantum-Secure Tweakable Block Ciphers},
howpublished = {Cryptology ePrint Archive, Paper 2020/1321},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1321}},
url = {https://eprint.iacr.org/2020/1321}
}
