Abstract A ROM IND-CCA2 Key Encapsulation Mechanism (KEM) supported by a Public Key Encryption (PKE) scheme based on the Weighted Modular Subset Sum Problem (WMSSP) is proposed. Concretely, it is proven that for certain sets of integers, whose inverses modulo a large predetermined integer have bounded bit size, an algorithm based on a truncated version of the extended Euclidean algorithm can effectively solve the WMSSP. The security analysis is conducted through the connection established between the Binary Subset Sum Problem and the Shortest Vector Problem. Various attacks against our proposal, relying on the computation of a shortest vector, have been analyzed. It is widely accepted that the problem supporting the security of this cryptosystem exhibits resilience against quantum threats. Moreover, the key generation and encryption-decryption processes exhibit remarkable time efficiency, as they rely exclusively on basic integer arithmetic.

Abstract A class of linear codes that extends classical Goppa codes to a non-commutative context is defined. An efficient decoding algorithm, based on the solution of a non-commutative key equation, is designed. We show how the parameters of these codes, when the alphabet is a finite field, may be adjusted to propose a McEliece-type cryptosystem.

A large class of MDS linear codes is constructed. These codes are endowed with an efficient decoding algorithm. Both the definition of the codes and the design of their decoding algorithm only require from Linear Algebra methods, making them fully accessible for everyone. Thus, the first part of the paper develops a direct presentation of the codes by means of parity-check matrices, and the decoding algorithm rests upon matrix and linear maps manipulations. The somewhat more sophisticated mathematical context (non-commutative rings) needed for the proof of the correctness of the decoding algorithm is postponed to the second part. A final section locates the Reed-Solomon skew-differential codes introduced here within the general context of codes defined by means of skew polynomial rings.

We show that, for cyclic convolutional codes, it is possible to compute a sequence of positive integers, called cyclic column distances, which presents a more regular behavior than the classical column distances sequence. We then design an algorithm for the computation of the free distance based on the calculation of this cyclic column distances sequence.

In this paper, an application of the theoretical algebraic notion of a separable ring extension in the realm of cyclic convolutional codes or, more generally, ideal codes, is investigated. It is worked under very mild conditions that cover all previously known as well as new non-trivial examples. It is proved that ideal codes are direct summands, as left ideals, of the underlying non-commutative algebra, in analogy with cyclic block codes. This implies, in particular, that they are generated by a non-commutative idempotent polynomial. Hence, by using a suitable separability element, an efficient algorithm for computing one of such idempotents is designed. We show that such an idempotent generator polynomial can be used to get information on the free distance of the convolutional code.

We propose a decoding algorithm for a class of convolutional codes called skew Reed-Solomon convolutional codes. These are convolutional codes of designed Hamming distance endowed with a cyclic structure yielding a left ideal of a non-commutative ring (a quotient of a skew polynomial ring). In this setting, right and left division algorithms exist, so our algorithm follows the guidelines of the Sugiyama's procedure for finding the error locator and error evaluator polynomials for Goppa block codes.

In this paper, we propose a new way of providing cyclic structures to convolutional codes. We define the skew cyclic convolutional codes as left ideals of a quotient ring of a suitable non-commutative polynomial ring. In contrast to the previous approaches to cyclicity for convolutional codes, we use Ore polynomials with coefficients in a field (the rational function field over a finite field), so their arithmetic is very well known and we may proceed similarly to cyclic block codes. In particular, we show how to obtain easily skew cyclic convolutional codes of a given dimension, and we compute an idempotent generator of the code and its dual.

Let (F ⊆ K) an extension of finite fields and (A = Mn K) be the ring of square matrices of order n over (K) viewed as an algebra over (F). Given an (F)--automorphism (σ) on (A) the Ore extension (A[z;σ]) may be used to built certain convolutional codes, namely, the ideal codes. We provide an algorithm to decide if the automorphism (σ) on (A) is a separable returning the corresponding separability element (p). In this case (p) is also a separability element for the extension (F[z] ⊆ A[z;σ]), and as a consequence ideal codes are generated by idempotents in (A[z;σ]), which can be computed applying previous algorithms of the authors.

Let R be an Ore extension of a skew-field. A basic computational problem is to decide effectively whether two given Ore polynomials f, g ∈ R (of the same degree) are similar, that is, if there exists an isomorphism of left R--modules between R/Rf and R/Rg. Since these modules are of finite length, we consider the more general problem of deciding when two given left R--modules of finite length are isomorphic. We show that if R is free of finite rank as a module over its center C, then this problem can be reduced to check the existence of an isomorphism of C--modules. This method works for a large class of left R--modules of finite length. Our result is proven in the realm of non-commutative principal ideal domains, and generalizes a result by Jacobson for some Ore extensions of a skew field by an automorphism. As a consequence, we propose an algorithm to check whether two given left R--modules of finite length are isomorphic by associating a matrix with coefficients in C to each of the modules, and checking if the corresponding rational canonical forms are equal. Our method is illustrated with examples of computations for Ore extensions of finite fields, and of the Hamilton quaternions.