Given two linear codes, the Linear Equivalence Problem (LEP) asks to find (if it exists) a linear isometry between them; as a special case, we have the Permutation Equivalence Problem (PEP), in which isometries must be permutations. LEP and PEP have recently gained renewed interest as the security foundations for several post-quantum schemes, including LESS. A recent paper has introduced the use of the Schur product to solve PEP, identifying many new easy-to-solve instances. In this paper, we extend this result to LEP. In particular, we generalize the approach and rely on the more general notion of power codes. Combining it with Frobenius automorphisms and Hermitian hulls, we identify many classes of easy LEP instances. To the best of our knowledge, this is the first work exploiting algebraic weaknesses for LEP. Finally we show an improved reduction to PEP whenever the coefficients of the monomial matrix are in a subgroup of the multiplicative group of the finite field.

Threshold-Computation-in-the-Head (TCitH) and VOLE-in-the-Head (VOLEitH), two recent developments of the MPC-in-the-Head (MPCitH) paradigm, have significantly improved the performance of digital signature schemes. This work embeds the restricted decoding problem within these frameworks: we propose a structurally simple modeling that achieves competitive signature sizes. Specifically, by instantiating the restricted decoding problem with the same hardness assumption underlying CROSS, we reduce sizes by more than a factor of two compared to the NIST submission. Moreover, we observe that ternary full-weight decoding, closely related to the hardness assumption underlying WAVE, is a restricted decoding problem. Using ternary full-weight decoding, we obtain signature sizes comparable to the smallest MPCitH-based candidates in the NIST competition.

Abstract Starting from links between Coding Theory and Secret Sharing Schemes, we develop an extensible and decentralized version of Shamir Secret Sharing, that allows the addition of new users after the initial share distribution. On top of it we design a totally decentralized ( t , n )-threshold Schnorr signature scheme that needs only t users online during the key generation phase, while the others join later. Under standard assumptions we prove our scheme secure against adaptive malicious adversaries. Furthermore, we show how our security notion can be strengthened when considering a rushing adversary. Using a classical game-based argument, we prove that if there is an adversary capable of forging the scheme with non-negligible probability, then we can build a forger for the centralized Schnorr scheme with non-negligible probability.

Given two linear codes, the Code Equivalence Problem asks to find (if it exists) an isometry mapping one code into the other. A special case is the Permutation Equivalence Problem (PEP), where the isometry must be a permutation. The hardness of PEP is crucially dependent on thehullof a code, that is, the intersection between a code and its dual. Indeed, most of the known algorithms have running time that grows exponentially with the hull dimension. Since random codes have very small hull with large probability, PEP is deemed easy for random codes. In this paper we study how the so-called Schur product between linear codes can be employed to solve PEP. The basic idea is to transform a given PEP instance by computing the square of the given codes. While it is well known that the square code operation preserves equivalence between linear codes, we show that, regardless of the hull dimension of the starting codes, their square codes have trivial hull with high probability. Furthermore, we show that as long as the code rate is sufficiently low, no additional permutations mapping the square codes exist with high probability. This effectively generates a new pair of equivalent codes with trivial hulls, where the underlying permutation remains identical to that of the original instance. This observation allows us to leverage existing hull-based attacks to recover the permutation for the square codes, and consequently, for the original codes. Furthermore, we improve this attack by exploiting the structural relationship between hulls: if a permutation maps two codes, the same permutation also maps their respective hulls. We show that by considering the square of the hull as a code in its own right, its hull also becomes trivial with high probability. This allows for the identification of new weak instances of PEP, leading to an attack whose complexity no longer depends on the initial hull dimension, as it is the case of most known algorithm. In particular, we show that our attack achieves average polynomial-time complexity (since the square of the hull, when seen as a code, intersects with its dual in a low dimensional space with large probability) as long asknorh2n, wheren, k, andhdenote the code length, dimension, and hull dimension, respectively. We corroborate our analysis, which relies on some (plausible) heuristics, with intensive numerical simulations. As a concrete application, we consider the updatable encryption scheme proposed by Albrecht, Benčina, and Lai at Eurocrypt 2025. All the recommended instances fall into the range of weak PEP instances identified in this paper; hence, they are susceptible to our attack. As a demonstration, we successfully recover the secret permutation for two of the instances claiming 128 bits of security in about 10 minutes on average on a laptop. As a fix, instances with hull dimensionh>√2nshould be employed.