Tweet

Vote on Hacker News

August 3, 2014

January 19, 2014

November 14, 2013

August 5, 2013

May 5, 2013

May 4, 2013

March 17, 2013

<-- back### Secure Distributed CSP - secure scheduling using homomorphic encryption & constraint satisfaction & a (small) paper error - 2013-08-05 21:26:33

Before we begin, this blog post is based on a 2004 paper called "Secure distributed constraint satisfaction: reaching agreement without revealing private information" by Makoto Yokoo, Koutarou Suzuki & Katsutoshi Hirayama. I found this paper to be brilliant, but extremely difficult to read and rather confusing, so I decided to create this blog post as a resource for anybody hoping to understand this paper. I also believe I have identified an error/oversight contained in this paper (see step 5). Paper link: http://www.sciencedirect.com/science/article/pii/S0004370204001547

To understand this, we first have to define three ideas:

1) Constraint Satisfaction Problem: Given a set of arbitrary constraints, find a solution to a problem which satisfies these constraints. This can be a Sudoku puzzle, the 8 queens problem etc. We are going to define this here as a scheduling problem where a series of users have constraints in the form of existing calendar entries.

For further reading - http://en.wikipedia.org/wiki/Constraint_satisfaction_problem

2) Homomorphic Encryption: When a operation (such as addition) is applied to the encrypted version of several values (ie. E(X) + E(Y) = E(Z)), the decrypted result is the same as the result if the operation was applied to the plaintext (ie. D(E(Z)) = D(E(X)) + D(E(Y))). Note: E = encryption function, D = decryption function

For futher reading: http://en.wikipedia.org/wiki/Homomorphic_encryption

3) ElGamal Encryption: ElGamal is a public key crypto algorithm. Input X and a random number r produce an encrypted pair E(x,y) based on a public key {p,t,B} and can then be decrypted using a private key. This encrypted pair is multiplicatively homomorphic.

For futher reading: http://en.wikipedia.org/wiki/ElGamal_encryption

The problem

We have a group of people who are attempting to schedule a meeting. However, they are all competitors. They can't share there schedules or busyness, or else they might gain some sort of competitive edge. They still need to plan this meeting.

Defining the problem a bit more formally

Each person is going to have a series of unary constraints in this CSP problem. This problem must be solved without sharing the unary constraints with any other person or server.

Step one- defining binary constraint matrix and define a server

Each user is going to define a binary constraint matrix between themself and each other user (using ONLY their own unary constraints). What the matrix below says is that this user can only meet with the other users at times x,r,q,p. This matrix is sparse (in the non-formal-mathematical sense) and can only contain information along the axis as users can only meet at the same time.

We are also going to define a server that issues an ElGamal public key.

Step two- modify the matrix

We are now going to do something strange. This is the first step towards using ElGamal. We are going convert all of the 0's into a random number > 1 (that has certain co-prime properties to the public key, for now, lets just say 3 and 5).

Step three- encrypt

We are going to encrypt each entry in the matrix using ElGamal encryption with the public key of the server (using a different random r value for each entry in the BC. The matrix below is split into two, but this should be viewed as 1 matrix which two values at each entry, ie. (y1,y2)).

Step four- share

Now that each users binary matrix has been encrypted, these can be shared between all users. We are now going to go through and multiply each pair of binary matrices together (this is where it is important that ElGamal is homomorphic). Image credit - right side is directly from the paper itself.

Step five- permutation

We now have a series of encrypted BC matrices that are common knowledge between all users. However, if we just sent these to the servers, the server would know our meeting time after decrypting!

Therefore, we must permute each multiplied matrix (by the same permutation for rows and columns! - the paper specifies a different column/row permutation which doesn't work for >2 users. Once the server decrypts this information later the definition of a column/row must stay consistent because with 3 or more users, you can't have a single user always ends up on the same row/column edge. I view this as an error with the paper section 4.3. It is also entirely possible that this isn't an error & I am missing something.).

Step six- send to server

The server now recieves a series of permutated encrypted matrices. It can (with it's private key) decrypt these matrices and then remove the >1/1 convention that we applied during step 2.

D(E(1)xE(1))=D(E(1)) due to the muliplicative homomorphic property of ElGamal, therefore the server knows which schedule works for both users, however, because all the users permuted their matrix, the server does not know which time slot actually works, only that one does.

step seven- solve the CSP

This step is much more straightforward. Because the server now has a series of matrices between all users, it can find the one time slot that works for everyone (This should be a relatively simple CSP to solve). It can then return this value to all users who know the permutation match for that time slot and therefore have a scheduled meeting!

Conclusion

What we did here was demonstrate a way that, using a server, users can safely schedule meetings without their colleagues having knowledge of their schedules (aka unary constraints) by utilizing the multiplicative homomorphic property of the ElGamal algorithm.

Information leakage

-If a single user and the server colludes in this implementation, it could gain information about other users.

-The server does know the "busy-ness" of a pair of users and can use that to to gain information about a specific user.

Taking this further

The paper talks further about having a layer in between the CSP solver(server) and users called "decryptors" that only provides partial solutions to the server, but if multiple decryptors collude, you can still get the full solution, so at some point, you have to trust the server you are sending the data to (which is why I did not include that information here... also I didn't understand it that well myself).

Code

I can share the C code that I used in the class that this project was written for, but out of respect for this class and future students, I will only share it on request... also it was written for a CS class, so don't expect any quality/scalability :)

PDF Presentation

Link to PDF presentation

(The "not recommended reading" slide in the PDF referred to the paper being moderately difficult to read/understand)

The views expressed here are strictly my own. © 2007-2015 Sam Erb