Efficient Public-key Encryption Scheme Based on Ring-LPN

The LPN problem is one of the basic problems to construct post-quantum cryptographic schemes, due to its simple operations and resistance to quantum attacks. However, large part of LPN based cryptographic schemes suffer from large key size which limits their availability. Fortunately, the structured LPN (such as Ring-LPN, Toepliz-LPN, etc.) based public-key cryptography can reduce storage requirements and further improve the efficiency. Therefore, we take advantage of the Ring-LPN and the tag-based encryption technology, propose and prove the knapsack problems on the ring, and then present a Ring-LPN based public key encryption scheme which is provably CCA secure. Concretely, our scheme has less computational cost and storage overhead when compared with those of previously proposed LPN based cryptographic schemes, fewer samples are required and ciphertext expansion rate are smaller than LPN based schemes which achieve the same security level. At the same time, the CCA security of the scheme is reduced to the Ring-LPN Assumption in the standard model.