Search

An efficient evaluation method is described for polynomials in finite fields. Its complexity is shown to be lower than that of standard techniques, when the degree of the polynomial is large enough compared to the field characteristic. Specifically, if n is the degree of the polynomiaI, the asymptotic complexity is shown to be O(root n), versus O(n) of classical algorithms. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted. more...

In this paper we study spread codes: a family of constant-dimension codes for random linear network coding. In other words, the codewords are full-rank matrices of size k×n with entries in a finite field Fq. Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires O((n−k)k3) operations over an extension field Fqk. Our algorithm is more efficient than the previous ones in the literature, when the dimension k of the codewords is small with respect to n. The decoding algorithm takes advantage of the algebraic structure of the code, and it uses original results on minors of a matrix and on the factorization of polynomials over finite fields. more...

Secure storage of noisy data for authentication purposes usually involves the use of error correcting codes. We propose a new model scenario involving burst errors and present for that several constructions. more...

A method is described which allows to evaluate efficiently a polynomial in a (possibly trivial) extension of the finite field of its coefficients. Its complexity is shown to be lower than that of standard techniques when the degree of the polynomial is large with respect to the base field. Applications to the syndrome computation in the decoding of cyclic codes, Reed-Solomon codes in particular, are highlighted. more...

Orbit codes are a family of codes employable for communications on a random linear network coding channel. The paper focuses on the classification of these codes. We start by classifying the conjugacy classes of cyclic subgroups of the general linear group. As a result, we are able to focus the study of cyclic orbit codes to a restricted family of them. more...

The last decades have seen a growing interest in hash functions that allow some sort of tolerance, e.g. for the purpose of biometric authentication. Among these, the syndrome fuzzy hashing construction allows to securely store biometric data and to perform user authentication without the need of sharing any secret key. This paper analyzes such a model, showing that it offers a suitable protection against information leakage and several advantages with respect to similar solutions, like the fuzzy commitment scheme. The design and characterization of LDPC codes to be used for this purpose is also addressed. more...

We propose a new variant of the McEliece cryptosystem which ensures that the code used as the public key is not permutation-equivalent to the secret code. This allows to increase the security of the public key, and to reconsider possible adoption of classical families of codes, like Reed-Solomon codes. A reduction in the key size or, equivalently, an increased level of security against information set decoding are the main advantages of the modified cryptosystem. As a drawback, the domain of intentional error vectors must be restricted, but we show that this has no significant impact on the security level. more...

Constant dimension codes are subsets of the nite Grassmann variety. The study of constant dimension codes with good distances have been central in random linear network coding theory. Orbit codes represent a subclass of constant dimension codes. They are characterized that the elements of the code can be viewed as the orbit under a group action. The paper gives a complete characterization of orbit codes that are generated by an irreducible cyclic group, i.e. an irreducible group having one generator. We show how some of the basic properties of these codes, the cardinality and the minimum distance, can be derived using the isomorphism of the vector space and the extension field. more...

This paper studies the decoding capabilities of maximum distance profile (MDP) convolutional codes over the erasure channel and compares them with the decoding capabilities of MDS block codes over the same channel. The erasure channel involving large alphabets is an important practical channel model when studying packet transmissions over a network, e.g, the Internet. more...

In this paper we introduce the class of spread codes for the use in random network coding. Spread codes are based on the construction of spreads in finite projective geometry. The major contribution of the paper is an efficient decoding algorithm of spread codes up to half the minimum distance. more...

People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation ∗ : S × S → S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x ∗ y of single pairs (x, y) ∈ S2 you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x ∗ y for all x, y ∈ S? This problem can trivially be solved by using |S|2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries. In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that ∗ is an abelian group operation. We also investigate black box rings and give lower und upper bounds for the number of queries needed to solve product recovering in this case. more...

Technological advance causes obsolescence and unpredictable lifetimes of digital storage media and systems. We present PEVIAR, a digital archival solution based on microfilm that offers superior lifetime and independence from proprietary hardware and software technologies. Digital data is to be stored as a 2-dimensional raster image. In order to determine the technical parameters of our system, we carry out an investigation of the device setup given by a recorder, the film itself and a scanner. We measure the modulation transfer function of these components and the granularity of the film material. We also propose a 2-dimensional channel model incorporating intersymbol interference. From our examinations we conclude that a resolution of 8µm can be achieved. more...

This paper studies the problem of pole assignment for symmetric and Hamiltonian transfer functions. A necessary and sufficient condition for pole assignment by complex symmetric output feedback transformations is given. Moreover, in the case where the McMillan degree coincides with the number of parameters appearing in the symmetric feedback transformations, we derive an explicit combinatorial formula for the number of pole assigning symmetric feedback gains. The proof uses intersection theory in projective space as well as a formula for the degree of the complex Lagrangian Grassmann manifold. more...

A generalization of the original Diffie-Hellman key exchange in ∕* found a new depth when Miller [27] and Koblitz [16] suggested that such a protocol could be used with the group over an elliptic curve. In this paper, we propose a further vast generalization where abelian semigroups act on finite sets. We define a Diffie-Hellman key exchange in this setting and we illustrate how to build interesting semigroup actions using finite (simple) semirings. The practicality of the proposed extensions rely on the orbit sizes of the semigroup actions and at this point it is an open question how to compute the sizes of these orbits in general and also if there exists a square root attack in general. In Section 5 a concrete practical semigroup action built from simple semirings is presented. It will require further research to analyse this system. more...