How to build a faster private information retrieval protocol

A CPA secure multi-bit somewhat homomorphic encryption scheme based on Learning With Errors over Rings assumption is presented. We use canonical embedding to transform ring elements into vectors over Z q , and thus decrease encryption and decryption cost. Comparing with GHV scheme appeared in 2010, to encrypt n bits, this scheme can reduce encryption cost from O(n 3/2) into O(nlog n). Finally, an efficient private information retrieval protocol that employs this scheme is presented.