Have I made any glaring mistakes in my use of Yao's garbled circuits?

Question

I would like to use garbled circuits to provide a service that allows people to vote where they do not need to reveal their votes to my server or to anyone else. Let's assume that I have secure ways to generate garbled circuits, perform oblivious transfer for the inputs, and to evaluate the circuits. Let's also assume that every person who will vote has a login to my service, that they have a working public/private keypair, and that the server has a copy of their public key. I will use this because in this scenario voters won't be able to easily connect to each other, and must communicate through the server.

This is just for a school project/my own interest. I will be very clearly advertising that the project was not done by security experts.

This is how I have envisioned the general flow of information:

1. The server, knowing the number of voters and having the ids of all the voters (as in, their logins to the service), crafts a garbled circuit which will compute the outcome of the vote.

2. The server gives this circuit to every voter, as well as the public keys of every other voter that will be participating.

3. Every voter retrieves their input from the server using oblivious transfer.

4. Each voter then encrypts their input with the public keys of every other voter. They then send their encrypted input back to the server.

5. The server then distributes every voter's input to every voter by giving them the version encrypted with the receiving voter's public key.

6. Every voter decrypts the others' inputs with their private key.

7. Every voter evaluates the garbled circuit.

8. Voters send the output of the circuit to the server.

9. If the server notices any of the outputs are different, it broadcasts that the vote is bad. Otherwise, it broadcasts the outcome of the vote.

10. Each voter checks that the broadcasted outcome is the same as the outcome they computed.

Have I missed anything obvious here? Do you see any ways to make it more efficient?

Answer 1

Unfortunately, the answer to your question is yes. You have made glaring mistakes. In particular, Yao's garbled circuits are suited for two-party computation only, and here you wish to carry out a multiparty computation. One huge problem that arises with your entire approach is that if the server colludes with one of the voters, then they can learn the inputs of all of the parties. (I haven't looked at all the fine details of the way you propose working, since this inherent problem arises at the onset.)

There is a protocol that generalizes Yao garbled circuits to the multiparty setting; it is called BMR. However, it is less mature and harder to implement.

If you wish to do a simple voting protocol with people voting just for and against, and you wish to just know how many voted in favor, then using an additively homomorphic encryption scheme like Paillier is the way to go. However, like everything in cryptography, it is very hard to get this right if you try to design it yourself. You should look at papers on voting protocols and then choose one of them to implement.

Alternatively, if it's for a school project, then think of a two-party application that is interesting and use garbled circuits.