Paper 2022/1684 Original: eprint.iacr.org/2022/1684 ↗
Division in the Plactic Monoid
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.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2022-12-04: last updated
- 2022-12-04: published
- Short URL
- https://ia.cr/2022/1684
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}