**Cryptanalysis against Symmetric-Key Schemes with Online Classical Queries and Offline Quantum Computations**

*Akinori Hosoyamada and Yu Sasaki*

**Abstract: **In this paper, quantum attacks against symmetric-key schemes are presented in which adversaries only make classical queries but use quantum computers for offline computations.
Our attacks are not as efficient as polynomial-time attacks making quantum superposition queries, while our attacks use the realistic model and overwhelmingly improve the classical attacks.
Our attacks convert a type of classical meet-in-the-middle attacks into quantum ones. The attack cost depends on the number of available qubits and the way to realize the quantum hardware. The tradeoff between data complexity $D$ and time complexity $T$ against the problem of cardinality $N$ is $D^2 \cdot T^2 =N$ and $D \cdot T^6 = N^3$ in the best and worst case scenarios to the adversary respectively, while the classic attack requires $D\cdot T = N$.
This improvement is meaningful from an engineering aspect because several existing schemes claim beyond-birthday-bound security for $T$ by limiting the maximum $D$ to be below $2^{n/2}$ according to the classical tradeoff $D\cdot T = N$. Those schemes are broken if quantum offline computations are performed by adversaries.
The attack can be applied to many schemes such as a tweakable block-cipher construction TDR, a dedicated MAC scheme Chaskey, an on-line authenticated encryption scheme McOE-X, a hash function based MAC H$^2$-MAC and a permutation based MAC keyed-sponge.
The idea is then applied to the FX-construction to discover new tradeoffs in the classical query model.

**Category / Keywords: **secret-key cryptography / post-quantum cryptography, classical query model, meet-in-the-middle, tradeoff, Chaskey, TDR, keyed sponge, KMAC, FX

**Original Publication**** (in the same form): **CT-RSA 2018

**Date: **received 5 Oct 2017, last revised 8 Jan 2018

**Contact author: **hosoyamada akinori at lab ntt co jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20180109:022137 (All versions of this report)

**Short URL: **ia.cr/2017/977

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]