Volume 12, Issue 1

1. On subset sum problem in branch groups

Andrey Nikolaev ; Alexander Ushakov.
We consider a group-theoretic analogue of the classic subset sum problem. Inthis brief note, we show that the subset sum problem is NP-complete in thefirst Grigorchuk group. More generally, we show NP-hardness of that problem inweakly regular branch groups, which implies NP-completeness if the group is, inaddition, contracting.

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

Emmanuel Fouotsa ; Nadia El Mrabet ; Aminatou Pecha.
Much attention has been given to the efficient computation of pairings onelliptic curves with even embedding degree since the advent of pairing-basedcryptography. The few existing works in the case of odd embedding degreesrequire some improvements. This paper considers the computation of optimal atepairings on elliptic curves of embedding degrees $k=9$, $15$, $27$ which havetwists of order three. Our main goal is to provide a detailed arithmetic andcost estimation of operations in the tower extensions field of thecorresponding extension fields. A good selection of parameters enables us toimprove the theoretical cost for the Miller step and the final exponentiationusing the lattice-based method as compared to the previous few works that existin these cases. In particular, for $k=15$, $k=27$, we obtain an improvement, interms of operations in the base field, of up to 25% and 29% respectively in thecomputation of the final exponentiation. We also find that elliptic curves withembedding degree $k=15$ present faster results than BN12 curves at the 128-bitsecurity level. We provide a MAGMA implementation in each case to ensure thecorrectness of the formulas used in this work.

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

Julian Danner ; Martin Kreuzer.
A fault injection framework for the decryption algorithm of the Niederreiterpublic-key cryptosystem using binary irreducible Goppa codes and classicaldecoding techniques is described. In particular, we obtain low-degreepolynomial equations in parts of the secret key. For the resulting system ofpolynomial equations, we present an efficient solving strategy and show how toextend certain solutions to alternative secret keys. We also provide estimatesfor the expected number of required fault injections, apply the framework tostate-of-the-art security levels, and propose countermeasures against this typeof fault attack.

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

Jordi Delgado ; Pedro V. Silva.
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 andthe relations between them. In particular, we characterize when complementsexist, compute the $\vee$-corank, and provide language-theoretical descriptionsof the sets of cyclic complements. Finally, we prove that the two notions ofcorank coincide on subgroups that admit cyclic complements of both kinds.