QR ⇒ TDH

QR 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:

• ‘QR’ is written as bare text with NO wikilink although content/Assumptions/quadratic-residuosity.md exists — the hypothesis node is inferred, not linked.
• QR branch of the disjunction.
• ‘QR’ is written as bare text with NO wikilink even though content/Assumptions/quadratic-residuosity.md exists — a reference-fixer-lane defect.