British researcher cracks crypto problem

A British researcher has helped put into practice an encryption scheme that could better protect sensitive data while it is being used in systems such as health-care computing.

The scheme involves fully homomorphic encryption, an approach that allows computation to be performed on encrypted data without the need to decrypt the data, according to Nigel Smart, professor of cryptology in the Department of Computer Science at the University of Bristol.

Last year, IBM researcher Craig Gentry came up with the first homomorphic scheme, which allowed simultaneous 'add' and 'multiply' operations on encrypted values, called ciphertexts.

In a paper presented at an IACR workshop in Paris on Tuesday, Smart outlined how he and Frederik Vercauteren of the Katholieke University Leuven in Belgium took Gentry's theoretical method and developed mechanisms to produce a practical variant.

"Although our practical variant is not truly practical, it can actually now be implemented and tested on real examples," Smart told ZDNet UK. "The problem is that the examples we can deal with are rather small."

Fully homomorphic encryption could allow hospitals or drug-research companies to perform statistical calculations on patient records held in databases without the need to decrypt the data and thus reveal information about the individual patients, Smart said.

The approach could also allow an online auctioneer to analyse encrypted bids and arrive at the winning bid without needing to reveal the values of the other bids or the identities of the bidders.

Smart and Vercauteren, as well as enabling the computation of small functions on encrypted data, produced an "explicit estimate of what the bottleneck is in turning this from computing only small functions to computing any function", Smart said.

The limitation keeping the technique from being completely practical is that as computation is carried out on ciphertexts, the ciphertexts become "dirty", said Smart. "Gentry has a way of 'cleaning' the ciphertexts, but currently this cleaning mechanism is not practical and only works for infeasibly large parameters," he added.

To move the technique forward, researchers need a more practical method for "cleaning" cyphertexts, he said. "Alternatively, a method which stops the ciphertext getting as dirty might help," he said. "More than likely it will be a combination of the two ideas. Better soap and less muck."