Generic subgroups of group amalgams

Benjamin Fine, Alexei Miasnikov, Gerhard Rosenberger

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

For many groups the structure of finitely generated subgroups is generically simple. That is with asymptotic density equal to one a randomly chosen finitely generated subgroup has a particular well-known and easily analyzed structure. For example a result of D. B. A. Epstein says that a finitely generated subgroup of GL(n, ℝ) is generically a free group. We say that a group G has the generic free group property if any finitely generated subgroup is generically a free group. Further G has the strong generic free group property if given randomly chosen elements g 1,..., g n in G then generically they are a free basis for the free subgroup they generate. In this paper we show that for any arbitrary free product of finitely generated infinite groups satisfies the strong generic free group property. There are also extensions to more general amalgams - free products with amalgamation and HNN groups. These results have implications in cryptography. In particular several cryptosystems use random choices of subgroups as hard cryptographic problems. In groups with the generic free group property any such cryptosystem may be attackable by a length based attack.

Original languageEnglish (US)
Pages (from-to)51-61
Number of pages11
JournalGroups, Complexity, Cryptology
Volume1
Issue number1
DOIs
StatePublished - Apr 1 2009

Fingerprint

Amalgam
Mercury amalgams
Free Group
Cryptography
Subgroup
Finitely Generated
Cryptosystem
Free Product with Amalgamation
Asymptotic Density
Free Product
Infinite Groups
Finitely Generated Group
Attack
Arbitrary

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics

Cite this

Fine, Benjamin ; Miasnikov, Alexei ; Rosenberger, Gerhard. / Generic subgroups of group amalgams. In: Groups, Complexity, Cryptology. 2009 ; Vol. 1, No. 1. pp. 51-61.
@article{2bcb6d5ef9a34054bd45f199e266ca3b,
title = "Generic subgroups of group amalgams",
abstract = "For many groups the structure of finitely generated subgroups is generically simple. That is with asymptotic density equal to one a randomly chosen finitely generated subgroup has a particular well-known and easily analyzed structure. For example a result of D. B. A. Epstein says that a finitely generated subgroup of GL(n, ℝ) is generically a free group. We say that a group G has the generic free group property if any finitely generated subgroup is generically a free group. Further G has the strong generic free group property if given randomly chosen elements g 1,..., g n in G then generically they are a free basis for the free subgroup they generate. In this paper we show that for any arbitrary free product of finitely generated infinite groups satisfies the strong generic free group property. There are also extensions to more general amalgams - free products with amalgamation and HNN groups. These results have implications in cryptography. In particular several cryptosystems use random choices of subgroups as hard cryptographic problems. In groups with the generic free group property any such cryptosystem may be attackable by a length based attack.",
author = "Benjamin Fine and Alexei Miasnikov and Gerhard Rosenberger",
year = "2009",
month = "4",
day = "1",
doi = "https://doi.org/10.1515/GCC.2009.51",
language = "English (US)",
volume = "1",
pages = "51--61",
journal = "Groups, Complexity, Cryptology",
issn = "1867-1144",
publisher = "Walter de Gruyter GmbH & Co. KG",
number = "1",

}

Generic subgroups of group amalgams. / Fine, Benjamin; Miasnikov, Alexei; Rosenberger, Gerhard.

In: Groups, Complexity, Cryptology, Vol. 1, No. 1, 01.04.2009, p. 51-61.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Generic subgroups of group amalgams

AU - Fine, Benjamin

AU - Miasnikov, Alexei

AU - Rosenberger, Gerhard

PY - 2009/4/1

Y1 - 2009/4/1

N2 - For many groups the structure of finitely generated subgroups is generically simple. That is with asymptotic density equal to one a randomly chosen finitely generated subgroup has a particular well-known and easily analyzed structure. For example a result of D. B. A. Epstein says that a finitely generated subgroup of GL(n, ℝ) is generically a free group. We say that a group G has the generic free group property if any finitely generated subgroup is generically a free group. Further G has the strong generic free group property if given randomly chosen elements g 1,..., g n in G then generically they are a free basis for the free subgroup they generate. In this paper we show that for any arbitrary free product of finitely generated infinite groups satisfies the strong generic free group property. There are also extensions to more general amalgams - free products with amalgamation and HNN groups. These results have implications in cryptography. In particular several cryptosystems use random choices of subgroups as hard cryptographic problems. In groups with the generic free group property any such cryptosystem may be attackable by a length based attack.

AB - For many groups the structure of finitely generated subgroups is generically simple. That is with asymptotic density equal to one a randomly chosen finitely generated subgroup has a particular well-known and easily analyzed structure. For example a result of D. B. A. Epstein says that a finitely generated subgroup of GL(n, ℝ) is generically a free group. We say that a group G has the generic free group property if any finitely generated subgroup is generically a free group. Further G has the strong generic free group property if given randomly chosen elements g 1,..., g n in G then generically they are a free basis for the free subgroup they generate. In this paper we show that for any arbitrary free product of finitely generated infinite groups satisfies the strong generic free group property. There are also extensions to more general amalgams - free products with amalgamation and HNN groups. These results have implications in cryptography. In particular several cryptosystems use random choices of subgroups as hard cryptographic problems. In groups with the generic free group property any such cryptosystem may be attackable by a length based attack.

UR - http://www.scopus.com/inward/record.url?scp=84858374173&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858374173&partnerID=8YFLogxK

U2 - https://doi.org/10.1515/GCC.2009.51

DO - https://doi.org/10.1515/GCC.2009.51

M3 - Article

VL - 1

SP - 51

EP - 61

JO - Groups, Complexity, Cryptology

JF - Groups, Complexity, Cryptology

SN - 1867-1144

IS - 1

ER -