On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product

Any Muanalifah; Sergei Sergeev

doi:10.1080/00927872.2021.1975125

On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product

Any Muanalifah, Sergei Sergeev

Mathematics

Research output: Contribution to journal › Article › peer-review

57 Downloads (Pure)

Abstract

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: “Given that A = V ⊗ F^⊗tfor a unique t and matrices A, V, F of appropriate dimensions, find this t.” We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

Original language	English
Pages (from-to)	861-879
Number of pages	19
Journal	Communications in Algebra
Volume	50
Issue number	2
Early online date	20 Sept 2021
DOIs	https://doi.org/10.1080/00927872.2021.1975125
Publication status	Published - 1 Feb 2022

Bibliographical note

Funding Information:
We would like to thank the anonymous referee of our paper for their careful reading, useful comments and appreciation of our work.

Publisher Copyright:
© 2021 Taylor & Francis Group, LLC.

Keywords

Cryptanalysis
matrix powers
semidirect product
tropical algebra

ASJC Scopus subject areas

Algebra and Number Theory

Access to Document

10.1080/00927872.2021.1975125Licence: None: All rights reserved

MuanalifahA2021tropical
This is an Accepted Manuscript version of the following article, accepted for publication in Communications in Algebra. Any Muanalifah & Sergeĭ Sergeev (2021) On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product, Communications in Algebra, DOI: 10.1080/00927872.2021.1975125. It is deposited under the terms of the Creative Commons Attribution-NonCommercial-NoDerivatives License (http://creativecommons.org/licenses/by-nc-nd/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited, and is not altered, transformed, or built upon in any way.
Accepted author manuscript, 346 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

Cite this

@article{c7befe968e5f4bde91446b44c85e5f4c,

title = "On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product",

abstract = "Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: “Given that A = V ⊗ F⊗t for a unique t and matrices A, V, F of appropriate dimensions, find this t.” We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.",

keywords = "Cryptanalysis, matrix powers, semidirect product, tropical algebra",

author = "Any Muanalifah and Sergei Sergeev",

note = "Funding Information: We would like to thank the anonymous referee of our paper for their careful reading, useful comments and appreciation of our work. Publisher Copyright: {\textcopyright} 2021 Taylor & Francis Group, LLC.",

year = "2022",

month = feb,

day = "1",

doi = "10.1080/00927872.2021.1975125",

language = "English",

volume = "50",

pages = "861--879",

journal = "Communications in Algebra",

issn = "0092-7872",

publisher = "Taylor & Francis",

number = "2",

}

TY - JOUR

T1 - On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product

AU - Muanalifah, Any

AU - Sergeev, Sergei

N1 - Funding Information: We would like to thank the anonymous referee of our paper for their careful reading, useful comments and appreciation of our work. Publisher Copyright: © 2021 Taylor & Francis Group, LLC.

PY - 2022/2/1

Y1 - 2022/2/1

N2 - Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: “Given that A = V ⊗ F⊗t for a unique t and matrices A, V, F of appropriate dimensions, find this t.” We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

AB - Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain as a promising platform for implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: “Given that A = V ⊗ F⊗t for a unique t and matrices A, V, F of appropriate dimensions, find this t.” We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

KW - Cryptanalysis

KW - matrix powers

KW - semidirect product

KW - tropical algebra

UR - http://www.scopus.com/inward/record.url?scp=85115208019&partnerID=8YFLogxK

U2 - 10.1080/00927872.2021.1975125

DO - 10.1080/00927872.2021.1975125

M3 - Article

SN - 0092-7872

VL - 50

SP - 861

EP - 879

JO - Communications in Algebra

JF - Communications in Algebra

IS - 2

ER -

On the tropical discrete logarithm problem and security of a protocol based on tropical semidirect product

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this