Search

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]

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]

The McEliece cryptosystem based on rank-metric codes is presented to offer both security and error-correction simultaneously in random network coding system. In the multicast network, the original messages are encoded with McEliece cryptosystem based on Gabidulin codes. Key distribution will be done one time. The rank codes decoding is performed in the sink. As long as t < d R C / 2 , the decoding is guaranteed, where t is the number of corrupted packets and d R C is the minimum rank distance of the rank codes C. Original messages are protected based on the cryptosystem. Compared with the rate n - μ - 2 t in traditional SEC network codes, the rate approaches n - 2 t where μ is the number of eavesdroppers. The rate won't decrease as the number of eavesdropped edges increases. [ABSTRACT FROM AUTHOR]

The McEliece cryptosystem based on quasi-cyclic low-density parity check (QC-LDPC) codes is presented to offer both security and error-correction simultaneously in the determined network coding system. The characteristics of the cryptosystem make it does not need to reduce information rate additionally to offer security. The messages u is encoded into x with QC-LDPC. x is transmitted through a network where a network coding error-correcting scheme is performed. ρ links are observed by the adversary and t errors occur in the network. The characteristic of MDS code make the errors cannot be spread, therefore, the corrupted packets which occur in t links will cause at most t errors in the received messages in the sink. As long as the number of errors occuring in the intermediate links will not exceed the minimum distance of QC-LDPC codes, the hybrid scheme can perform error-correcting and security simultaneously. The information rate reaches n - 2 t instead of n - μ - 2 t where n is the max-flow min-cut. [ABSTRACT FROM AUTHOR]

In this article, the authors propose a new version of the McEliece cryptosystem based on the Smith form of convolutional codes. They use the Smith form to hide a part of the code in the public matrix, and they leave the other part secret. The secret part will then be used for decryption. They hide this part by multiplying it on the left by a random matrix, and they add a random matrix which has a few conditions. Their scheme has a small public key size compared to the original McEliece scheme and resists the unique decoding attack against convolutional structure presented at the conference PQCrypto 2013 by Landais and Tillich. Further, the exhaustive search attack is infeasible on their system. [ABSTRACT FROM AUTHOR]

We present a polynomial-time structural attack against the McEliece system based on Wild Goppa codes defined over a quadratic finite field extension. We show that such codes can be efficiently distinguished from random codes. The attack uses this property to compute a filtration, that is to say, a family of nested subcodes which will reveal their secret algebraic description. [ABSTRACT FROM PUBLISHER]

Goppa codes were defined by Valery D. Goppa in 1970. In 1978, Robert J. McEliece used this family of error-correcting codes in his cryptosystem, which has gained popularity in the last decade due to its resistance to attacks from quantum computers. In this paper, we present Goppa codes over the p -adic integers and integers modulo p e. This allows the creation of chains of Goppa codes over different rings. We show some of their properties, such as parity-check matrices and minimum distance, and suggest their cryptographic application, following McEliece's scheme. [ABSTRACT FROM AUTHOR]

The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non-trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes. We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has no symmetry anymore. This result is obtained thanks to an operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold. The reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (respectively, Goppa) code provides the dual of an alternant (respectively, Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of Berger and Dür). This enables not only to present a unified view but also to generalize the construction of QC, QD, and even quasi-monoidic Goppa codes. Finally, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks. [ABSTRACT FROM PUBLISHER]

Code-based cryptography is one of the significant research direction in the quantum cryptography era. Except the quantum attack resistance, it has many other strong features compared with classical cryptography. First, the security reductions are tight. Also, the system is very fast, as both encryption and decryption procedures have a low complexity. Therefore, this paper studied code-based signcryption scheme, and combined McEliece encryption scheme with slightly modified versions of Xinmei signature scheme, then proposed a signcryption scheme based on McEliece public-key cryptography. This paper discussed the solution efficiency analysis. Compared with the first signature and then encryption method, the scheme upon completion of the signature and encryption at the same time, make the length of the private key as well as the ciphertext are reduced by 7.4% and 50%. Meanwhile, this paper studied the provable security of the scheme, and show that signcryption scheme has high security. [ABSTRACT FROM AUTHOR]

McEliece cryptosystem is an public-key cryptosystem; its security is based on the complexity of decoding problem for an arbitrary error-correcting code. V. M. Sidel'nikov in 1994 suggested to construct the cryptosystem on the base of binary Reed-Muller code. In 2007 L. Minder and A. Shokrollahi had designed a structural attack on theMcEliece cryptosystem based on the Reed-Muller codes.Herewe improve their attack and suggest a polynomial attack on the McEliece cryptosystem based on Reed-Muller codes RM(r, m) such that GCD(r,m − 1) = 1. [ABSTRACT FROM AUTHOR]

The McEliece cryptosystem is defined using a Goppa code, and decoding the Goppa code is a crucial step of its decryption. Patterson's decoding algorithm is the best known algorithm for decoding Goppa codes. Currently, the most efficient implementation of Patterson's algorithm uses a precomputation. In this paper, we modify Patterson's decoding algorithm so that one can remove the precomputation part while sustaining the best efficiency. Precomputations yield additional storage requirement to store the precomputed value which increases as the security level increases in McEliece cryptosystem. In the original decoding algorithm of Patterson, computing square root in a quotient field of polynomial ring over a finite field is necessary. In our modification, the computations are involved only in the arithmetics of polynomial ring over a finite field, not in the quotient field. This achieves better efficiency because one can remove polynomial reductions in the computations of quotient field. [ABSTRACT FROM AUTHOR]

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. It appears that this dimension depends on the type of code considered. Explicit formulas derived from extensive experimentations for the rank are provided for “generic” random, alternant, and Goppa codes over any field. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes. [ABSTRACT FROM AUTHOR]

In 1985, Gabidulin introduced the rank metric in coding theory over finite fields, and used this kind of codes in a McEliece cryptosystem, six years later. In this paper, we consider rank metric codes over Galois rings. We propose a suitable metric for codes over such rings, and show its main properties. With this metric, we define Gabidulin codes over Galois rings, propose an efficient decoding algorithm for them, and hint their cryptographic application. [ABSTRACT FROM AUTHOR]

In this correspondence, iteration-1 of bit flipping decoding based on a set of nonorthogonal check sums is analyzed for both regular and irregular models. In particular, the tradeoff between the Hamming weight (and overlapping) of the check sums and the number of redundant check sums required to start converging under iterative decoding is investigated. The model is then applied to an iterative attack of McEliece public-key cryptosystem since a successful attack of this system can be achieved by algebraic bounded distance decoding of a random code. Based on this model, the attack can be decomposed into two phases: a preprocessing phase which, for one particular key κ, consists of finding a sufficiently large set S of check sums up to a certain Hamming weight, and a bit flipping decoding phase which uses the set S for each message encrypted with the key κ. [ABSTRACT FROM AUTHOR]

In 1991, Gabidulin, Paramonov and Tretjakov presented a public key cryptosystem of the McEliece type based on rank codes correcting array errors, the GPT system. Making use of rank codes in cryptographic applications is advantageous since it is practically impossible to utilize combinatoric decoding. This enabled using public keys of a smaller size.Subsequently, in a series of works Gibson developed attacks that break the GPT system for public keys of about 5 Kbits.In this paper, we present a new PKC based on the idea of a column scrambler—a non-singular matrix by which the public key is multiplied to the right. The column scrambler ‘mixes’ columns of the public key. It makes system more resistant to structural attacks at a little extra cost of a few additional columns. Possible attacks are carefully studied. The system is found to be secure against known attacks for public keys greater than 10 Kbits. [Copyright &y& Elsevier]

We define a family of codes called twisted Hermitian codes, which are based on Hermitian codes and inspired by the twisted Reed–Solomon codes described by Beelen, Puchinger, and Nielsen. We demonstrate that these new codes can have high-dimensional Schur squares, and we identify a subfamily of twisted Hermitian codes that achieves a Schur square dimension close to that of a random linear code. Twisted Hermitian codes allow one to work over smaller alphabets than those based on Reed–Solomon codes of similar lengths. [ABSTRACT FROM AUTHOR]

In Goppa (1970), V. D. Goppa presents a new family of linear codes over finite fields. This family, now known as Goppa codes, has been studied for nearly 50 years, including efficient decoding algorithms (Patterson, 1975) and its applications in cryptography (McEliece, 1978). Moreover, in Andrade et al. (2005), de Andrade and Palazzo present a generalization of Goppa codes to finite rings. Motivated by cryptographic applications, in this article we focus on Goppa codes over Z ∕ 4 Z and study some of their properties. [ABSTRACT FROM AUTHOR]

The McEliece public-key cryptosystem relies on the NP-hard decoding problem, and therefore, is regarded as a solution for postquantum cryptography. Though early known, this cryptosystem was not employed so far because of efficiency questions regarding performance and communication overhead. This paper presents a novel processor architecture as a high-performance platform to execute key generation, encryption, and decryption according to this cryptosystem. A prototype of this processor is realized on a reconfigurable device and tested via a dedicated software interface. A comparison with a similar software solution highlights the performance advantage of the proposed hardware solution. [ABSTRACT FROM PUBLISHER]