Subset sum at the LPS10 parameters ⇒ PKE

Standard model · LPS10

Statement

If subset sum is hard at the LPS10 parameters, there is an IND-CPA-secure PKE whose security is polynomial-time equivalent to that hardness — LPS10. Those parameters satisfy , a density — KF15.

Notes

  • The required subset-sum assumption is weaker than the subset-sum assumptions behind the lattice-based encryption schemes of Ajtai–Dwork, Regev and Peikert — LPS10.
  • A variant of the scheme is secure against key-leakage attacks — LPS10.
  • Random subset sum of density is solvable in subexponential time, and the LPS10 parameters in time — KF15.
  • A PKE whose IND-CCA security is polynomial-time equivalent to subset sum improves on the IND-CPA security of this scheme — FMV16.