Cryptanalysis of the Subfield Bilinear Collision Problem

The security of a recent MPC-in-the-Head signature scheme introduced at Crypto 2024 by Huth and Joux required the introduction of a new ad hoc hardness assumption called the Subfield Bilinear Collision (SBC) problem. By relying on the VOLE-in-the-Head framework, the authors further improved the performance of this scheme at Asiacrypt 2025, resulting in a very compact construction. In this paper, we improve the original cryptanalysis of SBC in several ways. First, we describe a link between the SBC problem and the decoding problem in the rank metric for codes linear over an extension field, strengthening its theoretical hardness and expanding the range of attacks on the SBC problem. Second, we analyze Gröbner basis algorithms applied to the bilinear modeling of SBC proposed by Huth and Joux and formulate conjectures on the behavior of this system. Finally, we describe another algebraic modeling of SBC obtained by using the Plücker relations between the maximal minors of a matrix. While we do not threaten the parameters of the proposed signature schemes relying on SBC, our work opens the door to a more accurate analysis. In particular, we were not able to analyze the inclusion of the field equations in the Gröbner basis algorithm, which is especially relevant since q = 2 in these parameters. We leave this task for future work.