Paper 2021/938

Plactic signatures

Daniel R. L. Brown

Abstract

Plactic signatures use the plactic monoid (semistandard tableaus with Knuth’s associative multiplication) and full-domain hashing (SHAKE).

Note: This version adds (1) a fifth implementation of plactic monoid multiplication, which speeds up verification by a further 15% (so, about 30% faster than the reference implementation), and (2) a preliminary ad hoc implementation of compression, which can compress a 1000-byte public key or signature to about 570 bytes (on average).