This paper concerns the Minimal Internet Key Exchange (IKE) protocol, which has received little attention to date, despite its potential to make the best-known IKE protocol sufficiently lightweight to be also applied in contexts where it is currently prohibitive, due to its large footprint. First, we introduce and describe Colibri, an efficient, open-source implementation of the Minimal IKE protocol, which allows us to quantitatively assess its real advantages in terms of lightness. Then we introduce a post-quantum variant of the Minimal IKE protocol, which is essential to make it contemporary, and assess it through Colibri. We demonstrate that the protocol performance remains excellent even in such a more challenging context, making it suitable for deploying pervasive and quantum-resistant virtual private networks.

Bit-Flipping (BF) decoders are a family of decoders widely employed in post-quantum cryptographic schemes based on Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes, such as BIKE. BF decoders suffer from trapping sets, corresponding to low-weight error patterns that likely lead to decoding failures. For QC-MDPC codes, the most relevant family of trapping sets is that of near-codewords, which are error patterns associated to low-weight syndromes. Indeed, recent works show that error patterns having a large overlap with near-codewords are the main culprits for decoding failures at very low Decoding Failure Rate (DFR) values. In this paper, we show that any BF decoder can be tweaked and made somehow aware of near-codewords, which means being able to recognize, and recover from, bad configurations due to near-codewords. We show that this modification results in minimal computational overhead. Through intensive numerical simulations, we evaluate the effectiveness of this approach on several BF decoders, considering both toy code parameters and BIKE parameters for NIST security category 1. Our results show drastic reductions in the DFR. We also find that, with this modification, a recently proposed BF variant called BF-Max outperforms the two decoders used by BIKE within the NIST competition.

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.

This paper studies cryptographic key exchange in satellite communications, which requires specific solutions because the satellite context presents unique challenges, particularly concerning onboard resource constraints and long transmission latency. We address these challenges by considering the Internet Key Exchange (IKE) protocol, which is widely used in terrestrial networks, and studying its applicability in the satellite context. This requires addressing two main issues: i) its efficiency in terms of the resources and bandwidth required to adapt to satellite terminals, and ii) its resistance even to attackers equipped with a quantum computer, in order to resist obsolescence and defend against harvest-now-decrypt-later attacks. We study these aspects from both a design and experimental point of view, defining and assessing some protocol variants characterized by low complexity and quantum resistance. To address the need to manage the transition from classic cryptographic primitives to post-quantum ones, we also consider the possibility of using hybrid cryptographic solutions that combine them both.

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.

The Bit-Flipping (BF) decoder, thanks to its very low computational complexity, is widely employed in post-quantum cryptographic schemes based on Moderate Density Parity Check codes in which, ultimately, decryption boils down to syndrome decoding. In such a setting, for security concerns, one must guarantee that the Decoding Failure Rate (DFR) is negligible. Such a condition, however, is very difficult to guarantee, because simulations are of little help and the decoder performance is difficult to model theoretically. In this paper, we introduce a new version of the BF decoder, that we call BF-Max, characterized by the fact that in each iteration only one bit (the least reliable) is flipped. When the number of iterations is equal to the number of errors to be corrected, we are able to develop a theoretical characterization of the DFR that tightly matches with numerical simulations. We also show how BF-Max can be implemented efficiently, achieving low complexity and making it inherently constant time. With our modeling, we are able to accurately predict values of DFR that are remarkably lower than those estimated by applying other approaches.

We introduce the family of Low-Density Orthogonal Idempotent (LDOI) codes, which are group codes characterized by two-sided ideals of a semisimple group algebra that have an orthogonal idempotent with low Hamming weight. These codes can be thought of as the analog, over a group algebra, of Low-Density Parity-Check (LDPC) codes over finite fields. We initiate the study of LDOI codes and characterize some of their properties in terms of weight of the orthogonal idempotent and the so-called adjacency matrix. We then show how the iterative Bit Flipping (BF) algorithm - the simplest form of decoder used for LDPC codes - can be adapted to decode LDOI codes. We show that, for certain families of LDOI codes (namely, those having a binary adjacency matrix), the BF decoder is optimal (i.e., achieves maximum error correction capability) even when just one iteration is performed.

The Permuted Kernel Problem (PKP) asks to find a permutation which maps an input matrix into the kernel of some given vector space. The literature exhibits several works studying its hardness in the case of the input matrix being mono-dimensional (i.e., a vector), while the multi-dimensional case has received much less attention and, de facto, only the case of a binary ambient finite field has been studied. The Subcode Equivalence Problem (SEP), instead, asks to find a permutation so that a given linear code becomes a subcode of another given code. At the best of our knowledge, no algorithm to solve the SEP has ever been proposed. In this paper we study the computational hardness of solving these problems. We first show that, despite going by different names, PKP and SEP are exactly the same problem. Then we consider the state-of-the-art solver for the mono-dimensional PKP (namely, the KMP algorithm, proposed by Koussa, Macario-Rat and Patarin), generalize it to the multi-dimensional case and analyze both the finite and the asymptotic regimes. We further propose a new algorithm, which can be thought of as a refinement of KMP. In the asymptotic regime our algorithm does not improve on KMP but, in the finite regime (and for parameters of practical interest), we achieve significant improvements, especially for the multi-dimensional version of PKP. As an evidence, we show that it is the fastest algorithm to attack several recommended instances of cryptosystems based on PKP. As a side-effect, given the mentioned equivalence between PKP and SEP, all the algorithms we analyze in this paper can be used to solve instances of the latter problem.

We propose a protocol to jointly achieve authentication and consensus on a blockchain network, in which endpoints are required to digitally sign some random message using fuzzy keys according to a classic fuzzy signature paradigm typical, for example, of biometric authentication. We consider classic RSA digital signatures, showing that fuzziness in the secret key translates into some noise affecting the derived signatures. The removal of such a noise provides the basis for building a blockchain consensus mechanism, which we name Proof of Fuzzy Signature (PoFS). It basically provides a special instance of Proof of Work in which the mining process corresponds to the de-noising process of RSA digital signatures derived from fuzzy keys. This way, the authentication process is delegated to a distributed network and, at the same time, requires executing the useful task of removing noise from fuzzy signatures.

Several recently proposed code-based cryptosystems base their security on a slightly generalized version of the classical (syndrome) decoding problem. Namely, in the so-called restricted (syndrome) decoding problem, the error values stem from a restricted set. In this paper, we propose new generic decoders, that are inspired by subset sum solvers and tailored to the new setting. The introduced algorithms take the restricted structure of the error set into account in order to utilize the representation technique efficiently. This leads to a considerable decrease in the security levels of recently published code-based cryptosystems.

The Permuted Kernel Problem (PKP) asks to find a permutation of a given vector belonging to the kernel of a given matrix. The PKP is at the basis of PKP-DSS, a post-quantum signature scheme deriving from the identification scheme proposed by Shamir in 1989. The most efficient solver for PKP is due to a recent paper by Koussa et al. In this paper we propose an improvement of such an algorithm, which we achieve by considering an additional collision search step applied on kernel equations involving a small number of coordinates. We study the conditions for such equations to exist from a coding theory perspective, and we describe how to efficiently find them with methods borrowed from coding theory, such as information set decoding. We assess the complexity of the resulting algorithm and show that it outperforms previous approaches in several cases. We also show that, taking the new solver into account, the security level of some instances of PKP-DSS turns out to be slightly overestimated.

We introduce a new family of linear block codes over $\mathbb{Z}_{q}$ that we name low-Lee-density parity-check (LLDPC) codes. These codes, which are embedded with the Lee metric, are characterized by a parity-check matrix whose rows and columns have low Lee weight. We propose general constructions of LLDPC codes and devise an efficient iterative decoding algorithm for them, with complexity that grows linearly with the code length. We assess the error rate performance of these codes through numerical simulations.

Public‐key cryptosystems built on quasi‐cyclic (QC) low‐density parity‐check and moderate‐density parity‐check codes are promising candidates for post‐quantum cryptography, since they are characterised by compact keys and high algorithmic efficiency. The main issue with this kind of system is represented by the fact that, since the decoding procedure is probabilistic, it may leak information about the secret key. In this work, the authors study cryptanalysis procedures that aim at recovering the secret key by exploiting this fact. They identify the phenomenon that is at the basis of these procedures and show that the QC structure plays an important role in the success of these attacks. They use a graph analogy to study the complexity of these attacks, and show that their feasibility strongly depends on the QC structure. They also devise an approach to perform full cryptanalysis by combining an information set decoding algorithm with some partial knowledge about the structure of the secret key.

In this paper, we present a lightweight hardware design for a recently proposed quantum-safe key encapsulation mechanism based on QC-LDPC codes called LEDAkem, which has been admitted as a round-2 candidate to the NIST post-quantum standardization project. Existing implementations focus on high speed while few of them take into account area or power efficiency, which are particularly decisive for low-cost or power constrained IoT applications. The solution we propose aims at maximizing the metric of area efficiency by rotating the QC-LDPC code representations amongst the block RAMs in digit level. Moreover, optimized parallelized computing techniques, lazy accumulation and block partition are exploited to improve key decapsulation in terms of area and timing efficiency. We show for instance that our area-optimized implementation for 128-bit security requires 6.82 x 105 cycles and 2.26 x 106 cycles to encapsulate and decapsulate a shared secret, respectively. The area-optimized design uses only 39 slices (3 percent of the available logic) and 809 slices (39 percent of the available logic) for key encapsulation and key decapsulation respectively, on a small-size low-end Xilinx Spartan-6 FPGA.

Iterative decoders used for decoding low-density parity-check (LDPC) and moderate-density parity-check (MDPC) codes are not characterized by a deterministic decoding radius and their error rate performance is usually assessed through intensive Monte Carlo simulations. However, several applications, like code-based cryptography, need guaranteed low values of the error rate, which are infeasible to assess through simulations, thus requiring the development of theoretical models for the error rate of these codes. Some models of this type already exist, but become computationally intractable for parameters of practical interest. Other approaches approximate the code ensemble behaviour through assumptions, which may not hold true for a specific code. We propose a theoretical analysis of the error correction capability of LDPC and MDPC codes that allows deriving tight bounds on the error rate at the output of parallel bit-flipping decoders. Special attention is devoted to the case of codes with small girth. Single-iteration decoding is investigated through a rigorous approach, which does not require any assumption and results in a guaranteed error correction capability for any single code. We show an example of application of the new bound to the context of code-based cryptography, where guaranteed error rates are needed to achieve strong security levels.

Differently from bounded-distance decoders used for algebraic codes, iterative decoders used for low-density parity-check (LDPC) codes are not characterized by a deterministic decoding radius. Therefore, the error rates of LDPC-coded transmissions are usually estimated heuristically through simulations. This is adequate for many applications like wireless communications, where a frame error rate (FER) in the order of 10-6or higher is usually targeted. However, lower values of FER can barely be assessed through simulations, and this limits the use of LDPC codes in applications requiring a lower FER, like optical communications and code-based cryptography. In this paper we introduce and study a version of the classic bit flipping (BF) decoder for which we are able to devise and develop a theoretical characterization of the FER. In addition, we consider a two-iteration hard-decision decoder for LDPC codes derived from BF, and discuss its error rate performance. Our results are validated through numerical simulations.

We consider a one-time digital signature scheme recently proposed by Persichetti and show that a successful key recovery attack can be mounted with limited complexity. The attack we propose exploits a single signature intercepted by the attacker, and relies on a statistical analysis performed over such a signature, followed by information set decoding. We assess the attack complexity and show that a full recovery of the secret key can be performed with a work factor that is far below the claimed security level. The efficiency of the attack is motivated by the sparsity of the signature, which leads to a significant information leakage about the secret key.

In this study, the authors elaborate on a recently proposed variant of the public‐key McEliece and Niederreiter cryptosystems using generalised Reed–Solomon (GRS) codes as private codes. The use of these codes brings known advantages in terms of public key size, but particular care is needed in the choice of parameters not to endanger the system security. In fact, the considered system exploits a strong disguising technique of the private code within the public code. However, it has recently been pointed out that some new attacks exist which may threaten some instances of such a system, therefore the choice of parameters needs to consider some further constraints compared to the original version. After outlining these constraints, the authors propose a new modification of the system achieving greater flexibility in the parameter choice. Moreover, the new system exhibits a lower complexity than the original GRS code‐based system. Its very competitive features such as key size and encryption rate are highlighted with respect to classic systems.

Cyber risk assessment requires defined and objective methodologies; otherwise, its results cannot be considered reliable. The lack of quantitative data can be dangerous: if the assessment is entirely qualitative, subjectivity will loom large in the process. Too much subjectivity in the risk assessment process can weaken the credibility of the assessment results and compromise risk management programs. On the other hand, obtaining a sufficiently large amount of quantitative data allowing reliable extrapolations and previsions is often hard or even unfeasible. In this paper, we propose and study a quantitative methodology to assess a potential annualized economic loss risk of a company. In particular, our approach only relies on aggregated empirical data, which can be obtained from several sources. We also describe how the method can be applied to real companies, in order to customize the initial data and obtain reliable and specific risk assessments.

In this paper we study recent reaction attacks against QC-LDPC and QC-MDPC code-based cryptosystems, which allow an opponent to recover the private parity-check matrix through its distance spectrum by observing a sufficiently high number of decryption failures. We consider a special class of codes, known as monomial codes, to form private keys with the desirable property of having a unique and complete distance spectrum. We verify that for these codes the problem of recovering the secret key from the distance spectrum is equivalent to that of finding cliques in a graph, and use this equivalence to prove that current reaction attacks are not applicable when codes of this type are used in the McEliece cryptosystem.

We propose to use real-valued errors instead of classical bit flipping intentional errors in the McEliece cryptosystem based on moderate-density parity-check (MDPC) codes. This allows to exploit the error correcting capability of these codes to the utmost, by using soft-decision iterative decoding algorithms instead of hard-decision bit flipping decoders. However, soft reliability values resulting from the use of real-valued noise can also be exploited by attackers. We devise new attack procedures aimed at this, and compute the relevant work factors and security levels. We show that, for a fixed security level, these new systems achieve the shortest public key sizes ever reached, with a reduction up to 25% with respect to previous proposals.