# Is Type I lattice trapdoor hard to find even given oracle access to compute inverse of trapdoor function?

Consider the Type I lattice trapdoor in [GPV08]: https://eprint.iacr.org/2007/432.pdf

Suppose a PPT adversary is given the LWE trapdoor function in the picture:

$$g_{A^\top} (s,e) = A^\top s + e = b (\text{mod } q)$$

Let T be a type 1 trapdoor for A.

Now a PPT adversary is given an oracle that does the following: On input b', the oracle answers with a pair of (s',e') that satisfy $$A^\top s' + e' = b' (\text{mod } q)$$.

Can a PPT adversary find a trapdoor T by querying this oracle for polynomially many times?

Picture is from lecture notes: https://fangsong.info/teaching/s16_uw_pqc/qic891_pqc_lec3.pdf

If the adversary is a classical algorithm, then the answer to your question is not known. But if the adversary is a quantum algorithm that can query the oracle in superposition, then the answer is yes: by making queries to the oracle on certain (efficiently produceable) quantum states, it can recover a Type-I trapdoor for $$A$$.

For classical algorithms, the difficulty is that we do not know how to generate a valid output of $$g$$ (that the oracle is obliged to succeed on) except by choosing $$s,e$$ ourselves and feeding them through $$g$$. But then the oracle’s answer is useless to us, because we already know the answer before querying it.

For quantum algorithms the situation is different. We can prepare a certain superposition over “all” valid $$s,e$$, feed it through $$g$$ to get a superposition over outputs, and invoke the oracle to get back $$s,e$$. Critically, this allows us to uncompute (or “forget”) our original choices, leaving us with a useful quantum state. Specifically, by taking its quantum Fourier transform we get a superposition over short vectors $$x$$ such that $$Ax=0$$. By measuring the state we get such an $$x$$, and can repeat to accumulate many linearly independent ones, yielding a Type-1 trapdoor.

The difficulty in the classical setting, and the quantum strategy for dealing with it, are from Regev’s original paper on LWE. The connection to SIS/LWE was first described in the GPV paper.

• does this quantum attack work for type-2 trapdoor?
– Biu
Apr 10, 2020 at 1:31
• Can you define “Type-2 trapdoor”? That term is not widely used. Apr 10, 2020 at 1:32
• it's the trapdoor in definition 1.4 of this lecture note: people.csail.mit.edu/vinodv/6876-Fall2015/L16.pdf
– Biu
Apr 10, 2020 at 1:37
• Oh, that’s usually called an MP trapdoor. Yes, the same quantum technique works; we just need to sample a short solution to $Ax=u$ for some desired vectors $u$, namely, the columns of the gadget matrix $G$. This can be done by introducing an appropriate “phase” to the quantum state before taking the QFT, which yields a superposition over such solutions. Apr 10, 2020 at 1:42