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.