Oblivious Transfer - Computerphile

Рет қаралды 52,439

7 ай бұрын

Share part of a secret without knowing which part? Dr Tim Muller explains how Oblivious Transfer works.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharanblog.com
Thank you to Jane Street for their support of this channel. Learn more: www.janestreet.com

Пікірлер: 106

@cmilkau 7 ай бұрын

Errata: m'_1 = m_1 + k m* = m'_b - k m* = m_1 + k - k It's not hard to figure this out but neither is it hard to insert this during editing rather than confusing people.

@Nerothe42 7 ай бұрын

At 14:30 when he was mentioning that the message cannot be longer than the key (1024 bit) he made the (minor) mistake of then concluding the message could not be longer than 1KB - this should be 128 bytes instead 😛 for anyone wondering, the exact max length message in RSA would be 117 bytes because of 11 bytes of padding. But nitpicking aside, thank you for the awesome explanation of this protocol! :)

@ladnir 6 ай бұрын

You can use bigger rsa if you want. Or more typically, the ot is used to derive a key which is then used to encrypt an arbitrary length messaging.

@jonglass458 7 ай бұрын

If Alice deliberately mis-calculates p0 and Bob doesn't complain, then she'd know Bob was interested in m1. Is there a way for Bob to verify both p0 and p1 are correct before decrypting m1?

@snickers10m 7 ай бұрын

Awesome question! Sounds like a research topic!

@Gvozd111 7 ай бұрын

WARNING! NOT CORRECT (see replies below) Bob cab check this using Alice’s public key. Essentially he can “decrypt” both p0 and p1

@gazehound 7 ай бұрын

p0 and p1 were encrypted with Alice's private key, which means Bob can decrypt them since he knows Alice's public key. Bob also knows V, x0, and x1, so he can then perform the calculation himself to verify that both are correct.

@gazehound 7 ай бұрын

@@snickers10mNo research paper needed 😁

@snickers10m 7 ай бұрын

@Gvozd111 @gazehound Don't think this is that easy! Bob does not have direct access to the value of p0 or p1 -- only indirect access through m'0 and m'1. Assuming Bob asked for b=1, he doesn't know p0 in order to decrypt it with e If Bob knew p0 and p1, he could calculate both m0 and m1, defeating the point of the algorithm

@rosuav 7 ай бұрын

15:49 Yep. Programmers ALWAYS start by calling something "foo".

@mr.incognito9100 7 ай бұрын

How do you use this for the example problem at the beginning? Seems like I'm missing something

@snickers10m 7 ай бұрын

19:03 It sounds like we'll learn in a part 2 video! He said he wants to show us how this turns into "garbled circuits", which lets us run any algorithm without revealing the inputs. It sounds like that would solve the "find the most money" problem from the intro!

@yoyofargo 7 ай бұрын

Would love if you guys covered how input shaping works. It’s used for stabilizing 3d printers and cranes to stop oscillation/resonances and is simple enough to run on embedded systems.

@alexgravenor 7 ай бұрын

I hope there’s a follow up coming on Garbled Circuits. One of the more interesting things I’ve heard of in a while!

@gianluca.g 7 ай бұрын

One interesting application is online gambling: Alice presents a shuffled deck of cards to Bob, and Bob select and look at one card without knowing all the others. Meanwhile, Alice doesn't know which card Bob have seen.

@heinenrby7600 7 ай бұрын

Love learning about stuff like this, and diffie-hellman key exchange and Zero-knowledge proofs! Really opens the mind that some things that seem impossible are actually not!

@poopsmcgee69 7 ай бұрын

Can anyone explain a real world use case for something like this? Maybe i missed something, but i dont get how this pertains to the dinner check problem at the beginning of the video.

@dylankrejci9965 7 ай бұрын

In the example provided, the idea is that everyone at the table wants to know who has the most money, without knowing how much money everyone else has. You can imagine the algorithm as a third party who knows everyone’s wealth and tells everyone who has the most.

@ladnir 6 ай бұрын

OT is at the heart of a field called secure multiparty Computation. You can Google it but the idea is that it allows you to run an encrypted program between several parties. The parties learn nothing about the inputs to the program except the final answer. For example, say I want to train a machines learning model on data from two hospitals. Due to privacy concerns, the hospitals are unable to share the data. However, they both want to learn this model and don't think learning this model itself would be a privacy concern. They can use (many) OT to encrypt their inputs and then train an encrypted model. This model can then be decrypted. Google "secure ml" or "privacy preserving machine learning" for more details. Many other applications exist.

@poopsmcgee69 6 ай бұрын

@@dylankrejci9965I dont get why you'd need to do oblivious transfer for that... the "third party" would just collect everyone's account information, compare them, then print the result of who has the most, right?

@orngjce223 Ай бұрын

A real world use case for this could be for an online card game, where one computer has the whole list of cards but another computer only needs to select, say, five of them. The first computer _doesn't_ have to know _which_ cards the second computer selected, they just send the list and the second computer only gets some of them.

@azrobbins01 7 ай бұрын

Espresso machine right on your desk! Nice!

@nekojibril 7 ай бұрын

If m11 = m1 + p1, and p1 = k, then why is the next step after substituting k for p1: m11 = m1 - k? Shouldnt it be m1 + k? I am probably missing something important here :/ 12:53

@ph1ber 7 ай бұрын

No, you're right. Also, his definition of m* is wrong, it should just be m'_b - k, without the additional "+ p_b".

@sanchopanza9907 7 ай бұрын

When he writes m* = mb' - k + pb I think he means m* = mb' - k. Then you get m* = (mb + pb) - k = (mb + k) - k = mb.

@calvincrady 7 ай бұрын

Does this protocol work for values of n besides powers of 2 if you want each message to have an equal chance of being read? I imagine that if Alice can make it more likely for Bob to read one message over another, that'd break some of the use cases of the protocol. I was expecting the 1-n solution to be the same protocol but with n messages instead of just 2; so e.g. 1-3 would have x0, x1, x2, p0, p1, p2, etc. Is there any reason that wouldn't work?

@Faladrin 7 ай бұрын

The size of n isn't really a factor for that. The size of n affects two things: the level of security you have and the maximum size of a message you can send. The security is affected because n is a composite of two large primes and the harder it is to find those two primes the better your security. N could be 15 which is 5*3, but that might be too easy to figure out. N affects the size because of the use of modulo. The message cannot be bigger than N because if it is when you do any of the modulo arithmetic you will lose some portion of the message that was bigger than N. (i.e. 5 modulo 3 is 2, and nothing you ever do can ever get 5 back out of a modulo 3 operation, so if your n is 3 then your message can only be 0, 1 or 2.)

@leoschafer5172 7 ай бұрын

You send n messages and pick the next largest power of two. You can pretend that the other (empty) messages are random. Bob knows that only the first n messages contain something. So he can (with equal probability) choose one of these. He now knows which keys he needs for this and can request them. They key is that bob can choose what he wants. That means as long as he chooses one of the first n key combinations randomly everything works. Of course bob can still choose a combination that is useless on purpose (say for the n+1st message).

@gustafsundberg 7 ай бұрын

If I have to go to a desert island, I would bring the mod operator

@ed.puckett 7 ай бұрын

[9:24] How does Bob know pb when calculating m*? [Oh, pb is k] [12:37] m'1 = m1 + k, not m1 - k. I can see how this works but the description does not work out algebraically. I think m* should be defined as: m* = m'b - k Regardless, thank you for the video, I learned something new!

@gazehound 7 ай бұрын

Yes, he got the definition wrong unfortunately.

@Primalmoon 7 ай бұрын

16:00 Hmm, this notation is quite a lot of squiggly lines next to other squiggles, how does he keep it straight?

@freman 7 ай бұрын

the principal is fascinating but the application is confusing... if you have 4 bits of information and only one of them is valid and I want a valid bit of information and don't know which is valid... I'm probably going to end up with invalid information... I can understand say I stored something with you, I sent you 3 random bits of junk and something important and when I make a request I get all 4 back... but that doesn't scale and for auditing/logging you'd know I was constantly requesting those 4 bits of information so an actor would only need to start there.

@professorpwerrel 7 ай бұрын

Yeah I can't imagine how well this scales due to the amount of irrelevant information also received. Like, in an extreme case are you going to download 2TB to get access to your 1GB of data, all in the name of preventing the sending party knowing which data you're interested in?

@ladnir 6 ай бұрын

So the applications of ot are numerous. You can use it to compute "encrypted programs". This is called secure multiparty Computation. In this case we typically do millions or billions of OTs, each with a 1 bit message. Typically we don't use it to download 1TB or the other.

@Amonimus 7 ай бұрын

Let me get this straight, when Bob picks value (1 of n), he receives the value of m1 as well as undecipherable large derivatives of m2 up to n?

@ph1ber 7 ай бұрын

Yes, since Alice is not allowed to know which of the n possible messages Bob decided on, she always has to send (versions of) all of them in this particular protocol.

@Amonimus 7 ай бұрын

@@ph1ber Alright. Though while secure, this sounds extremely redundant. If Bob requests 1000 blocks one by one, Alice will have to send 1000000 blocks, 999000 of which would be unreadable and also duplicating.

@Faladrin 7 ай бұрын

@@Amonimus If Alice sends 1000 X's, Bob sends back a single V. Alice must then send back another 1000, m'. Bob can only read 1 of those. You seem to have the scaling wrong.

@Amonimus 7 ай бұрын

@@Faladrin 1:1000, For 1000 X and 1000 V it would be 1000000 m, no?

@snickers10m 7 ай бұрын

@@Amonimus Your scaling is correct: 1000 separate 1-in-1000 transfers results in 1000*1000 m' values sent in total. (GOT from my previous comment helps reduce this by combining the 1000 separate transfers into one). Although keep in mind that the power-of-2 approach used at 17:30 can be used to reduce the number of m' values sent per transfer below 1000. A 1-in-1000 transfer only needs to send 10 pairs of symmetric keys (because 2^10=1024). Edit: actually, nevermind on that last part. That would require the same symmetric keys in every transfer, which has its own security issues.

@doktormozg 7 ай бұрын

Good stuff

@kompetop 7 ай бұрын

we are impressed

@igson 7 ай бұрын

Have you guys changed the camera recently? I have noticed a lot of wobble for example when filming Dr. Muller and am getting motion sickness from watching the videos.

@brandonhouse7446 2 ай бұрын

I feel like this could be used to make for a much more interesting game of Clue.

@DJClintB 7 ай бұрын

Yeh that’s all great but you didn’t explain why it’s useful and how the money reveal problem at the start is solved by what you explained lol

@subliminalvibes 7 ай бұрын

I'm so pleased I'm not going crazy. I even rewatched it in case I'd missed something! LoL

@gianlucalocri 7 ай бұрын

But Alice know that either p0 or p1 is equal to k. So Alice can try to perform Xn+k^e using in turn X0,X1 as Xn and p0,p1 as k. Only one of these 4 possibility will result in V. So Alice can easily know b. What I'm missing?

@snickers10m 7 ай бұрын

Incorrect; both result in V, and Alice learns nothing from these calculations. Suppose b=1, so V=x1+k^e. As you propose, Alice first calculates x0+p0^e = x0+((V-x0)^d)^e = x0+V-x0 = V But also Alice calculates x1+p1^e = x1+((V-x1)^d)^e = x1+V-x1 = V I don't think Alice can learn b or k from manipulating V.

@kylelynch5425 7 ай бұрын

Is this used in zero-knowledge rollups at all?

@misterhat5823 7 ай бұрын

I got zero knowledge from it.

@scaredyfish 7 ай бұрын

Can you explain this in terms of some coloured liquids?

@javen9693 7 ай бұрын

the pee pee algorithm

@77dreimaldie0 7 ай бұрын

Why does b need to be a bit? Couldn't we do the same math with b in {1...n}, m1...mn, and X1...Xn?

@snickers10m 7 ай бұрын

What you propose would work (a single oblivious transfer of n files). He skips to the optimized version of your idea at 15:19, by using bit encoding to reduce the number of transfers needed. In your approach, to send n=1024 files, you need to oblivious transfer 1024 different symmetric keys (one for each file). In his approach, he only transfers 10 pairs of keys (20 keys), taking advantage of 1024=2^10. Your idea works, but his is more optimized.

@77dreimaldie0 7 ай бұрын

@@snickers10m Thanks! I did watch that far but did not realize how much more efficient the more complicated method is

@snickers10m 7 ай бұрын

@@77dreimaldie0 To be fair to your idea... sending 10 pairs of symmetric keys isn't *much* more efficient in terms of communication cost since you have to send all 1024 encrypted files anyways as well. (keys are probably much smaller than the files)

@CD4017BE 7 ай бұрын

@@snickers10mI think it is not so much about optimizing the amount of data that is transferred but rather the number of RSA encryptions and decryptions that need to be performed. Because RSA are computationally very expensive.

@19chris9 7 ай бұрын

Great video :)

@pratikkore7947 7 ай бұрын

you watched a 20 min video in 2 mins?

@azrobbins01 7 ай бұрын

@@pratikkore7947 Quick comments help with the algorithm and you can always delete or edit them later if you change you mind. I always click the "Like" button before I watch a video just because I am sure I will like by the end. I can always change it later if I change my mind.

@kompetop 7 ай бұрын

thé dulux transféré wit' tigres

@oleg4966 7 ай бұрын

There's something I still don't get from this explanation. Alice has, by default, transferred all public keys to Bob. What's to stop Bob from reading all of the messages that Alice sent him?

@merxj 7 ай бұрын

Bob does not know d so can't get P0. He can get P1 because of the way V was calculated. Check how he gets P1 at 11:36 and try to do it with P0. It doesn't work.

@fixinah Ай бұрын

Yeah, this math ain't going to be mathing at the end of a dinner with drinks.

@MOAB_MOAB 7 ай бұрын

By the time he got to "k"... I already knew the answer... And the answer is "no"

@Czeckie 7 ай бұрын

13:04 ish: the formula for m* is wrong. Then the computation for m1 is wrong. But everything is saved because when he computes m*, he uses a different and also wrong formula for it and miraculously gets the expected result. lol

@GhostEmblem 7 ай бұрын

When I studied computer science we never learned these kinds outside fourier transform, public private key encryption and error correction code. We spent so much time on development life cycles every year and business stuff they never even barly taught us coding they just gave us coding assignments and told us to build it by next week. I swear when it came to the actual things I wanted to learn they stopped after the basics and figured that was enough for us to figure out the rest on our own. But there was non stop repetative business bullshit repeating the same crap every year. Certainly the basics were extremely useful but I feel like I'm self taught most of the time and dont know anything advanced. Never heard of most of the stuff on this channel.

@sthex4640 7 ай бұрын

That's more or less the point of enrolling to "studies" - it's a more narrow look at a domain than highschool, but still a broad look at CS as a whole. If they focus on coding, the database-interested guys will complain. If they focus on networking, the ML-interested guys will complain. And if they focus on maths, everyone will complain :-) It really is up to the student to choose what to focus on at home, even though they can't score higher than an A, but this is how they shape their futures in IT.

@wbfaulk 7 ай бұрын

When I was studying computer science, it was very focused on theoretical subjects, generally including practical applications of those subjects, but almost nothing business or project-management oriented. I studied at a traditional university about 30 years ago. I'd be curious to know what type of institution you studied at, and when.

@AySz88 7 ай бұрын

I am also curious. I'm afraid this sounds like a specific job or trade prep program, catering to the training needs of a specific position for particular companies, rather than a "computer science" program. If the institution placed excessive emphasis on the job at the end, I imagine this experience is what you'd get. To be clear, that's not inherently bad except it seems you were given the wrong idea of what you were getting into. A job focused program is usually called something else, like a "coding boot camp".

@GhostEmblem 7 ай бұрын

It was Greenwich university England London I finished 3 years ago and before that I studied at Middlesex university for 2 years and transferred. It was the same at both places (Middlesex was worse though). No it wasn't a business course. No it wasn't a shady university. Yes they were proper Computer science degree courses. Yes they are traditional universities. No I didn't study 30 years ago, I studied 3 years ago.

@AySz88 7 ай бұрын

Checking their program online, it's narrower than what I'd expect for "computer science", and IMO mixes in a lot of what's better labeled as information technology than computer science. It's already a short 3-yr full time program, plus the last year is project focused as you mentioned. The most advanced CS-sounding class is optional in year 2, "Data Structures and Algorithms", and would usually be a prerequisite for topics like in this video. Their specializations are only "Information Systems or Networking" and their course selection seems to reflect that they don't really seem to have expertise in other things. For an example comparison, look at Cornell University and their Computer Science "Vectors". If you're interested in learning those topics (outside of any degree), perhaps Google for and browse courses' syllabuses and look for lectures following those lesson outlines. Considering prerequisites, start around 1.5 years into the program, with 2000 and 3000 level courses, before the more advanced Vectors. (Note that the final year at Cornell is also project focused, so don't feel too "behind".)

@kompetop 7 ай бұрын

ach so

@meguellatiyounes8659 7 ай бұрын

can talk about package managers and dependency solvers ?

@provladxxx01 7 ай бұрын

Люблю ваши видосы ❤

@nealpatel9869 7 ай бұрын

🎉

@ImmortalDuke 7 ай бұрын

Data that

@JoseMartinez-jk8db 7 ай бұрын

How are you, master every time you and your potentialities a million! I am going a little out of context to ask you to please tell me if you have a channel, a video that teaches how to change or slightly alter the public IP of our computer (the one that represents us on the Internet) without using VPN because the change is slight (or be it in the same city or even in the same community) but different from the initial one.

@randallanderson4999 7 ай бұрын

Dear Computerphile: I'm writing you to let you know why I unsub'd you. I have watched KZbin for over 15 years, and your channel for years. For each channels' videos I have watched I give a Thumbs Up before I even watch the video. Occasionally I have even commented to get the ratings up. Now KZbin has blocked my access, because I use an Adblocker. I'm sorry you are the one to lose because I will not be extorted by this company. UoPTucson

@poopsmcgee69 6 ай бұрын

might look into something called "KZbin reVanced"... as far as I can tell, it only works for mobile devices and it's a bit of a pain to set up... but it's working fine for me. Knock on wood, haven't been blocked from anything on KZbin for using it yet.