4
$\begingroup$

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

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ does this quantum attack work for type-2 trapdoor? $\endgroup$
    – Biu
    Apr 10 '20 at 1:31
  • $\begingroup$ Can you define “Type-2 trapdoor”? That term is not widely used. $\endgroup$ Apr 10 '20 at 1:32
  • $\begingroup$ it's the trapdoor in definition 1.4 of this lecture note: people.csail.mit.edu/vinodv/6876-Fall2015/L16.pdf $\endgroup$
    – Biu
    Apr 10 '20 at 1:37
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 10 '20 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.