TY - JOUR
T1 - Diophantine cryptography in free metabelian groups
T2 - Theoretical base
AU - Myasnikov, Alexei
AU - Roman'Kov, Vitalii
N1 - Publisher Copyright:
© 2014 by De Gruyter.
PY - 2014/11/1
Y1 - 2014/11/1
N2 - In this paper we study so-called Diophantine cryptology, a collection of cryptographic schemes where the computational security assumptions are based on hardness of solving some Diophantine equations, and some general ideas and techniques that occur in this area. In particular, we study an interesting variation of the endomorphism problem in groups, termed the double endomorphism problem. We prove that this problem is undecidable in free metabelian groups of sufficiently large rank. We relate this result to computational security assumptions of some group-based cryptosystems. In particular, we show how to improve the Grigoriev-Shpilrain's protocol to get a new computational security assumption based on the double endomorphism problem, providing a better theoretical foundation to security.
AB - In this paper we study so-called Diophantine cryptology, a collection of cryptographic schemes where the computational security assumptions are based on hardness of solving some Diophantine equations, and some general ideas and techniques that occur in this area. In particular, we study an interesting variation of the endomorphism problem in groups, termed the double endomorphism problem. We prove that this problem is undecidable in free metabelian groups of sufficiently large rank. We relate this result to computational security assumptions of some group-based cryptosystems. In particular, we show how to improve the Grigoriev-Shpilrain's protocol to get a new computational security assumption based on the double endomorphism problem, providing a better theoretical foundation to security.
KW - Free metabelian group
KW - authentication
KW - cryptosystems
KW - endomorphism problem
UR - http://www.scopus.com/inward/record.url?scp=84922008355&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84922008355&partnerID=8YFLogxK
U2 - 10.1515/gcc-2014-0011
DO - 10.1515/gcc-2014-0011
M3 - Article
AN - SCOPUS:84922008355
SN - 1867-1144
VL - 6
SP - 103
EP - 120
JO - Groups, Complexity, Cryptology
JF - Groups, Complexity, Cryptology
IS - 2
ER -