YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← 07-12 Oblivious Transfer

Get Embed Code
1 Language

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

  1. What we need is something called oblivious transfer, and in particular,
  2. we need what we'll call "one-out-of-two oblivious transfer"
  3. and what that means is Alice can create two values, X0 and X1.
  4. Bob will obtain one of those values, but Alice doesn't learn which one Bob learned.
  5. Bob can only obtain one of the two values but Alice doesn't know which one Bob obtained.
  6. There are lots of different protocols that provide this.
  7. The one I'm going to describe was invented by Even, Goldreich, and Lempel in 1985.
  8. It builds on RSA encryption and we're going to look at it
  9. as we need to use it in the garbled circuit protocol.
  10. Our goal is that Alice has two wire labels; this correspond to the inputs to some gate,
  11. and she wants to transfer one of them to Bob without revealing the other one.
  12. We're going to use Alice's public key.
  13. We'll assume that is known to Bob before the protocol starts.
  14. Our goal is to transfer one of these two wire labels to Bob.
  15. The first step is to create two random values.
  16. These are separate from the wire labels. These are going to be transferred to Bob.
  17. These have no meaning. They're just two random nonces created by Alice.
  18. Depending on which wire label Bob wants, Bob has some input either zero or one.
  19. He's going to pick either the first or the second of these. So, he is going to pick Xb.
  20. Is it equal to either X0 or X1, depending on his value of b.
  21. Then Bob will pick some random value r. Bob is going to use this to blind the response.
  22. He can allow Alice to learn whether he pick X0 or X1. That would reveal his input.
  23. What he's going to do instead is use this random value to blind the response.
  24. He'll compute this new value, which is the value of the X that he selected
  25. plus the random value raised to that public exponent modn.
  26. We're going to hide the value of Xb by adding a random value raised to the e power to it.
  27. That value is what sent back to Alice, and Alice is going to perform two different RSA decryptions.
  28. She knows the values that she selected for X0 and X1.
  29. She's going to subtract each of those from V.
  30. She'll decrypt it using her private key and we'll call the first one K0,
  31. that was the one constructed using X0, and the second one, K1,
  32. that was the one constructed using X1.
  33. The question is if b selected, what is it's input?
  34. That means b has the value for Xb is equal to X1.
  35. What are the values of K0 and K1? Select the best answer for each choice.
  36. It could be meaningless, it could match X0, X1, or r.