Abstract Nowadays, equivalence problems are widely used in cryptography, most notably to establish cryptosystems such as digital signatures, with MEDS, LESS, PERK as the most recent ones. However, in the context of matrix codes, only the code equivalence problem has been studied, while the subcode equivalence is well-defined in the Hamming metric. In this work, we introduce two new problems: the Matrix Subcode Equivalence Problem and the Inhomogeneous Matrix Subcode Problem, to which we apply the Multi-Party-Computation-in-the-Head (MPCitH) paradigm to build a signature scheme. These new problems, closely related to the Matrix Code Equivalence problem, ask to find an isometry given a code C and a subcode D . Furthermore, we prove that the Matrix Subcode Equivalence Problem reduces to the Hamming Subcode Equivalence problem, which is known to be NP-Complete, thus introducing the matrix code version of the Permuted Kernel Problem. We also adapt the combinatorial and algebraic algorithms for the Matrix Code Equivalence problem to the subcode case, and we analyze their complexities. We find with this analysis that the algorithms perform much worse than in the code equivalence case, which is the same as what happens in the Hamming metric. Finally, our analysis of the attacks allows us to take parameters much smaller than in the Matrix Code Equivalence case. Coupled with the effectiveness of Threshold-Computation-in-the-Head or VOLE-in-the-Head , we obtain a signature size of $$\approx $$ ≈ 4800 Bytes, with a public key of $$\approx $$ ≈ 275 Bytes. We thus obtain a reasonable signature size, which brings diversity in the landscape of post-quantum signature schemes, by relying on a new hard problem. In particular, this new signature scheme performs better than SPHINCS+, with a smaller size of public key + signature. Our signature compares also well with other signature schemes: compared to MEDS, the signature is smaller, and we reduced the size of the sum of signature and public key by a factor close to 5. We also obtain a signature size that is almost half the size of the CROSS signature scheme.

Tropical Differential Algebraic Geometry considers difficult or even intractable problems in Differential Equations and tries to extract information on their solutions from a restricted structure of the input. The fundamental theorem of Tropical Differential Algebraic Geometry and its extensions state that the support of power series solutions of systems of ordinary differential equations (with formal power series coefficients over an uncountable algebraically closed field of characteristic zero) can be obtained either, by solving a so-called tropicalized differential system, or by testing monomial-freeness of the associated initial ideals. Tropicalized differential equations work on a completely different algebraic structure which may help in theoretical and computational questions, particularly on the existence of solutions. We show here that both of these methods can be generalized to the case of systems of partial differential equations, this is, one can go either with the solution of tropicalized systems, or test monomial-freeness of the ideal generated by the initials when looking for supports of power series solutions of systems of differential equations, regardless the (finite) number of derivatives. The key are the vertex sets of Newton polytopes, upon which relies the definition of both tropical vanishing condition and the initial of a differential polynomial.

Tropical Differential Algebraic Geometry considers difficult or even intractable problems in Differential Equations and tries to extract information on their solutions from a restricted structure of the input. The Fundamental Theorem of Tropical Differential Algebraic Geometry states that the support of solutions of systems of ordinary differential equations with formal power series coefficients over an uncountable algebraically closed field of characteristic zero can be obtained by solving a so-called tropicalized differential system. Tropicalized differential equations work on a completely different algebraic structure which may help in theoretical and computational questions. We show that the Fundamental Theorem can be extended to the case of systems of partial differential equations by introducing vertex sets of Newton polytopes.