The Yao Construction and its Proof Of Security
Why Cryptography Stack Exchange recommends it
Cryptography Stack Exchange users, including Lindell himself, point people to it as an authoritative walkthrough of Yao's garbled circuits and the hybrid-argument proof technique.
Recommended by 1 people across 1 different months, 2016 to 2019.
What it is
A winter school lecture by Prof. Yehuda Lindell of Bar-Ilan University on Yao's garbled circuit construction for secure two-party computation and its proof of security. It covers the construction and the hybrid argument used in the security proof.
What people said
Recommends Yehuda Lindell · 2016-05 · Cryptography Stack Exchange · on “Yao's Garbled circuit: Does Bob ever see the circuit?”
You CANNOT use XOR based encryption here. So, you are reading from a bad source. I suggest reading [LINK] or watching this video [this video]
Cites Mikero · 2016-07 · Cryptography Stack Exchange · on “What exactly is a "garbled circuit"?”
A circuit is just a way to represent a computation. There is nothing specifically cryptographic about a circuit. It just means a straight-line computation (no looping or flow-control constructs) consisting of just operations on bits , like AND, OR, NOT. A garbled circuit is a way to "encrypt a computation" that reveals only the output of the computation, but reveals nothing about the inputs or any intermediate values. We use the term "circuit" because garbled circuits work by taking the computation you care about, expressed as a circuit , and then doing some cryptographic stuff for each operation (AND, OR, NOT) in the circuit. If we want to be a little more precise, a "garbling scheme" consi
Cites andy · 2019-06 · Cryptography Stack Exchange · on “Induction is problematic in computational cryptography - Why?”
In Dr. Lindell's lecture The Yao Construction and its Proof Of Security [this video] , in briefly explaining the hybrid argument, he makes the statement that mathematical induction is a problem in computational cryptography. He is explaining that a hybrid argument is "like" mathematical induction, but not the same. As far as I know, mathematical induction and hybrid arguments are not the same because for a hybrid argument, you need a finite ( $k$ ) sequence of distributions for the proof to work (that is, eventually bounding the sum of the $k$ negligible differences by the max difference * $k$ , which is negligible). For an infinite sequence, this doesn't work. Does anyone know what Dr. Lindell m