4
$\begingroup$

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?

$\endgroup$

migrated from security.stackexchange.com Mar 30 '16 at 15:38

This question came from our site for information security professionals.

  • 3
    $\begingroup$ Did you consider this paper, which is a lot more recent than Yao's? Side note: this might be a better fit at crypto.SE $\endgroup$ – Tobi Nary Mar 30 '16 at 11:30
  • $\begingroup$ That seems like a very good paper. At this point, I have invested a fair amount of my time into garbled circuits and am hoping to go down that route. However, if in the future I find implementing a scheme using garbled circuits untenable I will probably start at this paper. $\endgroup$ – Rhyzomatic Mar 30 '16 at 14:53
  • 2
    $\begingroup$ @SmokeDispenser Garbled circuits are much better suited for two-party computation tasks than GKN. $\endgroup$ – Yehuda Lindell Mar 30 '16 at 16:21
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, my mistake is perfectly obvious now that you've pointed it out. I am actually looking at voting schemes which are more complicated than just for or against, but that doesn't mean that I can't use homomorphic encryption. The paper that @SmokeDispenser mentioned looks like a good start. Considering that I know little about crypto and reading through papers is tough, do you have any other recommendations for papers that are on the simpler or notation-light side of things? $\endgroup$ – Rhyzomatic Mar 30 '16 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.