Homomorphic
Evaluation of the AES Circuit
Craig
Gentry (IBM Research)
Shai Halevi (IBM Research)
Nigel
P. Smart (
Abstract:
We describe a working implementation of leveled homomorphic
encryption (without bootstrapping) that can evaluate the AES-128 circuit in
three different ways. One variant takes under over 36 hours to evaluate an
entire AES encryption operation, using NTL (over GMP) as our underlying
software platform, and running on a large-memory machine. Using SIMD techniques,
we can process over 54 blocks in each evaluation, yielding an amortized rate
of just under 40 minutes per block. Another
implementation takes just over two and a half days to evaluate the AES
operation, but can process 720 blocks in each evaluation, yielding an
amortized rate of just over five minutes per block. We also detail a third
implementation, which theoretically could yield even better amortized
complexity, but in practice turns out to be less competitive.
For our implementations we develop both AES-specific optimizations as well as
several “generic” tools for FHE evaluation. These last tools
include (among others) a different variant of the Brakerski-Vaikuntanathan
key-switching technique that does not require reducing the norm of the ciphertext vector, and a method of implementing the Brakerski-Gentry-Vaikuntanathan modulus-switching
transformation on ciphertexts in CRT
representation.