Subset sum at the LPS10 parameters ⇒ PKE
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.