×

Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations. (English) Zbl 1507.94040

Smart, Nigel P. (ed.), Topics in cryptology – CT-RSA 2018. The cryptographers’ track at the RSA conference 2018, San Francisco, CA, USA, April 16–20, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10808, 198-218 (2018).
Summary: 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 tradeoffs between data complexity \(D\) and time complexity \(T\) against the problem of cardinality \(N\) are \(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 when quantum computations are available to the 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.
For the entire collection see [Zbl 1408.94008].

MSC:

94A60 Cryptography
81P94 Quantum cryptography (quantum-theoretic aspects)
81P68 Quantum computation
PDFBibTeX XMLCite
Full Text: DOI