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 privacy pros, dive deep into specialized topics or connect over common interests. Find your Community in KnowledgeNet Chapters, Sections and Affinity Groups.

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 a KnowledgeNet Chapter Near You

Talk privacy and network with local members at IAPP KnowledgeNet Chapter meetings, taking place worldwide.

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 »

IAPP-OneTrust PIA Platform

Simplify privacy impact assessments with this cloud-based customizable platform - free to IAPP members!

72% say privacy is now a board-level concern

Find out more about privacy governance in the IAPP-EY Annual Privacy Governance Report 2016.

Privacy Vendor List

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

IAPP Communities

Meet locally with privacy pros, dive deep into specialized topics or connect over common interests. Find your Community in KnowledgeNet Chapters, Sections and Affinity Groups.

More Resources »

Time to Get to Work at the Congress

It's almost here! Thought leadership, a thriving community and unrivaled education...the Congress prepares you for the challenges ahead. Register now!

Plan for the Summit

The world’s premier privacy conference returns with the sharpest minds, unparalleled programs and preeminent networking opportunities. Registration opens December 19!

Intensive Education at the Practical Privacy Series

This year's Series spotlights Data Breach, FTC and Consumer Privacy, GDPR and Government privacy issues. It’s the education you need NOW. Early bird ends Nov. 4!

Speak at the Symposium

The call for speakers is open! The Symposium returns to Toronto this Spring and programming is now underway. Looking to share your privacy prowess? Submit by November 20!

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»