Multivariate signatures based on identification schemes

15 Feb 2025

Introduction

The goal of an identification protocol is to enable the verification of someone’s identity. More specifically, a Prover must demonstrate to an interlocutor, called the Verifier, that they possess a certain secret without revealing any information about the secret itself. In the field of cryptography, numerous identification protocols are based on various mathematical problems. These protocols are of particular interest in the context of the transition to post-quantum algorithms, as they can serve as the foundation for constructing digital signatures (an important example is the Dilithium scheme).

However, until the early 2000s, no identification protocols based on multivariate assumptions were known. A breakthrough occurred in 2011, when Sakumoto et al. proposed two identification protocols constructed from systems of multivariate equations over a finite field: one 3-pass and another 5-pass. From the latter, the MQDSS scheme was developed in 2016—a multivariate signature scheme submitted to the NIST standardization process.

While constructing a digital signature from a 3-pass protocol can be achieved using a standard procedure (through the well-known Fiat-Shamir transform), an analogous approach for a 5-pass protocol is more challenging and intriguing.

Although MQDSS was ultimately excluded from the NIST competition and no multivariate schemes based on identification protocols are currently part of the standardization process, significant theoretical advancements have made this approach increasingly competitive.

3-pass Identification Schemes

Typically, an identification protocol consists of multiple interactions between the Prover and the Verifier. A 3-pass protocol is generally characterized by a well-defined structure. The Prover initially sends a first message, called the Commitment, to which the Verifier responds with a Challenge. Finally, the Prover sends a final message, called the Response, which provides proof of the Prover’s knowledge of a certain secret. Protocols with this structure are also referred to as Sigma Protocols.

The work of Sakumoto et al. was the first to propose an identification scheme based on multivariate assumptions. The 3-pass protocol is described below.

Let $\mathcal{F}$ be a multivariate system of $m$ equations in $n$ variables over $\mathbb{F}_q$ , and let $\mathcal{G}(\mathbf{x},\mathbf{y}) = \mathcal{F}(\mathbf{x}+\mathbf{y}) - \mathcal{F}(\mathbf{x}) - \mathcal{F}(\mathbf{y})$ denote its polar form.
Given $\mathcal{F}$ as an instance of the $\mathcal{MQ}$ problem over $\mathbb{F}_q$ and a vector $\mathbf{v} \in \mathbb{F}_q^m$ , the $\mathcal{MQ}$ problem involves finding a vector $\mathbf{s} \in \mathbb{F}_q^n$ such that $\mathbf{v} = \mathcal{F}(\mathbf{s})$ .
Thus, after randomly choosing $\mathbf{s} \in \mathbb{F}_q^n$ , the key generation algorithm computes $\mathbf{v} = \mathcal{F}(\mathbf{s})$ and outputs $(pk, sk) = (\mathbf{v}, \mathbf{s})$ .

The core idea of the 3-pass identification protocol lies in the Prover demonstrating knowledge of a tuple $(\mathbf{r}_0, \mathbf{r}_1, \mathbf{t}_0, \mathbf{t}_1, \mathbf{e}_0, \mathbf{e}_1)$ that satisfies the following relationships:

$\mathcal{G}(\mathbf{t}_0, \mathbf{r}_1)+\mathbf{e}_0=\mathbf{v}-\mathcal{F}(\mathbf{r}_1)-\mathcal{G}(\mathbf{t}_1, \mathbf{r}_1)-\mathbf{e}_1$

$(\mathbf{t}_0, \mathbf{e}_0)=(\mathbf{r}_0-\mathbf{t}_1, \mathcal{F}(\mathbf{r}_0)-\mathbf{e}_1).$

In this way, we have $\mathbf{s} = \mathbf{r}_0 + \mathbf{r}_1$ and $\mathbf{v} = \mathcal{F}(\mathbf{r}_0 + \mathbf{r}_1)$ . Note that $\mathcal{G}$ is the polar form of $\mathcal{F}$ .

The Prover then generates $\mathbf{r}_0, \mathbf{t}_0 \in \mathbb{F}_q^n$ , and $\mathbf{e}_0 \in \mathbb{F}_q^m$ , and calculates $\mathbf{r}_1, \mathbf{t}_1, \mathbf{e}_1$ using the relationships described above. The Prover computes the commitments $c_0, c_1, c_2$ as outlined in the protocol and sends them to the Verifier. The Verifier responds with a Challenge, which consists of a random number chosen from $0$ , $1$ , or $2$ . Based on the Challenge, the Prover reveals only one of the three tuples $(\mathbf{r}_0, \mathbf{t}_1, \mathbf{e}_1)$ , $(\mathbf{r}_1, \mathbf{t}_1, \mathbf{e}_1)$ , or $(\mathbf{r}_1, \mathbf{t}_0, \mathbf{e}_0)$ .

The Verifier can then check that the received tuple satisfies the relationships by verifying the correctness of the commitments. On the other hand, knowing only one of the three tuples, the Verifier learns either $\mathbf{r}_0$ or $\mathbf{r}_1$ , but not both. Consequently, the Verifier gains no information about the private key $\mathbf{s}$ .
The Verifier outputs $1$ if both checks on the commitments pass; otherwise, it outputs $0$ .

A 3-pass protocol of this type is said to be correct, as the Verifier will always accept an interaction with an honest Prover.

5-Pass Identification Schemes

In the 5-pass protocol proposed by Sakumoto et al., the private and public keys are still divided as follows: $\mathbf{s} = \mathbf{r}_0 + \mathbf{r}_1$ and $\mathcal{F}(\mathbf{s}) = \mathcal{F}(\mathbf{r}_0 + \mathbf{r}_1) = \mathcal{F}(\mathbf{r}_0) + \mathcal{F}(\mathbf{r}_1) + \mathcal{G}(\mathbf{r}_0, \mathbf{r}_1)$ , similar to the 3-pass protocol. However, unlike the latter, in the 5-pass protocol, $\mathbf{e}_1$ and $\mathbf{t}_1$ are computed according to the relations $\alpha \mathbf{r}_0 = \mathbf{t}_0 + \mathbf{t}_1$ and $\alpha \mathcal{F}(\mathbf{r}_0) = \mathbf{e}_0 + \mathbf{e}_1$ where $\alpha \in \mathbb{F}_q$ is randomly chosen by the Verifier.

The two additional steps involve the Verifier sending a message containing the value $\alpha$ and the Prover responding with the pair $(\mathbf{t}_1, \mathbf{e}_1)$ .
Then, after receiving the challenge from the Verifier, the Prover responds with either $\mathbf{r}_0$ or $\mathbf{r}_1$ , depending on the challenge.

If $\mathbf{r}_0$ , $\mathbf{t}_0$ , and $\mathbf{e}_0$ are chosen randomly, the Verifier does not gain any information about the private key $\mathbf{s}$ by knowing only one of $\mathbf{r}_0$ or $\mathbf{r}_1$ . The Verifier outputs 1 if the verification succeeds and 0 otherwise.

As in the previous case, this 5-pass scheme is correct, as the Verifier always accepts interactions with an honest Prover.

A crucial aspect to consider in the study of identification protocols is the probability that the Prover cheats, known as the cheating probability. The cheating probability represents the likelihood that a dishonest Prover can convince the Verifier without knowing the secret. Ideally, if the Prover does not know the secret, the Verifier should accept the received response with a very low probability. In this case, the protocol is said to have a low knowledge error.

The previously described 3-pass protocol has a relatively high knowledge error of $2/3$ .

By extending the protocol to five passes, a lower (though still relatively high) knowledge error can be achieved, specifically $1/2 + 1/2q$ , where $q$ is the size of the finite field $\mathbb{F}_q$ over which the polynomial system is defined.

MQDSS signature

In 2016, Chen et al. introduced MQDSS as a multivariate signature scheme, which was later submitted to the PQC standardization process initiated by NIST.

MQDSS adapts the 5-pass identification scheme into a non-interactive signature using the Fiat-Shamir transform. While this transformation is a well-known technique for converting interactive (3-pass) identification schemes into signature schemes, MQDSS introduces additional challenges due to its 5-pass structure.

In a typical 3-pass identification scheme, the transformation works by replacing the Verifier’s random Challenge with a hash of the previous Commitment. This modification eliminates the need for interaction between the parties while preserving security properties, provided that the hash function is modeled as a random oracle. The random oracle assumption is fundamental, as it ensures that the Challenge remains unpredictable and cannot be manipulated by an adversary.

The case of MQDSS is particularly interesting because its underlying identification scheme includes two Challenge-Response steps, making the transformation more complex, as described below.
Before applying the Fiat-Shamir transformation, it is necessary to amplify the protocol’s soundness, i.e., to reduce the cheating probability of a dishonest Prover to a negligible level. Typically, this is achieved by repeating the protocol in parallel a sufficient number of times, denoted as $t$ . In doing so, a dishonest Prover must convince the Verifier across multiple instances of the protocol simultaneously.

Signing Process

Suppose a user with a private key $\mathbf{s}$ wants to sign a message $\mathtt{msg}$ . The MQDSS scheme proceeds as follows:

The user generates the Commitment $\mathtt{cmt} \gets (\mathtt{cmt}^{(1)}, \ldots, \mathtt{cmt}^{(t)})$ , where each $\mathtt{cmt}^{(i)} = (c_{0,i}, c_{1,i})$ is obtained by repeating the commitment generation process in the identification scheme.
The first Challenge is computed as $\mathtt{ch}_1 = (\mathtt{ch}_1^{(1)}, \ldots, \mathtt{ch}_1^{(t)}) \gets \mathsf{H}_1(\mathbf{s}, \mathtt{msg}, \mathtt{cmt})$ , where $\mathsf{H}_1$ is a cryptographic hash function.
For each Commitment-Challenge pair $(\mathtt{cmt}^{(i)}, \mathtt{ch}_1^{(i)})$ , the user generates the first response $\mathtt{rsp}_1^{(i)}$ as in the identification scheme.
The second Challenge is computed based on all previous messages as $\mathtt{ch}_2 = (\mathtt{ch}_2^{(1)}, \ldots, \mathtt{ch}_2^{(t)}) \gets \mathsf{H}_2(\mathbf{s}, \mathtt{msg}, \mathtt{cmt}, \mathtt{ch}_1, \mathtt{rsp}_1)$ , where $\mathsf{H}_2$ is a cryptographic hash function.
Finally, the signature is obtained by computing, for each execution, the second response $\mathtt{rsp}_2^{(i)}$ as in the identification protocol. The signature is then given by the Commitment and the responses: $\sigma = (\mathtt{cmt}, \mathtt{rsp}_1, \mathtt{rsp}_2)$ .

Note that it is not necessary to include the Challenges in the signature, as the Verifier can reconstruct and validate them during the verification process. Specifically, the Verifier can compute the Challenges using the hash functions as in the signing process. Based on these, it can verify the correctness of the responses for each execution of the protocol.

Security Considerations

When applying Fiat-Shamir to a 5-pass protocol, the first consideration concerns the generation of the Challenges, which must incorporate all available protocol information at that point. For this reason, the hash of the second Challenge includes not only the Commitment but also the first Challenge and its corresponding response. Without this precaution, an attacker could potentially perform multiple second rounds for a single first round, possibly finding a combination leading to a forged signature.

A second important security consideration relates to the connection between the signature scheme and the secret held by the Prover in the identification scheme. To prove the security of the scheme, it is necessary to demonstrate that any valid signatures produced by an adversary can be used to break the underlying security assumption (in this case, the MQ problem). The standard technique involves “rewinding”: the adversary’s process is executed multiple times with different Challenges but the same initial Commitment. However, with 5-pass protocols, more care must be taken in how rewinding is performed.

In a 3-pass scheme, two valid signatures with different Challenges related to the same Commitment are sufficient to extract a solution to the underlying hard problem. In the 5-pass structure of MQDSS, more signatures are needed because there are two independent Challenges. The security proof must therefore account for this more complex rewinding strategy.

MQDSS in the NIST Competition

MQDSS was submitted to NIST’s first PQC standardization process as a candidate for digital signatures. The scheme initially appeared promising due to its structure and strong theoretical foundations, which directly relate its security to the MQ problem.

However, MQDSS later revealed significant limitations that led to its elimination in 2020 at the end of the second round. The most critical drawback of the scheme is its performance characteristics: the signatures have considerable sizes, on the order of tens of kilobytes. Additionally, the signing and verification operations are computationally expensive, and the signature generation process is slower compared to competing schemes.

Despite its performance limitations, the design and security aspects of the scheme initially garnered interest in MQDSS, particularly for conservative application scenarios. The decisive blow to MQDSS, however, came from an original attack published by Kales and Zaverucha in 2020. This attack exploited a subtle vulnerability in the application of the Fiat-Shamir transform to 5-pass protocols. The proposed strategy is based on a key observation: the process of finding valid responses for the second Challenge can proceed without modifying the Commitment and the first Challenge. This allows the attack to be split into two phases and optimized concerning the number of rounds.

Although the attack did not target the underlying mathematical problem or the theoretical security proofs, restoring the lost security through new parameters would have required 40% more iterations and keys that were 50% larger. This combination of factors ultimately led to MQDSS not being selected for the third round of the competition.

To date, although no multivariate scheme based on identification protocols is currently under standardization, there have been numerous theoretical developments that have made this approach competitive again. In particular, techniques related to the MPC-in-the-head paradigm can be readily applied to the protocol of Sakumoto et al., yielding promising results in terms of signature size and performance.

^[1] A theoretical function that responds to each query with a completely random output. In practice, it is typically replaced by a cryptographic hash function.

This article belongs to a series of contributions, edited by the Telsy Cryptography Research Group, devoted to quantum computing and its implications on Cryptography. For reference to other articles, please refer to the index.

For other articles related to Quantum and Cryptography topics, please refer to the related categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Edoardo Signorini, Cryptography Specialist at Telsy, where he has been part of the Cryptography Research Group since 2020. He received his PhD in Pure and Applied Mathematics from the Polytechnic University of Turin in 2024 with a thesis on Post-Quantum Digital Signature Aggregation. His work focuses on research in the area of Post-Quantum Cryptography and the analysis and development of cryptographic protocols.