CGC Bulletin 22
Contents
- A Public Key Block Cipher Based on Multivariate Quadratic Quasigroups
- Notes on periodic elements of Garside groups
- The Conjugacy Problem in the Grigorchuk Group is polynomial time decidable
- On the Cayley semigroup of a finite aperiodic semigroup
- The density of Lawrence-Krammer and non-conjugate braid representations of links
- The 4-string Braid group $B_4$ has property RD and exponential mesoscopic rank
- Unusual Geodesics in generalizations of Thompson's Group F
- Solving the conjugacy problem in Garside groups by cyclic sliding
- Virtual retractions, conjugacy separability and omnipotence
- Normal automorphisms of hyperbolic groups
- Finding conjugate stabilizer subgroups of almost 3-transitive groups
- Reciprocity and rationality for the greedy normal form of a Coxeter group
- Journal of Mathematical Cryptology 2(2): Contents
- Finitely presented residually free groups
- New examples of finitely presented groups with strong fixed point properties
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. A Public Key Block Cipher Based on Multivariate Quadratic Quasigroups
Danilo Gligoroski and Smile Markovski and Svein Johan Knapskog
We have designed a new class of public key algorithms based on quasigroup string transformations using a specific class of quasigroups called multivariate quadratic quasigroups (MQQ). Our public key algorithm is a bijective mapping, it does not perform message expansions and can be used both for encryption and signatures. The public key consist of n quadratic polynomials with n variables where n=140, 160, ... . A particular characteristic of our public key algorithm is that it is very fast and highly parallelizable. More concretely, it has the speed of a typical modern symmetric block cipher - the reason for the phrase "A Public Key Block Cipher" in the title of this paper. Namely the reference C code for the 160-bit variant of the algorithm performs decryption in less than 11,000 cycles (on Intel Core 2 Duo -- using only one processor core), and around 6,000 cycles using two CPU cores and OpenMP 2.0 library. However, implemented in Xilinx Virtex-5 FPGA that is running on 249.4 MHz it achieves decryption throughput of 399 Mbps, and implemented on four Xilinx Virtex-5 chips that are running on 276.7 MHz it achieves encryption throughput of 44.27 Gbps. Compared to fastest RSA implementations on similar FPGA platforms, MQQ algorithm is more than 10,000 times faster.
http://arxiv.org/abs/0808.0247
2. Notes on periodic elements of Garside groups
Eon-Kyung Lee and Sang-Jin Lee
Let $G$ be a Garside group with Garside element $\Delta$. An element $g\in G$ is said to be \emph{periodic} with respect to $\Delta$ if some power of $g$ lies in the cyclic group generated by $\Delta$. This paper shows the following. (i) The periodicity of an element does not depend on the choice of a particular Garside structure if and only if the center of $G$ is cyclic. (ii) If $g^k=\Delta^{ka}$ for some nonzero integer $k$, then $g$ is conjugate to $\Delta^a$. (iii) Every finite subgroup of the central quotient of $G$ is cyclic.
http://arxiv.org/abs/0808.0308
3. The Conjugacy Problem in the Grigorchuk Group is polynomial time decidable
I. Lysenok, A. Myasnikov, A. Ushakov
In this paper we prove that the Conjugacy Problem in the Grigorchuk group $\Gamma$ has polynomial time complexity.
http://arxiv.org/abs/0808.2502
4. On the Cayley semigroup of a finite aperiodic semigroup
Avi Mintz
Let $S$ be a finite semigroup. In this paper we introduce the functions $\phi_s:S^* \to S^*$, first defined by Rhodes, given by $\phi_s([a_1,a_2 ,...,a_n]) = [sa_1,sa_1a_2,..., sa_1a_2 ... a_n]$. We show that if $S$ is a finite aperiodic semigroup, then the semigroup generated by the functions $\{\phi_s\}_{s \in S}$ is finite and aperiodic.
http://arxiv.org/abs/0808.3415
5. The density of Lawrence-Krammer and non-conjugate braid representations of links
Alexander Stoimenow
We use some Lie group theory and Budney's unitarization of the Lawrence-Krammer representation, to prove that for generic parameters of definite form the image of the representation (also on certain types of subgroups) is dense in the unitary group. This implies that, except possibly for closures of full-twist braids, all links have infinitely many conjugacy classes of braid representations on any non-minimal number of (and at least 4) strands.
http://arxiv.org/abs/0809.0033
6. The 4-string Braid group $B_4$ has property RD and exponential mesoscopic rank
Sylvain Barr\'e (LMAM), Mikael Pichot
We prove that the braid group $B_4$ on 4 strings has the property RD of Haagerup-Jolissaint. The case of $B_3$ was resolved by Jolissaint some years ago and the case of higher braid groups is open. We also prove that the braid group $B_4$ is a group of intermediate rank (of dimension 3). Namely, we show that the quotient of $B_4$ by its center is a group of exponential mesoscopic rank. It follows that the braid group $B_4$ itself is of exponential mesoscopic rank, in contrast to the case of the 3-string braid group $B_3$.
http://arxiv.org/abs/0809.0645
7. Unusual Geodesics in generalizations of Thompson's Group F
Claire Wladis
We prove that seesaw words exist in Thompson's Group F(N) for N=2,3,4,... with respect to the standard finite generating set X. A seesaw word w with swing k has only geodesic representatives ending in g^k or g^{-k} (for given g\in X) and at least one geodesic representative of each type. The existence of seesaw words with arbitrarily large swing guarantees that F(N) is neither synchronously combable nor has a regular language of geodesics. Additionally, we prove that dead ends (or k--pockets) exist in F(N) with respect to X and all have depth 2. A dead end w is a word for which no geodesic path in the Cayley graph \Gamma which passes through w can continue past w, and the depth of w is the minimal m\in\mathbb{N} such that a path of length m+1 exists beginning at w and leaving B_{|w|}. We represent elements of F(N) by tree-pair diagrams so that we can use Fordham's metric. This paper generalizes results by Cleary and Taback, who proved the case N=2.
http://arxiv.org/abs/0809.1677
8. Solving the conjugacy problem in Garside groups by cyclic sliding
Volker Gebhardt and Juan Gonz\'alez-Meneses
We present a solution to the conjugacy decision problem and the conjugacy search problem in Garside groups, which is theoretically simpler than the usual one, with no loss of efficiency. This is done by replacing the well known cycling and decycling operations by a new one, called cyclic sliding, which appears to be a more natural choice.
We give an analysis of the complexity of our algorithm in terms of fundamental operations with simple elements, so our analysis is valid for every Garside group. This paper intends to be self-contained, not requiring any previous knowledge of prior algorithms, and includes all the details for the algorithm to be implemented on a computer.
http://arxiv.org/abs/0809.0948
9. Virtual retractions, conjugacy separability and omnipotence
Henry Wilton
We use wreath products to provide criteria for a group to be conjugacy separable or omnipotent. These criteria are in terms of virtual retractions onto cyclic subgroups. We give two applications: a straightforward topological proof of the theorem of Stebe that infinite-order elements of Fuchsian groups (of the first type) are conjugacy distinguished, and a proof that surface groups are omnipotent.
http://arxiv.org/abs/0809.2308
10. Normal automorphisms of hyperbolic groups
A. Minasyan, D. Osin
An automorphism $\alpha $ of a group $G$ is normal if it fixes every normal subgroup of $G$ setwise. We give an algebraic description of normal automorphisms of relatively hyperbolic groups. In particular, we show that for any such a group $G$, $Inn(G)$ has finite index in the subgroup $Aut_n(G)$ of normal automorphisms. If, in addition, $G$ is non-elementary and has no finite non-trivial normal subgroups, then $Aut_n(G)=Inn(G)$. As an application, we show that $Out(G)$ is residually finite for every finitely generated residually finite group $G$ with infinitely many ends.
http://arxiv.org/abs/0809.2408
11. Finding conjugate stabilizer subgroups of almost 3-transitive groups
Aaron Denney, Cristopher Moore, Alexander Russell
We reduce a case of the hidden subgroup problem (HSP) in several families of finite groups of Lie type, such as SL_2(F_q), PSL_2(F_q), and PGL_2(F_q), to efficiently solvable HSPs in the affine group AGL_1(F_q). These groups act on projective space in an "almost" 3-transitive way, and we use this fact in each group to distinguish conjugates of its Borel (upper triangular) subgroup. Our observation is purely group-theoretic, and as such does not break new ground in quantum algorithms. Nonetheless, these appear to be the first positive results on the HSP in finite simple groups such as PSL_2(F_q).
http://arxiv.org/abs/0809.2445
12. Reciprocity and rationality for the greedy normal form of a Coxeter group
Richard Scott
We show that the characteristic series for the greedy normal form of a Coxeter group is always a rational series, and prove a reciprocity formula for this series when the group is right-angled and the nerve is Eulerian. As corollaries we obtain many of the known rationality and reciprocity results for the growth series of Coxeter groups as well as some new ones.
http://arxiv.org/abs/0809.2251
13. Journal of Mathematical Cryptology 2(2): Contents
109
Cryptanalysis of the shifted conjugacy authentication protocol Jonathan Longrigg, Alexander Ushakov
117
On the security of multi-prime RSA M. Jason Hinek
149
Improved security analysis of PMAC Mridul Nandi, Avradip Mandal
163
Counting hyperelliptic curves that admit a Koblitz model Cevahir Demirkiran, Enric Nart
181
Sieve algorithms for the shortest vector problem are practical Phong Q. Nguyen, Thomas Vidick
14. Finitely presented residually free groups
Martin R. Bridson, James Howie, Charles F. Miller III, Hamish Short
We establish a general criterion for the finite presentability of subdirect products of groups and use this to characterize finitely presented residually free groups. We prove that, for all $n\in\mathbb{N}$, a residually free group is of type ${\rm{FP}}_n$ if and only if it is of type ${\rm{F}}_n$.
New families of subdirect products of free groups are constructed, including the first examples of finitely presented subgroups that are neither ${\rm{FP}}_\infty$ nor of Stallings-Bieri type. The template for these examples leads to a more constructive characterization of finitely presented residually free groups up to commensurability.
We show that the class of finitely presented residually free groups is recursively enumerable and present a reduction of the isomorphism problem. A new algorithm is described which, given a finite presentation of a residually free group, constructs a canonical embedding into a direct product of finitely many limit groups.
The (multiple) conjugacy and membership problems for finitely presented subgroups of residually free groups are solved.
http://arxiv.org/abs/0809.3704
15. New examples of finitely presented groups with strong fixed point properties
Indira Chatterji and Martin Kassabov
The aim of this note is to give an easy example of a finitely generated simple group that cannot act without a fix point on a CAT(0) space of finite dimension. Such an example has been recently constructed by Arjantseva et al., using other techniques
http://arxiv.org/abs/0809.3719
---
END OF ISSUE
