**Contemporary Mathematics**

Volume: 677;
2016;
229 pp;
Softcover

MSC: Primary 20; 68;

**Print ISBN: 978-1-4704-2303-2
Product Code: CONM/677**

List Price: $108.00

AMS Member Price: $86.40

MAA Member Price: $97.20

**Electronic ISBN: 978-1-4704-3587-5
Product Code: CONM/677.E**

List Price: $108.00

AMS Member Price: $86.40

MAA Member Price: $97.20

# Algebra and Computer Science

Share this page *Edited by *
*Delaram Kahrobaei; Bren Cavallo; David Garber*

This volume contains the proceedings of three
special sessions: Algebra and Computer Science, held during the Joint
AMS-EMS-SPM meeting in Porto, Portugal, June 10–13, 2015;
Groups, Algorithms, and Cryptography, held during the Joint
Mathematics Meeting in San Antonio, TX, January 10–13, 2015; and
Applications of Algebra to Cryptography, held during the Joint
AMS-Israel Mathematical Union meeting in Tel-Aviv, Israel, June
16–19, 2014.

Papers contained in this volume address a
wide range of topics, from theoretical aspects of algebra, namely
group theory, universal algebra and related areas, to applications in
several different areas of computer science.

From the
computational side, the book aims to reflect the rapidly emerging area
of algorithmic problems in algebra, their computational complexity and
applications, including information security, constraint satisfaction
problems, and decision theory.

The book gives special attention
to recent advances in quantum computing that highlight the need for a
variety of new intractability assumptions and have resulted in a new
area called group-based cryptography.

#### Readership

Graduate students and research mathematicians interested in cryptography, algebra, group theory, semigroup theory, information security, and theoretical computer science.

# Table of Contents

## Algebra and Computer Science

- Cover Cover11
- Title page iii4
- Contents v6
- Preface vii8
- Generic properties of subgroups of free groups and finite presentations 110
- A new multi-server scheme for private information retrieval 4554
- On secret sharing protocols 5160
- 1. Introduction 5160
- 2. The Shamir Secret Sharing Scheme 5261
- 3. Alternatives for Secret Sharing Protocols 5463
- 4. Comparison of Secret Sharing Protocols 6170
- 5. Verifying Secret Sharing Protocols (VSS) 6473
- 6. A New Secret Sharing Protocol Using Combinatorial Group Theory 6675
- 7. A Variation of the Secret Sharing Scheme based on Nielsen Transformations 7584
- 8. A Secret Sharing Protocol based on the Hurwitz Equation 7685
- References 7786

- A verifiable secret sharing scheme using non-abelian groups 7988
- Non-associative public-key cryptography 8594
- Non-associative key establishment protocols and their implementation 113122
- Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups 129138
- 1. Introduction 129138
- 2. Nilpotent and polycyclic groups 130139
- 3. Subset sum and knapsack problems in groups 131140
- 4. Subset sum problems in nilpotent groups 132141
- 5. Subset sum in polycyclic groups 134143
- 6. Knapsack problems in nilpotent groups 136145
- 7. Knapsack problems for finite extensions 140149
- 8. Knapsack problems for co-context-free groups 141150
- References 143152

- On the Tits alternative for a class of finitely presented groups with a special focus on symbolic computations 145154
- Geometry of the conjugacy problem in lamplighter groups 171180
- A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups 185194
- Cryptographic hash functions from sequences of lifted Paley graphs 213222
- 1. Preliminaries 214223
- 2. Construction of a hash function from an expander graph 218227
- 3. Paley Graphs 218227
- 4. 2-Lifted Paley Graphs Based Hash Function Scheme 222231
- 5. Expander Properties of 2-lifted Graphs 223232
- 6. Implementation Efficiency 224233
- 7. Cryptanalysis of our hash function 225234
- 8. Acknowledgements 226235
- Appendix A. Examples and Analysis 227236
- List of Figures 228237
- References 229238

- Back Cover Back Cover1242