New Fully Homomorphic Encryption Library

The idea of an homomorphic encryption scheme is not a new one.

Already one year after the introduction of RSA (the first public key encryption scheme discovered by the scientific community) it was noticed that RSA had the special property that if you multiply two ciphertexts together, then the resulting value would be a valid encryption of the product of the original plaintexts! In other words, by manipulating the ciphertexts (the random looking strings containing your data) you are manipulating in a meaningful way the content of the encryptions.

A “fully” homomorphic encryption scheme

As said, even RSA allows the user to perform multiplication directly in the encrypted domain. Other cryptosystems allow to perform additions in the encrypted domains. But for more than 30 years, we did not know how to construct a scheme that allows users to compute any function of encrypted values. That’s why Gentry’s breakthrough in 2009 has generated so much noise, even outside of the scientific community (e.g., Forbes, Business WeekForbes again).

Among other things, a fully homomorphic encryption (FHE) scheme allows to perform non-interactive secure computation, and in many applications this is crucial. The classic example is cloud computing: if you don’t trust your cloud provider with your data, you are in trouble: either you have to give away your private data in clear (running the risk that the cloud provider looks into possibly confidential data), or you have to encrypt the data before uploading it (losing the advantages of having the cloud computing for you). Another example is encrypted a spam filter: you like that your mailbox is not filled with junk, but you might not be happy about Google/Microsoft/etc. reading the contents of all your emails.

But if you encrypt your data with an FHE scheme, the cloud can compute on your data without looking at it!

Wow! When can I start using FHE?

The first scheme proposed by Gentry was insanely inefficient, and many did not believe we would see a working implementation of an FHE scheme for a long time. Fortunately, there are a lot of smart cryptographers around and in the last 4 years the efficiency of FHE schemes has been improved by several orders of magnitude.

To be concrete, in 2010 the available FHE schemes were so inefficient that they would simply not run on any hardware. At Crypto 2012 Gentry Halevi and Smart showed that it “only” takes 36 hours to evaluate AES in the encrypted domain. After one year this can already be done in under 3 hours! (If interaction is not a problem for your application, you could perform the same task using garbled circuits/oblivious transfer/etc. in a few seconds instead.)

HELib

The last result was obtained using a new library, recently released under GPL license by Shai Halevi and Victor Shoup. From the author announcement:

At long last, Victor Shoup and myself finally open-sourced (under GPL)
the HE library that we have been working on for the last year and
something. I created a project for this library on github, see

https://github.com/shaih/HElib

At this point, the documentation of this library is rather thin. You can
find a design-document under the doc sub-directory, and most modules
include fairly extensive comments in the source code itself, but that’s
pretty much it.

[…]

To get an idea for the performance of this library, I attach a short
excerpt from a presentation that I gave a few months ago. We should
probably be some 25% faster now than we were back then, but this gives
the right ballpark estimate.

We would very much appreciate comments, and would be even happier
if any of you wants to join us in developing this library.

— Victor & Shai

There is still a long way before you can start using FHE for your everyday problem, but these improvements are amazing and we should be grateful to Shai and Victor for making their work public.

Links

Secure Supply Chain Collaboration

This blog post aims to highlight a promising application of secure (multi-party) computation in business software.

Let me first summarize my view of the technical requirements and accomplishments of secure computation. If multiple parties have inputs (requirement A) and these inputs must be kept highly confidential (requirement B), then they can still safely collaborate (accomplishment A). There is a scenario in business operations where these requirements are met and the accomplishment is useful. In fact, the data is so sensitive that collaboration often does not take place in practice because of security concerns. In that way secure computation is an enabler of additional collaborations not practical previously. This scenario is supply chain collaboration (SCC).

What is the fundamental problem of SCC?

Companies produce goods and services (either to order from customers or to a planned stock level). For this they need to order supplies. The current process is as follows: A company determines how much it wants to produce, checks its supply and inventory and then places orders to its suppliers. This simple process proceeds all the way to the top of the supply chain where raw materials are sourced.

What is the fundamental problem with this approach?

It is long known that this mode of operation does not lead to an optimal use of resources. Each companies optimizes (locally) its use of capacity and stock, but the combination of locally optimal plans is rarely a globally optimal plan. In the entire supply chain significant resources are wasted which implies higher costs for consumers. You might have heard of the bull whip effect. The bull whip effect states that is inevitable in this mode of operation that the fluctuation of orders at the top of the supply is much higher than at the bottom of the supply chain. This implies that companies at the top of the supply chain need to maintain much larger capacities which binds capital and incurs significant additional costs.

What can you do to prevent the problem?

Companies along the supply chain need to exchange data. They need to engage in a collaborative planning process. Supply chain management has come up with a variety of such planning methods. They differ in the number of participating parties — two or many — and in the economic quantity to be optimized. A large scale example with multiple parties that optimizes production, warehousing and transportation is supply chain master planning. A medium scale example with two parties that optimizes production and warehousing is collaborative planning, forecasting and replenishment (known as CPFR). A small scale example that optimizes warehousing is the joint economic lot size (JELS).

How can secure computation help?

A common problem in SCC is that partners at not willing to exchange the necessary data, such as costs and capacities, for security reasons. They fear disadvantages in future collaborations, e.g. price negotiations, due to the insight into their price calculation. This is even often true for simple data exchanges, such as in vendor managed inventory. Therefore few of these schemes have found practical adoption so far. Supply chain researcher have come up with their own solutions, e.g. by using negotiation. Yet, these techniques rarely withstand a rigorous security analysis. Secure computation can implement these planning techniques provably without disclosing the input data. Hence, it may just be the technology that makes them acceptable in business practice.

What is the state of the art?

A number of specialized secure computation protocols have been proposed. The first one that initiated the idea was for CPFR (Atallah et al., 2006, M&SOM). A couple others came later, e.g. Pibernik et al. (2011, EJOR), address the problem of inference from the result of a secure computation of JELS. Even an attempt at something like supply chain master planning was undertaken (Kerschbaum et al., 2011, Computer). And, there are more and even more coming. Still, there are a couple of challenges left: First, as always, increasing the performance is a key challenge. Second, identifying the right computation (planning algorithm) to perform and the right computation model (cloud, etc.) to perform it in can be important for adoption in the market. This, of course, has an impact on which protocols are the fastest. Third, all aspects of security, such as malicious inputs or inferences from the result, etc., need to be addressed.

In summary, supply chain collaboration presents a major opportunity for wider adoption of secure computation due to its high confidentiality requirements. There are a number of challenges to be solved by the cryptography and business community and only their collaboration is likely to bring practically viable results.

Florian Kerschbaum

florian dot kerschbaum (at) sap dot com

Using Secure Computation to Avoid Satellite Collisions

If you follow this blog, you probably already know that MPC allows a set of parties to compute any function of their inputs without compromising the privacy of their data.

The number of real world situations where MPC can be used to solve apparently unsolvable problems is only limited by our imagination, as this recent video from the Estonian team behind the Sharemind project shows:

If you can’t watch the video, here is a short summary: the growing number of satellites orbiting the planet is increasing the danger of collisions. This is not only a theoretical scenario, and two satellites actually crashed in 2009. This could be avoided by sharing (exact) information about the satellites orbits. However, satellite owners are not willing to make the orbits of their satellites public.  But using MPC, the parties can cooperate and learn whether a collision is going to happen and nothing else!

More information can be found the Sharemind’s blog. If you want to know more about secure computation techniques you can visit the MPC Lounge (currently under construction).