Copy Link

Add to Bookmark

Report

CGC Bulletin 31

eZine lover (@eZine)

Published in

CGC Bulletin

· 7 months ago

CGC Bulletin 31

Contents

Mean-Set Attack: Cryptanalysis of Sibert et al. Authentication Protocol
Constructive membership testing in black-box classical groups
Exponentially generic subsets of groups
Journal of Mathematical Cryptology July 2010, Vol. 4, No. 1
Solving linear equations over finitely generated abelian groups
Quasigroups in cryptology
Genericity of Filling Elements
Reducible braids and Garside theory
Hurwitz equivalences of positive group generators
Series of representations of Thompson's groups $F$ and $T$
The Dehn function of Baumslag's Metabelian Group
The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks
Construction of Curtis-Phan-Tits system in black box classical groups
Statistics and compression of scl
A secret sharing scheme using groups
Nielsen equivalence of generating sets for closed surface groups
Length Functions for Semigroup Embeddings
Space functions of groups
Algebraic C(4) and T(4) groups are bi-automatic
A note on the structure of V(6) maps
Search and witness problems in group theory
Basic results on braid groups
The rate of escape on polycyclic and solvable groups
The conjugacy problem is not solvable in automaton groups
Tutorial on the braid groups
Journal of Mathematical Cryptology Vol. 4, No. 2

Regards,

Boaz Tsaban

Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html

1. Mean-Set Attack: Cryptanalysis of Sibert et al. Authentication Protocol

Natalia Mosina, Alexander Ushakov

We analyze the Sibert et al. group-based (Feige-Fiat-Shamir type) authentication protocol and show that the protocol is not computationally zero-knowledge. In addition, we provide experimental evidence that our approach is practical and can succeed even for groups with no efficiently computable length function such as braid groups. The novelty of this work is that we are not attacking the protocol by trying to solve an underlying complex algebraic problem, namely, the conjugacy search problem, but use a probabilistic approach, instead.

http://arxiv.org/abs/1006.4850

2. Constructive membership testing in black-box classical groups

Sophie Ambrose, Scott H. Murray, Cheryl E. Praeger and Csaba Schneider

The research described in this note aims at solving the constructive membership problem for the class of quasisimple classical groups. Our algorithms are developed in the black-box group model; that is, they do not require specific characteristics of the representations in which the input groups are given. The elements of a black-box group are represented, not necessarily uniquely, as bit strings of uniform length. We assume the existence of oracles to compute the product of two elements, the inverse of an element, and to test if two strings represent the same element. Solving the constructive membership problem for a black-box group $G$ requires to write every element of $G$ as a word in a given generating set. In practice we write the elements of $G$ as straight-line programs (SLPs) which can be viewed as a compact way of writing words.

http://arxiv.org/abs/1006.5858

3. Exponentially generic subsets of groups

Robert Gilman, Alexei Miasnikov, Denis Osin

In this paper we study the generic, i.e., typical, behavior of finitely generated subgroups of hyperbolic groups and also the generic behavior of the word problem for amenable groups. We show that a random set of elements of a nonelementary word hyperbolic group is very likely to be a set of free generators for a nicely embedded free subgroup. We also exhibit some finitely presented amenable groups for which the restriction of the word problem is unsolvable on every sufficiently large subset of words.

http://arxiv.org/abs/1007.0552

4. Journal of Mathematical Cryptology July 2010, Vol. 4, No. 1

Factor-4 and 6 compression of cyclotomic subgroups of and Koray Karabina

The monodromy pairing and discrete logarithm on the Jacobian of finite graphs Farbod Shokrieh

Common modulus attacks on small private exponent RSA and some fast variants (in practice) M. Jason Hinek and Charles C.Y. Lam

5. Solving linear equations over finitely generated abelian groups

Ren\'e Hartung

We discuss various methods and their effectiveness for solving linear equations over finitely generated abelian groups. More precisely, if $\varphi\colon G\to H$ is a homomorphism of finitely generated abelian groups and $b\in H$, we discuss various algorithms for checking whether $b\in \im\varphi$ holds and if so, for computing a pre-image of $b$ in $G$ together with the kernel of $\varphi$.

http://arxiv.org/abs/1007.2477

6. Quasigroups in cryptology

V.A. Shcherbacov

We give a review of some known published applications of quasigroups in cryptology.

http://arxiv.org/abs/1007.3572

7. Genericity of Filling Elements

Brent B. Solie

An element of a finitely generated non-Abelian free group F(X) is said to be filling if that element has positive translation length in every very small action of F(X) on an $\mathbb{R}$-tree. We give a proof that the set of filling elements of F(X) is exponentially F(X)-generic in the sense of Arzhantseva and Ol'shanskii. We also provide an algebraic sufficient condition for an element to be filling and show that there exists an exponentially F(X)-generic subset of filling elements whose membership problem is solvable in linear time.

http://arxiv.org/abs/1007.4022

8. Reducible braids and Garside theory

Juan Gonzalez-Meneses and Bert Wiest

We show that reducible braids which are, in a Garside-theoretical sense, as simple as possible within their conjugacy class, are also as simple as possible in a geometric sense. More precisely, if a braid belongs to a certain subset of its conjugacy class which we call the stabilized set of sliding circuits, an if it is reducible, then its reducibility is geometrically obvious: it has a round or almost round reducing curve. Moreover, for any given braid, an element of its stabilized set of sliding circuits can be found using the well-known cyclic sliding operation. This leads to a polynomial time algorithm for deciding the Nielsen-Thurston type of any braid, modulo one well-known conjecture on the speed of convergence of the cyclic sliding operation.

http://arxiv.org/abs/1008.0238

9. Hurwitz equivalences of positive group generators

Tetsuya Ito

For a positively presented group G, we provide a criterion for two tuples of positive group generators of G to be Hurwitz equivalent or Hurwitz-conjugation equivalent. We also present an algorithmic approach to solve the Hurwitz equivalence and the Hurwitz search problems by using (complete) positive group presentations. These methods can be applied to study a braid monodromy.

http://arxiv.org/abs/1008.1383

10. Series of representations of Thompson's groups $F$ and $T$

{\L}ukasz Garncarek

We define series of representations of the Thompson's groups $F$ and $T$. We show that they are irreducible and classify them up to unitary equivalence.

http://arxiv.org/abs/1008.1275

11. The Dehn function of Baumslag's Metabelian Group

Martin Kassabov and Tim Riley

Baumslag's group is a finitely presented metabelian group with a Z \wr Z subgroup. There is an analogue with an additional torsion relation in which this subgroup becomes C_m \wr Z. We prove that Baumslag's group has an exponential Dehn function. This contrasts with the torsion analogues which have quadratic Dehn functions.

http://arxiv.org/abs/1008.1966

12. The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks

Hang Dinh, Cris Moore, Alexander Russell

Quantum computers can break the RSA and El Gamal public-key cryptosystems, since they can factor integers and extract discrete logarithms. If we believe that quantum computers will someday become a reality, we would like to have \emph{post-quantum} cryptosystems which can be implemented today with classical computers, but which will remain secure even in the presence of quantum attacks.

In this article we show that the McEliece cryptosystem over rational Goppa codes resists precisely the attacks to which the RSA and El Gamal cryptosystems are vulnerable---namely, those based on generating and measuring coset states. This eliminates the approach of strong Fourier sampling on which almost all known exponential speedups by quantum algorithms are based. Specifically, we show that the natural case of the Hidden Subgroup Problem to which the McEliece cryptosystem reduces cannot be solved by strong Fourier sampling, or by any measurement of a coset state. We start with recent negative results on quantum algorithms for Graph Isomorphism, which are based on particular subgroups of size two, and extend them to subgroups of arbitrary structure, including the automorphism groups of Goppa codes. This allows us to obtain the first rigorous results on the security of the McEliece cryptosystem in the face of quantum adversaries, strengthening its candidacy for post-quantum cryptography. Additionally, we establish a variant of a conjecture of Kempe and Shalev on the subgroups of $S_n$ that can be efficiently reconstructed by quantum Fourier sampling.

http://arxiv.org/abs/1008.2390

13. Construction of Curtis-Phan-Tits system in black box classical groups

Alexandre Borovik and Sukru Yalcinkaya

We present a polynomial time Monte-Carlo algorithm for finite simple black box classical groups of odd characteristic which constructs all root ${\rm{SL}}_2(q)$-subgroups associated with the nodes of the extended Dynkin diagram of the corresponding algebraic group.

http://arxiv.org/abs/1008.2823

14. Statistics and compression of scl

Danny Calegari, Joseph Maher

In a hyperbolic group, a random word of length $n$ in the commutator subgroup has stable commutator length of order $n/\log{n}$. In any finitely generated group, either stable commutator length vanishes identically, or the result of a random walk of length $n$ conditioned to lie in the commutator subgroup has stable commutator length bounded above by order $n/\log{n}$ and below by order $\sqrt{n}$. The upper bounds are obtained by explicit estimates on random words and random geodesics in free and hyperbolic groups. The lower bounds are obtained from properties of the statistical distribution of values of quasimorphisms. One result we prove of independent interest is a central limit theorem for values of the rotation quasimorphism on random walks in semigroups of homeomorphisms of the circle.

http://arxiv.org/abs/1008.4952

15. A secret sharing scheme using groups

Dimitrios Panagopoulos

In this paper a secret sharing scheme based on the word problem in groups is introduced. The security of the scheme and possible variations are discussed in section 2. The article concludes with the suggestion of two categories of platform groups for the implementation of the scheme.

http://arxiv.org/abs/1009.0026

16. Nielsen equivalence of generating sets for closed surface groups

Larsen Louder

Generating sets for closed surfaces are either reducible or Nielsen equivalent to a standard generating set.

http://arxiv.org/abs/1009.0454

17. Length Functions for Semigroup Embeddings

Tara Davis

Following the work done by Olshanskii for groups, we describe, for a given semigroup $S$, which functions $l : S \rightarrow \mathbb{N}$ can be realized up to equivalence as length functions $g \mapsto |g|_{H}$ by embedding $S$ into a finitely generated semigroup $H$. We also, following the work done by Olshanskii and Sapir, provide a complete description of length functions of a given finitely generated semigroup with enumerable set of relations inside a finitely presented semigroup.

http://arxiv.org/abs/1009.2734

18. Space functions of groups

Alexander Olshanskii

We study the interrelation of space functions of groups and the space complexity of the algorithmic word problem in groups.

http://arxiv.org/abs/1009.3580

19. Algebraic C(4) and T(4) groups are bi-automatic

Uri Weiss

S. Gersten and H. Short have proved that if a group has a presentation which satisfies the algebraic C(4) and T(4) small-cancellation condition then the group is automatic. Their proof contains a gap which we aim to close. To do that we distinguish between algebraic small-cancellation conditions and geometric small cancellation conditions (which are conditions on the van Kampen diagrams). We show that, under certain additional requirements, geometric C(4) and T(4) small-cancellation conditions imply bi-automaticity. The additional requirements include a restriction on the labels of edges in minimal van Kampen diagrams. This, together with the so-called barycentric sub-division method proves the theorem.

http://arxiv.org/abs/1009.5531

20. A note on the structure of V(6) maps

Uri Weiss

The purpose of this note is make Theorem 13 in the article "On Biautomaticity of Non-Homogenous Small-Cancellation Groups" more accessible. Restatements of the theorem already appeared in few of the authors' succeeding works but with no details. We wish in this note to give the necessary details to these restatements.

http://arxiv.org/abs/1009.5545

21. Search and witness problems in group theory

Vladimir Shpilrain

Decision problems are problems of the following nature: given a property P and an object O, find out whether or not the object O has the property P. On the other hand, witness problems are: given a property P and an object O with the property P, find a proof of the fact that O indeed has the property P. On the third hand(?!), search problems are of the following nature: given a property P and an object O with the property P, find something "material" establishing the property P; for example, given two conjugate elements of a group, find a conjugator. In this survey our focus is on various search problems in group theory, including the word search problem, the subgroup membership search problem, the conjugacy search problem, and others.

http://arxiv.org/abs/1010.0382

22. Basic results on braid groups

Juan Gonzalez-Meneses

To appear in Annales Math\'ematiques Blaise Pascal. 45 pages, 11 figures

These are Lecture Notes of a course given by the author at the French-Spanish School "Tresses in Pau", held in Pau (France) in October 2009. It is basically an introduction to distinct approaches and techniques that can be used to show results in braid groups. Using these techniques we provide several proofs of well known results in braid groups, namely the correctness of Artin's presentation, that the braid group is torsion free, or that its center is generated by the full twist. We also recall some solutions of the word and conjugacy problems, and that roots of a braid are always conjugate. We also describe the centralizer of a given braid. Most proofs are classical ones, using modern terminology. I have chosen those which I find simpler or more beautiful.

http://arxiv.org/abs/1010.0321

23. The rate of escape on polycyclic and solvable groups

Russ Thompson

We show that the expected distance of a random walk from the origin behaves like n^{1/2} for a class of Abelian-by-cyclic groups. This class contains both polycyclic and non-polycyclic groups; in particular, Sol and the Baumslag-Solitar groups BS(1,q). We also show that there are non-Abelian-by-cyclic polycyclic groups with random walks whose expected distance from the origin behaves like n^{1/2} by considering subgroup distortion in such groups. In addition, we prove a law of iterated logarithm on these groups.

http://arxiv.org/abs/1010.0983

24. Presenting parabolic subgroups

Fran\c{c}ois Dahmani and Vincent Guirardel

Consider a relatively hyperbolic group G. We prove that if G is finitely presented, so are its parabolic subgroups. Moreover, a presentation of the parabolic subgroups can be found algorithmically from a presentation of G, a solution of its word problem, and generating sets of the parabolic subgroups. We also give an algorithm that finds parabolic subgroups in a given recursively enumerable class of groups.

http://arxiv.org/abs/1010.1083

25. The conjugacy problem is not solvable in automaton groups

Zoran Sunic, Enric Ventura

(Free-abelian)-by-free, self-similar groups generated by finite self-similar sets of tree automorphisms that have unsolvable conjugacy problem are constructed. Along the way, orbit undecidable, free subgroups of GL_d(Z), for d > 5, and Aut(F_d), for d > 4 are constructed as well.

http://arxiv.org/abs/1010.1993

26. Tutorial on the braid groups

Dale Rolfsen

This is an introduction to the braid groups, as presented in the summer school and workshop on braid groups at the National University of Singapore in June 2007.

http://arxiv.org/abs/1010.4051