Paper 2011/133

Fully Homomorphic SIMD Operations

N. P. Smart and F. Vercauteren

Abstract

At PKC 2010 Smart and Vercauteren presented a variant of Gentry's fully homomorphic public key encryption scheme and mentioned that the scheme could support SIMD style operations. The slow key generation process of the Smart--Vercauteren system was then addressed in a paper by Gentry and Halevi, but their key generation method appears to exclude the SIMD style operation alluded to by Smart and Vercauteren. In this paper, we show how to select parameters to enable such SIMD operations, whilst still maintaining practicality of the key generation technique of Gentry and Halevi. As such, we obtain a somewhat homomorphic scheme supporting both SIMD operations and operations on large finite fields of characteristic two. This somewhat homomorphic scheme can be made fully homomorphic in a naive way by recrypting all data elements seperately. However, we show that the SIMD operations can be used to perform the recrypt procedure in parallel, resulting in a substantial speed-up. Finally, we demonstrate how such SIMD operations can be used to perform various tasks by studying two use cases: implementing AES homomorphically and encrypted database lookup.

Note: Much improved exposition and algorithms.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
public-key cryptography
Contact author(s)
frederik vercauteren @ gmail com
History
2011-08-03: revised
2011-03-21: received
See all versions
Short URL
https://ia.cr/2011/133
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/133,
      author = {N. P.  Smart and F.  Vercauteren},
      title = {Fully Homomorphic SIMD Operations},
      howpublished = {Cryptology ePrint Archive, Paper 2011/133},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/133}},
      url = {https://eprint.iacr.org/2011/133}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.