Search

The author constructs a complete classification of linear codes that are obtained from different types of codimension subcodes of Reed–Muller codes using the Hadamard product operation. [ABSTRACT FROM AUTHOR]

This paper presents a scheme that is designed for the effective implementation of lattice reduction for polynomial matrices within the list-decoding algorithm that is applied to the binary Goppa codes. The reduced form of a polynomial matrix is obtained by transforming the given polynomial matrix into a matrix in the weak Popov form. To achieve efficient lattice reduction within the list-decoding algorithm, the proposed scheme reorganizes the polynomial matrix by leveraging its inherent properties and converts it into the weak Popov form. When using the proposed implementation technique to convert the reorganized polynomial matrix into the weak Popov form, the number of simple transformations of the first kind that had to be performed was reduced by about 15% compared to the technique used to convert the original matrix to the weak Popov form. As a result, the execution time of lattice reduction was also decreased.

This paper introduces a variant of the McEliece cryptosystem and employs the $(C_{1}, C_{1} + C_{2})$ -construction to generate a new code from two arbitrary linear codes. We propose an efficient hard-decision decoding algorithm for linear codes derived from the $(C_{1}, C_{1} + C_{2})$ -construction and integrate them into the McEliece framework. The security of the cryptosystem varies based on the specific codes used in the $(C_{1}, C_{1} + C_{2})$ -construction. Our proposed variant achieves a good level of security with approximately the same key size compared to one of the classic McEliece candidates of the National Institute of Standards and Technology (NIST) standardization process. Specifically, we demonstrate a 25% key size reduction for our proposed parameters compared to one of the 256-bit secured classic McEliece parameters.

This work addresses the pressing issue of ensuring reliable information protection amidst increasing data volumes and rising numbers of cyber threats. Traditional cryptographic systems, while generally reliable, may prove vulnerable to new types of attacks, especially quantum ones. This highlights the need for exploring and researching more resilient encryption methods. The work proposes a hybrid cryptosystem that combines the McEliece system with the RSA encryption algorithm. This approach leverages the advantages of both methods: the high security level of RSA, based on the difficulty of factoring large numbers, and the resilience of McEliece to quantum attacks due to the complexity of decoding arbitrary linear codes. A distinctive feature of the proposed hybrid system is the use of Galois fields GF(p) for all operations, which provides an additional layer of protection and flexibility compared to traditional systems based on binary numeral systems. The integration of two asymmetric cryptographic algorithms, whose resilience is based on solving different mathematical problems, enhances the reliability and security of the proposed system. The use of a common parameter n for key generation also simplifies key management and expands the key space by a factor of n. This solution combines error protection with cryptographic security, making it a powerful tool for data protection in environments with potentially unreliable communication channels. The research conducted as part of this work focuses on analyzing the effectiveness and security of the proposed hybrid cryptosystem. Special attention is given to characteristics such as relative information transmission speed, ciphertext length, key size, and resistance to cryptanalysis. The results demonstrate the advantages of the hybrid system compared to using each algorithm individually. The findings could form the basis for further development of cryptographic methods for information protection in the face of modern threats. [ABSTRACT FROM AUTHOR]

The algorithm for finding the enumerators of degree 2 and higher for the generalized (L, G)‑code is presented. This algorithm makes it possible to enhance the rate of finding enumerators as distinct from the exhaustive search algorithm. It can be used to construct a modern variant of the McEliece cryptosystem. The presented solution is based on using the representation of the Galois field element via the function containing the coefficients of a smaller field. In addition, the results of comparison of the modern McEliece cryptosystem constructed based on the Goppa codes and generalized (L, G)-codes are presented. [ABSTRACT FROM AUTHOR]

A study is performed of the algebraic properties of the Hadamard product (Schur product, component-wise product) of linear error-correcting codes. The complexity of constructing a product basis using known multiplier bases is discussed. The concept is introduced of quotient, quasi-quotient, and maximal inclusion quasi-quotient obtained from the Hadamard division of one linear code by another. An explicit form of the maximum Hadamard division quasi-quotient is established. A criterion is proved for the existence of a given code of an inverse code in a semiring formed by linear codes of length with the operations of sum and product of Hadamard codes. The explicit form of codes that have a reverse code in this semiring is described. [ABSTRACT FROM AUTHOR]

One of the Round 3 Finalists in the NIST post-quantum cryptography call is the Classic McEliece cryptosystem. Although it is one of the most secure cryptosystems, the large size of its public key remains a practical limitation. In this work, we propose a McEliece-type cryptosystem using large minimum distance error-correcting codes derived from self-dual codes. To the best of our knowledge, such codes have not been implemented in a code-based cryptosystem until now. Moreover, we modify the decryption step of the system by introducing a decryption algorithm based on two private keys. We determine the parameters of binary codes with large minimum distance, which, if implemented into a McEliece-type cryptosystem, would provide a security level respectively of 80, 128, and 256 bits. For the 80-bit security case, we construct a large minimum distance self-dual code of length 1064, and use it to derive a random punctured code to be used in the corresponding McEliece-type cryptosystem. Compared to the original McEliece cryptosystem, the key size is reduced by about 38.5%, although an optimal decoding set is yet to be constructed to make the new system fully defined and usable.

Code-based cryptography is a promising candidate for post-quantum cryptography due to its strong security guarantees and efficient implementations. In this paper, we explore the use of code-based cryptography for multi-party computation and digital signatures, two important cryptographic applications. We present several efficient and secure code-based protocols for these applications, based on the McEliece cryptosystem and its variants. Our protocols offer strong security guarantees against both classical and quantum attacks, and have competitive performance compared to other post-quantum cryptographic schemes. We also compare code-based cryptography with other post-quantum schemes, including lattice-based and hash-based cryptography, and discuss the advantages and disadvantages of each approach. [ABSTRACT FROM AUTHOR]

Advances in quantum computing have urged the need for cryptographic algorithms that are low-power, lowenergy, and secure against attacks that can be potentially enabled. For this post-quantum age, different solutions have been studied. Code-based cryptography is one feasible solutionwhose hardware architectures have become the focus of research in the NIST standardization process and has been advanced to the final round (to be concluded by 2022-2024). Nevertheless, although these constructions, e.g., McEliece and Niederreiter public key cryptography, have strong error correction properties, previous studies have proved the vulnerability of their hardware implementations against faults product of the environment and intentional faults, i.e., differential fault analysis. It is previously shown that depending on the codes used, i.e., classical or reduced (using either quasi-dyadic Goppa codes or quasi-cyclic alternant codes), flaws in error detection could be observed. In this work, efficient fault detection constructions are proposed for the first time to account for such shortcomings. Such schemes are based on regular parity, interleaved parity, and two different cyclic redundancy checks (CRC), i.e., CRC-2 and CRC-8. Without losing the generality, we experiment on the McEliece variant, noting that the presented schemes can be used for other code-based cryptosystems. We perform error detection capability assessments and implementations on field-programmable gate array Kintex-7 device xc7k70tfbv676-1 to verify the practicality of the presented approaches. To demonstrate the appropriateness for constrained embedded systems, the performance degradation and overheads of the presented schemes are assessed. [ABSTRACT FROM AUTHOR]

Classical cryptosystems proposed by Robert McEliece (1978) and Harold Niederreiter (1986) and their modern variations are studied. A detailed review of five code-based public key cryptosystems has been presented. It is shown that some of the modern interpretations of the classical McEliece and Niederreiter cryptosystems have significant issues. In particular, it has been established that the XGRS cryptosystem based on extended Reed-Solomon codes does not provide the declared level of security against the information set decoding attack, and also has a number of inaccuracies. It is shown that the time of key generation and decryption in modern cryptosystems is quite large, and the public and private keys take up a large amount of memory. The inaccuracies of the considered schemes revealed in this work can be used to improve and adjust the systems, as well as to build a more accurate assessment of their security level and efficiency. The presented cryptosystems can be considered as standards for post-quantum cryptography and can be used to protect data after development of powerful quantum computers.

Code-based cryptosystems are promising candidates for post-quantum cryptography. Recently, generalized concatenated codes over Gaussian and Eisenstein integers were proposed for those systems. For a channel model with errors of restricted weight, those q-ary codes lead to high error correction capabilities. Hence, these codes achieve high work factors for information set decoding attacks. In this work, we adapt this concept to codes for the weight-one error channel, i.e., a binary channel model where at most one bit-error occurs in each block of $m$ bits. We also propose a low complexity decoding algorithm for the proposed codes. Compared to codes over Gaussian and Eisenstein integers, these codes achieve higher minimum Hamming distances for the dual codes of the inner component codes. This property increases the work factor for a structural attack on concatenated codes leading to higher overall security. For comparable security, the key size for the proposed code construction is significantly smaller than for the classic McEliece scheme based on Goppa codes.

Code-based cryptography is a promising candidate for post-quantum cryptography due to its strong security guarantees and efficient implementations. In this paper, we explore the use of code-based cryptography for multi-party computation and digital signatures, two important cryptographic applications. We present several efficient and secure code-based protocols for these applications, based on the McEliece cryptosystem and its variants. Our protocols offer strong security guarantees against both classical and quantum attacks, and have competitive performance compared to other post-quantum cryptographic schemes. We also compare code-based cryptography with other post-quantum schemes, including lattice-based and hash-based cryptography, and discuss the advantages and disadvantages of each approach.

The McEliece cryptosystem based on quasi-cyclic moderate-density parity-check with adaptive chosen-ciphertext attack conversion is secure against information set decoding and message-resend attacks. However, it is vulnerable to reaction based key recovery attacks and cannot be implemented over the noise channel. To overcome this problem, we propose an improved McEliece cryptosystem based on quasi-cyclic quasi moderate-density parity-check (QC-QMDPC). In this cryptosystem, a stamp generation function which is based on the pseudorandom sequence is designed to resist the message-resend attack. The random channel noise is employed to enhance security. Furthermore, the upper bound of the density of QC-QMDPC code is proved for optimal efficiency. The index-based storage technique is proposed so that the key size can be reduced to approximately quadruple code length. The encoding and decoding algorithms are optimized to reduce the computational cost on the hardware platform. We analyze the performance of the proposed cryptosystem and compare it with other McEliece cryptosystems. The results show that the proposed cryptosystem is secure against critical attacks while keeping high error correction ability and efficiency. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing a cryptosystem with a public key based on error-resistant coding. At present, this type of cryptosystems is believed to be able to resist the advent of quantum computers and can be considered as a method of post-quantum cryptography. The main drawback of a code-based cryptosystem is a great length of the public key. Most papers devoted to reducing the cryptosystem key length consisted in replacing the Goppa codes used in the original cryptosystem with some other codes with a requirement that the system remains secure against attacks by a quantum computer. Here we propose another approach to the key length reduction that is stated as a task of a simple description of an error set which has either errors of weights greater than half the minimum distance or errors that cannot be corrected without an additional secret knowledge. If a code structure allows to give such a description of an error set, then the complexity of most attacks (for instance, information-set decoding) significantly increases. [ABSTRACT FROM AUTHOR]

Recently, Horlemann-Trautmann and Weger (Adv Math Commun, https://doi.org/10.3934/amc.2020089, 2020) proposed a general framework for a Quaternary McEliece cryptosystem over the ring Z 4 , and generalized the construction over the ring Z p m where p is a prime integer. By considering the Lee metric, the public key size for the McEliece cryptosystems can be substantially smaller than their counterparts in the Hamming metric. Furthermore, the hardness of the McEliece cryptosystems over Z p m is based on the Lee Syndrome Decoding problem, which was shown to be NP-complete. This paper aims to analyze the design and security of the Lee metric McEliece cryptosystem over Z p m in the Lee metric. We derive some necessary conditions for the quaternary codes used in the Lee metric McEliece cryptosystem, and show that the theoretical quaternary codes proposed in (Adv Math Commun, https://doi.org/10.3934/amc.2020089, 2020) do not exist. Furthermore, we propose a plaintext recovery attack on the Lee metric McEliece cryptosystem over Z p m , when the minimum Lee distance of the underlying codes with certain structures is greater than twice the Lee weight of the error. Our plaintext recovery attack is applicable to the cryptosystems over Z p m when m > 1 . We apply our plaintext recovery attack on the Quaternary McEliece cryptosystem, and manage to recover partial plaintext of length k 1 within O 2 min { k 1 , 0.0473 n } operations, where n is the length of ciphertext. Hence, the proposed theoretical parameters for the Quaternary McEliece over Z 4 in (Adv Math Commun, https://doi.org/10.3934/amc.2020089, 2020) do not achieve 128-bit security, as we can recover the partial plaintext within 0.591 s. This also implies that the use of quaternary codes in the McEliece cryptosystem may not reduce the public key size significantly. Furthermore, for some parameters of the Lee metric McEliece cryptosystems over Z 4 , our plaintext recovery attack can be more efficient than the Lee-Brickell's and Stern's Information Set Decoding Algorithm over Z 4 . [ABSTRACT FROM AUTHOR]

In this paper, the already strong McEliece cryptosystem is enhanced with atwo-dimensional finite Gaussian integer. By substituting the one-dimensional linear code with atwo-dimensional code employing afinite Gaussian integer, anew system simultaneously increases the key space and the errors to be correct by syndrome decoding. We compare the proposed system against the classic McEliece system in three aspects: the work factors performing the trial of the attacks, the computationalcomplexity cost, and the empirical running time of the system. Comparedto the classic McEliece cryptosystem,the enhanced cryptosystem achieves a higher security level against key recovering and decoding attacks. By carefully selecting parameters, asmall code element can improve the key strength without compromising the runtime efficiency.

To extend the transmission distance and/or improve secret-key rate of QKD protocols, we propose to employ the joint QKD-post-quantum cryptosystems in which QKD is used for raw-key transmission while the post-quantum cryptography (PQC) subsystem to transmit parity bits for information reconciliation. We also describe a run-time configurable spatially coupled (SC)-LDPC code, derived from template quasi cyclic (QC)-LDPC, suitable for use in both information reconciliation and McEliece crypto-subsystem. For twin-field (TF)-QKD subsystem, the proposed joint cryptosystem, which takes the complexity of algorithm used to break the PQC subsystem into account, is able to achieve record distance of 1238 km over ultra-low-loss fiber.

Recently, Ivanov, Kabatiansky, Krouk, and Rumenko (IKKR) proposed three new variants of the McEliece cryptosystem (CBCrypto 2020, affiliated with Eurocrypt 2020). In this letter, it is shown that one of the IKKR cryptosystems is equal to the McEliece cryptosystem. Furthermore, a polynomial-time attack algorithm for the other two IKKR cryptosystems is proposed. The proposed attack algorithm utilizes the linearity of IKKR cryptosystems. Also, an implementation of the IKKR cryptosystems and the proposed attack is given. The proposed attack algorithm finds the plaintext within 0.2 sec that is faster than the elapsed time for legitimate decryption. [ABSTRACT FROM AUTHOR]

Twisted Reed–Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed–Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic key-recovery methods. In this paper, an efficient key-recovery attack on the TRS variant that was used in the McEliece cryptosystem is presented. The algorithm exploits a new approach based on recovering the structure of a well-chosen subfield subcode of the public code. It is proved that the attack always succeeds and breaks the system for all practical parameters in O (n 4) field operations. A software implementation of the algorithm retrieves a valid private key from the public key within a few minutes, for parameters claiming a security level of 128 bits. The success of the attack also indicates that, contrary to common beliefs, subfield subcodes of the public code need to be precisely analyzed when proposing a McEliece-type code-based cryptosystem. Finally, the paper discusses an attempt to repair the scheme and a modification of the attack aiming at Gabidulin–Paramonov–Tretjakov cryptosystems based on twisted Gabidulin codes. [ABSTRACT FROM AUTHOR]

In this paper, the already strong McEliece cryptosystem is enhanced with a two-dimensional finite Gaussian integer. By substituting the one-dimensional linear code with a two-dimensional code employing a finite Gaussian integer, a new system simultaneously increases the key space and the errors to be correct by syndrome decoding. We compare the proposed system against the classic McEliece system in three aspects: the work factors performing the trial of the attacks, the computational complexity cost, and the empirical running time of the system. Compared to the classic McEliece cryptosystem, the enhanced cryptosystem achieves a higher security level against key recovering and decoding attacks. By carefully selecting parameters, a small code element can improve the key strength without compromising the runtime efficiency. [ABSTRACT FROM AUTHOR]

As shown by N. Sendrier in 2000, if a -linear code with length , dimensionality and code distance has a trivial group of automorphisms , it allows one to construct a determined support splitting algorithm in order to find a permutation for a code , being permutation-equivalent to the code , such that . This algorithm can be used for attacking the McEliece cryptosystem based on the code . This work aims the construction and analysis of the support splitting algorithm for the code , induced by the code , . Since the group of automorphisms PAut is nontrivial even in the case of that trivial for the base code , it enables one to assume a potentially high resistance of the McEliece cryptosystem on the code to the attack based on a carrier split. The support splitting algorithm is being constructed for the code and its efficiency is compared with the attack to a McEliece cryptosystem based on the code [ABSTRACT FROM AUTHOR]

The code-based McEliece and Niederreiter cryptosystems are promising candidates for post-quantum public-key encryption. Recently, q-ary concatenated codes over Gaussian integers were proposed for the McEliece cryptosystem, together with the one-Mannheim error channel, where the error values are limited to the Mannheim weight one. Due to the limited error values, the codes over Gaussian integers achieve a higher error correction capability than maximum distance separable (MDS) codes with bounded minimum distance decoding. This higher error correction capability improves the work factor regarding decoding attacks based on information-set decoding. The codes also enable a low complexity decoding algorithm for decoding beyond the guaranteed error correction capability. In this work, we extend this coding scheme to codes over Eisenstein integers. These codes have advantages for the Niederreiter system. Additionally, we propose an improved code construction based on generalized concatenated codes. These codes extend to the rate region, where the work factor is beneficial compared to MDS codes. Moreover, generalized concatenated codes are more robust against structural attacks than ordinary concatenated codes.

The McEliece cryptosystem is a promising candidate for post-quantum public-key encryption. In this work, we propose q-ary codes over Gaussian integers for the McEliece system and a new channel model. With this one Mannheim error channel, errors are limited to weight one. We investigate the channel capacity of this channel and discuss its relation to the McEliece system. The proposed codes are based on a simple product code construction and have a low complexity decoding algorithm. For the one Mannheim error channel, these codes achieve a higher error correction capability than maximum distance separable codes with bounded minimum distance decoding. This improves the work factor regarding decoding attacks based on information-set decoding.