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.