Concrete security of the SOV sparse-polynomial multivariate signature scheme against post-2020 algebraic attacks

SOV (Shim–Park–Koo, IEEE Access 2020) is a two-layer oil-and-vinegar multivariate-quadratic signature scheme over a small prime field whose central map uses non-overlapping sparse quadratic polynomials with designated matrix ranks, reducing the secret key by about 90% relative to Rainbow while claiming 128-bit security for the recommended parameter set SOV($\mathbb{F}_{31}$, 29, 28, 26). Its security argument rests on heuristic HybridF5 complexity estimates (under the unproven semi-regularity assumption), MAGMA/F4 experiments over $\mathbb{F}_{31}$, and a circa-2020 catalogue of known attacks. No published cryptanalysis of SOV itself is known, but the two pillars of its argument have since been undermined in neighboring work: Rainbow — whose good-key key-recovery analysis SOV's Theorem 1 reuses verbatim — was broken by Beullens' 2022 min-rank attack, and the sparse UOV scheme MQ-Sign, by the same research group and built on the same sparsity-for-key-reduction idea, was broken in polynomial time in 2023–2024. The open problem is whether SOV's claimed 128-bit security survives the post-2020 cryptanalytic toolbox, and whether the heuristic solver-cost model can be replaced by a sound hardness argument for the SOV central-map family.

Background

Multivariate-quadratic (MQ) cryptography constructs post-quantum public-key schemes whose public key is a system of quadratic polynomials over a small finite field; inverting such a system (the MQ problem) is NP-hard in the worst case, and the best generic algorithms known are Gröbner-basis methods such as F4 and F5 — algorithms that repeatedly linearize the system at increasing degree — whose running time is predicted by the degree of regularity of the system (the degree at which these linearizations first become over-determined), a prediction that is provable only for so-called semi-regular systems and is therefore heuristic for random-looking ones. The HybridF5 (HF5) algorithm guesses $k$ variables and runs F5 on the remaining overdetermined system; the paper's complexity estimates take the resulting formula as a cost model. Most MQ signature schemes use an affine-substitute-affine (ASA) trapdoor: a secret structured central map $F$, invertible by solving only linear systems, is hidden between two secret affine maps $S$ and $T$, and the public key is $P = S \circ F \circ T$. The classic Oil-and-Vinegar (OV) construction splits the $n$ variables into vinegar and oil parts, with quadratic terms missing from the oil-oil block so that fixing vinegar values linearizes the system; Unbalanced OV (UOV) uses more vinegar than oil. Rainbow is the layered variant (two oil layers with a shared vinegar set) that was a NIST post-quantum finalist; a persistent drawback of these schemes is large key material. SOV (Sparse Polynomials-based Oil and Vinegar), proposed by Shim, Park, and Koo in IEEE Access 2020, reduces the secret key by about 90% versus Rainbow by making the central polynomials sparse: each quadratic polynomial uses only non-overlapping cyclically-shifted pairs of variables, arranged so that the symmetric matrix of each first-layer polynomial has rank $2o_1$ while every second-layer quadratic form is full rank by design — the latter explicitly to defeat rank-based attacks. With parameters ($\mathbb{F}_{31}$, $v=29$, $o_1=28$, $o_2=26$), i.e. $n = 83$ variables and $m = 54$ equations, the authors claim 128-bit security, evidenced by F4 experiments in MAGMA (a computer algebra system with state-of-the-art Gröbner-basis routines) showing that public-key-derived systems over $\mathbb{F}_{31}$ solve about as slowly as random ones, and by complexity estimates against the known catalogue: direct attacks (HF5 cost for $m$ equations in $n$ variables); key-recovery attacks (KRAs) via equivalent keys (alternative triples producing the same public key) and good keys (a generalization that minimizes the system to be solved; the paper's Theorem 1 shows SOV's good keys have exactly the same form as Rainbow's, so the KRA cost equals the HF5 cost of an $(m+n-1)$-equation system in $n$ variables); the MinRank attack (finding a low-rank linear combination of the public quadratic matrices; for SOV, of cost about $o_1 \cdot q^{o_1+1}$); the HighRank attack (which guesses the variables appearing in the lowest-rank quadratic forms and checks consistency); and the Kipnis–Shamir attack (which re-expresses the secret oil subspace as the solution space of a bilinear system). The probability bounds in the MinRank and good-key analyses assume the central-map coefficients are sampled generically at random subject to the rank and non-overlap properties. All of these estimates are heuristic. After the paper appeared, the surrounding field changed drastically: Beullens (CRYPTO 2022) broke Rainbow with a new min-rank key-recovery attack far cheaper than the Rainbow-Band-Separation (RBS)/good-key systems' estimated cost, practically so at NIST security level 1; the support-minors method (an algebraic technique that models rank constraints via the minors of a matrix with unknown row space, sharpening min-rank solving) was likewise turned into improved rank attacks on layered schemes (Baena et al., CRYPTO 2022); and Aulbach–Samardjiska–Trimoska (PQCrypto 2024) broke the sparse UOV scheme MQ-Sign — proposed by the same first author's group in the Korean KpqC competition (Korea's national post-quantum cryptography standardization effort) using the same sparsity-for-key-reduction idea — in polynomial time, by deriving enough linear equations from the sparse secret polynomials, with Ikematsu–Jo–Yasuda extending the attack to general secret linear maps. None of these attacks has been applied to SOV, whose second layer is deliberately full rank (unlike Rainbow's) and whose sparsity pattern (non-overlapping terms across polynomials) differs from MQ-Sign's (sparse vinegar-oil blocks). The field itself has since consolidated on plain UOV with modern parameters, and SOV — essentially uncited — has received no published follow-up analysis.

Problem Statement

Determine the actual security of the SOV signature scheme — concretely, of the recommended parameter set SOV($\mathbb{F}_{31}$, 29, 28, 26) with $n = 83$ variables and $m = 54$ equations — against the post-2020 cryptanalytic toolbox, replacing the heuristic 2020-era cost estimates on which its claimed 128-bit security rests. The question has two linked components. (i) Attack surface: exhibit, or rule out, a key-recovery or universal-forgery attack on the stated parameter set with cost below $2^{128}$ operations. (ii) Cost-model foundations: relate the HybridF5/semi-regularity cost model, and the generic-randomness probability bounds used in the MinRank and good-key analyses, to actual hardness for the SOV central-map family. Component (i) is resolved by a reproducible attack below the claimed security level on the stated parameters (refuting the security claim), or by a proof — under clearly stated assumptions — that the relevant attack systems for the stated parameters cannot be solved below that level (confirming it). Component (ii) is resolved by stating, under clearly stated assumptions, the extent to which the HybridF5/semi-regularity cost model and the generic-randomness probability bounds used in the MinRank and good-key analyses apply to the SOV central-map family. A full resolution addresses both components (i) and (ii).

References

1. Kyung-Ah Shim, Cheol-Min Park, Namhun Koo: An Efficient MQ-Signature Scheme Based on Sparse Polynomials. IEEE Access 8:26257–26265, 2020. DOI 10.1109/ACCESS.2020.2970608, https://doi.org/10.1109/ACCESS.2020.2970608
2. Ward Beullens: Breaking Rainbow Takes a Weekend on a Laptop. Advances in Cryptology – CRYPTO 2022, LNCS 13508, pp. 464–479, Springer, 2022. DOI 10.1007/978-3-031-15979-4_16, https://eprint.iacr.org/2022/214
3. John Baena, Pierre Briaud, Daniel Cabarcas, Ray Perlner, Daniel Smith-Tone, Javier Verbel: Improving Support-Minors Rank Attacks: Applications to GeMSS and Rainbow. Advances in Cryptology – CRYPTO 2022, LNCS 13509, pp. 376–405, Springer, 2022. DOI 10.1007/978-3-031-15982-4_13, https://eprint.iacr.org/2021/1677
4. Thomas Aulbach, Simona Samardjiska, Monika Trimoska: Practical Key-Recovery Attack on MQ-Sign and More. Post-Quantum Cryptography – PQCrypto 2024, LNCS 14772, pp. 168–185, Springer, 2024. DOI 10.1007/978-3-031-62746-0_8, https://eprint.iacr.org/2023/432
5. Yasuhiko Ikematsu, Hyungrok Jo, Takanori Yasuda: A Security Analysis on MQ-Sign. Information Security Applications (WISA 2023), Springer, 2024, pp. 40–51. DOI 10.1007/978-981-99-8024-6_4, https://doi.org/10.1007/978-981-99-8024-6_4
6. Ward Beullens, Ming-Shing Chen, Shih-Hao Hung, Matthias J. Kannwischer, Bo-Yuan Peng, Cheng-Jhih Shih, Bo-Yin Yang: Oil and Vinegar: Modern Parameters and Implementations. IACR Transactions on Cryptographic Hardware and Embedded Systems 2023(3):321–365, 2023. DOI 10.46586/tches.v2023.i3.321-365, https://eprint.iacr.org/2023/059