Paper 2012/565

Packed Ciphertexts in LWE-based Homomorphic Encryption

Zvika Brakerski, Craig Gentry, and Shai Halevi

Abstract

In this short note we observe that the Peikert-Vaikuntanathan-Waters (PVW) method of packing many plaintext elements in a single Regev-type ciphertext, can be used for performing SIMD homomorphic operations on packed ciphertext. This provides an alternative to the Smart-Vercauteren (SV) ciphertext-packing technique that relies on polynomial-CRT. While the SV technique is only applicable to schemes that rely on ring-LWE (or other hardness assumptions in ideal lattices), the PVW method can be used also for cryptosystems whose security is based on standard LWE (or more broadly on the hardness of ``General-LWE''). Although using the PVW method with LWE-based schemes leads to worse asymptotic efficiency than using the SV technique with ring-LWE schemes, the simplicity of this method may still offer some practical advantages. Also, the two techniques can be used in tandem with ``general-LWE'' schemes, suggesting yet another tradeoff that can be optimized for different settings.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Homomorphic EncryptionLWEPacked Ciphertexts
Contact author(s)
shaih @ alum mit edu
History
2012-10-07: received
Short URL
https://ia.cr/2012/565
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/565,
      author = {Zvika Brakerski and Craig Gentry and Shai Halevi},
      title = {Packed Ciphertexts in LWE-based Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2012/565},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/565}},
      url = {https://eprint.iacr.org/2012/565}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.