Garbled circuit

<p>Garbled circuit is a <a href="/facts/Cryptographic_protocol/0WuyTkFo">cryptographic protocol</a> that enables two-party <a href="/facts/Secure_multi-party_computation/7xJbbvIo">secure computation</a> in which two mistrusting parties can jointly evaluate a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> over their private inputs without the presence of a trusted third party. In the garbled circuit protocol, the function has to be described as a <a href="/facts/Boolean_circuit/TwhfJp0q">Boolean circuit</a>.
</p><p>The history of garbled circuits is complicated. The invention of garbled circuit was credited to <a href="/facts/Andrew_Yao/F5AHrY0e">Andrew Yao</a>, as Yao introduced the idea in the oral presentation of a paper in <a href="/facts/Symposium_on_Foundations_of_Computer_Science/t0BvR59t">FOCS</a>'86. This was documented by <a href="/facts/Oded_Goldreich/Ufn1bqW7">Oded Goldreich</a> in 2003. The first written document about this technique was by Goldreich, <a href="/facts/Silvio_Micali/IxgCplaX">Micali</a>, and
<a href="/facts/Avi_Wigderson/CVHaUAdI">Wigderson</a> in <a href="/facts/Symposium_on_Theory_of_Computing/xsemn7kG">STOC</a>'87. The term "garbled circuit" was first used by Beaver, Micali, and <a href="/facts/Phillip_Rogaway/hYhbH8V5">Rogaway</a> in STOC'90. Yao's protocol solving <a href="/facts/Yao%27s_Millionaires%27_Problem/2tejhzlb">Yao's Millionaires' Problem</a> was the beginning example of secure computation, yet it is not directly related to garbled circuits.
</p>

Garbled circuit open-in-new

Garbled circuit