IBM researcher Craig Gentry discusses breakthrough

Last month, IBM announced that researcher Craig Gentry made a cryptographic breakthrough with big implications for data privacy. The so-called “fully homomorphic encryption” technology is years away, according to IBM, but its promise for companies that handle and store individuals’ data is anticipated to be profound.

”[Fully homomorphic encryption] would give us new confidence that you can secure the world’s infrastructure and bring intelligence to it without exposing data to greater risks,” the head of IBM’s research arm told Forbes.

Researcher Craig Gentry discusses the breakthrough here.

IAPP: Is the anticipated implementation platform-neutral (i.e., will it support any database structure)?

Gentry: Yes. Abstractly, you can view a ciphertext as a secure box that holds a message. Now, suppose that you have several messages m_1, ...m_t (or several database entries) that are encrypted under the same public key—i.e., the messages are, in some sense, inside the same box. If the encryption scheme is fully homomorphic, then, for any efficiently computable function f, you can use the encryptions of m_1, ..., m_t to compute a ciphertext that encrypts f(m_1, ...m_t) -- i.e., you get f (m_1, ..., m_t) inside the same box—and you can compute this new ciphertext without the secret decryption key.

For example, a user could store encryptions of m_1, ..., m_t on a database server. Suppose that the user later wants some function of its data—i.e., f(m_1, ..., m_t). This function f might be a JOIN query, or it might output all of the entries containing some substring, ... whatever. Using the fully homomorphic encryption scheme, the server can compute an encryption of f(m_1, ..., m_t), send that ciphertext to the user, and the user decrypts it to recover the desired information.

Again, as long as you can compute the function f reasonably efficiently, then you can compute the same function over encrypted data (getting an encrypted result), though computing the function over encrypted data takes much longer. In particular, the scheme is independent of the data structures used. (In contrast, most likely the function f that you want to compute would be dependent on the data structure.)

IAPP: Does the current implementation encrypt at the table, column, or field level, or are these reference models inapplicable?

There isn’t an ”implementation” yet; currently, there is only a mathematical description of the scheme.

The reference models are inapplicable, as stated above. Any program or database-querying system could be ”compiled” into an (encypted) program or (encrypted) system that has encrypted input and output.

IAPP: How does it compare to other fully homomorphic encryption schemes? What makes it different?

Gentry: There aren’t any other fully homomorphic encryption schemes. A bit more accurately, and to get a bit technical, there are previous schemes but their performance (running time) depends *exponentially* on the function f that you are computing, whereas the running time of my scheme depends only *polynomially* on the function f. In other words, to put it simply, even though my current scheme is rather slow, previous schemes would be much, much slower—ridiculously slower—for mildly complex functions f.

IAPP: A Forbes article on your scheme mentioned that the current application is cumbersome, and that years of newly developed efficiencies will be required to make it commercially viable. Can the technology be implemented (albeit, inefficiently) on typical current datawarehouse hardware, or are you anticipating that hardware advances over the coming years would make this viable? Is the sense that optimization of the algorithm will improve performance, or that computing hardware will advance to make this unnecessary?

I’m optimistic that, over the next couple of years or so, researchers will find ways to make the algorithms themselves significantly faster, and that the algorithmic speed-up will be much larger than the hardware speed-up over this period. I think it makes sense to find this low-hanging fruit before commercializing it.

It’s dangerous to speculate on when it will be ready to be used on databases...

One issue is that, although part of the appeal of my scheme is that it is ”fully” homomorphic in the sense that it can handle arbitrary functions f, my scheme performs significantly better if the complexity of the function f falls below a certain threshold. Once the complexity of f goes above a certain threshold, I need to use a technique that I call ”bootstrapping,” a computationally-intensive operation in which I ”refresh” the intermediate ciphertexts on my way to computing the eventual output ciphertext (an encryption of f(m_1, ..., m_t)). However, if the complexity of f falls below the threshold, I can get by without using bootstrapping, and the scheme is much closer to being practical for such functions. I would imagine that relatively simple functions, such as a JOIN operation in a database query, would fall into this below-the-threshold category.


If you want to comment on this post, you need to login.


Board of Directors

See the esteemed group of leaders shaping the future of the IAPP.

Contact Us

Need someone to talk to? We’re here for you.

IAPP Staff

Looking for someone specific? Visit the staff directory.

Learn more about the IAPP»

Daily Dashboard

The day’s top stories from around the world

Privacy Perspectives

Where the real conversations in privacy happen

The Privacy Advisor

Original reporting and feature articles on the latest privacy developments

Privacy Tracker

Alerts and legal analysis of legislative trends

Privacy Tech

Exploring the technology of privacy

Canada Dashboard Digest

A roundup of the top Canadian privacy news

Europe Data Protection Digest

A roundup of the top European data protection news

Asia-Pacific Dashboard Digest

A roundup of the top privacy news from the Asia-Pacific region

Latin America Dashboard Digest

A roundup of the top privacy news from Latin America

IAPP Westin Research Center

Original works. Groundbreaking research. Emerging scholars.

Get more News »

IAPP Communities

Meet locally with other privacy pros, dive deep into a specialized topic or simply share a common interest, IAPP Communities are for you.

IAPP Job Board

Looking for a new challenge, or need to hire your next privacy pro? The IAPP Job Board is the answer.

Join the Privacy List

Have ideas? Need advice? Subscribe to the Privacy List. It’s crowdsourcing, with an exceptional crowd.

Find more ways to Connect »

Find a Privacy Training Class

Two-day privacy training classes are held around the world. See the complete schedule now.

NEW! Raise Staff Awareness

Equip all your data-handling staff to reduce privacy risk, with Privacy Core™ e-learning essentials.

Online Privacy Training

Build your knowledge. The privacy know-how you need is just a click away.

The Training Post—Can’t-Miss Training Updates

Subscribe now to get the latest alerts on training opportunities around the world.

Upcoming Web Conferences

See our list of upcoming web conferences. Just log on, listen in and learn!

Train Your Team

Get your team up to speed on privacy by bringing IAPP training to your organization.

Learn more »

CIPP Certification

The global standard for the go-to person for privacy laws, regulations and frameworks

CIPM Certification

The first and only privacy certification for professionals who manage day-to-day operations

CIPT Certification

The industry benchmark for IT professionals worldwide to validate their knowledge of privacy requirements

NEW! FIP Designation

Recognizing the advanced knowledge and issue-spotting skills a privacy pro must attain in today’s complex world of data privacy.

Certify Your Staff

Find out how you can bring the world’s only globally recognized privacy certification to a group in your organization.

Learn more about IAPP certification »

Get Schooled in Privacy

Looking to get some higher-ed in privacy? Check out these schools that include data privacy courses in their curricula.

Privacy Vendor List

Find a privacy vendor to meet your needs with our filterable list of global service providers.

NEW! Raise Staff Awareness

Equip all your data-handling staff to reduce privacy risk, with Privacy Core™ e-learning essentials.

The Industry of Privacy

Take stock, compare your practices to those of other organizations, and get budget with these studies on the industry of privacy.

More Resources »

Time to Get to Work at the Congress

Thought leadership, a thriving community and unrivaled education...the Congress prepares you for the challenges ahead. Register today.

GDPR Comprehensive London

Our third and final GDPR Comprehensive 2016 was a great success. London delegates spent two full days with world-recognized experts taking a guided tour of the GDPR.

Call for Speakers at Summit 2017

Are you an engaging speaker with privacy expertise to share? We want you! Submit a proposal today! The Call for Speakers closes Oct. 2, 2016.

GDPR's Top Impacts - Webcon Delivered in French

Rejoignez des experts pour en savoir plus : Les 10 conséquences pratiques les plus importantes du RGPD. S’inscrire maintenant.

Intensive Education at the Practical Privacy Series

The Series is returning to DC, this year spotlighting Data Breach, FTC and Consumer Privacy, GDPR and Government privacy issues. It’s the education you need now!

Sponsor an Event

Increase visibility for your organization—check out sponsorship opportunities today.

More Conferences »

Become a Member

Start taking advantage of the many IAPP member benefits today

Corporate Members

See our list of high-profile corporate members—and find out why you should become one, too

Renew Your Membership

Don’t miss out for a minute—continue accessing your benefits

Join the IAPP»