Paper 2009/576

Public-Key Cryptographic Primitives Provably as Secure as Subset Sum

Vadim Lyubashevsky, Adriana Palacio, and Gil Segev

Abstract

We propose a semantically-secure public-key encryption scheme whose security is polynomial-time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC '97), Regev (STOC '03, STOC '05), and Peikert (STOC '09). Additionally, our proof of security is simple and direct. We also present a natural variant of our scheme that is secure against key-leakage attacks, as well as an oblivious transfer protocol that is secure against semi-honest adversaries.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
subset sumcryptosystemoblivious transfer
Contact author(s)
vlyubash @ cs ucsd edu
History
2009-12-01: received
Short URL
https://ia.cr/2009/576
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/576,
      author = {Vadim Lyubashevsky and Adriana Palacio and Gil Segev},
      title = {Public-Key Cryptographic Primitives Provably as Secure as Subset Sum},
      howpublished = {Cryptology ePrint Archive, Paper 2009/576},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/576}},
      url = {https://eprint.iacr.org/2009/576}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.