Paper 2021/429

New Practical Multivariate Signatures from a Nonlinear Modifier

Daniel Smith-Tone


Multivariate cryptography is dominated by schemes supporting various tweaks, or ``modifiers,'' designed to patch certain algebraic weaknesses they would otherwise exhibit. Typically these modifiers are linear in nature--- either requiring an extra composition with an affine map, or being evaluated by a legitimate user via an affine projection. This description applies to the minus, plus, vinegar and internal perturbation modifiers, to name a few. Though it is well-known that combinations of various modifiers can offer security against certain classes of attacks, cryptanalysts have produced ever more sophisticated attacks against various combinations of these linear modifiers. In this article, we introduce a more fundamentally nonlinear modifier, called Q, that is inspired from relinearization. The effect of the Q modifier on multivariate digital signature schemes is to maintain inversion efficiency at the cost of slightly slower verification and larger public keys, while altering the algebraic properties of the public key. Thus the Q modifier is ideal for applications of digital signature schemes requiring very fast signing and verification without key transport. As an application of this modifier, we propose new multivariate digital signature schemes with fast signing and verification that are resistant to all known attacks.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
post-quantumdigital signaturemultivariate
Contact author(s)
daniel smith @ nist gov
2021-04-06: received
Short URL
Creative Commons Attribution


      author = {Daniel Smith-Tone},
      title = {New Practical Multivariate Signatures from a Nonlinear Modifier},
      howpublished = {Cryptology ePrint Archive, Paper 2021/429},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.