CGC Bulletin 29 =============== Contents: 1. Groups -- Complexity -- Cryptology, Volume 1 (2009), Issue 2 2. Groups -- Complexity -- Cryptology, Volume 2 (2010), Issue 1 3. Journal of Mathematical Cryptology, Volume 3 (2009), No. 3 4. Lecture slides from Workshop on block ciphers and their security 5. The subword reversing method 6. Garside groups and Yang-Baxter equation 7. Efficient Isomorphism Testing for a Class of Group Extensions 8. Fusion Discrete Logarithm Problems 9. Residual properties of 1-relator groups 10. Decision problems for finite and infinite presentations of groups and monoids 11. Statistical properties of subgroups of free groups 12. Expansion properties of finite simple groups 13. The isomorphism problem for all hyperbolic groups 14. Fixed points of finite groups acting on generalised Thompson groups 15. Hydra groups 16. Finding non-trivial elements and splittings in groups 17. A Garside presentation for Artin-Tits groups of type $\tilde C_n$ 18. Compressed conjugacy and the word problem for outer automorphism groups of graph groups 19. On the conjugacy growth functions of groups Regards, Boaz Tsaban Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html --- 1. Groups -- Complexity -- Cryptology, Volume 1 (2009), Issue 2 Special Issue, dedicated to Ben Fine on the occasion of his 60th birthday G. Rosenberger, A Short Biography of Ben Fine D. Bak Shnaps, The Word and Conjugacy Problem for Shuffle Groups A. E. Clement, Torsion-free Abelian Factor Groups of the Baumslag-Solitar Groups and Subgroups of the Additive Group of the Rational Numbers M. H. Dean, Metabelian product of a free nilpotent group with a free abelian group A. M. Gaglione, S. Lipschutz, D. Spellman, Almost Locally Free Groups and a Theorem of Magnus: Some Questions D. Grigoriev, V. Shpilrain, Authentication from Matrix Conjugation V. Gro?e Rebel, M. Hahn, G. Rosenberger, The Tits Alternative for Tsaranov's Generalized Tetrahedron Groups D. Kahrobaei, M. Anshel, Decision and Search in Non-Abelian Cramer-Shoup Public Key Cryptosystem A. Kalka, E. Liberman, M. Teicher, A Note on the Shifted Conjugacy Problem in Braid Groups M. Kreuzer, Algebraic Attacks Galore! S. R. Lakin, R. M. Thomas, Space Complexity and Word Problems of Groups J. Longrigg, A. Ushakov, A Practical Attack on a Certain Braid Group Based Shifted Conjugacy Authentication Protocol C. Maclachlan, Existence and Non-Existence of Torsion in Maximal Arithmetic Fuchsian Groups S. Majewicz, M. Zyman, Power-Commutative Nilpotent R-Powered Groups D. Osin, On the Universal Theory of Torsion and Lacunary Hyperbolic Groups http://www.heldermann.de/GCC/GCC01/gcc01.htm#gcc012 --- 2. Groups -- Complexity -- Cryptology, Volume 2 (20010), Issue 1 U. Weiss, On Shephard Groups with Large Triangles M. Conder, An Update on Hurwitz Groups G. Amir and O. Gurel-Gurevich, The Diameter of a Random Cayley Graph of Zq M. Kassabov, Presentations of Matrix Rings http://www.heldermann.de/GCC/GCC02/gcc02.htm --- 3. Journal of Mathematical Cryptology September 2009, Vol. 3, No. 3 Foreword. Second Workshop on Mathematical Cryptology Jaime Gutierrez Hybrid approach for solving multivariate systems over finite fields Luk Bettale, Jean-Charles Faug?re, and Ludovic Perret Cryptanalysing the critical group: efficiently solving Biggs's discrete logarithm problem Simon R. Blackburn Algebraic attack on NTRU using Witt vectors and Gr?bner bases G?rald Bourgeois and Jean-Charles Faug?re k -error linear complexity over p of subsequences of Sidelnikov sequences of period (pr – 1)/3 Nina Brandst?tter and Arne Winterhof Some remarks on FCSRs and implications for stream ciphers Simon Fischer, Willi Meier, and Dirk Stegemann On solving norm equations in global function fields Istv?n Ga?l and Michael E. Pohst Numerical solvers and cryptanalysis Mario Lamberger, Tomislav Nad, and Vincent Rijmen On the density of some special primes John B. Friedlander and Igor E. Shparlinski http://www.reference-global.com/toc/jmc/2009/3/3?ai=10i&ui=ng6&af=H --- 4. Lecture slides from Workshop on block ciphers and their security On the 4-th of December 2009 the "Workshop on block ciphers and their security" was held in Trento (Italy). The talk slides are availabe on the workshop's website: http://www.science.unitn.it/~sala/workshopcry09/ Massimiliano Sala --- 5. The subword reversing method Patrick Dehornoy We summarize the main known results involving subword reversing, a method of semigroup theory for constructing van Kampen diagrams by referring to a preferred direction. In good cases, the method provides a powerful tool for investigating presented (semi)groups. In particular, it leads to cancellativity and embeddability criteria for monoids and to efficient solutions for the word problem of monoids and groups of fractions. http://arxiv.org/abs/0912.4272 --- 6. Garside groups and Yang-Baxter equation Fabienne Chouraqui We establish a one-to-one correspondence between a class of Garside groups admitting a certain presentation and the structure groups of non-degenerate, involutive and braided set-theoretical solutions of the quantum Yang-Baxter equation. We also characterize indecomposable solutions in terms of Delta-pure Garside groups. http://arxiv.org/abs/0912.4827 --- 7. Efficient Isomorphism Testing for a Class of Group Extensions Francois Le Gall The group isomorphism problem asks whether two given groups are isomorphic or not. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. In this paper we study this problem for a class of groups corresponding to one of the simplest ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group A by a cyclic group of order m. We present an efficient algorithm solving the group isomorphism problem for all the groups of this class such that the order of A is coprime with m. More precisely, our algorithm runs in time almost linear in the orders of the input groups and works in the general setting where the groups are given as black-boxes. http://arxiv.org/abs/0812.2298 --- 8. Fusion Discrete Logarithm Problems Martin Schaffer, Stefan Rass The Discrete Logarithm Problem is well-known among cryptographers, for its computational hardness that grants security to some of the most commonly used cryptosystems these days. Still, many of these are limited to a small number of candidate algebraic structures which permit implementing the algorithms. In order to extend the applicability of discrete-logarithm-based cryptosystems to a much richer class of algebraic structures, we present a generalized form of exponential function. Our extension relaxes some assumptions on the exponent, which is no longer required to be an integer. Using an axiomatic characterization of the exponential function, we show how to construct mappings that obey the same rules as exponentials, but can raise vectors to the power of other vectors in an algebraically sound manner. At the same time, computational hardness is not affected (in fact, the problem could possibly be strengthened). Setting up standard cryptosystems in terms of our generalized exponential function is simple and requires no change to the existing security proofs. This opens the field for building much more general schemes than the ones known so far. http://arxiv.org/abs/1001.1802 Editor's comment: Exponentiation is generalized in this paper, unfortunately not in a way which makes the resultding DLP harder. They pose an open problem whether this approach makes the Decisional DHP harder, which is of theoretical interest. --- 9. Residual properties of 1-relator groups Mark Sapir This is a survey of two papers joint with A. Borisov and a paper joint with I. Spakulova. It is based on my lectures at the conference "Groups St. Andrews 2009", Bath (August 2009). We prove that almost all 1-related groups with at least 3 generators are virtually residually (finite p-)groups for almost all primes p, and coherent. The proof involves methods from combinatorial group theory (the congruence extension property of certain subgroups of free groups) algebraic geometry (dynamics of polynomial maps over finite and p-adic fields) and probability theory (convex hulls of Brownian bridges). http://arxiv.org/abs/1001.2829 --- 10. Decision problems for finite and infinite presentations of groups and monoids Carmelo Vaccaro In this survey we show how well known results about the Word Problem for finite group presentations can be generalized to the Word Problem and other decision problems for non-necessarily finite monoid and group presentations. This is done by introducing functions playing the same role of the Dehn function for the given decision problem and by finding the Tietze transformations that leave this function invariant. This survey presents some original ideas and points of view. http://arxiv.org/abs/1001.3981 --- 11. Statistical properties of subgroups of free groups Fr\'ed\'erique Bassino (LIPN), Armando Martino, Cyril Nicaud (IGM), Enric Ventura, Pascal Weil (LaBRI) The usual way to investigate the statistical properties of finitely generated subgroups of free groups, and of finite presentations of groups, is based on the so-called word-based distribution: subgroups are generated (finite presentations are determined) by randomly chosen k-tuples of reduced words, whose maximal length is allowed to tend to infinity. In this paper we adopt a different, though equally natural point of view: we investigate the statistical properties of the same objects, but with respect to the so-called graph-based distribution, recently introduced by Bassino, Nicaud and Weil. Here, subgroups (and finite presentations) are determined by randomly chosen Stallings graphs whose number of vertices tends to infinity. Our results show that these two distributions behave quite differently from each other, shedding a new light on which properties of finitely generated subgroups can be considered frequent or rare. For example, we show that malnormal subgroups of a free group are negligible in the graph-based distribution, while they are exponentially generic in the word-based distribution. Quite surprisingly, a random finite presentation generically presents the trivial group in this new distribution, while in the classical one it is known to generically present an infinite hyperbolic group. http://arxiv.org/abs/1001.4472 --- 12. Expansion properties of finite simple groups Oren Dinai We prove that if G is SL_2(F) or PSL_2(F), where F is a finite field, and A is a set of generators of G, then either |AAA| > |A|^(1+epsilon), where epsilon is an absolute positive real number, or AAA=G. As a corollary we get that the diameter of any Cayley graph of G is Poly-Logarithmic in |G|. http://arxiv.org/abs/1001.5069 --- 13. The isomorphism problem for all hyperbolic groups Fran\c{c}ois Dahmani and Vincent Guirardel We give a solution to Dehn's isomorphism problem for the class of all hyperbolic groups, possibly with torsion. We also prove a relative version for groups with peripheral structures. As a corollary, we give a uniform solution to Whitehead's problem asking whether two tuples of elements of a hyperbolic group $G$ are in the same orbit under the action of $\Aut(G)$. We also get an algorithm computing a generating set of the group of automorphisms of a hyperbolic group preserving a peripheral structure. http://arxiv.org/abs/1002.2590 --- 14. Fixed points of finite groups acting on generalised Thompson groups D.H. Kochloukova, C. Mart\'inez-P\'erez and B.E.A. Nucinkis We study centralisers of finite order automorphisms of generalisations of Thompson's group F and conjugacy classes of finite subgroups in finite extensions of these groups. In particular, we show that centralisers of finite automorphisms in these generalised Thompson groups either admit a finite type classifying space or are not finitely generated. As an application we deduce results about the Bredon type of such finite extensions. http://arxiv.org/abs/1002.1866 --- 15. Hydra groups Will Dison and Tim Riley We give examples of CAT(0), biautomatic, free-by-cyclic, one-relator groups which have finite-rank free subgroups of huge (Ackermannian) distortion. This leads to elementary examples of groups whose Dehn functions are similarly extravagant. This behaviour originates in manifestations of Hercules-versus-the-hydra battles in string-rewriting. http://arxiv.org/abs/1002.1945 --- 16. Finding non-trivial elements and splittings in groups Maurice Chiodo It is well known that the triviality problem for finitely presented groups is unsolvable. We ask the question of whether there exists a general procedure to produce a non-trivial element from a finite presentation of a non-trivial group. If not, then this would resolve an open problem by J. Wiegold: `Is every finitely generated perfect group the normal closure of one element?' We prove a weakened version of our question; there is no general procedure to pick a non-trivial generator from a finite presentation of a non-trivial group. We also show there is no general procedure to decompose a finite presentation of a non-trivial free product into two non-trivial finitely presented factors. We apply our results to show that a construction by Stallings on splitting groups with more than one end can never be made algorithmic, nor can the process of splitting connect sums of non-simply connected closed 4-manifolds. http://arxiv.org/abs/1002.2786 --- 17. A Garside presentation for Artin-Tits groups of type $\tilde C_n$ Fran\c{c}ois Digne We prove that an Artin-Tits group of affine type C has a (dual) Garside structure which we obtain by viewing it as the group of fixed points under an involution in an Artin-Tits group of affine type A. http://arxiv.org/abs/1002.4320 --- 18. Compressed conjugacy and the word problem for outer automorphism groups of graph groups Niko Haubold, Markus Lohrey, Christian Mathissen It is shown that for graph groups (right-angled Artin groups) the conjugacy problem as well as a restricted version of the simultaneous conjugacy problem can be solved in polynomial time even if input words are represented in a compressed form. As a consequence it follows that the word problem for the outer automorphism group of a graph group can be solved in polynomial time. http://arxiv.org/abs/1003.1233 --- 19. On the conjugacy growth functions of groups Victor Guba, Mark Sapir To every finitely generated group one can assign the conjugacy growth function that counts the number of conjugacy classes intersecting a ball of radius $n$. Results of Ivanov and Osin show that the conjugacy growth function may be constant even if the (ordinary) growth function is exponential. The aim of this paper is to provide conjectures, examples and statements that show that in "normal" cases, groups with exponential growth functions also have exponential conjugacy growth functions. http://arxiv.org/abs/1003.1293 --- END OF ISSUE