Paper 2010/121

Lattice-Based Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack

Chen Huiyan and Li Zichen

Abstract

We propose a simple and efficient construction of CCA- secure public-key encryption scheme based on lattice. Our construction needs an encryption scheme, which we call \matrix encryption", as building block, and requires the underlying matrix encryption scheme to satisfy only a relatively weak notion of security which can be achievable without random oracles. With the pseudohomomorphism property of mR04 of [3], which is the multi-bit version of single-bit cryptosystems R04 [1], we design a matrix encryption scheme which satisfies the above requirements, thus, our construction provides a new approach for constructing CCA-secure encryption schemes in the standard model. So far as we know, our construction is the first CCA-secure cryptosystem which is directly constructed from lattice and whose security is based on the unique shortest vector problem (uSVP). In addition, the method designing the matrix encryption scheme from mR04 also adapts to mR05, mA05, mADGGH of [3], which are the multibit versions of single-bit cryptosystems R05 [2], A05 [5], and ADGGH [7], respectively, since they have the same pseudohomomorphism property as mR04. This result makes our approach constructing CCA-secure cryptosystem become generic and universal.