In the last twenty years, multivariate cryptography has emerged as a potential
alternative to RSA or DLOG [12,2] schemes. Many schemes have been proposed
whose security appears somehow related to the problem of deciding whether
or not a quadratic system of equations is solvable, which is known to be NPcomplete
[5]. An attractive feature of such schemes is that they have efficient
implementations on smart cards, although the public and secret keys are rather
large. Contrary to RSA or DLOG schemes, no polynomial quantum algorithm
is known to solve this problem.