Fully Homomorphic SIMD Operations

N. P.  Smart; F.  Vercauteren

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: 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},
      url = {https://eprint.iacr.org/2011/133}
}