Homomorphic Encryption From Codes

Download Now Date Added: Nov 2011
Format: PDF

The authors propose a new homomorphic encryption scheme based on the hardness of decoding under independent random noise from certain affine families of codes. Unlike in previous lattice-based homomorphic encryption schemes, where the message is hidden in the noisy part of the ciphertext, their scheme carries the message in the affine part of the transformation and applies noise only to achieve security. Their scheme can tolerate noise of arbitrary magnitude, as long as the noise vector has sufficiently small hamming weight (and its entries are independent).