Paper 2024/196

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

Abstract

In this note, we show that some of the parameters of the Quotient-Ring transform proposed for VOX are vulnerable. More precisely, they were chosen to defeat an attack in the field extension ${\mathbb{F}}_{q^l}$ obtained by quotienting ${\mathbb{F}}_q[X]$ by an irreducible polynomial of degree $l$. We observe that we may use a smaller extension ${\mathbb{F}}_{q^{l^{\prime }}}$ for any $l^{\prime }|l$, in which case the attacks apply again. We also introduce a simple algebraic attack without the use of the MinRank problem to attack the scheme. These attacks concern a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb. We estimate the cost of our attack on these parameter sets and find costs of at most $$ gates, and significantly lower in most cases. In practice, our attack requires $$ for parameter sets I,III,V for the initial VOX parameters, and $$ for parameter sets IIIa, Vb proposed after the rectangular MinRank attack.