Homomorphic Encryption paper scoops IBM Research Award
A Professor of Cryptology in the Department of Computer Science at Bristol University has won an award from IBM Research.
A paper on “Fully Homomorphic Encryption” by Bristol’s Professor Nigel Smart is the winner of the Pat Goldberg Memorial Best Paper Award, the university highlights.
The citation for the paper says:
This paper represents a large step forward in the advancement of fully- homomorphic encryption. It describes optimizations that allow for a fully-homomorphic implementation of a complex and practical circuit, the AES encryption algorithm. The optimizations are both AES-focused and applicable more generally to future implementations of fully-homomorphic circuits. They reduced the running time of a circuit like AES by roughly two orders of magnitude, down to 36 hours to compute the encryption of a single AES block. Other optimizations that process multiple blocks simultaneously achieve an amortized rate of just over five minutes per block, reducing the running time from around 150 days, to five minutes.
To note a few of the contributions of the work: strategies for minimizing costly operations that are unique in fully-homomorphic encryption; new ways of structuring algorithms to reduce the required key space; and twists on the key concepts regarding how to handle noise in evaluations. These techniques can be applied to a wide variety of algorithms to see how amenable they are to fully-homomorphic encryption implementations. Further, their integration of SIMD and other parallel optimizations that allow multiple blocks (in this case up to 720) to be processed simultaneously will likely be a hallmark of fully-homomorphic implementations moving forward. In scenarios where throughput, and not latency, are a primary concern, fully-homomorphic encryption is becoming more practical.
The work in this paper was funded by DARPA and AFRL under the PROCEED programme, the European Commission through the ECRYPT II project and via an ERC Advanced Grant, by EPSRC via the COED project, and by a Royal Society Wolfson Merit Award.
See also: Homomorphic encryption