English subtitles

← 07-10 Garbled Circuit Protocol

Get Embed Code
1 Language

Showing Revision 1 created 10/24/2012 by Amara Bot.

  1. Here's how this works as a protocol--we have two participants.
  2. We'll call Alice the generator--that means she is going to make the circuit,
  3. and Bob the evaluator--that means he's going to evaluate the circuit.
  4. At the beginning of the protocol, they've agreed on some circuit they want to evaluate.
  5. For this to be interesting would be much larger than that.
  6. It takes inputs from both Bob and from Alice.
  7. Alice is going to generate a garble table for each one of these logic gates in the circuit,
  8. and send the garbled circuit to Bob.
  9. She is also going to send her input values, but because they're
  10. random nonces Bob can't tell what they mean.
  11. Bob's going to evaluate the circuit using the garbled circuit protocol
  12. decrypting one entry from each of these.
  13. At the end of this, Bob's going to get some output values.
  14. Then they're going to do something to turn that into the semantic value,
  15. which possibly Bob receives, possibly Alice receives.
  16. We can design the protocol either way.
  17. I am not going to talk about that final step of how you turn the encrypted values
  18. at the end of the circuit into meaningful values.
  19. We'll leave that as a question for your exam.
  20. But there is one more question that I do need to talk about.
  21. That's the question of how does Bob obtain his inputs to the circuit.
  22. To evaluate these tables, Bob needs to have both Alice's inputs and his inputs.
  23. Here are the choices. Bob could generate them himself.
  24. He could ask Alice to provide his inputs.
  25. He could ask Alice for both possible values for all these wire labels,
  26. and then select the right one corresponding to his inputs.
  27. Or none of these possibilities actually work.