Analyzing public sector incomes on the cloud using MPC

Introduction

Following the success of deploying secure multi-party computation for a secure double auction in Denmark in 2008 and for the financial reporting of the ICT sector in Estonia in 2011, Cybernetica has developed a new MPC application together with a web-based frontend that provides statistical analysis of incomes in public sector in Estonia.

The demonstration website was originally developed for the European Cloud Partnership Steering Board meeting held in Tallinn this summer. The main goal of this webpage was to show that MPC technology is mature enough to be used in real cloud applications that operate on sensitive data. Also, a web-based interface makes it accessible and convenient for a lot of users without the need for installing special software.

We are glad to announce that we have decided to make this website a permanent demo.

Click here to see it run

Technical details

The online demonstration is built on the Sharemind secure multi-party framework that uses three computation parties. The three nodes are deployed on three virtual machines provided by three distinct cloud service providers: Amazon EC2, Windows Azure and Zone Media. All the cloud instances reside in Europe.

As the application computes only average salaries, grouped by various categories, the MPC protocols used are quite simple and are thus not the most interesting part of the demo. What makes this demonstration unique, is the fact that the MPC computation is done in real time and it is controlled by a web frontend. The web application solution builds on the ICT sector benchmark analysis application deployed in Estonia in 2011. However, this time there is no caching and the report computation is initiated directly from the web page.

Instead of embedding an HTTP server inside the Sharemind servers, we opted to use a separate HTTP server in front of each node that connects to Sharemind via its normal protocol and forwards all commands from the web.
This allows us to use existing, stable web server technologies.

Out implementation uses Node.js as the proxy server and the socket.io JavaScript library on top of that to mimic two-way WebSocket-like communication between the client’s web browser and the proxy server.

Future work

We plan to update the application to use the Sharemind application server, a newer, faster version of Sharemind with support for more protocols. Stay tuned!

“The Sharemind team” (sharemind@cyber.ee)

(The technical work was done by Reimo Rebane and Riivo Talviste at Cybernetica, with DanBogdanov supplying the vision. Thanks go out to our collaborators in STACC and the e-Governance Academy.)

Advertisements

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

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).

Crypto is Dead; Long Live Crypto!

At last week’s RSA conference, in the Cryptographer’s Panel, Adi Shamir said that we need to prepare for a post-crypto world. The same basic idea was put forward by Jonathan Zittrain in his invited talk at last years CRYPTO conference, which was entitled “The End of Crypto”. The basic idea behind both statements is that in the modern world the attacker is already inside the box, so no matter how much encryption you use the bad guy will always get your data.

Let us elaborate on this idea a bit more. In the consumer field you may use your smart phone to store all sorts of important data on it (email addresses, passwords, banking data etc), but most users also download apps. Very few of these apps have had any form of code or security review, and so could contain malicious code which can compromise your phone, and your security.

In the enterprise space the problem is even more acute. The existance of APTs (Advanced Persistant Threats) means that enterprises need to assume that the attacker is already within their perimeter. This has always been true, in that often attacks come from the inside, but now we have seen external attacks which are based on dorment code, lying in wait, within an enterprises security perimeter.

The usual cryptographic model is that there is at least one honest person in a protocol. This is still true, the user of a system may be honest, but if we cannot trust the system they are on to not be compromised, we can essentially not trust anything. What is the point of encrypting data if the attacker already has the key? Even if the data has been encrypted successfully, at some point it needs to be decrypted so as to process it. At the point of decryption, if the attacker controls the machine, he also controls the decrypted data. So with such all pervasive threats, how can crypto be of any use what-so-ever? In some sense this means “Crypto is Dead!”.

Luckily, however, cryptography is about more than just encryption and authentication. Modern cryptography gives us a number of tools which we can use to secure systems. In Bristol we have been working for a number of years in turning a theoretical technology called multi-party computation (MPC) into a practical reality. The basic idea behind MPC is the following: Suppose a set of n parties have their own secret inputs, for example party i has input xi. Now suppose they want to compute some function on these inputs say

f(x1,…,xn)

MPC allows us to do this, via a protocol, in such a way that the parties learn the output of the function, but no one learns anything about the other parties inputs. Traditional use-cases which have been proposed for MPC are the sharing of databases etc.

However, MPC also allows one to solve the problem of what hardware to trust in an enterprise environment such as that described above. In other words we can use MPC as a threat mitigation strategy to avoid APTs and other malware on our systems. We do this by altering the standard use case of MPC, instead of having multiple parties we have one party who just happens to be using multiple computers.

Suppose we expect that an attacker is inside our network. If we put in place enough protection to ensure he is not on all of our computers at once, then we may be able to hold a secret key on that uncompromised computer. But we do not know which computer is uncompromised. Using MPC we can get around this. Consider the simplified situation where we have two computers, where we know it is likely one is compromised and the other is not. We now “split” the encryption key between the two servers, for example via a one-time pad. So each party essentially has a random string, but the two parties together when combining their random string have the secret key. We treat the two random strings as the inputs x1 and x2 above, and now consider f as the encryption function. In this way the two servers can perform the encryption, without anybody ever knowing the underlying secret key itself.

We could use the same idea for messages. Instead of having one server needing to decrypt some ciphertext, with the obvious problem of what happens when the server is compromised, a combination of servers could use MPC to decrypt the ciphertext and then use MPC to process the plaintext. In this way no single party ever sees the underlying key, and the underlying plaintexts, at all.

This might seem like pie in the sky, but we can actually perform such computations today, using protocols developed in Bristol and at other places around the world. For example when we first implemented the AES functionality in a covertly secure manner back in 2009 we could evaluate a single AES block encryption between two partes in 60 seconds. Now this can take as little at 0.012 seconds, and we can process around 1000 such encryptions per second. With these latencies and throughputs we can actually implement solutions which help mitigate against the problem of servers being compromised by APTs.

Of course MPC only acts as a threat mitigation defence in such situations. If all machines are compromised, then all bets are off. But that is the same as with all security mechanisms, one needs to combine them together to provide a secure system. But the key message is that with MPC one no longer needs to place ones secrets all in one place. So whilst the traditional cryptographic model may be dead in the modern world, the application of cryptography to address security problems is far from dead. So Long Live Crypto!

This post originaly appeared on the BristolCrypto blog.