CGC Bulletin 20
CONTENTS
- Invariant-based Cryptosystems and Their Security Against Provable Worst-Case Break
- Efficient recovering of operation tables of black box groups and rings
- A Fast Algorithm for Stallings' Folding Process
- Rectangle groups
- Universal Upper Bound for the Growth of Artin Monoids
- An authentication scheme based on the twisted conjugacy problem
- Unitary Braid Representations with Finite Image
- Groebner-Shirshov basis for the braid semigroup
- Groebner-Shirshov basis for the braid group in the Birman-Ko-Lee-Garside generators
- Markov and Artin normal form theorem for braid groups
- Groebner-Shirshov basis for the braid group in the Artin-Garside generators
- A note on Artin-Markov normal form theorem for braid groups
- Finite Linear Quotients of $\B_3$ of Low Dimension
- Associativity of the Commutator Operation in Groups
- Thompson's Group F and Uniformly Finite Homology
- Detecting automorphic orbits in free groups
An especially rich issue this time.
Thanks to Mike Anshel for his contribution to this issue.
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. Invariant-based Cryptosystems and Their Security Against Provable Worst-Case Break
Dima Grigoriev , Arist Kojevnikov , Sergey Nikolenko
Cryptography based on noncommutative algebra still suffers from lack of schemes and lack of interest. In this work, we show new constructions of cryptosystems based on group invariants and suggest methods to make such cryptosystems secure in practice. We do not know any proof of security in its cryptographic sense or even a reduction of it to a sensible statement about regular complexity classes. In this paper we introduce a new notion of cryptographic security, a provable break, and prove that cryptosystems based on matrix group invariants and also a variation of the Anshel-Anshel-Goldfeld key agreement protocol for modular groups are secure against provable worst-case break unless NP \subset RP.
http://perso.univ-rennes1.fr/dmitry.grigoryev/pub/provable_journal.pdf
2. Efficient recovering of operation tables of black box groups and rings
Jens Zumbragel, Gerard Maze, Joachim Rosenthal
People have been studying the following problem: Given a finite set S with a hidden (black box) binary operation * on S which might come from a group law, and suppose you have access to an oracle that you can ask for the operation x*y of single pairs (x,y) you choose. What is the minimal number of queries to the oracle until the whole binary operation is recovered, i.e. you know x*y for all x,y in S?
This problem can trivially be solved by using |S|^2 queries to the oracle, so the question arises under which circumstances you can succeed with a significantly smaller number of queries.
In this presentation we give a lower bound on the number of queries needed for general binary operations. On the other hand, we present algorithms solving this problem by using |S| queries, provided that * is an abelian group operation. We also investigate black box rings and give lower and upper bounds for the number of queries needed to solve product recovering in this case.
http://arxiv.org/abs/0805.0514
3. A Fast Algorithm for Stallings' Folding Process
Nicholas Wembley Matheson Touikan
Internat. J. Algebra Comput. 16 (2006), no. 6, 1031--1045
We show that for a fixed free group F and an arbitrary finitely generated subgroup H (as given above) we can perform the Stalling's folding process in time O(N log^*(N)), where N is the sum of the word lengths of the given generators of H.
http://arxiv.org/abs/0805.2348
4. Rectangle groups
M.J.Dunwoody
A class of groups is investigated, each of which has a fairly simple presentation. For example the group $R = (a, b, c, d | a^3 = b^3 = c^3 = d^3 = 1, ba^{-1} =dc^{-1}, ca^{-1} = db^{-1}) $ is in the class. Such a group does not have as a homomorphic image any group which is a 2-orbifold group or which is a group of isometries of the reals. However it does have incompatible splittings over subgroups which are not small. This contradicts some ideas I had about universal JSJ decompostions for finitely presented groups over finitely generated subgroups. Such a group also has an unstable action on an R-tree and a cocompact action on a CAT(0) cube complex with finite cyclic point stabilizers, and trivial edge stabilizers.
http://arxiv.org/abs/0805.2494
5. Universal Upper Bound for the Growth of Artin Monoids
Barbu Berceanu, Zaffar Iqbal
In this paper we study the growth rates of Artin monoids and we show that 4 is a universal upper bound. We also show that the generating functions of the associated right-angled Artin monoids are given by families of Chebyshev polynomials. Applications to Artin groups and positive braids are given.
http://arxiv.org/abs/0805.2656
6. An authentication scheme based on the twisted conjugacy problem
Vladimir Shpilrain and Alexander Ushakov
The conjugacy search problem in a group $G$ is the problem of recovering an $x \in G$ from given $g \in G$ and $h=x^{-1}gx$. The alleged computational hardness of this problem in some groups was used in several recently suggested public key exchange protocols, including the one due to Anshel, Anshel, and Goldfeld, and the one due to Ko, Lee et al. Sibert, Dehornoy, and Girault used this problem in their authentication scheme, which was inspired by the Fiat-Shamir scheme involving repeating several times a three-pass challenge-response step.
In this paper, we offer an authentication scheme whose security is based on the apparent hardness of the twisted conjugacy search problem, which is: given a pair of endomorphisms (i.e., homomorphisms into itself) phi, \psi of a group G and a pair of elements w, t \in G, find an element s \in G such that t = \psi(s^{-1}) w \phi(s) provided at least one such s exists. This problem appears to be very non-trivial even for free groups. We offer here another platform, namely, the semigroup of all 2x2 matrices over truncated one-variable polynomials over F_2, the field of two elements, with transposition used instead of inversion in the equality above.
http://arxiv.org/abs/0805.2701
7. Unitary Braid Representations with Finite Image
Michael J. Larsen, Eric C. Rowell
We characterize unitary representations of braid groups $B_n$ of degree linear in $n$ and finite images of such representations of degree exponential in $n$.
http://arxiv.org/abs/0805.4222
8. Groebner-Shirshov basis for the braid semigroup
L. A. Bokut, Y. Fong, W.-F. Ke, L.-S. Shiao
We found Groebner-Shirshov basis for the braid semigroup $B^+_{n+1}$. It gives a new algorithm for the solution of the word problem for the braid semigroup and so for the braid group.
http://arxiv.org/abs/0806.1118
9. Groebner-Shirshov basis for the braid group in the Birman-Ko-Lee-Garside generators
L. A. Bokut
In this paper, we obtain Groebner-Shirshov (non-commutative Gr\"obner) bases for the braid groups in the Birman-Ko-Lee generators enriched by new ``Garside word" $\delta$. It gives a new algorithm for getting the Birman-Ko-Lee Normal Form in the braid groups, and thus a new algorithm for solving the word problem in these groups.
http://arxiv.org/abs/0806.1123
10. Markov and Artin normal form theorem for braid groups
L. A. Bokut, V. V. Chaynikov, K. P. Shum
In this paper we will present the results of Artin--Markov on braid groups by using the Groebner--Shirshov basis. As a consequence we can reobtain the normal form of Artin--Markov--Ivanovsky as an easy corollary.
http://arxiv.org/abs/0806.1124
11. Groebner-Shirshov basis for the braid group in the Artin-Garside generators
L. A. Bokut
In this paper, we give a Groebner-Shirshov basis of the braid group $B_{n+1}$ in the Artin--Garside generators. As results, we obtain a new algorithm for getting the Garside normal form, and a new proof that the braid semigroup $B^+{n+1}$ is the subsemigroup in $B_{n+1}$.
http://arxiv.org/abs/0806.1125
12. A note on Artin-Markov normal form theorem for braid groups
Yuqun Chen and Qiuhui Mo
In a recent paper by L. A. Bokut, V. V. Chaynikov and K. P. Shum in 2007, Braid group $B_n$ is represented by Artin-Burau's relations. For such a representation, it is told that all other compositions can be checked in the same way. In this note, we support this claim and check all compositions.
http://arxiv.org/abs/0806.0877
13. Finite Linear Quotients of $\B_3$ of Low Dimension
Eric C. Rowell, Imre Tuba
We study the problem of deciding whether or not the image of an irreducible representation of the braid group $\B_3$ of degree $\leq 5$ has finite image if we are only given the eigenvalues of a generator. We provide a partial algorithm that determines when the images are finite or infinite in all but finitely many cases, and use these results to study examples coming from quantum groups. Our technique uses two classification theorems and the computational group theory package GAP.
http://arxiv.org/abs/0806.0168
14. Associativity of the Commutator Operation in Groups
Fernando Guzman
The study of associativity of the commutator operation in groups goes back to some work of Levi in 1942. In the 1960's Richard J. Thompson created a group F whose elements are representatives of the generalized associative law for an arbitrary binary operation. In 2006, Geoghegan and Guzman proved that a group G is solvable if and only if the commutator operation in G eventually satisfies ALL instances of the associative law, and also showed that many non-solvable groups do not satisfy any instance of the generalized associative law. We will address the question: Is there a non-solvable group which satisfies SOME instance of the generalized associative law? For finite groups, we prove that the answer is no.
http://arxiv.org/abs/0805.4835
15. Thompson's Group F and Uniformly Finite Homology
Dan Staley
This paper demonstrates the uniformly finite homology developed by Block and Weinberger and its relationship to amenable spaces via applications to the Cayley graph of Thompson's Group F. In particular, a certain class of subgraph of F is shown to be non-amenable. This shows that if F is amenable, these subsets (which include every finitely generated submonoid of the positive monoid of F) must necessarily have measure zero.
http://arxiv.org/abs/0806.2877
16. Detecting automorphic orbits in free groups
Peter Brinkmann
We present an effective algorithm for detecting automorphic orbits in free groups, as well as a number of algorithmic improvements of train tracks for free group automorphisms.
http://arxiv.org/abs/0806.2889
---
END OF ISSUE
