LWE ⇒ TDH

LWE implies TDH.

Statement

Migrated verbatim from single-server-private-information-retrieval § Constructions:

• PIR with $\mathrm{polylog}(n)$ bandwidth can be built from DDH, QR, or LWE — DGI+19
  • This result goes through the use of TDH, which can be used to build PIR generically

Notes

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• The LWE-based TDH of DGI+19 comes with its own parameter regime, not carried by the edge.
• LWE branch of the disjunction.
• The sub-bullet’s own claim (‘TDH … can be used to build PIR generically’) is an independent edge TDH ⇒ PIR that also deserves its own record at migration time.