Oblivious Transfer - Computerphile

Поділитися
Вставка
  • Опубліковано 10 гру 2024

КОМЕНТАРІ • 104

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

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

  • @nekojibril
    @nekojibril Рік тому +19

    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 Рік тому +6

      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 Рік тому +11

      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.

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

  • @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!

  • @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!

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

  • @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!

  • @azrobbins01
    @azrobbins01 Рік тому +11

    Espresso machine right on your desk! Nice!

  • @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?

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

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

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

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

  • @gustafsundberg
    @gustafsundberg Рік тому +3

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

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

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

  • @kompetop
    @kompetop Рік тому +1

    we are impressed

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

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

  • @kylelynch5425
    @kylelynch5425 Рік тому +4

    Is this used in zero-knowledge rollups at all?

  • @scaredyfish
    @scaredyfish Рік тому +1

    Can you explain this in terms of some coloured liquids?

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

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

  • @doktormozg
    @doktormozg Рік тому

    Good stuff

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

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

  • @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".)

  • @MOAB_MOAB
    @MOAB_MOAB Рік тому

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

  • @brandonhouse7446
    @brandonhouse7446 8 місяців тому +1

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

  • @kompetop
    @kompetop Рік тому +1

    ach so

  • @tomoki-v6o
    @tomoki-v6o Рік тому

    can talk about package managers and dependency solvers ?

  • @George-Francis
    @George-Francis Рік тому +1

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

  • @provladxxx01
    @provladxxx01 Рік тому

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

  • @ImmortalDuke
    @ImmortalDuke Рік тому

    Data that

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

  • @FloydMaxwell
    @FloydMaxwell Рік тому

    Oblivious Transfer was clearly designed by a married man. 🙂

  • @fixinah
    @fixinah 8 місяців тому

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

  • @blaisepascal_fr
    @blaisepascal_fr Рік тому +1

    🎉

  • @randallanderson4999
    @randallanderson4999 Рік тому +1

    Dear Computerphile:
    I'm writing you to let you know why I unsub'd you. I have watched UA-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 UA-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 "UA-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 UA-cam for using it yet.

  • @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 Рік тому

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