TY - JOUR
T1 - Search problems in groups and branching processes
AU - Morar, Pavel
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2015 World Scientific Publishing Company.
PY - 2015/5/25
Y1 - 2015/5/25
N2 - 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.
AB - 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.
KW - (generalized) van Kampen diagrams
KW - Crump-Mode-Jagers process
KW - Wagner-Magyarik cryptosystem
KW - Word search problem
KW - annular diagrams
KW - conjugacy search problem
KW - group-based cryptography
KW - membership search problem
UR - http://www.scopus.com/inward/record.url?scp=84928774960&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84928774960&partnerID=8YFLogxK
U2 - 10.1142/S0218196715500058
DO - 10.1142/S0218196715500058
M3 - Article
AN - SCOPUS:84928774960
SN - 0218-1967
VL - 25
SP - 445
EP - 480
JO - International Journal of Algebra and Computation
JF - International Journal of Algebra and Computation
IS - 3
ER -