Paper 2026/916

Cryptanalysis of the Subfield Bilinear Collision Problem

Romaric Neveu, XLIM

Abstract

The Subfield Bilinear Collision (SBC) problem was introduced at Crypto 2024 by Huth and Joux to build an MPC-in-the-Head signature scheme. The problem has later proven to be even more efficient when used within the VOLE-in-the-Head framework (Asiacrypt 2025). In this note, we improve the original cryptanalysis of SBC in several ways. First, we describe a link between the SBC problem and the rank decoding problem, strengthening its theoretical hardness and expanding the range of attacks on the SBC problem. Second, we analyze Gröbner basis algorithms to solve the SBC bilinear system and obtain conjectures on the behavior of this system. Finally, we describe another algebraic modeling of SBC 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. More precisely, we do not take the field equations into account in our attacks. Including them would likely reduce the complexity, although the analysis would become more complicated. We leave this task for future work.

Note: To be updated with experiments and more content.

@misc{cryptoeprint:2026/916,
      author = {Pierre Briaud and Romaric Neveu},
      title = {Cryptanalysis of the Subfield Bilinear Collision Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/916},
      year = {2026},
      url = {https://eprint.iacr.org/2026/916}
}