Welcome to the resource topic for 2017/977
Title:
Cryptanalysis against Symmetric-Key Schemes with Online Classical Queries and Offline Quantum Computations
Authors: Akinori Hosoyamada, 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.
ePrint: https://eprint.iacr.org/2017/977
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .