Garbled Circuits - Computerphile

Going hand in hand with Oblivious Transfer is 'Garbled Circuits' - a way of using logic gates to carefully share information. Dr Tim Muller explains.
/ 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

[@alegian7934]

I feel like you should've elaborated the basic idea of oblivious transfer. which part of it is oblivious? what does the "rich people table" example look like, using an oblivious computation? I am struggling to translate the T0 and T1 into concrete user inputs, even though the explanation is very thorough

[@Imperial_Squid]

This topic feels close to zero knowledge proofs, which might be a good (if complex) topics for here or numberphile if you haven't covered them already!

[@TheJamesM]

I believe they've been covered on both Computerphile and Numberphile, but I'm sure there's always more to say.

[@Petertronic]

Dr Tim's explanations are so good, hope to see more videos with him.

[@OneOfThePetes]

I read it at first as "Garbled Biscuits"!

[@walrusbyte263]

Is that kinda like biscuits and gravy, but all mixed together?

[@Richardincancale]

I read your comment as Garibaldi Biscuits!

[@borregoayudando1481]

yum, computer chips

[@MNbenMN]

Gargled Crickets?

[@walrusbyte263]

Garbed croquet???

[@user-go5ri2yg5f]

But what's stopping the evaluator from entering both wire values into the circuit, doing the decryption of the result, and checking if the two results are the same? If the results are the same he learns that the garbler provided "0", if they are different that means the garbler provided "1". Am I missing something?

[@maximevorwerk1297]

The evaluator only knows one of each value pair because the other one only provides one of his, and the evaluator gets his by oblivious transfer, which only gives him one (8:30 in the video).

[@user-go5ri2yg5f]

@@maximevorwerk1297 Got it, thanks.

[@topherthe11th23]

3:55 - What Tim is saying here isn't true. If the value I supply to the AND circuit is "0" and I can see the output "0", I have no idea what the other person's input was. It could have been either "0" or "1".

[@TheJamesM]

The AND gate has to be hosted by one party or the other, so they will necessarily see the other party's input. I believe that's what this technique is designed to avoid.

[@abhishekraj4393]

00:02 Garbled circuits enable secure multiparty computation. 01:29 Oblivious transfer and garbled circuits for secure computation. 02:57 Understanding the working of a simple Boolean circuit 04:21 Garbled circuits involve wire values for true and false, enabling secure computation. 06:05 Symmetric encryption using combined key values 07:52 Utilizing garbled circuits for encryption and output determination based on specific conditions. 09:07 Decryption based on value combinations for one of four rows. 10:26 Garbled Circuits use symmetric encryption but face efficiency challenges

[@DataJuggler]

I think asking the waiter to split the check would be easier than this.

[@drdca8263]

I feel like maybe the AND gate is slightly too small of a computation? If one of the players chooses 1, then they will always learn what option the other player picked, because the result of the AND gate will always be the other player’s number. It seems like for such a protocol to make sense, there has to be multiple possible inputs that each player could provide, which would lead to the same final outcome, regardless of the input provided by at least one of the other players? Edit: ah! The reason an AND gate was used as an example, is because it is a basic building block of the actual use-cases. Ok. Hm, so, why does this stop being an issue in larger cases, if they are all made up of parts like this? I guess if the values that are encrypted are not values where the one decrypting knows which is 1 and which is 0? And then it just goes into the next layer. Ok, that seems to make sense.

[@Faladrin]

Well, the nature of the rich man's table problem also always gives you some info about the other people. If you are not the richest then you know the richest has more than you. If you are the richest, you know you have more than the rest. This information is always obtained by the answer. This is the clue that I think isn't well said in the video. The point of garbled circuits isn't to hide information you would obtain from the answer, only information you would obtain from the input (if you could see it).

[@drdca8263]

@@Faladrin Right! My point being that in this case, for some possible inputs you could give, from the final result, you obtain *all* of the information about their input. I was thinking “in order to illustrate that the only(?) information you get about the inputs, is whatever is implied about them purely from knowing the output, then there should be some information about the inputs which is not revealed in the output, and which the protocol doesn’t reveal.”. But, I think it makes sense to do it with a single gate and not satisfy this desideratum, if doing it with 2 gates would be too long. ... though I suppose you are right that in the millionaire problem, you could obtain an answer to any question of the form “is it larger than x?”, and so doing the protocol repeatedly would allow you to quickly determine an honest participant’s number. Though, that wouldn’t let you see their number through dishonestly running it only once, only a single bit about it.

[@alejandrocesarcaldi1334]

Run, Logan! Run! Sorry. Had to do it.

[@MetalMilitia072583]

I read this Gar Bled 😂

[@danielemur]

Build a circuit to compute garbled circuits out of garbled circuits

[@elliotgillum]

🎉

[@2treeman435]

omg same

[@zoltannagy4258]

Milyen sokoldalú ez a Puzsér 😀

[@busterfranken9105]

Hey hey to whomever is in charge! I run a global AI for Good community crowdsourcing AI solutions for impact organizations like Stanford, Greenpeace, ESA - would love to chat challenge-based learning with you, is there any way we can get into contact?

[@misterhat5823]

If you truly worked for "organizations like Stanford, Greenpeace, ESA," you'd be able to contact the channel owner without relying on leaving a comment.