Plactic key agreement (insecure?)

Daniel R.  L.  Brown

Paper 2021/625

Plactic key agreement (insecure?)

Daniel R. L. Brown, BlackBerry

Abstract

Plactic key agreement is a new key agreement scheme that uses Knuth’s multiplication of semistandard tableaus from combinatorial algebra. The security of plactic key agreement relies on the difficulty of some computational problems, such as division of semistandard tableaus. Division by erosion uses backtracking to divide tableaus. Division by erosion is estimated to be infeasible against public keys of 768 or more bytes. If division by erosion is the best attack against plactic key agreement, then secure plactic key agreement could be practical. Chris Monico found a new attack on plactic key agreement, which is fast, potentially polynomial-time, and could very well make plactic key agreement insecure.

Note: Chris Monico found a new attack on plactic key agreement, which is fast, potentially polynomial-time, and could very well make plactic key agreement insecure.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Journal of Mathematical Cryptology
Keywords: key agreement key exchange combinatorics plactic monoid semistandard tableau
Contact author(s): danibrown @ blackberry com
History: 2022-09-23: last of 6 revisions; 2021-05-17: received; See all versions
Short URL: https://ia.cr/2021/625
License: CC BY

BibTeX

@misc{cryptoeprint:2021/625,
      author = {Daniel R.  L.  Brown},
      title = {Plactic key agreement (insecure?)},
      howpublished = {Cryptology ePrint Archive, Paper 2021/625},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/625}},
      url = {https://eprint.iacr.org/2021/625}
}