Multivariate Cryptography: Polynomial-Based Security

Multivariate cryptography bases security on solving systems of polynomial equations. While the SynX quantum-resistant wallet uses hash and lattice-based schemes, multivariate approaches represent another post-quantum family.

The MQ Problem

Multivariate Quadratic (MQ) problem:

• Given many quadratic equations over finite fields
• Find solution values satisfying all equations
• NP-complete in general case
• No known quantum algorithm provides significant speedup

How Multivariate Signatures Work

Basic construction:

• Private key: two invertible transformations + central map
• Public key: composition appears random
• Signing: invert using private structure
• Verification: evaluate public polynomials

NIST Candidates

Rainbow's Failure

Like SIKE, Rainbow was broken in 2022:

• Structure enabled classical attack
• Weekend computation on standard PC
• Reinforced need for conservative choices

Advantages of Multivariate

• Very small signature sizes (when secure)
• Fast verification
• Different mathematical basis than lattices
• Long research history

Challenges

• Several candidates broken recently
• Large key sizes for secure parameters
• Complex to implement correctly
• Smaller research community than lattices

Why SynX Uses SPHINCS+ Instead

The SynX quantum-resistant wallet chose hash-based signatures:

• Minimal assumptions (just hash function security)
• No algebraic structure to exploit
• Selected by NIST in 2022 and standardised as SLH-DSA (FIPS 205)
• Conservative despite larger size

Diversity in PQC Landscape

Multiple families provide ecosystem resilience:

• Lattice (Kyber, Dilithium)
• Hash-based (SPHINCS+)
• Code-based (Classic McEliece)
• Multivariate (ongoing research)

Frequently Asked Questions

Could multivariate become mainstream?

Possible with new constructions. Current SynX choices are NIST-standardised and have no known practical attack today.

Why do signatures keep getting broken?

PQC is newer than classical cryptography. NIST process helps identify weaknesses before deployment.