Research ArticleNo Access

Division in the plactic monoid

Department of Mathematics and Statistics, Texas Tech University, Lubbock, TX 79424, USA

https://doi.org/10.1142/S021949882550080XCited by:0 (Source: Crossref)

This article is part of the issue:

Special Issue on Recent Advances in Coding Theory and Cryptography In honor of Joachim Rosenthal
Guest Editors: Elisa Gorla, Anna-Lena Horlemann, Roxana Smarandache and Jens Zumbrägel

Abstract

In [D. R. L. Brown, Plactic key agreement (insecure?), J. Math. Cryptol.17(1) (2023) 20220010], 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$ $c, b$ in the plactic monoid, the problem is to find $q$ for which $q b = 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.

Communicated by E. Gorla

Keywords:

AMSC: 20M05, 94A60

References

1. D. R. L. Brown , Plactic key agreement (insecure?), J. Math. Crypt. 17(1) (2023) 20220010. Crossref, Google Scholar
2. D. E. Knuth , Permutations, matrices, and generalized Young tableaux, Pac. J. Math. 34(3) (1970) 709–727. Crossref, Web of Science, Google Scholar
3. M. Lothaire , Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications (Cambridge University Press, 2002). Crossref, Google Scholar
4. M. Rabi and A. T. Sherman, Associative one-way functions: A new paradigm for secret-key agreement and digital signatures, Technical report, USA (1993). Google Scholar
5. C. Schensted , Longest increasing and decreasing subsequences, Can. J. Math. 13 (1961) 179–191. Crossref, Web of Science, Google Scholar
6. P. W. Shor , Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. 35th Ann. Symp. Foundations of Computer Science (Sante Fe, NM, USA, 1994), pp. 124–134. Crossref, Google Scholar