CGC Bulletin 20

eZine lover (@eZine)

Published in 

CGC Bulletin

 · 11 months ago

CONTENTS

1. Invariant-based Cryptosystems and Their Security Against Provable Worst-Case Break
2. Efficient recovering of operation tables of black box groups and rings
3. A Fast Algorithm for Stallings' Folding Process
4. Rectangle groups
5. Universal Upper Bound for the Growth of Artin Monoids
6. An authentication scheme based on the twisted conjugacy problem
7. Unitary Braid Representations with Finite Image
8. Groebner-Shirshov basis for the braid semigroup
9. Groebner-Shirshov basis for the braid group in the Birman-Ko-Lee-Garside generators
10. Markov and Artin normal form theorem for braid groups
11. Groebner-Shirshov basis for the braid group in the Artin-Garside generators
12. A note on Artin-Markov normal form theorem for braid groups
13. Finite Linear Quotients of $\B_3$ of Low Dimension
14. Associativity of the Commutator Operation in Groups
15. Thompson's Group F and Uniformly Finite Homology
16. 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