Return to Video

07-12 Oblivious Transfer

  • 0:00 - 0:04
    What we need is something called oblivious transfer, and in particular,
  • 0:04 - 0:07
    we need what we'll call "one-out-of-two oblivious transfer"
  • 0:07 - 0:11
    and what that means is Alice can create two values, X0 and X1.
  • 0:11 - 0:16
    Bob will obtain one of those values, but Alice doesn't learn which one Bob learned.
  • 0:16 - 0:21
    Bob can only obtain one of the two values but Alice doesn't know which one Bob obtained.
  • 0:21 - 0:23
    There are lots of different protocols that provide this.
  • 0:23 - 0:28
    The one I'm going to describe was invented by Even, Goldreich, and Lempel in 1985.
  • 0:28 - 0:31
    It builds on RSA encryption and we're going to look at it
  • 0:31 - 0:34
    as we need to use it in the garbled circuit protocol.
  • 0:34 - 0:40
    Our goal is that Alice has two wire labels; this correspond to the inputs to some gate,
  • 0:40 - 0:45
    and she wants to transfer one of them to Bob without revealing the other one.
  • 0:45 - 0:47
    We're going to use Alice's public key.
  • 0:47 - 0:50
    We'll assume that is known to Bob before the protocol starts.
  • 0:50 - 0:55
    Our goal is to transfer one of these two wire labels to Bob.
  • 0:55 - 0:57
    The first step is to create two random values.
  • 0:57 - 1:01
    These are separate from the wire labels. These are going to be transferred to Bob.
  • 1:01 - 1:05
    These have no meaning. They're just two random nonces created by Alice.
  • 1:05 - 1:10
    Depending on which wire label Bob wants, Bob has some input either zero or one.
  • 1:10 - 1:15
    He's going to pick either the first or the second of these. So, he is going to pick Xb.
  • 1:15 - 1:21
    Is it equal to either X0 or X1, depending on his value of b.
  • 1:21 - 1:26
    Then Bob will pick some random value r. Bob is going to use this to blind the response.
  • 1:26 - 1:32
    He can allow Alice to learn whether he pick X0 or X1. That would reveal his input.
  • 1:32 - 1:35
    What he's going to do instead is use this random value to blind the response.
  • 1:35 - 1:41
    He'll compute this new value, which is the value of the X that he selected
  • 1:41 - 1:46
    plus the random value raised to that public exponent modn.
  • 1:46 - 1:52
    We're going to hide the value of Xb by adding a random value raised to the e power to it.
  • 1:52 - 1:58
    That value is what sent back to Alice, and Alice is going to perform two different RSA decryptions.
  • 1:58 - 2:01
    She knows the values that she selected for X0 and X1.
  • 2:01 - 2:04
    She's going to subtract each of those from V.
  • 2:04 - 2:08
    She'll decrypt it using her private key and we'll call the first one K0,
  • 2:08 - 2:11
    that was the one constructed using X0, and the second one, K1,
  • 2:11 - 2:14
    that was the one constructed using X1.
  • 2:14 - 2:18
    The question is if b selected, what is it's input?
  • 2:18 - 2:21
    That means b has the value for Xb is equal to X1.
  • 2:21 - 2:27
    What are the values of K0 and K1? Select the best answer for each choice.
  • 2:27 -
    It could be meaningless, it could match X0, X1, or r.
Tytuł:
07-12 Oblivious Transfer
Team:
Udacity
Projekt:
CS387 - Applied Cryptography
Duration:
02:32
Amara Bot added a translation

English subtitles

Revisions