In the last twenty years, multivariate cryptography has emerged as a potentialalternative to RSA or DLOG [12,2] schemes. Many schemes have been proposedwhose security appears somehow related to the problem of deciding whetheror 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 efficientimplementations on smart cards, although the public and secret keys are ratherlarge. Contrary to RSA or DLOG schemes, no polynomial quantum algorithmis known to solve this problem.