Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

New Practical Multivariate Signatures from a Nonlinear Modifier

Published

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

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 October 26, 2021)
Created April 1, 2021, Updated July 13, 2021