New Practical Multivariate Signatures from a Nonlinear Modifier

Published

April 1, 2021

Author(s)

Daniel Smith-Tone

Abstract

Multivariate cryptography is dominated by schemes supporting various modifiers to patch certain algebraic weaknesses. 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.

Citation

Cryptology ePrint Archive

Volume

2021

Pub Weblink

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

Pub Type

Websites

Download Paper

Local Download

Keywords

post-quantum, digital signature, multivariate

Citation

Smith-Tone, D. (2021), New Practical Multivariate Signatures from a Nonlinear Modifier, Cryptology ePrint Archive, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=932106, https://eprint.iacr.org/2021/429 (Accessed April 29, 2024)