[Resource Topic] 2021/429: New Practical Multivariate Signatures from a Nonlinear Modifier

Welcome to the resource topic for 2021/429

New Practical Multivariate Signatures from a Nonlinear Modifier

Authors: 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.

ePrint: https://eprint.iacr.org/2021/429

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .