IBM Research has just announced that one of the five winners of the Pat Goldberg Memorial Best Paper Award for 2012 is a paper on Fully Homomorphic Encryption by Bristol's Prof. Nigel Smart with two colleagues from IBM's T.J. Watson Research Laboratory.
Close to 120 papers in computer science, electrical engineering and mathematical sciences published in refereed conference proceedings and journals in 2012 were submitted by IBM Research authors worldwide for the Pat Goldberg Memorial 2012 Best Papers in CS, EE and Math. From these submissions, the Research Professional Interest Communities (PICs) nominated 36 papers based on technical significance (depth and breadth) and expected impact on computer science, electrical engineering or mathematical sciences, or their applications in the research disciplines covered by the PICs.
A committee then reviewed the nominated papers and selected five as winners of the Pat Goldberg Memorial 2012 Best Paper Awards. Among the five was the paper "Homomorphic Evaluation of the AES Circuit" co-authored by Prof. Nigel Smart of the Dept. of Computer Science at the University of Bristol and Shai Halevi and Craig Gentry of IBM. The paper appeared in the prestigous IACR organized CRYPTO 2012 conference in Santa Barbara.
The citation for the paper says that "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 paper has already been heavily cited, with over 90 citations according to Google Scholar."
Full details of all the winners is available here.
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.