A research student who had a summer job at IBM, has cracked a cryptography problem that has baffled experts for over 30 years. The breakthrough may pave the way to secure cloud computing services.
Craig Gentry conducted the research while he was a summer student at IBM Research, working on his PhD at Stanford University. Gentry's breakthrough, called "privacy homomorphism", or "fully homomorphic encryption", makes it possible to analyse encrypted information without sacrificing confidentiality.
This is important because if data is encrypted it is impossible to analyse. IT staff such as database and network administrators need to see the type of data being accessed or transported across a network to optimise the database and network to improve performance. However, you wouldn't want database administrators accessing private information such as the salaries in the HR database to find out how much the board earns.
Storage administrators also need to understand the data being accessed to make sure the enterprise storage system is running at its best. However, until now, they could not see encrypted data, which meant the systems could not be optimised for the type of data, or the data needed to be unencrypted, leading to possible IT security infringements.
Gentry appears to have cracked the problem by using a mathematical object called an ideal lattice to enable people to fully interact with encrypted data in ways previously thought impossible. IBM says the breakthrough could enable computer makers that offer secure storage to optimise data storage without decrypting the information.
IBM believes privacy homomorphism will boost cloud computing by helping providers host confidential data of businesses and governments.
Privacy homomorphism may allow a cloud computing provider to perform computations on clients' data at their request, such as analysing sales patterns, without exposing the original data.
Other potential applications include identifying spam in encrypted e-mail, or protecting information contained in electronic medical records. IBM believes the breakthrough might also one day enable computer users to retrieve information from a search engine with more confidentiality.
Charles Lickel, vice-president of software research at IBM, says, "Fully homomorphic encryption will enable businesses to make more informed decisions, based on more studied analysis, without compromising privacy. We also think that the lattice approach holds potential for helping to solve additional cryptography challenges in the future."
Two fathers of modern encryption, Ron Rivest and Leonard Adleman, together with Michael Dertouzos, introduced and struggled with the notion of fully homomorphic encryption 30 years ago. Although advances through the years offered partial solutions to this problem, a full solution that achieves all the desired properties of homomorphic encryption did not exist until now, according to IBM.
Quoted on the Cryptography, Law and Privacy blog, Hal Finney, who co-wrote PGP 2, describes Gentry's breakthrough as "one of the most remarkable crypto papers ever". Finney says, "Not only does it solve one of the oldest open problems in cryptography, the construction of a fully homomorphic encryption system, it does so by means of a self-embedding technique reminiscent of Godel's theorem."
However, on the same site, another blogger described Gentry's approach as "impractical".
IBM seems sure homomorphic encryption will work. Lickel says, "We think that the lattice approach holds potential for helping to solve additional cryptography challenges in the future."
It is too early to say how this technology will develop. The general consensus online is that Gentry has genuinely cracked a tough problem. Now, IBM just has to make it commercially viable.
This was first published in June 2009