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

Jens Zumbrägel

Jens Zumbrägel appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.RAInformation Theorymath.ITmath.NTmath.COCryptography and Securitymath.GNArtificial IntelligenceLogic in Computer Sciencemath.KTmath.LO

Catalog footprint

What is connected

25works
11topics
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

25 published item(s)

preprint2023arXiv

Cryptographic Group and Semigroup Actions

We consider actions of a group or a semigroup on a set, which generalize the setup of discrete logarithm based cryptosystems. Such cryptographic group actions have gained increasing attention recently in the context of isogeny-based cryptography. We introduce generic algorithms for the semigroup action problem and discuss lower and upper bounds. Also, we investigate Pohlig-Hellman type attacks in a general sense. In particular, we consider reductions provided by non-invertible elements in a semigroup, and we deal with subgroups in the case of group actions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

List Decoding of Quaternary Codes in the Lee Metric

We present a list decoding algorithm for quaternary negacyclic codes over the Lee metric. To achieve this result, we use a Sudan-Guruswami type list decoding algorithm for Reed-Solomon codes over certain ring alphabets. Our decoding strategy for negacyclic codes over the ring $\mathbb Z_4$ combines the list decoding algorithm by Wu with the Gröbner basis approach for solving a key equation due to Byrne and Fitzpatrick.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Efficient Decoding of Gabidulin Codes over Galois Rings

This paper presents the first decoding algorithm for Gabidulin codes over Galois rings with provable quadratic complexity. The new method consists of two steps: (1) solving a syndrome-based key equation to obtain the annihilator polynomial of the error and therefore the column space of the error, (2) solving a key equation based on the received word in order to reconstruct the error vector. This two-step approach became necessary since standard solutions as the Euclidean algorithm do not properly work over rings.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Computation of a 30750-Bit Binary Field Discrete Logarithm

This paper reports on the computation of a discrete logarithm in the finite field $\mathbb F_{2^{30750}}$, breaking by a large margin the previous record, which was set in January 2014 by a computation in $\mathbb F_{2^{9234}}$. The present computation made essential use of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbrägel, and is the first large-scale experiment to truly test and successfully demonstrate its potential when applied recursively, which is when it leads to the stated complexity. It required the equivalent of about 2900 core years on a single core of an Intel Xeon Ivy Bridge processor running at 2.6 GHz, which is comparable to the approximately 3100 core years expended for the discrete logarithm record for prime fields, set in a field of bit-length 795, and demonstrates just how much easier the problem is for this level of computational effort. In order to make the computation feasible we introduced several innovative techniques for the elimination of small degree irreducible elements, which meant that we avoided performing any costly Gröbner basis computations, in contrast to all previous records since early 2013. While such computations are crucial to the $L(\frac 1 4 + o(1))$ complexity algorithms, they were simply too slow for our purposes. Finally, this computation should serve as a serious deterrent to cryptographers who are still proposing to rely on the discrete logarithm security of such finite fields in applications, despite the existence of two quasi-polynomial algorithms and the prospect of even faster algorithms being developed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Steinberg algebras of Hausdorff ample groupoids over commutative semirings

We investigate the algebra of a Hausdorff ample groupoid, introduced by Steinberg, over a commutative semiring S. In particular, we obtain a complete characterization of congruence-simpleness for such Steinberg algebras, extending the well-known characterizations when S is a field or a commutative ring. We also provide a criterion for the Steinberg algebra of the graph groupoid associated to an arbitrary graph to be congruence-simple. Motivated by a result of Clark and Sims, we show that, over the Boolean semifield, the natural homomorphism from the Leavitt path algebra to the Steinberg algebra is an isomorphism if and only if the associated graph is row-finite. Moreover, we establish the Reduction Theorem and Uniqueness Theorems for Leavitt path algebras of row-finite graphs over the Boolean semifield.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

MacWilliams' extension theorem for infinite rings

Finite Frobenius rings have been characterized as precisely those finite rings satisfying the MacWilliams extension property, by work of Wood. In the present note we offer a generalization of this remarkable result to the realm of Artinian rings. Namely, we prove that a left Artinian ring has the left MacWilliams property if and only if it is left pseudo-injective and its finitary left socle embeds into the semisimple quotient. Providing a topological perspective on the MacWilliams property, we also show that the finitary left socle of a left Artinian ring embeds into the semisimple quotient if and only if it admits a finitarily left torsion-free character, if and only if the Pontryagin dual of the regular left module is almost monothetic. In conclusion, an Artinian ring has the MacWilliams property if and only if it is finitarily Frobenius, i.e., it is quasi-Frobenius and its finitary socle embeds into the semisimple quotient.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Towards Collaborative Conceptual Exploration

In domains with high knowledge distribution a natural objective is to create principle foundations for collaborative interactive learning environments. We present a first mathematical characterization of a collaborative learning group, a consortium, based on closure systems of attribute sets and the well-known attribute exploration algorithm from formal concept analysis. To this end, we introduce (weak) local experts for subdomains of a given knowledge domain. These entities are able to refute and potentially accept a given (implicational) query for some closure system that is a restriction of the whole domain. On this we build up a consortial expert and show first insights about the ability of such an expert to answer queries. Furthermore, we depict techniques on how to cope with falsely accepted implications and on combining counterexamples. Using notions from combinatorial design theory we further expand those insights as far as providing first results on the decidability problem if a given consortium is able to explore some target domain. Applications in conceptual knowledge acquisition as well as in collaborative interactive ontology learning are at hand.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

On congruence-semisimple semirings and the $K_0$-group characterization of ultramatricial algebras over semifields

In this paper, we provide a complete description of congruence-semisimple semirings and introduce the pre-ordered abelian Grothendieck groups $K_0(S)$ and $SK_0(S)$ of the isomorphism classes of the finitely generated projective and strongly projective S-semimodules, respectively, over an arbitrary semiring S. We prove that the $SK_0$-groups and $K_0$-groups are complete invariants of, i.e., completely classify, ultramatricial algebras over a semifield F. Consequently, we show that the $SK_0$-groups completely characterize zerosumfree congruence-semisimple semirings.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

The Extension Theorem for Bi-invariant Weights over Frobenius Rings and Frobenius Bimodules

We give a sufficient condition for a bi-invariant weight on a Frobenius bimodule to satisfy the extension property. This condition applies to bi-invariant weights on a finite Frobenius ring as a special case. The complex-valued functions on a Frobenius bimodule are viewed as a module over the semigroup ring of the multiplicative semigroup of the coefficient ring.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Designs and codes in affine geometry

Classical designs and their (projective) q-analogs can both be viewed as designs in matroids, using the matroid of all subsets of a set and the matroid of linearly independent subsets of a vector space, respectively. Another natural matroid is given by the point sets in general position of an affine space, leading to the concept of an affine design. Accordingly, a t-(n, k, $λ$) affine design of order q is a collection B of (k-1)-dimensional spaces in the affine geometry A = AG(n-1, q) such that each (t-1)-dimensional space in A is contained in exactly $λ$ spaces of B. In the case $λ$ = 1, as usual, one also refers to an affine Steiner system S(t, k, n). In this work we examine the relationship between the affine and the projective q-analogs of designs. The existence of affine Steiner systems with various parameters is shown, including the affine q-analog S(2, 3, 7) of the Fano plane. Moreover, we consider various distances in matroids and geometries, and we discuss the application of codes in affine geometry for error-control in a random network coding scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Indiscreet logarithms in finite fields of small characteristic

Recently, several striking advances have taken place regarding the discrete logarithm problem (DLP) in finite fields of small characteristic, despite progress having remained essentially static for nearly thirty years, with the best known algorithms being of subexponential complexity. In this expository article we describe the key insights and constructions which culminated in two independent quasi-polynomial algorithms. To put these developments into both a historical and a mathematical context, as well as to provide a comparison with the cases of so-called large and medium characteristic fields, we give an overview of the state-of-the-art algorithms for computing discrete logarithms in all finite fields. Our presentation aims to guide the reader through the algorithms and their complexity analyses ab initio.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the discrete logarithm problem in finite fields of fixed characteristic

For $q$ a prime power, the discrete logarithm problem (DLP) in $\mathbb{F}_{q}$ consists in finding, for any $g \in \mathbb{F}_{q}^{\times}$ and $h \in \langle g \rangle$, an integer $x$ such that $g^x = h$. We present an algorithm for computing discrete logarithms with which we prove that for each prime $p$ there exist infinitely many explicit extension fields $\mathbb{F}_{p^n}$ in which the DLP can be solved in expected quasi-polynomial time. Furthermore, subject to a conjecture on the existence of irreducible polynomials of a certain form, the algorithm solves the DLP in all extensions $\mathbb{F}_{p^n}$ in expected quasi-polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Profinite algebras and affine boundedness

We prove a characterization of profinite algebras, i.e., topological algebras that are isomorphic to a projective limit of finite discrete algebras. In general profiniteness concerns both the topological and algebraic characteristics of a topological algebra, whereas for topological groups, rings, semigroups, and distributive lattices, profiniteness turns out to be a purely topological property as it is is equivalent to the underlying topological space being a Stone space. Condensing the core idea of those classical results, we introduce the concept of affine boundedness for an arbitrary universal algebra and show that for an affinely bounded topological algebra over a compact signature profiniteness is equivalent to the underlying topological space being a Stone space. Since groups, semigroups, rings, and distributive lattices are indeed affinely bounded algebras over finite signatures, all these known cases arise as special instances of our result. Furthermore, we present some additional applications concerning topological semirings and their modules, as well as distributive associative algebras. We also deduce that any affinely bounded simple compact algebra over a compact signature is either connected or finite. Towards proving the main result, we also establish that any topological algebra is profinite if and only if its underlying space is a Stone space and its translation monoid is equicontinuous.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Simpleness of Leavitt Path Algebras with Coefficients in a Commutative Semiring

In this paper, we study ideal- and congruence-simpleness for the Leavitt path algebras of directed graphs with coefficients in a commutative semiring S, as well as establish some fundamental properties of those algebras. We provide a complete characterization of ideal-simple Leavitt path algebras with coefficients in a semifield S that extends the well-known characterizations when the ground semiring S is a field. Also, extending the well-known characterizations when S is a field or commutative ring, we present a complete characterization of congruence-simple Leavitt path algebras over row-finite graphs with coefficients in a commutative semiring S.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Breaking `128-bit Secure' Supersingular Binary Curves (or how to solve discrete logarithms in ${\mathbb F}_{2^{4 \cdot 1223}}$ and ${\mathbb F}_{2^{12 \cdot 367}}$)

In late 2012 and early 2013 the discrete logarithm problem (DLP) in finite fields of small characteristic underwent a dramatic series of breakthroughs, culminating in a heuristic quasi-polynomial time algorithm, due to Barbulescu, Gaudry, Joux and Thomé. Using these developments, Adj, Menezes, Oliveira and Rodríguez-Henríquez analysed the concrete security of the DLP, as it arises from pairings on (the Jacobians of) various genus one and two supersingular curves in the literature, which were originally thought to be $128$-bit secure. In particular, they suggested that the new algorithms have no impact on the security of a genus one curve over ${\mathbb F}_{2^{1223}}$, and reduce the security of a genus two curve over ${\mathbb F}_{2^{367}}$ to $94.6$ bits. In this paper we propose a new field representation and efficient general descent principles which together make the new techniques far more practical. Indeed, at the `128-bit security level' our analysis shows that the aforementioned genus one curve has approximately $59$ bits of security, and we report a total break of the genus two curve.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

New Results on the Pseudoredundancy

The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding minimum pseudoweight equals its minimum Hamming distance. By using the value assignment of Chen and Kløve we present new results on the pseudocodeword redundancy of binary linear codes. In particular, we give several upper bounds on the pseudoredundancies of certain codes with repeated and added coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

MacWilliams' Extension Theorem for Bi-Invariant Weights over Finite Principal Ideal Rings

A finite ring R and a weight w on R satisfy the Extension Property if every R-linear w-isometry between two R-linear codes in R^n extends to a monomial transformation of R^n that preserves w. MacWilliams proved that finite fields with the Hamming weight satisfy the Extension Property. It is known that finite Frobenius rings with either the Hamming weight or the homogeneous weight satisfy the Extension Property. Conversely, if a finite ring with the Hamming or homogeneous weight satisfies the Extension Property, then the ring is Frobenius. This paper addresses the question of a characterization of all bi-invariant weights on a finite ring that satisfy the Extension Property. Having solved this question in previous papers for all direct products of finite chain rings and for matrix rings, we have now arrived at a characterization of these weights for finite principal ideal rings, which form a large subclass of the finite Frobenius rings. We do not assume commutativity of the rings in question.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Finite simple additively idempotent semirings

Since for the classification of finite (congruence-)simple semirings it remains to classify the additively idempotent semirings, we progress on the characterization of finite simple additively idempotent semirings as semirings of join-morphisms of a semilattice. We succeed in doing this for many cases, amongst others for every semiring of this kind with an additively neutral element. As a consequence we complete the classification of finite simple semirings with an additively neutral element. To complete the classification of all finite simple semirings it remains to classify some very specific semirings, which will be discussed here. Our results employ the theory of idempotent irreducible semimodules, which we develop further.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the algebraic representation of selected optimal non-linear binary codes

Revisiting an approach by Conway and Sloane we investigate a collection of optimal non-linear binary codes and represent them as (non-linear) codes over Z4. The Fourier transform will be used in order to analyze these codes, which leads to a new algebraic representation involving subgroups of the group of units in a certain ring. One of our results is a new representation of Best's (10, 40, 4) code as a coset of a subgroup in the group of invertible elements of the group ring Z4[Z5]. This yields a particularly simple algebraic decoding algorithm for this code. The technique at hand is further applied to analyze Julin's (12, 144, 4) code and the (12, 24, 12) Hadamard code. It can also be used in order to construct a (non-optimal) binary (14, 56, 6) code.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the Pseudocodeword Redundancy of Binary Linear Codes

The AWGNC, BSC, and max-fractional pseudocodeword redundancies of a binary linear code are defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Algebraic Decoding of Negacyclic Codes Over Z_4

In this article we investigate Berlekamp's negacyclic codes and discover that these codes, when considered over the integers modulo 4, do not suffer any of the restrictions on the minimum distance observed in Berlekamp's original papers. The codes considered here have minimim Lee distance at least 2t+1, where the generator polynomial of the code has roots z,z^3,...,z^{2t+1} for a primitive 2nth root of unity z in a Galois extension of Z4. No restriction on t is imposed. We present an algebraic decoding algorithm for this class of codes that corrects any error pattern of Lee weight at most t. Our treatment uses Grobner bases and the decoding complexity is quadratic in t.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Characteristics of Invariant Weights Related to Code Equivalence over Rings

The Equivalence Theorem states that, for a given weight on the alphabet, every linear isometry between linear codes extends to a monomial transformation of the entire space. This theorem has been proved for several weights and alphabets, including the original MacWilliams' Equivalence Theorem for the Hamming weight on codes over finite fields. The question remains: What conditions must a weight satisfy so that the Extension Theorem will hold? In this paper we provide an algebraic framework for determining such conditions, generalising the approach taken in [Greferath, Honold '06].

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Simpleness of Semirings and Complete Semirings

In this paper, among other results, there are described (complete) simple - simultaneously ideal- and congruence-simple - endomorphism semirings of (complete) idempotent commutative monoids; it is shown that the concepts of simpleness, congruence-simpleness and ideal-simpleness for (complete) endomorphism semirings of projective semilattices (projective complete lattices) in the category of semilattices coincide iff those semilattices are finite distributive lattices; there are described congruence-simple complete hemirings and left artinian congruence-simple complete hemirings. Considering the relationship between the concepts of "Morita equivalence" and "simpleness" in the semiring setting, we have obtained the following results: The ideal-simpleness, congruence-simpleness and simpleness of semirings are Morita invariant properties; A complete description of simple semirings containing the infinite element; The representation theorem - "Double Centralizer Property" - for simple semirings; A complete description of simple semirings containing a projective minimal one-sided ideal; A characterization of ideal-simple semirings having either infinite elements or a projective minimal one-sided ideal; A confirmation of Conjecture of [Kat04a] and solving Problem 3.9 of [Kat04b] in the classes of simple semirings containing either infinite elements or projective minimal left (right) ideals, showing, respectively, that semirings of those classes are not perfect and the concepts of "mono-flatness" and "flatness" for semimodules over semirings of those classes are the same. Finally, we give a complete description of ideal-simple, artinian additively idempotent chain semirings, as well as of congruence-simple, lattice-ordered semirings.

0 citations0 reviewsNo code linkedOpen access