# Computational and Combinatorial Group Theory and Cryptography

Share this page *Edited by *
*Benjamin Fine; Delaram Kahrobaei; Gerhard Rosenberger*

This volume contains the proceedings of the
AMS Special Session on Computational Algebra, Groups, and
Applications, held April 30–May 1, 2011, at the University of
Nevada, Las Vegas, Nevada, and the AMS Special Session on the
Mathematical Aspects of Cryptography and Cyber Security, held
September 10–11, 2011, at Cornell University, Ithaca, New York.

Over the past twenty years combinatorial and infinite group theory
has been energized by three developments: the emergence of geometric
and asymptotic group theory, the development of algebraic geometry
over groups leading to the solution of the Tarski problems, and the
development of group-based cryptography. These three areas in turn
have had an impact on computational algebra and complexity theory.

The papers in this volume, both survey and research, exhibit the
tremendous vitality that is at the heart of group theory in the
beginning of the twenty-first century as well as the diversity of
interests in the field.

# Table of Contents

## Computational and Combinatorial Group Theory and Cryptography

- Preface vii8 free
- Weyl Gröbner Basis Cryptosystems 110 free
- A New Look at Finitely Generated Metabelian Groups 2130
- 1. Introductory remarks 2130
- 2. Philip Hall’s approach 2231
- 3. A few properties of finitely generated metabelian groups 2231
- 4. The Bieri-Strebel invariant 2332
- 5. The geometry of the Cayley graph and metabelian presentations 2433
- 6. Hilbert functions 2433
- 7. Where to go from here 2534
- 8. Affine algebraic sets, localization and completions 2534
- 9. A new approach to the isomorphism problem for finitely generated metabelian groups 2635
- 10. Localization of finitely generated, residually nilpotent, metabelian groups and the Telescope Theorem 2736
- 11. Embedding groups and localization 2938
- 12. Some of the implications of the use of localization 3039
- 13. Classifying para-equivalent metabelian groups 3140
- 14. Examples 3342
- 15. Further examples and Dedekind domains 3443
- References 3645

- 𝐼𝐴-Automorphisms of Groups with Almost Constant Upper Central Series 3948
- A Proposed Alternative to the Shamir Secret Sharing Scheme 4756
- Improving Latin Square Based Secret Sharing Schemes 5160
- 1. Introduction 5160
- 2. Cryptographic hash functions 5261
- 3. Secret sharing schemes 5261
- 4. Latin square 5463
- 5. Application of critical set in secret sharing 5564
- 6. Limitations of Latin square based schemes 5665
- 7. Apply hash function to Latin square based schemes 5766
- 8. Conclusion and Future Research 6271
- References 6372

- A Hand-Computation Involving Surface Groups, the Reidemeister-Schreier Rewriting Process and Kurosh Subgroup Theorem 6574
- Adjunction of Roots in Exponential A-Groups 7180
- Logspace Computations in Coxeter Groups and Graph Groups 7786
- Collection by Polynomials in Finite 𝑝-groups 95104
- All Finite Generalized Tetrahedon Groups II 105114
- The Classification of One Relator Limit Groups and the Surface Group Conjecture 107116
- 1. Introduction 107116
- 2. Surface Groups and The Surface Group Conjecture 109118
- 3. Cyclically Pinched and Conjugacy Pinched One Relator Groups 111120
- 4. Fully Residually Free Groups 113122
- 5. Property IF and Results on the Surface Group Conjecture 114123
- 6. Baumslag Doubles and a Question of Gromov 116125
- 7. The Free-by-Cyclic Conjectures 117126
- 8. Approaches to the Classification of One Relator Limit Groups 118127
- 9. The Lyndon Properties 120129
- 10. The Classification of One Relator CSA Groups 122131
- References 124133

- Discrimination and Separation in the Metabelian Variety 129138
- A Secret Sharing Scheme Based on Group Presentations and the Word Problem 143152
- Authenticated Key Agreement with Key Re-Use in the Short Authenticated Strings Model 151160
- 1. Introduction 151160
- 2. Preliminaries 156165
- 3. Communication and Adversarial Model 158167
- 4. Encryption-based SAS Message Authentication Protocol 161170
- 5. Encryption-based SAS Authenticated Key Agreement Protocol 165174
- Appendix A. IND-CCA Encryption 168177
- Appendix B. Difficulty in Extending the General Compilation Theorem of Pasini-Vaudenay 169178
- Appendix C. Reductions ℬ_{𝒞}[1-3] in the Proof of Theorem 1 171180
- References 172181

- Publicly Verifiable Secret Sharing Using Non-Abelian Groups 175184
- A Note on the Hyperbolicity of Strict Pride Groups 181190
- An Algorithm to Express Words as a Product of Conjugates of Relators 187196