Center for it-sikkerhed

Value can often be gained from combining data sources from mutually distrusting organizations. An example could be two medical companies who have databases containing different substances and their effects. The companies could gain added value from being able to query the combined database. However, combining the databases in a traditional manner where both parties or a trusted third-party learns the full content of both databases is usually unacceptable because the databases are of great value. Legal agreements can be used to put bonds on which information may be used to what purpose. However, the possibility of misuse can newer removed in this way.

Another solution is to use secure multiparty computation. Secure multiparty computation (SMC) is a cryptographic technique, where a number of parties work together to compute a function on input private to each party in such a way that no other party learns the input.

The SMC technique can be applied to database operations, and we have recently developed a demonstrator of a database based on SMC. The demonstrator allows two parties Alice and Bob to create their own private database table, and compute the values, which appears in both tables. The database operation is performed in such a way that neither Alice nor Bob learns the private table of the other party, but only which values appear in both tables.

The demonstrator is available online at:
Alice: http://46.51.178.23:8080/sdb/DBManager.html?party=A
Bob: http://46.51.178.23:8080/sdb/DBManager.html?party=B

The security comes from Alice and Bob working together to perform the database operations. Each party encrypts their private table and masks each entry by raising it to a power. They then exchange the tables and do the same again. Then they work together to decrypt the tables, and get two tables with the values masked. The intersection is computed based on these tables. Alice and Bob can now work together to remove the masking of the resulting values, and thus reveal the result. The only information revealed is the values in the intersection, and thus neither Alice nor Bob learns the entire content of the other parties private table. The SMC protocol is more precisely defined in the progress report of Claudio Orlandi available online: http://www.cs.au.dk/~orlandi/report.pdf.

Secure databases also has applications in governments and general research. Different branches of a government collect information about the citizens as part of their normal operations. This could be information about tax, treatment for decease, social services, or simply where they live. Much useful knowledge can be learned from combining this information. But combining some of the information might be illegal, because the information is not collected for that specific purpose and so the citizens have not agreed to the use.

We have built the demonstrator as a web application using GWT and Java servlets, which interacts with a PostGreSQL database. One can make the demonstrator work on any other database management system, which supports internal C functions.
There are some limitations in the current implementation. The demonstrator describes the limitations. We can remove all the limitations if we apply more work.
The demonstrator is based on research in SMC performed by the Cryptographics group at the University of Aarhus.

If you or your organization find this technology interesting, or want to learn more about it, then please contact us.