Active security of parallel-repeated MQ identification schemes without the compression hypothesis

The 3-pass and 5-pass identification schemes of Sakumoto, Shirai, and Hiwatari (CRYPTO 2011) are zero-knowledge arguments of knowledge of a secret $s$ with $v=F(s)$ for a public random multivariate-quadratic (MQ) function $F$, assuming only a statistically hiding and computationally binding commitment scheme. Their $N$-fold parallel composition is proven secure against impersonation under passive attack for all parameters, but the active-attack theorem additionally requires $F$ to be substantially compressing ($n=m+k$ with $k=\omega(\log\lambda)$ variables over equations) and preimage resistant. Every practically used instantiation lies outside this regime, including the paper's own choices $\mathrm{MQ}(84,80,\mathbb{F}_2)$ and $\mathrm{MQ}(45,30,\mathbb{F}_{2^4})$ and the square parameters $\mathrm{MQ}(64,64,\mathbb{F}_{31})$ underlying the MQDSS signature. Recent literature (2025-2026) resolved one ingredient of the gap: one-wayness of the uniform MQ family now provably implies second-preimage resistance at the same dimensions, so the dimension shift in the source's Lemma 7 is no longer needed. The surviving open core is whether the remaining compression hypothesis can be removed: is the parallel-repeated scheme secure against active (cheating-verifier) impersonation at non-compressing parameters under the one-wayness of MQ alone, or does an active attack exist?

Background

An MQ function is a vector $F=(f_1,\dots,f_m)$ of $m$ polynomials in $n$ variables over a finite field $\mathbb{F}_q$, each of total degree two; $\mathrm{MQ}(n,m,\mathbb{F}_q)$ denotes the family of all such maps $F:\mathbb{F}_q^n\to\mathbb{F}_q^m$. Finding $s$ with $F(s)=v$ for a random instance is the MQ problem. Its decision version is NP-complete in the worst case, while its average-case hardness at balanced parameters ($m\approx n$) -- where the best known algorithms (Gröbner-basis methods, i.e. polynomial-system solvers built from linear algebra on shifted copies of the system, exhaustive search, and hybrids of both) are all exponential -- is the central conjecture of multivariate public-key cryptography (MPKC), a post-quantum alternative to factoring- and discrete-log-based schemes since no efficient quantum algorithm for it is known. The assumption that inverting $F$ on a random image is hard is called one-wayness or preimage resistance; second-preimage resistance (SPR) asks that, given a random pair $(F,x)$, it be hard to find $x'\neq x$ with $F(x')=F(x)$. For general function families SPR implies one-wayness only when the function sufficiently compresses its input (Rogaway-Shrimpton), and random MQ functions are known not to be collision resistant (Billet-Robshaw-Peyrin), so the relations among these notions for MQ functions are delicate.

An identification scheme lets the holder of a secret key convince a verifier that she owns it without revealing it. The schemes of Sakumoto, Shirai, and Hiwatari (the source of this question) are arguments of knowledge for the relation $v=F(s)$: they use a cut-and-choose over additive shares of $s$, made possible by the polar form $G(x,y)=F(x+y)-F(x)-F(y)$, which is bilinear and hence splits a quadratic evaluation into share-wise pieces; a non-interactive string commitment Com, statistically hiding (committed values are information-theoretically concealed) and computationally binding (a polynomial-time sender cannot open one commitment two ways), seals the shares before the verifier's challenge. The 3-pass protocol has knowledge error $2/3$ and the 5-pass protocol $1/2+1/(2q)$ -- the probability that a cheating prover passes one round -- and both are honest-verifier statistically zero-knowledge. Security against impersonation comes in increasing strengths: passive (the adversary only eavesdrops on honest transcripts), active (the adversary first plays cheating verifier against the honest prover, then must impersonate to the honest verifier), and concurrent (cheating-verifier sessions may interleave arbitrarily).

To make the knowledge error negligible, the base protocol is repeated $N=\omega(\log\lambda)$ times in parallel within one transcript. The source paper proves the parallel scheme secure against passive impersonation for every $(n,m)$, via standard parallel-repetition results for constant-round public-coin arguments of knowledge (Pass-Venkitasubramaniam). For active security, its Lemma 8 and Theorem 9 additionally require that $F$ be substantially compressing, $n=m+k$ with $k=\omega(\log \lambda)$, and that $\mathrm{MQ}(n-1,m,\mathbb{F}_q)$ be preimage resistant. The proof chain is: (1) Lemma 7 shows that preimage resistance of $\mathrm{MQ}(n,m,\mathbb{F}_q)$ implies SPR of $\mathrm{MQ}(n+1,m,\mathbb{F}_q)$, via an embedding that turns a second preimage whose difference from the given point has last coordinate $1$ into a preimage of the embedded challenge; (2) the parallel protocol is statistically witness indistinguishable (WI -- a cheating verifier cannot tell which of several preimages the prover holds; Feige-Shamir), because Com is statistically hiding; and (3) for a compressing $F$, a random image has no second preimage with probability at most $q^{-k}$, so a reduction that is handed $(F,x)$, simulates the honest prover perfectly using witness $x$ through the cheating-verifier phase, and then extracts the impersonator's witness obtains, with overwhelming probability, a preimage different from $x$ -- breaking SPR. Theorem 9 is proved for the 3-pass scheme, the paper extends the argument to the 5-pass scheme, and it notes that the proof extends to concurrent attacks.

The regime hypothesis is not cosmetic. The paper's own recommended parameters are $\mathrm{MQ}(84,80,\mathbb{F}_2)$ for the 3-pass scheme and $\mathrm{MQ}(45,30,\mathbb{F}_{2^4})$ for the 5-pass scheme, with $n-m=4$ and $15$; the MQDSS signature later built from the 5-pass scheme uses square parameters $n=m=64$ over $\mathbb{F}_{31}$. At such parameters a random public key has a unique preimage with constant probability, so step (3) fails statistically, and the natural reduction faces a structural barrier: to run the cheating-verifier phase it must simulate the honest prover, which requires knowing some preimage of the challenge value -- exactly what a bare one-wayness challenge withholds. For the homomorphism-based Schnorr and GQ identification schemes this kind of barrier was eventually overcome and active security was proven from the standard assumptions (Bellare-Palacio); those proofs exploit the algebraic homomorphism ($x\mapsto g^x$ or RSA exponentiation), which lets one shift a commitment after seeing the challenge, an operation with no known analogue for MQ functions. Recent work removed one ingredient of the present gap: Zhuang-Zhang-Ding prove that one-wayness of the uniform MQ family implies SPR at the same $(n,m,q)$ with tight loss (so the dimension shift of Lemma 7 is unnecessary), and that SPR conversely implies one-wayness whenever $m\le n+O(\log\lambda)$. The compression hypothesis itself, however, has neither been discharged nor shown to be necessary for the interactive schemes -- this is the open question.

Problem Statement

Fix a security parameter $\lambda$. Let Com be a non-interactive string commitment scheme that is statistically hiding and computationally binding, let $N=\omega(\log\lambda)$, and let $(P^{(p)},V^{(p)})$ be the $N$-fold parallel repetition of the Sakumoto-Shirai-Hiwatari 3-pass identification protocol (respectively, the 5-pass protocol) for the relation $v=F(s)$ with $F\in_R\mathrm{MQ}(n,m,\mathbb{F}_q)$, exactly as specified in the source paper (DOI 10.1007/978-3-642-22792-9_40); for the 3-pass protocol this includes the commitment-compression variant in which the first-pass message is $H(c_0,c_1,c_2)$.

The source proves passive impersonation security of $(P^{(p)},V^{(p)})$ for all $(n,m)$, and active impersonation security when $n=m+k$ with $k=\omega(\log\lambda)$, assuming preimage resistance of $\mathrm{MQ}(n-1,m,\mathbb{F}_q)$ (Theorem 9). The problem is to settle the security status of the same parallel scheme at parameters that are not substantially compressing -- at minimum the square case $n=m$ and the near-square case $n-m=O(1)$, which includes the source's own practical choices $\mathrm{MQ}(84,80,\mathbb{F}_2)$ and $\mathrm{MQ}(45,30,\mathbb{F}_{2^4})$ and the square $\mathrm{MQ}(64,64,\mathbb{F}_{31})$ used in later instantiations:

(a) Prove that $(P^{(p)},V^{(p)})$ is secure against impersonation under active attack -- and, if the technique permits, under concurrent attack -- assuming only one-wayness (preimage resistance) of the MQ family at polynomially related parameters, with every step valid at $n-m=O(1)$: no invocation of $n-m=\omega(\log\lambda)$, of the statistical existence of a second preimage of the public key, or of any assumption stronger than one-wayness; or

(b) Refute: exhibit a probabilistic polynomial-time adversary pair (cheating verifier, impersonator) that wins the active-impersonation game against $(P^{(p)},V^{(p)})$ with non-negligible probability at such parameters, without breaking the one-wayness of the MQ family (the attack must exploit the protocol structure rather than an inversion algorithm for MQ).

The objective is to close the gap between the unconditional passive security and the conditional active security of the parallel-repeated SSH MQ identification schemes at the balanced parameters under which they are actually used. The objective covers both the 3-pass and the 5-pass protocol variants and the whole non-compressing parameter regime, including the square case $n=m$ and the near-square case $n-m=O(1)$.

References

1. Koichi Sakumoto, Taizo Shirai, Harunaga Hiwatari: Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials. In: Advances in Cryptology - CRYPTO 2011, Lecture Notes in Computer Science, vol. 6841, pp. 706-723. Springer (2011). DOI: 10.1007/978-3-642-22792-9_40. https://doi.org/10.1007/978-3-642-22792-9_40 (open-access full text: https://link.springer.com/content/pdf/10.1007%2F978-3-642-22792-9_40.pdf)
2. Zijun Zhuang, Yingjie Zhang, Jintai Ding: Trapdoor-Free Multivariate One-Time Signatures in the Standard Model. Cryptology ePrint Archive, Paper 2025/952 (2025). https://eprint.iacr.org/2025/952
3. Zijun Zhuang, Yingjie Zhang, Jintai Ding: Relations Between the Uniform MQ Assumption and Other Multivariate Assumptions. Cryptology ePrint Archive, Paper 2026/1694 (2026). https://eprint.iacr.org/2026/1694
4. Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, Peter Schwabe: From 5-Pass MQ-Based Identification to MQ-Based Signatures. In: Advances in Cryptology - ASIACRYPT 2016. Springer (2016). DOI: 10.1007/978-3-662-53890-6_5. https://doi.org/10.1007/978-3-662-53890-6_5 (also Cryptology ePrint Archive, Paper 2016/708: https://eprint.iacr.org/2016/708)
5. Daniel Kales, Greg Zaverucha: An Attack on Some Signature Schemes Constructed from Five-Pass Identification Schemes. In: Cryptology and Network Security (CANS 2020). Springer (2020). DOI: 10.1007/978-3-030-65411-5_1. https://doi.org/10.1007/978-3-030-65411-5_1 (also Cryptology ePrint Archive, Paper 2020/837: https://eprint.iacr.org/2020/837)
6. Ward Beullens: Sigma Protocols for MQ, PKP and SIS, and Fishy Signature Schemes. In: Advances in Cryptology - EUROCRYPT 2020. Springer (2020). DOI: 10.1007/978-3-030-45727-3_7. https://doi.org/10.1007/978-3-030-45727-3_7
7. Hiroki Furue, Dung Hoang Duong, Tsuyoshi Takagi: An Efficient MQ-Based Signature in the QROM. In: CANDAR 2019. IEEE (2019). DOI: 10.1109/CANDAR.2019.00010. https://doi.org/10.1109/CANDAR.2019.00010
8. Emanuele Bellini, Rusydi H. Makarim, Carlo Sanna, Javier Verbel: An Estimator for the Hardness of the MQ Problem. In: Progress in Cryptology - AFRICACRYPT 2022, Lecture Notes in Computer Science, vol. 13503, pp. 323-347. Springer (2022). DOI: 10.1007/978-3-031-17433-9_14. https://doi.org/10.1007/978-3-031-17433-9_14
9. Özgür Dagdelen, David Galindo, Pascal Véron, Sidi Mohamed El Yousfi Alaoui, Pierre-Louis Cayrel: Extended security arguments for signature schemes. Designs, Codes and Cryptography (2014). DOI: 10.1007/s10623-014-0009-7. https://doi.org/10.1007/s10623-014-0009-7
10. Phillip Rogaway, Thomas Shrimpton: Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. In: Fast Software Encryption (FSE 2004), Lecture Notes in Computer Science, vol. 3017, pp. 371-388. Springer (2004). DOI: 10.1007/978-3-540-25937-4_24. https://doi.org/10.1007/978-3-540-25937-4_24
11. Olivier Billet, Matt J. B. Robshaw, Thomas Peyrin: On Building Hash Functions from Multivariate Quadratic Equations. In: Information Security and Privacy (ACISP 2007), Lecture Notes in Computer Science, vol. 4586, pp. 82-95. Springer (2007). DOI: 10.1007/978-3-540-73458-1_7. https://doi.org/10.1007/978-3-540-73458-1_7
12. Rafael Pass, Muthuramakrishnan Venkitasubramaniam: An Efficient Parallel Repetition Theorem for Arthur-Merlin Games. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC 2007), pp. 420-429. ACM (2007). DOI: 10.1145/1250790.1250853. https://doi.org/10.1145/1250790.1250853
13. Uriel Feige, Adi Shamir: Witness Indistinguishable and Witness Hiding Protocols. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990), pp. 416-426. ACM (1990). DOI: 10.1145/100216.100272. https://doi.org/10.1145/100216.100272
14. Mihir Bellare, Adriana Palacio: GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks. In: Advances in Cryptology - CRYPTO 2002, Lecture Notes in Computer Science, vol. 2442, pp. 162-177. Springer (2002). DOI: 10.1007/3-540-45708-9_11. https://doi.org/10.1007/3-540-45708-9_11
15. Fábio S. Monteiro, Denise H. Goya, Routo Terada: Improved Identification Protocol Based on the MQ Problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E98-A (2015). DOI: 10.1587/transfun.e98.a.1255. https://doi.org/10.1587/transfun.e98.a.1255