[Model] MultivariateQuadratic

[QingyunQian]

Motivation

Add the Multivariate Quadratic (MQ) problem over F_2, a core problem in post-quantum cryptography and algebraic cryptanalysis. This fills a gap in the project by introducing polynomial equation solving over the Boolean field, which is fundamental to multivariate public-key cryptosystems (MPKC) and algebraic attacks on symmetric ciphers. MQ over F_2 is polynomial-time interreducible with SAT, connecting it directly to the existing reduction graph.

Associated reduction rules:

• [Rule] Satisfiability to MultivariateQuadratic #131: [Rule] Satisfiability → MultivariateQuadratic
• [Rule] MultivariateQuadratic to Satisfiability #132: [Rule] MultivariateQuadratic → Satisfiability

Definition

Name: MultivariateQuadratic
Reference:

• Patarin, J. (1996). "Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms."
• Ding, J., & Yang, B. Y. (2009). "Multivariate Public Key Cryptography." In Bernstein, Buchmann & Dahmen (eds.), Post-Quantum Cryptography, Springer, DOI: 10.1007/978-3-540-88702-7_6
• Multivariate cryptography (Wikipedia)

Given m quadratic polynomials f_0, f_1, ..., f_{m-1} over F_2 = {0, 1} with n binary variables x_0, x_1, ..., x_{n-1}, determine whether there exists a solution x ∈ F_2^n such that all equations are satisfied:

f_0(x_0, ..., x_{n-1}) = 0
f_1(x_0, ..., x_{n-1}) = 0
...
f_{m-1}(x_0, ..., x_{n-1}) = 0

where each f_i is a quadratic polynomial of the form:

f_i(x) = Σ_{0 ≤ j ≤ k < n} a_{ijk} x_j x_k + Σ_{j=0}^{n-1} b_{ij} x_j + c_i,  where a_{ijk}, b_{ij}, c_i ∈ F_2

Note: over F_2, x_j^2 = x_j, so squared terms are absorbed into linear terms. The quadratic terms are only cross-terms x_j x_k with j < k.

Note: This is the decision version (does a solution exist?), distinct from the search version (find a solution).

Variables

• Count: n (number of binary variables)
• Per-variable domain: {0, 1} (elements of F_2)
• Meaning: x_i ∈ {0, 1} represents the i-th binary variable in the polynomial system. A valid assignment satisfies all m equations simultaneously (all f_i evaluate to 0 mod 2).

Schema (data type)

Type name: MultivariateQuadratic
Variants: none (F_2 only)

Field	Type	Description
num_variables	usize	Number of binary variables n
equations	Vec	List of m quadratic polynomials over F_2

Where QuadraticPoly contains:

• quadratic_terms: Vec<(usize, usize)> — pairs (j, k) with j < k where the coefficient a_{jk} = 1 (only store nonzero terms; all coefficients are 0 or 1 in F_2)
• linear_terms: Vec — indices j where the coefficient b_j = 1
• constant: bool — constant term c_i (true = 1, false = 0)

Getter methods: num_variables(), num_equations() (used in declare_variants! complexity strings and #[reduction(overhead)] expressions).

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• Restricted to F_2 (Boolean field). Extension to general F_q is future work.
• Over F_2, coefficients are in {0, 1}, so only nonzero terms need to be stored.

Complexity

• Best known exact algorithm: Dinur (SODA 2021) gives a randomized algorithm running in O(1.6181^n) time for solving degree-2 polynomial systems over F_2. This improves over Lokshtanov et al. (SODA 2017) who first beat brute force with O(2^{0.876n}), and Björklund et al. (ICALP 2019) who gave an intermediate improvement.
• declare_variants! complexity string: "1.6181^num_variables" (Dinur, SODA 2021)
• Complexity class: NP-complete over F_2 in the decision setting.
• References:
  • I. Dinur (2021). "Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting." SODA 2021, pp. 2550–2564.
  • D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, H. Yu (2017). "Beating Brute Force for Systems of Polynomial Equations over Finite Fields." SODA 2017, pp. 2190–2202.
  • Faugère, J. C. (1999). "A new efficient algorithm for computing Gröbner bases (F4)." Journal of Pure and Applied Algebra 139, pp. 61–88.
  • Patarin, J. (1996). "Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP)." EUROCRYPT 1996, LNCS 1070.

Extra Remark

Relationship to existing algebraic problems:

Problem	MQ over F_2	Key Difference
QUBO	Quadratic optimization over {0,1}	MQ: constraint satisfaction; QUBO: unconstrained optimization
ILP	Linear constraints over integers	MQ: quadratic constraints over F_2
SAT	Boolean satisfiability	MQ over F_2 and SAT are polynomial-time interreducible; MQ uses polynomial equations, SAT uses CNF clauses

Why MQ is distinct:

• Domain: Binary field F_2 (same domain as QUBO, but different problem type)
• Constraints: Quadratic equations = 0 (not unconstrained like QUBO, not linear like ILP, not clause-based like SAT)
• Problem type: SatisfactionProblem (returns bool, not optimization objective)
• Algorithms: Gröbner bases (F4/F5), XL algorithm, polynomial method — fundamentally different from SAT solvers (DPLL/CDCL)

Applications in cryptography:

• Post-quantum cryptography: HFE/UOV-style multivariate signature schemes and related MPKC constructions
• Algebraic attacks: Breaking stream ciphers, block ciphers via polynomial representation

How to solve

• It can be solved by (existing) bruteforce (enumerate all 2^n binary assignments)
• It can be solved by reducing to integer programming — binary variables with quadratic constraints linearized via auxiliary variables
• Other: Gröbner basis (F4/F5), XL algorithm, polynomial method (Dinur 2021)

Example Instance

Instance 1: F_2 — YES (satisfiable)

Field: F_2 = {0, 1}
Variables: n = 3 (x_0, x_1, x_2)
Equations:
  f_0: x_0·x_1 + x_2 = 0
  f_1: x_1·x_2 + x_0 = 0

Exhaustive check:
  (0,0,0): f_0 = 0+0 = 0 OK, f_1 = 0+0 = 0 OK  ← solution
  (0,0,1): f_0 = 0+1 = 1 X
  (0,1,0): f_0 = 0+0 = 0 OK, f_1 = 0+0 = 0 OK  ← solution
  (0,1,1): f_0 = 0+1 = 1 X
  (1,0,0): f_0 = 0+0 = 0 OK, f_1 = 0+1 = 1 X
  (1,0,1): f_0 = 0+1 = 1 X
  (1,1,0): f_0 = 1+0 = 1 X
  (1,1,1): f_0 = 1+1 = 0 OK, f_1 = 1+1 = 0 OK  ← solution

Answer: YES
Solutions: (0,0,0), (0,1,0), (1,1,1)

Instance 2: F_2 — NO (unsatisfiable, with quadratic terms)

Field: F_2 = {0, 1}
Variables: n = 3 (x_0, x_1, x_2)
Equations:
  f_0: x_0·x_1 + x_0·x_2 + x_0 = 0
  f_1: x_0·x_1 + x_1·x_2 + x_1 + 1 = 0
  f_2: x_0·x_2 + x_1·x_2 + x_2 + 1 = 0

Exhaustive check (all arithmetic mod 2):
  (0,0,0): f_0 = 0 OK, f_1 = 0+0+0+1 = 1 X
  (0,0,1): f_0 = 0 OK, f_1 = 0+0+0+1 = 1 X
  (0,1,0): f_0 = 0 OK, f_1 = 0+0+1+1 = 0 OK, f_2 = 0+0+0+1 = 1 X
  (0,1,1): f_0 = 0 OK, f_1 = 0+1+1+1 = 1 X
  (1,0,0): f_0 = 0+0+1 = 1 X
  (1,0,1): f_0 = 0+1+1 = 0 OK, f_1 = 0+0+0+1 = 1 X
  (1,1,0): f_0 = 1+0+1 = 0 OK, f_1 = 1+0+1+1 = 1 X
  (1,1,1): f_0 = 1+1+1 = 1 X

Answer: NO (all 8 assignments fail at least one equation)

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Reference year error; complexity bound is conservative
Well-written	⚠️ Warn	Minor indexing inconsistency; no reduction rules planned

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Novel problem — no MultivariateQuadratic exists in the codebase. The motivation (post-quantum cryptography, algebraic cryptanalysis) is concrete. MQ over F₂ is interreducible with SAT, connecting it to the existing reduction graph.

Warning: No concrete [Rule] issues are referenced. Without at least one reduction (e.g., MQ ↔ SAT over F₂), this would be an orphan node.

Non-trivial

Genuinely distinct from all 24 existing problems. Unlike QUBO (unconstrained binary quadratic optimization), MQ is constraint satisfaction over arbitrary finite fields F_q. Unlike SAT (boolean clauses), MQ uses polynomial equations. Different domain, different algorithms (Gröbner bases vs DPLL/CDCL).

Correctness

Reference verification:

Reference	Status	Notes
Patarin (1996), EUROCRYPT	✅ Verified	Real paper, LNCS vol. 1070
Ding & Yang (2020)	❌ Wrong year	The chapter "Multivariate Public Key Cryptography" by Ding & Yang was published in 2009, not 2020 (in Bernstein, Buchmann & Dahmen eds., Post-Quantum Cryptography, Springer). A 2020 second edition exists but has different authors (Ding, Petzoldt & Schmidt).
Faugère F4 (1999)	✅ Verified	J. Pure Appl. Algebra 139, pp. 61–88
Bardet, Faugère & Salvy (2004)	✅ Verified	INRIA RR-5049

Complexity: The stated O(q^n) by exhaustive search is correct but conservative. For F₂ specifically, Lokshtanov et al. (SODA 2017, "Beating Brute Force for Systems of Polynomial Equations over Finite Fields") achieve O(2^{0.8765n}).

Recommendation: Update Ding & Yang to 2009 (or cite the 2020 2nd edition with correct authors). Consider citing Lokshtanov et al. 2017 for a tighter F₂ bound.

Well-written

All sections present. Minor issues:

• Definition uses 1-based indexing (w_1, ..., w_n) but examples use 0-based (x0, x1, x2). Should harmonize to 0-based for consistency with Rust implementation.
• Should clarify whether initial implementation targets prime fields only (where u64 modular arithmetic suffices) or also extension fields like F₂₅₆.

Recommendations

• Fix Ding & Yang reference year from 2020 → 2009
• Consider citing Lokshtanov et al., SODA 2017 for O(2^{0.8765n}) over F₂
• Plan at least one reduction rule (MQ → SAT or SAT → MQ over F₂) to connect to the graph
• Use 0-based indexing in the formal definition

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; connects to post-quantum cryptography
Non-trivial	✅ Pass	Distinct feasibility constraints (quadratic equations over finite fields) from all existing problems
Correctness	⚠️ Warn	Ding & Yang reference year is wrong (2009, not 2020); complexity bound is only brute-force O(q^n) — better algorithms exist
Well-written	⚠️ Warn	Missing declare_variants! complexity string; minor notation issues

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. MultivariateQuadratic does not exist in the codebase (confirmed via pred show). The problem is genuinely useful:

• It fills a gap in algebraic/cryptographic problems — the project currently has QUBO, ILP, CVP, and BMF in the algebraic category but nothing for polynomial equation systems over finite fields.
• The issue correctly identifies concrete planned reductions: MQ over F₂ is polynomial-time interreducible with SAT, and MQ connects to QUBO through different domains/objectives.
• Post-quantum cryptography is a strong, concrete motivation.
• The problem is a SatisfactionProblem (Metric = bool), which is well-supported by the existing trait hierarchy.

Non-trivial

Pass. MultivariateQuadratic has genuinely distinct feasibility constraints from all 24 existing problems:

• vs QUBO: QUBO is unconstrained quadratic optimization over {0,1}; MQ is quadratic constraint satisfaction over F_q.
• vs ILP: ILP has linear constraints over integers; MQ has quadratic constraints over finite fields.
• vs Satisfiability/KSatisfiability: SAT operates over Boolean clauses in CNF form; MQ uses polynomial equations over arbitrary finite fields. While MQ over F₂ and SAT are interreducible, MQ generalizes to q > 2.
• vs CVP: CVP is a lattice problem with a completely different input structure (basis matrix + target vector).

The issue's comparison table correctly summarizes these distinctions.

Correctness

Warn (not fatal). Two issues found:

1. Ding & Yang reference year is wrong. The issue cites "Ding, J., & Yang, B. Y. (2020)" but the actual publication is from 2009: "Multivariate Public Key Cryptography" in Post-Quantum Cryptography (eds. Bernstein, Buchmann, Dahmen), Springer, 2009, DOI: 10.1007/978-3-540-88702-7_6. There is a 2020 second edition of a related book (Multivariate Public Key Cryptosystems, Advances in Information Security series), but the cited chapter title and book title match the 2009 edition.

2. Complexity bound is conservative. The issue states "O(q^n) by exhaustive search" as the best known algorithm and correctly notes Gröbner basis methods lack uniform worst-case bounds. However, for the important special case of F₂, Lokshtanov et al. (SODA 2017, "Beating Brute Force for Systems of Polynomial Equations over Finite Fields") give a randomized O(2^{0.8765n}) algorithm. For general F_q, probabilistic algorithms achieve O(q^{δn}) for δ < 1. The issue should cite a tighter bound for the declare_variants! complexity string.

3. All other references verified:

   • Patarin (1996), "Hidden Fields Equations (HFE)..." — confirmed at Springer LNCS 1070, Eurocrypt '96. ✅
   • Faugère (1999), "A new efficient algorithm for computing Gröbner bases (F4)" — confirmed in J. Pure Applied Algebra, vol. 139, pp. 61-88. ✅
   • Bardet, Faugère & Salvy (2004), "On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations" — confirmed at ICPSS 2004. ✅
   • MQ is NP-complete over F₂ — well-established in the literature. ✅

Well-written

Warn (not fatal). The issue is generally well-structured and complete, but has some minor issues:

Positive aspects:

• All template sections present and substantive (Motivation, Definition, Variables, Schema, Complexity, How to solve, Example Instance)
• Two concrete examples provided (YES and NO instances), both small enough to verify by hand
• Clear formal definition with polynomial form specified
• Schema table with field descriptions

Issues to address:

1. No declare_variants! complexity string. The Complexity section discusses algorithms qualitatively but does not provide a concrete complexity expression suitable for code (e.g., "q^num_variables" using getter method names). This is needed for implementation.

2. Coefficient type inconsistency. The Schema uses u64 for coefficients but the definition says coefficients are in F_q. For q > 2^64 (extension fields like F_{2^256}), u64 would not suffice. The issue mentions F₂₅₆ as a variant but the schema cannot represent it. This should be clarified — perhaps restrict to prime fields where q < 2^64, or document the limitation.

3. Missing getter method names. The Schema does not specify what getter methods the type will expose (e.g., num_variables(), num_equations(), field_size()). These are needed for overhead expressions in future reductions.

4. Example 2 is linear, not quadratic. The "NO" example uses only linear terms (f₁: x₀ + x₁ = 0, f₂: x₀ + x₁ + 1 = 0). While technically a valid MQ instance (with zero quadratic coefficients), it does not exercise the quadratic structure of the problem. A better NO example would include actual quadratic terms.

Recommendations

• Fix Ding & Yang reference year from 2020 to 2009 (or cite the 2020 second edition with correct title)
• Add a concrete complexity string: "q^num_variables" for brute-force, or cite Lokshtanov et al. for F₂ variant with "2^(0.8765 * num_variables)"
• Clarify coefficient representation for large fields or restrict to prime fields with q < 2^64
• Replace Example 2 with one that has actual quadratic terms