An advance in Encrypted Search

I recently posted in The Search for Encrypted Search an overview of the breakthrough last year made by Craig Gentry of IBM to search data while it is in encrypted form. The breakthrough was largely theoretical since the required computational overhead to support encrypted search is huge, which for example would increase the time for a Google search by roughly a factor of a trillion.

In such cases, it is always an open question as to whether the breakthrough will stand as an unimprovable milestone, or be the beginning of series of improvements towards a practical solution. We now have the first evidence that we are dealing with the latter case for encrypted search.

A press release from the University of Bristol in the UK reports that

Nigel Smart, Professor of Cryptology in the Department of Computer Science at the University of Bristol, will present a paper in Paris this week [Friday 28 May], which makes a step towards a fully practical system to compute on encrypted data. The work could have wide ranging impact on areas as diverse as database access, electronic auctions and electronic voting.

Professor Smart said: “We will present a major improvement on a recent encryption scheme invented by IBM in 2009.”

“Our scheme allows for computations to be performed on encrypted data, so it may eventually allow for the creation of systems in which you can store data remotely in a secure manner and still be able to access it.”

Together with Frederik Vercauteren, from the Katholieke University Leuven in Belgium, Smart has simplifed Gentry’s scheme so that it becomes more practical - not totally so, but an improvement. More information should be available after the paper is published.