Cryptology City

Cryptology City
Home

❯

Reductions

❯

Subset sum at constant density above one ⇒ Subset sum

Nov 21, 2026

Subset sum at constant density above one ⇒ Subset sum

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

Statement

If subset sum is hard at constant density above one for ℓ(n)=(1−c)n and a constant c∈(0,1), then subset sum is hard for (n,M) with M=2ℓ(n), with the same advantage — folklore.


Graph View

  • Subset sum at constant density above one ⇒ Subset sum
  • Statement

Backlinks

  • Subset sum

Created with Quartz v4.5.2 © 2026

  • GitHub
  • Bluesky