For eleven days, twelve hours and twelve minutes, four AMD server processors worked through a maze whose walls were equations. There was no stolen password at the center and no bank account waiting to be opened. The prize was a list of 36 numbers, each drawn from a clocklike world containing only the integers 0 through 30, that simultaneously satisfied 24 quadratic equations.

The calculation ended on October 16, 2025. Its meaning arrived more slowly. After peer review, Project Researcher Kosuke Sakata and Professor Tsuyoshi Takagi of the University of Tokyo’s Graduate School of Information Science and Technology published their method online on July 17, 2026, in IACR Transactions on Cryptographic Hardware and Embedded Systems. The university announced it five days later; the work is also scheduled for presentation at CHES 2026.

The solved instance belonged to the Fukuoka MQ Challenge, a public proving ground created in 2015 to measure the hardness of multivariate quadratic—or MQ—systems. It contained 36 variables and 24 equations over the finite field GF(31). The researchers estimate that this challenge was about 47,000 times more difficult than the prior record instance, which had 33 variables and 22 equations in the same category.

That phrase demands precision. The new algorithm was not measured to run 47,000 times faster. The 47,000 figure compares estimated problem complexity. Nor did the team defeat RSA, the web’s transport security, a NIST post-quantum standard or any deployed user’s private key. They solved one deliberately generated, signature-shaped benchmark. Its importance lies in the attack technique: every reduction in the real cost of solving MQ systems can change how cryptographers set safe parameters.

Cryptanalysis does not merely break locks. At its best, it measures the strength of locks before society entrusts anything valuable to them.
36 variablesThe unknowns in the record Type VI challenge instance.
24 equationsQuadratic constraints that all had to hold at once.
GF(31)A finite field whose arithmetic wraps around modulo 31.
994,320 secondsRecorded runtime: 11 days, 12 hours and 12 minutes.
2,011 instancesSmaller systems attempted after guessing 15 variables.
≈ 47,000×The researchers’ estimate of increased problem difficulty—not a measured speedup.

What kind of puzzle is MQ?

A linear system such as 2x + 3y = 7 can be organized into a matrix and attacked systematically with Gaussian elimination. Add products such as xy, squares such as x² and dozens of interacting variables, and the landscape changes. A generic MQ problem asks for a vector (x1, …, xn) that makes every quadratic polynomial in a collection equal zero.

A miniature MQ system over GF(31)
  • x² + 3xy + 7y + 5 = 0
  • 4xy + y² + 2x + 9 = 0
  • All addition and multiplication wrap around modulo 31: 30 + 2 becomes 1.

Finite-field arithmetic prevents numerical approximation from rescuing the solver. A candidate either satisfies each equation exactly or it does not. The quadratic terms also multiply the number of possible interactions. When algebraic elimination combines equations, intermediate terms of higher degree appear. The original problem may fit comfortably in memory while the machinery needed to solve it expands until memory—not the final answer—becomes the enemy.

MQ systems are useful in public-key cryptography because they can support a trapdoor. A signer privately retains a specially structured system that is easy to invert, then conceals it behind transformations. The public key looks like a difficult collection of quadratic equations. Verification is fast: substitute the signature and check the equations. Forgery should require solving the hard-looking public system without knowing its hidden structure.

The Fukuoka challenge removes any claim of secrecy and asks a cleaner scientific question: how large a generic system can today’s methods and hardware actually solve? Type VI models an underdetermined signature setting, with roughly one and a half variables for every equation, over GF(31). Coefficients are generated reproducibly from digits of π, and organizers supply instances and maintain a hall of fame. It is a measuring course, not a deployed cryptosystem.

Why nonlinear algebra becomes a matrix problem

The central tool is a Gröbner basis: an equivalent description of the same polynomial system arranged so its consequences are easier to read and solutions easier to extract. It is often described as a nonlinear cousin of row-echelon form. The analogy is useful, but the cost is radically different. Linear elimination never raises the degree. Polynomial elimination creates new combinations, and the population of possible monomials can explode.

The modern lineage reaches back to David Hilbert’s work on polynomial ideals in 1890. In 1965, Austrian mathematician Bruno Buchberger developed the theory and the first general algorithm for computing the bases, naming them for his adviser Wolfgang Gröbner. Buchberger’s method repeatedly forms special combinations called S-polynomials and reduces them, exposing new algebraic consequences until the basis is complete.

In 1999, French computer algebra researcher Jean-Charles Faugère introduced F4. Instead of reducing one polynomial at a time, F4 collects many related reductions into a Macaulay matrix and applies sparse linear algebra. It can be dramatically faster in practice even though it does not improve the worst-case complexity. For cryptanalysts, F4 turned the abstract problem of polynomial elimination into a concrete contest over which rows to create, how to store them and when to discard useless work.

The contest is unforgiving. A matrix row represents a polynomial; columns represent monomials such as x1x7 or x3²x9. At successive degrees, columns multiply. Many candidate combinations reduce to zero or add nothing new, but a conventional implementation may spend time and memory discovering that only after building the matrix.

Let Hilbert count before the computer builds

Sakata and Takagi’s central idea is to use a Hilbert series as a forecast. The series compresses information about the graded algebraic structure of the system: loosely, it counts how many independent monomial directions should remain at each degree. That advance knowledge lets the algorithm identify combinations likely to be necessary in the early part of the calculation instead of materializing a much larger pool and learning afterward which rows were redundant.

The researchers call the early strategy Hilbert-driven F4, or HDF4. In later phases—when the algebra no longer behaves as cleanly—the implementation switches priorities, choosing critical-pair combinations less likely to enlarge the Macaulay matrices. Their record submission lists HDF4 together with Mutant F4, or MF4. The innovation is therefore not one miraculous shortcut. It is a disciplined schedule for feeding F4 useful algebra while starving its worst source of matrix growth.

There was another practical layer. The team guessed values for 15 of the 36 variables and then attacked the smaller systems that remained. It ran 2,011 such instances, using 16 threads per instance across four AMD EPYC 7763 processors. The average instance took about 7,830 seconds of wall-clock time. This hybrid strategy trades a large outer search for much cheaper inner algebra; success depends on reaching a guess compatible with a solution.

The details explain an initially strange result. On the same October 2025 date, the team also recorded a solve of the smaller 34-variable, 23-equation Type VI instance. That run consumed about 21½ days—longer than the 36-by-24 record. Runtime is not a simple staircase. It depends on guessing, parallel scheduling, the algebraic character of individual subproblems and when a successful branch appears. “Harder” is a modeled complexity comparison, not a guarantee that every observed clock time will be larger.

Type VI recordSystemMethod and hardwareReported time
November 14, 202333 variables / 22 equations / GF(31)Hilbert-driven F4; AMD EPYC 7763; 12 guessed variables183,307 seconds, about 2 days 2 hours 55 minutes
October 16, 202534 variables / 23 equations / GF(31)HDF4 + MF4; four EPYC 7763 processors; 13 guessed variables1,857,440 seconds, about 21 days 12 hours
October 16, 202536 variables / 24 equations / GF(31)HDF4 + MF4; four EPYC 7763 processors; 15 guessed variables994,320 seconds, about 11 days 12 hours

A challenge born in Fukuoka

Tsuyoshi Takagi’s connection to the benchmark predates the new record. With Takanori Yasuda, Xavier Dahan, Yun-Ju Huang and Kouichi Sakurai, he introduced the MQ Challenge at a NIST workshop in Washington in April 2015. The organizers wanted a common, reproducible way to compare solvers. Papers could claim attractive asymptotic costs or report results on different machines and different equation families; a shared set of instances forced algorithms to meet on the same ground.

The suite separates encryption-shaped systems from signature-shaped ones and tests three fields: GF(2), GF(2⁸) and GF(31). Types I through III have twice as many equations as variables, reflecting an overdefined encryption setting. Types IV through VI have about 1.5 times as many variables as equations, reflecting the underdefined systems common in multivariate signatures. Type VI—the Tokyo record—is the last of those, over GF(31).

Records rose through better variants of XL, F4 and Gröbner-basis algorithms, not merely faster processors. M4GB pushed the Type VI frontier to 20 equations in 2017. Sakata and Takagi reached 21 and 22 equations in 2023 with a Hilbert-driven approach. The new work reached 23 and then 24. A gain of two equations can sound modest until one remembers that cryptographic hardness is designed to grow combinatorially. In this terrain, the next step is a wider mountain.

From public keys to the quantum deadline

Modern public-key cryptography began with a conceptual break. In 1976, Whitfield Diffie and Martin Hellman showed how two parties could establish a shared secret over an open channel. In 1978, Ronald Rivest, Adi Shamir and Leonard Adleman published RSA, whose security rests on the difficulty of factoring a large composite integer. Related systems based on discrete logarithms later protected web sessions, software updates, identity systems and digital signatures.

In 1994, Peter Shor showed that a sufficiently capable quantum computer could factor integers and compute discrete logarithms in polynomial time. No such fault-tolerant machine can yet attack the key sizes used across the modern internet. But information requiring long secrecy may be collected now and decrypted later, while changing cryptographic infrastructure can take a decade. That is why governments and standards organizations are migrating before the machine exists.

Multivariate cryptography followed a different mathematical road. In 1988, Tsutomu Matsumoto and Hideki Imai proposed public quadratic polynomial tuples for signatures and encryption. Jacques Patarin broke the construction in 1995 by exposing relations hidden beneath its transformations, then developed new families such as Hidden Field Equations and Oil and Vinegar. The 1999 Unbalanced Oil and Vinegar scheme altered the variable structure after an attack defeated the balanced version.

The history is a cycle: designers hide structure to make signing easy; cryptanalysts exploit too much structure to make forgery easy. Rainbow, a layered descendant of Oil and Vinegar, advanced to the final round of NIST’s first post-quantum competition but did not survive the wave of improved structural attacks. That failure did not prove all MQ cryptography useless. It proved that the generic hardness of solving random equations is only one layer of a scheme’s security. The trapdoor, key compression and implementation can each introduce a shortcut unavailable in a random challenge.

Where multivariate signatures stand in 2026

NIST’s first post-quantum standards, published in August 2024, did not standardize a multivariate scheme. ML-KEM and ML-DSA are based on structured lattices; SLH-DSA is hash-based. Falcon, another lattice signature, is being prepared as FIPS 206, while the code-based HQC was selected in 2025 as an additional encryption mechanism.

But the multivariate branch remains active. In May 2026, NIST advanced nine additional digital-signature candidates to a third evaluation round. Four—MAYO, QR-UOV, SNOVA and UOV—belong to the multivariate family, while MQOM also uses the MQ problem through a different proof-system design. Their attraction is fast verification and exceptionally small signatures. Their persistent cost is large public keys, and attempts to compress those keys with extra algebraic structure can create fresh attack surfaces.

This is the environment in which the Tokyo record matters. NIST evaluates complete schemes; the Fukuoka challenge evaluates generic equation solving. The two cannot be equated, but they inform one another. Generic attacks establish a floor beneath every MQ construction. Scheme-specific attacks look for trapdoors through the ceiling. Secure parameters need room between them.

What the world record says—and what it does not

The result supportsThe result does not support
A new F4 variant can control matrix growth well enough to solve a larger Type VI benchmark.“University of Tokyo broke post-quantum encryption.”
The 36-variable, 24-equation instance is estimated to be about 47,000 times harder than the prior record problem.The algorithm is proven 47,000 times faster in measured runtime.
Generic MQ attack costs should be recalibrated using the new method.Every MQ signature at every parameter size is now unsafe.
Hilbert-series guidance can eliminate redundant algebra before matrices are built.The worst-case complexity of MQ or Gröbner-basis computation has disappeared.
The benchmark advances reproducible cryptanalytic science.A real user key, encrypted message or NIST standard was compromised.

The distinction between a benchmark and a break is not rhetorical caution; it is the substance of security engineering. A 36-variable challenge is tiny beside parameters chosen for real protection, but its cost can reveal whether extrapolations from smaller systems were too optimistic. Conversely, the ability to solve one random benchmark says less about a particular scheme than an attack that exploits that scheme’s hidden symmetry.

Hardware also matters. Four EPYC 7763 processors are substantial but ordinary server technology, not a quantum machine or a national supercomputer. Yet the record submission does not provide a universal cost normalized across every implementation. Memory use, compiler choices, field arithmetic, thread scheduling and the distribution of guessed instances all affect performance. Reproduction and independent comparison will show how broadly the gains transfer.

The unanswered questions

The University of Tokyo team identifies two immediate directions: exploiting newer processor instructions and expanding parallel execution. Both could turn the present demonstration into a faster, more scalable solver. The larger scientific question is whether Hilbert-guided selection keeps its advantage as systems, fields and equation-to-variable ratios change. A method tuned to Type VI may behave differently on overdefined encryption-shaped challenges or on the highly structured public keys of actual signatures.

Quantum computing adds another layer but not a magic wand. Shor’s algorithm devastates factoring and discrete logarithms because those problems possess quantum-accessible structure. No comparably efficient quantum algorithm is known for generic MQ. Grover-style search can reduce some exhaustive-search exponents, and future hybrid algorithms may improve algebraic attacks, but “post-quantum” never means “immune to every quantum or classical advance.” It means parameters are selected against the best attacks currently known.

Implementation security remains outside the record. A mathematically sound signature can leak through timing, power consumption, faults or bad randomness. The large keys of multivariate schemes create bandwidth and storage costs. Standards must weigh security proofs, cryptanalysis, performance, implementability and diversity—not crown the family with the hardest-looking equation.

The attacker builds the ruler

Cryptography advances through an unusual form of public adversity. Designers publish a construction and invite experts to dismantle it. Challenge organizers publish equations and invite solvers to climb as far as they can. A successful attack may erase years of design work, yet it also prevents a weak system from becoming infrastructure. A record solve may move the boundary only two equations, yet it replaces an estimate with evidence.

Sakata and Takagi’s achievement joins two long histories. One is the history of secrecy—from Diffie and Hellman’s open-channel key exchange to the migration now underway for the quantum era. The other is the history of symbolic algebra—from Hilbert’s counting, through Buchberger’s bases, to Faugère’s matrices and today’s multicore servers. The new method works because an idea about the shape of polynomial spaces can tell silicon what not to compute.

That may be the most important lesson of the 994,320 seconds. Brute force alone did not win. The processors finished because mathematics narrowed their attention. The resulting list of 36 field elements is less valuable than the path that reached it: a path other researchers can test, improve and use to set stronger margins.

No lock was opened in Tokyo. Something more preliminary—and, for future security, more useful—was accomplished. The edge of the feasible was measured again. It lies farther out than it did, and every cryptographer designing beyond that edge now has a sharper ruler.

Primary sources and further reading

This report distinguishes the peer-reviewed 2026 publication and the university announcement from the benchmark solve recorded on October 16, 2025. The “47,000 times” figure is presented as the researchers’ estimate of relative problem difficulty, not measured algorithmic acceleration.