{
  "id": "1407.1685",
  "version": "v1",
  "published": "2014-07-07T12:35:14.000Z",
  "updated": "2014-07-07T12:35:14.000Z",
  "title": "Search problems in groups and branching processes",
  "authors": [
    "Pavel Morar",
    "Alexander Ushakov"
  ],
  "categories": [
    "math.GR"
  ],
  "abstract": "In this paper we study complexity of randomly generated instances of Dehn search problems in finitely presented groups. We use Crump-Mode-Jagers 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-Wagner public key encryption protocol the majority of random keys can be broken by a polynomial time algorithm.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-07-07T12:35:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "03D15",
      "20F65"
    ],
    "keywords": [
      "branching processes",
      "dehn search problems",
      "polynomial time algorithm",
      "crump-mode-jagers processes",
      "random instances"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1407.1685M"
    }
  }
}