Division in the Plactic Monoid

Chris Monico

Paper 2022/1684

Division in the Plactic Monoid

Chris Monico

, Texas Tech University

Abstract

In [1], a novel cryptographic key exchange technique was proposed using the plactic monoid, based on the apparent difficulty of solving division problems in that monoid. Specifically, given elements c, b in the plactic monoid, the problem is to find q for which qb = c, given that such a q exists. In this paper, we introduce a metric on the plactic monoid and use it to give a probabilistic algorithm for solving that problem which is fast for parameter values in the range of interest.

Note: Preprint of an article submitted for consideration in Journal of Algebra and Its Applications © 2022 [copyright World Scientific Publishing Company] https://www.worldscientific.com/worldscinet/jaa

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: plactic monoid young tableau
Contact author(s): c monico @ ttu edu
History: 2022-12-05: approved; 2022-12-04: received; See all versions
Short URL: https://ia.cr/2022/1684
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1684,
      author = {Chris Monico},
      title = {Division in the Plactic Monoid},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1684},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1684}
}