Dedicated Quantum Attacks on XOR-Type Function With Applications to Beyond-Birthday- Bound MACs

A lot of work in the field of quantum cryptanalysis is currently devoted to finding applications of Grover-meets-Simon algorithm and its complexity is given in the form of
$\mathcal {O}$
, but research on how to implement the attack efficiently is still insufficient. After all, it is crucial to study quantum attacks in resource-limited situations, according to NIST’s guidance on circuit depth. This work first evaluates the parallelization of Grover-meets-Simon by drawing on the Grover’s parallel approach and shows that as the width increases by
$2^{t}(t\gt 0)$
, the depth decreases by a factor of
$\sqrt {2^{t}}$
. Further, the first dedicated quantum attack on a class of functions that appear in cryptographic scheme applications (so-called XOR-type function) is proposed. The depth, width, and the number of gates required for the attack are greatly reduced compared to the general parallelization. Then we apply the attack to various Beyond-Birthday-Bound (BBB) MACs, where the XOR function can be constructed, including
SUM-ECBC
and its variants (
2K-SUM-ECBC
,
2K-ECBC_Plus
), and
GCM-SIV2
. In the typical case where
SUM-ECBC
is based on AES-128, our attack saves at least 62.3% in depth, 19.5% in width and 22.2% in gate count simultaneously. The impact on some lightweight ciphers is further explored, and it is interesting to note that the lighter the quantum circuit implementation of the cipher is, the greater the possible impact of an attack will be. This observation may provide new insights into quantum cryptanalysis.