Paper 2024/196

Subfield attack: leveraging composite-degree extensions in the Quotient Ring transform

Abstract

The VOX signature scheme is a multivariate signature scheme which was submitted to the Round 1 Additional Digital Signature Schemes NIST process. VOX relies on the Hat Plus perturbation and the Quotient-Ring transform (QR). We formalize a dimension criterion enabling the direct attack to be used as a key recovery attack against UOV schemes. This enables a practical cryptanalysis of the Round 1 VOX parameters. Next, we show that some of the alternative parameters proposed for VOX after attacks on the Round 1 submission are still vulnerable. More precisely, these parameters were chosen to defeat an attack of Furue and Ikematsu in the field extension defined by the QR parameter. We observe that one may use a smaller field extension of any degree dividing the QR parameter, in which case the attacks apply again. These attacks are relevant for a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb. In particular, we apply the subfield framework to our previous dimension criterion for the direct attack. We estimate the cost of our attack on these parameter sets and find costs of at most 2^67 gates, and significantly lower in most cases. In practice on a commercial laptop, our attack requires 0.3s, 1.35s, 0.56s for parameter sets I, III, V for VOX, and 56.7s, 6.11s for the alternative parameter sets IIIa, Vb. Our analysis also improves the cryptanalysis of some alternative parameters proposed by Guo and Ding, and of the ``Minus'' variant of VOX.