Oblivious Transfer - Computerphile

แชร์
ฝัง
  • เผยแพร่เมื่อ 18 พ.ย. 2024

ความคิดเห็น • 105

  • @Nerothe42
    @Nerothe42 ปีที่แล้ว +23

    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
      @ladnir ปีที่แล้ว +2

      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
    @jonglass458 ปีที่แล้ว +107

    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
      @snickers10m ปีที่แล้ว +9

      Awesome question! Sounds like a research topic!

    • @Gvozd111
      @Gvozd111 ปีที่แล้ว +5

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

    • @gazehound
      @gazehound ปีที่แล้ว +6

      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
      @gazehound ปีที่แล้ว +3

      ​@@snickers10mNo research paper needed 😁

    • @snickers10m
      @snickers10m ปีที่แล้ว +5

      ​@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
    @rosuav ปีที่แล้ว +30

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

  • @alexgravenor
    @alexgravenor ปีที่แล้ว +9

    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
    @gianluca.g ปีที่แล้ว +11

    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.

  • @yoyofargo
    @yoyofargo ปีที่แล้ว +4

    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.

  • @heinenrby7600
    @heinenrby7600 ปีที่แล้ว +6

    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!

  • @mr.incognito9100
    @mr.incognito9100 ปีที่แล้ว +9

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

    • @snickers10m
      @snickers10m ปีที่แล้ว +2

      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!

  • @nekojibril
    @nekojibril ปีที่แล้ว +18

    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
      @ph1ber ปีที่แล้ว +5

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

    • @sanchopanza9907
      @sanchopanza9907 ปีที่แล้ว +10

      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.

  • @azrobbins01
    @azrobbins01 ปีที่แล้ว +11

    Espresso machine right on your desk! Nice!

  • @cmilkau
    @cmilkau ปีที่แล้ว +9

    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.

  • @ed.puckett
    @ed.puckett ปีที่แล้ว +4

    [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
      @gazehound ปีที่แล้ว

      Yes, he got the definition wrong unfortunately.

  • @gustafsundberg
    @gustafsundberg ปีที่แล้ว +3

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

  • @freman
    @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
      @professorpwerrel ปีที่แล้ว +2

      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
      @ladnir ปีที่แล้ว

      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.

  • @DJClintB
    @DJClintB ปีที่แล้ว +9

    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

  • @Primalmoon
    @Primalmoon ปีที่แล้ว +2

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

  • @Amonimus
    @Amonimus ปีที่แล้ว +4

    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
      @ph1ber ปีที่แล้ว +3

      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
      @Amonimus ปีที่แล้ว +1

      @@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
      @Faladrin ปีที่แล้ว

      @@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
      @Amonimus ปีที่แล้ว

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

    • @snickers10m
      @snickers10m ปีที่แล้ว +1

      ​​​​​​@@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.

  • @calvincrady
    @calvincrady ปีที่แล้ว +2

    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
      @Faladrin ปีที่แล้ว

      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
      @leoschafer5172 ปีที่แล้ว +2

      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).

  • @gianlucalocri
    @gianlucalocri ปีที่แล้ว +6

    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
      @snickers10m ปีที่แล้ว +4

      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
    @kylelynch5425 ปีที่แล้ว +4

    Is this used in zero-knowledge rollups at all?

    • @misterhat5823
      @misterhat5823 ปีที่แล้ว +4

      I got zero knowledge from it.

  • @kompetop
    @kompetop ปีที่แล้ว +1

    we are impressed

  • @scaredyfish
    @scaredyfish ปีที่แล้ว +1

    Can you explain this in terms of some coloured liquids?

    • @javen9693
      @javen9693 ปีที่แล้ว

      the pee pee algorithm

  • @igson
    @igson ปีที่แล้ว

    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.

  • @77dreimaldie0
    @77dreimaldie0 ปีที่แล้ว +2

    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
      @snickers10m ปีที่แล้ว +1

      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
      @77dreimaldie0 ปีที่แล้ว

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

    • @snickers10m
      @snickers10m ปีที่แล้ว

      ​@@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
      @CD4017BE ปีที่แล้ว

      @@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.

  • @oleg4966
    @oleg4966 ปีที่แล้ว

    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
      @merxj ปีที่แล้ว +1

      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.

  • @kompetop
    @kompetop ปีที่แล้ว +1

    thé dulux transféré wit' tigres

  • @MOAB_MOAB
    @MOAB_MOAB ปีที่แล้ว

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

  • @doktormozg
    @doktormozg ปีที่แล้ว

    Good stuff

  • @19chris9
    @19chris9 ปีที่แล้ว +3

    Great video :)

    • @pratikkore7947
      @pratikkore7947 ปีที่แล้ว +3

      you watched a 20 min video in 2 mins?

    • @azrobbins01
      @azrobbins01 ปีที่แล้ว +4

      @@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.

  • @GhostEmblem
    @GhostEmblem ปีที่แล้ว +11

    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
      @sthex4640 ปีที่แล้ว +5

      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
      @wbfaulk ปีที่แล้ว +1

      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
      @AySz88 ปีที่แล้ว +1

      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
      @GhostEmblem ปีที่แล้ว +1

      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
      @AySz88 ปีที่แล้ว +3

      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
    @kompetop ปีที่แล้ว +1

    ach so

  • @brandonhouse7446
    @brandonhouse7446 8 หลายเดือนก่อน +1

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

  • @Czeckie
    @Czeckie ปีที่แล้ว

    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

  • @George-Francis
    @George-Francis ปีที่แล้ว +1

    I watched the whole thing and don't understand a single thing.

  • @randallanderson4999
    @randallanderson4999 ปีที่แล้ว +1

    Dear Computerphile:
    I'm writing you to let you know why I unsub'd you. I have watched TH-cam 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 TH-cam 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

    • @PoopCop
      @PoopCop ปีที่แล้ว

      might look into something called "TH-cam 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 TH-cam for using it yet.

  • @tomoki-v6o
    @tomoki-v6o ปีที่แล้ว

    can talk about package managers and dependency solvers ?

  • @JoseMartinez-jk8db
    @JoseMartinez-jk8db ปีที่แล้ว

    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.

  • @ImmortalDuke
    @ImmortalDuke ปีที่แล้ว

    Data that

  • @fixinah
    @fixinah 7 หลายเดือนก่อน

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

  • @FloydMaxwell
    @FloydMaxwell ปีที่แล้ว

    Oblivious Transfer was clearly designed by a married man. 🙂

  • @blaisepascal_fr
    @blaisepascal_fr ปีที่แล้ว +1

    🎉

  • @provladxxx01
    @provladxxx01 ปีที่แล้ว

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

  • @haydo8373
    @haydo8373 ปีที่แล้ว

    Ooo

  • @Locane256
    @Locane256 ปีที่แล้ว

    Christ that was hard to watch - I was lost basically 6 minutes in. Not a mathematician though so maybe this video isnt meant for me.

  • @hughegentry8255
    @hughegentry8255 ปีที่แล้ว +8

    When it comes to science communication this bloke is no Richard Feynman.

    • @jonathangjertsen3450
      @jonathangjertsen3450 ปีที่แล้ว +11

      hey man, that's cool, next time, keep it to yourself 👍

    • @rosameltrozo5889
      @rosameltrozo5889 ปีที่แล้ว

      @@jonathangjertsen3450no

    • @VideosVlogsThatsIt
      @VideosVlogsThatsIt ปีที่แล้ว

      Lol cringe loser getting mad on the internet

    • @misterhat5823
      @misterhat5823 ปีที่แล้ว +3

      @@jonathangjertsen3450 It's a true statement. Quit whining.

    • @jonathangjertsen3450
      @jonathangjertsen3450 ปีที่แล้ว +6

      @@misterhat5823 Not really. It's an opinion stated in the haughtiest most obnoxious way possible. Absolutely embarrassing for all parties involved

  • @deenaxic9134
    @deenaxic9134 11 หลายเดือนก่อน

    This is an example of where Computer Scientists have too much funding to research in meaningless things.

  • @johnsenchak1428
    @johnsenchak1428 ปีที่แล้ว +2

    BORING

    • @misterhat5823
      @misterhat5823 ปีที่แล้ว

      Not boring, but I certainly couldn't follow it.

  • @SwordQuake2
    @SwordQuake2 ปีที่แล้ว +2

    3:54 that has nothing to do with computer science. It's basic mathematics...