International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Provably Quantum-Secure Tweakable Block Ciphers

Akinori Hosoyamada , NTT Secure Platform Laboratories, Tokyo, Japan; Nagoya University, Nagoya, Japan
Tetsu Iwata , Nagoya University, Nagoya, Japan
DOI: 10.46586/tosc.v2021.i1.337-377
Search ePrint
Search Google
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(2n/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.
Video from TOSC 2021
  title={Provably Quantum-Secure Tweakable Block Ciphers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2021, Issue 1},
  author={Akinori Hosoyamada and Tetsu Iwata},