journal of Groups, complexity, cryptology - Latest Publications

Quadratic Equations in Graph Products of Groups and the Exponent of Periodicity

Diekert, Volker — Fri, 03 Apr 2026 04:50:23 +0000

In 1977, Makanin established the decidability of equations in free monoids. A key ingredient in his proof is the exponent of periodicity: for a word $w$, it is the largest exponent $e$ such that $w$ contains a nonempty factor of the form $p^e$. Makanin showed the following for a system of equations in free monoids: if the system has a solution with a sufficiently large exponent of periodicity, then it has infinitely many solutions. However, the converse -- whether the existence of infinitely many solutions implies the existence of solutions with arbitrarily large exponent of periodicity -- remains open. In this paper, we investigate the analogous problem for quadratic equations in finitely generated groups. We use normal forms to define the exponent of periodicity. We then identify structural conditions on groups and their normal forms that guarantee that infinite solution sets of quadratic systems have an unbounded exponent of periodicity. We prove that these conditions are preserved under graph products and, in particular, hold for all finitely generated right-angled Artin groups. In addition, we show that they also hold for finitely generated (graph products of) torsion-free nilpotent and hyperbolic groups, and we characterize the Baumslag-Solitar groups satisfying them.

On the Diophantine problem related to power circuits

Rybalov, Alexander — Thu, 02 Apr 2026 02:07:20 +0000

Myasnikov, Ushakov, and Won introduced power circuits in 2012 to construct a polynomial-time algorithm for the word problem in the Baumslag group, which has a non-elementary Dehn function. Power circuits are computational structures that support addition and the operation $(x,y) \mapsto x \cdot 2^y$ on integers. They also posed the question of decidability of the Diophantine problem over the structure $\langle \mathbb{N}_{>0}; +, x \cdot 2^y, \leq, 1 \rangle$, which is closely related to power circuits. In this paper, we prove that the Diophantine problem over this structure is undecidable.

Subgroups of Cyclically Amalgamated Free Products

Kreuzer, Martin — Tue, 17 Mar 2026 07:10:55 +0000

Given a group $G = H_1 \ast_A H_2$ which is the free product of two finitely generated groups $H_1$ and $H_2$ with amalgamation over a cyclic subgroup $A$ which is malnormal in $G$, we study relations between the structure of its subgroups and the structure of the group $G$ itself. Firstly, we show that if $H_1$ and $H_2$ are 3-free products of cyclics of rank $\ge 3$ then $G$ is also a 3-free product of cyclics. Secondly, we prove that if $H_1$ and $H_2$ are 4-free products of cyclics of rank $\ge 4$ then every 4-generated subgroup of $G$ is a free product of $\le 4$ cyclics or a 1-relator quotient of a free product of four cyclic groups. Here a group is called an $n$-free product of cyclics if every $n$-generated subgroup is a free product of $\le n$ cyclic groups. These results are based on ubiquitous applications of the Nielsen method for amalgamated free products which we recall carefully. Lastly, given an infinite, finitely presented group which is not free, but all of its infinite index subgroups are free, a well-known conjecture says that it is isomorphic to a surface group. We revisit and elaborate on predominantly group theoretic proofs of this conjecture for cyclically amalgamated products as above, as well as for certain HNN extensions.

A note on co-Hopfian groups and rings

Gaglione, Anthony M. — Thu, 04 Dec 2025 03:29:36 +0000

Let $p$ and $n$ be positive integers. Assume additionally that $p\neq 3$ is a prime and that $n>2$. Let $R$ be a field of characteristic $p$. A very special consequence of a result of Bunina and Kunyavskii (2023, arXiv:2308.10076) is that $SL_{n}(R)$ is co-Hopfian as a group if and only if $R$ is co-Hopfian as a ring. In this paper, we prove that if $k$ is the algebraic closure of the $2$ element field, then $SL_{2}(k)$ is a co-Hopfian group. Since this $k$ is trivially seen to be co-Hopfian as a ring our result somewhat extends that of Bunina and Kunyavskii. We apply our result to prove that the class of groups satisfying Turner's Retract Theorem (called Turner groups here) is not closed under elementary equivalence thereby answering a question posed by the authors in (2017, Comm. Algebra).

Kahrobaei--Koupparis DSS: universal forgery

Ushakov, Alexander — Thu, 04 Dec 2025 03:23:33 +0000

Regardless of the choice of parameters, knowledge of a single signed message, i.e., a pair message/signature, produced by Kahrobaei-Koupparis digital signature scheme, proposed in [D. Kahrobaei and C. Koupparis, 2012], is sufficient to forge a valid signature for any other message.

Andrews-Curtis groups

Gilman, Robert H. — Fri, 04 Jul 2025 00:11:05 +0000

For any group $G$ and integer $k\ge 2$ the Andrews-Curtis transformations act as a permutation group, termed the Andrews-Curtis group $AC_k(G)$, on the subset $N_k(G) \subset G^k$ of all $k$-tuples that generate $G$ as a normal subgroup (provided $N_k(G)$ is non-empty). The famous Andrews-Curtis Conjecture is that if $G$ is free of rank $k$, then $AC_k(G)$ acts transitively on $N_k(G)$. The set $N_k(G)$ may have a rather complex structure, so it is easier to study the full Andrews-Curtis group $FAC(G)$ generated by AC-transformations on a much simpler set $G^k$. Our goal here is to investigate the natural epimorphism $λ\colon FAC_k(G) \to AC_k(G)$. We show that if $G$ is non-elementary torsion-free hyperbolic, then $FAC_k(G)$ acts faithfully on every nontrivial orbit of $G^k$, hence $λ\colon FAC_k(G) \to AC_k(G)$ is an isomorphism.

Twisted conjugacy in dihedral Artin groups I: Torus Knot groups

Crowe, Gemma — Mon, 26 May 2025 01:46:37 +0000

In this paper we provide an alternative solution to a result by Juhász that the twisted conjugacy problem for odd dihedral Artin groups is solvable, that is, groups with presentation $G(m) = \langle a,b \; | \; _{m}(a,b) = {}_{m}(b,a) \rangle$, where $m\geq 3$ is odd, and $_{m}(a,b)$ is the word $abab \dots$ of length $m$, is solvable. Our solution provides an implementable linear time algorithm, by considering an alternative group presentation to that of a torus knot group, and working with geodesic normal forms. An application of this result is that the conjugacy problem is solvable in extensions of odd dihedral Artin groups.

Membership problems in nilpotent groups

Bodart, Corentin — Fri, 25 Apr 2025 08:44:14 +0000

We study both the Submonoid Membership problem and the Rational Subset Membership problem in finitely generated nilpotent groups. We give two reductions with important applications. First, Submonoid Membership in any nilpotent group can be reduced to Rational Subset Membership in smaller groups. As a corollary, we prove the existence of a group with decidable Submonoid Membership and undecidable Rational Subset Membership, confirming a conjecture of Lohrey and Steinberg. Second, the Rational Subset Membership problem in $H_3(\mathbb Z)$ can be reduced to the Knapsack problem in the same group, and is therefore decidable. Combining both results, we deduce that the filiform $3$-step nilpotent group has decidable Submonoid Membership.

Conjugacy Class Growth in Virtually Abelian Groups

Dermenjian, Aram — Mon, 24 Feb 2025 02:48:40 +0000

We study the conjugacy class growth function in finitely generated virtually abelian groups. That is, the number of elements in the ball of radius $n$ in the Cayley graph which intersect a fixed conjugacy class. In the class of virtually abelian groups, we prove that this function is always asymptotically equivalent to a polynomial. Furthermore, we show that in any affine Coxeter group, the degree of polynomial growth of a conjugacy class is equivalent to the reflection length of any element of that class.

Computing the unit group of a commutative finite $\mathbb{Z}$-algebra

Kreuzer, Martin — Wed, 31 Jul 2024 01:20:10 +0000

For a commutative finite $\mathbb{Z}$-algebra, i.e., for a commutative ring $R$ whose additive group is finitely generated, it is known that the group of units of $R$ is finitely generated, as well. Our main results are algorithms to compute generators and the structure of this group. This is achieved by reducing the task first to the case of reduced rings, then to torsion-free reduced rings, and finally to an order in a reduced ring. The simplified cases are treated via a calculation of exponent lattices and various algorithms to compute the minimal primes, primitive idempotents, and other basic objects. All algorithms have been implemented and are available as a SageMath package. Whenever possible, the time complexity of the described methods is tracked carefully.

Groups of F-Type

Fine, Benjamin — Sat, 27 Jul 2024 01:52:28 +0000

We consider a class of groups, called groups of F-type, which includes some known and important classes like Fuchsian groups of geometric rank $\ge 3$, surface groups of genus $\ge 2$, cyclically pinched one-relator groups and torus-knot groups, and discuss algebraic and geometric properties of groups of F-type.

On equationally Noetherian predicate structures

Buchinskiy, Ivan — Wed, 17 Jul 2024 03:45:53 +0000

In this paper, we prove a criterion for a predicate structure to be equationally Noetherian.

Constrained inhomogeneous spherical equations: average-case hardness

Ushakov, Alexander — Tue, 09 Jul 2024 11:22:25 +0000

In this paper we analyze computational properties of the Diophantine problem (and its search variant) for spherical equations $\prod_{i=1}^m z_i^{-1} c_i z_i = 1$ (and its variants) over the class of finite metabelian groups $G_{p,n}=\mathbb{Z}_p^n \rtimes \mathbb{Z}_p^\ast$, where $n\in\mathbb{N}$ and $p$ is prime. We prove that the problem of finding solutions for certain constrained spherical equations is computationally hard on average (assuming that some lattice approximation problem is hard in the worst case).

On isomorphisms to a free group and beyond

Shpilrain, Vladimir — Mon, 20 May 2024 02:02:17 +0000

The isomorphism problem for infinite finitely presented groups is probably the hardest among standard algorithmic problems in group theory. Classes of groups where it has been completely solved are nilpotent groups, hyperbolic groups, and limit groups. In this short paper, we address the problem of isomorphism to particular groups, including free groups. We also address the algorithmic problem of embedding a finitely presented group in a given limit group.

On countable isotypic structures

Gvozdevsky, Pavel — Tue, 14 May 2024 21:37:14 +0000

We obtain several results concerning the concept of isotypic structures. Namely we prove that any field of finite transcendence degree over a prime subfield is defined by types; then we construct isotypic but not isomorphic structures with countable underlying sets: totally ordered sets, fields, and groups. This answers an old question by B. Plotkin for groups.

Efficient Algorithms for Finite $\mathbb{Z}$-Algebras

Kreuzer, Martin — Wed, 24 Apr 2024 05:36:12 +0000

For a finite $\mathbb{Z}$-algebra $R$, i.e., for a $\mathbb{Z}$-algebra which is a finitely generated $\mathbb{Z}$-module, we assume that $R$ is explicitly given by a system of $\mathbb{Z}$-module generators $G$, its relation module ${\rm Syz}(G)$, and the structure constants of the multiplication in $R$. In this setting we develop and analyze efficient algorithms for computing essential information about $R$. First we provide polynomial time algorithms for solving linear systems of equations over $R$ and for basic ideal-theoretic operations in $R$. Then we develop ZPP (zero-error probabilitic polynomial time) algorithms to compute the nilradical and the maximal ideals of 0-dimensional affine algebras $K[x_1,\dots,x_n]/I$ with $K=\mathbb{Q}$ or $K=\mathbb{F}_p$. The task of finding the associated primes of a finite $\mathbb{Z}$-algebra $R$ is reduced to these cases and solved in ZPPIF (ZPP plus one integer factorization). With the same complexity, we calculate the connected components of the set of minimal associated primes ${\rm minPrimes}(R)$ and then the primitive idempotents of $R$. Finally, we prove that knowing an explicit representation of $R$ is polynomial time equivalent to knowing a strong Gr\"obner basis of an ideal $I$ such that $R = \mathbb{Z}[x_1,\dots,x_n]/I$.

Cayley Linear-Time Computable Groups

Kruengthomya, Prohrak — Wed, 03 Apr 2024 11:52:32 +0000

This paper looks at the class of groups admitting normal forms for which the right multiplication by a group element is computed in linear time on a multi-tape Turing machine. We show that the groups $\mathbb{Z}_2 \wr \mathbb{Z}^2$, $\mathbb{Z}_2 \wr \mathbb{F}_2$ and Thompson's group $F$ have normal forms for which the right multiplication by a group element is computed in linear time on a $2$-tape Turing machine. This refines the results previously established by Elder and the authors that these groups are Cayley polynomial-time computable.

Amenability problem for Thompson's group $F$: state of the art

Guba, Victor — Thu, 19 Oct 2023 01:32:55 +0000

This is a survey of our recent results on the amenability problem for Thompson's group $F$. They mostly concern esimating the density of finite subgraphs in Cayley graphs of $F$ for various systems of generators, and also equations in the group ring of $F$. We also discuss possible approaches to solve the problem in both directions.

Bounding conjugacy depth functions for wreath products of finitely generated abelian groups

Ferov, Michal — Thu, 28 Sep 2023 06:14:38 +0000

In this article, we study the asymptotic behaviour of conjugacy separability for wreath products of abelian groups. We fully characterise the asymptotic class in the case of lamplighter groups and give exponential upper and lower bounds for generalised lamplighter groups. In the case where the base group is infinite, we give superexponential lower and upper bounds. We apply our results to obtain lower bounds for conjugacy depth functions of various wreath products of groups where the acting group is not abelian.

An axiomatization for the universal theory of the Heisenberg group

Gaglione, Anthony M. — Thu, 31 Aug 2023 08:44:42 +0000

The Heisenberg group, here denoted $H$, is the group of all $3\times 3$ upper unitriangular matrices with entries in the ring $\mathbb{Z}$ of integers. A.G. Myasnikov posed the question of whether or not the universal theory of $H$, in the language of $H$, is axiomatized, when the models are restricted to $H$-groups, by the quasi-identities true in $H$ together with the assertion that the centralizers of noncentral elements be abelian. Based on earlier published partial results we here give a complete proof of a slightly stronger result.

Multi-recipient and threshold encryption based on hidden multipliers

Roman'kov, Vitaly — Tue, 21 Mar 2023 03:56:49 +0000

Let $S$ be a pool of $s$ parties and Alice be the dealer. In this paper, we propose a scheme that allows the dealer to encrypt messages in such a way that only one authorized coalition of parties (which the dealer chooses depending on the message) can decrypt. At the setup stage, each of the parties involved in the process receives an individual key from the dealer. To decrypt information, an authorized coalition of parties must work together to use their keys. Based on this scheme, we propose a threshold encryption scheme. For a given message $f$ the dealer can choose any threshold $m = m(f).$ More precisely, any set of parties of size at least $m$ can evaluate $f$; any set of size less than $m$ cannot do this. Similarly, the distribution of keys among the included parties can be done in such a way that authorized coalitions of parties will be given the opportunity to put a collective digital signature on any documents. This primitive can be generalized to the dynamic setting, where any user can dynamically join the pool $S$. In this case the new user receives a key from the dealer. Also any user can leave the pool $S$. In both cases, already distributed keys of other users do not change. The main feature of the proposed schemes is that for a given $s$ the keys are distributed once and can be used multiple times. The proposed scheme is based on the idea of hidden multipliers in encryption. As a platform, one can use both multiplicative groups of finite fields and groups of invertible elements of commutative rings, in particular, multiplicative groups of residue rings. We propose two versions of this scheme.

Geodesic Growth of Numbered Graph Products

Marjanski, Lindsay — Sat, 04 Feb 2023 00:34:30 +0000

In this paper, we study geodesic growth of numbered graph products; these are a generalization of right-angled Coxeter groups, defined as graph products of finite cyclic groups. We first define a graph-theoretic condition called link-regularity, as well as a natural equivalence amongst link-regular numbered graphs, and show that numbered graph products associated to link-regular numbered graphs must have the same geodesic growth series. Next, we derive a formula for the geodesic growth of right-angled Coxeter groups associated to link-regular graphs. Finally, we find a system of equations that can be used to solve for the geodesic growth of numbered graph products corresponding to link-regular numbered graphs that contain no triangles and have constant vertex numbering.

Exponent equations in HNN-extensions

Figelius, Michael — Mon, 26 Dec 2022 07:22:18 +0000

We consider exponent equations in finitely generated groups. These are equations, where the variables appear as exponents of group elements and take values from the natural numbers. Solvability of such (systems of) equations has been intensively studied for various classes of groups in recent years. In many cases, it turns out that the set of all solutions on an exponent equation is a semilinear set that can be constructed effectively. Such groups are called knapsack semilinear. Examples of knapsack semilinear groups are hyperbolic groups, virtually special groups, co-context-free groups and free solvable groups. Moreover, knapsack semilinearity is preserved by many group theoretic constructions, e.g., finite extensions, graph products, wreath products, amalgamated free products with finite amalgamated subgroups, and HNN-extensions with finite associated subgroups. On the other hand, arbitrary HNN-extensions do not preserve knapsack semilinearity. In this paper, we consider the knapsack semilinearity of HNN-extensions, where the stable letter $t$ acts trivially by conjugation on the associated subgroup $A$ of the base group $G$. We show that under some additional technical conditions, knapsack semilinearity transfers from base group $G$ to the HNN-extension $H$. These additional technical conditions are satisfied in many cases, e.g., when $A$ is a centralizer in $G$ or $A$ is a quasiconvex subgroup of the hyperbolic group $G$.

Equations in virtually class 2 nilpotent groups

Levine, Alex — Tue, 04 Oct 2022 01:39:45 +0000

We give an algorithm that decides whether a single equation in a group that is virtually a class $2$ nilpotent group with a virtually cyclic commutator subgroup, such as the Heisenberg group, admits a solution. This generalises the work of Duchin, Liang and Shapiro to finite extensions.

Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms

Grochow, Joshua A. — Thu, 11 Aug 2022 11:23:20 +0000

We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we develop an algorithm that takes two cubic forms $f, g\in \mathbb{F}_q[x_1,\dots, x_n]$, and decides whether $f$ and $g$ are isomorphic in time $q^{O(n)}$ for most $f$. This average-case setting has direct practical implications, having been studied in multivariate cryptography since the 1990s. Our second result concerns the complexity of testing equivalence of alternating trilinear forms. This problem is of interest in both mathematics and cryptography. We show that this problem is polynomial-time equivalent to testing equivalence of symmetric trilinear forms, by showing that they are both Tensor Isomorphism-complete (Grochow-Qiao, ITCS, 2021), therefore is equivalent to testing isomorphism of cubic forms over most fields.

The Axiomatics of Free Group Rings

Fine, Benjamin — Mon, 06 Dec 2021 08:51:51 +0000

In [FGRS1,FGRS2] the relationship between the universal and elementary theory of a group ring $R[G]$ and the corresponding universal and elementary theory of the associated group $G$ and ring $R$ was examined. Here we assume that $R$ is a commutative ring with identity $1 \ne 0$. Of course, these are relative to an appropriate logical language $L_0,L_1,L_2$ for groups, rings and group rings respectively. Axiom systems for these were provided in [FGRS1]. In [FGRS1] it was proved that if $R[G]$ is elementarily equivalent to $S[H]$ with respect to $L_{2}$, then simultaneously the group $G$ is elementarily equivalent to the group $H$ with respect to $L_{0}$, and the ring $R$ is elementarily equivalent to the ring $S$ with respect to $L_{1}$. We then let $F$ be a rank $2$ free group and $\mathbb{Z}$ be the ring of integers. Examining the universal theory of the free group ring ${\mathbb Z}[F]$ the hazy conjecture was made that the universal sentences true in ${\mathbb Z}[F]$ are precisely the universal sentences true in $F$ modified appropriately for group ring theory and the converse that the universal sentences true in $F$ are the universal sentences true in ${\mathbb Z}[F]$ modified appropriately for group theory. In this paper we show this conjecture to be true in terms of axiom systems for ${\mathbb Z}[F]$.

Finitely generated subgroups of free groups as formal languages and their cogrowth

Darbinyan, Arman — Tue, 16 Nov 2021 04:03:24 +0000

For finitely generated subgroups $H$ of a free group $F_m$ of finite rank $m$, we study the language $L_H$ of reduced words that represent $H$ which is a regular language. Using the (extended) core of Schreier graph of $H$, we construct the minimal deterministic finite automaton that recognizes $L_H$. Then we characterize the f.g. subgroups $H$ for which $L_H$ is irreducible and for such groups explicitly construct ergodic automaton that recognizes $L_H$. This construction gives us an efficient way to compute the cogrowth series $L_H(z)$ of $H$ and entropy of $L_H$. Several examples illustrate the method and a comparison is made with the method of calculation of $L_H(z)$ based on the use of Nielsen system of generators of $H$.

A fibering theorem for 3-manifolds

Sahattchieve, Jordan A. — Thu, 11 Nov 2021 05:24:13 +0000

An erratum to this article is posted at https://gcc.episciences.org/page/errata This paper generalizes results of M. Moon on the fibering of certain compact 3-manifolds over the circle. It also generalizes a theorem of H. B. Griffiths on the fibering of certain 2-manifolds over the circle.

Groups with context-free Diophantine problem

Yankovskiy, Vladimir — Thu, 26 Aug 2021 15:57:47 +0000

We find algebraic conditions on a group equivalent to the position of its Diophantine problem in the Chomsky Hierarchy. In particular, we prove that a finitely generated group has a context-free Diophantine problem if and only if it is finite.

Onto extensions of free groups

Mijares, Sebastià — Thu, 15 Apr 2021 15:13:52 +0000

An extension of subgroups $H\leqslant K\leqslant F_A$ of the free group of rank $|A|=r\geqslant 2$ is called onto when, for every ambient free basis $A'$, the Stallings graph $\Gamma_{A'}(K)$ is a quotient of $\Gamma_{A'}(H)$. Algebraic extensions are onto and the converse implication was conjectured by Miasnikov-Ventura-Weil, and resolved in the negative, first by Parzanchevski-Puder for rank $r=2$, and recently by Kolodner for general rank. In this note we study properties of this new type of extension among free groups (as well as the fully onto variant), and investigate their corresponding closure operators. Interestingly, the natural attempt for a dual notion -- into extensions -- becomes trivial, making a Takahasi type theorem not possible in this setting.

A new method for solving the elliptic curve discrete logarithm problem

Abdullah, Ansari — Tue, 16 Feb 2021 10:31:18 +0000

The elliptic curve discrete logarithm problem is considered a secure cryptographic primitive. The purpose of this paper is to propose a paradigm shift in attacking the elliptic curve discrete logarithm problem. In this paper, we will argue that initial minors are a viable way to solve this problem. This paper will present necessary algorithms for this attack. We have written a code to verify the conjecture of initial minors using Schur complements. We were able to solve the problem for groups of order up to $2^{50}$.

On Types of Elliptic Pseudoprimes

Babinkostova, L. — Wed, 10 Feb 2021 09:37:09 +0000

We generalize the notions of elliptic pseudoprimes and elliptic Carmichael numbers introduced by Silverman to analogues of Euler-Jacobi and strong pseudoprimes. We investigate the relationships among Euler Elliptic Carmichael numbers , strong elliptic Carmichael numbers, products of anomalous primes and elliptic Korselt numbers of Type I: The former two of these are introduced in this paper, and the latter two of these were introduced by Mazur (1973) and Silverman (2012) respectively. In particular, we expand upon a previous work of Babinkostova et al. by proving a conjecture about the density of certain elliptic Korselt numbers of Type I that are products of anomalous primes.

Density of Metric Small Cancellation in Finitely Presented Groups

Bishop, Alex — Wed, 09 Sep 2020 08:18:41 +0000

Small cancellation groups form an interesting class with many desirable properties. It is a well-known fact that small cancellation groups are generic; however, all previously known results of their genericity are asymptotic and provide no information about "small" group presentations. In this note, we give closed-form formulas for both lower and upper bounds on the density of small cancellation presentations, and compare our results with experimental data.

On subset sum problem in branch groups

Nikolaev, Andrey — Wed, 24 Jun 2020 09:00:50 +0000

We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group. More generally, we show NP-hardness of that problem in weakly regular branch groups, which implies NP-completeness if the group is, in addition, contracting.

Optimal Ate Pairing on Elliptic Curves with Embedding Degree $9,15$ and $27$

Fouotsa, Emmanuel — Fri, 17 Apr 2020 11:40:56 +0000

Much attention has been given to the efficient computation of pairings on elliptic curves with even embedding degree since the advent of pairing-based cryptography. The few existing works in the case of odd embedding degrees require some improvements. This paper considers the computation of optimal ate pairings on elliptic curves of embedding degrees $k=9$, $15$, $27$ which have twists of order three. Our main goal is to provide a detailed arithmetic and cost estimation of operations in the tower extensions field of the corresponding extension fields. A good selection of parameters enables us to improve the theoretical cost for the Miller step and the final exponentiation using the lattice-based method as compared to the previous few works that exist in these cases. In particular, for $k=15$, $k=27$, we obtain an improvement, in terms of operations in the base field, of up to 25% and 29% respectively in the computation of the final exponentiation. We also find that elliptic curves with embedding degree $k=15$ present faster results than BN12 curves at the 128-bit security level. We provide a MAGMA implementation in each case to ensure the correctness of the formulas used in this work.

A fault attack on the Niederreiter cryptosystem using binary irreducible Goppa codes

Danner, Julian — Fri, 20 Mar 2020 11:27:39 +0000

A fault injection framework for the decryption algorithm of the Niederreiter public-key cryptosystem using binary irreducible Goppa codes and classical decoding techniques is described. In particular, we obtain low-degree polynomial equations in parts of the secret key. For the resulting system of polynomial equations, we present an efficient solving strategy and show how to extend certain solutions to alternative secret keys. We also provide estimates for the expected number of required fault injections, apply the framework to state-of-the-art security levels, and propose countermeasures against this type of fault attack.

On the lattice of subgroups of a free group: complements and rank

Delgado, Jordi — Mon, 02 Mar 2020 11:56:10 +0000

A $\vee$-complement of a subgroup $H \leqslant \mathbb{F}_n$ is a subgroup $K \leqslant \mathbb{F}_n$ such that $H \vee K = \mathbb{F}_n$. If we also ask $K$ to have trivial intersection with $H$, then we say that $K$ is a $\oplus$-complement of $H$. The minimum possible rank of a $\vee$-complement (resp. $\oplus$-complement) of $H$ is called the $\vee$-corank (resp. $\oplus$-corank) of $H$. We use Stallings automata to study these notions and the relations between them. In particular, we characterize when complements exist, compute the $\vee$-corank, and provide language-theoretical descriptions of the sets of cyclic complements. Finally, we prove that the two notions of corank coincide on subgroups that admit cyclic complements of both kinds.