In Paris this week Prof Nigel Smart will be presenting a paper which make a step towards a fully practical system to compute on encrypted data. The paper will be presented at the 13th IACR workshop on Public Key Cryptography. This work could eventually have impacts on areas as diverse as database access, electronic auctions and electronic voting.
For nearly 30 years one cryptographic dream has been to come up with an encryption scheme for which you can 'add' and 'multiply' ciphertexts, i.e. a so-called fully homomorphic scheme. This means that given two ciphertexts c1 and c2 which encrypt messages m1 and m2 under a key k, i.e.
there is an operation Add, which anyone can perform, which produces a ciphertext c3 which is the encryption of m1+m2; and an operation Multiply, again which anyone can perform, which produces a ciphertext c4 which is the encryption of m1*m2,
#c3=Add(c1,c2) = enc(k,m1+m2)
#c4=Multiply(c1,c2) = enc(k,m1*m2)
The important point is that to apply Add and Multiply we do not need knowledge of the key k.
So whats the big deal about Add and Multiply? Well as soon as you can Add and Multiply you can compute ANY function! For example, suppose you are engaged in an online auction, you could encrypt your bids to the auctioneer, but maybe you do not trust the auctioneer to find out what your bid is. Maybe the auctioneer
could use this to cheat and encourage higher bids to increase his commission. Using a fully homomorphic scheme the auctioneer could work out who won, and what the winning bid was without learning what all the other bids were.
As another example you could encrypt your vote in an online election and then the central authority could work out who won the election, without learning anything about the votes of the individual voters. Thus voter privacy would be ensured.
Over the years many encryption schemes have been proposed which either have the Add operation or the Multiply operation, but not both. In 2009 Craig Gentry from IBM came up with the first scheme which simulataneously allows you to Add and Multiply ciphertexts. Gentry's scheme was a major theoretical breakthrough.
In the paper to be presented in Paris this week, Nigel Smart and Frederik Vercauteren (KU Leuven and ex-Bristol) devise a way of simplifying Gentry's scheme so that it becomes more practical. Whilst the new scheme is not fully practical it is an important step along the way to forming a system which is truly practical.
Smart and Vercauteren's scheme also provides an intriguing new application of objects in an area of Pure Mathematics called Class Groups of Number Fields. Such objects have been studied in pure mathematics for around two centurys with little possibility of impact on everyday life. This work is therefore another example of the unexpected applicability of decades of curiosity driven research.