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

IAPP Westin Research Center

Original works. Groundbreaking research. Emerging scholars.

Advertise in IAPP Publications

Find out how to get your message in front the people you want to reach. Download a media kit now.

Get more News »

Find a KnowledgeNet Chapter Near You

Network and talk privacy at IAPP KnowledgeNet meetings, taking place worldwide.

Women Leading Privacy

Events, volunteer opportunities and more designed to help you give and get career support and expand your network.

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.

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.

New Web Conferences Added!

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

Train Your Staff

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

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 Close-up

Looking for tools and info on a hot topic? Our close-up pages organize it for you in one easy-to-find place.

Where's Your DPA?

Our interactive DPA locator helps you find data protection authorities and summary of law by country.

IAPP Westin Research Center

See the latest original research from the IAPP Westin fellows.

Looking for Certification Study Resources?

Find out what you need to prepare for your exams

More Resources »

GDPR Comprehensive: Registration Open

New! Intensive two-day GDPR training led by the sharpest minds in the field. It's a can't-miss event.

The Congress Is Cancelled

The IAPP Europe Data Protection Congress 2015 is cancelled. Click through to learn more.

Sponsor an Event

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

Exhibit at an Event

Put your brand in front of the largest gatherings of privacy pros in the world. Learn more.

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»