Diophantine cryptography in free metabelian groups: Theoretical base

Alexei Myasnikov, Vitalii Roman'Kov

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)103-120
Number of pages18
JournalGroups, Complexity, Cryptology
Volume6
Issue number2
DOIs
StatePublished - 1 Nov 2014

Keywords

  • Free metabelian group
  • authentication
  • cryptosystems
  • endomorphism problem

Fingerprint

Dive into the research topics of 'Diophantine cryptography in free metabelian groups: Theoretical base'. Together they form a unique fingerprint.

Cite this