I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. However, I can only seem to locate the extended abstract which lacks proofs and does not seem to mention garbled circuits. It only appears to define useful properties for solving the problem and state several theorems without proof. A complete version of the paper is mentioned at the end of this extended abstract, but I cannot locate it. Is the complete version under a different name?

I have already found expositions that explain garbled circuits. At this point I am interested in finding the complete paper, if possible.

  • $\begingroup$ Is your goal to find the full paper, or to learn the ideas of Yao's garbled circuits construction? If the latter, there are lots of expositions of it (in cryptography lecture notes, textbooks, more recent papers). Which are you looking for? $\endgroup$
    – D.W.
    Jun 14 '14 at 18:10
  • $\begingroup$ I have found expositions that explain garbled circuits, but I am also interested in finding the complete paper. $\endgroup$ Jun 14 '14 at 18:13
  • 1
    $\begingroup$ Complete versions don't always exist. If you can't find it, it's probably not there. $\endgroup$ Jun 14 '14 at 23:37
  • 2
    $\begingroup$ Interesting. In the bibliography of the Turing award page it says that garbled circuits were only implicit in the paper, and that he only introduced them explicitly in the talk he gave at the conference. amturing.acm.org/bib/yao_1611524.cfm#bib_6 $\endgroup$ Jun 15 '14 at 13:04
  • 1
    $\begingroup$ Please five a full reference; it may be important for a question like this. $\endgroup$
    – Raphael
    Jul 15 '14 at 13:09

Garbled circuits were only implied by the extended abstract. They were only explicitly introduced in the talk given by Andrew Yao at the conference.

This is clear from a footnote on the Turing Award Page:

The first of these two papers introduces secure function evaluation, and gives a > protocol for the famous Millionaires’ Problem. In talks related to these papers > Yao introduced a technique for secure computation known as garbled circuits.

which may be found here: http://amturing.acm.org/bib/yao_1611524.cfm#bib_6

Credit is due to Wandering Logic for giving this very helpful answer in the comments above.


Wikipedia now has a brief survey of the history of garbled circuits with reference to published materials:



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.