Efficient Multivariate Signature Generation

A cryptographic method, comprising:

• receiving a message with a digital signature X, for verification using a predefined public key, which defines a multivariate polynomial mapping Q( ) over a finite field F;
• extracting a first vector Y of verification values from the received message;
• applying the multivariate polynomial mapping to the digital signature so as to find a second vector of output values Q(X);
• and
• authenticating the message by finding a factor aεF such that each output value is equal to the corresponding element of a vector sum Y+aYSHIFT.

A cryptographic method, comprising:

• providing a public key that defines a multivariate polynomial mapping Q( ) over a finite field F;
• extracting a first vector Y of verification values from a message;
• computing over the first vector, using a processor, a digital signature X comprising a second vector of signature values such that application of the mapping to the digital signature gives a third vector Q(X) of output values such that each output value is equal to a corresponding element of a vector sum Y+aYSHIFT over F, wherein YSHIFT is a shifted version of Y, and aεF;
• applying an affine transform B−1 to the first vector Y in order to compute an intermediate vector Z′;
• applying a univariate polynomial function P−1(Z′), corresponding to the multivariate polynomial mapping, over an extension field of F in order to find the digital signature in a polynomial representation X′;
• and
• conveying the message with the digital signature to a recipient for authentication using the public key, wherein P−1(Z′)=(U(T))dZ′d, wherein U is a polynomial in the extension field over a variable T with at least one coefficient given by the factor a, and d is an exponent, and
• wherein computing the digital signature comprises precomputing and storing respective power vectors Va=(U(T))d for multiple possible factors a εF, and using the stored power values in order to compute and test multiple candidate digital signatures X′ for a given exponentiation of Z′→Z′d.

Cryptographic apparatus, comprising:

• a memory, which is configured to store a private key corresponding to a public key that defines a multivariate polynomial mapping Q( ) over a finite field F;
• and
• a processor, which is configured to extract a first vector Y of verification values from a message, and to compute over the first vector, using the private key, a digital signature X comprising a second vector of signature values such that application of the mapping to the digital signature gives a third vector Q(X) of output values such that each output value is equal to a corresponding element of a vector sum Y+aYSHIFT over F, wherein YSHIFT is a shifted version of Y, and aεF, and to convey the message with the digital signature to a recipient for authentication using the public key,
• wherein the processor is configured to compute the digital signature by applying an affine transform B−1 to the first vector Y in order to compute an intermediate vector Z′, and applying a univariate polynomial function P−1(Z′), corresponding to the multivariate polynomial mapping, over an extension field of F in order to find the digital signature in a polynomial representation X′,
• wherein P−1(Z′)=(U(T))dZ′d, wherein U is a polynomial in the extension field over a variable T with at least one coefficient given by the factor a, and d is an exponent, and
• wherein the processor is configure to precompute and store respective power vectors Va=(U(T))d for multiple possible factors aεF, and to use the stored power values in order to compute and test multiple candidate digital signatures X′ for a given exponentiation of Z′→Z′d.