BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Joachim Rosenthal

Joachim Rosenthal appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITCryptography and Securitymath.NTmath.AGmath.COComputational Complexitymath.DSmath.GRmath.OC

Catalog footprint

What is connected

39works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

39 published item(s)

preprint2022arXiv

A Deterministic Algorithm for the Discrete Logarithm Problem in a Semigroup

The discrete logarithm problem in a finite group is the basis for many protocols in cryptography. The best general algorithms which solve this problem have time complexity of $\mathcal{O}(\sqrt{N}\log N)$, and a space complexity of $\mathcal{O}(\sqrt{N})$ where $N$ is the order of the group. (If $N$ is unknown, a simple modification would achieve a time complexity of $\mathcal{O}(\sqrt{N}(\log N)^2)$.) These algorithms require the inversion of some group elements or rely on finding collisions and the existence of inverses, and thus do not adapt to work in the general semigroup setting. For semigroups, probabilistic algorithms with similar time complexity have been proposed. The main result of this paper is a deterministic algorithm for solving the discrete logarithm problem in a semigroup. Specifically, let $x$ be an element in a semigroup having finite order $N_x$. The paper provides an algorithm, which, given any element $y\in \langle x \rangle $, provides all natural numbers $m$ with $x^m=y$, and has time complexity $O(\sqrt{N_x}(\log N_x)^2)$ steps. The paper also gives an analysis of the success rates of the existing probabilistic algorithms, which were so far only conjectured or stated loosely.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Convolutional codes over finite chain rings, MDP codes and their characterization

In this paper, we develop the theory of convolutional codes over finite commutative chain rings. In particular, we focus on maximum distance profile (MDP) convolutional codes and we provide a characterization of these codes, generalizing the one known for fields. Moreover, we relate (reverse) MDP convolutional codes over a finite chain ring with (reverse) MDP convolutional codes over its residue field. Finally, we provide a construction of (reverse) MDP convolutional codes over finite chain rings generalizing the notion of (reverse) superregular matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Description of some Classes of Codes using Group Algebras

Circulant matrices are an important tool widely used in coding theory and cryptography. A circulant matrix is a square matrix whose rows are the cyclic shifts of the first row. Such a matrix can be efficiently stored in memory because it is fully specified by its first row. The ring of $n \times n$ circulant matrices can be identified with the quotient ring $\mathbb{F}[x]/(x^n-1)$. In consequence, the strong algebraic structure of the ring $\mathbb{F}[x]/(x^n-1)$ can be used to study properties of the collection of all $n\times n$ circulant matrices. The ring $\mathbb{F}[x]/(x^n-1)$ is a special case of a group algebra and elements of any finite dimensional group algebra can be represented with square matrices which are specified by a single column. In this paper we study this representation and prove that it is an injective Hamming weight preserving homomorphism of $\mathbb{F}$-algebras and classify it in the case where the underlying group is abelian. Our work is motivated by the desire to generalize the BIKE cryptosystem (a contender in the NIST competition to get a new post-quantum standard for asymmetric cryptography). Group algebras can be used to design similar cryptosystems or, more generally, to construct low density or moderate density parity-check matrices for linear codes.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Existence and Cardinality of $k$-Normal Elements in Finite Fields

Normal bases in finite fields constitute a vast topic of large theoretical and practical interest. Recently, $k$-normal elements were introduced as a natural extension of normal elements. The existence and the number of $k$-normal elements in a fixed extension of a finite field are both open problems in full generality, and comprise a promising research avenue. In this paper, we first formulate a general lower bound for the number of $k$-normal elements, assuming that they exist. We further derive a new existence condition for $k$-normal elements using the general factorization of the polynomial $x^m-1$ into cyclotomic polynomials. Finally, we provide an existence condition for normal elements in $\fqm$ with a non-maximal but high multiplicative order in the group of units of the finite field.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Properties of Error Patterns in the Constant Lee Weight Channel

The problem of scalar multiplication applied to vectors is considered in the Lee metric. Unlike in other metrics, the Lee weight of a vector may be increased or decreased by the product with a nonzero, nontrivial scalar. This problem is of particular interest for cryptographic applications, like for example Lee metric code-based cryptosystems, since an attacker may use scalar multiplication to reduce the Lee weight of the error vector and thus to reduce the complexity of the corresponding generic decoder. The scalar multiplication problem is analyzed in the asymptotic regime. Furthermore, the construction of a vector with constant Lee weight using integer partitions is analyzed and an efficient method for drawing vectors of constant Lee weight uniformly at random from the set of all such vectors is given.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Construction of LDPC convolutional codes via difference triangle sets

In this paper, a construction of $(n,k,δ)$ LDPC convolutional codes over arbitrary finite fields, which generalizes the work of Robinson and Bernstein and the later work of Tong is provided. The sets of integers forming a $(k,w)$-(weak) difference triangle set are used as supports of some columns of the sliding parity-check matrix of an $(n,k,δ)$ convolutional code, where $n\in\mathbb{N}$, $n>k$. The parameters of the convolutional code are related to the parameters of the underlying difference triangle set. In particular, a relation between the free distance of the code and $w$ is established as well as a relation between the degree of the code and the scope of the difference triangle set. Moreover, we show that some conditions on the weak difference triangle set ensure that the Tanner graph associated to the sliding parity-check matrix of the convolutional code is free from $2\ell$-cycles not satisfying the full rank condition over any finite field. Finally, we relax these conditions and provide a lower bound on the field size, depending on the parity of $\ell$, that is sufficient to still avoid $2\ell$-cycles. This is important for improving the performance of a code and avoiding the presence of low-weight codewords and absorbing sets.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Construction of Rate (n-1)/n Non-Binary LDPC Convolutional Codes via Difference Triangle Sets

This paper provides a construction of non-binary LDPC convolutional codes, which generalizes the work of Robinson and Bernstein. The sets of integers forming an $(n-1,w)$-difference triangle set are used as supports of the columns of rate $(n-1)/n$ convolutional codes. If the field size is large enough, the Tanner graph associated to the sliding parity-check matrix of the code is free from $4$ and $6$-cycles not satisfying the full rank condition. This is important for improving the performance of a code and avoiding the presence of low-weight codewords and absorbing sets. The parameters of the convolutional code are shown to be determined by the parameters of the underlying difference triangle set. In particular, the free distance of the code is related to $w$ and the degree of the code is linked to the "scope" of the difference triangle set. Hence, the problem of finding families of difference triangle set with minimum scope is equivalent to find convolutional codes with small degree.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Erasure decoding of convolutional codes using first order representations

In this paper, we employ the linear systems representation of a convolutional code to develop a decoding algorithm for convolutional codes over the erasure channel. We study the decoding problem using the state space description and this provides in a natural way additional information. With respect to previously known decoding algorithms, our new algorithm has the advantage that it is able to reduce the decoding delay as well as the computational effort in the erasure recovery process. We describe which properties a convolutional code should have in order to obtain a good decoding performance and illustrate it with an example.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Encryption Scheme Based on Expanded Reed-Solomon Codes

We present a code-based public-key cryptosystem, in which we use Reed-Solomon codes over an extension field as secret codes and disguise it by considering its shortened expanded code over the base field. Considering shortened expanded codes provides a safeguard against distinguisher attacks based on the Schur product. Moreover, without using a cyclic or a quasi-cyclic structure we obtain a key size reduction of nearly $45 \%$ compared to the classic McEliece cryptosystem proposed by Bernstein et al.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Group key management based on semigroup actions

In this work we provide a suite of protocols for group key management based on general semigroup actions. Construction of the key is made in a distributed and collaborative way. Examples are provided that may in some cases enhance the security level and communication overheads of previous existing protocols. Security against passive attacks is considered and depends on the hardness of the semigroup action problem in any particular scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Managing key multicasting through orthogonal systems

In this paper we propose a new protocol to manage multicast key distribution. The protocol is based on the use of orthogonal systems in vector spaces. The main advantage in comparison to other existing multicast key management protocols is that the length and the number of the messages which have to be sent are considerably smaller. This makes the protocol especially attractive when the number of legitimate receivers is large.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Subspace Fuzzy Vault

Fuzzy vault is a scheme providing secure authentication based on fuzzy matching of sets. A major application is the use of biometric features for authentication, whereby unencrypted storage of these features is not an option because of security concerns. While there is still ongoing research around the practical implementation of such schemes, we propose and analyze here an alternative construction based on subspace codes. This offers some advantages in terms of security, as an eventual discovery of the key does not provide an obvious access to the features. Crucial for an efficient implementation are the computational complexity and the choice of good code parameters. The parameters depend on the particular application, e.g. the biometric feature to be stored and the rate one wants to allow for false acceptance. The developed theory is closely linked to constructions of subspace codes studied in the area of random network coding.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Enhanced public key security for the McEliece cryptosystem

This paper studies a variant of the McEliece cryptosystem able to ensure that the code used as the public key is no longer permutation-equivalent to the secret code. This increases the security level of the public key, thus opening the way for reconsidering the adoption of classical families of codes, like Reed-Solomon codes, that have been longly excluded from the McEliece cryptosystem for security reasons. It is well known that codes of these classes are able to yield a reduction in the key size or, equivalently, an increased level of security against information set decoding; so, these are the main advantages of the proposed solution. We also describe possible vulnerabilities and attacks related to the considered system, and show what design choices are best suited to avoid them.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the Geometry of Balls in the Grassmannian and List Decoding of Lifted Gabidulin Codes

The finite Grassmannian $\mathcal{G}_{q}(k,n)$ is defined as the set of all $k$-dimensional subspaces of the ambient space $\mathbb{F}_{q}^{n}$. Subsets of the finite Grassmannian are called constant dimension codes and have recently found an application in random network coding. In this setting codewords from $\mathcal{G}_{q}(k,n)$ are sent through a network channel and, since errors may occur during transmission, the received words can possible lie in $\mathcal{G}_{q}(k',n)$, where $k'\neq k$. In this paper, we study the balls in $\mathcal{G}_{q}(k,n)$ with center that is not necessarily in $\mathcal{G}_{q}(k,n)$. We describe the balls with respect to two different metrics, namely the subspace and the injection metric. Moreover, we use two different techniques for describing these balls, one is the Plücker embedding of $\mathcal{G}_{q}(k,n)$, and the second one is a rational parametrization of the matrix representation of the codewords. With these results, we consider the problem of list decoding a certain family of constant dimension codes, called lifted Gabidulin codes. We describe a way of representing these codes by linear equations in either the matrix representation or a subset of the Plücker coordinates. The union of these equations and the equations which arise from the description of the ball of a given radius in the Grassmannian describe the list of codewords with distance less than or equal to the given radius from the received word.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

List Decoding of Lifted Gabidulin Codes via the Plücker Embedding

Codes in the Grassmannian have recently found an application in random network coding. All the codewords in such codes are subspaces of $\F_q^n$ with a given dimension. In this paper, we consider the problem of list decoding of a certain family of codes in the Grassmannian, called lifted Gabidulin codes. For this purpose we use the Plücker embedding of the Grassmannian. We describe a way of representing a subset of the Plücker coordinates of lifted Gabidulin codes as linear block codes. The union of the parity-check equations of these block codes and the equations which arise from the description of a ball around a subspace in the Plücker coordinates describe the list of codewords with distance less than a given parameter from the received word.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Using LDGM Codes and Sparse Syndromes to Achieve Digital Signatures

In this paper, we address the problem of achieving efficient code-based digital signatures with small public keys. The solution we propose exploits sparse syndromes and randomly designed low-density generator matrix codes. Based on our evaluations, the proposed scheme is able to outperform existing solutions, permitting to achieve considerable security levels with very small public keys.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Complete Characterization of Irreducible Cyclic Orbit Codes and their Plücker Embedding

Constant dimension codes are subsets of the finite Grassmann variety. The study of these codes is a central topic in random linear network coding theory. Orbit codes represent a subclass of constant dimension codes. They are defined as orbits of a subgroup of the general linear group on the Grassmannian. This paper gives a complete characterization of orbit codes that are generated by an irreducible cyclic group, i.e. a group having one generator that has no non-trivial invariant subspace. 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. Furthermore, we investigate the Plücker embedding of these codes and show how the orbit structure is preserved in the embedding.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

An Algebraic Approach for Decoding Spread Codes

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 x n) with entries in a finite field F_q. Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires O((n-k)k^3) operations over an extension field F_{q^k}. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Decoding of Subspace Codes, a Problem of Schubert Calculus over Finite Fields

Schubert calculus provides algebraic tools to solve enumerative problems. There have been several applied problems in systems theory, linear algebra and physics which were studied by means of Schubert calculus. The method is most powerful when the base field is algebraically closed. In this article we first review some of the successes Schubert calculus had in the past. Then we show how the problem of decoding of subspace codes used in random network coding can be formulated as a problem in Schubert calculus. Since for this application the base field has to be assumed to be a finite field new techniques will have to be developed in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Coding Solutions for the Secure Biometric Storage Problem

The paper studies the problem of securely storing biometric passwords, such as fingerprints and irises. With the help of coding theory Juels and Wattenberg derived in 1999 a scheme where similar input strings will be accepted as the same biometric. In the same time nothing could be learned from the stored data. They called their scheme a "fuzzy commitment scheme". In this paper we will revisit the solution of Juels and Wattenberg and we will provide answers to two important questions: What type of error-correcting codes should be used and what happens if biometric templates are not uniformly distributed, i.e. the biometric data come with redundancy. Answering the first question will lead us to the search for low-rate large-minimum distance error-correcting codes which come with efficient decoding algorithms up to the designed distance. In order to answer the second question we relate the rate required with a quantity connected to the "entropy" of the string, trying to estimate a sort of "capacity", if we want to see a flavor of the converse of Shannon's noisy coding theorem. Finally we deal with side-problems arising in a practical implementation and we propose a possible solution to the main one that seems to have so far prevented real life applications of the fuzzy scheme, as far as we know.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Cyclic Orbit Codes

In network coding a constant dimension code consists of a set of k-dimensional subspaces of F_q^n. Orbit codes are constant dimension codes which are defined as orbits of a subgroup of the general linear group, acting on the set of all subspaces of F_q^n. If the acting group is cyclic, the corresponding orbit codes are called cyclic orbit codes. In this paper we give a classification of cyclic orbit codes and propose a decoding procedure for a particular subclass of cyclic orbit codes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Decoding of Convolutional Codes over the Erasure Channel

In this paper we study the decoding capabilities of convolutional codes over the erasure channel. Of special interest will be maximum distance profile (MDP) convolutional codes. These are codes which have a maximum possible column distance increase. We show how this strong minimum distance condition of MDP convolutional codes help us to solve error situations that maximum distance separable (MDS) block codes fail to solve. Towards this goal, we define two subclasses of MDP codes: reverse-MDP convolutional codes and complete-MDP convolutional codes. Reverse-MDP codes have the capability to recover a maximum number of erasures using an algorithm which runs backward in time. Complete-MDP convolutional codes are both MDP and reverse-MDP codes. They are capable to recover the state of the decoder under the mildest condition. We show that complete-MDP convolutional codes perform in certain sense better than MDS block codes of the same rate over the erasure channel.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Efficient evaluation of polynomials over finite fields

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On conjugacy classes of subgroups of the general linear group and cyclic orbit codes

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On fuzzy syndrome hashing with LDPC coding

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 this model, showing that it offers a suitable protection against information leakage and several advantages with respect to similar solutions, such as the fuzzy commitment scheme. Furthermore, the design and characterization of LDPC codes to be used for this purpose is addressed.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Decoding Complexity of Cyclic Codes Up to the BCH Bound

The standard algebraic decoding algorithm of cyclic codes $[n,k,d]$ up to the BCH bound $t$ is very efficient and practical for relatively small $n$ while it becomes unpractical for large $n$ as its computational complexity is $O(nt)$. Aim of this paper is to show how to make this algebraic decoding computationally more efficient: in the case of binary codes, for example, the complexity of the syndrome computation drops from $O(nt)$ to $O(t\sqrt n)$, and that of the error location from $O(nt)$ to at most $\max \{O(t\sqrt n), O(t^2\log(t)\log(n))\}$.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Pseudocodeword weights for non-binary LDPC codes

Pseudocodewords of q-ary LDPC codes are examined and the weight of a pseudocodeword on the q-ary symmetric channel is defined. The weight definition of a pseudocodeword on the AWGN channel is also extended to two-dimensional q-ary modulation such as q-PAM and q-PSK. The tree-based lower bounds on the minimum pseudocodeword weight are shown to also hold for q-ary LDPC codes on these channels.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Tree-Based Construction of LDPC Codes

We present a construction of LDPC codes that have minimum pseudocodeword weight equal to the minimum distance, and perform well with iterative decoding. The construction involves enumerating a d-regular tree for a fixed number of layers and employing a connection algorithm based on mutually orthogonal Latin squares to close the tree. Methods are presented for degrees d=p^s and d = p^s+1, for p a prime, -- one of which includes the well-known finite-geometry-based LDPC codes.

0 citations0 reviewsNo code linkedOpen access
preprint1997arXiv

Some Remarks on Real and Complex Output Feedback

We provide some new necessary and sufficient conditions which guarantee arbitrary pole placement of a particular linear system over the complex numbers. We exhibit a non-trivial real linear system which is not controllable by real static output feedback and discuss a conjecture from algebraic geometry concerning the existence of real linear systems for which all static feedback laws are real.

0 citations0 reviewsNo code linkedOpen access