Search problems in groups and branching processes

Pavel Morar, Alexander Ushakov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish
Pages (from-to)445-480
Number of pages36
JournalInternational Journal of Algebra and Computation
Volume25
Issue number3
DOIs
StatePublished - 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