## 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.
Title:
07-12 Oblivious Transfer
Team:
Udacity
Project:
CS387 - Applied Cryptography
Duration:
02:32

• Amara Bot