Paper 2026/1573

The Non-Intersecting Codewords Problem and its Application to MPC-in-the-Head Signatures

Abstract

Since McEliece introduced the first code-based encryption scheme in 1978, most code-based cryptographic constructions have relied on hard problems related to decoding random linear codes (or variants thereof) or code equivalence. More recently, the use of the MPC-in-the-Head paradigm has enabled the construction of a new class of very competitive digital signature schemes relying on such assumptions, including the NIST submissions Mirath, PERK, RYDE, and SDitH, as well as a recent proposal based on the so-called Subfield Bilinear Collision problem by Huth and Joux (Crypto 2024). In this work, we enrich the portfolio of code-based MPC-in-the-Head signature schemes by introducing a new hard problem to cryptography, referred to as the Non-Intersecting Codewords (NIC) problem. In this problem, one has to find two codewords of a given linear code such that their supports in the Hamming metric do not intersect. After discussing how to generate hard instances and studying several attacks on it, we show that the NIC problem can be used to construct a competitive MPC-in-the-Head signature scheme. Using generic constructions, we obtain smaller signature sizes than SDitH and PERK, attaining a signature size of 2~934~Bytes for NIST security level I.