  In this paper we present a novel method to generate hard instances with
planted solutions based on the public-private McEliece post-quantum
cryptographic protocol. Unlike other planting methods rooted in the
infinite-size statistical analysis, our cryptographic protocol generates
instances which are all hard (in cryptographic terms), with the hardness tuned
by the size of the private key, and with a guaranteed unique ground state. More
importantly, because of the private-public key protocol, planted solutions
cannot be easily recovered by a direct inspection of the planted instances
without the knowledge of the private key used to generate them, therefore
making our protocol suitable to test and evaluate quantum devices without the
risk of "backdoors" being exploited.
