Abstract
In this paper, we study complexity of randomly generated instances of Dehn search problems in finitely presented groups. We use Crump-Mode-Jagers (CMJ) processes to show that most of the random instances are easy. Our analysis shows that for any choice of a finitely presented platform group in Wagner-Magyarik public key encryption protocol the majority of random keys can be broken by a polynomial time algorithm.
| Original language | English |
|---|---|
| Pages (from-to) | 445-480 |
| Number of pages | 36 |
| Journal | International Journal of Algebra and Computation |
| Volume | 25 |
| Issue number | 3 |
| DOIs | |
| State | Published - 25 May 2015 |
Keywords
- (generalized) van Kampen diagrams
- Crump-Mode-Jagers process
- Wagner-Magyarik cryptosystem
- Word search problem
- annular diagrams
- conjugacy search problem
- group-based cryptography
- membership search problem
Fingerprint
Dive into the research topics of 'Search problems in groups and branching processes'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver