{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T04:09:11Z","timestamp":1648958951137},"reference-count":44,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2015,5]]},"abstract":"<jats:p> In this paper, we study complexity of randomly generated instances of Dehn search problems in finitely presented groups. We use Crump\u2013Mode\u2013Jagers (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\u2013Magyarik public key encryption protocol the majority of random keys can be broken by a polynomial time algorithm. <\/jats:p>","DOI":"10.1142\/s0218196715500058","type":"journal-article","created":{"date-parts":[[2015,1,29]],"date-time":"2015-01-29T02:17:05Z","timestamp":1422497825000},"page":"445-480","source":"Crossref","is-referenced-by-count":1,"title":["Search problems in groups and branching processes"],"prefix":"10.1142","volume":"25","author":[{"given":"Pavel","family":"Morar","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Stevens Institute of Technology, 1 Castle Point on Hudson, Hoboken, New Jersey 07030, USA"}]},{"given":"Alexander","family":"Ushakov","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Stevens Institute of Technology, 1 Castle Point on Hudson, Hoboken, New Jersey 07030, USA"}]}],"member":"219","published-online":{"date-parts":[[2015,4,9]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.2307\/3213469"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004604"},{"key":"rf4","doi-asserted-by":"crossref","unstructured":"J. D.\u00a0Biggins, Classical and Modern Branching Processes, The IMA Volumess in Mathematics and Its Applications\u00a084 (Springer, 1996)\u00a0pp. 19\u201340.","DOI":"10.1007\/978-1-4612-1862-3_2"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-7152(96)00092-2"},{"key":"rf6","first-page":"137","volume":"33","author":"Birget J.-C.","year":"2006","journal-title":"Tatra Mountains Math. Publ."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.44.10.1061"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01101402"},{"key":"rf9","series-title":"Advanced Courses in Mathematics CRM Barcelona","volume-title":"The Geometry of the Word Problem for Finitely Generated Groups","author":"Brady N.","year":"2007"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.2307\/1970200"},{"key":"rf11","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1215\/ijm\/1256044631","volume":"30","author":"Collins D. J.","year":"1986","journal-title":"Illinois J. Math."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(68)90005-X"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/360\/06566"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5930"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/BF00265991"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12788-9_7"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80093-4"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019682203828"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(79)90238-2"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996611"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-51866-9"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.2307\/1427068"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.2001.9033"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(03)00167-4"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996266"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1007\/11779360_25"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-009-9307-x"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61896-3"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004977"},{"key":"rf33","series-title":"Advanced Courses in Mathematics \u2014 CRM Barcelona","volume-title":"Group-based cryptography","author":"Miasnikov A. G.","year":"2008"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1090\/surv\/177"},{"key":"rf35","first-page":"121","volume":"3","author":"Miasnikov A. G.","year":"2011","journal-title":"Groups Complex. Cryptol."},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2011.03.019"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1007\/BF00534830"},{"key":"rf38","first-page":"1","volume":"44","author":"Novikov P.","year":"1955","journal-title":"Proc. Steklov Inst."},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-3618-1"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(84)90141-0"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993000"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050207"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01350654"},{"key":"rf44","doi-asserted-by":"publisher","DOI":"10.1515\/gcc.2010.015"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1007\/BF02095993"},{"key":"rf46","doi-asserted-by":"publisher","DOI":"10.1017\/S0013091500008221"},{"key":"rf47","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706003396"},{"key":"rf49","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-003-0135-3"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196715500058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:04:40Z","timestamp":1565136280000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196715500058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,9]]},"references-count":44,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2015,4,9]]},"published-print":{"date-parts":[[2015,5]]}},"alternative-id":["10.1142\/S0218196715500058"],"URL":"https:\/\/doi.org\/10.1142\/s0218196715500058","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,9]]}}}