Paper 2021/429

New Practical Multivariate Signatures from a Nonlinear Modifier

Daniel Smith-Tone

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
post-quantumdigital signaturemultivariate
Contact author(s)
daniel smith @ nist gov
History
2021-04-06: received
Short URL
https://ia.cr/2021/429
License
Creative Commons Attribution
CC BY

BibTeX

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