A Practical Public Key Encryption Scheme Based on Learning Parity With Noise

To protect cyber security and privacy, it is critical to design security and practical public key encryption schemes. Today, big data and cloud computing bring not only unprecedented opportunities but also fundamental security challenges. Big data faces many security risks in the collection, storage, and use of data and brings serious problems regarding the disclosure of private user data. It is challenging to achieve security and privacy protection in the big data environment. Thus, to meet the growing demand of public key encryption in this environment, we proposed a single-bit public key encryption scheme based on a variant of learning parity with noise (LPN) and extended it to a multi-bit public key encryption scheme. We proved the correctness and chosen plaintext attack security of the proposed method. Our schemes solved encoding error rate problems of the existing public key schemes based on LPN, and the encoding error rate in our schemes is negligible.