Cryptology City

Cryptology City
Home

❯

Reductions

❯

SXDH, LWE and LPN over a common prime ⇒ Sub exponential SXDH

Nov 21, 2026

SXDH, LWE and LPN over a common prime ⇒ Sub-exponential SXDH

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

If SXDH, LWE and LPN are sub-exponentially hard over a common prime for a bilinear group generator, with constant c, then SXDH is sub-exponentially hard for the same generator with ε=c: the first of its three problems is DDH in each source group, with size bound 2λc and advantage bound 2−λc, by definition — folklore.


Graph View

  • SXDH, LWE and LPN over a common prime ⇒ Sub-exponential SXDH
  • Statement

Backlinks

  • Decisional Diffie-Hellman

Created with Quartz v4.5.2 © 2026

  • GitHub
  • Bluesky