Simpler CCA Secure PKE from LPN Problem Without Double-Trapdoor

摘要

The first CCA secure public key encryption (PKE) on the learning parity with noise (LPN) assumption was invented by Dottling et al. (ASIACRYPT 2012). At PKC 2014, Kiltz et al. gave a simpler and more efficient construction, where a double-trapdoor technique was introduced to handle the decryption queries in game simulation. Different from the technique, we build in the standard model the CCA secure PKE on a variant of Extended Knapsack LPN problem (which is provably equivalent to the standard LPN problem). We abstract out an ephemeral key from the LPN assumption, which can then be used to encrypt the underlying plaintext when equipped with several typical classes of cryptographic primitives. Thanks to these techniques, the decryption queries can be correctly answered (yet without relying on a double-trapdoor mechanism) during security reduction from LPN. The resulting simple proposal appears more modular and efficient.