[leftmargin = *]
Aaronson and Christiano [1]}. As mentioned above, this scheme is based on hidden subspaces of the vector space \(\mathbb {F}_2^n\) . The hard problem behind this scheme is to recover a secret linear subspace of \(\mathbb {F}_2^n\)  from the the set of common roots of a set of random polynomials over \(\mathbb {F}_2\) . The previous attack, carried out by Pena et al. [2]}, against this scheme uses the Gröbner basis algorithm. Their attack is only effective if the scheme was defined over \(\mathbb {F}_p\)  for larger \(p\) , instead of \(\mathbb {F}_2\) . It was conjectured in [2]} that there exists a quasi-polynomial time algorithm for the original scheme over \(\mathbb {F}_2\) .
We give a polynomial time quantum algorithm for the case \(\mathbb {F}_2\) . Our attack is geometric, it uses the fact that a linear variety is isomorphic to its Zariski tangent space at any point. In particular, the subspace hidden by a set of polynomials can be viewed as a linear variety \(Y\)  included in an affine variety \(X\) . We show that one can recover the hidden subspace by simply computing the kernel of the Jacobian matrix of \(X\)  at a random point of the subspace \(Y\) . Such a random point is obtained by measuring a money state.

Zhandry [4]}. This scheme is based on Multivariate Hash Functions. There are different versions of the paper [4]} that give slightly different formulations of the scheme, but the underlying hardness assumptions can all be stated using the idea of multi-collision of multivariate polynomial hash functions. We will focus on the version [6]}, in which the hardness assumption is directly stated using quadratic forms.
We give a polynomial time quantum algorithm, using which one can obtain arbitrarily many copies of a given banknote. Our algorithm uses the verification circuit of the scheme to produce a certain superposition of “bolts”. A measurement on this superposition then produces a copy of the money state with high probability. The ability to produce arbitrarily many copies of the money state comes from the fact the measurement outcome \(y^{\prime }\)  can be compared against the given serial number \(y\) . If \(y^{\prime } = y\)  then desired money state has been produced, otherwise the whole process is repeated.

Kane [7]}. This scheme is based on modular forms. There have not been any attempts at cryptanalyzing this scheme yet, partly because of the mathematics involved which is rather nontrivial. The underlying hard problem in this scheme is simply cloning the money state which is an eigenstate of the set of all Hecke operators.
Although we have not been able to break this scheme, we give a polynomial time quantum reduction from the underlying hard problem to the problem of inverting a certain matrix \(A\) . Our algorithm is based on a deep connection between ideal classes in a rational quaternion algebra and the space of modular forms of weight 2 over the complex numbers. The connection is provided by the theory of Theta series. The matrix \(A\)  is highly structured, with entries the representation numbers of explicit quaternary quadratic forms. In other words, \(A\)  can be described by a set of polynomials of degree two in four variables. To work with this matrix, one does not need to know much about the theory behind the scheme. We believe that this reduction is an important first step toward an effective cryptanalysis of this scheme, and opens interesting new avenues for future attacks.

