Generalizing cryptosystems based on the subset sum problem

摘要

We identify a generic construction of cryptosystems based on the subset sum problem and characterize the required homomorphic map. Using the homomorphism from the Damg?rd-Jurik cryptosystem, we then eliminate the need for a discrete logarithm oracle in the key generation step of the Okamoto et al. scheme to provide a practical cryptosystem based on the subset sum problem. We also analyze the security of our cryptosystem and show that with proper parameter choices, it is computationally secure against lattice-based attacks. Finally, we present a practical application of this system for RFID security and privacy.