The bet that early multivariate schemes hid their shortcut. Attackers found hidden patterns and inverted them without the key.
The idea: These schemes take a map that's easy to invert, like raising to a fixed power in a large field, and hide it between two secret linear scrambles. Patarin noticed that for C* every input and output satisfy simple equations, which anyone can learn from enough examples and then use to invert the map without the scrambles.
Why it matters: It took down SFLASH, a scheme a European standards project had recommended.
On the map: ✗ C* broken 1995 (Patarin), its "minus" variant SFLASH, 2007
Matsumoto and Imai's 1988 scheme C*[1] was one of the first multivariate public-key schemes: an easily inverted map over a large field, disguised by secret linear changes of variables. In 1995 Patarin found[2] simple equations linking inputs and outputs that let anyone invert it without the key.
"Minus" variants, which hide some of the outputs, were meant to block that attack. SFLASH used one. In 2007 Dubois, Fouque, Shamir and Stern[3] found a hidden symmetry that let them rebuild the missing outputs, after which Patarin's attack applied again. HFE, a related trapdoor, has also been badly weakened by algebraic attacks[4].
If any of these breaks, this breaks too.
If this breaks, these break with it.